HOME

TheInfoList



OR:

The correspondence problem refers to the problem of ascertaining which parts of one image correspond to which parts of another image, where differences are due to movement of the camera, the elapse of time, and/or movement of objects in the photos. Correspondence is a fundamental problem in
computer vision Computer vision is an interdisciplinary scientific field that deals with how computers can gain high-level understanding from digital images or videos. From the perspective of engineering, it seeks to understand and automate tasks that the hum ...
— influential computer vision researcher
Takeo Kanade is a Japanese computer scientist and one of the world's foremost researchers in computer vision. He is Uncas A. Whitaker, U.A. and Helen Whitaker Professor at Carnegie Mellon University. He has approximately 300 peer-reviewed academic publicatio ...
famously once said that the three fundamental problems of computer vision are: “Correspondence, correspondence, and correspondence!” Indeed, correspondence is arguably the key building block in many related applications:
optical flow Optical flow or optic flow is the pattern of apparent motion of objects, surfaces, and edges in a visual scene caused by the relative motion between an observer and a scene. Optical flow can also be defined as the distribution of apparent veloci ...
(in which the two images are subsequent in time), dense
stereo vision Stereopsis () is the component of depth perception retrieved through binocular vision. Stereopsis is not the only contributor to depth perception, but it is a major one. Binocular vision happens because each eye receives a different image becaus ...
(in which two images are from a stereo camera pair),
structure from motion Structure from motion (SfM) is a photogrammetric range imaging technique for estimating three-dimensional structures from two-dimensional image sequences that may be coupled with local motion signals. It is studied in the fields of computer visio ...
(SfM) and visual
SLAM Slam, SLAM or SLAMS may refer to: Arts, entertainment, and media Fictional elements * S.L.A.M. (Strategic Long-Range Artillery Machine), a fictional weapon in the ''G.I. Joe'' universe * SLAMS (Space-Land-Air Missile Shield), a fictional anti-ball ...
(in which images are from different but partially overlapping views of a scene), and cross-scene correspondence (in which images are from different scenes entirely).


Overview

Given two or more images of the same 3D scene, taken from different points of view, the correspondence problem refers to the task of finding a set of points in one image which can be identified as the same points in another image. To do this, '' points'' or ''
features Feature may refer to: Computing * Feature (CAD), could be a hole, pocket, or notch * Feature (computer vision), could be an edge, corner or blob * Feature (software design) is an intentional distinguishing characteristic of a software item ...
'' in one image are matched with the points or features in another image, thus establishing corresponding points or corresponding features, also known as homologous points or homologous features. The images can be taken from a different point of view, at different times, or with objects in the scene in general motion relative to the camera(s). The correspondence problem can occur in a stereo situation when two images of the same scene are used, or can be generalised to the N-view correspondence problem. In the latter case, the images may come from either N different cameras photographing at the same time or from one camera which is moving relative to the scene. The problem is made more difficult when the objects in the scene are in motion relative to the camera(s). A typical application of the correspondence problem occurs in
panorama A panorama (formed from Greek πᾶν "all" + ὅραμα "view") is any wide-angle view or representation of a physical space, whether in painting, drawing, photography, film, seismic images, or 3D modeling. The word was originally coined in ...
creation or
image stitching Image stitching or photo stitching is the process of combining multiple photographic images with overlapping fields of view to produce a segmented panorama or high-resolution image. Commonly performed through the use of computer software, most app ...
— when two or more images which only have a small overlap are to be stitched into a larger composite image. In this case it is necessary to be able to identify a set of corresponding points in a pair of images in order to calculate the transformation of one image to stitch it onto the other image.


Basic methods

There are two basic ways to find the correspondences between two images. Correlation-based – checking if one location in one image looks/seems like another in another image. Feature-based – finding features in the image and seeing if the layout of a subset of features is similar in the two images. To avoid the
aperture problem Motion perception is the process of inferring the speed and direction of elements in a scene based on visual, vestibular and proprioceptive inputs. Although this process appears straightforward to most observers, it has proven to be a difficult pr ...
a good feature should have local variation in two directions.


Use

In computer vision the correspondence problem is studied for the case when a computer should solve it automatically with only images as input. Once the correspondence problem has been solved, resulting in a set of image points which are in correspondence, other methods can be applied to this set to
reconstruct Reconstruction may refer to: Politics, history, and sociology *Reconstruction (law), the transfer of a company's (or several companies') business to a new company *'' Perestroika'' (Russian for "reconstruction"), a late 20th century Soviet Unio ...
the position, motion and/or rotation of the corresponding 3D points in the scene. The correspondence problem is also the basis of the particle image velocimetry measurement technique, which is nowadays widely used in the
fluid mechanics Fluid mechanics is the branch of physics concerned with the mechanics of fluids ( liquids, gases, and plasmas) and the forces on them. It has applications in a wide range of disciplines, including mechanical, aerospace, civil, chemical and bio ...
field to quantitatively measure fluid motion.


Simple example

To find the correspondence between set A ,2,3,4,5and set B ,4,5,6,7find where they overlap and how far off one set is from the other. Here we see that the last three numbers in set A correspond with the first three numbers in set B. This shows that B is offset 2 to the left of A.


Simple correlation-based example

A simple method is to compare small patches between rectified images. This works best with images taken with roughly the same point of view and either at the same time or with little to no movement of the scene between image captures, such as stereo images. A small window is passed over a number of positions in one image. Each position is checked to see how well it compares with the same location in the other image. Several nearby locations are compared for objects in one image which may not be at exactly the same image-location in the other image. It is possible that there is no fit that is good enough. This may mean that the feature is not present in both images, it has moved farther than your search accounted for, it has changed too much, or is being hidden by other parts of the image.


See also

*
Stereoscopy Stereoscopy (also called stereoscopics, or stereo imaging) is a technique for creating or enhancing the illusion of depth in an image by means of stereopsis for binocular vision. The word ''stereoscopy'' derives . Any stereoscopic image is ...
*
Parallax Parallax is a displacement or difference in the apparent position of an object viewed along two different lines of sight and is measured by the angle or semi-angle of inclination between those two lines. Due to foreshortening, nearby objects ...
*
Photogrammetry Photogrammetry is the science and technology of obtaining reliable information about physical objects and the environment through the process of recording, measuring and interpreting photographic images and patterns of electromagnetic radiant ima ...
*
Depth perception Depth perception is the ability to perceive distance to objects in the world using the visual system and visual perception. It is a major factor in perceiving the world in three dimensions. Depth perception happens primarily due to stereopsis an ...
*
Stereopsis Stereopsis () is the component of depth perception retrieved through binocular vision. Stereopsis is not the only contributor to depth perception, but it is a major one. Binocular vision happens because each eye receives a different image becaus ...
*
Computer vision Computer vision is an interdisciplinary scientific field that deals with how computers can gain high-level understanding from digital images or videos. From the perspective of engineering, it seeks to understand and automate tasks that the hum ...
* Fundamental matrix * Joint compatibility branch and bound algorithm *
Epipolar geometry Epipolar geometry is the geometry of stereo vision. When two cameras view a 3D scene from two distinct positions, there are a number of geometric relations between the 3D points and their projections onto the 2D images that lead to constraints b ...
*
Image registration Image registration is the process of transforming different sets of data into one coordinate system. Data may be multiple photographs, data from different sensors, times, depths, or viewpoints. It is used in computer vision, medical imaging, milit ...
*
Birchfield–Tomasi dissimilarity In computer vision, the Birchfield–Tomasi dissimilarity is a pixelwise image dissimilarity measure that is robust with respect to sampling effects. In the comparison of two image elements, it fits the intensity of one pixel to the linearly inter ...
*
Scale-invariant feature transform The scale-invariant feature transform (SIFT) is a computer vision algorithm to detect, describe, and match local ''features'' in images, invented by David Lowe in 1999. Applications include object recognition, robotic mapping and navigation, ima ...
(SIFT)


References


D. Scharstein and R. Szeliski. A Taxonomy and Evaluation of Dense Two-Frame Stereo Correspondence Algorithms.
(PDF) {{Stereoscopy


External links


Middlebury Stereo Vision page
Geometry in computer vision Stereoscopy zh:图像对应问题