A block-matching method reduces pixel depth prior to match evaluation to drastically reduce the computations required intensive block-matching applications such motion estimation for video compression. Pixel-depth reduction is achieved by analyzing incorporating images to determine how to reduce pixel depth so as to retain information useful for block matching. Original pixel values (e.g., 8-bit), are compressed to lower-depth (e.g., e.g., 1-bit or 1.6-bit) pixel values. The resulting converted blocks are XORed to yield a comparison image. The 1s in the comparison image are tallied to provide a match measure. In the image analysis, the original images can be subsampled and averages can be computed based on the subsample pixels to reduce computational overhead.