Pulse or digital communications – Bandwidth reduction or expansion – Television or motion video signal
Reexamination Certificate
1998-07-16
2001-12-11
Diep, Nhon T (Department: 2613)
Pulse or digital communications
Bandwidth reduction or expansion
Television or motion video signal
Reexamination Certificate
active
06330282
ABSTRACT:
BACKGROUND OF THE INVENTION
The present invention relates to an art of compressing and encoding digital video, and more particularly to a block matching arithmetic device for use in motion vector search.
The video compression coding technique is a technique of greatly compressing an enormous amount of information using high temporal correlation of video signals, spacial correlation, and human's visual characteristics of video signals. The video compression coding technique can realize very high compression ratio by combining the inter-frame predictive coding technique, conversion coding technique, and variable-length coding technique. Here, the word “frame” means one screen forming video.
The inter-frame predictive coding technique utilizes the correlation of the temporal direction of video and relates to a method of predicting a current frame based on a reference frame and then transmitting a predictive error signal. There are as an improved inter-frame predictive coding technique an inter-motion-compensation-frame predictive coding scheme in which the motion of a time-varying image is considered, inter-field predictive coding scheme in which inter-frame prediction is replaced with inter-field prediction, and an interpolation predictive coding scheme which performs interpolation by a past reference frame and a future reference frame. There is further an adaptive predictive coding scheme which adaptively selects plural predictive coding schemes described above.
The conversion coding technique is a technique of compressing information contents by linearly converting plural signals. The conversion coding technique is commonly applied to a predictive error signal in a space (horizontal, or vertical) direction in the adaptive predictive coding scheme. In this conversion, the redundancy in a space direction appears noticeably in an image signal. Like the adaptive predictive coding scheme, the conversion coding technique includes an adaptive conversion coding scheme that adaptively selects plural conversion schemes such as a frame conversion coding, a field conversion coding, and a conversion coding only in the horizontal direction.
The variable-length coding technique is a technique of compressing information contents using the tilt of a signal level probability distribution and is generally applied to motion vector in the adaptive predictive coding scheme and conversion coefficient in the adaptive conversion coding scheme. ITU-T H.261 or ISO IS1172(MPEG-1) being the international standard scheme for a time-varying compression coding adopts as an interframe predictive coding scheme an inter-motion-compensation-frame predictive coding scheme using motion vectors. In this scheme, the current frame
151
, as shown in
FIG. 15
, is divided into blocks (current blocks)
152
formed of, for example, (N (lines)×M (rows)) pixels (generally, 16×16). The motion vector search areas
154
for searching motion vectors on the reference frame
153
are set to be (2V (lines)×2H (rows)) pixels, where when the center point of a current block is set to, for example, the coordinates (0, 0), the coordinate on the horizontal line ranges from −H to H−1 while the coordinate on the vertical line ranges from −V to V−1. Then, the motion vector is worked out by searching the reference block 155 which provides the smallest difference to the current block within the search range.
For example, when the image is still, the difference becomes zero if the reference block which is at the same position as the current block, that is, has the coordinates (0, 0) is a predictive block. If the reference block which is shifted from the candidate block at the same position by h pixels rightward and v pixels downward has the smallest distortion, the block with the coordinates (v, h) is provided as a predictive block. Thus the motion vector MV(v, h) is transmitted. The difference computation will be described here. When the pixel on the upper left of the current block
152
is represented as a(0, 0) and the pixel on the reference frame corresponding to the coordinates a(0, 0) of the current block is represented as b(0, 0), the pixel on the upper left of the reference block
155
where the motion vector becomes MV(h, v) is represented as b(h, v). In this case, the distortion D(h, v) of the current block
152
and the reference block
155
is represented by the following formula (1):
D(h,v)=&Sgr;&Sgr;∥b(h+m,v+n)−a(m,n)∥ (1)
where ∥ is the norm for computing a distortion. An absolute difference or square error is generally performed. However, an absolute difference operation is frequently used in terms of the complexity and efficiency of computation.
As described above, the method of comparing a current frame and a reference frame in block units is called a block matching method. Where a motion vector is searched in pixel units, (2V×2H) reference blocks per current block exits in the motion vector search area
154
. When all current blocks in a current frame are searched for a motion vector, an enormous amount of operation is required for the block matching arithmetic operation. Conventionally, the device, for example, disclosed by JP-A-No. 340538/1996 is known as a high-speed, high performance motion vector search device. This device is a device used for only the motion vector search operation and includes plural processor elements to search a motion vector by implementing block matching operations in parallel for plural candidate blocks. However, such a device requires a great number of processor elements, thus resulting in a bulky, expensive device.
Recently, high-speed, high end microprocessors with 64-bit architecture have come to the market with the advance of semiconductor technology. As such a microprocessor can be listed UltraSparc I and II by Sun Microsystems, Alpha 21164 by DEC, R10000 by MIPS, PA-80000 by Hewlett-Packard, Power PC620 by Motrola, and so on. In some cases, a 64-bit arithmetic unit such as an ALU built in a microprocessor can be divided into eight 8-bit units, four 16-bit units, and two 32-bit units to process plural data in parallel by a single instruction. The SIMD (Single Instruction Stream, Multiple Data Stream) instruction improves the data operation capability according to data size by eight times, four times, or twice. In some microprocessors, an instruction for executing a data arithmetic operation peculiar to the process algorithm is added to speed a multimedia process such as graphic process or image coding process.
Some UltraSparc processors by Sun Microsystems use an instruction set specially designed for a multimedia process called VIS (Visual Instruction Set) (IEEE Micro, Vol. 16, No. 4, pp 10-20, August, 1996). The instruction set contains an pdist instruction used for motion vector search according to the block matching method. As shown in
FIG. 16
, the 64-bit register r
1
stores eight 8-bit data a
0
to a
7
while the 64-bit register r
2
stores eight 8-bit data bo to b
7
. The pdist instruction accumulates the sum of absolute values of references between eight 8-bit data of the register r
1
and 8 pieces of 8-bit data of the register r
2
at the corresponding positions with data of the register r
3
. Since the image data is formed of 8 bits, an block matching arithmetic operation for eight pixels can be implemented by the pdist instruction of one cycle. Where the block size of the block matching operation is 16×16, the error of a single motion vector candidate can be computed by executing the pidist instruction 32 times.
However, when the microprocessor reads or writes word data output from/to the data memory, data can be read or written by only the addresses aligned with the byte number of one word. For example, when one word is formed of 64 bits, word data can be read or written based on only the lower three bits formed of 000 among addresses grouped every 8 bits, that is, 0000h, 0008h, 0010h, 0018h, . . .
FIG. 17
illustrates a conventional block matching arithmetic device tha
Diep Nhon T
McGuireWoods LLP
NEC Corporation
LandOfFree
Block matching arithmetic device and recording medium... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Block matching arithmetic device and recording medium..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Block matching arithmetic device and recording medium... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2576867