Pulse or digital communications – Bandwidth reduction or expansion
Reexamination Certificate
1998-02-09
2001-12-18
Kelley, Chris (Department: 2713)
Pulse or digital communications
Bandwidth reduction or expansion
C375S240160
Reexamination Certificate
active
06332001
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to the art of motion-compensated interframe coding applicable to the coding of moving images, and more particularly to a method of detecting similarity of small regions (blocks) in an image between frames.
The present invention is also concerned with an iterative transform coding process which is applicable to the coding of still images or moving images, and more particularly to a method of detecting similarity of small regions (blocks) in an image within a frame or between frames.
2. Description of the Prior Art
Moving image data have heretofore been compressed by the MPEG (Moving Picture Experts Group) interframe coding process which codes a frame by referring to other frames which precede and follow the frame in time, or the H.261 and H.263 coding processes which code a frame by referring to another frame which precedes the frame in time.
These interframe coding processes incorporate motion-compensated interframe coding principles by which a frame is coded while compensating for a motion produced between frames.
At present, different MPEG versions such as MPEG-1(ISO/IEC 11172) and MPEG-2(ISO/IEC 13818) are available in the art. Both MPEG-1 and MPEG-2 use three types of coded pictures including I-picture, P-picture, and B-picture. Specifically, a sequence of frames of a moving image is mixed with frames that have been coded with an either one of these types of coded pictures.
An I-picture is a picture frame that is intra-coded (intraframe-coded) independently of other frames. Macroblocks (a predetermined number of blocks of pixels) in the frame are all intra-coded. I-pictures which are periodically included in a sequence of frames of a moving image can be used as points for random access or error recovery.
A P-picture is a picture frame which is interframe predictive-coded from another frame that precedes the frame in time. The picture frame is predictive-coded only in a forward direction based on an I-picture or a P-picture positioned in the past.
A B-picture is a picture frame which is interframe predictive-coded from other two frames that precede and follow the picture frame in time. The picture frame is predictive-coded in a forward direction or a backward direction or both directions based on I-pictures or P-pictures that precede and follow the picture frame in time. The predictive direction is determined in terms of macroblocks.
ITU-T Recommendation H.261 and H.263 coding processes are the video coding standards for teleconferencing applications. The H.261 and H.263 coding processes do not compress a picture frame according to predictive-coding based on a frame that follows the picture frame in time, but compress a picture frame according to interframe predictive-coding based on a frame that precedes the picture frame in time. Specifically, the H.261 and H.263 coding processes use two types of coded pictures, i.e., I-picture and P-picture, and mix frames coded with either of these picture types with a sequence of frames of a moving image.
According to the above motion-compensated interframe coding principles, it is necessary to detect a motion vector in a moving image. One of processes for detecting such a motion vector is a block matching process.
The block matching process divides an image frame into rectangular regions (rectangular blocks) each comprising a matrix of 8×8 pixels or 16×16 pixels, and detects a motion per block between frames.
More specifically, the block matching process determines a motion vector by evaluating similarity between a block (input block) in a frame which it to be coded and blocks that are shifted a predetermined distance within a given search range about a block within a preceding frame (reference image frame) which is in the same position as the input block, and identifying a block (similar block) which has the highest similarity to the input block. For example, if a horizontal search range is ±15 pixels for each frame, then when a P-picture frame to be coded is 4 frames apart from a reference image frame, a search range of ±60 pixels is searched.
Therefore, a motion vector can be determined when similarity (predicted error) is calculated between blocks in an image frame to be coded and a reference image frame. As well known in the art, an accumulative sum of absolute errors AE or square errors SE is used as an evaluating function to determine similarity. An accumulative sum of absolute errors AE and an accumulative sum of square errors SE are expressed by the following equations:
AE
=
∑
i
N
&LeftBracketingBar;
x
i
-
X
i
&RightBracketingBar;
SE
=
∑
i
N
(
x
i
-
X
i
)
2
where x
i
: a pixel value in an input block or a range block;
X
i
: a pixel value in a search block or a domain block;
and
N: the number of pixels in a block.
The coding of an image according to a conventional block matching process which uses square errors SE will be described below with reference to
FIG. 1
of the accompanying drawings.
As shown in
FIG. 1
, a variable MIN which holds a minimum square error SE (block similarity is higher as the square error SE is smaller) is initialized in a step S
60
, and thereafter a first input block is read from an image frame to be coded in a step S
61
. Then, a first search block is read from a search range in a reference image frame in a step S
62
.
A square error SE between the input block and the search block is calculated in a step S
63
, and the calculated square error SE is compared with the variable MIN in a step S
64
. If the square error SE is smaller than the variable MIN, then the calculated square error SE is held as the variable MIN, and the position of the search block in the frame is held in a step S
65
.
The steps S
62
-S
65
are repeated until it is decided that all search blocks in the search range are processed in a step S
66
. A square error SE smaller than the variable MIN held in the preceding processing cycle is determined and held, and the position of the search block the frame is held in the step S
65
. In this manner, the position of the search block whose similarity is highest in the search range (with the minimum square error SE) is identified.
A motion vector between the input block and the identified block whose similarity is highest is coded in a step S
67
.
The steps S
61
-S
67
are repeated until it is decided that all input blocks in the frame to be coded are processed in a step S
68
, thereby coding motion vectors between the input blocks and the search block.
As a result, a search block whose similarity to each of all the input blocks in the frame to be coded is high is identified as a similar block, and a motion vector between the input block and the similar block is coded.
Another known block matching process is an iterative coding process (fractal coding process) which divides a still image or a moving image into a plurality of blocks, searches a search range established in the image for a block (domain block) similar to a block (range block) to be coded, and codes an affine transformation parameter between the range block and the domain block.
The iterative coding process models an image using its self-correlation and codes an affine transformation parameter representative of a feature of the image, as disclosed in “Fractal Image Compression” written by A. E. Barnsley and L. P. Hurd, Numerical Science series—4, published by Toppan, “Image compression by iterative coding” written by Ida and Datake, Communication society, Spring National Conference, D-341, 1991, “A novel fractal block-coding technique for digital images” written by A. E. Jacquin, ICASSP 90 Proceeding, M8. 2, 1992, and U.S. Pat. No. 5,065,447.
The coding of an image according to a conventional iterative coding process which uses square errors SE will be described below with reference to
FIG. 2
of the accompanying drawings.
As shown in
FIG. 2
, a variable MIN which holds a minimum square error SE is initialized in a step S
70
, and thereafter a first
Arayashiki Akifumi
Hirata Shin-Ichi
Oyamada Ouichi
Kelley Chris
Kokusai Electric Co. Ltd.
Wenderoth , Lind & Ponack, L.L.P.
Wong Allen
LandOfFree
Method of coding image data does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method of coding image data, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method of coding image data will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2584399