As discussed in #232
reconstruct_hybrid uses a sequential forward and backward scan of the image followed by a breadth-first search using a queue. In principle you only need a single iteration of scan and search, but because we use a queue with a maximum capacity of dims[0] * dims[1] - 1 elements, the queue can conceivably fill up. When it does so we run another iteration.
#232 fixed a problem where the same pixel would be added to the queue multiple times in backward_scan. It is now, we believe, impossible for the queue to fill up in backward_scan. Now our attention turns to propagate.
It seems possible for the queue to fill up in propagate because the breadth-first search can attempt to visit pixels more than once. Vincent (1993) notes that this will happen when two regional maxima with different elevations are adjacent.
Right now, if the queue fills up, we skip enqueuing the pixel that would overflow the queue and continue on with the breadth-first search. Since the search continues to dequeue pixels, the queue does eventually empty. Some pixels may have been left unconverged in that case, though, which is why we run the iteration again. Is this correct? As I said in #232:
My intuition is because the marker elevation of a pixel never decreases, if you fail to enqueue a pixel and one of its neighbors is lower than it, that update will still be able to be applied in the next iteration. But this could easily be wrong.
We need to figure out in which cases the queue actually does fill up in propagate. Following #232, none of the existing test cases, including the snapshot tests, fills up the queue. A test case with several regional minima with different elevations would be a good place to start. Alternatively a "rolled up" image along the lines of Vincent's Fig. 16 does poorly in the sequential scan, so the queue has a lot more work to do.
As discussed in #232
reconstruct_hybriduses a sequential forward and backward scan of the image followed by a breadth-first search using a queue. In principle you only need a single iteration of scan and search, but because we use a queue with a maximum capacity ofdims[0] * dims[1] - 1elements, the queue can conceivably fill up. When it does so we run another iteration.#232 fixed a problem where the same pixel would be added to the queue multiple times in
backward_scan. It is now, we believe, impossible for the queue to fill up inbackward_scan. Now our attention turns topropagate.It seems possible for the queue to fill up in
propagatebecause the breadth-first search can attempt to visit pixels more than once. Vincent (1993) notes that this will happen when two regional maxima with different elevations are adjacent.Right now, if the queue fills up, we skip enqueuing the pixel that would overflow the queue and continue on with the breadth-first search. Since the search continues to dequeue pixels, the queue does eventually empty. Some pixels may have been left unconverged in that case, though, which is why we run the iteration again. Is this correct? As I said in #232:
We need to figure out in which cases the queue actually does fill up in
propagate. Following #232, none of the existing test cases, including the snapshot tests, fills up the queue. A test case with several regional minima with different elevations would be a good place to start. Alternatively a "rolled up" image along the lines of Vincent's Fig. 16 does poorly in the sequential scan, so the queue has a lot more work to do.