A novel two-bit transform based block motion estimation (ME) algorithm is presented in this paper. The proposed approach achieves more effective binarization of image frames than the previous 2BT approach by making use of the positive and negative derivative values separately, which are computed from the second derivatives of a local area as the threshold value for the second bit plane. The second derivatives are also used to find the most accurate motion vectors (MVs) and to reduce computational complexity. Experimental results show that the proposed binary motion estimation algorithm improves motion estimation accuracy and furthermore provides faster processing time in flat or background regions with an acceptable bit-rate increase. In applying the proposed 2BT-SD approach in a real video compression standard, a further reduction of ME processing time with reasonably good compression efficiency is achieved by 2BT-SD based integer ME (IME) followed by full resolution fractional ME.