Extract contour path from an image

Question

Let's say I have a 16x16 black & white bitmap image

Here white pixels indicate empty space and black pixels indicate filled space.

I want to extract all of it's contour lines that surround black pixels, including holes and nested contour lines. (see the second image)

Let's define a coordinate space for pixels

• top-left pixel -> index (0,0)
• top-right pixel -> index (15,0)
• bottom-left pixel -> index (0,15)
• bottom-right pixel -> index (15,15)

Contour lines also have their coordinate space

• top-left corner of top-left pixel -> index (0,0)
• top-right corner of top-right pixel -> index (16,0)
• bottom-left corner of bottom-left pixel -> index (0,16)
• bottom-right corner of bottom-right pixel -> index (16,16)

Finally, contour lines are defined as a sequence of points in that coordinate space.

On the second image I marked 3 contours to demonstrate what the desired output should look like.

Path1 (RED): 1(1,0) 2(2,0) 3(2, 3) 4(3,3) 5(0,3) ... 23(4,4) 24(1, 4)
    Hole1 of Path1 (BLUE): 1(7,5) 2(7,6) 3(6,6) ... 13(11,6) 14(11,5)

Path2 (RED again): 1(8,6) 2(10,6) 3(10,8) 4(8,8)
...

Note that the order of points in contour is important. Winding difference for holes is not that important, but we should somehow indicate "hole" property of that contour.

I solved this problem using ClipperLib, but it is more like a brute-force approach in my opinion, if we ignore what happens inside the ClipperLib.

Here's a brief description of the algorithm.

First, define a 16x16 subject polygon from which we will be subtracting all white pixels 
Scan the image matrix row by row
    On each row extract all contiguous white rectangle shapes as a clipping polygon
Do the polygon clipping by subtracting all collected white rectangular polygons from initial 16x16 subject polygon
Extract path data (including holes) from ClipperLib's PolyTree solution

I'm wondering if there is a better way to solve this problem?

Answer 1

Using ClipperLib seems overkill here, as it addresses general polygons by means of complex intersection detection and topological reconstruction algorithms, whereas your problem is more "predictable".

You can proceed in two steps:

• use a standard contouring algorithm, such as used by cv.findContours. (It is an implementation of "Satoshi Suzuki and others. Topological structural analysis of digitized binary images by border following. Computer Vision, Graphics, and Image Processing, 30(1):32–46, 1985.")

• from the contours, which link pixel centers to pixel centers, derive the contours that follow the pixel edges. This can probably be achieved by studying the different configurations of sequences of three pixels along the outline.

Answer 2

You can use boundary tracing algorithms for this. I personally use Moore-Neighbor tracing, because it's intuitive and straightforward to implement. You first find the boundary contours, and then come up with a hole searching algorithm (you may need to combine parts of scanline fill algorithm). Once you find a hole, you can apply the same boundary tracing algorithm, but in opposite direction.

You can definitely use libraries like OpenCV to find contours, but it my experience, it may produce degenerate output incompatible with other libraries, such as poly2tri used to decompose polygons into triangles.

If we take your input sample image, then the red path could be considered self-intersecting (vertices 7 and 23 are touching), which may lead to failed polygon decomposition. You may need to figure out a way to find and treat those objects as separate, if that's a problem. However, the newest Clipper2 is going to have triangulation unit that could handle such degenerate input, if you ever need to solve this problem down the road.