Little Things #

Made the 8-way flood fill in the CapturedImage class (which is used to find connected changed pixels) use an in-place vectorinstead of recursive calls for performance/scalability reasons.

I had previously noticed that thin vertical lines were not being picked up by the frame-to-frame difference algorithm. This turned out to be not because of the algorithm itself, but because of the despeckling that I did immediately after. The despeckling would remove any pixel which didn't have at least two non-background neighbors. In the case of a vertical line, since we'd start the scanning from the top, we'd remove the end-point since it only had a non-background pixel right below it. On the next scan-line, the same thing would happen, since this pixel had now become the end-point. The fix was to make the despeckling a two pass process. On the first pass, we simply count how many non-background neighbors each pixel has. On the second pass we remove those whose neighbor count is below the threshold of two and don't have any neighbors that satisfy the threshold. I also tweaked the despeckling so that if a background pixel was completely surrounded by non-background ones, it would be replaced with the average color of its neighbors. This removed one pixel "holes" that would throw off the thinning and stroke algorithms.

As previously mentioned, one problem with counting crossings to see how many times a pixel can be visited (in the case of stroke intersections) was that, even when the image is thinned, there can be pixels that, in their 8x8 neighborhood, don't have enough black-to-white transitions to be flagged as a crossing. Based on the Liu paper, I came up with an alternative criterion that also includes neighbors. Basically, for a pixel to be marked as supporting two visits, it must pass at least one of these tests:

  • 4 or more black to white transitions
  • 3 black to white transitions and 4 or more black neighbors
  • 2 black to white transitions and 5 or more black neighbors

When following pixels to determine which ones make up a stroke, to make sure that we went through a crossing in the right direction, we would first look for the next pixel in the same direction as the previous one that had been found. So for example, in the case on the left, the two strokes would be separated "naturally" (red and green denote the two strokes, yellow pixels are shared):

  1      1
  1      1
11111 111111
  1     1
  1     1

However, in the case of the pattern on the right, the stroke has no choice but to make a turn, and then it continues along that path, with the net separation being two unnatural strokes that each make a sudden turn.

Despite being on my third paragraph describing the problem, the actual fix was two lines long. If we keep track of the average direction for the past several points, then local changes in the direction will not have such disproportionate impact. Given some decay constant K, the new direction D' and the average direction D, the update function is D = D * K + D' * (1.0 - K)

Post a Comment