Image analysis – Image compression or coding – Including details of decompression
Reexamination Certificate
2000-05-22
2004-03-16
Boudreau, Leo (Department: 2621)
Image analysis
Image compression or coding
Including details of decompression
C382S238000, C382S242000
Reexamination Certificate
active
06707946
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Related Art
The present invention relates to a method of decoding coded segmented pictures, or partitions, divided into homogeneous regions to which specific labels are respectively associated, and to a corresponding decoding device. This invention has mainly applications in the field of the MPEG-4 standard, for instance for the implementation of MPEG-4 decoders.
2. Description of the Related Art
The multiple grid chain code approach (MGCC), described in the document “Multiple grid chain coding of binary shapes”, by P. Nunes, F. Ferreira and F. Marqués, Proceedings of International Conference on Image Processing, vol. III, pp. 114-117, Oct. 26-29, 1997, Santa Barbara, Calif., USA, allows to efficiently encode binary shape information of video objects in the context of object-based video coding schemes. This approach relies on a contour representation of the partition. As shown in
FIG. 1
that depicts a small general partition of size N×M with for example three regions to which respective labels are associated (in the present case, represented by grey, black and white circles), any pixel has four different contour elements associated.
FIG. 2
shows the same partition as depicted in
FIG. 1
, but with the indication of the specific contour elements that define the changes between every pair of neighbour pixels that do not belong to the same region.
FIG. 3
shows in a corresponding matrix of (2N+1)×(2M+1) sites the implementation of both grids: that associated to the pixel sites (=the circles) and that related to the contour sites (=the segments of lines). The contour elements that are situated between pixels of different labels are considered as active.
As illustrated in
FIG. 4
, an element of the contour grid may have up to six active neighbours: due to that, the contour grid is usually referred to as hexagonal grid. A conventional way to code the partition information in the contour grid is to select an initial point in the grid and to track the active sites up to finishing the contour. This method performs a lossless coding of the partition information, by encoding the movement from a current contour element to the following neighbour contour element (only three possible movements: straight, right, left).
Another contour tracking method is to move through the contour using larger steps, only contour elements linked by such larger steps being encoded: in the above-cited document, the described MGCC technique uses basic cells of 3×3 pixels, as the one illustrated in
FIG. 5
, where all contour and pixel sites in the cell are shown. For compression efficiency reasons, two types of cells are then used: counter-clockwise, as in
FIG. 6
, or clockwise, as in FIG.
7
. The way to index the different contour elements in each type of cell is presented: the initial contour site is denoted by the symbol
0
and the other ones by the symbols
1
to
7
, the symbol
1
being assigned to the site which is on the same side of the cell as the symbol
0
. Consequently, to characterize a cell, three parameters are necessary: its initial contour site, its type (clockwise or counter-clockwise), and its orientation (=east or west for a cell with an horizontal initial contour element, north or south for a vertical one). The coding algorithm selects between each of these two types of cell in order to maximize the number of contour elements coded per cell.
The MGCC technique uses said indexing, as well as its possible rotations. Starting by the input element of the cell indexed with a
0
in
FIG. 6
, any output element from the set (
1
,
2
, . . . ,
6
,
7
) can be reached, but the way to go through the cell is not univocally defined by the output element: as shown in the example of
FIGS. 8 and 9
, a movement (in this case, from
0
to
4
) may indeed correspond to two different contour configurations. The contour elements inside the cell (
8
,
9
,
10
,
11
), not coded, introduce ambiguity in the coding process, two different sets of contour sites (
0
,
8
,
9
,
4
) or (
0
,
11
,
10
,
4
) being possible. This ambiguity introduces coding losses. Nevertheless, the only possible error is the erroneous labeling of the central pixel of the cell, i.e. only of an isolated boundary pixel.
In a contour tracking process, several cells are then linked up in order to complete the contour. To link two cells, the output contour site of the current cell becomes the input contour site of the following cell, as
FIG. 10
shows. When coding with the MGCC approach the boundary of a single region, the bitstream thus generated therefore contains: (a) the position of the initial contour site, and (b) the chain of symbols representing the movements performed in order to track the contour.
In the contour tracking process, it is needed to change progressively the position of the basic cell through the grid. The proposed technique is described for instance in the article “Encoding of line drawings with a multiple grid chain code”, by T. Minami and K. Shinohara, IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. PAMI-8, n
o
2, March 1986, pp. 269-276. The basic principle of said technique is explained with reference to
FIGS. 11
to
15
.
As indicated indeed in
FIG. 11
giving an example of coding with a fixed grid, a contour segment has been coded by means of the symbol
4
in the first cell (a counter-clockwise one). If cells of the same grid are used, the symbol
7
(
FIG. 12
) is used in the second cell for tracking the contour (the symbol
0
being always the new initial—or input—site), and the symbol
2
(
FIG. 13
) in the third one, these second and third cells being in that case clockwise ones. Three cells are therefore needed to track the contour from the first initial site. On the contrary, only two are needed if the grid (i.e, in fact, the position of the center of the cell) is changed: as shown in
FIGS. 14 and 15
that illustrate a modification of the grid with respect to the example of
FIGS. 11
to
13
, only a second cell is now needed to go to the same output site.
This solution of
FIGS. 14 and 15
leads to a more compact representation of the contour. However, three different classes of grids are then necessary to define the shift of each grid with respect to the origin of the corresponding cell (called GO) before said shift. These three classes G
1
, G
2
, G
3
are defined, as indicated in the following classification table (Table 1) by the position (x, y) of the pixel which is the origin of each type of cell, with respect to the pixel which is the origin of said corresponding cell:
TABLE 1
SHIFT WITH RESPECT TO THE ORIGIN
GRID
OF THE REFERENCE GRID GO:
G0
(0, 0)
G1
(1, 0)
G2
(0, 1)
G3
(1, 1)
In the example of
FIG. 10
, a cell of the class G
2
was used, with respect to the corresponding current cell GO. In another example illustrated in
FIG. 16
, a cell of the class G
1
is used, with respect to the corresponding current cell GO.
However, the MGCC approach previously described can only be used to code binary partitions. In case of general segmented pictures, the partitions contain regions that share contours. A more appropriate approach is then described in the european patent application N
o
99400436.4 (PHF995 11), filed on Feb. 23
rd
, 1999, that relates to a method of coding segmented pictures, or partitions (divided into homogeneous regions to which specific labels are respectively associated), comprising, for each successive partition, the steps of:
(a) translating the picture of labels into a description in terms of a contour element chain in which the elements are defined by means of their movements through successive basic cells, between an input point and an output point of said cells;
(b) tracking inside each successive cell each contour from its initial contour point, previously extracted, to its end by storing chain symbols corresponding both to input, internal and output contour elements of said cell and to priorities between multiple outputs elements;
(c) repeati
Gasull Antoni
Gomila Cristina
Marques Ferran
Boudreau Leo
Dang Duy M.
Koninklijke Philips Electronics , N.V.
LandOfFree
Partition decoding method and device does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Partition decoding method and device, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Partition decoding method and device will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3205418