Image analysis – Image compression or coding – Shape – icon – or feature-based compression
Reexamination Certificate
1999-10-29
2004-05-25
Lee, Cheukfan (Department: 2622)
Image analysis
Image compression or coding
Shape, icon, or feature-based compression
C382S239000
Reexamination Certificate
active
06741748
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to an improved scan interleaving method based on context values of neighboring pixels, an improved binary shape encoding/decoding method, and an encoding/decoding apparatus suitable for the same.
2. Description of the Related Art
Scan interleaving methods, which are used to encode/decode binary images require multipurpose encoding/decoding functions such as adjustment of resolution or image quality, encoding/decoding to resist transmission errors, or transmission rate adjustment.
FIG. 1
illustrates a conventional concept of an encoder and a decoder. In
FIG. 1
, a shape encoder
11
encodes input shape data, and sends an encoded bit stream
13
to a shape decoder
15
. The shape decoder
15
restores the shape data from the transmitted bit stream.
However, in consideration of the resolution or image quality of a shape to be encoded, the shape encoder
11
shown in
FIG. 1
generates a great number of bits by performing encoding, thus increasing system complexity. This problem becomes serious in multipurpose encoding/decoding of binary images in the video communications field in which various additional functions such as adjustment of resolution or image quality, encoding/decoding to resist transmission errors, or transmission rate adjustment are required.
To overcome this problem, a so-called scan interleaving method is used, in which a pixel of a current scanning line is encoded/decoded through an XOR operation by referring to the immediately preceding and succeeding scanning lines of the current scanning line.
According to the scan interleaving (SI) method, if the pixel of the current scanning line and those of the immediately preceding and succeeding scanning lines of the current scanning line are all the same value, the current pixel is not encoded. The current pixel is only encoded when they are different from one another. In order to determine whether the pixel of the current scanning line and those of the immediately preceding and succeeding scanning lines of the current scanning line are all the same value, an XOR operation is performed.
FIG. 2
is a view for illustrating a conventional scan interleaving method. In
FIG. 2
, reference numeral
200
denotes original shape data, reference numeral
210
denotes base image data, and reference numeral
220
denotes object image data to be scan-interleaved.
The base image data is composed of pixels on odd (or even) numbered scanning lines among pixels forming the original shape data
200
.
The object image data
220
is composed of pixels on even (or odd) numbered scanning lines among the pixels forming the original shape data 200, and includes transitional sample data (TSD) and exceptional sample data (ESD), and predictive sample data (PSD).
The TSD, which are denoted by squares, indicate pixels for which the pixel on a current scanning line is the same as only one of the corresponding pixels on the preceding and succeeding scanning lines as shown in the object image data
220
of FIG.
2
. For example, the third pixel from the left on the first scanning line of the object image data
220
is different to only one of the third pixels from the left on the first and second scanning lines of the base image data
210
. Thus, the TSD in this case is “1”. This is obtained by performing an XOR operation on the pixel on the current scanning line with the corresponding pixel on the preceding line, then, an XOR operation on the pixel of the current line with the corresponding pixel of the succeeding line, and finally an XOR operation on the two XOR results.
The ESD, which are denoted by circles, indicate pixels for which the pixel on the current scanning line is different to both of the corresponding pixels on the preceding and succeeding scanning lines as shown in the object image data
240
of FIG.
2
. For example, the third pixel from the right of the first scanning line in the object image data
220
is different to both of the third pixels from the right of the first and second scanning lines in the base image data
210
. Thus, the ESD in this case is “0” by performing an XOR operation on the third pixel from the right on the current scanning line with the corresponding pixel on the preceding line, then, an XOR operation on the pixel on the current line with the corresponding pixel on the succeeding line, and finally an XOR operation on the two XOR results.
The PSD are all the pixels except the TSD (
230
) and the ESD (
240
) pixels in the object image data (
220
).
In the scan interleaving method, the base image data is independently encoded from the object image data. In encoding the object image data, a pixel context value is determined by the condition of adjacent pixels, and the object image data is entropy-encoded based on a probability model dependent on pixel context value.
The ESD is divided into continuous data and noncontinuous data, and then encoded. In the latter, the pixel prediction probability of the context and the occurrence run of the value of the ESD are entropy-encoded.
In the former, the pixel prediction probability of the context and the continuous segments of the first data value of the successive ESD are encoded.
However, the conventional scan interleaving method performs TSD encoding and ESD encoding in two separate steps, thus increasing the algorithm complexity and making implementation difficult.
In addition, the overall encoding performance is decreased due to encoding the ESD.
SUMMARY OF THE INVENTION
To solve the above problems, it is a first object of the present invention to provide an improved scan interleaving method for selectively encoding a part or the whole of object image data according to presence or absence of ESD.
It is a second object of the present invention to provide an improved scan interleaving method for increasing the overall coding efficiency by determining an optimum scan interleaving direction.
It is a third object of the present invention to provide a hierarchical binary shape encoding method.
It is a fourth object of the present invention to provide an encoding apparatus suitable for the hierarchical binary shape encoding method.
It is a fifth object of the present invention to provide a hierarchical binary shape decoding method.
It is a sixth object of the present invention to provide a decoding apparatus suitable for the hierarchical binary shape decoding method.
To achieve the above first object, there is provided a scan interleaving method for obtaining base image data and object image data to be encoded including TSD, ESD and PSD by scan-interleaving binary image data, and encoding the obtained base image data, and object image data which includes TSD, ESD and PSD, including the steps of (a) receiving the binary image data, (b) scan-interleaving the received binary image data, (c) obtaining the base image data from the scan-interleaving result, (d) obtaining the object image data from the scan-interleaving result, (e) encoding the base image data obtained in said step (d), (f) determining whether the object image data obtained in said steps (a) through (e) includes ESD, (g) encoding TSD only when there is no ESD, and (h) encoding TSD, ESD and PSD when there is ESD.
To achieve the second object, there is provided a scan interleaving method for obtaining base image data and object image data including TSD, ESD and PSD by scan-interleaving binary image data, and encoding the obtained base image data, and TSD, ESD and PSD, including the steps of (a′) receiving the binary image data, (b′) determining a scan interleaving direction for the received binary image data, (c′) scan interleaving the received binary data in the determined scan interleaving direction, (d′) obtaining the base image data from the scan-interleaving result, (e′) obtaining the object image data from the scan-interleaving result, (f′) encoding the base image data obtained in step (d′), (g′) determining whether the object image data includes ESD, (h′) encoding TSD onl
Jang Euee-seon
Shin Jae-seob
Son Se-hoon
Burns Doane Swecker & Mathis L.L.P.
Lee Cheukfan
Samsung Electronics Co.
LandOfFree
Scan interleaving method based on context values of... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Scan interleaving method based on context values of..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Scan interleaving method based on context values of... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3268474