The Thinning Continues #

The annoying thing about the Wang paper is that it's not very detailed. I can't tell if it's because of space limitations when it was published (it is part of the IEEE Transactions - maybe there's a more detailed version out there), but it leaves a lot of things "as an exercise for the reader" as it were.

For example, one of the things that it requires is the number of "contour loops" (e.g. a line would have one, a hollow circle two, a figure eight three, and so on) present in the image, and their starting points. My first approach was to find an edge pixel in the image, walk along it (the paper's successor function is, given the current and previous edge pixels, walk along clockwise in the neighborhood, starting with the previous pixel, and pick the first dark pixel encountered) and mark all other edge pixels encountered as visited, and to then repeat the process until there's no more edge pixels left. However, this didn't work, because some edge pixels would be skipped over when walking along. For example, in the picture below, the red pixels would be marked off on the first pass, but the green one, though considered an edge pixel, would have to wait for another pass, causing the creation of a spurious "loop".


The better way of doing this was to pick any background pixel, do a flood-fill (marking off any background pixels as visited) and pick any of the edge pixels encountered as the starting point. Then repeat this until there are no more background pixels left.

The paper is also cryptic in that it provides pseudo-code for the algorithm, but it doesn't say anything about why or how it works. For example, there's a function c that, from my best guess, appears to check for diagonal cases, but I'm not really sure why. It's also not very clear on the termination function when iterating. Just seeing if you pass the same point twice isn't good enough, since you can encounter it from two directions, and not in fact have completed a loop. Testing for a point plus its predecessor (to incorporate direction) seems fundamentally like a good idea, but there's still problems since points can get deleted, and what used to be its predecessor may not be there at all in the next iteration, and then we're stuck in an infinite loop.

The net result of all this is that the thinning seems to mostly work, except it doesn't sometimes thin two pixel thick diagonal lines, and it entirely decimates another type of diagonal lines (not very even/regular ones). The former I think I've tracked to bugs in the mysterious c function, but for the latter I have no idea.

Post a Comment