Anagram Engineering

Webdesign und Softwarelösungen aus Vorarlberg. Ihr Partner für innovative Lösungen rund ums Internet. Full Service Agentur.

Search for corresponding lines



Next: Object detection
Up: Correspondence Analysis
Previous: Correspondence Analysis

Search for corresponding lines

After the line lists for both images are generated, the correspondence problem needs to be solved. In contrast to an intensity-based correspondence analysis, there is no need to have a maximum disparity limit because all the lines are compared and thus all possible disparities are taken into consideration. But a constraint, that a line which is nearer than another is more likely to be chosen than a line which is more far away, has to be inserted. This constraint is needed, because if there are two objects mapped with approximately the same y-coordinate and approximately the same line properties, e.g. the same length, attitude and midpoint, as it is if two robots are next to each other, the left border of the robot could be matched with the left border of the other robot. Figure 3.12 depicts this situation.

To avoid matching of two opposite lines, the gradient direction is taken into consideration. Figure 3.12 shows the gradient direction for the left edge image (depicted as red arrows in the electronic version of this thesis at the top and bottom). To measure the similarity between two lines, the weighted sum of the difference between the attitude $ alpha$ , the direction $ theta$, the length $ g$ and the difference in the y-coordinate between the start and end point $ p_s,p_e$ of the line is computed. Let $ '$ denote a line inside the right image, then the rating $ r$ of a line $ l$ can be formulated as

$displaystyle r(l,l') = w_{pos}arrowvert p_s- p_s' arrowvert +w_{pos}arrowve... ...vert + w_{alpha} (alpha-alpha') + w_g (g-g') + w_{theta} (theta - theta')$ (3.15)


where $ w_{pos}$,
$ w_{alpha}$, $ w_g$ and
$ w_{theta}$ are weights, that define the importance of the line property. The currently implemented method uses
$ (0.5, 200, 0.1, 0)$ as $ Vec{w}$.
A line $ l$ corresponds to a line $ l'$, if

  • the rating $ r(l,l')$ is smaller than the best rating achieved, thus (
    $ forall x arrowvert r(l,l') leq r(l,x)$) must hold.
  • the x-coordinate of the compare point in the left image is greater than the x-coordinate of the compare point in the right image
  • the y-coordinate of the intersection between the horizontal line which has its origin in the left compare point and the line in the right image lies inside this line.
  • the rating $ r$ is below a given threshold
  • the calculated disparity between the two lines is smaller than the maximum disparity allowed
  • the difference of the gradient direction
    $ theta-theta'$ is below a given threshold

During the search for corresponding lines, every line inside the left image is compared with every line inside the right image. The lines with the best rating are considered as corresponding lines. If two lines fulfill the constraints mentioned above, the lines are removed from the list of possible candidates. To avoid false matches, the rating has to be smaller than a given threshold. If two corresponding lines with disparity $ d$ have been found, a horizontal line of length $ d$ is inserted in the left image. It has its origin in the midpoint of the left line and if the right line would be inserted into the left image, the compare point would be the end point of the line.

Next: Object detection
Up: Correspondence Analysis