Apparatus and method for labeling connected component in a three-dimensional image

• US 4,991,224 A
• Filed: 10/19/1989
• Issued: 02/05/1991
• Est. Priority Date: 09/03/1986
• Status: Expired due to Fees

• Current Assignee: Kabushiki Kaisha Toshiba (Toshiba Corporation)
• Original Assignee: Kabushiki Kaisha Toshiba (Toshiba Corporation)
• Inventors: Sawada, Nobuo, Takahashi, Kazushige
• Primary Examiner(s): Boudreau, Leo H.
• Assistant Examiner(s): Couso, Jose L.
• Application Number:
  US07/425,400
• Time in Patent Office: 474 Days
• Field of Search: 382/6, 382/9, 382/16, 382/26, 382/27, 382/25, 382/20, 382/45, 382/48, 364/518, 364/521, 377/10, 377/11
• US Class Current: 382/180
• CPC Class Codes: G06T 7/00 Image analysis

Abstract

An apparatus for labeling three-dimensionally connected components in a three-dimensional image is provided. The apparatus includes a two-dimensional labeling processor which labels each connected component in two-dimensional images giving a proper component code, and a coordinate calculator which calculates coordinates of a representative point representing each connected component. The apparatus further includes a connectivity detection processor which checks connectivity of representative points in adjacent two-dimensional image planes and an editing processor which modifies the component codes already provided by the two-dimensional labeling processor using the connectivity information to obtain three-dimensionally labeled image codes.

Claims

1. An apparatus for labeling connected components in a three-dimensional image, comprising:

input means for inputting a plurality of two-dimensional image planes of the three-dimensional image;

first labeling means, coupled to said input means, for labeling each two-dimensionally connected component in each twodimensional image plane, each two-dimensionally connected component including a plurality of pixels, and for generating labeled two-dimensional images in which each connected component is given an independent component code;

image memory means, coupled to the first labeling means, for storing said labeled two-dimensional images; and

second labeling means, coupled to the first labeling means, for three-dimensionally labeling each connected component in said three dimensional image, said second labeling means including;

calculation means for determining a number of representative points for each of said connected components in each two-dimensional plane, said number of representative points being substantially less than the plurality of pixels in a component, and said representative points denoted by coordinates,

detection means for detecting connectivities of the representative points of the connected components between adjacent two-dimensional image planes by comparing the coordinates of said representative points, and

editing means, coupled to said image memory means, for modifying the component code of each connected component in labeled two-dimensional image planes in accordance with the connectivities detected by said detection means.

2. The apparatus according to claim 1, wherein said second labeling means further includes:

coordinate memory means for storing coordinates of the representative points detected by said calculation means, and

connectivity memory means for storing connectivity information derived by said detection means.

3. The apparatus according to claim 2, wherein said connectivity memory means stores at least pairs of connected component codes which are detected as having connectivity to each other by said detection means.

4. The apparatus according to claim 2, wherein said editing means includes:

first means for determining three-dimensionally labeled component codes for each connected component from the connectivity information stored in said connectivity memory means, and

second means coupled to said image memory means for replacing the two-dimensionally labeled component codes by the three-dimensionally labeled component codes determined by said first means.

8. The apparatus according to claim 1 wherein said calculation means determines one representative point for each of said connected components, each of said representative points corresponding to one of said connected components.

9. The apparatus according to claim 8 where each of said representative points is a center of gravity of the corresponding connected component.

10. The apparatus according to claim 8 where each representative point is a geometric center of the corresponding connected component.

5. A method for labeling connected components in a three-dimensional image, comprising the steps of:

(a) inputting a plurality of two-dimensional image planes of three-dimensional objects;

(b) two-dimensionally labeling each two-dimensionally connected component in each two-dimensionally image plane, wherein each connected component is given a different component code, and wherein each connected component includes a plurality of pixels;

(c) calculating coordinates of exactly one representative point for each connected component;

(d) detecting connectivity information of connected components in adjacent two-dimensional image planes by comparing coordinates of the representative points corresponding to the adjacent two-dimensional image planes; and

(e) modifying the component codes of connected components in accordance with the connectivity information.

6. The method according to claim 5, wherein step (d) comprises the steps of:

reading out coordinates corresponding to one of the representative points included in a two-dimensional image plane as a first representative point;

reading out coordinates corresponding to one of the representative points included in an adjacent two-dimensional image plane as a second representative point; and

judging the connectivity of said first and second representative points by comparing their coordinates.

7. A method for labeling connected components in a three-dimensional image, comprising the steps of:

(a) inputting a first two-dimensional image plane of three-dimensional objects;

(b) labeling each two-dimensionally connected components in the two-dimensional image plane being inputted by step (a), wherein each connected component is given a different component code, and wherein each connected component includes a plurality of pixels;

(c) calculating coordinates of a representative point for each connected component in a coordinate memory;

(d) storing the coordinates of the representative point for each connected component in a coordinate memory;

(e) repeating steps (a) through (d) for every twodimensional image plane of the three-dimensional objects;

(f) detecting connectivity information of connected components in adjacent two-dimensional image planes by comparing coordinates of the representative points stored in the coordinate memory corresponding to the adjacent two-dimensional image planes; and

(g) modifying component codes of connected components in accordance with the connectivity information to replace the two-dimensionally labeled component codes by three-dimensionally labeled component codes.