Decided yesterday that my haphazard "intuitive" approach to stroke extraction (convolution with that positive/negative kernel, stroke extraction as outlined in my presentation) wasn't really going to work. The next step was to turn to the literature that I had accumulated. Hew99 (Strokes from Pen-Opposed Extended Edges) seemed promising, but his approach of extracting opposed edges and trying to infer stroke direction seemed overly complex and not very well described in any case. He did however mention other approaches, one being the thinning-based Liu97 (Robust Stroke Segmentation Method for Handwritten Chinese Character Recognition). His results looked good, but he didn't provide any details on the thinning part of his algorithm, instead he pointed to Wang89 (A Fast and Flexible Thinning Algorithm). The paper was somewhat cryptic and/or entertaining due to its age (ooo, we shall describe the image as a matrix of pixels, quelle nouvelle idee), but the idea seemed workable.

Before I could get to the thinning, I first had to split up the difference image into sub-images, one per future set of strokes (each being a subset of 8-way connected pixels). In my quest to learn more, I decided to use the STL for a few classes that I'd need for this (hash_set and vector). The idea was fundamentally sound, but using hash_set took longer than expected, since it's not part of the standard STL (SGI extension apparently), and using it requires one to use the __gnu_cxx namespace. What with Xcode's error messages about this not being very clear, it took a while.

Thinning requires one to worry about edge pixels, and this also gives us an easy way to compute stroke thicknesses (2 * shape area/share perimeter length). This can be used to throw out differences that aren't really strokes (e.g. people), though right now this only works if strokes aren't partially obscured (i.e. not connected). I may have to add color distance to my connectivity criteria (right now it just being "is not a background pixel").