| 2-D point landmark correspondence |
| Image Registration and Fusion Systems |
 | |  |
Point landmark correspondence or point pattern matching is the process of finding correspondence between two sets of points. If
landmarks in only one of the images are given, corresponding landmarks in the second image can be determined through a process
known as template matching. If landmarks in both images are given, the following algorithm can be used to determine the
correspondence between them. The algorithm assumes that the images are related by a linear transformation.
Pose Consistency Algorithm:
Suppose two large sets of point landmarks are given and they are denoted by P and Q. Let's also suppose there are n1 landmarks in
P and n2 landmarks in Q. Denoting the ith landmark in P by pi and the jth landmark in Q by qj, we will find a list of (i,j) tuples that show
the indices of corresponding landmarks in the images. Let's denote this list by L, and the number of correspondences found by n. Let's
also denote coordinates of landmarks in P by (x,y) and coordinates of landmarks in Q by (X,Y). Assuming the images are related by a
linear transformation, then we have: x=aX+bY+c; y=dX+eY+f. In the following algorithm, D is a short distance threshold such as 2 pixels.
This is the maximum distance allowed between two corresponding landmarks.
Step 1: Create empty list L and let n=0.
Step 2: Select three landmarks from set P and three landmarks from set Q.
Step 3: Determine parameters a–f of a linear transformation using the coordinates of the three landmark pairs. Note that there are 6
such cases.
Step 4: For j=1,…,n2,
Step 4.1: Substitute point qi into the equation of the transformation and find the corresponding point q’j in the space of P.
Step 4.2: Find the point in set P that is closest to qi. Let pi be such a point. If d =|pi – qi| < D, save (i,j) in entry n in L and increment n by
1.
Step 5: If n is sufficiently large, return L and a-f. If no more choices of point triples exist in P and Q, report failure. Otherwise, go to Step 2.
In Step 5, if n > n2/2 (i.e., if correspondence is established between more than half of the landmarks in the two images), the
transformation can be considered correct. Otherwise, the process is repeated until either 1) the search is exhausted, or 2) the obtained
linear transformation matches more than half the landmarks in the images.
An example of landmark correspondence by this algorithm is given below. In images in the top row are landmarks (shown by red dots)
selected in two Landsat 5 images of Tampa, Florida, taken in Nov. 1984 and Sept. 2006. The scene is relatively flat and because the
sensor is very far from the scene compared to variations in scene elevation, corresponding landmarks in the images can be related by
a linear transformation, and the above algorithm can be used to determine the correspondence between the landmarks. The
landmarks in the images were selected by a procedure described elsewhere (See the 2-D point landmark selection page for details).
Although many selected landmarks exist in only one of the images due to considerable scene changes over 22 years, there are
landmarks that exist in both images. The algorithm is capable of finding the corresponding landmarks in the images and registering
them. Registration of the images by an affine transformation (See the 2-D auto affine registration page for details) using the obtained
set of correspondences is shown in the image at the bottom left. Subtracting the registered images we obtain the bottom right image,
which shows detected scene changes over time
landmarks in only one of the images are given, corresponding landmarks in the second image can be determined through a process
known as template matching. If landmarks in both images are given, the following algorithm can be used to determine the
correspondence between them. The algorithm assumes that the images are related by a linear transformation.
Pose Consistency Algorithm:
Suppose two large sets of point landmarks are given and they are denoted by P and Q. Let's also suppose there are n1 landmarks in
P and n2 landmarks in Q. Denoting the ith landmark in P by pi and the jth landmark in Q by qj, we will find a list of (i,j) tuples that show
the indices of corresponding landmarks in the images. Let's denote this list by L, and the number of correspondences found by n. Let's
also denote coordinates of landmarks in P by (x,y) and coordinates of landmarks in Q by (X,Y). Assuming the images are related by a
linear transformation, then we have: x=aX+bY+c; y=dX+eY+f. In the following algorithm, D is a short distance threshold such as 2 pixels.
This is the maximum distance allowed between two corresponding landmarks.
Step 1: Create empty list L and let n=0.
Step 2: Select three landmarks from set P and three landmarks from set Q.
Step 3: Determine parameters a–f of a linear transformation using the coordinates of the three landmark pairs. Note that there are 6
such cases.
Step 4: For j=1,…,n2,
Step 4.1: Substitute point qi into the equation of the transformation and find the corresponding point q’j in the space of P.
Step 4.2: Find the point in set P that is closest to qi. Let pi be such a point. If d =|pi – qi| < D, save (i,j) in entry n in L and increment n by
1.
Step 5: If n is sufficiently large, return L and a-f. If no more choices of point triples exist in P and Q, report failure. Otherwise, go to Step 2.
In Step 5, if n > n2/2 (i.e., if correspondence is established between more than half of the landmarks in the two images), the
transformation can be considered correct. Otherwise, the process is repeated until either 1) the search is exhausted, or 2) the obtained
linear transformation matches more than half the landmarks in the images.
An example of landmark correspondence by this algorithm is given below. In images in the top row are landmarks (shown by red dots)
selected in two Landsat 5 images of Tampa, Florida, taken in Nov. 1984 and Sept. 2006. The scene is relatively flat and because the
sensor is very far from the scene compared to variations in scene elevation, corresponding landmarks in the images can be related by
a linear transformation, and the above algorithm can be used to determine the correspondence between the landmarks. The
landmarks in the images were selected by a procedure described elsewhere (See the 2-D point landmark selection page for details).
Although many selected landmarks exist in only one of the images due to considerable scene changes over 22 years, there are
landmarks that exist in both images. The algorithm is capable of finding the corresponding landmarks in the images and registering
them. Registration of the images by an affine transformation (See the 2-D auto affine registration page for details) using the obtained
set of correspondences is shown in the image at the bottom left. Subtracting the registered images we obtain the bottom right image,
which shows detected scene changes over time
To obtain a license for this software, please follow the link =>
Fig. 1. (Top row) Temporal Landsat images. These images are courtesy of NASA. (Bottom left) Registered images. (Bottom right)
Absolute difference of registered images.
Absolute difference of registered images.