Matching operation is usually a computationally expensive process. To reduce the cost of computation, a technique of two-step matching is used. In this technique, one first matches a few lines of the orientated image to lines of the unorientated image. This step of the match is called kernel matching, and the line correspondences obtained in this step are called the match base. After kernel matching, a further matching for the remaining lines is performed. In further matching, the matching function is computed with respect to the already matched lines, and therefore the cost of computation is reduced.

Kernel matching.
Kernel matching plays an important role in the whole matching process since the line correspondences obtained from this step will serve as a reference for further matching.

The kernel matching can be formulated as follows:

• Assign unique labels to each line pair with “L” shape junction of the first and the second images.
• Use dynamic programming to find the best match line pair with “L” junction from the second image for each line pair with “L” junction of the first image.
• Compute the orientation disparity. Suppose that n lines in the first image have been matched with n lines in the second image. The orientation disparity of the two line subsets can be computed based on the center point connecting directions. Suppose a_ij is the direction from the center point of line L_i to that of line L_j in the first image, b_ij is the direction determined by L_ki and L_kj in the second image. The orientation disparity is defined as
  d_ij = | a_ij - b_ij |                   ( 1 )
  
• Compute the number line’s orientation disparities are smaller than the user defined threshold, and remove those matched lines with lower number from the first and the second images.
• Calculate the position disparities. For a matched line pair L_i in the first image and L_ki in the second image, (x_i, y_i) and (x_ki, y_ki) denote the center points of them respectively. Thus, two position disparities in horizontal and vertical directions will be obtained as
  
  
• Calculate means and variances of the position disparities. The means are computed as and the variances as
  
  and the variances as
  
  
• Remove those matched lines whose position disparities p and q satisfy the flowing conditions
  
  or
  
  In the choice of kernel matching lines, the number should be over three. In our experiment, five or seven longest line pairs with highest matching function merits are selected.

Further matching
After the kernel matching is completed, the correspondences obtained from the match will serve as a reference for the match of the remaining lines. The process of matching the remaining lines based on the already matched lines is called further matching. In further matching, the lines in the first image will be matched one by one, from long to short, to lines in the second. The matching function for further matching are computed with respect to the lines obtained in the kernel matching. Since there are references for the matching, the search range is limited. The criterion for line correspondences is the same as that for kernel matching.

Elimination of conflict matched lines
Mismatching may happen in finding line correspondences. Bidirection matching is an efficient way to limit mismatching. In the process of bidirection matching, matching operations from the first image to the second one and from the second image to the first one are performed. Then line correspondences are confirmed if they exist in both directions of matches. Bidirection matching can usually eliminate most of the mismatched lines although some lines correctly matched only in one direction will also be removed.

Recovering the Position and Orientation of the camera

Absolute Orientation Based on Landmark Line


Fig.2. Geometric Relationship Between 3D Straight Line and 2D Image.
Before discussing the approach to absolute orientation based on landmark lines, we should address that the intrinsic parameters such as focal length, shift of the principle point, distortions of lens, pixel size difference in horizontal and vertical directions, etc. have been correctly determined, the camera should be considered as an ideal pinhole model.

Given a 3D straight landmark line L in the world space and its 2D projection l on the image, a plane through the center of camera S and the two straight lines can be obtained. Fig.2 shows the geometric relationship. Let N be the normal vector of the constructed plan, two geometric constrains are obtained as:

where, Nx, Ny and Nz are the components of N projected on three coordinate axis of the world coordinate system respectively; Xc, Yc, Zc, a,b, and g are the parameters of landmark line in world coordinate system. If more than 3 landmark lines have been matched to the image, the position and orientation of camera could be computed (Chen, 1999).

In the context of landmark-based navigation, it is possible to exploit some of the constraints imposed by the fact that most mobile robots and vehicle navigate on the ground plane in reducing the number of degrees of freedom in the transformation that maps the world model features into the image features. Most positioning tasks make the assumption that the camera is on the ground, so the height of the camera above the ground is assumed to be known or to be a constant. The pitch and roll angles of the camera can be measured with gyro because of its very little drift errors in the tilt and swing angles. So, there are effectively three parameters in the navigation: two translations (Xs, Ys) and one rotation (Yaw angle). This means that only 2D maps or GIS are able to be used to provide landmark information for navigation. So, if more than two straight lines can be extracted from the image and matched with the landmark lines of the map, (Xs, Ys) and Yaw angle of the camera could be calculated. Of course, these lines should be vertical.

For the mismatched lines, an effective approach to detecting blunders was used (Chen, 1999).

Relative Orientation
One of the most obvious characters of mobile robot or vehicle navigation is that the distance from the camera to landmark models in the real world is too near. This will cause very few or even none of any landmark lines could be extracted from the images.

Relative orientation is an effective approach to solve this problem, which describes the relative position and rotation of two neighboring images with respect to one another. It is a 5-parameter problem (see Fig.3). Suppose the position and orientation of one image (camera 1) are known. Based on the image a common coordinate system of the two neighboring images are constructed (Camera1-XYZ in Fig. 3). B denotes the distance between the two image, and is called base-line. Bx, By, and Bz denote the translation of the second image relative to the first one. Yaw, Pitch, and Roll denote the orientation of the second image relative to the first image.


Fig.3. Geometric Relationship of Relative Orientation.
Given a common point P in world space and its two image points in the two image p and p’, whose coordinates in Camera1-XYZ are (X, Y, Z) and (X’, Y’, Z’) respectively, a plane called epipolar plane can be obtained and described as:

To compute the (Bx, By, Bz, Yaw, Pitch, Roll) of the second image, at least five conjugate points from the two images are used. However, since in automatic relative orientation arbitrary conjugate features can be used, the power of redundancy can be readily exploited. Rather than five conjugate points needed to solve the 5-parameter problem, a few hundred points can be used. Due to high redundancy blunders caused by mismatched can be easily detected, and a better point distribution can be obtained. This makes the automatically generated orientation parameters more reliable and more accurate. In addition, the well known dangerous cylinder has no practical significance, since it is virtually impossible for all conjugate points to lie on one of these surface.