Correspondence Problem

In this project, every method and algorithm described was implemented in an FPGA, either on Microblaze using C or directly in Verilog. This way the whole system is implemented in a single board, making it more useful and portable.

Because of the limited instructions memory available on the FPGA, an advanced method of finding correspondences is impossible to design. The correspondence problem was made simple by dividing it into some small weighting functions. The various actions of the functions are now listed, in chronological order:

• One image is read from the image, and analysed block by block, using a block size of 5x5.
• The block is submitted to a non-linear corner detection function. To make it simple, a detection of non-corner characteristics is performed, instead of the corner itself. The following picture represents some of the rejected masks of blocks:

The method is restarted from the previous point if a non-corner block is detected.

• The block is analysed with an algorithm similar to SUSAN and Census, but a little simpler. The algorithm returns a value seen as the block's value, or quality. This value is calculated as the higher value, between the sum of the pixels with less value (luminosity) than the central pixel, and the pixels with higher value. Pixels with a luminosity value similar to the central pixel are ignored, in order to suppress noise effect.
  • The image is divided in different zones, of 80x60 pixels, and a list of the blocks with higher quality is saved for each zone. This division is important in order to obtain correspondence matches throughout the entire image, improving the precision of the calculation of the required transformation.
• For each candidate in the lists, a search for a match is performed in the other image. The search-area is defined as a rectangular block around the same coordinates. This area is iteratively reduced around the epipolar line, calculated in the beginning of next phase.
  • A block is read for each pixel in the search-area, and a function evaluates the similarity. The similarity of the blocks (around the central pixels) is calculated based on:
    • A linear comparator - SAD. Sensitive to luminosity changes, and susceptible to noise.
    • A non-linear comparator - based on the algorithm used to obtain the quality: the number of pixels that: a pixel has a higher value than the central one and the corresponding pixel from the other image as a smaller value, or vice-versa. Sensitive to characteristics changes (corners, etc...), and insensitive to noise.
    • The distance to the epipolar line. For simplification proposes, the distance taken into account is only the vertical distance. This fact is acceptable in stereo kits where the cameras are aligned (practically) horizontally.
    • For solving draws, the quality of the blocks of both images is summed to the similarity value.
  • For each candidate in the reference image the coordinates of best matches are saved.
  • The matches for each candidate is refined, using the same algorithms as in the last steps, but this time using a block size of 15x15.
  • The similarity value for each candidate is replaced by it's unicity: the difference between the similarity of the best match and the similarity of the second best match. This eliminates errors in patterns and repetitive textures, giving more importance to unique corners and characteristics.
  • A list of the best correspondences between images is constructed using various weighting conditions:
    • For each zone of the reference image only 2 correspondences can be saved. This makes the final correspondence list have points throughout the entire images.
    • A match cannot have a similarity value less than 1/10 th of the best match. This eliminates not-so-sure correspondences.

This proposed algorithm as been thoroughly tested in the given cameras. These cameras have significant blur effect and lens distortion, and even so this algorithm was capable of detecting correspondences with good quality, as can be seen in the next image.

In about 40 correspondences only 2 of them were wrong (white arrow). After the second iteration using the epipolar geometry calculated from these pairs' coordinates (see next phase), these wrong correspondences were detected and eliminated, resulting in 40 good correspondences.

The coordinates of the correspondence pairs are extracted, end sent to another algorithm which estimates the epipolar geometry used in the next iteration, and finally calculates the transformation required to the videos. These transformations perform the stereo-video rectification.