Image analysis – Image compression or coding – Shape – icon – or feature-based compression
Reexamination Certificate
1998-12-21
2001-09-04
Couso, Jose L. (Department: 2721)
Image analysis
Image compression or coding
Shape, icon, or feature-based compression
Reexamination Certificate
active
06285795
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to a video encoding/decoding system; and, more particularly, to a method and an apparatus for efficiently encoding/decoding a binary shape signal by using a modified binary arithmetic coding 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 video object plane (VOP), wherein each binary pixel has a binary value, e.g., 0 or 255, 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 technique, 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 in order to provide a current bordered BAB as depicted in FIG.
7
. In
FIG. 7
, the pixels in the light 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 the neighboring BAB's of the current BAB 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.
6
A. Therefore, in
FIG. 6A
, a shaded pixel, i.e., a pixel in the current BAB, is encoded by using its intra-context
10
comprised of, 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) which represents a difference between the motion vector and a motion vector predictor (MVP) thereof is encoded by using, e.g., a variable length coding (VLC) scheme. Referring to
FIG. 6B
, the inter-context is composed of two subsets of pixels: a first subset of pixels
20
A includes, e.g., C
0
to C
3
, which are selected from pixels in the current frame in a manner similar to that used in the intra-CAE; and a second subset of pixels
20
B includes, e.g., C
4
to C
8
, which are 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. 8
, wherein the light area corresponds to the motion compensated BAB and the dark area corresponds to the border. After the bordered motion compensated BAB is determined, the second subset of pixels including the binary pixels C
4
to C
8
is selected from the bordered motion compensated BAB.
Accordingly, either the intra-context or the inter-context is selected as illustrated above and a context number for each of the pixels in the current BAB is calculated based on its corresponding context. Once the context number for each of the pixels in the current BAB is ciphered, a probability corresponding to the context number is detected from a probability table containing predetermined probabilities assigned to various context numbers, e.g., 2
10
context numbers calculated from the intra-context including C
0
to C
9
and 2
9
context numbers computed based on the inter-context including C
0
to C
8
, and the detected probability is arithmetically encoded to thereby produce an encoded binary shape signal. For further details of the CAE techniques and the MVD, reference may be made to
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.
In order to further enhance the coding efficiency of the binary shape signal, one of the mode signals listed in Table 1 is assigned for each BAB.
TABLE 1
Coding Modes
mode 1
MVD==0 && No Update
mode 2
MVD!=0 && No Update
mode 3
all 0
mode 4
all 255
mode 5
intra-CAE
mode 6
MVD==0 && inter-CAE
mode 7
MVD!=0 && inter-CAE
Mode
1
represents that a MVD for a BAB is zero and the BAB can be represented by a most similar candidate BAB thereof, whereas mode
2
indicates that a MVD for a BAB has a value other than zero and the BAB can be represented by a most similar candidate BAB. For the BAB of mode
1
only, the mode signal is encoded; and the BAB of mode
2
is represented by the mode signal and the MVD thereof. In determining “No Update”, a difference BAB is formed by a difference between each pixel of the most similar BAB and a corresponding pixel thereof in the current BAB; and it is checked whether an error of any of the 4×4 subblocks of 4×4 pixels included in the difference BAB is less than a predetermined threshold, said error of a subblock being, e.g., a sum of absolute pixel values within the subblock. If error values of all the subblocks are equal to or less than the predetermined threshold, the BAB is declared as of mode
1
or
2
depending on the value of the MVD thereof.
Similarly, if an error for any 4×4 subblock is equal to or less than the predetermined threshold when the pixels in a BAB are all changed to 0, the BAB is coded as an “all
—
0” mode, i.e., mode
3
. If the error for any 4×4 subblock is equal to or less than the threshold when the pixels in a BAB are all changed to 255, the BAB is coded as an all
—
255 mode, i.e., mode
4
. For a BAB of mode
3
or
4
, only the mode signal is encoded for the BAB. When a BAB does not belong to any one of modes
1
to
4
, “intra-CAE” or “inter-CAE” is employed for the coding of the BAB, wherein a BAB of mode
5
is represented by the mode signal and intra-CAE coded BAB data. A BAB of mode
6
is represented by the mode signal and inter-CAE coded BAB data; and a BAB of mode
7
is represented by the mode signal, inter-CAE coded BAB data and a MVD.
In MPEG-4, the mode determination scheme described above has been suggested in encoding a binary shape signal; and an exemplary method and apparatus for enabling the coding of the binary shape signal is disclosed in a commonly owned copending application, U.S. Ser. No. 08/984,033, filed on Dec. 2, 1997 and entitled “INTERLACED BINARY SHAPE CODING METHOD AND APPARATUS”.
Since, however, the conventional CAE technique requires a large-sized memory storing the probability table containing the predetermined probabilities, i.e., 2
10
probabilities for the intra-context and 2
9
probabilities for the inter-context, and has a burden of the encoding complexity due to the calculation of a context number corresponding to each pixel in the binary shape signal and arithmetical coding of the binary shape signal based on the probability table, it would be difficult to effectively carry out the encoding process in a high speed.
SUMMARY OF THE INVENTION
It is, therefore, a primary object of the invention to provide a method and an apparatus for encoding/decoding a binary shape signal by using a modified binary arithmetic coding technique instead of a CAE technique to thereby achieve a
Couso Jose L.
Daewoo Electronics Co. Ltd.
Pennie & Edmonds LLP
LandOfFree
Method and apparatus for encoding/decoding a binary shape... 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/decoding a binary shape..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for encoding/decoding a binary shape... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2516812