TopoToolbox / TopoToolbox/libtopotoolbox

What happens when the queue fills up in `reconstruct_hybrid`?

Open
#233 1 comment 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

Dominant language
C
Stars
2
Forks
11
PR merge metrics
No merged PRs in 30d

Description

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.

Contributor guide

Open the contributing guide

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

Research direction

Start by inspecting reconstruct_hybrid, especially propagate and its fixed-capacity queue, then review the existing test cases and snapshot tests. Create a case with regional minima at different elevations or a rolled-up image based on Vincent's Fig. 16, and determine whether skipped enqueues leave pixels unconverged. Done means the queue behavior and iteration strategy are confirmed correct or a concrete failure is reproduced.

Written by the indexing model from the issue text.

Assessment

Tech stack
c
Domain
computer-vision
Issue type
Bug
Difficulty
5/5
Estimated time
Over a week
Activity status
Quiet
Clarity
Needs clarification
Newbie friendliness
35/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.