When we see two images of the same scene, with slight differences, we can usually tell they are the same. As a simplified example, consider the two houses below:
How do we know they are the same house? Apart from me saying so, we can look past the changes in season and the tree blocking parts of the house and still recognise them as the same place. But a computer can have difficulty determining this. What we need is a way to match the two objects together by using different parts of the house, such as the provided points A, B and C. If we can match the roof, the front door, and path together, and they look similar between images, we can be reasonably sure the images show the same house.
This concept applies to 3D surfaces as well. We will use the example of human faces. How would we know two faces are the same? We can look at things on the surface like eye colour, or the size of different facial features like the nose and lips. Using these facial features powers facial recognition. A facial recognition algorithm finds these features, and compares them against its stored features, to determine if the face is a match.
How does correspondence differ?
What we’ve explored is a roundabout introduction to correspondence. A correspondence is the matching performed between two images, or faces. In the case of surfaces, it will match key points on the face, such as the nose to the nose, the eyes to the eyes, the chin to the chin. When we only deal with a few points on the surface, it is known as sparse correspondence.
On the other hand, dense correspondence tries to map all of the parts of an image to another related image. Dense correspondence is a pre-requisite to many applications including computer vision, computer graphics, and facial recognition.
This is a much more difficult problem than simply sparse. For our house example above, it would match every single pixel in the first image to a corresponding pixel in the second. Every part of the sky, every window, every part of the trees and the road. In the case of facial recognition, it will try to match the key features above, but also every single point on the face. Algorithms such as NICP  try to perform this automatically.
What does this allow us to do?
Sparse correspondence allows facial recognition, image search engines, or automatic categorising of images. Dense correspondence, when it is established, allows even more:
- 3D facial recognition
- Assistance in diagnosing syndromes
- Allow patients to “preview” an upcoming cosmetic procedure
- Add and remove expressions on 3D faces
 Optimal Step Nonrigid ICP Algorithms for Surface Registration (Amberg, Romdhani, Vetter, 2007)
Edith Cowan University