One-bit transform (1BT)- and two-bit transform (2BT)-based block motion estimation (ME) schemes have been proposed in the literature to reduce the computational complexity of the ME process by enabling simple Boolean EX-OR matching of lower bit depth representations of image frames. Recently a multiplication-free 1BT (MF-1BT) has been proposed to facilitate 1BT to be carried out with integer arithmetic using addition and shifts only. Thresholding schemes are typically used in order to construct the lower bit depth representations utilized in 1BT and 2BT. In our experience we have observed that one problem with such schemes is that pixel values that lie on directly opposite sides of the threshold are categorized into separate classes and are, therefore, counted as a nonmatch in the search process even if they are close in value. A constrained 1BT (C-1BT) that restricts pixels with values adjacent to the transform threshold during 1BT matching, counting them as a match regardless of their 1BT value, is proposed in this paper. It is shown that the proposed C-1BT approach improves the ME accuracy of 1BT-based ME and even outperforms 2BT-based ME at macroblock level.