Block Matching Algorithm (BMA) which is widely used in motion-compensated image coding to remove the interframe redundancy, has some implicit drawbacks. BMA estimates only the translational motion vectors on block-by-block basis and hence cannot estimate the change of scale or rotation. To overcome this problem this dissertation proposes a new Elastic Block Matching Algorithm (EBMA), which searches for a convex quadrilateral after the conventional search by the BMA.
First, the effect of 3D motion of planar object on 2D projection image plane is analyzed, and then a 2D image transformation of bilinear form is selected as a motion model for an image block. By applying the bilinear model to a block, the block transforms to an elastic quadrilateral block and we can stretch its vertices to any direction.
Second, a new EBMA is proposed. In this algorithm, instead of calculating the motion parameters directly, the corresponding vertices of a convex quadrilateral is estimated in the reference image by matching all. It consists of two steps of procedure: one for the estimation of translation and the other for the estimation of shape deformation. After the initial estimation by translational block motion, the EBMA moves the vertices of predicted block to compensate for shape deformation.
The EBMA is found to give a remarkable gain in motion-compensated interframe prediction compared with the BMA.
Finally, a method to design the EBMA for realtime image data up to 10 Mpixels/sec is studied. In this design, Image Resampling Sequencer which is used in Digital Video Effect Equipment is used to warp the predicted block.