Stereo Matching Using the Hausdorff Distance

EE148 Project Webpage

Team Members: Philip Nowell, Sam Thompson, Lilli Davis


Project Summary

The problem of reconstructing 3d information from 2d stereo images is a long standing and difficult one. One of the most difficult aspects of this problem is that of automatically determining matching features between the stereo image pair. The problem of curve matching between image pairs is made difficult because the topilogical connections between the segments may be lost or distorted between the images. Depending on the baseling and relative rotation of the cameras, curves may be deformed, segmented, or not correspond at all between the left and right images.

The algorithm which we have implemented as a method of stero matching applies a mathematical metric known as the Hausdorff Distance as a feature-based method of establishing correspondences between the stereo image pair. Though for all our test images we used stereo images separated by a relatively small baseline and cameras with little relative rotation, the Hausdorff metric applies equally well to images which vary to a greater degree.

The Hausdorff Distance

The Hausdorff distance between the sets of points on two curves A and B is the maximum over each element a of A of the minimum over each element b of B of the distance from a to b. More simply, take the first element a of A and find the minimum distance to the set B. Do that again for the second element of A, and so on until you've done it for every element of A, and the Hausdorff distance is defined as the maximum of each of these minimum distances.

The Hausdorff distance may be defined more concisely as


In the stereo matching process before the Hausdorff distance may be applied between two curves the disparity of each curve must be calculated. The disparity is defined as the optimal traslation for a curve in the left*1* image so that if the left and right images were superimposed, the curve from the left image would be directly on top of the curve to which it matches. Thus before the Hausdorff distance may be usefully calculated between two curves the curves must be superimposed so that they overlap as much as possible.

    *1* The algorithm we chose to implement matches curves from the left image to the right image though this is arbitrary and may be reversed.
The Hausdorff distance, when taken between two optimally superimposed curves will then give a mathematical indication of how similar the two curves are. Though the Hausdorff metric itself is relatively straightforward and simple to apply, because it must be applied to point sets there are several steps of preprocessing which an image must undergo in order to extract and organize the curves.

Image Pre-Processing


Pre-processing is the term we use to describe all the steps which must be implemented in order to reduce a pair of stereo images to data structures holding sets of curves which can then be usefully manipulated.

  • Step #1: GAUSSIAN SMOOTHING
The first step in the image processing is to apply a simple Gaussian filter so that noise on the image will not be deteced as curves. The Gaussian filter works by using a weighted average of the colors surrounding any one pixel within a five pixel radius. The value of the pixel is set to be the average of the surrounding pixels with the pixels being weighted so that the nearest ones are most influential on the the color of the center pixel. This process is applied to the image once horizonally and then once vertically; The two blurring passes being separated to increase our computational efficiancy.


  • Step #2: EDGE DETECTION
Once the image has been smoothed it is ready to have an edge detection algorithm run on it. The edge detection process works by passing through every pixel to pixel transition and marking an edge if the discrepancy in color between the two pixels is above a threshold value. The results of the edge detection algorithm can be seen below.


  • Step #3: EDGE THINNING
But, as can be seen above, the edges acquired by the edge detection algorithm are in some places several pixels thick. The Hausdorff matching algorithm requires curves no wider than one pixel. We therefore thinned the edges using an 8 neighbor rule. To understand the eight neighbor rule it is helpful to visualize each pixel (marked as 0) surrounded by it's eight neighbors.



Starting at the pixel marked '1', all the nighbors around the pixel are traversed in order and the number of 0 to 1 transitions is counted. A 0 to 1 transition means that you have come from a pixel which is not used in an edge onto a pixel which is used in an edge. This information allows one to determine weather or not the pixel is on an edge boundary and therefore should be deleted.

A pixel P is flagged for deletion if it satisfies the following conditions:
  • The sum of the values (0 or 1) of the neighbors of P is >= 2 and <= 6
  • There is only one 0 to 1 transition when the pixels around P are traversed in order
  • neighbors 1, 3, 5 all equal 0 (are not used in any edge)
  • neighbors 3, 5, 7 all equal 0 (are not used in any edge)
A pixel which satisfies these conditions is not deleted immediately but only flagged for deletion because edge thinning is occuring on both boundaries of the curve. Thus in a two pixel wide curve, both the left and right sides could be deleted.

To ameliorate this problem, two passes are used for the completion of the algorithm. After all of the pixels are marked for deletion, in the first pass all teh south and east pixels are deleted and in the second pass all the north and west pixels are deleted. Splitting the process into two halves allows the process to efficiantly thin the edges into one pixel wide curves.


  • Step #4: CURVE COLLECTION
Once all edges have been thinned to one pixel wide contours, the edges may be segmented into individual curves. The segmentation of the edges into curves is accomplished by locating pixels which have three or more neighbors. These pixels are junctions where three or more curves meet. All that needs to be done in order to segment the edges into cuves is to remove these junction pixels, the loss of a single pixel not being a significant change to our data set.

Once the edges have been segmented into cuves, the curves are collected and stored in an array. Each curve is represented by an array of numbers known as a chain code. A chain code is constructed by beginning at the head of the curve and storing the neighbor value of the next pixel in the curve. The neighbor value is a number from 1 to 8 which is an indication of the location of the next pixel in the curve, with north being 1, south being 5, and so on.

representation of a pixel (marked 0) and it's neighbors,
chain codes consist of lists of neighbor values as the curve is traversed


After the curve collection process, an array of curves represented as chain codes has been created and stored for futher use. The following is an image of the segmented curves, the colors differentiating between distinct curves.


  • Step #5: WEAK VISIBILITY GRAPH
To accurately match the curves between the stereo pair of images it is necessary to store information about which curves are 'near' which other curves. To collect this information we chose to use a weak visibility graph. In a weak visibility graph each curve is represented by a vertex. Two vertices are connected if there is a line in any direction which can connect the two curves without passing through another curve. The nodes are connected by edges which are weighted according to the distance between the two curves. Thus the total weak visibility graph contains information about all the curves, which other curves they are near, and how far the curves are apart.

  • Step #6: MINIMUM SPANNING TREE
The weak visibility graph in itself, however, is a little too bulky to be of much direct use in the matching computation. To turn the graph into a usefull object a minimum spanning tree must be calculated. There are many algorithms for taking the minimum spanning tree of connected graphs, and we chose to use a relatively simple process called Kruskal's algorithm.

In Kruskal's algorithm all edges of the graph are sorted according to weight with the smallest edges first. Then to form the minimum spanning tree edges are simply added in order but before each edge is added there is a check to be certain that a loop was not formed. The result of this process is that the shortest edges are added while the longest edges are all towards the end of the list and are therefore left out of the tree as by the time they are reached the whole tree has been spanned.


  • Step #7: VORONOI DIAGRAM
To complete the pre-processing it is necessary for information about the relative locations of each curve to be stored in one more way. In addition to a minimum spanning tree, our algorithm employs a voronoi diagram to store information about which curves are near to which other curves. To create a voronoi diagram each pixel is colored according to the minimum distance from that pixel to any other pixel. Black regions in the voronoi diagram indicate the presence of many curves in that area whereas the white regions indicate places where curves are more sparsely distributed.


The Matching Process

Once the preprocessing stage has been completed our stereo images have been reduced to a collection of data indicating the location of each curve in each image and how the curves in each image relate to each other. The actual matching process begins with choosing a starting edge in the left image called the root node.

The root node is chosen to be one of the longest and straightest curves in the left image because a long straight curve will have a much lower probability of being noise. Also such a curve will be more likely to have a good match in the right image--a good match meaning a corresponding curve which does not branch or diverge in some strange way.

Once the root has been found in the left image, it is placed on a voronoi diagram of the right image in such a way as to maximize the amount of black on the root curve. That is, the root is moved around in the voronoi diagram until it is placed on top of a curve which it most resembles. To place the root in the right image a search window of fixed size is used. This search window is determined by some basic assumptions such as that curves from the left image will be translated left in the right image and that the curve will not be translated much in the y direction between the stereo images. After the root node has been placed the translation which optimally placed the curve is recorded as the curves disparity.

origonal placement of root node from left image on the right image voronoi diagram and the calculated optimal location of the root node.


To match the remaining curves the minimum spanning tree is traversed recursively with each node passing its disparity to its neighbors to dynamically determine a search window for each node. This dynamic search window determination adds significantly to both the efficancy and accuracy of the matching process as each curve need only be matched within a small search window, and this, in turn, makes it less likely that curves will match to similar curves which are far away in the image.

After the minimum spanning tree has been traversed completely and each curve from the left image has been placed optimally on the right image, matching points are determined by simply stepping along each properly placed curve from the left image and taking the nearest point in the right image. It is necessary to match points instead of curves because in the stereo images curves could be eliminated or segmented and therefore you will not have a one to one curve correspondence between the two images.

Final Results

Here is a picture of our final results. Each point is colored the same as the point which we calculated it matched to. As can be sees, the curve matching algorithm which we implemented worked quite well.



When starting our project our intent had been to actually reconstruct a 3D image by triangulating between our matched points. But in attempting to do this we ran into problems reconstructing our image because the matching points triangulated to 3D points which varied too much in space. Therefore, because of the nature of the 3D construction, we ended up with many disconnected and spiky horizontal slats across our image.

If given more time, we would either attempt to implement a simple ball-pivot algorithm to connect our horizontal slats (after applying some sort of smoothing filter) or attempt to apply our algorithm to multiple perspective views of the same object in the hopes of getting better information. But since our time to work on the project is up, we consider our project complete having finished the curve matching algorithm. We are pleased with our results as effective automatic feature matching between stereo image pairs is a significant accomplishment in itself.

Team Member Responsibilities

Note: Though each team member was made responsible for specific aspects of the project, most methods were written collaboratively and therefore the ascription of any one task to any one individual is somewhat difficult.

Philip Nowell:
  • Research
  • Curve Segmentation and Storage
  • Edge Detection, Gaussian Smoothing
  • Edge Thinning
Sam Thompson:
  • Weak Visibility Graph
  • Minimum Spanning Tree
  • Matching Methods
  • Testing Functions
Lilli Davis:
  • Research , Final Report
  • Root Node Calculation
  • Disparity Evaluation
  • Matching Methods

References

[Kedem, Yarmovski96]: Klara Kedem and Yana Yarmovski, "Curve Based Stereo Matching Using the Minimum Hausdorff Distance", Symposium on Computational Geometry, 415-418, May 1996.

[Schmid, Zisserman00]: Cordelia Schmid and Andrew Zisserman, "The Geometry of Matching Lines and Curves Over Multiple Views", International Journal of Computer Vision, 40(3):199-233, 2000.

[Davis?]: Larry Davis, "Edge and Local Feature Detection"

Related Websights & Additional Information

Contact Information

Lilli Davis : davis@ugcs
Philip Nowell : nowell@cs
Sam Thompson : samuelt@its