# US 2004/0202373 A1 · Method and apparatus to reduce the system load of motion estimation for dsp

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

- Number: US 2004/0202373 A1
- Document ID: US20040202373A1
- Status: Published application
- Kind: A1
- Application number: 10/249,440
- Filed: 2003-04-10
- Published: 2004-10-14
- Earliest claimed: 2003-04-10
- Assignees: Faraday Technology Corp.
- Inventors: Heng-Kuan Lee; Yu-Min Wang; Ching-Jer Liang
- Web page: https://patentgrep.com/patent/US20040202373A1

## CPC

- G06F 17/16: Matrix or vector computation {, e.g. matrix-matrix or matrix-vector multiplication, matrix factorization (matrix transposition G06F7/78)}
- G06T 7/223: using block-matching
- H04N 19/43: Hardware specially adapted for motion estimation or compensation
- H04N 19/61: in combination with predictive coding
- G06T 2200/28: involving image processing hardware
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- G06T: IMAGE DATA PROCESSING OR GENERATION, IN GENERAL
- H04N: PICTORIAL COMMUNICATION, e.g. TELEVISION

## Abstract

A method and apparatus to reduce the system load of motion estimation for DSP discloses circular buffers, a plurality of absolute difference calculation circuits, a multiple input adder, a full adder, a plurality of accumulators, and a control circuit. The first four bytes from the reference block buffer and the first four bytes from the search window buffer are sent to the four absolute difference calculation circuits. The control circuit determines which of the accumulators requires incrementing the value already in that accumulator by the current output of the multiple input adder. A new set of bytes from the search window buffer is then sent to the absolute difference calculation circuits, a new sum is calculated, and a second accumulator is incremented by the new sum. When all accumulators have been updated, new reference block data used. Each byte of data is loaded from memory only once.

## Claims

### Claim 1

A digital signal processor comprising:
a first buffer for storing data from a reference block;
a second buffer for storing data from a search window;
a plurality of absolute difference calculation circuits for calculating the absolute difference between the reference block data and the search window data;
a multiple input adder for summing outputs from the absolute difference calculation circuits;
a plurality of accumulators, each accumulator corresponding to a different search location within the search window and for accumulating the sums of absolute differences corresponding to that search location;
a full adder for adding the sums of the absolute differences corresponding to one of the search locations to a value held in the accumulator corresponding to that same search location; and
a control circuit for determining which portions of data in the first buffer and in the second buffer are transmitted to the absolute difference calculation circuits and for determining to which accumulator the transmitted data corresponds.

### Claim 2 (depends on 1)

The digital signal processor of claim 1 wherein the control circuit determines which portions of data in the first buffer are transmitted to the absolute difference calculation circuits such that each portion of reference block data is loaded from memory into the first buffer only one time when calculating match values for a plurality of search locations equal to the plurality of accumulations.

### Claim 3 (depends on 1)

The digital signal processor of claim 1 wherein the first buffer and the second buffer are registers.

### Claim 4 (depends on 1)

The digital signal processor of claim 1 wherein the plurality of absolute difference calculation circuits is equal to four.

### Claim 5 (depends on 4)

The digital signal processor of claim 4 wherein the plurality of accumulators is equal to four.

### Claim 6 (depends on 1)

The digital signal processor of claim 1 further comprising a multiplexer controlled by the control circuit to select one of the plurality of accumulators so that the value held in the selected accumulator is input to the full adder.

### Claim 7 (depends on 6)

The digital signal processor of claim 6 further comprising a demultiplexer controlled by the control circuit so that after the value held in the selected accumulator is input to the full adder, an output of the full adder is stored in the selected accumulator.

### Claim 8 (depends on 7)

The digital signal processor of claim 7 wherein the control circuit rotates selection of the plurality of accumulators on a round-robin basis, a different accumulator being selected each time different data is transmitted from the second buffer to the absolute difference calculation circuits.

### Claim 9 (depends on 8)

The digital signal processor of claim 8 wherein each absolute difference calculation circuit comprises a subtractor, a multiplexer, and diode inverter.

### Claim 10 (depends on 9)

The digital signal processor of claim 9 wherein each subtractor outputs a carry signal to a decoder, the decoder summing the carry signals from the plurality of subtractors and outputting the sum of the carry signals to one input of the multiple input adder.

### Claim 11

A digital signal processor for calculating image correlational values between a reference block and a plurality of search locations within a search window, the digital signal processor comprising:
a first buffer for storing data from the reference block;
a second buffer for storing data from the search window;
a plurality of absolute difference calculation circuits for calculating the absolute difference between a plurality of bytes of data from the first buffer and an equal plurality of bytes of data from the second buffer, the differences being summed by a multiple input adder and output as a first result;
a plurality of accumulators, each accumulator for uniquely accumulating first results corresponding to a specific search location;
a control circuit for determining which bytes of the first buffer and which bytes of the second buffer are transmitted to the absolute difference calculation circuits; and
a multiplexer for determining which accumulator is to accumulate the first results, the multiplexer selecting one of the accumulators according to a signal from the control circuit;
wherein when the control circuit transmits each first set of bytes from the first buffer to the absolute difference calculation circuits, a plurality of second sets of bytes from the second buffer, each second set of bytes uniquely corresponding to one of the plurality of search location, are sequentially transmitted to the absolute difference calculation circuits such that the first result generated by each second set of bytes is accumulated in the accumulator corresponding to that search location.

### Claim 12 (depends on 11)

The digital signal processor of claim 11 wherein the multiplexer selects one of the accumulators according to a signal from the control circuit, the signal comprising the least significant bits of a byte number transmitted by the control circuit from the second buffer to the absolute difference calculation circuits.

### Claim 13 (depends on 12)

The digital signal processor of claim 12 further comprising a full adder with one input connected to an output of the multiple input adder for receiving the first result.

### Claim 14 (depends on 13)

The digital signal processor of claim 13 further comprising a demultiplexer for allowing transmission of a value in the selected accumulator to another input of the full adder.

### Claim 15 (depends on 14)

The digital signal processor of claim 14 wherein each absolute difference calculation circuit comprises a subtractor, a multiplexer, and diode inverter.

### Claim 16

A method to reduce system load during motion estimation in a digital signal processor by calculating absolute differences between a reference block and a plurality of search locations within a search window at the same time, the digital signal processor comprising a first buffer and a second buffer for storing pixel data, a plurality of absolute difference calculation circuits, a multiple input adder, a full adder, a plurality of accumulators, and a control circuit, the control circuit having a storage unit comprising indices indicating an address in the first or second buffer, the method comprising:
initializing all accumulators and indices;
loading data from a reference block into the first buffer;
loading data from the search window in memory into the second buffer;
transmitting a first set of data in the first buffer and a second set of data in the second buffer to the absolute difference calculation circuits;
incrementing the value in a first selected accumulator by the absolute differences between the first set of data in the first buffer and the second set of data in the second buffer;
transmitting the same first set of data in the first buffer and a different second set of data in the second buffer to the absolute difference calculation circuits; and
incrementing the value in a second selected accumulator by the absolute differences between the first set of data in the first buffer and the different second set of data in the second buffer.

### Claim 17 (depends on 16)

The method of claim 16 further comprising transmitting the same first set of data in the first buffer and a third second set of data in the second buffer to the absolute difference calculation circuits and incrementing the value in a third selected accumulator by the absolute differences between the first set of data in the first buffer and the third second set of data in the second buffer.

### Claim 18 (depends on 17)

The method of claim 17 wherein when the first set of data and the second of data are transmitted to the absolute difference calculation circuits, the resultingly calculated absolute differences are summed by the multiple input adder and the sum output to one input of the full adder, the control circuit signals a demultiplexer to allow a value held in the first selected accumulator to be transmitted to another input of the full adder where the value is added to the sum at the first input of the full adder, and the control circuit signals a multiplexer to allow the output of the full adder to be stored in the first selected accumulator.

### Claim 19 (depends on 18)

The method of claim 18 wherein each byte of data in the reference block is loaded from memory into the first buffer only one time during the calculations of the absolute differences between the reference block and the plurality of search locations.
