Patent ID: 7027511

Claim:
A fast motion estimation of a video sequence using N-queens pixel decimation, comprising the steps of: (a) selecting a reference block and a block to be processed in a video sequence, each said block being composed of N×N pixels, where N is a number larger than or equal to 4; (b) selecting in each said block N pixels in accordance with an N×N queens pattern, said N pixels of said N×N queens pattern simultaneously fulfilling all of the conditions of: (i) none of said N pixels occupies a position in said block along the same row as any other one of said N pixels; (ii) none of said N pixels occupies a position in said block along the same column as any other one of said N pixels; and, (iii) none of said N pixels occupies a position in said block along the same diagonal as any other one of said N pixels; (c) calculating a block difference value to determine if said reference block matches said block to be processed and determining motion estimation parameters from said matching blocks if said block difference value matches a predetermined criterion, proceeding to step (d) otherwise; (d) selecting a next reference block and block to be processed and repeating the method at step (b) until said block difference value matches said predetermined criterion; and (e) determining said motion estimation parameters from said matching blocks.