Method and apparatus for identifying discrete objects in a visual field

Abstract

The processing time for identifying discrete objects in a visual field composed of pixels is reduced by establishing indirect links between points of occurrence in the array and object names in an object designation list.

I claim: 
     
       1. A method for identifying discrete objects in a visual field composed of an array of pixels, comprising: establishing a first table for recording a set of pointers, each of said pointers being associated with the occurrence of a prespecified condition in a corresponding one of said pixels;   establishing a second table for recording one or more object names;   setting the pointers of the pointer table to point to one or more object names in the second table; and   changing one of the object names in the second table when it is found that the pixels associated therewith through their respective pointers belong to an object of a different name;   counting the number of pointers pointing to one or more specific object names recorded in the second table.   
     
     
       2. The method of claim 1 further comprising the step of: passing a scanning window, smaller than the array, across the array to detect the occurrence of the prespecified condition in one or more of said pixels.   
     
     
       3. The method of claim 2 wherein the scanning window passes across the array just once. 
     
     
       4. The method of claim 2 wherein the scanning window covers no more than six pixels at a time. 
     
     
       5. The method of claim 1 further comprising the steps of: digitizing a view of a surface; and   specifying said occurrence condition to be the occurrence of a hillock.   
     
     
       6. The method of claim 1 further comprising the steps of: digitizing a view of a nodule covered semiconductive substrate; and   specifying said occurrence condition to be the occurrence of a nodule.   
     
     
       7. The method of claim 1 further comprising the step of generating an occurrence density plot on the basis of said pointer counting step. 
     
     
       8. The method of claim 7 further comprising plotting occurrence density against the number of discrete objects having such occurrence density. 
     
     
       9. The method of claim 7 further comprising: controlling a manufacturing process parameter in accordance with said density plot. 
     
     
       10. An apparatus for identifying discrete objects in an array of pixels, comprising: scanning means for scanning the pixels of the array and generating data representing one or more prespecified attributes of the pixels;   processor means for processing data received from the scanning means;   memory means for recording data generated by the processor means; wherein the memory means is structured to contain a first table comprises of one or more pointers respectively associated with one or more of the pixels in the array which have a prespecified attribute and the memory means is further structured to contain a second table composed of object designations for assigning object names to said pixels indirectly through said pointers of the first table, and   wherein said memory means is structured to contain a third table comprises of one or more bins for recording the number of pointers pointing to an object designation in the second table.     
     
     
       11. The apparatus of claim 10 wherein said scanning means scans the pixels sequentially via a scanning window that is smaller than the array. 
     
     
       12. The apparatus of claim 10 wherein the processor means includes means for changing an object designation in said second table. 
     
     
       13. An apparatus for identifying discrete objects in an array of pixels, comprising: a first memory means for storing object names;   a second memory means for storing pointers pointing to the object names, each pointer indirectly linking a pixel having a prespecified attribute to an object name in the first memory means;   name changing means, coupled to the first memory means, for changing an object name stored in the first memory means; and   means for counting the number of pointers linking pixels to one or more specific object names stored in the first memory means.   
     
     
       14. The apparatus of claim 13 further comprising means responsive to said counting means, for generating an occurrence density plot. 
     
     
       15. The apparatus of claim 14, further comprising means for plotting occurrence density against the number of discrete objects having such occurrence density. 
     
     
       16. The apparatus of claim 14 further comprising means for controlling a manufacturing process parameter in accordance with said density plot. 
     
     
       17. A method for identifying an object in a visual field, comprising the steps of: identifying an interrogation region of said visual field;   identifying a focal pixel on a scan line in said interrogation region corresponding to part of an object;   initializing updating a pointer table and an object designation table with respect to said focal pixel, comprising the steps of: determining whether said focal pixel forms an edge of an object;   adding a new object designation to said object designation table and a pointer thereto in said pointer table if in accordance with said object edge determining step, said focal pixel is an object edge pixel; and   adding to said pointer table a copy of an existing pointer in said pointer table corresponding to a pixel preceding said focal pixel if in accordance with said object edge determining step, said focal pixel is not an object edge pixel; and     completing updating said pointer table and said object designation table with respect to said focal pixel, comprising the steps of: identifying a first occurrence, if any, on a preceding line within said interrogation region;   amending the object designation in said object designation table corresponding to said focal pixel in accordance with an object designation corresponding to said first occurrence;   following said focal pixel object amending step, amending an object designation corresponding to a subsequent occurrence, if any, on said preceding line within said interrogation region in accordance with the object designation corresponding to said focal pixel;   identifying an occurrence, if any, subsequent to said focal pixel and within said interrogation region; and   adding to said pointer table a copy of the pointer in said pointer table corresponding to said focal pixel, said pointer copy corresponding to said occurrence subsequent to said focal pixel.     
     
     
       18. The method of claim 17, wherein: said interrogation region is a rectangular interrogation region of two lines having three pixels each, and said focal pixel is a middle pixel in one of said lines;   said preceding pixel of said initializing step and said focal pixel are in the same line;   said update completing step further comprises amending object designations corresponding to all occurrences, if any, subsequent to said first occurrence, on said preceding line in said interrogation region in accordance with the object designation corresponding to said focal pixel; and   said occurrence subsequent to said focal pixel in said completing step is an occurrence in a pixel in the same line as the focal pixel.