G. E. Hinton, Relaxation and its Role in Vision, 1977 · ch. 1, 3 and 5

The Search ArenaWaltz filtering vs. the simplex method vs. continuous LP relaxation

step 0 / 0

A · Waltz filtering

discrete constraint propagation · §1.4.3
FILTERING

B · Serial simplex

vertex to vertex · §3.9
PHASE 1
vertices visited, projected from n dimensions onto 3 principal axes

C · Parallel relaxation

continuous supposition values · §3.12–3.19, 5.2
RELAXING

Local evidence adds to P for B and C

Waltz filtering has no way to use graded evidence or costs: a label is either allowed or not.

Comparison final results for this scene

How to read the panels

+convex edge −concave edge occluding edge: the body is on the right of the arrow

A keeps every catalogue labelling at each junction and deletes any that lack a sponsor along a line. Red flashes are deletions in this sweep.

B solves the same linear programme as C, one pivot at a time. Amber lines changed label at this pivot.

C gives every label a supposition value and updates all of them at once. Brightness is the value; an amber ring marks a junction read as unusual.