Pulse or digital communications – Bandwidth reduction or expansion – Television or motion video signal
Reexamination Certificate
1998-12-17
2001-03-20
Britton, Howard (Department: 2713)
Pulse or digital communications
Bandwidth reduction or expansion
Television or motion video signal
C382S234000, C348S441000
Reexamination Certificate
active
06205175
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to a method and apparatus for encoding a contour of an object in a video signal; and, more particularly, to a method and apparatus for encoding a contour of an object in a video signal by employing a vertex coding technique.
DESCRIPTION OF THE PRIOR ART
In digitally televised systems such as video-telephone, teleconference and high definition television systems, a large amount of digital data is needed to define each video frame signal since a video line signal in the video frame signal comprises a sequence of digital data referred to as pixel values. Since, however, the available frequency bandwidth of a conventional transmission channel is limited, in order to transmit the large amount of digital data therethrough, it is necessary to compress or reduce the volume of data through the use of various data compression techniques, especially in the case of such low bit-rate video signal encoders as video-telephone and teleconference systems.
One of such techniques for encoding video signals for a low bit-rate encoding system is the so-called object-oriented analysis-synthesis coding technique, wherein an input video image is divided into objects, and three sets of parameters for defining the motion, contour and pixel data of each object are processed through different encoding channels.
In processing a contour of an object expressed in a video signal, contour information representing positions of contour pixels constituting the contour is important for the analysis and synthesis of the shape of the object. A classical coding method used to represent the contour information is a chain coding technique. The chain coding technique, however, requires a substantial amount of bits for representing the contour information, although the technique does not incur any loss in the contour information.
To overcome the drawback of the chain coding method, therefore, there have been proposed several methods to encode the contour information such as a polygonal approximation, B-spline approximation and DST (Discrete Sine Transform) combined with a polygonal approximation technique. In such approximation techniques, the contour is approximated by line or curve segments, each of the segments connecting a pair of neighboring vertices on the contour, and the vertices are encoded based on, e.g., the so-called locally-adaptive octant-based vertex coding technique (see, e.g., International Organization for Standardization, Coding of Moving Pictures and Audio Information, ISO/IEC JTCI/SC29/WG11, Shape Coding AHG, Jul. 30, 1996, entitled “Revised Description of S
4
a: Geometrical Representation Method”by K. O'Connell, P. Gerken and J. H. Kim).
Referring to
FIG. 1
, there is shown a schematic block diagram of a conventional apparatus for encoding vertices of a contour of an object in a video signal based on the octant-based vertex coding technique.
A binary mask is inputted to a contour extraction block
10
, wherein, each of the pixels in the binary mask is represented by one of the binary values depending on whether said each pixel resides either in an object or in a background region. For example, the binary values are 0 and 255, respectively.
The contour extraction block
10
extracts a contour image of the object by using the binary mask and provides the contour image to a vertex selection block
20
. The contour is made of contour pixels, each being an object pixel positioned on the boundary of the object.
The vertex selection block
20
selects a plurality of vertices by using a conventional iterative refinement technique, e.g., a polygonal approximation technique, wherein a pair of contour pixels separated by a maximum distance are determined first as a starting vertex and additional contour pixels are selected, one by one, as another vertex until a largest perpendicular distance d
max
from a line segment joining a pair of adjacent vertices to a contour segment defined by the pair of adjacent vertices does not exceed a preset threshold D
max
.
At a vertex coding block
30
, the vertices received from the vertex selection block
20
are encoded based on, e.g., the so-called octant-based vertex coding technique.
In the octant-based vertex coding technique, an x and a y component, denoted as X and Y, of a displacement R between every pair of adjacent vertices are calculated. Thereafter, two vertices corresponding to a largest magnitude among all the x and the y components (X's and Y's) are selected as an initial vertex and a final vertex of the contour. N vertices are then sequentially indexed along the contour starting from the initial vertex toward the final vertex as shown in
FIG. 2
, N being a total number of vertices on the contour and assumed to be
8
in
FIG. 2
for the purpose of illustration. In
FIG. 2
, the x component corresponding to the pair of vertices V
1
and V
8
is shown to be the largest among the 8 pairs of X's and Y's obtained from the vertices V
1
to V
8
.
After determining the initial and the final vertices, an x_max and a y_max, the respective maximum values among the x and the y components (X
i
's and Y
i
's) of the displacements R
i
's, are determined as an x_dynamic_range and a y_dynamic_range of the contour, respectively, wherein R
i
=P
i+1
−P
i
for i=1,2, . . . ,N−1, P
i
being a position vector corresponding to a vertex V
i
. Subsequently, the total number of vertices N, the x_dynamic_range, the y_dynamic_range and an absolute position of the initial vertex V
1
are encoded, while each of the remaining vertices, i.e., V
i+1
for i=1 to (N−1), is encoded based on the displacement R
i
from its previous vertex V
i
.
Specifically, as shown in
FIG. 3
, an octant to which a vertex V
i+1
belongs is determined among octant
0
to octant
7
based on an x component X
i
and a y component Y
i
of the displacement R
i
, wherein the eight nearest neighbors to the origin (all marked by the closed circles in
FIG. 3
) represent the starting points of the eight octants.
After determining octants for the vertices V
i+1
's, the indices of the octants are coded by using the conventional differential chain coding technique; and the magnitudes of the components X
i
and Y
i
, i.e., x_mag and y_mag, representing the relative position of the vertex V
i+1
with respect to its preceding vertex V
i
are encoded using the bits determined based on the x_dynamic_range and the y_dynamic_range, respectively.
In another instance of the octant-based vertex coding technique, the octant indices and R
i
's are encoded alternatively through the use of the so-called syntax-adaptive arithmetic coding (SAAC). In the SAAC, the number of possible symbols depends on the dynamic range maximum, i.e., max(x_dynamic_range, y_dynamic_range). For further details of the octant-based vertex coding technique, see K. O'Connell et al., supra.
By virtue of the process of ordering the vertices as described above, the amount of data representing the vertices can be effectively reduced in the octant-based vertex coding technique, since each of the vertices except the initial one is represented by the octant it belongs to and the magnitudes of X
i
and Y
i
.
Meanwhile, in the conventional vertex coding method, the number of bits needed to encode the magnitudes depends directly on the x_dynamic_range and the y_dynamic_range. In other words, the number of bits needed to encode a magnitude of a line segment depends on a maximum magnitude thereof obtained based on the x_dynamic_range and the y_dynamic_range.
Specifically, in the conventional vertex coding method, the number of bits needed to encode a line segment having a largest length among line segments approximating a contour is determined as a threshold (TH) for use in encoding each line segment thereof. Then, each of the line segments thereof is encoded with the TH number of bits.
Since such conventional vertex coding method still requires a large amount of bits in representing or encoding the ve
Britton Howard
Daewoo Electronics Co. Ltd.
Diep Nhon T.
Pennie & Edmonds LLP
LandOfFree
Method and apparatus for encoding a contour of an object in... 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 contour of an object in..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for encoding a contour of an object in... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2480298