Image processing device suitable for obtaining the volume and center of gravity of a three-dimensional binary image

• US 4,975,973 A
• Filed: 05/25/1988
• Issued: 12/04/1990
• Est. Priority Date: 05/30/1987
• Status: Expired due to Fees

• Current Assignee: Kabushiki Kaisha Toshiba (Toshiba Corporation)
• Original Assignee: Kabushiki Kaisha Toshiba (Toshiba Corporation)
• Inventors: Inoue, Yoichi, Kasano, Akira
• Primary Examiner(s): Moore, David K.
• Assistant Examiner(s): Razavi, Michael
• Application Number:
  US07/198,442
• Time in Patent Office: 923 Days
• Field of Search: 382/18, 382/23, 382/28, 358/107, 358/88, 356/1, 356/379, 356/380, 356/372, 364/564, 364/560, 364/570, 364/521
• US Class Current: 382/168
• CPC Class Codes: G06T 2207/10081 Computed x-ray tomography [CT]
• CPC Class Codes: G06T 2207/20021 Dividing image into blocks, subimages or windows
• CPC Class Codes: G06T 7/62 of area, perimeter, diameter or volume
• CPC Class Codes: G06T 7/66 of image moments or centre of gravity

Abstract

A first memory stores a divided three-dimensional binary image as image data j of p bits. A second memory, equal to the first memory in size, stores data k of q bits, representing the section number of a corresponding memory section of the first memory. A histogram computing circuit concatenates data j and data k and obtains a histogram for the concatenated data. A computing unit computes a marginal distribution of the three-dimensional image on the basis of the histogram. A data conversion unit converts the p bit data to a first data image. An adder unit obtains from the first image a second image representing the marginal distribution P(x,y). The computing unit computes a marginal distribution P(x) and a marginal distribution P(y) from the second image, and also computes the volume and center of gravity of the three-dimensional binary image.

Claims

1. An image processing device for obtaining the volume and center of gravity of a three-dimensional binary image, comprising:

first frame memory means having a storage capacity of (M×

m) bits in an x direction, (N×

n) bits in a y direction, and p bits in a z direction, for storing image data of p bits in each (x, y) coordinate position, said first frame memory means being logically divided into m equal parts in the x direction and n equal parts in the y direction to form 0-th through (m×

n-1)-th memory sections, and said 0-th through (m×

n-1)-th memory sections respectively storing 0-th through (m×

n-1) th divided three-dimensional binary image parts obtained by dividing a three-dimensional binary image composed of M pixels in the x direction, N pixels in the y direction, and (m×

n×

p) pixels in the z direction by a unit of p pixels in the z direction;

second frame memory means having a storage capacity of (M×

m) bits in the x direction and (N×

n) bits in the y direction, and storing in each (x, y) coordinate position thereof data of q bits representing the section number of the section to which the same (x, y) coordinate position of said first frame memory means belongs;

histogram computing means for concatenating p-bit data in each (x, y) coordinate position of said first frame memory means and q-bit data in the same (x, y) coordinate position of said second frame memory means with the p-bit data taken as lower data and the q-bit data as upper data, and obtaining a histogram representing a distribution of the number of pieces of the concatenated (p+q)-bit data having an equal value;

first marginal distribution computing means for computing a marginal distribution of said three-dimensional binary image for the z direction thereof, on the basis of the histogram obtained by said histogram computing means;

data conversion means for converting the p-bit data stored in each (x, y) coordinate position of said first frame memory means to the number of bits having a logic 1 contained in the p-bit data, to form a first image;

adding means for dividing the first image obtained by said data conversion means into m equal parts and n equal parts in the x and y directions, respectively, to form (m×

n) partial images, and adding image data located in the same relative position in the (m×

n) partial images, to obtain a second image;

second marginal distribution computing means for computing a marginal distribution P(x) and a marginal distribution P(y) of said three-dimensional binary image for the x and y directions thereof, on the basis of the second image;

volume computing means for computing the volume of the three-dimensional binary image on the basis of either of the three marginal distributions P(x), P(y), and P(z); and

center of gravity computing means for computing the position of the center of gravity of the three-dimensional binary image, on the basis of the volume computed by said volume computing means and the marginal distributions P(x), P(y), and P(z).

2. An image processing device according to claim 1, wherein said data conversion means comprises:

a data conversion table having memory areas assigned addresses, and storing in each of said memory areas the number of bits of a logic 1 contained in the address assigned thereto;

addressing means for addressing said data conversion table by use of the p-bit data stored in each (x, y) coordinate position of said first memory means; and

reading means for reading the value stored in a memory area addressed by said addressing means of said data conversion table, and storing it in the corresponding (x, y) coordinate position thereof.

3. An image processing device according to claim 1, wherein said adding means divides said first image into two images of equal size, with M pixels in the x direction and N pixels in the y direction taken as a minimum unit;

adds image data in substantially the same positions in the two images of equal size;

obtains a third image formed of image data resulting from addition; and

repeatedly performs the division and addition, using the third image as a new first image, until the third image becomes M pixels in the x direction and N pixels in the y direction in size, the finally obtained third image of M pixels in the x direction and N pixels in the y direction in size being made the second image.

4. An image processing device according to claim 1, wherein said first marginal distribution computing means obtains the marginal distribution P(z) for the z direction, in accordance with the following equation:

##EQU6## where k is a memory section number, j is p-bit image data, hst(2^p×

k+j) is a histogram of concatenated data specified by the value k and data j, and J(i) is the set of the p-bit image data in which the i-th bit is a logic 1.

5. An image processing device according to claim 1, wherein said histogram computing means comprises:

table memory means for storing the histogram;

means for producing the concatenated data while updating the (x, y) coordinate position in sequence;

means for addressing said table memory means by use of the concatenated data; and

means for incrementing by one the count value stored in a memory area of said table memory means designated by the concatenated data.

6. An image processing device according to claim 1, wherein said second marginal distribution computing means computes the marginal distribution P(x) for the x direction and the marginal distribution P(y) for the y direction, in accordance with the following equations:

##EQU7## where nx is the number of pixels in the x direction and ny is the number of pixels in the y direction of the three-dimensional binary image, and P(x, y) is the marginal distribution image represented by image data in the (x, y) coordinate position of the second image.

7. An image processing device according to claim 6, wherein said volume computing means obtains the volume in accordance with the following equation:

##EQU8## where nz is the number of pixels of the three-dimensional binary image in the z direction.

8. An image processing device according to claim 7, wherein said volume computing means obtains the coordinates of the center of gravity in accordance with the following equations:

##EQU9##

9. An image processing device for obtaining the volume and center of gravity of a three-dimensional binary image formed of M pixels, N pixels, and (m×

n×

p) pixels in x, y, and z directions, comprising;

0-th through (m=n-1)-th memory means each having a storage capacity of M bits, N bits, and p bits in the directions of x, y and z coordinate axes, said 0-th through (m×

n-1)-th memory means respectively storing 0-th through (m×

n-1)-th divided three-dimensional binary images obtained by dividing the three-dimensional binary image by a unit of p pixels in the direction of z coordinate axis;

histogram computing means for obtaining a histogram representing a distribution of the number of concatenated data of an equal value, the concatenated data consisting of (p+q)-bit data having as lower data thereof p-bit data in each (x, y) coordinate position of said 0-th through (m×

n-1)-th memory means, and as upper data thereof, q-bit data representing the memory number of a memory having the p-bit data;

first marginal distribution computing means for computing the marginal distribution of the three-dimensional binary image for its z coordinate axis, on the basis of the histogram computed by said histogram computing means;

data conversion means for converting the p-bit data in each (x, y) coordinate position of said 0-th through (m×

n-1)-th memory means to data representing the number of bits of a logic 1 contained in the p-bit data;

means for adding, among the conversion data obtained by said conversion means, conversion data in positions which are the same in the relative address position, to obtain a marginal distribution P(x, y) image of the three-dimensional binary image;

means for obtaining a marginal distribution in the x direction and a marginal distribution in the y direction by using the marginal distribution image;

volume computing means for computing the volume V of the three-dimensional binary image by using one of the marginal distributions P(x), P(y), and P(z); and

center of gravity computing means for computing the position in coordinates of the center of gravity of the three-dimensional binary image by using the volume V computed by said volume computing means and the marginal distributions P(x), P(y), and P(z).

10. An image processing device according to claim 9, wherein said 0-th through (m×

n-1)-th memory means is formed by logically dividing said first memory means into m equal parts in the x direction and n equal parts in the y direction, which has a storage capacity of (M×

m) bits in the x direction, (N×

n) bits in the y direction, and p bits in the z direction; and

wherein said histogram computing means comprises

second frame memory means having a storage capacity of (M×

m) bits in the x direction and (N×

n) bits in the y direction, for storing, in each (x, y) coordinate position, q-bit data representing the number of said 0-th to (m×

n-1)-th memory means to which the same (x, y) coordinate position of said first memory means belongs; and

means for concatenating the p-bit data in each (x, y) coordinate position of said first frame memory means and the q-bit data in the same (x, y) coordinate position of said second frame memory means, with the p-bit data as lower data and the q-bit data as upper data, to generate concatenated data, and obtaining a histogram of the concatenated data for all the (x, y) coordinate positions.

11. An image processing device according to claim 9, wherein said histogram computing means comprises:

table memory means for storing the histogram;

means for producing the concatenated data while updating the (x, y) coordinate position in sequence;

means for addressing said table memory means by use of the concatenated data; and

means for incrementing by one the count value stored in a memory area of said table memory means designated by the concatenated data.

12. An image processing device according to claim 9, wherein said conversion means comprises:

a data conversion table having memory areas assigned addresses, for storing in each of said memory areas the number of bits of a logic 1 contained in the address assigned thereto;

means for addressing said data conversion table by use of the p-bit data stored in each (x, y) coordinate position of said 0-th through (m×

n-1)-th memory means; and

means for reading said value stored in a memory area addressed by said addressing means of said data conversion table and storing it in the corresponding (x, y) coordinate position thereof.

13. An image processing device according to claim 10, wherein said means for obtaining marginal distributions divides a first image, formed of conversion data obtained by said conversion means, into two images of equal size, with M pixels in the x direction and N pixels in the y direction taken as a minimum unit;

adds image data in substantially the same positions in the two images of equal size;

obtains a second image formed of image data resulting from addition; and

repeatedly performs the division and addition, using the second image as a new first image, until the second image becomes M pixels in the x direction and N pixels in the y direction in size, the finally obtained second image of M pixels in the x direction and N pixels in the y direction in size being made the marginal distribution image P(x, y).

14. An image processing device according to claim 9, wherein said first marginal distribution computing means obtains the marginal distribution P(z) for the z direction, in accordance with the following equation:

##EQU10## where k is a memory section number, j is p-bit image data, hst(2^p×

k+j) is a histogram of concatenated data specified by the value k and data j, and J(i) is the set of the p-bit image data in which the i-th bit is a logic 1.

15. An image processing method for obtaining the volume and center of gravity of a three-dimensional binary image, comprising:

dividing a three-dimensional binary image composed of M pixels in an x direction, N pixels in a y direction, and (m×

n×

p) pixels in a z direction, by a p-pixel unit in the z direction, to form 0-th through (m×

n-1) partial three-dimensional binary images;

storing the 0-th through (m×

n-1)-th partial three-dimensional binary images in 0-th through (m×

n-1)-th memory blocks each having a storage capacity of M bits in the x direction, N bits in the y direction, and p bits in the z direction, respectively;

concatenating p-bit data in each (x, y) coordinate position of said memory blocks and q-bit data representing the number of the memory block with the p-bit data as lower data and the q-bit data as upper data, to generate (p+q)-bit concatenated data;

obtaining a histogram representing a distribution of the concatenated data of equal values;

computing a marginal distribution of the three-dimensional binary image for its z direction, on the basis of the histogram;

converting the p-bit data in each (x, y) coordinate position of said memory blocks to data representing the number of bits of a logic 1 contained in the p-bit data, to obtain a first image;

dividing the first image into (m×

n) partial images with m images in the x direction and n images in the y direction, and adding image data located, in the same relative positions in the partial images to obtain a second image representing a marginal distribution image P(x, y) of the three-dimensional binary image;

obtaining a marginal distribution P(x) in the x direction and a marginal distribution P(y) in the y direction, on the basis of the marginal distribution image represented by the second image;

computing the volume V of the three-dimensional binary image on the basis of one of the marginal distributions P(x), P(y), and P(z); and

computing the position in coordinates of the center of gravity of the three-dimensional binary image, on the basis of the volume V and the marginal distributions P(x), P(y), and P(z).

16. An image processing method according to claim 15, wherein the data converting to obtain the first image comprises:

preparing a data conversion table having memory areas assigned addresses, for storing in each of said memory areas the number of bits of a logic 1 contained in the address assigned thereto;

addressing said data conversion table by use of the p-bit data stored in each (x, y) coordinate position of said 0-th through (m×

n-1)-th memory blocks; and

reading a value stored in an addressed memory area of said data conversion table and storing the value.

17. An image processing method according to claim 15, wherein the obtaining of a second image comprises dividing the first image into two images of equal size, with M pixels in the x direction and N pixels in the y direction taken as a minimum unit;

adding image data in substantially the same positions in the two images of equal size., obtaining a third image formed of image data resulting from addition;

repeatedly performing the division and addition, using the third image as a new first image, until the third image becomes M pixels in the x direction and N pixels in the y direction in size; and

making the finally obtained third image of M pixels in the x direction and N pixels in the y direction in size the second image.

18. An image processing method according to claim 15, wherein said comprising a marginal distribution P(z) obtains the marginal distribution for the z direction in accordance with the following equation:

##EQU11## where k is a memory section number, j is p-bit image data, hst(2^p k+j) is a histogram of concatenated data specified by the value k and data j, and J(i) is the set of the p-bit image data in which the i-th bit is a logic 1.

19. An image processing method according to claim 15, wherein said computing a marginal distribution P(z) comprises:

initializing a table memory;

producing concatenated data while updating the (x, y) coordinate position in sequence;

addressing said table memory by use of the concatenated data; and

incrementing by one the count value stored in a memory area of said table memory designated by the concatenated data.

20. An image processing device for implementing the method claimed in claim 15.