Interpretation Tree Demo

First we will explain what the applet is currently doing in the other frame -- you did use the middle button didn't you?

The Task

The task is to find an instance of this model object in the image of many similar models on the right. An edge detection and line grouping stage has already been performed and the edges and lines are overlaid on both the model and data images.

The Search

The search proceeds by taking each model line and comparing it to each of the lines in the data image (there are about a hundred in this example). If the lines match (i.e. the ratio of their lengths is between the values on the Length Min and Length Max sliders), then the search takes the next model line and compares it to all the remaining data lines. If one of those matches, we take the third model line, look for a match, and so on until we have matched a sufficient number to be confident that we've found the correct answer. A collection of such model-to-data pairings is called an interpretation.

Binary Matches
Once we have a few pairings between model and data lines, we can apply slightly more sophisticated tests to check that we've got the right answer. For example if the first model line is matched to data line X, say, and the second is matched to data line Y, then we also know that the angle between the two model lines (1 and 2) should be the same as that between X and Y. To cope with errors in the acquisition process, we just require that the difference between the model angle and the data angle is less than the value on the Angle slider.

Backtracking

The problem comes, of course, when we can't find a match for a model feature in the data. In that case we must backtrack to try other sets of features, and this is where the tree comes in. For each model feature there will often be several of the data lines that are within the length thresholds, so if one pairing fails, we should go back to the others that matched and try to expand those hypotheses. If all the others produce invalid interpretations, then this model feature has no possible data matches and we go back up the tree to the previous model-to-data match.

Wildcards

It may often happen that a model line should have a matching line in the data, but that because of errors, there isn't one. It make no sense to terminate the search at that point, because all the following model lines might match perfectly well. In this case we introduce a wildcard match which is simply a match that says that a certain model feature has no counterpart in the image. The wildcard matches are marked in pink on the images and in the tree display.

Exercises

  1. Allow the search to terminate at the default settings. The final interpretation explored is that on the far right of the tree, and the participating lines are shown on the images. Can you identify the model lines with the nodes of the tree?
  2. First, try reducing the Angle threshold by one stop, to 25 degrees. This causes the correct solution to be falsely rejected and means that the whole tree is explored. This gets boring after a couple of thousand nodes so you might want to just put it back to 25.
  3. If we increase the angle threshold on the other hand, notice that we still get the correct solution, but have to explore many more nodes. What would happen if the angle threshold were set to 180, effectively turning it off?
  4. Similar results happen with the Length thresholds -- too tight and the correct answer is missed, too loose and many extra nodes are explored.