## Sunday, March 23, 2014

### Stereo Matching 101: Disparities, Occlusions and "Ordering Constraint"

Maybe it's time to visit or revisit the basics of stereo matching, in particular, disparities, occlusions and the so-called "ordering constraint".

The above diagram shows the classic stereo rectified camera setup. The term "rectified" means that, in the context of stereo matching, matches are made along horizontal lines (scan lines). Aligning the stereo pair in StereoPhoto Maker has the same effect as rectification. In this diagram, the left (right) image corresponds to the CCD plane (digital camera) or the film plane (old school emulsion film camera) and the center of projection is the lens (pinhole) except that obviously, the two have been swapped for easier mathematics (Clearly, the image plane should be behind the lens, not in front.) The coordinate system for each image has its origin at the upper left. The disparity is simply the difference between the x values of the matched points. The disparity is positive if the point on the right image must be shifted to the left to get to the matched point on the left image.

The above diagram shows what an occlusion (half occlusion) is. An occlusion is simply a point in the scene that can be seen by one camera but not the other. You can have occlusions when you attempt to match a point on the left image to a point on the right image, and vice versa.

The above diagram shows what the "ordering constraint" is. In layman terms, it just means that if a point in the scene appears to be to the right of another point in the left image, the relative positioning should be the same in the right image.

The above diagram shows an example of "ordering constraint" violation. It's the classic example of the picket fence in front of something else in the 3D scene. Anytime you have an object with a good size opening in the foreground, the "ordering constraint" is likely to be violated. Some stereo matching algorithms out there assumes that the "ordering constraint" always stands, which may not be a bad idea. For example, the stereo matching procedure used in OpenCV, a block-matching algorithm based upon "Small Vision Systems: Hardware and Implementation" by K. Konolige, makes use of the "ordering constraint".