Three dimensional connectivity system employing an equivalence schema for determining connected substructures within a body

• US 4,791,567 A
• Filed: 09/15/1986
• Issued: 12/13/1988
• Est. Priority Date: 09/15/1986
• Status: Expired due to Term

• Current Assignee: General Electric Company
• Original Assignee: General Electric Company
• Inventors: Cline, Harvey E., Ludke, Siegwalt, Lorensen, William E.
• Primary Examiner(s): Smith, Jerry
• Assistant Examiner(s): Hayes, Gail O.
• Application Number:
  US06/907,333
• Time in Patent Office: 820 Days
• Field of Search: 364/414, 364/521-533, 364/512, 582/16, 582/27, 340/728, 378/901
• US Class Current: 345/424
• CPC Class Codes: G06T 17/00 Three dimensional [3D] modelling, e.g. data description of 3D objects
• 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. 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 spaced grid locations within the body are presented. A subset of the original data may then be provided to a display processor, particularly one employing gradient normal shading for display of three dimensional images. Even more particularly, the present invention is related to a method and system for determining equivalence classes of objects, the objects typically comprising one or two dimensional connected regions found in a planar slice of data from magnetic resonance imaging or x-ray tomography systems.

Claims

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

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

(b) selecting signal pattern values, from said memory means, which are associated with slices through said body;

(c) determining connectivity of two-dimensional substructures within each slice independently of connectivity in other slices, said connectivity being indicated by ordered indicia associated with distinct planar substructures;

(d) determining connectivity of said two-dimensional substructures between adjacent slices, said connectivity being indicated in a pair list of connected substructures;

(e) permuting a list of said ordered indicia in a memory means in accordance with said pair list, said permutation being carried out only for those pairs which are not already indicated as being connected;

(f) determining from said permuted list those two-dimensional substructures which are connected.

2. A method for determining equivalence classes of labeled objects from a list of pairs of related objects within a set of such objects, said method comprising the steps of:

storing in sequentially accessible memory locations a set of ordered indicia which are in one to one correspondence with said labels as specified in said list of object pairs;

switching in said memory locations, pairs of ordered indicia corresponding to labels sequentially selected from said list of pairs;

marking, with a first class indicia, those locations in said memory which contain the same ordered indicia as were present prior to said switching step;

accessing from said memory an ordered indicia which has not been marked with a class indicia;

determining from said unmarked ordered indicia a set of related indicia;

marking said memory locations corresponding to said set of related indicia with an indicia corresponding to a next class.

3. The method of claim 2 further including the step of repeating said previous steps of accessing, determining and marking until each of said memory locations is marked with a class indicia.

4. The method of claim 2 in which said determining of a set of related indicia comprises the following steps:

accessing a memory location specified by said ordered indicia to determine a next memory location address, as specified by the ordered indicia in said next memory location;

accessing a memory location with said next memory address;

repeating said previous step until the ordered indicia obtained is the same as an ordered indicia which has been previously obtained.