Successive Elimination Algorithm for Constrained One-bit Transform Based Motion Estimation Using the Bonferroni Inequality

The constrained one-bit transform (C1BT) was proposed to increase the motion estimation (ME) accuracy of the previous one-bit transform (1BT) especially for small motion blocks. Although making another bit-plane is very simple and efficient, its performance is even better than that of the two-bit transform (2BT) based ME. However, unlike the 1BT-based ME and the 2BT-based ME, the successive elimination algorithm (SEA) based on the triangle inequality for C1BT-based ME cannot be derived because C1BT matching error criterion does not satisfy the typical measure conditions. In this letter, a fast full-search block matching algorithm for C1BT-based ME is developed. The proposed algorithm evaluates lower bounds for constrained one-bit matching criterion based on the Bonferroni inequality to eliminate the impossible candidates faster and save computations substantially. Experimental results show that while the ME accuracy of the proposed algorithm is the same as that of the full search C1BT, the proposed algorithm reduces computational complexity significantly.