Image segmentation and object tracking method and corresponding system

• US 6,130,964 A
• Filed: 02/05/1998
• Issued: 10/10/2000
• Est. Priority Date: 02/06/1997
• Status: Expired due to Term

• Current Assignee: Uniloc 2017 LLC (SoftBank Group Corp.)
• Original Assignee: US Philips Corporation (Koninklijke Philips N.V.)
• Inventors: Molina, Cristina, Marques, Ferran
• Primary Examiner(s): Tadayan, Bijan
• Assistant Examiner(s): Bayat, Ali
• Application Number:
  US09/018,984
• Time in Patent Office: 978 Days
• Field of Search: 382/103, 382/154, 382/173, 382/100, 382/174, 382/248, 382/101, 382/236-243, 382/107-141, 348/413, 348/416, 348/118, 348/172, 348/401-412
• US Class Current: 382/236
• CPC Class Codes: G06T 2207/10016 Video; Image sequence
• CPC Class Codes: G06T 2207/20016 Hierarchical, coarse-to-fine, multiscale or multiresolution image processing; Pyramid transform
• CPC Class Codes: G06T 7/11 Region-based segmentation
• CPC Class Codes: G06T 7/174 involving the use of two or more images
• CPC Class Codes: G06T 7/215 Motion-based segmentation
• CPC Class Codes: H04N 19/70 characterised by syntax aspects related to video coding, e.g. related to compression standards

Abstract

This relates to a method for image segmentation and video object tracking. While conventional methods rely on the motion homogeneity of the objects to be tracked, the present method is based on a concept of partition projection in which both spatial and motion information are now exploited, and implemented by means of a modified double partition approach, including a re-segmentation of a first partition followed by a projection step of the obtained fine partition into the current frame. Objects presenting non-homogeneous motion, static objects, and parts of an object with homogeneous motion can thus be tracked.

Claims

1. An object tracking method applied to an image sequence, said method comprising in series the following steps:

(A) a segmentation step for defining the regions of a first coarse partition P(t-1) of an image I(t-1), said regions corresponding to the objects to be tracked, and, from said coarse partition P(t-1) and on the basis of a spatial homogeneity criterion, a finer partition FP(t-1);

(B) a projection step for defining a projection PFP(t) of said fine partition FP(t-1) into the current image I(t);

(C) a re-labelling step of said projected fine partition PFP(t), for defining the final partition P(t);

wherein said projection step comprises in series the following sub-steps;

(1) a marker projection sub-step, provided for yielding on the basis of motion and spatial information a set of markers for the current image, said marker projection sub-step itself comprising in series the following operations;

(a) based on a motion estimation operation between the images I(t-1) and I(t), a backwards motion compensation operation of the fine partition FP(t-1), yielding a compensated fine partition CFP(t-1) made of so-called compensated markers;

(b) in said compensated fine partition, a component selection operation, provided for selecting, among the possible unconnected components that correspond to a single label of the coarse partition P(t-1) and have the same label, only the components that, for each of these specific labels, satisfy a predetermined spatial criterion;

(2) a partition creation sub-step, by means of a growing process of said set of compensated markers in order to obtain said final partition.

2. A method according to claim 1, wherein said partition creation sub-step itself comprises in series the following operations:

(c) a marker re-labelling operation, provided for re-labelling, when several markers have been created from a single region of the fine partition FP(t-1), all the markers except one;

(d) a growth operation of all selected markers in the current image I(t) by means of a tridimensional extended watershed algorithm, leading to the projected fine partition PFP(t);

(e) a merging operation of the regions of said projected fine partition PFP(t) that, having the same label in the previous image, are connected after the region growing, for defining the final partition P(t).

3. A method according to claim 2, wherein said marker projection sub-step also comprises in series:

(c) a cleaning operation based on the gradient of the compensated markers;

(d) a boundary removal operation;

these two operations being applied in order to ensure the gray level homogeneity of the projected markers while preserving their homotopy.

4. A method according to claim 1, wherein said motion estimation operation is a backwards block-matching process, provided for ensuring that, after the compensation operation, every pixel in the current image I(t) has assigned one and only one pixel from the coarse partition P(t-1).

5. A method according to claim 1, wherein, during said component selection operation, an unconnected component with a given label k is selected if it contains at least a given percentage of all pixels with the same label k in the compensated fine partition CFP(t-1).

6. A method according to claim 5, wherein said percentage is about 40%.

7. A method according to claim 1, wherein, for each of said compensated markers, the mean value of the gradient of the pixels that said marker covers is computed, all pixels that are above a given threshold over said mean value being also assigned to a so-called uncertainty area surrounding the compensated markers and already including the non-selected components.

8. A method according to claim 7, wherein, for each marker re-labelling operation, a second mean value is calculated using the pixel values of the region in the previous image I(t-1) and the values of the pixels covered by said marker.

9. A system for an object tracking applied to partitions, resulting from a segmentation of images, of an image sequence, each partition P(t-1) determining in corresponding image I(t-1) regions that define the objects to be tracked and leading after a refined segmentation to a finer partition FP(t-1), said system comprising the serial arrangement of a projection stage, for defining a projection PFP(t) of said fine partition FP(t-1) into the current image I(t), and a re-labelling stage, for defining from said projection fine partition PFP(t) the current partition P(t), wherein said projection stage comprises:

(a) a motion estimation circuit, for carrying out a motion estimation between the images I(t-1) and I(t);

(b) a motion compensation circuit, for defining, on the basis of said motion estimation applied to said fine partition FP(t-1), a compensated fine partition CFP(t-1) made of so-called compensated markers;

(c) a component selection circuit, for selecting, among possible unconnected components that correspond to a single label of the partition P(t-1) and have the same label, only the components that, for each of the specific labels satisfying a predetermined spatial criterion;

(d) a partition creation device, for finally defining said current partition P(t) by means of a growing process of the compensated markers.

10. A system according to claim 9, further comprising in series between the component selection circuit and the partition creation device, a cleaning circuit, provided to ensure the grey level homogeneity of the projected markers while preserving homotopy.