Method for segmenting a video image into elementary objects

• US RE42,977 E1
• Filed: 09/06/2001
• Issued: 11/29/2011
• Est. Priority Date: 09/07/2000
• Status: Expired due to Term

• Current Assignee: Gula Consulting Limited Liability Company (Intellectual Ventures LLC)
• Original Assignee: Gula Consulting Limited Liability Company (Intellectual Ventures LLC)
• Inventors: Chassaing, Françoise, Maziere, Magali, Sanson, Henri
• Primary Examiner(s): Vo; Tung
• Application Number:
  US12/355,565
• Time in Patent Office: 3,736 Days
• Field of Search: 375/240.16, 375/240.1, 348/234, 348/236, 348/419.1, 348/416.1, 382/234, 382/236
• US Class Current: 375/240.16
• CPC Class Codes: G06K 2209/05 Recognition of patterns in medical or anatomical images
• CPC Class Codes: G06K 9/6207 based on a local optimisation criterion, e.g. "snakes", i.e. active contour models of the pattern to be recognised
• CPC Class Codes: G06T 2207/10016 Video; Image sequence
• CPC Class Codes: G06T 2207/20104 Interactive definition of region of interest [ROI]
• CPC Class Codes: G06T 2207/20116 Active contour; Active surface; Snakes
• CPC Class Codes: G06T 2207/30196 Human being; Person
• CPC Class Codes: G06T 7/12 Edge-based segmentation
• CPC Class Codes: G06T 7/149 involving deformable models, e.g. active contour models

Abstract

A starting contour is defined surrounding around an elementary object delimited by a natural contour in a video image. On the basis of the starting contour, an original active contour is defined, formed by a set of nodes distributed on this starting contour, each node being formed by a point belonging to this starting contour and by an elastic energy function representative of the distance separating this node from a neighbouring node. With regards to a set of reference values representative of the contour of this object, the active contour is subjected to a convergent deformation under a blocking condition, by displacing at least one of the nodes of the original active contour toward the natural contour of the elementary object to generate a current active contour iteratively subjected to this convergent deformation.

Claims

1. A method for segmenting a video image based on elementary objects, comprising, with regard to at least one elementary object delimited by a natural contour of the video image, the steps of:

defining, around the elementary object, a starting contour arbitrarily and completely surrounding said elementary object;

defining, on the basis of said starting contour, an original active contour, formed by a set of nodes distributed on the starting contour, each node being formed by a point belonging to the starting contour and by an elastic energy function representative of the distance separating the node from a neighbouring node;

subjecting, with regard to a set of reference values representing the natural contour of said elementary object, said original active contour to a convergent deformation, by displacing toward the natural contour of the elementary object at least one of the nodes of the original active contour, so as to generate a current active contour, the current active contour being subjected iteratively to said convergent deformation to generate distinct successive current active contours as long as said displacement satisfies the non-blocking condition and in halting any nodal displacement of said current active contour otherwise, generating a final current active contour substantially reproducing the natural contour of said elementary object.

2. The method as claimed in claim 1, wherein the set of nodes of each active contour is defined by polygonal modeling by sampling over the trace of the active contour as a function of the distance between consecutive nodes, thereby adapting the resolution of definition of each of the successive active contours.

3. The method as claimed in claim 1, wherein said convergent deformation comprises:

in calculating at each of the nodes of the current active contour a vector normal to the active contour;

in subjecting at least one of the nodes of said active contour to a centripetal displacement in the direction of said normal vector associated with said node.

4. The method as claimed in claim 1, wherein said set of reference values comprises a set of values of image intensity gradient, calculated over said active contour.

5. The method as claimed in claim 1, comprising, for said elementary object being constituted by an animate object in the image, which animate object is capable of motion, of deformation and of partition, for any active contour capable of constituting a loop exhibiting at least one point of intersection subsequent to a partition of said elementary object into components of elementary objects, the steps of:

detecting the existence on said active contour of at least one intersection;

splitting/grouping said active contour into a number of distinct active contours equal to the number of intersections plus one unit, thereby assigning a final active contour to each component of said elementary object.

6. The method as claimed in claim 1, comprising, for said elementary object being constituted by an animate object moving in the image, for at least two successive video images, the steps of:

defining on each final active contour of each image a band, forming a ring, encompassing the set of nodes belonging to said active contour;

performing between points of said ring an estimation of motion of the elementary object from the image to the next image, thereby defining a motion vector over the nodes of said active contour; and

applying, at each node of said active contour, said motion vector, to the next image, thereby tracking the moving elementary object by said final active contour and discriminating said moving elementary object having regard to the motion of the latter.

7. The method as claimed in claim 6, comprising, with the aim of refining the segmentation of the image, subsequent to the estimation of the motion of the ring of the active contour, the steps of:

displacing each node of the active contour by the value of the estimated motion so as to generate an initial active contour for the new image;

dilating the initial active contour, by geometrical transformation, so as to generate a reference initial active contour for the new image, said reference initial active contour constituting an original active contour of the object; and

iteratively recommencing the convergent deformation of said original active contour, so as to generate said final current active contour.

8. A protocol for searching for an elementary object of interest in a sequence of images stored in a database accessible on a server site, from a terminal for access to the server site, the access terminal being furnished with a sample consisting of at least one sample video image emanating from the sequence of images, comprising the steps of:

segmenting said sample video image following the method which is the subject of the present invention according to claim 1, so as to generate at least one sample active contour constituted by a list of nodes associated with said elementary object of interest belonging to the sample video image;

transmitting said list of nodes from said terminal for access to said server site;

segmenting at least one current image of said sequence of images stored in said database following the method according to claim 1, so as to generate at least one reference active contour; and

comparing, by comparison of similarity, said sample active contour with said reference active contour and, on comparison of similarity, stopping the search so as to ensure the transmission of all or part of said sequence of stored images to said access terminal, and continuing the search over every image following said current image in said sequence of stored images otherwise.

9. The protocol as claimed in claim 8, furthermore comprising the steps of:

discriminating, in said object of interest, sample object component attributes such as color, texture, motion parameters, in said sample video image;

transmitting said object component attributes from said access terminal to said server site;

discriminating, in the object delimited by said reference active contour, reference object component attributes of the same type as those of the sample object component attributes; and

comparing the reference object component attributes and the sample object component attributes so as to instruct the stoppage, respectively the continuation of the search.

10. A method of segmenting a video image based on elementary objects, wherein at least one elementary object is delimited by a natural contour of the video image, the method comprising:

defining by a computing device, around the elementary object, a starting contour arbitrarily and completely surrounding said elementary object;

defining by the computing device, on the basis of said starting contour, an original active contour, formed by a set of nodes distributed on the starting contour, each node being formed by a point belonging to the starting contour and by an elastic energy function representative of the distance separating the node from another node of the set of nodes; and

subjecting by the computing device, with regard to a set of reference values representing the natural contour of said elementary object, said original active contour to a convergent deformation, by displacing toward the natural contour of the elementary object at least one of the nodes of the original active contour, so as to generate a current active contour, the current active contour being subjected iteratively to said convergent deformation to generate distinct successive current active contours as long as said displacement satisfies a non-blocking condition and in halting any nodal displacement of said current active contour otherwise, generating a final current active contour substantially reproducing the natural contour of said elementary object.

11. The method of claim 10, wherein the set of nodes of each active contour is defined by polygonal modeling by sampling over a trace of the active contour as a function of the distance between consecutive nodes, thereby adapting a resolution of definition of each of the successive active contours.

12. The method of claim 10, wherein subjecting a contour to a convergent deformation comprises:

calculating at each of the nodes of an active contour a vector normal to the current active contour;

subjecting at least one of the nodes of the active contour to a centripetal displacement in the direction of said normal vector associated with said node.

13. The method of claim 10, wherein said set of reference values comprises a set of values of image intensity gradient (GR).

14. The method of claim 13, wherein the video image comprises an elementary zone including a horizontal number of pixels and a vertical number of pixels, wherein each particular pixel includes a coordinate (i, j), wherein i is a horizontal coordinate of the particular pixel and j is a vertical coordinate of the particular pixel, wherein the GR satisfies at least the following equations:

I_x(i,j)=(I(i+1, j)−

I(i−

1, j))/2

I_y(i,j)=(I(i, j+1)−

I(i,j−

1))/2

wherein I(i+1,j) is an intensity of a pixel adjacent to the particular pixel on one side in a horizontal direction, I(i−

1,j) is an intensity of a pixel adjacent to the particular pixel on another side in the horizontal direction, I(i, j+1) is an intensity of a pixel adjacent to the particular pixel on one side in a vertical direction, I(i, j−

1) is an intensity of a pixel adjacent to the particular pixel on another side in the vertical direction, I_x(i,j) is a value of the GR in the horizontal direction, and I_y(i,j) is a value of the GR in the vertical direction.

15. The method of claim 14, wherein a Norm N of the GR is given by the following equation:

N=Square Root[I_x²(i,j)+I_y²(i,j)].

16. The method of claim 10, wherein said elementary object constitutes an animate object in the image, which animate object is capable of motion, of deformation and of partition, for any active contour capable of constituting a loop exhibiting at least one point of intersection subsequent to a partition of said elementary object into components of elementary objects, and the method further comprises:

detecting by the computing device, existence on a current active contour of at least one intersection; and

splitting, by said computing device, a current active contour into a number of distinct active contours equal to the number of intersections plus one unit, thereby assigning a final active contour to each component of said elementary object.

17. The method of claim 10, wherein said elementary object constitutes an animate object in the image, moving for at least two successive video images, and the method further comprises:

defining by the computing device, on each final active contour of each image, a band forming a ring and encompassing the set of nodes belonging to the final active contour;

performing by the computing device, between points of said band an estimation of motion of the elementary object from the image to a next video image, thereby defining a motion vector over the nodes of the final active contour; and

applying by the computing device, at each node of the final active contour, said motion vector, to the next video image, thereby tracking the moving elementary object by the final active contour and discriminating said moving elementary object having regard to the motion of the elementary object.

18. The method of claim 17, further comprising refining by the computing device the segmentation of the image, subsequent to the estimation of the motion of the ring of the final active contour, the refining comprising:

displacing by the computing device, each node of the final active contour by the value of the estimated motion so as to generate an initial active contour for the new image;

dilating by the computing device, the initial active contour, by geometrical transformation, so as to generate a reference initial active contour for the new image, said reference initial active contour constituting an original active contour of the object; and

iteratively performing the convergent deformation of said original active contour, so as to generate a final current active contour for the new image.

19. An apparatus configured to segment a video image based on elementary objects, wherein at least one elementary object is delimited by a natural contour of the video image, the apparatus comprising:

a processor; and

a data store coupled to the processor, and having stored therein computer-implemented application programs that if executed by the processor, cause the apparatus to perform the following actions;

defining, around the elementary object, a starting contour arbitrarily and completely surrounding said elementary object;

defining, on the basis of said starting contour, an original active contour, formed by a set of nodes distributed on the starting contour, each node being formed by a point belonging to the starting contour and by an elastic energy function representative of the distance separating the node from another node of the set of nodes; and

subjecting, with regard to a set of reference values representing the natural contour of said elementary object, said original active contour to a convergent deformation, by displacing toward the natural contour of the elementary object at least one of the nodes of the original active contour, so as to generate a current active contour, the current active contour being subjected iteratively to said convergent deformation to generate distinct successive current active contours as long as said displacement satisfies a non-blocking condition and in halting any nodal displacement of said current active contour otherwise, generating a final current active contour substantially reproducing the natural contour of said elementary object.

20. The apparatus of claim 19, wherein said elementary object constitutes an animate object in the image, which animate object is capable of motion, of deformation and of partition, for any active contour capable of constituting a loop exhibiting at least one point of intersection subsequent to a partition of said elementary object into components of elementary objects, and wherein the programming instructions if executed, further cause the apparatus to perform following actions:

detecting existence on an active contour of at least one intersection; and

splitting the active contour into a number of distinct active contours equal to the number of intersections plus one unit, thereby assigning a final active contour to each component of said elementary object.

21. The apparatus of claim 19, wherein said elementary object constitutes an animate object in the image, moving for at least two successive video images, and wherein the programming instructions if executed, further cause the apparatus to perform following actions:

defining on each final active contour of each image a band, forming a ring, encompassing the set of nodes belonging to the final active contour;

performing between points of said ring an estimation of motion of the elementary object from the image to a next video image, thereby defining a motion vector over the nodes of the final active contour; and

applying, at each node of said active contour, said motion vector, to the next video image, thereby tracking the moving elementary object by the final active contour and discriminating said moving elementary object having regard to the motion of the elementary object.

22. An article of manufacture comprising:

non-transitory computer-readable media; and

instructions encoded thereon and configured to cause an apparatus, when the instructions are executed by a processor of the apparatus, to segment a video image based on elementary objects, wherein at least one elementary object delimited by a natural contour of the video image, and wherein segmenting a video image includes;

defining, around the elementary object, a starting contour arbitrarily and completely surrounding said elementary object;

defining, on the basis of said starting contour, an original active contour, formed by a set of nodes distributed on the starting contour, each node being formed by a point belonging to the starting contour and by an elastic energy function representative of the distance separating the node from another node of the set of nodes; and

subjecting, with regard to a set of reference values representing the natural contour of said elementary object, said original active contour to a convergent deformation, by displacing toward the natural contour of the elementary object at least one of the nodes of the original active contour, so as to generate a current active contour, the current active contour being subjected iteratively to said convergent deformation to generate distinct successive current active contours as long as said displacement satisfies a non-blocking condition and in halting any nodal displacement of said current active contour otherwise, generating a final current active contour substantially reproducing the natural contour of said elementary object.

23. The article of claim 22, wherein said elementary object constitutes an animate object in the image, which animate object is capable of motion, of deformation and of partition, for any active contour capable of constituting a loop exhibiting at least one point of intersection subsequent to a partition of said elementary object into components of elementary objects, and wherein the programming instructions when executed by the processor of the apparatus, further cause the apparatus to perform following actions:

detecting existence on an active contour of at least one intersection; and

splitting the active contour into a number of distinct active contours equal to the number of intersections plus one unit, thereby assigning a final active contour to each component of said elementary object.

24. The apparatus of claim 22, wherein said elementary object constitutes an animate object in the image, moving for at least two successive video images, and wherein the programming instructions when executed by the processor of the apparatus, further cause the apparatus to perform following actions:

defining on each final active contour of each image a band, forming a ring, encompassing the set of nodes belonging to the final active contour;

performing between points of said ring an estimation of motion of the elementary object from the image to a next video image, thereby defining a motion vector over the nodes of the final active contour; and

applying, at each node of said active contour, said motion vector, to the next video image, thereby tracking the moving elementary object by the final active contour and discriminating said moving elementary object having regard to the motion of the elementary object.

25. A system configured to segment a video image based on elementary objects, wherein at least one elementary object is delimited by a natural contour of the video image, the system comprising:

means for defining, around the elementary object, a starting contour arbitrarily and completely surrounding said elementary object;

means for defining, on the basis of said starting contour, an original active contour, formed by a set of nodes distributed on the starting contour, each node being formed by a point belonging to the starting contour and by an elastic energy function representative of the distance separating the node from another node of the set of nodes; and

means for subjecting, with regard to a set of reference values representing the natural contour of said elementary object, said original active contour to a convergent deformation by displacing toward the natural contour of the elementary object at least one of the nodes of the original active contour, so as to generate a current active contour, the current active contour being subjected iteratively to said convergent deformation to generate distinct successive current active contours as long as said displacement satisfies a non-blocking condition and in halting nodal displacement of said current active contour otherwise, generating a final current active contour substantially reproducing the natural contour of said elementary object.