A new Elastic-Block Matching Algorithm using bilinear space warping is proposed. In this scheme a convex quadrilateral, which minimizes a distortion measure against the current square block, is searched to compensate the shape deformation caused by a rigid body's 3 dimensional depth motion or rotation. The proposed algorithm gives a remarkable improvement in motion-compensated prediction compared with the conventional algorithm.