Other Free Encyclopedias » Online Encyclopedia » Encyclopedia - Featured Articles » Contributed Topics from A-E

Block Matching

estimation disparity error field

Definition: Block matching is the most widely used method for disparity estimation in stereo coding algorithms.

Disparity/depth estimation is an important key step in many stereo coding algorithms, since it can be used to de-correlate information obtained from a stereo pair. In the predictive coding framework (consisting of disparity estimation/compensation, transform/quantization, and entropy coding), the redundancy is reduced by compensating the target image from the reference image with the disparity vectors.

Block matching is the most widely used method for disparity estimation and is simple and effective to implement. The basic idea of block matching is to segment the target image into fixed size blocks and find for each block the corresponding block that provides the best match from the reference image. In general, the block minimizing the estimation error is usually selected as the matching block. However, block matching with a simple error measure may not yield smooth disparity fields, and thus may result in increased entropy of the disparity field and therefore increased bit rate of the disparity field. The proposed schemes to improve the estimation efficiency include: genetic algorithms, subspace projection methods, extended windows, balanced filtering, RD-based estimation and dynamic programming algorithm.

Another approach to improve the estimation efficiency is relaxing the one-vector-per-block assumption, e.g. the annoying blocking artifacts in the reconstructed image. In fixed size block matching, the higher prediction errors occur because the block boundaries do not coincide with the object boundaries. By reducing the block size, the estimation error can be reduced, but as the block size becomes smaller the associated overhead (bit rate) required to transmit the disparity field becomes too large. In addition, smaller blocks frequently fail to provide good matching results because the estimation is subject to various noise effects and thus a less homogeneous disparity field is generated. Note that pixel-based estimation is the best way to reduce the entropy of the disparity compensated difference frame. However, this comes at the cost of an expensive increase in the overhead necessary to represent the resulting disparity field. Meanwhile, increasing the block size increases the robustness against noise in the disparity estimation, but it also increases the magnitude of the estimation error. A good solution to this dilemma is hierarchical (or sequential) block segmentation. Segmenting a block with higher prediction error into smaller subblocks can further reduce the rate. Another approach is region matching, instead of block matching, which allows more efficient estimation by considering complex displacement. Obviously, region or object-based schemes are attractive because they have many advantages and allow the addition of various object-based functionalities, which are well supported by the MPEG-4 standard.

Blom, Eric (Walter) [next] [back] Blochwitz, Hans Peter

User Comments

Your email address will be altered so spam harvesting bots can't read it easily.
Hide my email completely instead?

Cancel or