Image analysis – Image compression or coding – Interframe coding
Reexamination Certificate
1998-03-05
2001-06-19
Chang, Jon (Department: 2623)
Image analysis
Image compression or coding
Interframe coding
C382S107000, C348S699000, C348S407100
Reexamination Certificate
active
06249612
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates to a image coding device based on, for example, MPEG (Moving Picture Image Coding Experts), and more particularly relates to a detection technique of motion vectors.
2. Description of Related Art
MPEG system was established by ISO/IEC JTC1/SC29 which is the abbreviation of International Organization for Standardization/International Electrotechnical Commission, Joint Technical Committee 1/Sub Committee 29 and an organization for discussing dynamic image coding.
MPEG system is a coding system for compressing an image data using combination of DCT (Discrete Cosine Transform), motion compensative prediction, and variable word length coding.
The structure of an image coding device based on MPEG system is shown in FIG.
1
. In this drawing, the image data is supplied to the input terminal T
1
. The image data is inputted to a motion vector detection circuit
21
and subtraction circuit
22
. The motion vector detection circuit
21
calculates a motion vector from the current frame and reference frame (for example, precedent frame) using the input image data, and supplies it to a motion compensation circuit
23
.
The image data of the reference frame is stored also in a frame memory
24
. The image data is supplies to the motion compensation circuit
23
. The motion compensation circuit
23
performs motion compensation of the image data transmitted from the frame memory
24
using the motion vector supplied from the motion vector detection circuit
21
. The output from the motion compensation circuit
23
is transmitted to the subtraction circuit
22
and addition circuit
25
.
The subtraction circuit
22
determines the prediction error data by calculating the difference between the image data of the current frame supplied from the input terminal T
1
and the motion-compensated image data of the reference frame supplied from the motion compensation circuit
23
, and supplies it to a DCT circuit
26
. The DCT circuit
26
performs DCT processing on the error prediction data and transmits it to a quantizer
27
. The quantizer
27
quantizes the output from the DCT circuit
26
, and transmits it to a variable work length coding circuit (not shown in the drawing).
The output from the quantizer
27
is supplied also to a reverse quantizer
29
. The output is subjected to reverse quantizing processing, and the output is subjected to reverse DCT processing in a reverse DCT circuit
30
and is returned to the original prediction error data, and supplied to the addition circuit
25
.
The addition circuit
25
adds the prediction error data to the output data from the motion compensation circuit
23
to calculate both data of the current frame. The calculated image data is stored in the frame memory
24
as an image data of the next reference frame.
The block matching method has been known as a method for detecting a motion vector in such a image coding device. In the block matching method, a picture is divided into a small rectangular regions (blocks), and motion is detected block by block. The block size is a size of horizontal 8 pixels×vertical 8 pixels (abbreviated as 8×8 hereinafter) or a size of 16×16. Next, the block matching method is described with reference to FIG.
2
.
In
FIG. 2
, a reference block RB of M×N is set in the reference frame
41
. A search block SB having the same size as the reference block RB is set in a search frame
42
. The search block SB is moved in a prescribed search range
43
of a size ±m×±n around the SB
0
located at the same position as that of the reference block RB in the search frame
42
. The match between the reference block RB and search block SB is calculated, the search block having the highest match is assigned as a matching block, and the motion vector is calculated from the matching block.
In detail, in the case that the match of a search block SBk located at the position shifted (u, v) from a search block SBo located at the same position as the reference block RB is highest, the motion vector of the reference RB is referred to (u, v). When, the search block which leads to the minimum of the total of the absolute value difference of respective pixels at the same position of the reference block RB and search block SB or the total of the difference square of respective pixels is assigned as the search block of the highest match.
In MPEG system, one sequence of a dynamic image is divided into GOP (Group of Picture) composed of a plurality of frames (picture) for coding. A GOP is composed of an in-frame coding image (I picture), inter-frame coding image (P picture) predicted from the precedent frame already coded, and inter-frame coding image (B picture) predicted from two precedent and subsequent frames already coded.
For example, in
FIG. 3
, first the I
0
, which is an I picture, is in-frame coded, and then the motion is detected using a P picture of the P
3
as a reference frame and the I
0
as a search frame. Next, the motion is detected in both direction using B picture of B
1
as a reference frame and I
0
and P
3
as search frames. Next, the motion is detected in both direction using B picture of B
2
as a reference frame and I
0
and P
3
as search frames.
As shown in
FIG. 4
, generally the search range required for motion detection is desirably increased in proportion to the frame interval between a reference frame and search frame. Herein, an example involving a reference frame containing a reference block having the block size of 16×16 is described. For example, in the case that the search range ranges ±16 in horizontal and vertical directions for a frame interval of 1 frame, the search range desirably ranges ±32 for a frame interval of 2 frames and ±48 for a frame interval of 3 frames.
However, if the search range is widened in proportion to the frame interval, the quantity of hardware required for motion detection increases to 4 times and 9 times that for the frame interval of 1 frame. In other words, a lot of hardware is required to perform motion detection for the frame interval of 3 frames as in the case of motion detection using P
3
as a reference frame and I
0
as a search frame.
The telescopic search has been known as a method for enlarging the search range without increment of hardware. The telescopic search can cover the wide search range by providing offset at the center of the search range for respective reference blocks maintaining the research range always within ±16. The telescopic research is described with reference to
FIG. 5
herein under.
As shown in
FIG. 5
, for example, in the case that search is performed on the search frame positioned
3
frame apart from the reference frame, at first, a motion vector MV
1
at the reference block with the search range of ±16 on the search frame
1
positioned
1
frame apart is obtained. Next, search is performed within the search range of ±16 with the center on the search range of MV
1
on the search frame
2
positioned 2 frames apart in order to obtain a motion vector MV
2
. When, the search range of the view from the reference block in the reference frame is ±32. Finally, on the search frame
3
positioned 3 frames apart, search is performed within the search range of ±16 with the center on the search range of MV
2
in order to obtain a motion vector MV
3
. As described herein above, finally the motion vector positioned 3 frames apart is obtained for the search range of ±48. If pipe line processing is performed, hardware quantity of only 3 times that for covering the search range of ±16 is required.
Comparison of transfer rate of search data between the fixed search range and telescopic search is shown in FIG.
6
.
In the case of the fixed search range, reference blocks adjacent in the horizontal direction, for example, RB
0
and RB
1
overlap on 32×48 as shown in
FIG. 6A
, and only data of 16×48 where the search ranges do not overlap may be transferred additiona
Chang Jon
Frommer William S.
Frommer Lawrence & Haug LLP.
Johnson Timothy M.
Shallenburger Joe H.
LandOfFree
Device and method for image coding does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Device and method for image coding, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Device and method for image coding will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2460923