The Correspondence Problem

text describing the correspondence problem

The Correspondence Problem

The correspondence problem is the problem of determining that two things correspond to each other, although they might appear different at the low (e.g. sensory) level, for instance because they underly variations, either of the objects themselves (different chairs are still all part of the category "chair"), contextural variations (e.g differnt backgrund clutter, occlusions etc.. ) mapping variations (e.g. differnt lighting conditions in vision, e.g acoustic conditions in speech recognition), receptive variations (different states of the receptors e.g due to adaption, etc.. ). Humans are masters in solving the correspondence problem, and I believe that our intelligence is based on this mastery.

We know that an object like a chair that is seen from different perspective and casts different images on the retina is still the same object. In the field of cognitive psychology this phenomenon is often expressed with the term "constancy". As such "location constancy" is the ability to keep track of "constant" poses of objects despite movements of the sensor system and possibly also the objects. "Color constancy" is the ability to know that two colors are actually the same, though they appear different on the sensory level, because of lighting variations."Object constancy" involves the ability to categorize objects into classes.

In all cases, the problem arises in two facets, depending on the type of the "partners" involved in a correspondence. Either each partner is in the sensory domain (e.g. like in image matching applications or optical flow in visual perception.), or only one part is in the sensory domain while the other is an internal model or datastructure (e.g. object recognition). Hence, solving the correspondence problem also means to think about how things should be modeled and stored to allow fast retrieval.

What makes the correspondence problem so hard to solve, is that it cannot be solved without solving a second problem which is the "segmentation problem". The segmentation problem means to identify the structures in the sensor domain that are part of the corresponence. For instance, when a human's speech is to be understood in the presence of background noise, the difficulty is to identify the accousitc parts that are actually of the person speaking and not of someone different, talking in the background. What makes things diffifcult is that the correspondence problem and the segmentation problem have to be solved simultaneously.