Acceleration of block matching by indirectly comparing square errors

For accelerating block matching using square errors as distance, we will propose a method of simplifying the search of the minimum distance value. Before determining the distance value between blocks, the distance value is indirectly compared with the minimum value up to this time by using an evaluation value whose operation is small, and the case in which the distance value cannot reach a minimum is decided. By doing so, the number of times of actually determining the distance value can be reduced. The ratio of processing times for the algorithm of searching the minimum value by determining all distance values becomes a linear function of the ratio (ratio of indirect decision) of the blocks which can be indirectly decided. We have performed a simulation of the proposed algorithm by applying it to the block matching for the detection of motion vectors between moving pictures. As a result, it was confirmed that the processing time can be reduced by about 20% by enlarging the set (searching space) of searching the minimum value. Moreover, experiments have shown that the ratio of indirect decision inside the sequence after the block at which it becomes a minimum distance inside that space will became larger. Accordingly, the proposed algorithm is executed by performing ordering inside the space such that the block of becoming a minimum distance comes to the front. As a result, the processing time is further reduced by about 20%, thus proving that such ordering is effective in the proposed algorithm. © 2002 Wiley Periodicals, Inc. Electron Comm Jpn Pt 2, 85(8): 65–75, 2002; Published online in Wiley InterScience (www.interscience.wiley.com). DOI 10.1002/ecjb.10067