Is exhaustive search “optimal”?
A. Definitely not in the context of block-based MCP video. Since one motion vector represents the prediction of 256 pixels, divergent pixels within the macroblock are misrepresented by the “global” vector. This leads back to the general philosophy of block-based coding as an approximation technique. In their ICASSP’93 paper, Sullivan discusses ways in which block-based prediction schemes can solve part of this problem. Exhaustive search may find blocks with the least distortion (displaced frame difference) but will not produce motion vectors with the lowest entropy.
