Image analysis – Image compression or coding – Predictive coding
Reexamination Certificate
2001-11-19
2004-08-03
Do, Anh Hong (Department: 2624)
Image analysis
Image compression or coding
Predictive coding
C382S236000, C382S241000
Reexamination Certificate
active
06771826
ABSTRACT:
FIELD OF THE ENGINEERING
The present invention relates to methods of encoding and decoding a digital picture data for storing or transmitting thereof, more specifically, a method of encoding and decoding the motion information producing predicted pictures, and a method of producing an accurate predicted picture, and an apparatus using the same methods.
BACKGROUND ART
Data compression (=encoding) is required for efficient storing and transmitting of a digital picture.
Several methods of encoding are available as prior arts such as “discrete cosine transform” (DCT) including JPEG and MPEG, and other wave-form encoding methods such as “subband”, “wavelet”, “fractal” and the like. Further, in order to remove redundant signals between pictures, a prediction method between pictures is employed, and then the differential signal is encoded by wave-form encoding method.
A method of MPEG based on DCT using motion compensation is described here. First, resolve an input picture into macro blocks of 16×16 pixels. One macro block is further resolved into blocks of 8×8, and the blocks of 8×8 undergo DCT and then are quantized. This process is called “Intra-frame coding.” Motion detection means including a block matching method detects a prediction macro block having the least errors on a target macro block from a frame which is time sequentially adjoined. Based on the detected motion, an optimal predicted block is obtained by performing motion compensation of the previous pictures. A signal indicating a predicted macro block having the least errors is a motion vector. Next, a difference between the target block and its corresponding predicted block is found, then the difference undergoes DCT, and the obtained DCT coefficients are quantized, which is transmitted or stored together with motion information. This process is called “Inter-frame coding.”
At the data receiving side, first, the quantized DCT coefficients are decoded into the original differential signals, next, a predicted block is restored based on the motion vector, then, the differential signal is added to the predicted block, and finally, the picture is reproduced.
A predicted picture is formed in a block by block basis; however, an entire picture sometimes moves by panning or zooming, in this case, the entire picture undergoes motion compensation. The motion compensation or a predicted picture formation involves not only a simple parallel translation but also other deformations such as enlargement, reduction and rotation.
The following equations (1)-(4) express movement and deformation, where (x, y) represents a coordinates of a pixel, and (u, v) represents a transformed coordinates which also expresses a motion vector at (x, y). Other variables are the transformation parameters which indicate a movement or a deformation.
(
u, v
)=(
x+e, y+f
) (1)
(
u, v
)=(
ax+e, dy+f
) (2)
(
u, v
)=(
ax+by+e, cx+dy+f
) (3)
(
u, v
)=(
gx
2
+pxy+ry
2
+ax+by+e, hx
2
+qxy+sy
2
+cx+dy+f
) (4)
Equation (3) is so called the Affine transform, and this Affine transform is described here as an example. The parameters of the Affine transform are found through the following steps:
First, resolve a picture into a plurality of blocks, e.g., 2×2, 4×4, 8×8, etc., then find a motion vector of each block through block matching method. Next, select at least three most reliable motion vectors from the detected motion vectors. Substitute these three vectors to equation (3) and solve the six simultaneous equations to find the Affine parameters. In general, errors decrease at the greater number of selected motion vectors, and the Affine parameters are found by the least squares method. The Affine parameters thus obtained are utilized to form a predicted picture. The Affine parameters shall be transmitted to the data receiving side for producing the identical predicted picture.
However, when a conventional inter-frame coding is used, a target picture and a reference picture should be of the same size, and the conventional inter-frame coding method is not well prepared for dealing with pictures of different sizes.
Size variations of adjoining two pictures largely depend on motions of an object in these pictures. For instance, when a person standing with his arms down (
FIG. 7A
) raises the arms, the size of the rectangle enclosing the person changes (
FIG. 7B.
) When an encoding efficiency is considered, the target picture and reference picture should be transformed into the same coordinates space in order to decrease a coded quantity of the motion vectors. Also, the arrangement of macro blocks resolved from a picture varies depending on the picture size variation. For instance, when the image changes from
FIG. 7A
to
FIG. 7B
, a macro block
701
is resolved into macro blocks
703
and
704
, which are subsequently compressed. Due to this compression, a vertical distortion resulting from the quantization appears on the person's face in the reproduced picture (FIG.
7
B), whereby a visual picture quality is degraded.
Because the Affine transform requires high accuracy, the Affine parameters (a, b, c, d, e, f, etc.) are, in general, real numbers having numbers of decimal places. A considerable amount of bits are needed to transmit parameters at high accuracy. In a conventional way, the Affine parameters are quantized, and transmitted as fixed length codes or variable length codes, which lowers the accuracy of the parameters and thus the highly accurate Affine transform cannot be realized. As a result, a desirable predicted picture cannot be produced.
As the equations (1)-(4) express, the number of transformation parameters ranges from 2 to 10 or more. When a transformation parameter is transmitted with a prepared number of bits enough for maximum numbers of parameters, a problem occurs, i.e., redundant bits are to be transmitted.
DISCLOSURE OF THE INVENTION
The present invention aims to, firstly, provide an encoder and a decoder of a digital picture data for transmitting non-integer transformation parameters of long number of digits, such as the Affine transform, at high accuracy for less amount of coded data. In order to achieve the above objective, a predicted picture encoder comprising the following elements is prepared:
(a) picture compression means for encoding an input picture and compressing the data,
(b) coordinates transform means for outputting a coordinates data which is obtained by decoding the compressed data and transforming the decoded data into a coordinates system,
(c) transformation parameter producing means for producing transformation parameters from the coordinates data,
(d) predicted picture producing means for producing a predicted picture from the input picture by the transformation parameters, and
(e) transmission means for transmitting the compressed picture and the coordinates data.
Also a digital picture decoder comprising the following elements is prepared:
(f) variable length decoding means for decoding an input compressed picture data and an input coordinates data,
(g) transformation parameter producing means for producing transformation parameters from the decoded coordinates data,
(h) predicted picture producing means for producing a predicted picture data using the transformation parameters,
(i) addition means for producing a decoded picture by adding the predicted picture and the compressed picture data.
To be more specific, the transformation parameter producing means of the above digital encoder and decoder produces the transformation parameters using “N” (a natural number) pieces of pixels coordinates-points and the corresponding “N” pieces of transformed coordinates-point obtained by applying a predetermined linear polynomial function to the N pieces of pixels coordinates-points. Further, the transformation parameter producing means of the above digital encoder and decoder outputs transformation parameters produced t
Do Anh Hong
Matsushita Electric - Industrial Co., Ltd.
RatnerPrestia
LandOfFree
Digital image encoding and decoding method and digital image... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Digital image encoding and decoding method and digital image..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Digital image encoding and decoding method and digital image... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3349364