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.

 

SEA

 

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

Blog at WordPress.com.

Up ↑

%d bloggers like this: