# US 7,609,765 B2 · Fast multi-frame motion estimation with adaptive search strategies

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 7,609,765 B2
- Document ID: US7609765B2
- Status: Granted
- Kind: B2
- Application number: 11/004,004
- Filed: 2004-12-02
- Published: 2006-06-08
- Granted: 2009-10-27
- Earliest claimed: 2004-12-02
- Assignees: Intel Corporation
- Inventors: Eric Li
- Web page: https://patentgrep.com/patent/US7609765B2

## CPC

- H04N 19/513: Processing of motion vectors
- H04N 5/145: {Movement estimation (for video coding H04N19/51)}
- H04N 19/57: Motion estimation characterised by a search window with variable size or shape
- H04N 19/573: Motion compensation with multiple frame prediction using two or more reference frames in a given prediction direction
- H04N: PICTORIAL COMMUNICATION, e.g. TELEVISION

## Abstract

A method includes examining a statistical distribution of motion vectors employed for motion compensation in a first frame of image data. The examining is to produce a distribution model of the motion vectors in the first frame. The method further includes selecting, based at least in part on the distribution model, a block-matching search pattern for use with respect to a second frame of image data. The second frame follows the first frame in a sequence of frames of image data.

## Claims

### Claim 1

A method comprising:
examining a statistical distribution of motion vectors employed for motion compensation in a first frame of image data, said examining to produce a distribution model of said motion vectors in said first frame, said distribution model being a range of said motion vectors and associated probabilities; and
selecting, based at least in part on said distribution model, a block-matching search pattern for use with respect to a second frame of image data, said second frame following said first frame in a sequence of frames of image data;
wherein said examining includes calculating a mean value MVmean of the motion vectors employed for motion compensation in said first frame;
wherein said examining includes calculating a dimension M of a diamond-shaped area which contains at least 99% of the motion vectors employed for motion compensation in said first frame;
wherein M is the smallest value which satisfies the condition:
λ(1+β+β2+ . . . +βM)>=0.99, with:
λ=1/MVmean, and
β=1-(/MVmean).

### Claim 2 (depends on 1)

The method of claim 1, wherein said selecting includes selecting between a hexagonal search pattern and a cross search pattern.

### Claim 3 (depends on 1)

The method of claim 1, further comprising:
determining a motion vector for use with respect to a block of pixel data of said second frame, said determining being performed with the selected block-matching search pattern.

### Claim 4 (depends on 3)

The method of claim 3, further comprising:
performing motion-compensated compression-coding of said block of pixel data of said second frame, said motion-compensated compression-coding utilizing said motion vector for use with respect to said block of pixel data of said second frame.

### Claim 5

A method comprising:
determining a characteristic of a first frame of image data, said characteristic being a statistical characteristic of motion vectors employed for motion compensation in said first frame of image data; and
selecting, on the basis of the determined characteristic, between a first block-matching search pattern for use with respect to a second frame of image data and a second block-matching search pattern for use with respect to the second frame of image data, said second frame immediately following said first frame in a sequence of frames of image data;
wherein said determining includes calculating a mean value MVmean of the motion vectors employed for motion compensation in said first frame;
wherein said determining includes calculating a dimension M of a diamond-shaped area which contains at least 99% of the motion vectors employed for motion compensation in said first frame;
wherein M is the smallest value which satisfies the condition:
λ(1+β+β2+ . . . +βM)>=0.99, with:
λ=1/MVmean, and
β=1-(/MVmean).

### Claim 6 (depends on 5)

The method of claim 5, wherein said selecting includes selecting between a hexagonal search pattern and a cross search pattern.

### Claim 7 (depends on 5)

The method of claim 5, further comprising:
determining a motion vector for use with respect to a block of pixel data of said second frame, said determining being performed with the selected block-matching search pattern.

### Claim 8 (depends on 7)

The method of claim 7, further comprising:
performing motion-compensated compression coding of said block of pixel data of said second frame, said motion-compensated compression coding utilizing said motion vector for use with respect to said block of pixel data of said second frame.

### Claim 9

An apparatus comprising:
a storage medium having stored therein instructions that when executed by a machine result in the following:
examining a statistical distribution of motion vectors employed for motion compensation in a first frame of image data, said examining to produce a distribution model of said motion vectors in said first frame, said distribution model being a range of said motion vectors and associated probabilities; and
selecting, based at least in part on said distribution model, a block-matching search pattern for use with respect to a second frame of image data, said second frame following said first frame in a sequence of frames of image data;
wherein said examining includes calculating a mean value MVmean of the motion vectors employed for motion compensation in said first frame;
wherein said examining includes calculating a dimension M of a diamond-shaped area which contains at least 99% of the motion vectors employed for motion compensation in said first frame;
wherein M is the smallest value which satisfies the condition:
λ(1+β+β2+ . . . +βM)>=0.99, with:
λ=1/MVmean, and
β=1−(/MVmean).

### Claim 10 (depends on 9)

The apparatus of claim 9, wherein said selecting includes selecting between a hexagonal search pattern and a cross search pattern.