This paper presents a novel bi-directional motion estimation technique, which determines the motion vectors more accurately in situations when there are variations in the inter-frame characteristics due to the changes in the brightness values of the corresponding pixels from frame to frame. The proposed bi-directional motion estimation technique is applied specifically to the fixed-size block, variable-size block and region-wise motion compensation schemes. The proposed method is applied to a number of benchmark video sequences and the results are compared with those obtained by applying the existing methods. These results show that the proposed method can improve the rate-distortion performance. In particular, in situations when there are large variations in the brightness of the corresponding regions from frame to frame, the proposed method improves significantly the rate-distortion performance.