Pulse or digital communications – Bandwidth reduction or expansion
Reexamination Certificate
1999-09-27
2003-07-15
Kelley, Chris (Department: 2713)
Pulse or digital communications
Bandwidth reduction or expansion
C375S240240, C382S241000, C382S242000, C382S238000, C382S199000, C382S203000, C382S258000
Reexamination Certificate
active
06594310
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to a method of coding segmented pictures, or partitions, divided into homogeneous regions to which specific labels are respectively associated, and to a corresponding device. This invention has mainly applications in relation with the MPEG-4 standard, for the implementation of MPEG-4 encoders.
BACKGROUND OF THE INVENTION
Conventional methods of coding segmented pictures—or partitions—are usually considered as rather expensive in terms of amount of bits, e.g. an average value of 1,3 bit per pixel of contour with the so-called chain code technique. Lossy shape coding techniques have therefore been proposed, but losses in shape information often result in an unacceptable degradation of the subjective quality of the image displayed on the basis of the decoded picture.
Quasi-lossless shape coding techniques (and therefore, by extension, quasi-lossless partition coding techniques) have then been proposed. For instance, the so-called 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. Said approach also allows general partition coding, while introducing very few and controlled losses, only restricted to isolated picture elements (pixels) belonging to the boundaries of the regions of each partition.
This conventional MGCC 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 (in the present case, represented by the grey, black and white circles) are associated, 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.
On turn, an element of the contour grid may have up to six active neighbours, as illustrated in
FIG. 4
, and, due to that, the contour grid is usually referred to as hexagonal grid. A 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 the end of the corresponding 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 will therefore contain: (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, no.2, Mar. 1986, pp. 269-276. The basic principle is explained with reference to
FIGS. 11
to
15
.
As indicated in
FIG. 11
giving an example of coding with a fixed grid, a contour segment has been here 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 indeed 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, 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 G
0
); in another example illustrated in
FIG. 16
, a cell of the class G
1
is used (with respect to the corresponding current cell G
0
).
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, and said approach is no longer appropriate.
SUMMARY OF THE INVENTION
It is therefore an object of
Gasull Antoni
Gomila Cristina
Marques Ferran
An Shawn S.
Gross Russell
Kelley Chris
LandOfFree
Partition coding 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 coding method and device, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Partition coding method and device will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3070269