Image analysis – Image compression or coding – Quantization
Reexamination Certificate
2000-12-08
2004-03-30
Wu, Jingge (Department: 2623)
Image analysis
Image compression or coding
Quantization
C382S250000
Reexamination Certificate
active
06714687
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to an image encoding/decoding method, an apparatus thereof, and a recording medium in which a program therefor is recorded, and more particularly, relates to an image encoding/decoding method, an apparatus thereof, and a recording medium in which a program therefor is recorded, according to Hybrid Vector Quantization (HVQ) system.
2. Description of Related Art
According to JPEG (Joint Photographic Expert Group) system, 8 times 8 pixel blocks are converted to DC (direct current) value and each coefficient value of from base to 63 times frequency by two dimensional DCT (discrete cosine transform), and information amount is reduced by quantizing the coefficient value in a different quantization width within no reduction of image quality utilizing frequency components of natural images which are gathered in a low frequency range, and then Huffman encoding is carried out.
According to HVQ system, which is a kind of mean value separation type block encoding same as JPEG, adaptive orthogonal transform (AOT) which is an intermediate system between a vector quantization and orthogonal transform encoding is used as a compression principle. AOT is a system in which the minimum number of non-orthogonal basis is selected from nests of the basis corresponding to a code book of vector quantization and the objective blocks become close to the desired and allowable error “Z”. According to the HVQ system, decoding is quickly carried because a decoding operation can be done in the form of integer. Natural images and artificial images (animation images, CG images) can be compressed in high image quality, because there are not mosquito and block noise, which are particularly generated in JPEG, and false contour, which is particularly generated in GIF. The invention relates to a method for further improving the image quality and for carrying out the coding operation at a higher speed in the HVQ system.
The applicants of the invention have proposed an image encoding/decoding method in accordance with the HVQ system utilizing self-similarity of images in Japanese Patent Application No. 189239/98. The contents of such proposal will be explained as follows. In the disclosure, a sign <a> means vector “a” or block “a”, a sign ∥a∥ means norm of the vector “a”, and a sign <a·b> means inner product of vectors a and b. Further, vectors and blocks in drawings and [numbers] are represented by block letters.
FIG. 1
is a block diagram showing a conventional image encoder. In
FIG. 1
,
11
is an original image memory for storing an original image data,
12
is a DC value production unit for seeking a block average (DC) value per each pixel block (4 times 4 pixel) of the original image data,
13
is a differential PCM encoding unit (DPCM) for carrying out a differential predict encoding per each DC value,
14
is inverse DPCM encoding unit for decoding each DC value from the differential PCM encoding,
15
is a DC image memory for storing a decoded DC image,
16
is a DC nest production unit for cutting off the DC nest of a desired size from a part of the DC image, and
17
is a DC nest memory for storing the DC nest.
Further,
18
is a subtractor for separating a corresponding decoding DC value “DC
J
” from a target image block <R
J
> to be encoded,
19
is a differential vector buffer for storing a differential vector <d
J
> which is DC separated,
20
is an extracted block buffer for storing a base extraction block <U
i
> of 4 times 4 pixels which is down-sampled from the DC nest,
21
is an equilibrator for seeking a block mean value a
i
of the base extraction block <U
i
>,
22
is a subtractor for separating the block means value a
i
from the base extraction block <U
i
>,
23
is an extracted vector buffer for storing the base extraction block <U
i
> which is separated by the mean value,
24
is an adaptive orthogonal transform (AOT) processing unit for producing an orthogonal basis &agr;
k
<u
k
′> (k=1~m) to search the DC nest to make the differential vector <d
j
> closer to the allowable error Z, where a square norm ∥d
j
∥
2
of the differential vector is over the allowable error Z,
25
is a coefficient transform unit for seeking an expanding square coefficient &bgr;
k
which is multiplied by a non-orthogonal basis vector <u
k
> (k=1~m) per the produced orthogonal basis &agr;
k
<u
k
′> (k=1~m) to produce an equivalent non-orthogonal basis &bgr;
k
<u
k
> (k=1~m, and
26
is an encoding unit by Huffman coding, run length coding or fixed length coding system for the compression encoding of information such as DPCM encoding of the DC value or the non-orthogonal basis &bgr;
k
<u
k
>.
In the DC value production unit
12
, the block mean value of 4 times 4 pixels is provided in which the first decimal place is rounded off or down. In the DPCM
13
, where the DC value of row J and column T is shown by the DC
J, I
, a predictive value DC
J, I
′ of the DC
J,I
is provided by the formula, DC
J, I
′=(DC
J, I−1
+DC
J−1, I
)/2, and its predictive error (&Dgr; DC
J, I
=DC
J, I
−DC
J, I
′) is linear-quantized by a quantization coefficient Q(Z) and is output. The quantization coefficient Q(Z) corresponds to the allowable error Z and is variable within the range of 1 to 8 according to the allowable error Z.
In the DC nest production unit
16
, the DC nest is prepared by copying the range of vertical
39
×horizontal
71
from the DC image. It is preferred that the DC nest includes more alternating current components because it is used as a codebook. Therefore, it is prepared by copying such the range that the sum of absolute values of difference between the DC values adjacent to each other in a plurality of the extracted ranges become maximum.
In making down-samples of the base extraction block <U
i
>, a vertex per one DC value in vertical and horizontal section is set to (p
x
, p
y
) &egr; [0, 63]×[0, 31] and a distance of its sub-samples is set to 4 kinds of (s
x
, s
y
) &egr; {(1, 1), (1, 2), (2, 1), (2, 2) }. Accordingly, the total numbers of the base extraction blocks <U
i
> are N (=8192) and are referred by an index counter “i” from the AOT
24
. Behavior of conventional adaptive orthogonal transform processing unit
24
will be explained below.
FIG. 2
is a flow chart of conventional adaptive orthogonal transform processing and
FIG. 3
is an image drawing of the processing. In
FIG. 2
, it is input in the processing that the square norm ∥d
j
∥
2
of the differential vector is more than Z. In step S
121
, the square norm ∥d
j
∥
2
of the differential vector is set in a resister E. A basis number counter is initialized to k=1. In step S
122
, much value ( e.g. 100,000) is set in a minimum value holding resister E′. In step S
123
, an index counter of the base extraction block <U
i
> is initialized to i=0. By these steps, the initial address and distance of sub-samples in the DC nest are set to (p
x
, p
y
)=(0, 0) and (s
x
, s
y
)=(1, 1), respectively.
In step S
124
, the base extraction vector <u
i
> is produced by separating the block mean value a
i
from the base extraction blocks <U
i
>. Since the operation or calculation is carried out under the accuracy of integer level, any value of first decimal place in the block mean value a
i
is rounded off or down. In step S
125
, the base extraction vector <u
i
> is subjected to orthogonal transform processing to be converted to the orthogonal basis vector <u
k
′>, if necessary (k>1).
FIG. 3
(A) and (B) are image drawings of the orthogonal transform processing. In
FIG. 3
(A), the first base extraction vector <u
1
> can be the first basis vector <u
1
′> as it is.
Then, the second base extraction vector <u
2
>
Itagaki Fumihiko
Kawashima Miyuki
Antonelli Terry Stout & Kraus LLP
Hudson Soft Co. Ltd.
Wu Jingge
LandOfFree
Image encoding/decoding method, apparatus thereof and... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Image encoding/decoding method, apparatus thereof and..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Image encoding/decoding method, apparatus thereof and... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3209567