Morphological Reconstruction
Morphological reconstruction is a powerful operation in Mathematical Morphology that inserts the concept of connectivity in images, both for binary and gray scale. The binary image reconstruction is equivalent of a painting process everyone has experienced using some painting packages using the flood fill color tool. The user picks a color and touches a white region on the image. Everything that is connected to that point will become colored. In morphology, we say that the selected point is the marker, the input image is everything and the reconstructed image are all the points that were colored. The image reconstruction can be built by an infinite sequence of dilation and intersection, until the result reaches a stability. The dilation and intersection is called conditional dilation.
In the example below, the marker is a vertical line in the middle of the image and the conditioning image is the binary image of the blobs. After applying 8 successive conditional dilations, we note that the marker gets wider, invading the conditional image, mimmicking the same behavior of the flood fill effect in the painting packages. The result of the reconstruction, shown in red in the last image is a stable result. If another conditional dilation is applied, the result is the same. Note that the red blobs are the blobs in the image that are connected to the central line (marker). So the reconstruction detects all the pixels that are connected to the markers.
G=imread('blob3.tif');
mmshow(G); ;
Bc=mmsecross;
F=mmsubm(G,G);
F(:,64)=1; %marker
mmshow(G,F); ;
F8=mmcdil(F,G,Bc,8);
mmshow(G,F8); ;
R=mmcdil(F,G,mmsecross,100);
mmshow(G,R); ;
|
Influence of the Structuring Element in the Reconstruction
What is the functionality of the structuring element in the previous example? It is responsible for the connectivity criteria. If we work with 4-connected criteria, we have to use the elementary cross and to work with 8-connected criteria, we use the elementary square.
B4=mmseshow(mmsecross(1),'EXPAND'); mmshow(B4); ; B8=mmseshow(mmsebox(1),'EXPAND'); mmshow(B8); ;
|
Is it possible to use other sizes and shapes for this structuring element. The answer is yes, as long as the structuring element is symmetric and contais the origin, the reconstruction gives usefull results.
In the example below, an image with text is reconstructed using a central marker. When a connectivity of 4 is used, only parts of the small letter o is detected, but using connectivity 8, the whole letter is detected. If a connectivity of 120 neighbors is used, by specifying a box of radius 5, all the letters within the word erosion is detected. The meaning in this case is to detect any letter and any word in the central region of the image, using connectivity 8 and 120, respectively.
F=imread('letters.tif');
M=mmsubm(F,F);
M(:,size(F,2)/2)=1;
G4=mminfrec(M,F,mmsecross);
G8=mminfrec(M,F,mmsebox);
G120=mminfrec(M,F,mmsebox(5));
mmshow(F,M);
mmshow(F,G4);
mmshow(F,G8);
mmshow(F,G120);
|
Properties of the Reconstruction:
- It is idempotent, anti-extensive, crescent
- It has all the features of an opening
- It is an algebraic opening
- It is the building block of connected operators
Designing the Markers in the Reconstruction
A question that arises is how to design the markers to be used in the reconstruction. There are three most important ways to select the markers:
- A priori information. This is the case where we know where to place the marker. For instance in the examples above, the marker was a central line in the image because we want to detect objects that are in the center of the image.
- Erosion (Open by reconstruction). In this case the fitting of the structuring element is objet is the criteria to detect or refuse an object. This is a classification machine by shape criteria.
- Subtraction (h-dome). This is for gray scale images and will be discussed later.
- Result of a complex solution towards object recognition. This is the normal procedure for object classification and recognition. The problem is simplified in finding the marker of the objects to be detected.
Marker a Priori
Detecting Objects on the Image Frame
In this example, the marker is placed in the image frame, shown in red (dilated just for the purpose of illustration). The reconstruction of the image detects all the blobs that touch the image frame. It is possible then, to subtract this from the original (top-hat) to get the blobs not touching the image frame.
F=imread('blob3.tif');
M=mmframe(F);
mmshow(F,mmdil(M,mmsebox(2)));
G1=mminfrec(M,F); % detect cells connected to border
mmshow(G1);
G2=mmsubm(F,G1);
mmshow(G2);
|
Detecting Holes of a PCB
This is another example of the same idea. The holes of the PCB below are the only objects that are not connected to the image frame.
F=mmneg(imread('pcbholes.tif'));
M=mmframe(F);
mmshow(F,mmdil(M,mmsebox(2)));
G=mminfrec(M,F);
mmshow(G);
H=mmsubm(F,G);
mmshow(H);
|
Marker From Erosion
When the markers comes from an erosion of the image, the structuring element is the shape criteria to select an object.
Detecting tall thin objects
In this example, a vertical structuring element of height 15 pixels is used. The marker (erosion) is placed only on the objects in which the structuring element fits. The input image is a binary text and the only characters which satisfy this criteria are the greek letter psi.
F=imread('letters.tif');
mmshow(F);
B=mmseline(15,90);
M=mmero(F,B);
mmshow(M);
G=mminfrec(M,F);
mmshow(G);
|
Detecting thick objects
This is another simple example of pattern detection. In this case, we are interested to detect objects which are thicker than 13 pixels. This means that we want to detect objects in which a circle of 13 pixels (radius 6) of diameter can fit.
F=imread('tools.tif');
mmshow(F);
B=mmsedisk(6);
M=mmero(F,B);
mmshow(M);
G=mminfrec(M,F);
mmshow(G);
|
Gray Scale Morphological Reconstruction
The binary reconstruction can be extended to gray scale by using the gray scale conditional dilation. In this respect the gray scale reconstruction is exactly the same as the binary reconstruction: an infinite sequence of conditional dilations of the marker conditioned to the image to reconstruct. The most used structuring elements for the reconstruction (connectivity) are the elementary cross (4-connected) and elementary box (8-connected), but as in the binary case other simmetrical structuring elements can be used. For gray scale, it is also possible to use specially designed non-flat structuring elements. As it will be explained latter, the gray scale reconstruction is the building block to design connected filters. The highlights of the gray scale reconstruction are:
- Exactly the same equation as the binary case.
- Exactly the same structuring element: most used: 4-connected and 8-connected
- Brings connectivity for gray-scale images
- Building block for gray scale connected filter
Reconstruction of a Signal
In the example below, the signal (1-D gray scale conditioning image) is part of a horizontal line of a bar code with light and dark gray stripes. The marker is a 255 pixel on the middle light gray bar. The signal is plot in black and the marker in red. After applying 4 successive conditional dilations (in green), we note that the marker gets wider, following the conditionaing image. After 4 conditional dilations (in blue), the marker goes wider but never goes up. The result of the reconstruction, shown in magenta stars is a stable result. If another conditional dilation is applied, the result remains the same. Note that the reconstructed signal enhances the middle bar, the bar where the marker was placed. If a threshold is applied to the reconstructed signal, the middle bar can be detected.
faux=imread('n2538.tif');
f=mmneg(faux(10,41:80));
m=mmsubm(f,f);
m(1,size(f,2)/2)=255;
x=1:size(f,2);
f4=mmcdil(m,f,mmsecross,4);
f12=mmcdil(m,f,mmsecross,12);
finf=mmcdil(m,f,mmsecross,250);
plot(x,f,'k', x,m,'r', x,f4,'g', x,f12,'b', x,finf,'m*');
|
2D Example - segmentating a single cell
Below is a 2-D gray scale example that repeats the same technique shown before for 1-D signal. A 255-pixel marker is placed over one blood cell in the negated blood cell image. The result of the reconstruction enhances this single blood cell because it is surrounded by dark pixels. The lightest gray pixel outside this cell in the reconstructed image has the maximum gray scale value connecting the marked cell and any other cell. Is is possible to select a particular threshold to detect the single marked cell.
f=mmneg(imread('bloodcells.tif'));
m=mmsubm(f,f);
m(100,105)=255;
mmshow(f,mmdil(m,mmsecross(3)));
rec=mminfrec(m,f);
mmshow(rec);
mmshow(mmthreshad(rec,75));
|
Another segmentation example
The same technique is applied in the example below. In this case, there is a rather difficult task to segment the roads from a gray scale scan of a map. The map was drawn mainly with dark lines. A marker is placed on a road and the reconstructed image enhances the road as all of the road pixels are surrounded by dark pixels in the same sense as in the blood cell example before. By choosing a proper threshold all the roads can be detected in the map. This example illustrate the power of the reconstruction in image segmentation.
f=imread('mapacampus.tif');
m=mmsubm(f,f);
m(55,55)=255;
m=mmdil(m,mmsebox(2));
mmshow(f,m);
rec=mminfrec(m,f);
mmshow(rec);
fbin=mmcmp(rec,'>=',230);
warning: converting from type double to uint8
mmshow(fbin);
|
Removing isolated islands
The center of the cells in the image of the blood cells are slightly whiter than the dark pixels of the cells. It is possible to cut out this brither center if a 255-marker is placed in the frame of the image. In this way the reconstructed image turns the center of the cells with the gray scale value that comes from the lightest pixel connecting any surrounding cell pixel to the center pixel of the cell.
f=imread('bloodcells.tif');
m=mmframe(f);
mmshow(f,mmdil(m,mmsebox(2)));
rec=mminfrec(m,f);
mmshow(rec);
|
Exercises
- Describe in geometric terms what kind of filtering was applied in the examples above using the letters and the tools images.
- Describe the gray-scale reconstruction using the thresholding decomposition.
- Design a labeling algorithm using the reconstruction.
- Apply the
mmlabel function in the image drawing.tif with connectivity 4 and 8 and explain the difference of the results.
mmlabel function in the image drawing.tif with connectivity 4 and 8 and explain the difference of the results.