Method and apparatus for automatic digital image analysis

• US 4,724,543 A
• Filed: 09/10/1985
• Issued: 02/09/1988
• Est. Priority Date: 09/10/1985
• Status: Expired due to Fees

• Current Assignee: Beckman Research Institute (City of Hope)
• Original Assignee: Beckman Research Institute of the City of Hope (City of Hope)
• Inventors: Klevecz, Robert R., Eccles: Beverly A.
• Primary Examiner(s): Moore, David K.
• Assistant Examiner(s): Skinner, A. Anne
• Application Number:
  US06/774,286
• Time in Patent Office: 882 Days
• Field of Search: 382/41, 382/49, 382/27, 382/6
• US Class Current: 382/133
• CPC Class Codes: G06V 20/69 Microscopic objects, e.g. biological cells or cellular parts

Abstract

A method and apparatus for digitally analyzing continuous visual images, particularly with reference to the detection of mammalian cell mitotic events is disclosed. The visual images are analyzed by first extracting high frequency picture components, threshold comparison of such components and probing for annular objects indicative of putative mitotic cells. The detection of annulae is performed by an algorithm for recognizing rings of differential radii and compensating for other variations. Thereafter, spatial and temporal relationships between such objects is stored and compared to determine whether cell division occurred.

Claims

1. A digital image processing system for detecting specific shapes, comprising:

(a) image gathering means for providing a series of electronic signals representing a series of visual images;

(b) conversion means for converting each of said electronic signals to a digital representation and for modifying said digital representation according to external commands;

(c) memory means for storing each said digital representation as an array of pixels, each of said pixels including a value representing gray shading for a unit of said visual image;

(d) processing means coupled to said memory means and to said conversion means for issuing said commands to said conversion means and for detecting and analyzing changes in successive said digital representations;

(e) processing means further comprising means for transforming each said digital representation by;

(i) dilating said digital representation by a series of first structuring elements to provide a dilated digital representation;

(ii) subtracting said dilated digital representation from said digital representation, for identification of high contrast portions of said visual image;

(iii) threshold comparison of said high contrast portions by comparing the gray value of each of said pixels of said high contrast portions with a first reference value, replacing the gray values for each of said pixels whose value exceeds or equals said first reference value with a first fixed gray value and replacing the gray values for each of said pixels whose value is less than said first reference value with a second fixed gray value to provide a first threshold image;

(iv) performing an annulus transformation on said first threshold image to create an annulustransformed image by;

(1) determining a numerical value for the degree of coincidence between pixels having said first fixed gray value in said first threshold image and masks having annular patterns of pixels, said numerical value representing a degree of ring closure, and

(2) storing in said memory means the numerical value for said degree of ring closure and coordinates corresponding to the center of each of said annular masks;

(v) performing a ring-toss transformation on said annulus-transformed image to create a ring-toss transformed image by;

(1) generating a pattern of pixels by dilation of said annulus-transformed image by a second annular structuring element, and

(2) subtracting said dilated annulustransformed image from said annulustransformed image;

(vi) generating a second threshold image by threshold comparison of said ring-toss transformed image by comparing the gray value of each of said pixels of said ring-toss transformed image with a second reference value, replacing the gray values for each of said pixel whose value exceeds or equals said second reference value with a third fixed gray value and replacing the gray values in each of said pixels whose value is less than said second reference value with a fourth fixed gray value;

(vii) storing said second threshold image in said memory means;

(f) means for comparing successive second threshold images of said transformed digital representations to detect appearances of said specific shapes.

2. The image processing system of claim 1 wherein said processing means comprises reading means for reading said digital representations from said memory.

3. The image processing system of claim 2 wherein said processing means comprises writing means for writing said digital representations to said memory.

4. The image processing system of claim 3 wherein said processing means includes logic means for generating structuring elements, said structuring elements including a specific pattern of bits.

5. The image processing system of claim 4 wherein said processing means comprises logic means for executing logic operations including the functions of logical AND, OR, NOT and exclusive-OR.

6. The image processing system of claim 5 further comprising mass storage means coupled to said processing means for permanent storage of data.

7. The image processing system of claim 6 wherein said processing means comprises logic means for creating lists of data in said memory.

8. The image processing system of claim 7 wherein said processing means comprises searching means for identifying particular elements in said lists of data.

9. The image processing system of claim 8 further comprising an input means coupled to said processing means whereby parameters supplied by a user may be stored in said memory.

10. The image processing system of claim 9 wherein said processing means comprises control means for issuing commands to said conversion means.

11. The image processing system of claim 10 wherein said control means comprises sequencing means for reading a series of instructions from said memory for transmission to said conversion means.

12. The image processing system of claim 11 wherein said processing means further comprises arithmetic means for execution of arithmetic operations including ADDITION, SUBTRACTION, MULTIPLICATION and DIVISION.

27. A digital image processing system as in claim 12, comprising means for recording appearances of said specific shapes.

28. A digital image processing system as in claim 27, comprising means for displaying appearances of said specific shapes.

13. A method for identifying and recording the appearance of specific objects as digital representations of a series of visual images in a digital image processing system, said objects including patterns of pixels, comprising the steps of:

(a) converting each said visual image into a digital representation;

(b) providing memory means for storage of each said digital representation as an array of pixels, each pixel including a value representing gray shading for a unit of said visual image;

(c) transforming said digital representation by;

(i) dilating said digital representation by a series of first structuring elements to provide a dilated digital representation;

(ii) subtracting said dilated digital representation from said digital representation, for identification of high contrast portions of said visual image;

(iii) threshold comparison of said high contrast portions by comparing the gray value of each of said pixels of said high contrast portions with a first reference value, replacing the gray values for each of said pixels whose value exceeds or equals said first reference value with a first fixed gray value and replacing the gray values for each of said pixels whose value is less than said first reference value with a second fixed gray value to provide a first threshold image;

(iv) performing an annulus transformation on said first threshold image to create an annulustransformed image by;

(1) determining a numerical value for the degree of coincidence between pixels having said first fixed gray value in said first threshold image and masks having annular patterns of pixels, said numerical value representing a degree of ring closure, and

(2) storing in said memory means the numerical value for said degree of ring closure and coordinates corresponding to the center of each said annular masks;

(v) performing a ring-toss transformation on said annulus-transformed image to create a ring-toss transformed image by;

(1) generating a pattern of pixels by dilation of said annulus-transformed image by a second annular structuring element, and

(2) subtracting said dilated annulustransformed image from said annulustransformed image;

(vi) generating a second threshold image by threshold comparison of said ring-toss transformed image by comparing the gray value of each of said pixels of said ring-toss transformed image with a second reference value, replacing the gray values for each of said pixels whose value exceeds or equals said second reference value with a third fixed gray value and replacing the gray values in each of said pixels whose value is less than said second reference value with a fourth fixed gray value;

(vii) storing said second threshold image in said memory means;

(d) comparing successive said transformed digital representations to detect appearances of said objects;

(e) recording appearances of said objects; and

(f) displaying appearances of said objects.

14. The method as defined by claim 13 wherein said second threshold image is used to update said digital representation stored in said memory means, using a logical OR operation.

15. The method as defined by claim 14 further comprising the step of isolating significant objects in said digital representation by connectivity number.

16. The method as defined in claim 15 further comprising the step of creating a temporal vicinity list in said memory, said temporal vicinity list comprising:

coordinates of an identified object;

a degree of ring closure of said object;

a first time said object was first detected;

a second time said object was last detected; and

an index in said temporal vicinity list of another object to which said identified object is paired.

17. The method as defined in claim 16 further including the step of pairing said identified objects by storing the coordinates of each object in the pair in the temporal vicinity list entry of the other object in said pair.

18. The method as defined in claim 17 wherein said pairing is applied only to objects within a specific number of pixels of each other.

19. The method as defined in claim 18 wherein said pairing takes place between the identified object and the nearest other object when more than one object is within said specific number of pixels.

20. The method as defined in claim 19 further including the step of recording all incidences of said pairing on said mass storage means.

21. The method as defined in claim 20, further including the step of updating said temporal vicinity list for each of said objects identified in said binary representation.

22. The method as defined in claim 21 wherein said updating includes searching said temporal vicinity list for other objects within a specified proximity of said identified object, adding said identified object to the temporal vicinity list if no such other object is found and, if such other object is found, storing the coordinates and degree of ring closure information for said object in the node for said identified object in the temporal vicinity list.

23. The method as defined in claim 22 further including the step of scanning said temporal vicinity list for objects which have aged, such aging occurring when said object is last identified more than a specified time prior to the current visual image being processed.

24. The method as defined in claim 23 further including the step of deleting from said temporal vicinity list all of said objects which have aged and are not paired with another object.

25. The method as defined in claim 24 further including the step of deleting paired objects only when both objects in said pair have aged.

26. The method as defined in claim 25 further including the step of displaying for the use all incidences of said parings on said display means.

29. A pattern recognition system for detecting annular objects in visual images, each of said visual images having been converted to a digital representation as an array of pixels stored in a memory means, each of said pixels having an associated numerical value representing gray shading, comprising:

means for transforming each said digital representation by;

(a) dilating said digital representation by a series of first structuring elements to provide a dilated digital representation;

(b) subtracting said dilated digital representation from said digital representation, for identification of high contrast portions of said visual image;

(c) threshold comparison of said high contrast portions by comparing the gray value of each of said pixels of said high contrast portions with a first reference value, replacing the gray values for each of said pixels whose value exceeds or equals said first reference value with a first fixed gray value and replacing the gray values for each of said pixels whose value is less than said first reference value with a second fixed gray value to provide a first threshold image;

(d) performing an annulus transformation on said first threshold image to create an annulus-transformed image by;

(i) determining a numerical value for the degree of coincidence between pixels having said first fixed gray value in said first threshold image and masks having annular patterns of pixels, said numerical value representing a degree of ring closure, and

(ii) storing in said memory means the numerical value for said degree of ring closure and coordinates corresponding to the center of each of said annular masks;

(e) performing a ring-toss transformation on said annulus-transformed image to create a ring-toss transformed image by;

(i) generating a pattern of pixels by dilation of said annulus-transformed image by a second annular structuring element, and

(ii) subtracting said dilated annulus-transformed image from said annulus-transformed image;

(f) generating a second threshold image by threshold comparison of said ring-toss transformed image by comparing the gray value of each of said pixels of said ring-toss transformed image with a second reference value, replacing the gray values for each of said pixels whose value exceeds or equals said second reference value with a third fixed gray value and replacing the gray values in each of said pixels whose value is less than said second reference value with a fourth fixed gray value;

(g) storing said second threshold image in said memory means.

30. A pattern recognition system as in claim 29, comprising:

(a) means for comparison of successive stored second threshold images of said transformed digital representation to detect appearance of objects in said second threshold images including;

(i) means for updating said stored transformed digital representation using said second threshold image in a logical OR operation;

(ii) means for identifying objects by isolating significant objects in said transformed digital representation based upon connectivity number of said objects;

(iii) means for creating a temporal vicinity list in said memory, said temporal vicinity list comprising;

coordinates of an identified object,

a degree of ring closure of said object,

a first time said object was first detected,

a second time said object was last detected, and

an index in said temporal vicinity list of another object to which said identified object is paired;

(iv) means for pairing said identified objects by storing the coordinates of each object in the pair in the temporal vicinity list entry of the other object in said pair, wherein said pairing is applied only to objects within a specific number of pixels of each other, and wherein said pairing takes place between the identified object and the nearest other object when more than one object is within said specific number of pixels;

(v) means for recording all instances of said pairing in said storage means;

(vi) means for updating said temporal vicinity list for each of said objects identified in said transformed digital representation, wherein said updating includes searching said temporal vicinity list for other objects within a specified proximity of said identified object, adding said identified object to the temporal vicinity list if no such other object is found and, if such other object is found, storing the coordinates and degree of ring closure information for said other object in a node for said identified object in the temporal vicinity list;

(vii) means for scanning said temporal vicinity list for objects which have aged, such aging occurring when said object is last identified more than a specific time prior to the current visual image being processed;

(viii) means for deleting from said temporal vicinity list all of said objects which have aged and are not paired with another object;

(ix) means for deleting paired objects from said temporal vicinity list only when both objects in said pair have aged; and

(x) means for displaying all instances of said pairings.

31. A pattern recognition method for detecting annular objects in visual images, each of said visual images having been converted to a digital representation as an array of pixels stored in a memory, each of said pixels having an associated numerical value representing gray shading, comprising the steps of:

transformation of said digital representation by;

(a) dilating said digital representation by a series of first structuring elements to provide a dilated digital representation;

(b) subtracting said dilated digital representation from said digital representation, for identification of high contrast portions of said visual image;

(c) threshold comparison of said high contrast portions by comparing the gray value of each of said pixels of said high contrast portions with a first reference value, replacing the gray values for each of said pixels whose value exceeds or equals said first reference value with a first fixed gray value and replacing the gray values for each of said pixels whose value is less than said first reference value with a second fixed gray value to provide a first threshold image;

(d) performing an annulus transformation on said first threshold image to create an annulus-transformed image by;

(i) determining a numerical value for the degree of coincidence between pixels having said first fixed gray value in said first threshold image and masks having annular patterns of pixels, said numerical value representing a degree of ring closure, and

(ii) storing in said memory the numerical value for said degree of ring closure and coordinates corresponding to the center of each of said annular masks;

(e) performing a ring-toss transformation on said annulus-transformed image to create a ring-toss transformed image by;

(i) generating a pattern of pixels by dilation of said annulus-transformed image by a second annular structuring element, and

(ii) subtracting said dilated annulus-transformed image from said annulus-transformed image;

(f) generating a second threshold image by threshold comparison of said ring-toss transformed image by comparing the gray value of each of said pixels of said ring-toss transformed image with a second reference value, replacing the gray values for each of said pixels whose value exceeds or equals said second reference value with a third fixed gray value and replacing the gray values in each of said pixels whose value is less than said second reference value with a fourth fixed gray value;

(g) storing said second threshold image in said memory.

32. A pattern recognition method as in claim 31, comprising the steps of:

(a) comparison of successive stored second threshold images of said transformed digital representation to detect the appearance of objects in said second threshold images;

(b) updating said stored transformed digital representation using said result of said transforming step in a logical OR operation;

(c) identifying objects by isolating significant objects in said transformed digital representation based upon connectivity number of said objects;

(d) creating a temporal vicinity list in said memory, said temporal vicinity list comprising;

(i) coordinates of an identified object,

(ii) a degree of ring closure of said object,

(iii) a first time said object was first detected,

(iv) a second time said object was last detected, and

(v) an index in said temporal vicinity list of another object to which said identified object is paired;

(e) pairing said identified objects by storing the coordinates of each object in the pair in the temporal vicinity list entry of the other object in said pair, wherein said pairing is applied only to objects within a specific number of pixels of each other, and wherein said pairing takes place between the identified object and the nearest other object when more than one object is within said specific number of pixels;

(f) recording all instances of said pairing in said memory;

(g) updating said temporal vicinity list for each of said objects identified in said transformed digital representation, wherein said updating includes searching said temporal vicinity list for other objects within a specified proximity of said identified object, adding said identified object to the temporal vicinity list if no such other object is found and, if such other object is found, storing the coordinates and degree of ring closure information for said other object in a node for said identified object in the temporal vicinity list;

(h) scanning said temporal vicinity list for objects which have aged, such aging occurring when said object is last identified more than a specific time prior to the current visual image being processed;

(i) deleting from said temporal vicinity list all of said objects which have aged and are not paired with another object;

(j) deleting paired objects from said temporal vicinity list only when both objects in said pair have aged; and

(k) displaying all instances of said pairings.