High-Performance Block-Matching VLSI Architecture With Low Memory Bandwidth For Power-Efficient Multimedia Devices

• US 20100091862A1
• Filed: 12/28/2008
• Published: 04/15/2010
• Est. Priority Date: 10/14/2008
• Status: Active Grant

• Current Assignee: National Taiwan University (Government of The Republic of China)
• Original Assignee: National Taiwan University (Government of The Republic of China)
• Inventors: Kuo, Sy-Yen, Huang, Shih-Chia
• Granted Patent: US 8,787,461 B2
• Time in Patent Office: Days
• US Class Current: 375/240.16
• CPC Class Codes: H04N 19/43 Hardware specially adapted for motion estimation or compensation
• CPC Class Codes: H04N 19/51 Motion estimation or motion compensation
• CPC Class Codes: H04N 19/513 Processing of motion vectors
• CPC Class Codes: H04N 19/523 with sub-pixel accuracy
• CPC Class Codes: H04N 19/533 Motion estimation using multistep search, e.g. 2D-log search or one-at-a-time search [OTS]
• CPC Class Codes: H04N 19/56 Motion estimation with initialisation of the vector search, e.g. estimating a good candidate to initiate a search
• CPC Class Codes: H04N 19/57 Motion estimation characterised by a search window with variable size or shape
• CPC Class Codes: H04N 19/573 Motion compensation with multiple frame prediction using two or more reference frames in a given prediction direction

Abstract

A high-performance block-matching VLSI architecture with low memory bandwidth for power-efficient multimedia devices is disclosed. The architecture uses several current blocks with the same spatial address in different current frames to search the best matched blocks in the search window of the reference frame based on the best matching algorithm (BMA) to implement the process of motion estimation in video coding. The scheme of the architecture using several current blocks for one search window greatly increases data reuse, accelerates the process of motion estimation, and reduces the data bandwidth and the power consumption.

Claims

1. A high-performance block-matching VLSI architecture, for executing a motion estimation of an coding operation with low memory bandwidth, for a power-efficient multimedia device, the high-performance block-matching VLSI architecture comprising:

an external memory, for saving data of a search window of a reference frame;

a motion estimation processor, for finding out a plurality of corresponding best matched blocks and a plurality of corresponding motion vectors having a current block address of a current block from the search window according to a best matching algorithm (BMA); and

a data bus, coupled to the external memory and the motion estimation processor for transmitting data,

wherein the motion estimation processor comprises an internal memory, a memory processing block, an address selection processing block, a predicting search path processing block, a BMA processing block, and a motion estimation result processing block, wherein

the memory processing block controls a data access operation between the internal memory and the external memory;

the address selection processing block selects a current block address in a current frame;

the predicting search path processing block executes a prediction of a search path regarding the current block according to the current block address selected by the address selection processing block, so as to predict the search path corresponding to the current block in the search window;

the BMA processing block loads corresponding data of the search window from the external memory to the internal memory, and finds out the best matched blocks and the motion vectors by the BMA, according to the search path predicted by the predicting search path processing block; and

the motion estimation result processing block recording the motion vectors of the current block and the best matched block.

2. The high-performance block-matching VLSI architecture according to claim 1, wherein the BMA determines a minimum value of a sum of absolute differences (SAD) as the best matched block, the SAD being defined by the equation of

$S$



A 



D 

( i , j ) = ∑

m = 0 15 

∑

n = 0 15 



X 

( m , n ) - Y 

( m + i , n + j ) 

wherein X(m, n) represents an image data of the current block at coordinates (m,n), Y(m+i, n+j) represents the image data of the reference block at coordinates (m+i, n+j), wherein i is a horizontal coordinate, and j is a vertical coordinate, and i and j are integers.

3. The high-performance block-matching VLSI architecture according to claim 1, wherein each of the motion vectors is a vector directed from the address of the current block to the address of the corresponding best matched block.

4. A high-performance block-matching method for a VLSI architecture, for executing a motion estimation of an coding operation with low memory bandwidth, for a power-efficient multimedia device, the high-performance block-matching method comprising:

step A;

starting the motion estimation, wherein data of a search window of a reference frame and data of a plurality of current blocks are saved in an external memory, then entering step B;

step B;

selecting an address of the current blocks, then entering step C;

step C;

loading the data of one current block corresponding to the address of the current block to an internal memory, then entering step D;

step D;

finding out a predicted search path, then entering step E;

step E;

loading data designated by the predicted search path in the search window from the external memory to the internal memory, then entering step F;

step F;

executing a best matching algorithm (BMA) matching operation according to a BMA to find out a best matched block, then entering step G;

step G;

determining whether the BMA matching operation has been executed to all of the current blocks having the same address, and if no, then entering step H, or otherwise if yes then entering step I;

step H;

loading another current bock having the address, and returning back to step F;

step I;

completing the motion estimation of the current blocks having the address, according to the BMA matching operation result of the same address, then entering step J;

step J;

determining whether BMA matching operations of current blocks of all current block addresses have been completed, if no then entering step K, or otherwise if yes then entering step L;

step K;

selecting another current block address, and returning back to step C;

step L;

generating a motion estimation result, then entering step M; and

step M;

completing the motion estimation.

5. The high-performance block-matching method according to claim 4, wherein the BMA determines a minimum value of a sum of absolute differences (SAD) as the best matched block, the SAD being defined by the equation of

$S$



A 



D 

( i , j ) = ∑

m = 0 15 

∑

n = 0 15 



X 

( m , n ) - Y 

( m + i , n + j ) 

wherein X(m, n) represents an image data of the current block at coordinates (m,n), Y(m+i, n+j) represents the image data of the reference block at coordinates (m+i, n+j), wherein i is a horizontal coordinate, and j is a vertical coordinate, and i and j are integers.

6. The high-performance block-matching method according to claim 4, wherein each of the motion vectors is a vector directed from the address of the current block to the address of the corresponding best matched block.

7. The high-performance block-matching method according to claim 4, wherein step F further comprises:

obtaining motion vectors, adaptive search ranges, and search paths of a plurality of adjacent blocks of the current block;

predicting to obtain a predicted motion vector and a predicted adaptive search range of the current block; and

predicting to obtain a predicted search path of the current block in the search window, according to the predicted motion vector, the predicted adaptive search range, and a current search pattern of the current block and the search path of the adjacent blocks.

8. The high-performance block-matching method according to claim 7, wherein the predicted adaptive search range is a maximum one of the adaptive search ranges of the adjacent blocks, or an average of the adaptive search ranges of the adjacent blocks.

9. The high-performance block-matching method according to claim 7, wherein the adjacent blocks are blocks adjacently positioned at a left side, an upper left side, and an upper side of the current block

10. The high-performance block-matching method according to claim 7, wherein the predicted motion vector of the current block is positioned on a motion vector plane defined by the motion vectors of the adjacent blocks, and is determined by executing an extrapolation calculation.

11. The high-performance block-matching method according to claim 4, wherein the predicted motion vector is an average of the motion vectors of the adjacent blocks.