Image object matching using core analysis and deformable shape loci

• US 5,926,568 A
• Filed: 06/30/1997
• Issued: 07/20/1999
• Est. Priority Date: 06/30/1997
• Status: Expired due to Term

• Current Assignee: Duke University, North Carolina University of At Chapel Hill
• Original Assignee: Duke University, University of North Carolina At Chapel Hill (University of North Carolina System)
• Inventors: Chaney, Edward L., Fritsch, Daniel S., Wilson, Alyson G., Johnson, Valen, Pizer, Stephen M.
• Primary Examiner(s): Boudreau, Leo H.
• Assistant Examiner(s): CAGE, SHAWN B
• Application Number:
  US08/885,330
• Time in Patent Office: 750 Days
• Field of Search: 382/217, 382/218, 382/128, 382/199, 382/159, 382/130, 382/173, 128/922
• US Class Current: 382/217
• CPC Class Codes: G06T 2207/10072 Tomographic images
• CPC Class Codes: G06T 2207/20044 Skeletonization; Medial axis transform
• CPC Class Codes: G06T 2207/30016 Brain
• CPC Class Codes: G06T 2207/30056 Liver; Hepatic
• CPC Class Codes: G06T 7/344 involving models
• CPC Class Codes: G06T 7/35 using statistical methods
• CPC Class Codes: G06V 10/754 involving a deformation of the sample pattern or of the reference pattern; Elastic matching

Abstract

Methods, systems, and computer program products are provided for automatic image recognition of standard shapes which include a core-based deformable loci skeletal grid used to define and represent an object via a model template. The template includes deformable segments, the changes of which are measurable against the deformed model corresponding to an object in a subsequent image. Statistical correlation techniques optimize the match to further refine the shape of the subsequent image.

Claims

1. A method for producing a representation of object shape by establishing a shape hierarchy recognition pattern based on the shape of an object in a digital reference, comprising the steps of:

(a) defining a medial axis along a dimension of the object, the medial axis having a plurality of medial sites there along;

(b) generating a plurality of medial to medial ("MM") link segments defined by adjacent medial sites;

(c) generating opposing first and second boundary sites for each of said medial sites, wherein said first and second boundary sites are separated by said medial axis;

(d) generating a plurality of medial to boundary ("MB") link segments each MB segment defined by a respective one of said first and second boundary sites and a corresponding one of said medial sites;

(e) generating a plurality of boundary to boundary ("BB") link segments defined by adjacent boundary sites; and

(f) generating an object shape template for the object based on said medial sites, said boundary sites, said MM links, said MB links, and said BB links.

2. A method according to claim 1, wherein said object includes a parent figure and at least one subfigure, and said template represents the parent figure and the subfigure, said method further comprising the step of:

(g) generating at least one figure to figure ("FF") link segment corresponding to each identified subfigure, said FF link being connected to a selected site of the parent figure.

3. A method according to claim 1, further comprising the step of determining a width component associated with variation of width of the object along said medial axis.

4. A method according to claim 3, wherein a user inputs selected core information to the computer and the medial axis and the associated width components are automatically generated by a computer.

5. A method according to claim 4, wherein said width is determined by optimizing medialness and determining local boundariness measurements.

6. A method according to claim 4, wherein said automatic generation of the medial axis and associated width components determine corresponding boundary sites.

7. A method according to claim 1, further comprising the step of accepting user input for generating said target shape.

8. A method according to claim 2, further comprising the step of accepting user input to establish the figure to figure link segments.

9. A method according to claim 2, wherein the object shape template is a model template from a reference image, the method further comprising the step of (h) measuring the correspondence of the model template to a second digital image (the target image) having at least one object (the target object) therein.

10. A method according to claim 9, further comprising the steps of:

(i) calculating a medialness value corresponding to a medial site wherein the medialness value corresponds to the value used to determine the correspondence of both position and width at the medial site with data associated with the target image; and

(ii) calculating a boundariness value corresponding to a boundary site, using a scale proportional to the scale of the linked medial site wherein the boundariness value is used to determine the correspondence of the position at the boundary site with the target image data.

11. A method according to claim 9, further comprising the step of deforming said model template to match the shape of the target object and analyzing the deformed model template with the model template.

12. A method according to claim 11, wherein said analyzing step comprises extracting a sum of medialness and boundariness measurements corresponding to sites in the representation of the object in the target image.

13. A method according to claim 10, the method further comprises the steps of:

deforming the model template to match the object in the target image;

measuring agreement of the deformed template with an object in the target image; and

analyzing the difference in the model links in the deformed template with those of the model template to recognize and segment the target object in the target image.

14. A method according to claim 13, wherein said analyzing step includes the step of generating a penalty value, wherein the penalty value corresponds to a measure of deformation of the deformed template, such that the greater the deformation, the higher the penalty value.

15. A method according to claim 13, further comprising the step of analyzing in predetermined order selected subsets of said sites to optimize the objective function.

16. A method according to claim 9, further comprising the steps of:

identifying an object represented by the model template;

extracting the identified object from a target image; and

refining the boundary interpolated through the boundary sites of the identified object.

17. A method according to claim 11, wherein at least two images are registered based on said object template generated from a reference image and its geometric transformation into the target image.

18. A method according to claim 11, wherein points are computed on a boundary contour defined by said linked boundary sites, and wherein said contour is interpolated based on these computed boundary points.

19. A method according to claim 18, further comprising the steps of displaying the object representation template on a 3D display so as to render a depiction of an object, wherein the surface contour further uses the intersection of view rays through each screen pixel which locates a boundary point along a line generated by an imaging beam orthogonal to the surface at each point.

20. A method according to claim 13, further comprising the step of extracting measures of shape, shape anomaly, and shape sequence anomaly according to changes in orientation, length, and width of said links.

27. A method according to claim 20, wherein variation of said target image object relative to said first image object generates a poor correlation value which corresponds to progression of a disease.

21. A method for synthesizing objects in computer graphics by producing a representation of an object shape by establishing a figural shape hierarchy recognition pattern based on the shape of a target object having a plurality of subfigures therein, comprising the steps of:

(a) defining a medial axis along a dimension of a target figure, the medial axis having a plurality of medial sites there along;

(b) generating a plurality of medial to medial ("MM") link segments defined by adjacent medial sites;

(c) generating an object template based on said medial sites, and said MM link segments;

(d) designing objects, using a successively developed figural hierarchy, defined by successive decrease of spacing of sites in each figure'"'"'s representation, wherein points are computed on a boundary contour relative to said linked medial sites, and wherein said contour is interpolated based on these computed boundary points with each figure in this hierarchy associated with an image to be rendered and graphically displayed; and

(e) morphing said object from a first beginning position to a second end position by interpolation of said medial sites in the figures held in common between the beginning and end positions of the object being morphed.

22. A method according to claim 21, wherein said synthesizing method is used to physically model successively higher resolution images based on the hierarchical approach of step (d) and wherein said morphed objects are displayed at successively higher resolution based on the hierarchical approach of step (d).

23. A method for automatic registration or segmentation of anatomical features for radiation therapy or diagnostic evaluation, comprising the steps of:

generating a first digital image of a predetermined anatomical region of the body;

defining a model template of a desired object within said first image using scale-space relationships, said model template including a skeletal grid defining relational deformable shape loci and links, including a medial axis, a contour boundary shape, MM links, MB links, and BB links;

generating an unclassified target digital image of a desired region in a patient'"'"'s body;

applying said model template to said unclassified image to automatically find the corresponding object in said unclassified target image;

allowing said template deformable shape loci and links to deform to match the contour and core of said corresponding object in said unclassified target image;

determining relational measurements associated with said model template and said target object shape; and

correlating measurements associated with said model template and said target object to determine at least one of registration and segmentation of said target image.

24. A method according to claim 23, wherein said defining step accepts user input to define the object of interest in the training image.

25. A method according to claim 23, wherein poor correlation between said target object shape and said template indicates a set-up error.

26. A method according to claim 23, wherein said first image and said target image are generated from the same patient.

28. A method according to claim 23, wherein said first image and said unclassified image are both portal images, and wherein registration between the two quantitatively indicates field positioning errors.

29. A computer program product for object recognition employing a deformable loci skeletal grid representation pattern, said computer program product comprising:

computer usable medium having computer readable program code means embodied in said medium, said computer-readable program code means comprising;

computer readable program code means for causing said computer to generate a skeletal grid shape representation pattern corresponding to a preselected object, said grid including a plurality of medial sites, a plurality of boundary sites, a plurality of medial to medial links joining adjacent medial sites, a plurality of medial to boundary links joining a selected medial site with a corresponding boundary site, and a plurality of boundary to boundary links joining adjacent boundary sites; and

computer readable program code means for allowing said links in said grid to be deformed for subsequent matching to a similarly shaped object.

30. A computer program product for object representation according to claim 29, wherein said computer readable program code means further includes computer readable program code means for causing said computer to represent subfigural objects within said object and relationally link said represented subfigural objects to said skeletal grid.

31. A system for generating a representation of object shape by establishing a shape hierarchy recognition pattern based on the shape of a target object in a digital reference, comprising:

means for defining a medial axis along a dimension of a target figure, the medial axis having a plurality of medial sites there along;

means for generating a plurality of medial to medial ("MM") link segments defined by adjacent medial sites;

means for generating opposing first and second boundary sites for each of said medial sites, wherein said first and second boundary sites are separated by said medial axis;

means for generating a plurality of medial to boundary ("MB") link segments each MB segment defined by a respective one of said first and second boundary sites and a corresponding one of said medial sites;

means for generating a plurality of boundary to boundary ("BB") link segments defined by adjacent boundary sites; and

means for generating an object template based on said medial sites, said boundary sites, said MM links, said MB links, and said BB links.