US5768413A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and apparatus for segmenting images using stochastically deformable contours
Assignee: Arch Development Corp
•
Filing: 1995-10-04
•
Granted: 1998-06-16
•
Expires: 2015-10-04
Abstract
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.
Inventors
- 👤 David N. Levin
- 👤 Robert P. Grzeszczuk
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-27 07:56
CPC Classifications
G; G06; G06T; G06T7/00; G06T7/10; G06T7/149; G06T7/12; G06T7/143; G06T2207/00; G06T2207/10; G06T2207/10072; G06T2207/10088; G06T2207/30; G06T2207/30004; G06T2207/30016; G06T2207/30048
Claims Analysis
Total Claims: 40
Claim 1
Independent Claim
424 words
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.
Claim 2
Independent Claim
424 words
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.
Claim 3
Dependent Claim
37 words
The method according to claim 1 wherein the predetermined statistical properties of the training objects represent image intensities of a plurality of pixels, said pixels being within a predetermined distance from the contour of the training objects.
Claim 4
Dependent Claim
34 words
The method according to claim 1 wherein the predetermined statistical properties of the evolving contour represent image intensities of a plurality of pixels, said pixels being within a predetermined distance from the evolving contour.
Claim 5
Dependent Claim
32 words
The method according to claim 1 wherein the predetermined statistical properties of the training objects and the evolving contour represent intrinsic geometric properties of the training objects and the evolving contour, respectively.
Claim 6
Dependent Claim
36 words
The method according to claim 4 wherein the intrinsic properties of the training objects and the evolving contour include properties selected from the group consisting of tortuosity, smoothness, circularity, shape and area enclosed by the contours.
Claim 7
Dependent Claim
45 words
The method according to claim 1 wherein the imaging system is selected from the group of imaging systems consisting of MR scanners, CAT scanners, X-ray scanners, PET scanners, particle-beam imaging systems, radar systems, infra-red systems, sonar systems, ultrasound scanners, photographic systems and camera imaging systems.
Claim 8
Dependent Claim
48 words
The method according to claim 1 wherein the step of obtaining said predetermined statistical properties of the training objects includes the step of creating a histogram representing image intensities of the plurality of pixels, said pixels being within a predetermined distance of the contour of the training objects.
Claim 9
Dependent Claim
34 words
The method according to claim 1 wherein the step of creating an initial evolving contour includes the step of randomly creating a closed contour if the target object is represented by a closed contour.
Claim 10
Dependent Claim
35 words
The method according to claim 1 wherein the step of creating an initial evolving contour includes the step of randomly creating a bounded line segment if the target object is represented by a line segment.
Claim 11
Dependent Claim
37 words
The method according to claim 1 wherein the step of deriving the energy function of the evolving contour includes the step of creating a histogram representing image intensities of the plurality of pixels defining the training object.
Claim 12
Dependent Claim
15 words
The method according to claim 10 wherein said predetermined distance is a single pixel distance.
Claim 13
Dependent Claim
17 words
The method according to claim 10 wherein said predetermined distance is less than a ten pixel distance.
Claim 14
Dependent Claim
25 words
The method according to claim 1 wherein the step of determining whether to accept or reject the deformations is performed according to a Boltzman function.
Claim 15
Dependent Claim
44 words
The method according to claim 1 wherein the step of determining whether to accept or reject the deformations is performed at a temperature selected between a predetermined high temperature and a predetermined low temperature, said temperature controlling a probability that the deformation is accepted.
Claim 16
Dependent Claim
25 words
The method according to claim 14 wherein the step of determining whether to accept or reject the deformations is initially performed at the high temperature.
Claim 17
Dependent Claim
30 words
The method according to claim 14 wherein the step of determining whether to accept or reject the deformations is iteratively performed as the temperature is lowered at a predetermined rate.
Claim 18
Dependent Claim
35 words
The method according to claim 14 wherein the step of determining whether to accept or reject the deformations performed at the high temperature permits about between 65% and 95% of the deformations to be accepted.
Claim 19
Dependent Claim
32 words
The method according to claim 17 wherein the step of determining whether to accept or reject the deformations performed at the high temperature permits about 80% of the deformations to be accepted.
Claim 20
Dependent Claim
31 words
The method according to claim 1 wherein the step of repeating steps (h)-(m) is performed such that said predetermined fraction of said predetermined number of deformations is less than about 5.0%.
Claim 21
Dependent Claim
31 words
The method according to claim 1 wherein the step of repeating steps (h)-(m) is performed such that said predetermined fraction of said predetermined number of deformations is less than about 0.5%.
Claim 22
Dependent Claim
52 words
The method according to claim 10 wherein the step of calculating the value of the energy function includes the step of creating a histogram representing image intensities of the plurality of pixels within an image of the target object, said plurality of pixels being within a predetermined distance from the evolving contour.
Claim 23
Dependent Claim
32 words
The method according to claim 14 wherein the step of determining whether to accept or reject the deformations is iteratively performed at a temperature that is lowered according to an exponential rate.
Claim 24
Dependent Claim
284 words
The method according to claim 1 wherein the step of applying the deformation generator includes 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 locations of 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, each said deposited pixel 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.
Claim 25
Dependent Claim
30 words
The method according to claim 23 wherein each crack of the evolving contour represents a boundary between pixels of an image of the target object that border the evolving contour.
Claim 26
Dependent Claim
24 words
The method according to claim 23 wherein the step of selecting a crack along the evolving contour is performed according to a random function.
Claim 27
Dependent Claim
30 words
The method according to claim 23 wherein the step of depositing the predetermined number of single pixels includes the step of depositing about between one and six hundred single pixels.
Claim 28
Dependent Claim
34 words
The method according to claim 23 wherein the step of depositing the predetermined number of single pixels includes the step of depositing the single pixels within the bounding area according to a random function.
Claim 29
Dependent Claim
25 words
The method according to claim 23 wherein the step of assigning the first direction and second direction is made randomly according to a predetermined distribution.
Claim 30
Dependent Claim
43 words
The method according to claim 23 wherein the step of assigning the first direction and the second direction includes the step of assigning at least one of said first direction and said second direction to all of the predetermined number of single pixels.
Claim 31
Dependent Claim
50 words
The method according to claim 23 wherein the step of assigning the first direction and the second direction includes the step of assigning the first direction to a portion of the predetermined number of pixels and assigning the second direction to a remainder of the predetermined number of single pixels.
Claim 32
Dependent Claim
34 words
The method according to claim 23 wherein the predetermined rules for traversing the crack diagram permit said crack diagram to divide the target image into a connected outside region and a connected inside region.
Claim 33
Dependent Claim
46 words
The method according to claim 23 wherein the predetermined rules for traversing the crack diagram permit each crack of the crack diagram to be traversed only once, permit a continuous traversal path from said starting point to said ending point and prevent a self-intersecting traversal path.
Claim 34
Dependent Claim
28 words
The method according to claim 23 wherein the step of updating the crack diagram includes the step of eliminating cracks from the crack diagram that are not traversed.
Claim 35
Dependent Claim
245 words
The method according to claim 1 wherein the step of applying the deformation generator includes the steps of: (a) creating a plurality of loop contours, each said loop contour defined by an perturbative crack array, the perturbative crack array having cracks, each said crack being connected to any other crack in the perturbative crack array by at least two different sets of connected cracks within the perturbative crack array; (b) creating a crack diagram representing the evolving contour, each crack of said crack diagram representing an image pixel boundary in an image the target object; (c) selecting a crack along the evolving contour; (d) selecting at least one loop contour; (e) depositing the at least one selected loop contour on the selected crack along the evolving contour; (f) performing a logical OR operation to combine cracks of the crack diagram representing the evolving contour with the cracks of the perturbative crack array defining the loop contour; (g) determining the location of the intersections where the evolving contour intersects the loop contour to define a starting point where the evolving contour enters the loop contour, and an ending point where the evolving contour exits the loop contour; and (h) traversing the crack diagram from the starting point to the ending point and updating the crack diagram according to predetermined rules to form an updated crack diagram such that the traversed cracks are merged into the evolving contour, said updated crack diagram representing a modified evolving contour.
Claim 36
Dependent Claim
28 words
The method according to claim 34 wherein the at least one loop contour is selected from a library of stored loop contours selected according to a random function.
Claim 37
Dependent Claim
67 words
The method according to claim 34 wherein the step of traversing the crack diagram includes the step of traversing the crack diagram according to one of at least first and second predetermined traversal rules, said traversal according to said first predetermined traversal rule forming an outcropping in the evolving contour, and said traversal according to said second predetermined traversal rule forming an indentation in the evolving contour.
Claim 38
Dependent Claim
41 words
The method according to claim 34 wherein the predetermined rules permit each crack of the crack diagram to be traversed only once, permit a continuous traversal path from the starting point to the ending point and prevent a self-intersecting traversal path.
Claim 39
Independent Claim
310 words
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.
Claim 40
Independent Claim
310 words
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.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2001-06-15 | 2001-12-15 | 2002-06-16 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2005-06-15 | 2005-12-15 | 2006-06-16 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2009-06-15 | 2009-12-15 | 2010-06-16 | $7700.00 | Window Closed / Lapsed |