Scan interleaving method

Details Scan interleaving method Scan interleaving method

1998-03-23

2001-05-29

Lee, Cheukfan (Department: 2622)

Image analysis

Image compression or coding

Shape, icon, or feature-based compression

C382S239000, C382S242000

Reexamination Certificate

active

06240212

ABSTRACT:

This application claims priority under 35 U.S.C. §§119 and/or 365 to Application No. 97-25784 filed in Korea on Jun. 19, 1997; the entire content of which is hereby incorporated by reference.
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to a scan interleaving method suitable for multipurpose encoding of binary images, and more particularly, to an improved scan interleaving method for selectively encoding a part or the whole of object image data according to the presence or absence of exceptional sample data (ESD).
2. Description of the Related Art
A scan interleaving method has been used to encode binary images in various applications such as adjustment of resolution or image quality, encoding to resist transmission errors, or transmission rate adjustment.
FIG. 1
illustrates a conventional concept of an encoder and a decoder. In
FIG. 1
, an encoder
11
encodes input image data, and sends a resulting bit stream. A decoder
15
extracts image data from the transmitted bit stream.
But, the encoder
11
shown in
FIG. 1
generates a great number of bits, thus increasing system complexity. This problem becomes serious in multipurpose encoding of binary images.
To overcome this problem, a so-called scan interleaving method is used, in which shape data is encoded through an XOR operation on adjacent scanning lines.
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 the image data to be encoded which is called object image data.
The base image data is composed of pixels on even (or odd) numbered scanning lines among pixels forming the original shape data
200
.
The object image data
220
is composed of pixels on odd (or even) numbered scanning lines among the pixels forming the original shape data
200
, and includes transitional sample data (TSD), ESD, and predictive sample data (PSD).
The TSD (the reference numeral
230
) is the pixels marked by rectangles in the object image data
220
shown in
FIG. 2
, and indicates that pixels on a current scanning line is the same as only one of the corresponding pixels on previous and following scanning lines. For example, the third pixel from the left on the first scanning line of the object image data
220
is different from 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 of the previous line, then, an XOR operation on the pixel of the current line with the corresponding pixel of the following line, and finally an XOR operation on the two XOR results.
The ESD (the reference numeral
240
) is the circled pixels in the object image data
220
, and indicates that a pixel on the current scanning line is different from both of the corresponding pixels of the previous and following scanning lines. For example, the third pixel from the right of the first scanning line in the object image data
220
is different from 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 of the previous line, then, an XOR operation on the pixel of the current line with the corresponding pixel of the following line, and finally an XOR operation on the two XOR results.
PSD are all the pixels except TSD (
230
) and ESD (
240
) in 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 achieved from the neighboring condition in consideration 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 predition probability of the context and the occurrence run of the value of the ESD are entropy-encoded. In the former, the pixel predition probability of the context and the continuous segments 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 an 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 another 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.
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, PSD by scan-interleaving binary image data, and encoding the obtained base image data, and object image data which includes TSD, ESD and PSP, comprising 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;
(f) determining whether the object image data includes ESD;
(g) encoding TSD 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, TSD, ESD, and PSD, comprising 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 in an encoding method;
(g′) determining whether the object image data includes ESD;
(h′) encoding TSD when there is no ESD; and
(I′) encoding the TSD, ESD, and PSD when there is ESD.


REFERENCES:
patent: 4845561 (1989-07-01), Doyle et al.
patent: 4914520 (1990-04-01), Beard
patent: 5850264 (1998-12-01), Agarwal
patent: 0607484A1 (1994-07-01), None
Bossen et al., “A Simple and Efficient Binary Shape Coding Technique Based On Bitmap Representation,” 1997Institute of Electrical and Electronics Engineers, Apr. 21, 1997, pp. 3129-3132.
Ebrahimi, Touradj, “MPEG-4 video verification model: A video encoding/decoding algorithm based on content representation,”Signal Processing: Image Communication, 1997, pp. 367-384.
Lee et al., “An Efficient Encoding of DCT Blocks with Block-Adaptive Scanning,”IEICE Transactions on Communications, vol. E77-B, No. 12, Dec. 1994, pp. 1489-1494.

Affiliated with

Also associated with

Rating

Scan interleaving method 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, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Scan interleaving method will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2561079