Image analysis – Image compression or coding – Shape – icon – or feature-based compression
Reexamination Certificate
1998-12-22
2001-07-17
Chang, Jon (Department: 2623)
Image analysis
Image compression or coding
Shape, icon, or feature-based compression
C382S247000, C375S240080
Reexamination Certificate
active
06263115
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to a video encoding system; and, more particularly, to a method and apparatus for enhancing a coding efficiency of a binary shape signal by selecting a more appropriate context based on a zig-zag scanning technique.
DESCRIPTION OF THE PRIOR ART
A binary shape signal, representing the location and shape of an object, can be expressed as a binary alpha block (BAB) of, e.g., 16×16, binary pixels within a frame or a video object plane (VOP), wherein each binary pixel has a binary value, e.g., 0 or 1, representing either a background pixel or an object pixel. A BAB can be encoded by using a conventional bit-map-based shape coding method such as a context-based arithmetic encoding (CAE) method.
For instance, for an intra-frame, a current BAB is encoded by using a conventional intra-CAE method, wherein each pixel in the current BAB is arithmetically coded based on an intra-context comprised of a set of pixels selected from a current frame. In other words, when encoding the current BAB, pixels from neighboring BAB's are used to make up the intra-context. A border of width
2
around the current BAB is used as depicted in
FIG. 5
in order to provide a current bordered BAB. In
FIG. 5
, the pixels in the light grey area of the current bordered BAB are the part of the current BAB to be encoded and the pixels in the dark area of the current bordered BAB are the border pixels. These are obtained from previously encoded and reconstructed BAB's except for those marked ‘0’ which are unknown at a decoding time. Based on the current bordered BAB, the intra-context is selected as shown in FIG.
4
A. Therefore, in
FIG. 4A
, a shaded pixel, i.e., a pixel in the current BAB, is encoded by using its intra-context
10
, e.g., C
0
to C
9
.
For an inter-frame, the current BAB may be coded by using either the intra-CAE or an inter-CAE technique depending on whichever CAE technique between the two generates a less amount of encoded data. According to the inter-CAE technique, an error representing a difference between the current BAB and each of predetermined candidate BAB's thereof included in a previous frame is calculated first and a most similar candidate BAB and a motion vector are found by a motion estimation technique, wherein the most similar candidate BAB represents a candidate BAB generating a least error among the candidate BAB's and the motion vector denotes a displacement between the current BAB and the most similar candidate BAB. Thereafter, each pixel in the current BAB is arithmetically coded based on an inter-context and a motion vector difference (MVD) representing a difference between the motion vector and a motion vector predictor (MVDP) thereof is encoded by using, e.g., a variable length coding (VLC) scheme. Referring to
FIG. 4B
, the inter-context is composed of two subsets of pixels, a first subset of pixels
20
A, e.g., C
0
to C
3
in
FIG. 4B
, being selected from pixels in the current frame in a similar manner to what is used in the intra-CAE and a second subset of pixels
20
B, e.g., C
4
to C
8
in
FIG. 4B
, being chosen from the previous frame based on the motion vector. Namely, a border of width
1
around a motion compensated BAB, detected from the previous frame by using the motion vector, is utilized to supply a bordered motion compensated BAB as described in FIG.
6
. In
FIG. 6
, the light grey area corresponds to the motion compensated BAB and the dark area corresponds to the border. Once the bordered motion compensated BAB is determined, the second subset of pixels
20
B containing the binary pixels C
4
to C
8
is selected from the bordered motion compensated BAB, wherein the pixel position of the pixel C
6
is identical to that of the shaded pixel in the first subset
20
A.
Accordingly, either the intra-context or the inter-context is selected as illustrated above and a context number of the shaded pixel in the current BAB is calculated based on its corresponding context. Once the context number of the shaded pixel is ciphered, a probability corresponding to the context number is detected from a probability table containing predetermined probabilities assigned to various context numbers and the detected probability is arithmetically encoded to thereby produce an encoded binary shape signal. Further details of the CAE techniques and the MVD can be found in MPEG-4 Video Verification Model Version 7.0, International Organization for Standardization, Coding of Moving Pictures and Associated Audio Information, ISO/IEC JTC1/SC29/WG11 MPEG97/N1642, Bristol, April 1997.
Since, however, in the conventional CAE technique, each of the pixels in the current BAB is encoded along a horizontal scanning order, the context is determined by mainly considering horizontal correlation between the pixels in the current BAB. Therefore, it is desired to select an appropriate context by taking vertical correlation together with the horizontal correlation between the pixels in the current BAB into consideration to thereby enhance the coding efficiency of the binary shape signal.
SUMMARY OF THE INVENTION
It is, therefore, a primary object of the present invention to provide a method and apparatus for encoding a binary shape signal by using a more appropriate context determined based on a zig-zag scanning technique in order to improve a coding efficiency of the binary shape signal.
In accordance with one aspect of the present invention, there is provided a method for encoding a binary shape signal including a plurality of binary blocks, each binary block having a multiplicity of pixels and each pixel having one of two different binary values, comprising the steps of:
(a) zig-zag scanning a current binary block to provide a target pixel being one of the pixels in the current binary block;
(b) determining a context corresponding to the target pixel from pixels processed prior to the target pixel by considering the scanning result;
(c) calculating a context number of the target pixel based on the context;
(d) finding a probability of the target pixel by using the context number;
(e) repeating the steps (a) to (f) until probabilities for all of the pixels in the current binary block are found; and
(f) arithmetically encoding the current binary block by using the probabilities for all of the pixels to thereby produce the encoded binary shape signal.
In accordance with another aspect of the present invention, there is provided an apparatus for encoding a binary shape signal including a plurality of binary blocks, each binary block having a multiplicity of pixels and each pixel having one of two different binary values, which comprises:
a scanning block for zig-zag scanning a current binary block and outputting each of the pixels in the current binary block in the scanning order;
a context determination block for selecting a context corresponding to said each of the pixels from pixels processed prior to said each of the pixels by regarding the scanning order;
a context number calculation block for ciphering a context number of said each of the pixels by using the corresponding context; and
a coding block for detecting a probability of said each of the pixels by using the corresponding context number and arithmetically encoding the current binary block by using the probabilities for all of the pixels to thereby produce the encoded binary shape signal.
REFERENCES:
patent: 5422734 (1995-06-01), Kang
patent: 5841900 (1998-11-01), Yokoyama
patent: 5880688 (1999-03-01), Rust
patent: 5933105 (1999-08-01), Cho
patent: 5974184 (1999-10-01), Eifrig et al.
patent: 6108449 (2000-08-01), Sekiguchi et al.
patent: 6133955 (2000-10-01), Han
Ostermann “Coding of arbitrarily shaped objects with binary and greyscale alpha-maps: what can MPEG-4 do for you?” Proc. of the 1998 IEEE international Symposium on Circuits and Systems, vol. 5, pp273-276, Jun. 1998.
Chang Jon
Daewoo Electronics Co. Ltd.
Pennie & Edmonds LLP
Wu Jingge
LandOfFree
Method and apparatus for encoding a binary shape signal does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for encoding a binary shape signal, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for encoding a binary shape signal will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2523351