Method and apparatus for determining connected substructures within a body

• US 4,751,643 A
• Filed: 08/04/1986
• Issued: 06/14/1988
• Est. Priority Date: 08/04/1986
• Status: Expired due to Term

• Current Assignee: General Electric Company
• Original Assignee: General Electric Company
• Inventors: Cline, Harvey E., Lorensen, William E.
• Primary Examiner(s): Smith, Jerry
• Assistant Examiner(s): Kibby, Steven G.
• Application Number:
  US06/893,060
• Time in Patent Office: 680 Days
• Field of Search: 378/901, 324/309, 364/414, 340/729, 382/6, 382/22, 382/27
• US Class Current: 382/132
• CPC Class Codes: G06T 17/00 Three dimensional [3D] modelling, e.g. data description of 3D objects
• CPC Class Codes: G06T 2207/10081 Computed x-ray tomography [CT]
• CPC Class Codes: G06T 2207/10088 Magnetic resonance imaging [MRI]
• CPC Class Codes: G06T 2207/20101 Interactive definition of point of interest, landmark or seed
• CPC Class Codes: G06T 2207/30016 Brain
• 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/187 involving region growing; involving region merging; involving connected component labelling
• CPC Class Codes: Y10S 378/901 Computer tomography program or processor

Abstract

An apparatus and method for determining connected substructures within a body is disclosed. The system and method are particularly advantageous for use in medical diagnostic imaging applications. In particular, three dimensional regions exhibiting the same tissue type are similarly labeled. Using the label information together with a seed location located in the substructure of interest, all similarly labeled connected data points are determined. The system and method of the present invention is operable in any situation in which three dimensional signal patterns representing the value of one or more physical properties associated with the substructures within a body at regularly grid locations within the body are presented. A subset of the original data is then provided to a display processor particularly one employing gradient normal shading for display of three dimensional images.

Claims

1. A method for determining, in three dimensions, connected substructures within a body, said method comprising the steps of:

(a) storing, in a memory means, three-dimensional signal patterns representing the value of at least one physical property associated with substructures within said body at regularly spaced parallelopiped grid locations within said body;

(b) labeling said stored signal patterns wherein those signal patterns representing values which lie within a specified range receive a same label;

(c) storing and placing on a memory stack an initial grid location, said grid location corresponding to a position within or on a desired internal substructure of said body;

(d) selecting and removing the grid location from the top of said memory stack;

(e) comparing the label associated with said grid location selected from said memory stack with labels associated with adjacent grid locations to identify grid locations having the same label as said label associated with the grid location from said stack;

(f) marking, as connected, those grid locations for which a selected arrangement of adjacent grid locations exhibit the same label;

(g) storing on said memory stack a list of any of said marked grid locations; and

(h) repeating steps (d), (e), (f) and (g) for a plurality of times not to extend beyond the occurrence of an empty stack.

2. The method of claim 1 further including the step of

(i) selecting those signal pattern values stored in step (a) having grid locations marked as connected in accordance with step (f).

3. The method of claim 2 further including the step of

(j) supplying said selected signal pattern values from step (i) to a display processor for displaying a three-dimensional image of said connected substructure.

4. The method of claim 1 in which, in step (f), said selected arrangement comprises a single 1-connected cell.

5. The method of claim 1 in which, in step (f), said selected arrangement comprises a set of 9-connected cells lying in a plane.

6. The method of claim 1 in which the number of adjacent grid locations is 6.

7. The method of claim 1 in which the number of adjacent grid locations is 26.

8. The method of claim 1 in which steps (d), (e), (f) and (g) are repeated until said memory stack is empty.

9. A method for determining, in three dimensions, connected substructures within a body, said method comprising the steps of:

(a) storing, in a memory means, three-dimensional signal patterns representing the value of at least one physical property associated with substructures within said body at regularly spaced parallelopiped grid locations within said body;

(b) selecting an initial grid location and storing said initial location on a memory stack;

(c) selecting and removing the grid location from the top of said memory stack;

(d) retrieving, from said memory means, a signal pattern value associated with the grid location indicated by the top of said stack, said grid location designated by the top of said stack being referred to as the central grid location, and also retrieving from said memory means signal pattern values associated with grid locations adjacent to said central location;

(e) comparing the signal pattern values of said adjacent grid locations to determine which of said values lie within a specified range;

(f) marking as connected those grid locations with associated values within said range and for which a selected arrangement of adjacent grid locations exhibit values in the same range as said central grid location;

(g) storing on said memory stack a list of any of said marked grid locations; and

(h) repeating steps (d), (e), (f) and (g) for a plurality of times not to extend beyond the occurrence of an empty stack.

10. The method of claim 9 further including the step of

(i) selecting those signal pattern values stored in step (a) having grid locations marked as connected in accordance with step (f).

11. The method of claim 10 further including the step of

(j) supplying said selected signal pattern values from step (i) to a display processor for displaying a three-dimensional image of said connected substructure.

12. The method of claim 9 in which, in step (f), said selected arrangement comprises a single 1-connected cell.

13. The method of claim 9 in which, in step (f), said selected arrangement comprises a set of nine connected grid locations lying in a plane.

14. The method of claim 9 in which the number of adjacent grid locations is 6.

15. The method of claim 9 in which the number of adjacent grid locations is 26.

16. The method of claim 9 in which steps (d), (e), (f) and (g) are repeated until said memory stack is empty.

17. A system for determining, in three dimensions, connected substructures within a body, said system comprising:

memory means for storing three-dimensional signal patterns representing the value of at least one physical property associated with substructures within said body at regularly spaced parallelopiped grid locations within said body;

means for labeling said grid locations wherein those grid locations having signal pattern values which lie within a specified set of range values receive a same label;

memory stack means for storing an initial grid location and subsequent grid locations, the top of said stack thus identifying a central grid location for determination of connectedness thereto;

means for selecting and removing the central grid location from the top of said memory stack;

means for supplying said labels associated with grid locations which are adjacent to the grid locations specified by said memory stack;

means for comparing the labels associated with selected ones of said adjacent grid locations;

means for marking, as connected, those grid locations which exhibit the same label as said grid location associated with the grid location from said stack and for which a selected arrangement of adjacent grid locations exhibit the same label;

means for storing on said memory stack a list of any of said marked grid locations.

18. The system of claim 17 in which said adjacent grid locations are six in number.

19. The system of claim 17 in which said adjacent grid locations are twenty-six in number.

20. The system of claim 17 further including means for selecting signal pattern values associated with said marked grid locations.

21. The system of claim 20 further including display processor means for display of said connected substructure as specified by said selected marked grid locations.

22. The system of claim 17 in which said selected arrangement comprises a single grid location.

23. The system of claim 17 in which said selected arrangement comprises a set of nine grid locations lying in a plane.

24. The system of claim 17 further including means for generating said three-dimensional signal pattern values and for supplying signal patterns representing said values to said memory means.

25. The system of claim 24 in which said generating means includes an x-ray scanner.

26. The system of claim 24 in which said generating means includes a magnetic resonance imaging device.

27. A system for determining in three dimensions, connected substructures within a body, said system comprising:

means for storing three-dimensional signal patterns representing the value of at least one physical property associated with substructures contained within said body at regularly spaced parallelopiped grid locations;

memory stack means for storing an initial grid location and subsequent grid locations the top of said stack thus identifying a central grid location for determination of connectedness thereto;

means for retrieving the signal pattern value associated with the central grid location specified by said memory stack means and the signal pattern values associated with grid locations adjacent to said central grid location as specified by said memory stack;

means for comparing the signal values associated with said central grid location and said adjacent grid locations to determine which of said values lie within the same specified range as said central grid location value;

means for marking, as connected, those grid locations which exhibit values lying in the same range as said central grid location value and for which a selected arrangement of adjacent grid locations also exhibits values lying in the same range as said central grid location value; and

means for storing, on said memory stack, a list of any of marked grid locations.

28. The system of claim 27 in which said adjacent grid locations are six in number.

29. The system of claim 27 in which said adjacent grid locations are twenty-six in number.

30. The system of claim 27 further including means for selecting signal pattern values associated with said marked grid locations.

31. The system of claim 30 further including display processor means for display of said connected substructure as specified by said selected marked grid locations.

32. The system of claim 27 in which said selected arrangement comprises a single grid location.

33. The system of claim 27 in which said selected arrangement comprises a set of nine grid locations lying in a plane.

34. The system of claim 27 further including means for generating said three-dimensional signal pattern values and for supplying signal patterns representing said values to said storing means.

35. The system of claim 34 in which said generating means includes an x-ray scanner.

36. The system of claim 34 in which said generating means includes a magnetic resonance imaging device.