We present a technique to improve the speed of block motion estimation using only a subset of pixels from a block to evaluate the distortion with minimal loss of coding efficiency. To select such a subset we use a special sub-sampling structure, N-queen pattern. The N-queen pattern can characterize the spatial information in the vertical, horizontal and diagonal directions for both texture and edge features. In the 4-queen case, it has a special property that every skipped pixel has the minimal and equal distance of one to the selected pixel. Despite of the randomized pattern, our technique has compact data storage architecture. Our results show that the pixel decimation of N-queen patterns improves the speed by about N times with small loss in PSNR. The loss in PSNR is negligible for slow motion video sequence and has 0.45 dB loss in PSNR at worst for high motion video sequence.