How does chain code work

Computer Vision, Chapter 2: Chain Code. The new chain code with 4 directions = chain code or crack code

Transcript

1 Computer Vision, Chapter 2: Chain Code Copyright by V. Miszalok, last update: The new chain code = chain code or crack code The chain code algorithm The algorithm at the edge of the picture Starting point finder The matrix of vertical cracks and label matrix inside and outside borders Perimeter, area, center of gravity, circumscribing rectangle The new chain code with 4 directions = Chain Code or Crack Code = West = North = South = East Modern code for area delimitations, based on a cell (x, y), the delimitation as a chain of directed cracks = East, = south, = west, = north. The code takes the boundary relation into account and always delivers a closed crack chain with end point == start point == (x, y). Property: Number of south cracks = Number of north cracks Property 2: Number of east cracks = Number of west cracks Property 3: Extent of area = number of cracks. Convention: start pixels always at the first, topmost transition from background to foreground. Convention 2: Start crack is always south, i.e. the direction of rotation is always such that the foreground is on the left and the background on the right. Example: Image b = starting point = end point = cell (/) crack chain = south, west, south, east, south, east, north, east, north, north, west, west = swsosononnww Often one uses English south, east, north , west with the abbreviations s, e, n, w. Then the complete chain code of the area is: (/) swsesenennww perimeter = number of cracks = 2, area = number of enclosed pixels = 6 Example 2: Image b = area: (/) senw, perimeter = 4, area = area 2 : (2 /) ssennw, perimeter = 6, area = 2 This chain code can be easily extended to 3D grids. He then gets two additional directions backwards = b and forwards = f. B points in the positive and f in the negative Z-direction, i.e. b in the display and f out of the display. Example: (,,) esb is the code for a path that leads from (,,) to (,,) for a cube along the CH top front, the CV front right and the CZ bottom right. See: ../../../ Samples / CV / StraightLine3D / straight_line3D.htm ../../../ Samples / CV / StraightLine3D / straight_line3D.exe. The laws of the 2D chain code also apply accordingly in 3D. Therefore, the following text is limited to the 2D chain code.

2 2 The chain code algorithm is the most modern form of area delimitation. When a contour follower = contour finder = tracer = boundary tracing is mentioned, the chain code algorithm is usually meant today. There are two versions of the algorithm:) with switch-case: longer but easy to understand (will be presented in the following). 2) with modulo 4 operator: Very compact but not so easy to understand: ../../ samples / cv / chaincode / chain_code.htm. See also the lecture by Prof. Kovalevsky: ../../../ Samples / CV / ChainCode / chaincode_kovalev_e.htm Also try out the samples: ../../../ Samples / CV / StraightLine / straight_line. htm ../../../ Samples / CV / StraightLine / straight_line.exe ../../../ Samples / CV / StraightLine3D / straight_line3D.htm ../../../ Samples / CV / StraightLine3D / straight_line3D.exe. Task: Given is a binary image b [ysize, xsize] with the gray values ​​= background and = foreground. In the image there should be at least one foreground pixel with the gray value whose upper left corner can serve as the starting point c [y, x] and whose left edge cv [y, x] can serve as a vertical starting crack in the south. The start to the south means that the foreground must always be on the left side of the directed cracks. It must also be known whether the 4 or 8 neighborhood applies in the foreground. Find the complete chain code of the boundaries of this area. The algorithm for neighborhoods of 4 keys first after the pixel to the left before the current crack. If it is, then turn left, done. If it is, then feel for the pixel to the right of the current crack. Is it, go straight, done. Is it, go right, done. In Pseucode: if (pixel front left == background) turn left; else if (pixel right front == background) go straight ahead; else turn right. 4-way case distinctions with switch (last_crack), if the last crack points to a cell (x, y): case 'e': if (b [y-, x] ==) goto n; else if (b [y, x] ==) goto e; else goto s; case 's': if (b [y, x] ==) goto e; else if (b [y, x-] ==) goto s; else goto w; case 'w': if (b [y, x-] ==) goto s; else if (b [y-, x-] ==) goto w; else goto n; if (b [y-, x-] ==) goto w; case 'n': else if (b [y-, x] ==) goto n; else goto e;

3 The 4-way algorithm in C #, given the starting point Point start: 3 System.Text.StringBuilder cracks = new System.Text.StringBuilder (); cracks.append ('s'); Int32 x = start.x; Int32 y = start.y +; Char last_crack = 's'; {switch (last_crack) {case 'e': if (b [y-, x] ==) goto n; if (b [y, x] ==) goto e; goto s; case 's': if (b [y, x] ==) goto e; if (b [y, x-] ==) goto s; goto w; case 'w': if (b [y, x-] ==) goto s; if (b [y-, x-] ==) goto w; goto n; case 'n': if (b [y-, x-] ==) goto w; if (b [y-, x] ==) goto n; goto e; e: last_crack = 'e'; cracks.append ('e'); x ++; continue; s: last_crack = 's'; cracks.append ('s'); y ++; continue; w: last_crack = 'w'; cracks.append ('w'); x--; continue; n: last_crack = 'n'; cracks.append ('n'); y--; continue; while (x! = start.x y! = start.y); The algorithm in the neighborhood of 8 key first after the pixel to the right before the current crack. If it is, then turn right, done. If it is, then feel for the pixel to the left of the current crack. Is it, go straight, done. Is it, go left, done. in pseucode: if (pixel right front == foreground) turn right; else if (pixel front left == foreground) go straight ahead; else turn left. 8 case distinctions with switch (last_crack), if the last crack points to a cell (x, y): case 'e': if (b [y, x] ==) goto s; else if (b [y-, x] ==) goto e; else goto n; case 's': if (b [y, x-] ==) goto w; else if (b [y, x] ==) goto s; else goto e; case 'w': if (b [y-, x-] ==) goto n; else if (b [y, x-] ==) goto w; else goto s; if (b [y-, x] ==) goto e; case 'n': else if (b [y-, x-] ==) goto n; else goto w; The 8 algorithm in C #, given the starting point Point start: System.Text.StringBuilder cracks = new System.Text.StringBuilder (); cracks.append ('s'); Int32 x = start.x; Int32 y = start.y +; Char last_crack = 's'; {switch (last_crack) {case 'e': if (b [y, x] ==) goto s; if (b [y-, x] ==) goto e; goto n; case 's': if (b [y, x-] ==) goto w; if (b [y, x] ==) goto s; goto e; case 'w': if (b [y-, x-] ==) goto n; if (b [y, x-] ==) goto w; goto s; case 'n': if (b [y-, x] ==) goto e; if (b [y-, x-] ==) goto n; goto w; e: last_crack = 'e'; cracks.append ('e'); x ++; continue; s: last_crack = 's'; cracks.append ('s'); y ++; continue; w: last_crack = 'w'; cracks.append ('w'); x--; continue; n: last_crack = 'n'; cracks.append ('n'); y--; continue; while (x! = start.x y! = start.y);

4 4 The algorithm was formulated on the basis of a binary image. It also works on every gray value image b with a threshold threshold, if all accesses to the pixels are changed as follows: in a neighborhood of 4: if (b [..., ...] ==) replace with: if (b [.. ., ...] = threshold) Works on color images only if a color criterion has been formulated which clearly separates the foreground from the background. Such a color criterion is usually difficult to find. You can find building instructions on this subject at ../../../ c_cvcis / c2_chaincode / cvcischaincode_d.htm, or you can download an executable EXE: ../../../ c_cvcis / c2_chaincode / cvcischaincode.exe. You can find a lecture by Prof. Kovalevsky on chain code at: ../../../ samples / cv / chaincode / chaincode_kovalev_e.htm You can find a compact formulation of the Kovalevsky algorithm at: ../../ .. /samples/cv/chaincode/chain_code.htm and the appropriate demo program at: ../../../ samples / cv / chaincode / chain_code.exe The algorithm at the edge of the screen Both algorithms fail when the chaincode hits one the four edges of the image, because they feel for nonexistent pixels outside the image matrix. Let xsize == bmp.width = number of columns. Let ysize == bmp.height = number of lines. Then: left edge of the picture: x ==; right edge of the image: x == xsize- upper edge of the image: y ==; lower edge of the picture: y == ysize- There are two solutions to the picture edge problem: The columns and xsize- as well as the rows and ysize- are set arbitrarily on the background and the rt existing image information is destroyed. The algorithm can now never reach the edge of the image. 2. You check the current indices x and y and if x == or x == xsize or if y == or y == ysize you force the direction changes necessary at the edge of the image without pixel tests. Contour tracker in a neighborhood of 4 with image edge treatment: switch (last_crack) {case 'e': if (x == xsize b [y-, x] ==) goto n; if (y == ysize b [y, x] ==) goto e; goto s; case 's': if (y == ysize b [y, x] ==) goto e; if (x == b [y, x -] ==) goto s; goto w; case 'w': if (x == b [y, x -] ==) goto s; if (y == b [y-, x -] ==) goto w; goto n; case 'n': if (y == b [y-, x -] ==) goto w; if (x == xsize b [y-, x] ==) goto n; goto e; Contour tracker for 8 neighborhoods with image edge treatment: switch (last_crack) {case 'e': if (x == xsize) goto n; if (y && b [y, x -] ==) goto w; if (b [y, x] ==) goto s; goto e; case 'w': if (x ==) goto s; if (y> && b [y-, x-] ==) goto n; if (b [y, x -] ==) goto w; goto s; case 'n': if (y ==) goto w; if (x

5 Starting point finder 5 It is easy to find a first starting point for the first crack code of the first area in an unknown image. Just take the upper corner c (x, y) of the first vertical crack that appears at the transition from one to one. Let xsize == bmp.width = number of columns. Let ysize == bmp.height = number of lines. Then you can find the starting point in an image matrix b of size b [ysize, xsize] like this: // left edge of the image: x ==; right edge of the image: x == xsize- (== bmp.width -) // upper edge of the image: y ==; lower edge of the picture: y == ysize- (== bmp.height-) for (y =; y 255! * / Char last_crack; for (y =; y

6 6 Inner and outer boundaries An area always has exactly one outer boundary = outer boundary. It can have one, two or more inner borders (holes). Further areas can lie within these inner boundaries, such as islands in a lake, which in turn have inner boundaries, etc. The algorithm is initially blind to the assignment of boundaries to areas. He knows e.g. not whether and which codes lie within other codes. If you consistently place the starting point in the left corner of the leftmost pixel in the top line of an area and observe the convention that all chain codes must always start with a south crack and that the area must always be on the left of the boundary during rotation , then the following applies: a) If the last crack of a chain code (last crack before the re-entry into the starting point) has a westward direction, then the code encodes an outer boundary. b) If the last chain code has an east direction, then it is an inner boundary. This distinction is not exhaustive, as it is still unknown which inner boundary belongs to which outer boundary. For this purpose, you have to number all chain codes consecutively and you have to find exactly one outer limit for each inner limit to which it belongs. Given is: a chain code of an inner boundary with the code number: j 2. any number of chain codes of inner and outer boundaries in any order with the code numbers k

7 Area The area of ​​a chain code is equal to the number of pixels it encloses. This number is negative if the code encodes an inner border (= hole). The formula for calculating the area is that for calculating the area of ​​a polygon: F = sum over all i of (x [i] - x [i +]) * (y [i] + y [i +]) / 2.If one understands the two ends of each crack as two consecutive corners of a polygon, the result is: for western cracks: x [i] - x [i +] = and y [i] = y [i +] = y = line number F = F + y; for east cracks: x [i] - x [i +] = - and y [i] = y [i +] = y = line number F = F - y; for south cracks: x [i] - x [i +] = F = F; for north cracks: x [i] - x [i +] = F = F; In summary, there is a simple calculation rule for the area of ​​a crack code: F = sum of all line numbers of all east cracks minus sum of all line numbers of all west cracks. The area of ​​a chain code is thus obtained with the correct sign, i.e. positive for outer boundaries and negative for inner boundaries. The area of ​​an area is the sum of the positive area of ​​the outer contour plus the negative areas of the holes. Example: 7 Original area = east: y = 3 area + = y area = 3 east: y = 3 area + = y area = 6 west: y = 2 area - = y area = 4 west: y = area - = y area = 3 center of gravity To calculate the center of gravity S = (xs, ys) of a chain code, imagine all pixels c2 [y, x] inside as elements of mass shrunk to their pixel center c [y + .5, x + .5] in front. xs = sum of all x-coordinates of the shrunk elements divided by their number. ys = sum of all y-coordinates of the shrunk elements divided by their number. Number of shrunk elements = number of pixels = positive area of ​​the chain code. Caution: When calculating the centers of gravity of areas with inner contours, the shrunk elements of the hole pixels must not be added together. Circumferential rectangle xmin ymin ymax xmax The circumscribing rectangle of an area encloses its outer boundary (= outer chain code) with 4 axially parallel straight lines. These straight lines are extensions of the cracks with the lowest and highest column numbers (xmin and xmax) and the lowest and highest row numbers (ymin, ymax). A circumscribing rectangle is completely defined by specifying its upper left corner Pmin = (xmin, ymin) and its lower right corner Pmax = (xmax, ymax). The real (sometimes complicated) areas are replaced by their circumscribing rectangles when quick (not necessarily exact) answers are required, such as: Question: Is a mouse pointer with the coordinate x, y within an area? Answer: No, if x xmax or y ymax. Question: Do two areas G and G2 overlap. Answer: No, if their circumscribing rectangles do not overlap. Question: Where is the center (xm, ym) of an area? Answer: xm = (xmax + xmin) / 2, ym = (ymax + ymin) / 2 The calculations in the form of a subroutine void crack_calculations (int x, int y, byte [] crack, int no) {/ * x, y = starting point; crack [.. no-] contains e, s, w, n characters; * / int x, y, xmin, ymin, xmax, ymax, i =, peri =; area =; float sx =, sy =; x = xmin = xmax = x; y = ymin = ymax = y; {if (i ++> no) break; switch (cracks [i-]) {case 'e': x ++; if (x> xmax) xmax = x; peri ++; area + = y; sx + = y * (x + .5); sy + = y * y / 2; break; case 's': y ++; if (y> ymax) ymax = y; peri ++; break; case 'w': x--; if (x