Order-clustering of secant tips into edges for positioning of semiconductor structures
Abstract The paper presents the concept of order-clustering applied for recognition of edges and corners of polygonal objects, especially of two-dimensional shapes met in microelectronics. The recognition process starts with slicing an image into secants. The secant tips are clustered according to the scanning direction. Edge inclination is chosen as one of the main criteria of the order-clustering, enabling parallel shape analysis of each edge inclination (type) without losing the track of edge continuity. A specific distance criterion combined with the order-clustering eliminates arduous disturbances. The nearest neighbor order-clustering appends a tip of a secant to a cluster of edge type when the tip is the closest to the recent element of the edge type and when it satisfies an assumed order for the tip coordinates. The new secant tip is selected from the next line of an image. The superposition of the following factors: secant begginings, secant ends, nonascending order of secant tips and non-descending order of secant tips, allows clustering of edges into four basic types. An additional criterion of a minimum distance splits each edge type into two. The edges are clustered into continuous segments: if the candidate element does not satisfy all the assumed criteria, the recent element of the cluster is treated as the last element of a continuous edge segment. Two continuous segments belonging to different clusters of edges are merged into a corner if they are of sufficient lengths and if they are sufficiently close to each other. Polygons are clustered by merging corners of different types. An example of reconstruction of tetragons is presented.