 |
Claims  |
|
|
We claim:
1. A method of coding segmented pictures, or partitions, that correspond to a sequence of original pictures and identify in said pictures contours and closed regions to which
corresponding labels are associated, said method comprising a first definition step for defining the time motion evolution of the partitions between two successive pictures and a second coding step for coding motion, contours and textures of said regions
of successive partitions, wherein, for each current partition considered with respect to the previous one, the first step comprises in cascade:
(1) a motion estimation and compensation sub-step, for the definition of a motion-compensated partition marking for each region coming from the previous partition the position of the core of the region in the current partition;
(2) a temporal extension sub-step of said regions previously defined by compensation in the current partition, for the definition of a so-called projected partition;
(3) an iterative partition topology definition sub-step, for the determination, on the basis of motion and texture criteria, of additional partitions created iteratively either by merging or re-segmenting regions of said projected partition, said
additional partitions and the projected partition forming levels of a partition tree;
(4) a decision sub-step, for the selection of the regions of an optimal partition within the proposals of regions contained in any level of said partition tree and of the best strategy for coding each region of said optimal partition, said
successive optimal partitions constituting the sequence of the partitions to be coded, wherein said decision sub-step comprises a decision tree definition sub-step for the selection of an optimal partition among the projected and additional partitions
contained in said partition tree and an optimization sub-step for selecting the most appropriate coding strategy with respect to each region of said optimal partition; said second step then comprising, for the definition of the coded information that
has to be transmitted and/or stored for each region of said partitions, a decision coding sub-step.
2. A coding method according to claim 1, wherein said motion estimation and compensation sub-step comprises a motion estimation operation, by way of a block matching method, and a motion compensation operation, by keeping from every region in
the previous partition only its largest connected component marking with the same label as in the previous partition the position of the core of said region in the current partition, and said temporal extension sub-step comprises the implementation of a
watershed lines method.
3. A coding method according to claim 1, wherein a texture coding method to be applied to each region of said optimal partition is chosen within a list comprising the method of approximation by mean value, the polynomial approximation method,
the shape adaptive discrete cosine transform method, and the dyadic bidimensional wavelet transform method.
4. A coding method according to claim 1, wherein said first definition step also comprises in cascade with the first ones the following additional sub-steps:
(1) before the motion estimation and compensation sub-step, an additional segmentation sub-step for segmenting the current partition, then called a coarse partition, until all regions are homogeneous according to a given criterion, said
segmentation sub-step allowing to create a so-called dense partition;
(2) between the temporal extension sub-step and the partition topology definition sub-step, an additional merging sub-step for merging the projected regions of said dense partition, said merging sub-step allowing to define a so-called projected
coarse partition.
5. A coding method according to claim 4, wherein said additional segmentation is a size-oriented one, the size parameter being progressively decreased until a given homogeneity criterion referring to the gray level homogeneity of the pixels,
such as the mean squared error of the pixels with respect to the mean of the regions, is reached.
6. A system for coding segmented pictures, or partitions, that correspond to a sequence of original pictures and identify in said pictures contours and closed regions to which corresponding labels are associated, said system comprising a first
time motion evolution defining sub-system and a second motion, contour and texture coding sub-system, in which the coded information to be transmitted and/or stored for each current partition comprises coded signals corresponding to an optimal partition
composed either of regions of a main partition determined by a motion estimation and compensation of a previous partition or of regions of additional partitions created iteratively by merging or re-segmenting said regions of the main partition in
accordance with a motion and a texture criteria of neighboring regions, wherein the first mentioned sub-system comprises means for selecting an optimal partition among proposed regions comprised of the regions of the main partition determined by the
motion estimation and compensation and the regions of additional partitions created iteratively by the merging or re-segmentation, the proposed regions forming levels of a partition tree, and for selecting the most appropriate coding strategy with
respect to each region of the optimal partition; said coded signals including the appropriate indications on the origin of each region, in the form of merging orders and splitting information.
7. A coding system according to claim 6, in which, for each current partition considered with respect to the previous one:
(I) said first sub-system comprises:
(A) a first partition preprocessing sub-assembly, comprising:
(1) a time evolution definition device, comprising:
(a) a motion estimation circuit;
(b) a motion compensation circuit; and
(c) a temporal extension circuit, the output of which constitutes a so-called projected partition defining said main partition;
(2) a partition topology definition device, comprising:
(d) at least a merging circuit; and
(e) at least a re-segmenting circuit;
the output of said partition topology device constituting the levels of the partition tree composed of said projected partition and of the additional partitions created by said merging and re-segmenting circuits;
(B) a second decision sub-assembly, comprising:
(f) a decision tree construction circuit; and
(g) an optimization circuit;
the output of said decision sub-assembly constituting an optimal partition sent to said second coding sub-system, and said optimal partition being obtained by an association of regions from various levels of the partition tree;
(II) said second sub-system comprises:
(C) a third coding sub-assembly, comprising:
(4) a first decision decoding device;
(5) a second motion coding device;
(6) a third contour coding device;
(7) a fourth texture coding device; and
(8) a multiplexer of the coded output signals of said four coding devices.
8. A coding system according to claim 7, in which said merging circuit comprises a motion estimation stage and a merging proposition stage, and is followed by a second similar merging circuit, and so on, in order to build the upper levels of
said partition tree by merging from the projected partition neighbouring regions which have a similar motion.
9. A coding system according to claim 7, in which said decision tree construction circuit comprises a distortion computation stage, a rate computation stage and a memory, said memory being provided for storing in the form of a decision tree a
list of distortions and a list of rates having both the same length as an associated list of texture coding methods in which a selection is made for the coding operation of the texture of each region of said partition tree, and said optimization circuit
comprises a computing sub-stage, provided for making a local analysis of each node of said decision tree, and a decision sub-stage, provided for defining from the whole set of regions of the partition tree a final set of the regions that constitute said
optimal partition to be coded.
10. A coded signal corresponding, with respect to a sequence of segmented pictures comprising a plurality of regions and associated labels and defining successive partitions, to each region of the current partition of said sequence, said coded
signal consisting of a multiplexed signal comprising:
(A) a coded motion information, corresponding to the estimation of a motion model that characterizes the evolution of the segmentation between said successive partitions and allows to define a so-called projected partition;
(B) a coded partition information, corresponding to texture and contour information of each region of an optimal partition selected, on the basis of rate and distortion criteria, among all the regions of a hierarchy of additional finer and
coarser partitions constructed from the projected partition corresponding to the current one, wherein levels of a partition tree are formed from said hierarchy and include additional partitions created by iteratively merging or re-segmenting regions of
the projected partition in accordance with a motion and a texture criteria of the regions; and
(C) a coded decision information, corresponding to the coding strategy defined for each of said selected regions of the projected and the additional partitions, according to the coding cost and quality associated to said rate and distortion
criteria.
11. A storage medium for storing a coded signal corresponding, with respect to a sequence of segmented pictures comprising a plurality of regions and associated labels and defining successive partitions, to each region of the current partition
of said sequence, said coded signal consisting of a multiplexed signal comprising:
(A) a motion information, corresponding to the estimation of a motion model that characterizes the evolution of the segmentation between said successive partitions and allows to define a so-called projected partition;
(B) a partition information, corresponding to texture and contour information of each region of an optimal partition selected, on the basis of rate and distortion criteria, among all the regions of a hierarchy of additional finer and coarser
partitions constructed from the projected partition corresponding to the current one, wherein levels of a partition tree are formed from said hierarchy and include additional partitions created iteratively by merging or re-segmenting regions of the
projected partition in accordance with a motion and a texture criteria of the regions; and
(C) a decision information, corresponding to the coding strategy defined for each of said selected regions of the projected and the additional partitions, according to the coding cost and quality associated to said rate and distortion criteria.
12. A method for decoding signals corresponding to segmented pictures, or partitions, that identify in an associated sequence of original pictures contours and closed regions to which corresponding labels are associated and having been
previously coded by a coding method comprising a first definition step provided for defining, for each current partition considered with respect to the previous one, on the one hand a so-called projected partition obtained by motion estimation and
compensation and a temporal extension of the compensated partition and on the other hand additional partitions created iteratively either by merging or re-segmenting regions of said projected partition in accordance with a motion and a texture criteria
of neighboring regions, and for selecting an optimal partition composed of regions contained in any level of a partition tree formed by said projected and additional partitions, and a second coding step provided for the definition of the coded
information that has to be transmitted and/or stored for each region of each of the successive optimal partitions, wherein said decoding method comprises a first decision decoding step, provided for defining which coding strategy has been previously used
for each region of each optimal partition, a second motion decoding step, a third partition decoding step, and a fourth texture decoding step.
13. A decoding method according to claim 12, wherein said third partition decoding step comprises a first relabelling sub-step, provided for limiting the value of label numbers by reassigning a label value to each region, only labels 1 to N
being used if there are N regions, a second merging sub-step, provided for performing the merging orders, a third intra regions decoding sub-step, a fourth motion-compensation and compensated errors decoding sub-step, and a decoded compensation errors
partition labelling sub-step.
14. A system for decoding signals corresponding to segmented pictures, or partitions, that identify in an associated sequence of original pictures contours and closed regions to which corresponding labels are associated, said signals
constituting for each current partition a coded information corresponding to an optimal partition composed of selective ones of proposed regions comprised of regions of a main partition determined by a motion estimation and compensation of a previous
partition and a temporal extension of the compensated partition and of regions of additional partitions created iteratively by merging or re-segmenting regions of the main partition in accordance with a motion and a texture criteria of neighboring
regions, the proposed regions forming levels of a partition tree, wherein said decoding system comprises an input buffer, provided for storing and demultiplexing said coded information, a decision decoding device, provided for decoding the information
corresponding to the strategy used for coding said optimal partition, a motion decoding device, a partition decoding device, and a texture decoding device. |
|
 |
|
 |
Claims |
|
|
|
Description |
|
|
BACKGROUND OF THE INVENTION
The present invention relates to a method of coding segmented pictures, or partitions, that correspond to a sequence of original pictures and identify in said pictures contours and closed regions to which corresponding labels are associated, said
method comprising a first definition step for defining the time motion evolution of the partitions between two successive pictures and a second coding step for coding motion, contours and textures of said regions of successive partitions, and to a
corresponding coding system. The invention also relates to a signal coded by means of such a coding system, to a storage medium for storing this coded signal, to a method of decoding said coded signal, and to a corresponding decoding system.
A method and apparatus for decomposing a signal corresponding to an original picture into components using features (such as contours and regions) identified in said picture and then coding separately said components is described for instance in
the european patent application EP 0389044. However such a conventional method of coding segmented pictures has no flexibility with respect to the type of segmentation that has be obtained or to the type of coding for the different areas of the original
pictures. Particularly these method and apparatus are not an appropriate technical proposition as a possible solution for the elaboration of the MPEG4 (Moving Picture Experts Group) audio visual coding standard which targets interactive multimedia
applications at low and very low bit rates (the limit of which is generally considered as equal or close to 1 Mbit/s.).
SUMMARY OF THE INVENTION
It is a first object of the invention to propose a coding method able to efficiently handle a partition-based representation of a scene, without any particular assumption about the scene content, its complexity or the image format (the scene can
have an arbitrary number of objects with arbitrary relations, positions and motions), and particularly to be an adapted coding approach for addressing the various functionalities contemplated in the future standard MPEG4.
At this end, the invention concerns a coding method as described in the preamble of the description and in which, for each current partition considered with respect to the previous one, the first step comprises in cascade:
(1) a motion estimation and compensation sub-step, for the definition of a motion-compensated partition marking for each region coming from the previous partition the position of the core of this region in the current partition;
(2) a temporal extension sub-step of said regions previously defined by compensation in the current partition, for the definition of a so-called projected partition;
(3) a partition topology definition sub-step, for the determination, on the basis of motion and texture criteria, of additional partitions created either by merging or by re-segmenting regions of said projected partition, said additional
partitions forming together with the projected one a partition tree;
(4) a decision sub-step, for the selection of the regions of an optimal partition within the proposals of regions contained in any level of said partition tree and of the best strategy for coding each region of said optimal partition, said
successive optimal partitions constituting the sequence of the successive partitions to be coded, said second step then comprising, for the definition of the coded information that has to be transmitted and/or stored for each region of said partitions, a
decision coding sub-step.
This method presents, from the viewpoint of the user, a very noticeable flexibility mainly based on an advantageous preprocessing of the image sequence. Moreover, the hierarchy of partitions that is proposed to the subsequent decision step and
in which contours are preserved whatever the considered hierarchical level allows to deal with the final coding step in an optimal manner. The coding scheme is indeed able to accommodate very different situations and to lead to the best image
representation for any given coding cost and whatever the set of available coding techniques.
In a particular embodiment, said coding method is characterized in that said motion estimation and compensation sub-step comprises a motion estimation operation, by way of a block matching method, and a motion compensation operation, by keeping
from every region in the previous partition only its largest connected component marking with the same label as in the previous partition the position of the core of said region in the current partition, and said temporal extension sub-step comprises the
implementation of a watershed lines method.
Moreover, according to the invention, it is advantageous that said decision sub-step comprises a first decision tree definition sub-step, for the selection of an optimal partition among the projected and additional partitions contained in said
partition tree, and a second optimization sub-step, for taking a decision about the most appropriate coding strategy with respect to each region of said optimal partition, the second coding step being then provided for selecting for each region of the
selected optimal partition the most appropriate texture coding method according to a predetermined criterion.
According to the coding philosophy of the proposed method, several texture coding techniques may be chosen. Preferably, said texture coding method to be applied to each region of said optimal partition is chosen within a list comprising the
method of approximation by mean value, the polynomial approximation method, the shape adaptive discrete cosine transform method, and the dyadic bidimensional wavelet transform method.
Finally, in an improved implementation allowing to consider the case when the original regions are not homogeneous in gray level, said first step also comprises in cascade with the first ones the following additional sub-steps:
(1) before the motion estimation and compensation sub-step, an additional segmentation sub-step for segmenting the current partition, then called a coarse partition, until all regions are homogeneous according to a given criterion, said
segmentation sub-step allowing to create a so-called dense partition;
(2) between the temporal extension sub-step and the partition topology definition sub-step, an additional merging sub-step for merging the projected regions of said dense partition, said merging sub-step allowing to define a so-called projected
coarse partition, said additional segmentation being preferably a size-oriented one and the size parameter being then progressively decreased until a given homogeneity criterion referring to the gray level homogeneity of the pixels, such as the means
squared error of the pixels with respect to the mean of the regions, is reached.
Another object of the invention is to propose a coding system allowing to implement said coding method. At this end, the invention concerns a system for coding segmented pictures, or partitions, that correspond to a sequence of original pictures
and identify in said pictures contours and closed regions to which corresponding labels are associated, said system comprising a first time motion evolution defining sub-system and a second motion, contour and texture coding sub-system, in which the
coded information to be transmitted and/or stored for each current partition comprises coded signals corresponding to an optimal partition composed either of regions of a main partition determined by a motion estimation and compensation of a previous
partition or of regions of additional partitions created by merging or re-segmenting said regions of the main partition, said coded signals including the appropriate indications on the origin of each region, in the form of merging orders and splitting
information.
According to a preferential implementation, the sub-systems of this coding system are organized in the following manner:
(I) said first sub-system comprises:
(A) a first partition preprocessing sub-assembly, comprising:
(1) a time evolution definition device, comprising:
(a) a motion estimation circuit;
(b) a motion compensation circuit;
(c) a temporal extension circuit, the output of which constitutes a so-called projected partition defining said main partition;
(2) a partition topology definition device, comprising:
(d) at least a merging circuit;
(e) at least a re-segmenting circuit;
the output of said partition topology definition device constituting a partition tree composed of said projected partition and of additional partitions created by said merging and re-segmenting circuits;
(B) a second decision sub-assembly, comprising:
(f) a decision tree construction circuit;
(g) an optimization circuit;
the output of said decision sub-assembly constituting an optimal partition sent to said second coding sub-system, and said optimal partition being obtained by an association of regions from various levels of the partition tree;
(II) said second sub-system comprises:
(C) a third coding sub-assembly, comprising:
(4) a first decision coding device;
(5) a second motion coding device;
(6) a third contour coding device;
(7) a fourth texture coding device;
(8) a multiplexer of the coded output signals of said four coding devices.
In that implementation, said merging circuit may comprise a motion estimation stage and a merging proposition stage, and is followed by a second similar merging circuit, and so on, in order to build the upper levels of said partition tree by
merging from the projected partition neighbouring regions which have a similar motion.
Whatever the implementation, the decision sub-assembly of this coding system is organized in such a manner that said decision tree construction circuit comprises a distortion computation stage, a rate computation stage and a memory, said memory
being provided for storing in the form of a decision tree a list of distortions and a list of rates having both the same length as an associated list of texture coding methods in which a selection is made for the coding operation of the texture of each
region of said partition tree, and said optimization circuit comprises a computing sub-stage, provided for making a local analysis of each node of said decision tree, and a decision sub-stage, provided for defining from the whole set of regions of the
partition tree a final set of the regions that constitute said optimal partition to be coded.
A further object of the invention is also to define a coded signal such as generated by such a coding system, said coded signal consisting of a multiplexed signal comprising:
(A) a coded motion information, corresponding to the estimation of a motion model that characterizes the evolution of the segmentation between said successive partitions and allows to define a so-called projected partition;
(B) a coded partition information, corresponding to texture and contour information of each region of an optimal partition selected, on the basis of rate and distortion criteria, among all the regions of a hierarchy of additional finer and
coarser partitions constructed from the projected partition corresponding to the current one;
(C) a coded decision information, corresponding to the coding strategy defined for each of said selected regions of the projected and additional partitions, according to the coding cost and quality associated to said rate and distortion criteria.
Another object of the invention is to propose a storage medium for storing said coded signal.
Another object of the invention is also to propose a decoding method able to be applied to a multiplexed coded bitstream as yielded at the output of the coding system implementing the previously described coding method. At this end, the
invention concerns a method of decoding signals corresponding to segmented pictures, or partitions, that identify in an associated sequence of original pictures contours and closed regions to which corresponding labels are associated and having been
previously coded by a coding method comprising a first step provided for defining, for each current partition considered with respect to the previous one, on the one hand a so-called projected partition obtained by motion estimation and compensation and
a temporal extension of the compensated partition and on the other hand additional partitions created either by merging or re-segmenting regions of said projected partition, and for selecting an optimal partition composed of regions contained within the
proposals contained in any level of the partition tree formed by said projected and additional partitions, and a second step provided for the definition of the coded information that has to be transmitted and/or stored for each region of each of the
successive optimal partitions.
In accordance with the invention, said decoding method advantageously comprises a first decision decoding step, provided for defining which coding strategy has been previously used for each region of each optimal partition, a second motion
decoding step, a third partition decoding step, and a fourth texture decoding step, and, preferably, said third partition decoding step comprises a first relabelling sub-step, provided for limiting the value of label numbers by reassigning a label value
to each region, only labels 1 to N being used if there are N regions, a second merging sub-step, provided for performing the merging orders, a third intra regions decoding sub-step, a fourth motion-compensation and compensated errors decoding sub-step,
and a decoded compensation errors partition labelling sub-step.
A further object of the invention is finally to propose a decoding system allowing to implement said decoding method. At this end, the invention concerns a system for decoding signals corresponding to segmented pictures, or partitions, that
identify in an associated sequence of original pictures contours and closed regions to which corresponding labels are associated, said signals constituting for each current partition a coded information corresponding to an optimal partition composed
either of regions of a main partition determined by a motion estimation and compensation of a previous partition and a temporal extension of the compensated partition or of regions of additional partitions created by merging or re-segmenting regions of
the main partition, wherein said decoding system comprises an input buffer, provided for storing and demultiplexing said coded information, a decision decoding device, provided for decoding the information corresponding to the strategy used for coding
said optimal partition, a motion decoding device, a partition decoding device, and a texture decoding device.
BRIEF DESCRIPTION OF THE DRAWINGS
These and other aspects of the invention will be apparent from and elucidated with reference to the embodiments described hereinafter and considered in connection with the accompanying drawings, in which:
FIG. 1 is a general representation of a system according to the present invention and FIG. 2 illustrates the corresponding coding method;
FIG. 3 illustrates a time extension operation of the regions;
FIG. 4 illustrates a merging operation;
FIG. 5 illustrates a re-segmentation operation;
FIG. 6 illustrates a decision tree construction operation;
FIG. 7 illustrates how local decisions on the coding strategy are taken;
FIG. 8 illustrates the decision process implemented in order to lead to an optimal partition;
FIG. 9 is a schematic representation of the structure of the decoding device and illustrates the corresponding decoding method;
FIG. 10 is a diagram giving a more detailed illustration of the partition and texture decoding process;
FIG. 11 is an embodiment of the partition decoding device;
FIG. 12 is a very simplified example of a segmented picture;
FIG. 13 is a schematic illustration of a type of motion between two successive pictures P(t-1) and P(t);
FIG. 14 illustrates a possible solution for implementing one of the motion estimation steps carried out during the merging operation of FIG. 4;
FIG. 15 shows local axis and scales for a given region, with a normalizing coefficient equal to two;
FIG. 16 is an illustration of a coding method with a specific type of order estimation.
DETAILED DESCRIPTION OF THE INVENTION
Referring now to FIG. 1, there is illustrated a system comprising three main sub-assemblies. A first partition preprocessing sub-assembly 1, provided for receiving the incoming sequence of segmented frames or pictures S(t-j), . . . , S(t-1),
S(t), S(t+1), . . . (that correspond themselves to original textured images P(t-j), . . . , P(t-1), P(t), P(t+1) . . . ), comprises a time evolution definition device 11 and a partition topology definition device 12. A second decision sub-assembly 2
is provided for receiving a set of partitions generated by said first sub-assembly 1 and defining a coding strategy. A third coding sub-assembly 3, provided for receiving said selected partition and the decision related to the coding strategy in
connection with this selected partition, comprises a decision coding device 31, a motion coding device 32, a partition (or contour) coding device 33, a texture coding device 34, and a multiplexer 35.
The general coding method that the previously cited sub-assemblies implement will now be explained with reference to FIG. 2 and in relation with FIG. 1. A time evolution definition sub-step, carried out in the device 11, is provided to follow
the temporal evolution of the regions of the current partition. In the described example, in order to limit as much as possible both the processing delay and the computational load, only the previous coded picture or frame and its partition at time
(t-1) are used to define the time evolution of the partition at time t. The time evolution definition substep is provided to adapt the partition of a previous frame (of the previous frame S(t-1) in the present case) to the current frame, this partition
of the frame S(t-1) (t-i in a more general case) corresponding to the final partition which has been chosen for the previous picture (after a previous implementation of the coding method according to the invention, the output signals of the coding
devices of the coding sub-assembly 3 are sent back to the first partition preprocessing sub-assembly 1). Said sub-step therefore accommodates the partition of S(t-1) to the data of the picture S(t), without introducing new regions. Such an adaptation
of the partition of the previous frame is performed in three operations. First, a motion estimation operation 111a is carried out between the original frames S(t-1) and S(t). Then the previous partition is motion-compensated (operation 112a), and
finally an extension operation 113a of the previous regions into the current frame is provided.
The first motion estimation operation 111a takes place in a motion estimation circuit 111. The motion is estimated between the preceding frame S(t-1) (a previous frame S(t-j) in the general case) and the next frame S(t) which is going to be
segmented, according for instance to a block-matching process applied backwards. Such a technique is described for example in "A VLSI architecture for hierarchical motion estimation", IEEE Transactions on Consumer Electronics, vol. 41, n.degree.2, May
1995, pp. 248-257: the frame S(t) is divided into small blocks of picture elements (usually 8.times.8 pixels for QCIF format of 176.times.144 pixels) and for each of them a search is conducted within a given window in the frame S(t-1) in order to locate
in that frame a best matching block. The obtained motion information is a sufficient approximation even when the motion of some blocks involving more than one object is not strictly uniform. This motion information is given in the form of motion
vectors respectively estimated for all the blocks of the considered frame.
The second motion compensation operation 112a is carried out in a motion compensation circuit 112, by applying the obtained motion vectors to the regions and in order to obtain as a final result a frame containing, for each region coming from the
previous frame, a connected component with the same label as in said previous frame. Each of these components has been itself obtained in the following manner. If P(t-1) is the previous picture and S(t-1) its partition (or segmented frame, in the form
of a set of labels), every pixel of the current frame will be covered (after the backward motion estimation) by one, and only one, pixel from the previous frame. It is obvious, however, that such a compensation can produce in each compensated partition
small disconnected components, generally close to the contours of the regions. These disconnected parts could produce wrong extensions of the labels and have to be eliminated by way of a cleaning operation keeping from every region in P(t-1) only its
largest connected component in the compensated partition P'(t-1) (this operation produces non labelled pixels in P'(t-1), but it does not involve any problem since this partition is only used as an initialization for the operation 113a that will follow
the operation 112a). The motion compensated partition finally obtained, in which there is at most one connected component per region of P(t-1), marks for each region coming from the previous frame the position of the core of this region in the current
frame.
The third extension operation 113a is implemented in a temporal extension circuit 113, in order to define the boundaries of the regions thus projected from the motion compensated partition. Such an extension of a compensated partition in a
current frame can be performed for instance by using the conventional morphological tool called watershed lines method and described for example in the communication "Time-Recursive Segmentation of Image Sequences", M. Pardas and P. Salembier, EUSIPCO
94, VIIth European Signal Processing Conference, Edinburgh (United Kingdom), Sep. 13, 1994. The above obtained connected components constitute thanks to their specific label identifying the presence of homogeneous regions a set of markers defining the
core of the regions which are going to be extracted. As described in the cited document and after having recalled (with reference to FIG. 3) that P(t-1) and P(t) are the pictures at times (t-1) and t, and that S(t-1) and S(t) are respectively the
already known partition (at time t-1) and the unknown partition (at time t) that has to be determined, two three-dimensional signals are constructed by grouping together the pictures P(t-1) and P(t) to form a temporal block P of size 2 in the temporal
dimension and similarly grouping (in order to form a block S considered as the set of markers that should be used to segment the block P) the partition S(t-1) and an empty frame S(.) representing a frame of uncertainty. Such a frame is so called because
the pixels of this frame do not yet correspond to a given marker.
The implementation of the watershed lines method WM results in a growing process in which these pixels are assigned to a given marker until the markers occupy all the available space of the empty frame, each pixel being assigned to a specific
region because it is in the neighbourhood of the marker of this region and is more similar (in the sense defined by a specific criterion) to the area defined by this marker than to any other area corresponding to another marker in its neighbourhood. A
possible similarity criterion may be for example the gray tone difference D between the pixel under consideration and the mean of the pixels that have already been assigned to this region, or also a modified criterion introducing a weighting factor
"Alpha". This last solution allows now to consider no longer D alone but the weighted sum (Alpha.times.D)+(1-Alpha)C, where C is a penalty term corresponding to a contour complexity obtained for instance by counting the number of contour points that are
added if the considered pixel is assigned to a particular region, and therefore to give more or less importance to the gray level measure or to the contour complexity.
A projected partition PJ(t) is therefore available when the third operation 113a is completed. From this projected partition a partition tree will be built for providing (using motion and texture criteria) different partitions among which the
second decision sub-assembly 2 will later select for coding the picture the most convenient regions, constituting a final partition composed of regions issued from the different levels of the partition tree. This building process is carried out in the
partition topology definition device 12, the aim of which is in fact to create from the projected partition two different kinds of partitions (by a procedure which is purely intra):
partitions which are created by merging regions from the projected partition and which define the upper levels of the partition tree: this merging, based on a motion criterion as it will be explained, allows to obtain greater regions grouping
neighbouring regions that have a similar motion (the internal contours between these neighbouring regions need no longer to be coded);
partitions which are created by re-segmenting the projected partition (providing the possibility of obtaining in the current partition new regions which were not present in the previous one) and which define the lower levels of the partition
tree: the reasons for obtaining these new regions may be the introduction of new objects in the scene (their texture is generally different from that of the neighbouring objects) and or the fact that two regions characterized by a very different texture
but merged because they have a similar motion in a previous frame can suddenly differ in their motion in the current frame, thus leading to a too large compensation error if they continue to be coded using the same motion parameters.
The partition topology definition sub-step thus carried out by the device 12 is performed in two operations: first a merging operation 121a (at least one), secondly a re-segmentation operation 122a (at least one).
The merging operation 121a takes place in a (first) merging circuit 121. Referring to FIG. 4, this circuit 121, the aim of which is to merge neighbouring regions which have a similar motion, comprises a motion estimation stage 1211 and a merging
proposition stage 1212. Given the two original textured pictures P(t-1) and P(t) and the partition S(t-1), the stage 1211 is provided for computing the motion parameters of the projected partition PJ(t) yielded by the device 11. This motion estimation
process returns for each region of the projected partition a set of motion parameters describing the motion of said region between (t-1) and t. The motion estimation step implemented in the stage 1211 may for instance be of the type described in the
french patent application N.degree. 9604194 filed on Apr. 3, 1996, the content of which is recalled in the annex A, at the end of the present description, with reference to FIGS. 12 to 15.
Once the motion parameters of the projected partition are known, the estimation of the cost of merging neighbouring regions is carried out in the merging proposition stage 1212. For every couple of neighbouring regions, a merging cost is
computed, and a required number of merging opportunities is obtained by selecting the couples of neighbouring regions with the smallest merging costs, on the basis of a merging criterion. For instance, two neighbouring regions should be merged if the
cost of coding the prediction error produced when these regions are considered as a single one (i.e., when they are motion compensated with the same set of motion parameters) is smaller than the cost of coding the contour located between them. In fact,
as the coding method is not yet known, the criterion is slightly modified. The compensation error (and no longer the precise coding cost) produced by the merging is taken into account: more precisely, the cost which is considered is the increase of the
mean square compensation error in the merged region with respect to the mean square compensation error when the two regions are compensated separately (in order to simplify the computations, the new motion parameters corresponding to the merged regions
are not computed: the compensation error produced when merging two regions is computed using only one of the two sets of already known motion parameters corresponding to the two regions, the one which produces the smaller compensation error). In the
case of intra frames, the motion is not taken into account for proposing the merging. As the coding does not use any motion information, the merging option is then proposed on a texture basis, the costs being computed by taking into account the
difference of the mean gray level value of the neighbouring regions.
As already said, the coding method is not yet known. The actual decision of merging two regions in terms of coding cost will be definitively taken later, in the decision sub-assembly 2, and several merging proposals may be produced at each
level. As the final merging procedure must be iterated for each level in the partition tree, a merging is however produced and applied as illustrated in FIG. 4 both on the current projected partition and on the partition of the previous image, leading
to merged partitions PM1(t-1) and PM1(t), which constitute the further inputs for a possible repetition of the procedure in a second merging circuit 121b (a further motion estimation in another motion estimation stage 1211b, a further merging proposition
in another merging proposition stage 1212b), and so on for the whole set of upper levels of the partition tree.
In the re-segmentation operation 122a, which takes place in a re-segmenting circuit 122 and must be carried either when new objects appear or when two regions suddenly adopt divergent motions, one needs to separate regions with unhomogeneous
texture. This re-segmentation procedure will therefore be based on a texture criterion. It may be implemented for instance with a hierarchical structure starting from the projected partition and which progressively introduces new regions in the
partition at every level without modifying the contours of the previous levels. This re-segmentation procedure is composed of four steps carried out in corresponding stages: a residue computation stage 1221, a simplification stage 1222, a marker
extraction stage 1223, and a decision stage 1224. As illustrated in FIG. 5, these stages are also respectively designated by the references RC, SP, ME and DC.
Knowing that each level has to improve the segmentation of the previous level by introducing new significant regions, each region of the projected partition is filled with its mean gray level value or with a gray level function such as a
polynomial one. A residue is obtained (in the stage 1221) as the difference between the original picture P(t-1) and the modelled one, the partition S(t-1). An example of such a residue computation by image modelling is for instance described in the
european patent application EP 0627693. The other operations (the simplification, carried out in order to make the partition easier to segment; the marker extraction, carried out in order to detect the presence of homogeneous regions and further
identify their core by labelling of specific zones; the decision, taken in order to deal with the uncertainty areas which have not yet been assigned to any region and correspond to pixels around the region contours) are described in the already cited
document "Time-Recursive Segmentation . . . ", EUSIPCO 94. As for the merging operation, the procedure may be repeated in an iterative manner, a size criterion being used for all the re-segmentation levels except the last one for which a contrast
criterion is used (at each level of this iterative procedure, the only difference is the simplification intensity which is decreased in order to progressively introduce small or low-contrasted regions). Once merging and re-segmentation have been
performed, a motion refinement as described in the cited patent application EP 0627693 is applied for each region of all the partition levels.
As can be seen when the building process in the partition topology definition device 12 is achieved, a partition tree defining a set of possible regions issued from the projected partition has been obtained. The operations which have been
implemented in that device 12 are simply provided in o | | |
