Method and apparatus for segmenting images using stochastically deformable contours
First Claim
1. A method for segmenting images by identifying the boundary of a target object, said boundary having a contour, the method comprising the steps of:
- (a) selecting a plurality of training objects with contours having predetermined statistical properties in common with predetermined statistical properties of the contour of the target object;
(b) placing each said training object in a position to be scanned by an imaging system;
(c) scanning each of the training objects to obtain said predetermined statistical properties of the contours of the training objects;
(d) deriving an energy function from said predetermined statistical properties of the contours of the training objects;
(e) selecting a target object to be scanned and placing said target object in a position to be scanned by the imaging system;
(f) creating an initial evolving contour having an initial topology similar to a topology of the target object;
(g) calculating a value of the energy function of the evolving contour in a neighborhood of the target object, utilizing the predetermined statistical properties of the evolving contour;
(h) deforming the evolving contour by applying a deformation generator;
(i) calculating a value of the energy function of the evolving contour utilizing the predetermined statistical properties of the evolving contour in the neighborhood of the target object after the evolving contour has been deformed, said energy function having a low energy value when the statistical properties of the evolving contour are similar to the statistical properties of the contour of the training object, and having a high energy value when the statistical properties of the evolving contour are not similar to the statistical properties of the contour of the training object;
(j) comparing the value of the energy function of the evolving contour before and after the evolving contour has been deformed, respectively;
(k) accepting the deformations of the evolving contour if the value of the energy function after said deformation is lower than the value of the energy function before said deformation;
(l) determining whether to accept or reject the deformations of the evolving contour if the value of the energy function after said deformation is not lower than the value of the energy function before said deformation, said rejection of the deformations causing the deformations not to be merged into the evolving contour;
(m) merging said accepted deformations into the evolving contour;
(n) repeating steps (h)-(m) until less than a predetermined fraction of a predetermined number of deformations generated by said deformation generator are accepted; and
(o) using the evolving contour to identify the boundary of the target object.
1 Assignment
0 Petitions
Accused Products
Abstract
A method for segmenting an image in which an arbitrarily shaped contour is deformed stochastically until it approximates the contour of a target object. The evolution of the contour is controlled by a simulated annealing process which causes the contour to settle into a global minimum of an image-derived "energy" function. The non-parametric energy function is derived from the statistical properties of previously-segmented training images. High computational complexity is avoided by using an efficient method of introducing a random local perturbation, and assuring the resulting shape changes are unbiased. This method for perturbing the contour allows for execution times several orders of magnitude shorter than in simple implementations.
-
Citations
38 Claims
-
1. A method for segmenting images by identifying the boundary of a target object, said boundary having a contour, the method comprising the steps of:
-
(a) selecting a plurality of training objects with contours having predetermined statistical properties in common with predetermined statistical properties of the contour of the target object; (b) placing each said training object in a position to be scanned by an imaging system; (c) scanning each of the training objects to obtain said predetermined statistical properties of the contours of the training objects; (d) deriving an energy function from said predetermined statistical properties of the contours of the training objects; (e) selecting a target object to be scanned and placing said target object in a position to be scanned by the imaging system; (f) creating an initial evolving contour having an initial topology similar to a topology of the target object; (g) calculating a value of the energy function of the evolving contour in a neighborhood of the target object, utilizing the predetermined statistical properties of the evolving contour; (h) deforming the evolving contour by applying a deformation generator; (i) calculating a value of the energy function of the evolving contour utilizing the predetermined statistical properties of the evolving contour in the neighborhood of the target object after the evolving contour has been deformed, said energy function having a low energy value when the statistical properties of the evolving contour are similar to the statistical properties of the contour of the training object, and having a high energy value when the statistical properties of the evolving contour are not similar to the statistical properties of the contour of the training object; (j) comparing the value of the energy function of the evolving contour before and after the evolving contour has been deformed, respectively; (k) accepting the deformations of the evolving contour if the value of the energy function after said deformation is lower than the value of the energy function before said deformation; (l) determining whether to accept or reject the deformations of the evolving contour if the value of the energy function after said deformation is not lower than the value of the energy function before said deformation, said rejection of the deformations causing the deformations not to be merged into the evolving contour; (m) merging said accepted deformations into the evolving contour; (n) repeating steps (h)-(m) until less than a predetermined fraction of a predetermined number of deformations generated by said deformation generator are accepted; and (o) using the evolving contour to identify the boundary of the target object. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37)
-
-
38. A method for segmenting images by identifying the boundary of a target object, said boundary having a contour, said contour approximated by an evolving contour having an initial topology similar to a topology of the target object, the method comprising the steps of:
-
(a) creating a crack diagram representing the evolving contour, each crack of said crack diagram representing an image pixel boundary in an image of the target object; (b) selecting a crack along the evolving contour; (c) defining a bounding area encompassing the selected crack and a portion of the evolving contour; (d) determining the location of the intersections where the evolving contour intersects the bounding area to define a starting point where the evolving contour enters the bounding area, and to define an ending point where the evolving contour exits the bounding area; (e) depositing a predetermined number of single pixels within the bounding area, said deposited pixels represented by four deposited bounding cracks in the crack diagram; (f) assigning at least one of a first direction and a second direction to each deposited pixel, said assignment of the first direction defining a pixel region, said assignment of the second direction defining a pixel hole; (g) traversing the crack diagram according to predetermined rules from the starting point to the ending point, and selecting deposited cracks connected to the evolving contour; (h) modifying the evolving contour by merging the selected deposited cracks with the crack diagram representing the evolving contour to form an indentation in the evolving contour if the deposited pixels are defined to be pixel holes; (i) modifying the evolving contour by merging the selected deposited cracks with the crack diagram representing the evolving contour to form an outcropping in the evolving contour if the deposited pixels are defined to be pixel regions; and (j) updating the crack diagram to represent the modified evolving contour.
-
Specification