Milestones
| 1 | 2 | 3 |

1. Boundary extraction of Patches

The first task is to extract the boundaries of patches of an image. The image is already segmented and is of type [M x N x 3] Uint8.


a) Creation of a bitmask for each patch

To extract a boundary a bitmask of the patch of interest is needed in the form that there are ones at the patches position, and zeros else. The private function getPatchBitmask of the class SA_Image implements this.

The algorithm uses a dynamic vector of (x,y) pairs as stack of positions that have to be processed in a loop. As long as the stack vector is not empty in each loop the top position of the stack vector is evaluated (meaning, if the color at the position is the same as at the start position, a one is written into the bitmask at this position) and removed. In the same cycle the moore neighborhood is then pushed on the stack if the color on their position is the same as at the start position (which is passed to the function by parameter). A visited flag matrix is held to guarantee one visit per pixel.




b) Extraction of the boundary using the bitmask

To get the boundary of the bitmask (that represents a patch of the segmented image) it is passed to the private function getPatchBitmask of the class SA_Image.

getPatchBitmask first scans row wise through the bitmask to find the first one, which then is used as start position of the boundary.
Then the algorithm uses the following logic to trace the boundary, until the start position is reached again. A direction vector with length one is used to step along.

If the Bitmask at the position is 1 then turn (the direction vector) left if the left pixel is 1. Else go on.
If the Bitmask at the position is 0 then turn (the direction vector) right.

The first rule has the extra constraint "if the left pixel is 1" to guarantee a closed boundary (no diagonal steps) at stair regions.




c) Finalizing the first milestone

The points a) and b) show how to get a boundary from one patch. To get the boundaries of all patches another function is needed.

The public function getBoundaries of the class SA_Image scans row wise through the passed image until it reaches a pixel that has not the color [0,0,0]. For this pixel a bitmask is created using getPatchBitmask. This bitmask is first used to get the boundary (with traceBoundary) and second to set all the pixel of the Image where the bitmask is 1 to [0,0,0].
This is done until the last row of the image is scanned through.

To efficiently store the boundaries, which are [k x 2] matrices with variable k, the class SA_VectorArray is used.




Copyright © 2007 Thomas Oskam, ETH Zürich. All rights reserved.