Image analysis – Image compression or coding – Adaptive coding
Reexamination Certificate
1999-10-05
2004-02-24
Do, Anh Hong (Department: 2624)
Image analysis
Image compression or coding
Adaptive coding
C382S251000, C382S253000
Reexamination Certificate
active
06697529
ABSTRACT:
The disclosure of the following priority application is herein incorporated by reference:
Japanese Patent Application No. 10-284531 filed Oct. 6, 1998
The disclosure of U.S. Pat. No. 5,594,554 is herein incorporated by reference.
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to a data compression method and a recording medium with a data compression program for executing the data compression method recorded therein. More specifically, the present invention relates to technology through which conditions for quantization that are required to obtain a desired code volume are determined with a high degree of accuracy through a single trial.
2. Description of the Related Art
Processing such as image compression (e.g., JPEG compression) is performed on image data as a standard procedure in an electronic camera or a computer to record image data in a recording medium with a high degree of efficiency. Such image compression processing may be executed through the procedure described in (1)~(4) below, for instance.
(1) The image data are divided into pixel blocks each constituted of approximately 8×8 pixels. Orthogonal transformation such as DCT (discrete cosine transformation) is performed on these pixel blocks to convert the image data to spatial frequency components.
(2) A standard quantization table that defines quantization increments corresponding to the individual spatial frequency components constituted of 8×8 pixels is prepared. The standard quantization table is multiplied by a scale factor SF to obtain a quantization table that is to be used.
(3) Using the quantization table obtained as described above, the data that have undergone DCT are quantized.
(4) The quantized data are coded through variable-length coding, run-length coding or the like.
However, since the volume of information greatly varies among different sets of image data, it is extremely difficult to uniformly predict the code volume after compression. For this reason, it is necessary to follow the procedure in (1)~(4) described above many times while varying the value of the scale factor SF in order to perform the compression which results in a desired code volume (hereafter referred to as the “target code volume”). As a means for reducing the number of such trials, U.S. Pat. No. 5,594,554, the disclosure of which is herein incorporated by reference, discloses a method whereby a correct scale factor SF is determined based upon the minimum of two trial compressions.
FIG. 18
is a flowchart illustrating this method in the prior art. The following is an explanation of the method in the prior art, given along the flow of the steps in FIG.
18
. First, in the method in the prior art, a first trial compression is performed on input image data. A scale factor SF
1
used at this time and a code volume ACVdata
1
after the compression are stored in memory (
FIG. 18
S
91
).
Next, a second trial compression is performed on the input image data. A scale factor SF
2
used at this time and a code volume ACVdata
2
after the compression are stored in memory (
FIG. 18
S
92
). The results thus obtained are incorporated in a relational expression representing the relationship between the scale factor SF and the code volume ACVdata to obtain;
First Relational Expression:
log
(
ACVdata
1
)=
a*log
(
SF
1
)+
b
(1)
and
Second Relational Expression:
log
(
ACVdata
2
)=
a*log
(
SF
2
)+
b
(2).
By solving expression 1 and expression 2 above, the two undetermined parameters “a” and “b” in the relational expressions are ascertained (
FIG. 18
S
93
). As a result, a relational expression that expresses in approximation the relationship between the scale factor SF and the code volume ACVdata is obtained for the input image data;
Relational Expression:
log
(
ACVdata
)=
a*log
(
SF
)+
b
(3).
By solving this relational expression 3 with a target code volume TCV substituted in it, an appropriate target scale factor NSF for achieving the target code volume TCV is calculated (
FIG. 18
S
94
). Using this target scale factor NSF, the input image data are compressed again (
FIG. 18
S
95
).
In the method in the prior art described above, at least two trial compressions must be executed to ascertain the two undetermined parameters “a” and “b”. However, a further reduction in the number of trials is urgently required to support faster image compression and the like.
SUMMARY OF THE INVENTION
An object of the present invention is to provide a data compression method that makes it possible to obtain a target scale factor NSF through a single trial and a recording medium having a data compression program that makes it possible to implement the data compression method on a computer recorded therein.
FIG. 1
is a flowchart that illustrates the present invention. The following is an explanation of the present invention given in reference to FIG.
1
.
In order to achieve the object described above, the data compression method according to the present invention comprises a quantization trial step (
FIG. 1
S
1
,
FIG. 4
S
36
,
FIG. 9
S
48
,
FIG. 12
S
36
,
FIG. 14
S
76
) in which input data are quantized using an initial quantization table that is set in advance, a coding trial step (
FIG. 1
S
2
,
FIG. 4
S
36
,
FIG. 9
S
48
,
FIG. 12
S
36
,
FIG. 14
S
77
) in which a code volume achieved when the data that have undergone quantization in the quantization trial step are coded is determined, a relationship ascertaining step (
FIG. 1
S
3
and S
4
, FIG.
4
S
37
,
FIG. 9
S
52
,
FIG. 12
S
37
,
FIG. 14
S
78
and S
79
) in which the scale factor in the initial quantization table and the code volume are substituted in “the relational expression representing the relationship between the code volume and the scale factor” that includes two undetermined parameters “a” and “b” to ascertain the undetermined parameters in the relational expression based upon “the relational expression after the substitution” and “the statistical relationship between the undetermined parameters “a” and “b” obtained through a previous quantization operation,” a scale factor determining step (
FIG. 1
S
5
,
FIG. 4
S
38
,
FIG. 9
S
53
,
FIG. 12
S
38
,
FIG. 14
S
80
) in which a target scale factor that corresponds to the target code volume is determined by using the relational expression having the undetermined parameter ascertained in the relationship ascertaining step substituted therein, a quantization step (
FIG. 1
S
6
and S
7
,
FIG. 4
S
39
,
FIG. 9
S
54
,
FIG. 12
S
39
,
FIG. 14
S
81
and S
82
) in which the input data are quantized using a quantization table that corresponds to the target scale factor determined in the scale factor determining step and a coding step (
FIG. 1
S
8
,
FIG. 4
S
39
,
FIG. 9
S
54
,
FIG. 12
S
39
,
FIG. 14
S
83
) in which the data that have been quantized in the quantization step are coded.
The inventors of the present invention have discovered that, as demonstrated in the embodiments which are to be detailed later, there is a statistical relationship achieving a high degree of reproducibility between the two undetermined parameters “a” and “b”. Thus, in the relationship ascertaining step in the present invention, this statistical relationship obtained through a previous quantization operation is utilized to ascertain the undetermined parameters. This substantially reduces the number of undetermined parameters in the relational expression explained above from 2 to 1.
Thus, it becomes possible to ascertain all the undetermined parameters in the relational expression by obtaining trial data of the input data (the scale factor, the code volume) at least once. Consequently, through the data compression method according to the present invention, the number of trials can be reduced compared to the number of trials required in the method in the prior art (at least 2), so that the quantity of calculation required in the data compression method and the length of time required for implementing the data compre
Do Anh Hong
Nikon Corporation
Oliff & Berridg,e PLC
LandOfFree
Data compression method and recording medium with 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 Data compression method and recording medium with data..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Data compression method and recording medium with data... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3304657