Method for automatic segmentation of image data from multiple data sources

• US 6,947,590 B2
• Filed: 08/03/2001
• Issued: 09/20/2005
• Est. Priority Date: 08/04/2000
• Status: Expired due to Fees

• Current Assignee: Canon Kabushiki Kaisha (Canon Inc.)
• Original Assignee: Canon Kabushiki Kaisha (Canon Inc.)
• Inventors: Parker, Brian John, Magarey, Julian Frank Andrew
• Primary Examiner(s): Couso, Yon J.
• Assistant Examiner(s): Hung, Yubin
• Application Number:
  US09/920,958
• Publication Number:
  US 20020041710A1
• Time in Patent Office: 1,509 Days
• Field of Search: 382/162, 382/164, 382/171, 382/173, 382176-180, 382/191, 382/225, 382226-228
• US Class Current: 382/164
• CPC Class Codes: G06T 2207/10016 Video; Image sequence
• CPC Class Codes: G06T 7/11 Region-based segmentation
• CPC Class Codes: G06T 7/162 involving graph-based methods
• CPC Class Codes: G06T 7/187 involving region growing; involving region merging; involving connected component labelling
• CPC Class Codes: G06V 10/267 by performing operations on regions, e.g. growing, shrinking or watersheds

Abstract

A method (300) and apparatus (400) is described for segmenting an image (102). Starting with each pixel of the image (102) being a separate region, segments are formed by merging the regions. As merging proceeds, a merging cost of the regions being merged generally increases. This increase however is not purely monotonic as the overall rise in the merging cost is punctuated by departures from monotonicity. A complete pass is made through the segmentation, in which all regions are merged until only one remains. By analysing the points immediately after significant departures from monotonicity, a final segmentation stopping value (λ_stop) is chosen as being the last return to monotonicity from such a significant departure. Segmentation is repeated until the merging cost reaches the final segmentation stopping value (λ_stop).

Claims

1. A method of segmenting an image formed by a plurality of pixels, each pixel being described by a vector having components each relating to a different measured image characteristic, said method comprising the steps of:

(a) receiving, for each pixel, a plurality of the vector components and a corresponding error covariance representation of that pixel;

(b) for each pixel, fitting each component and the corresponding covariance representation to a predetermined linear model to obtain a set of model parameters and corresponding confidence representations;

(c) defining the pixels each to be initial regions of the image;

(d) merging the regions in a statistical order using the sets of model parameters and confidence representations to obtain a null segmentation of the image;

(e) analysing a curve formed using the model parameters and corresponding confidence representations to determine an optimal halting criterion at which to cease the merging of the regions; and

(f) processing said merging of the initial regions to halt when the optimal halting criterion is reached.

2. A method according to claim 1, wherein step (f) comprises re-executing the merging of the initial regions using said model parameters and confidence representations, and halting when said optimal halting criterion is reached.

3. A method according to claim 1, wherein sub step (e) comprises identifying returns to monotonicity from local minima in the curve and selecting a predetermined the return approaching the null segmentation as the optimal halting criterion.

4. A method according to claim 3, wherein step (f) comprises re-executing the merging of the initial regions using the model parameters up until the predetermined return is reached.

5. A method according to claim 1, wherein the statistical order is determined using an order of minimum covariance-normalised vector distance between adjacent regions of the segmentation.

6. A method according to claim 1, wherein the statistical order is determined using a length of a common boundary between adjacent regions.

7. A method according to claim 1, wherein the statistical order is determined by dividing a covariance-normalised vector distance between adjacent regions of the segmentation by a length of a common boundary between adjacent regions, and ordering the resulting quotients.

8. A method according to claim 7, wherein each quotient forms a test statistic, a record of which is retained at each merging step to form the curve.

9. A method according to claim 1, wherein the plurality of vector components comprise at least two of colour, range and motion.

10. A method according to claim 9, wherein the colour vector component comprises at least one colour channel of a colour space in which the image can be reproduced.

11. A method for unsupervised selection of a stopping point for a region-merging segmentation process, said method comprising the steps of:

(a) analysing a graph of merging cost values to identify departures from substantial monotonicity of the graph; and

(b) selecting the stopping point to be a merging cost value corresponding to a return to monotonicity of the graph, the selected stopping point being associated with one of a limited plurality of final ones of the departures in the region merging process.

12. A method according to claim 11, wherein the selected stopping point corresponding to a return associated with the final departure.

13. A method according to claim 11, wherein the departures are larger than a predetermined threshold.

14. A method according to claim 11, wherein the merging cost values comprise an ordered series of test statistics, each test statistic being formed, for each adjacent pair of regions in the segmented image, by dividing a covariance-normalised vector distance between the pair by a length of a common boundary between the pair.

15. Apparatus for segmenting an image formed by a plurality of pixels, each pixel being described by a vector having components each relating to a different measured image characteristic, said apparatus comprising:

means for receiving, for each pixel, a plurality of the vector components and a corresponding error covariance representation of that pixel;

means for fitting, for each pixel, each component and the corresponding covariance representation to a predetermined linear model to obtain a set of model parameters and corresponding confidence representations;

defining means for defining the pixels each to be initial regions of the image;

merging means for merging the regions in a statistical order using the sets of model parameters and confidence representations to obtain a null segmentation of the image;

curve analysing means for analysing a curve formed using the model parameters and corresponding confidence representations to determine an optimal halting criterion at which to cease the merging of the regions; and

processing means for processing the merging of the initial regions to halt when the optimal halting criterion is reached.

16. Apparatus according to claim 15, wherein said processing means comprises means for re-executing the merging of the initial regions using the model parameters and confidence representations, and halting when the optimal halting criterion is reached.

17. Apparatus according to claim 15, wherein said curve analysing means comprises means for identifying returns to monotonicity from local minima in the curve and means for selecting a predetermined the return approaching the null segmentation as the optimal halting criterion.

18. Apparatus according to claim 17, wherein said processing means comprises means for re-executing the merging of the initial regions using the model parameters up until the predetermined return is reached.

19. Apparatus according to claim 15, wherein the statistical order is determined using an order of minimum covariance-normalised vector distance between adjacent regions of the segmentation.

20. Apparatus according to claim 15, wherein the statistical order is determined using a length of a common boundary between adjacent regions.

21. Apparatus according to claim 15, wherein the statistical order is determined by dividing a covariance-normalised vector distance between adjacent regions of the segmentation by a length of a common boundary between adjacent regions, and ordering the resulting quotients.

22. Apparatus according to claim 21, wherein each quotient forms a test statistic, a record of which is retained at each merging to form the curve.

23. Apparatus according to claim 15, wherein the plurality of vector components comprise at least two of colour, range and motion.

24. Apparatus according to claim 23, wherein the colour vector component comprises at least one colour channel of a colour space in which the image can be reproduced.

25. Apparatus for unsupervised selection of a stopping point for a region-merging segmentation process, said apparatus comprising:

means for analysing a graph of merging cost values to identify departures from substantial monotonicity of the graph; and

means for selecting the stopping point to be a merging cost value corresponding to a return to monotonicity of graph, the selected stopping point being associated with one of a limited plurality of final ones of the departures in the region merging process.

26. Apparatus according to claim 25, wherein the selected stopping point corresponds to a return associated with the final departure.

27. Apparatus according to claim 25, wherein the departures are larger than a predetermined threshold.

28. Apparatus according claim 25, wherein the merging cost values comprise an ordered series of test statistics, each test statistic being formed, for each adjacent pair of regions in the segmented image, by dividing a covariance-normalised vector distance between the pair by a length of a common boundary between the pair.

29. A program for making a computer execute a procedure to segment an image formed by a plurality of pixels, each pixel being described by a vector having components each relating to a different measured image characteristic, said program comprising:

code for receiving, for each pixel, a plurality of the vector components and a corresponding error covariance representation of that pixel;

code for, for each pixel, fitting each component and the corresponding covariance representation to a predetermined linear model to obtain a set of model parameters and corresponding confidence representations;

code for defining the pixels to each be initial regions of the image;

code for merging the regions in a statistical order using the sets of model parameters and confidence representations to obtain a null segmentation of the image;

code for analysing a curve formed using the model parameters and corresponding confidence representations to determine an optimal halting criterion at which to cease the merging of the regions; and

code for processing the merging of the initial regions to halt when the optimal halting criterion is reached.

30. A program for making a computer execute a procedure for unsupervised selection of a stopping point for a region-merging segmentation process, said program comprising:

code for analysing a graph of merging cost values to identify departures from substantial monotonicity of the graph; and

code for selecting the stopping point to be a merging cost value corresponding to a return to monotonicity of the graph, the selected stopping point being associated with one of a limited plurality of final ones the departures in the region merging process.

31. A program according to claim 30, wherein the selected stopping point corresponding to a return associated with the final departure.

32. A program according to claim 30, wherein the departures are larger than a predetermined threshold.

33. A program according to claim 30, wherein the merging cost values comprise an ordered series of test statistics, each test statistic being formed, for each adjacent pair of regions in the segmented image, by dividing a covariance-normalised vector distance between the pair by a length of a common boundary between the pair.