Successive Elimination Algorithm (SEA) for video motion estimation

The successive elimination algorithm (SEA) is one of the excellent lossless fast algorithms that effectively accelerates the search speed without loss of performance compared to that of brute force FULL search. SEA reduces the number of SAD calculations of the match point using a concise inequality, avoiding further calculation of points that will not become the best match point. A point (i, j) that could be the best match point in the SEA has the following prerequisite:

∇ Sum0 – MinSAD ≤ ∇ Sum(i, j) ≤ ∇ Sum0 + MinSAD

where ∇ Sum0 is the sum of the grayscale absolute value of all coding block points, MinSAD is the minimum SAD of the searched points, and ∇ Sum(i, j) is the sum of the grayscale absolute value at all points of the block that matches (i, j). Whether the matching calculation process of a point (i, j) is terminated depends on whether the above formula is met. When considering a new match point, we first determine whether it meets the formula. If it does, SAD(i, j) is calculated,  otherwise the process skips this point. If SAD(i, j) is smaller than the current MinSAD, then MinSAD = SAD(i, j) and the corresponding vector is updated. The final search result is MinSAD and its corresponding motion vector.