[Work Log] Work Log
Finished implementing and debugging neuron skeleton-image-to-graph code. It was deceptively difficult; there are lots of corner cases when tracing pixels that lead to unexpected behavior. I had to totally redesign how junctions were calculated three times. I also twice refactored how previously-visited pixels were recorded, and how chains are split at junctions.
We define the "neighbor set" of a pixel as the set of all nonzero 8-connected neighbors with the caveat that diagonal neighbors are not "blocked" by a horizontal neighbor. The idea here is that we want all paths through the graph to be unique, and "blocked" diagonal neighbors have two paths: one in which the diagonal neighbor is adjacent to the current pixel, and one in which it is adjacent to the blocking pixel. Omitting it from the neighbor set solves the problem by eliminating the extra path, while guaranteeing a path still exists that passes through the offending neighbor pixel. In practice, this prevents chains from sneaking around previously visited pixels by visiting diagonal neighbors. It also is central to the definition of a "junction" below.
We use a modified floodfill algorithm to explore the entire graph. First, we add one or more seed pixels to the queue. While the queue is not empty, we dequeue a pixel, add it to the current pixel chain, and enqueue its neighbors. We also check if it is a junction pixel; if so, we add the current pixel-chain to the chain set, and begin a new empty chain. We define a junction as any pixel with a neighbor set of size three or more. If during any iteration, no pixels are added to the queue, the chain has reeached its end; we add it to the chain set and begin a new empty chain.
Several additional details are important.
Because we allow several seed pixels, our depth-first search may encounter the seed pixels while they still exist deeper in the queue. The side effect is that the seed pixels may be added to two different chains. We resolve this by marking pixels when they are added to a chain, and if a pixel is dequeued that is already added to a chain, we discard it.
After finding all chains, at most one endpoint is associated with a junction. We require that the junction point appear in every pixel-chain that enters the junction, so some chains need their second junction point added. Recall that a chain only terminates at junctions or if it has no unclaimed neighbors. For any non-junction endpoints, any neighbors (not counting the chain's antecedent pixel) must be junctions. To prove there is at most one junction neighbor, assume it had two junction endpoints. Then the pixel would have three neighbors: two endpoints and its antecedent pixel. This implies the pixel is a junction itself -- a contradition. Thus, adding a junction to a dangling endpoint amounts to finding an unclaimed neighbor.
Two adjacent junction pixels must be handled separately.
Posted by Kyle Simek