Home | Index of Lectures | << Prev | Next >> | PDF Version of this Page |
Simple Algorithms Based on Digital TopologyCopyright © by V. Kovalevsky, last update: October 24, 2011 |
Let me know what you think | |
Tracing Boundaries in 2D Images Searching a Starting Point of Tracing The Code of "Trace" in native C Image Reconstruction by Filling the Interiors of Boundaries Component Labeling in an n-Dimensional Space Skeletons in 2D and 3D |
coordinate system | directions of the Crack Code |
2 pixels Pos and Neg must be tested |
The tracing is performed in combinatorial coordinates. The program goes from one boundary point to the next one along the boundary
cracks. To recognize the next boundary crack the program tests two pixels "Pos" and "Neg" lying ahead of the
actual crack. The program calculates the coordinates of these pixels by adding the 2D vectors "Positive[direction]"
and "Negative[direction]" to the vector "P" of the actual point. The vectors are predefined as small constant
arrays. Then the program gets the gray values (or colors) of the pixels from the given image while transforming the combinatorial
coordinates "Pos" and "Neg" to standard coordinates by simply dividing them by 2 (integer division).
The direction of the next crack is then calculated depending on the two gray values simply by adding a 1 or a 3 modulo 4 to the
actual direction. Then the actual point moves along the new direction. The process stops when the starting point is reached again.
The algorithm in pseudo-code:
P.X=Start.X; P.Y=Start.Y; direction=1; // P is the current point do { Pos=P+Positive[direction]; // Pos is the positive pixel Neg=P+Negative[direction]; // Neg is the negative pixel if (image[Pos/2]==foreground) // Pos/2 is in standard raster direction=(direction+1) MOD 4; // positive turn else if (image[Neg/2]==background) // Neg/2 is in standard raster direction=(direction+3) MOD 4; // negative turn P=P+step[direction]; // a move in the new direction } while( P.X!=Start.X || P.Y!=Start.Y);
For finding a starting point of the tracing the image must be scanned raw by raw. As soon as two subsequent pixels of different colors are found the starting point is defined as the upper end point of the crack lying between the pixels.
The foreground object remains on the negative side of tracing. To avoid multiple tracing the already visited vertical cracks must be labeled. The algorithm is slightly simpler if it has to start only at a transition from the background to the foreground but not at a transition from the foreground to the background. |
Simple C and C++ have no structure like class CPoint which may be used as a 2D vector with addition. Therefore we use in the "Console" integer variables as components of a vector. The addition of vectors must be done component by component.
#define US unsigned char int POSX[4]={1,-1,-1, 1}; // move from point to positive pixel int POSY[4]={1, 1,-1,-1}; int NEGX[4]={1, 1,-1,-1}; // move from point to negative pixel int NEGY[4]={-1,1, 1,-1}; int StepX[4]={2,0,-2, 0}; // move to next point int StepY[4]={0,2, 0,-2}; int Value( US *img, int NX, int NY, int xc, int yc ) { if( xc>=0 && xc<2*NX && yc>=0 && yc<2*NY ) return img[yc/2*NX+xc/2]; return 0; // the function returns the value of the cell (xc, yc) } int Label( US *img, int NX, int NY, int xc, int yc ) { if ( (xc&1)+(yc&1)!=1 ) { printf( "Label: (%d,%d) is no crack. Stop\n",xc,yc ); return -1; } if ( xc<0 ) { printf( "Bad coordinate xc=%d. Stop\n", xc ); return -1; } img[yc/2*NX+xc/2]|=VERT; // labeling a vertical crack return 1; } int Trace( US *img, int NX, int NY, int xc, int yc ) { int cnt=0, deb=1, rv=1, x=xc, y=yc, dir=1; do // (x, y) is the current point; (PosX, PosY) and (NegX, NegY) are pixels { int PosX=x+POSX[dir]; int PosY=y+POSY[dir]; int NegX=x+NEGX[dir]; int NegY=y+NEGY[dir]; int ValPos=Value( img, NX, NY, PosX, PosY ); // value of img[Pos] int ValNeg=Value( img, NX, NY, NegX, NegY ); // value of img[Neg] if (ValPos >0) dir = (dir+1)%4; // positive turn else if (ValNeg==0) dir = (dir+3)%4; // negative turn if ( dir==1 ) rv=Label(img,NX,NY,x,y+1); //if ( dir==3 ) rv=Label(img,NX,NY,x,y-1); if ( rv<0 ) { printf( "Error at cnt=%d\n",cnt ); return -1; } x = x+StepX[dir]; y=y+StepY[dir]; cnt++; } while( (x!=xc || y!=yc) && cnt<1000 ); return cnt; }
To check whether an n-cell P of an n-space lies in the interior of an (n-1)-dimensional manifold
M it is sufficient to count the intersections of M with a ray (e.g. parallel to X coordinate axis) going from P to the border of the space.
The counting is easy to perform only if the space is a complex. Otherwise it is difficult to distinguish between intersection and
tangency.
If the curve is given as a sequence of pixels then one needs to investigate three raws of the image to distinguish between crossing
and tangency. Indeed, in the figures "intersection" and "tangency" the third raw is exactly the same.
However, when representing the image as a complex a curve becomes a sequence of alternating 0- and 1-cells. Now the mentioned
problem becomes easy since a ray consisting of pixels and vertical cracks between them can only cross a curve at a vertical crack.
A tangency is impossible.
The algorithm of filling is now very simple: before starting the filling all vertical cracks of the curve must be labeled
(in some way) in the image. In the case of an nD image the (n−1)-dimensional cells orthogonal to the chosen
coordinate axis must be labeled. The program scans the image raw by raw. It sets the logical variable fill
to FALSE
at the beginning of each raw. As soon as a labeled vertical crack (an (n−1)-cell) is encountered the variable
fill is inverted: fill=NOT fill. If fill
is TRUE the next pixel (n-cell) gets the label of the foreground, otherwise - the label of the background.
intersection | tangency | no problem in a complex |
for ( each row R parallel to X ) { fill=FALSE; for ( each n-cell C in the row R ) { if ( the first (n-1)-side of C is labeled ) fill = NOT fill; if ( fill==TRUE ) C = foreground; else C = background; } }This algorithm with some small changes is applicable also in higher dimensions.
The space is represented as an n-dimensional array S. The indices correspond to the coordinates. Each element of S contains a color. After the labeling each element of S gets (in another array L) the label of the component which it belongs to.
The naive approach: About NY^{3}/2 rewritings |
The advanced approach: About NX/2 rewritings |
The algorithm scans the image two times: after the first run each element gets in L the "root" of its component as its label. During the second run the roots are replaced by subsequent numbers. | ||
first run | second run |
for (i=0; i<|S|; i++) L[i]=i;
for (i=0; i<|S|; i++)
{ for (j=0; j Max_n]; j++) // "Max_n" is the maximum number of already visited adjacent elements
{ k=Neighbour(i, j); // "Neighbour(i, j)" the jth adjacent element of "i"
if (Adjacent(i, k) AND S[k]==S[i]) SetEquivalent(i, k, L);
}
}
SecondRun(L, |S|);
void SetEquivalent(i, k, L)
{ if (Root(i, L)>Root(k, L) ) L[Root(k, L)]=Root(i, L);
else L[Root(i, L)]=Root(k, L);
}
int Root(k, L)
{ for(int i=0; i<|L|; i++)
{ if (k==L[k]) return k;
k=L[k];
}
ErrorMessage( ); return -1;
}
void SecondRun(L, N)
{ for (int i = 0, int count=1; i<=N-1; i++)
{ int label=L[i];
if (label==i ) { L[i]=count; count++;}
else L[i]=L[label];
}
}
Skeletons in 2D and 3D |
The skeleton of a given set T of an n-dimensional
a) S has the same number of connected components as T;
b) The number of connected components of
c) Certain singularities of T are retained in S;
d) S is the smallest subset of T having the properties a) to c).
Singularities may be defined e.g. as the "end points" in a 2D image or "borders of layers" in a 3D image etc. |
This makes the parallel calculation of a skeleton to a difficult problem. |
A complex
The membership of a cell C of any dimension may be changed between the foreground T and the background B if
each of the intersections |
The algorithm consists in deleting simple cells alternately from the closing and open boundary of the foreground subset being processed. Cells considered as singularities are not deleted. Singularities may be defined e.g. as endpoints of lines in the two-dimensional case or as boundaries of "flat cakes" in the three-dimensional case.
The skeleton S thus constructed may contain both principal cells and cells of lower dimensions (b). However, it is
easily possible to transform it either to a "thin skeleton" consisting of cells of dimension less or equal
to |
The region S | Its frontier B=Fr(S) |
C=S−Simple(B) | O=OB(C) | F=C−Simple(O) | Skel=F−Simple(Fr(F)) |
original body | skeleton |
top of page: |
Last update: October 24, 2011