Image analysis – Image compression or coding – Polygonal approximation
Reexamination Certificate
2001-07-11
2004-05-11
Patel, Jayanti K. (Department: 2623)
Image analysis
Image compression or coding
Polygonal approximation
C345S420000
Reexamination Certificate
active
06735343
ABSTRACT:
FIELD OF THE INVENTION
The present invention includes two distinct aspects which are preferably used together. The first aspect relates to a method to find polygons which uses data from the corners of polygons. The second aspect relates to search tree for a geometric match wherein search tree segments are truncated or pruned. The preferred embodiment of the invention relates to locating polygons based on corner data using the inventive geometric matching technique.
BACKGROUND OF THE INVENTION
The manufacture of integrated circuit chips rely on high speed manufacturing processes which typically incorporate systems which inspect the chips or provide a reference location on the chips. Such systems include cameras which capture images of the chips and controllers or computers which are operative to locate objects within the images. Objects are located or inspected to either approve the quality and configuration of a part or direct some aspect of the manufacturing process.
Many different techniques have been developed to locate objects within images. Many popular techniques involve correlation. There are several types of correlation methods including convolution, normalized correlation, least mean squares error and least mean absolute error. Correlation requires the definition of a template or kernel which is a separate small image with the same shape as the object to be located. Like the object, the template may be represented by spatial coordinate points with a brightness for each value. These spatial points are commonly referred to as pixels. The template is moved across the image and correlated against the image to determine a match. Correlation techniques are often used because they can locate an object within an image in a comparatively short period of time. One of the fastest and most accurate correlation techniques in the marketplace is binary vector correlation. The theory behind binary vector correlation is covered in a paper entitled “Vector Morphology and Iconic Neural Networks” by S. S. Wilson in
IEEE Transactions on Systems Man, and Cybernetics
, November/December, 1989 Vol. 19, nol 6, pp. 1636-1644. Correlation techniques have improved as disclosed in commonly assigned U.S. Pat. No. 6,023,530.
While correlation techniques are comparatively fast, one problem with many correlation techniques is that they are rotationally and scale intolerant. Rotational intolerance describes the situation where the relative angle of the object within the image, as measured from a Cartesian axis, is different from the angle of the template as measured from the same Cartesian axis. An example of this would be a square and a diamond with equal length sides and corner angles of ninety degrees. Scale intolerance problems created when the template is a different size compared to the object. Thus, correlation techniques are not particularly useful in finding rotated objects.
An example of where correlation techniques have been successfully used is in the semiconductor industry to locate pads on integrated circuit chips. Pads provide the interconnection interface to device or other circuitry and need to be accurately located before probing and bonding. In the past, the pad was square or rectangular in shape. However, as chip design has advanced pad shapes have changed and have rotated. Thus, prior art correlation techniques are not particularly well suited to certain advancements in the manufacturing of integrated circuit chips.
Also in pick and place operations, chip components are picked from a tray, inspected and then placed to be soldered on a printed circuit board. The picked component may be rotated or offset from an expected position and it is necessary to use a vision system to find its orientation, the correct size and potentially inspect it in order for it to be placed correctly on the board. In another aspect of this process, a vision system may be used to locate fiducials or registration marks on the circuit boards in order to find the location and orientation of the board before chip components are placed.
An image processing techniques which has been used to locate rotated objects is geometric matching. Geometric matching describes the process of comparing individual geometric features from a model against geometric features extracted from an image to locate an object within the image. For example, the geometric features from a model may be the length, location and direction of a pattern of line segments. A geometric matching technique would extract line segments from an input image and compare each extracted line segment against the collection of predefined geometric features to locate an object within an image.
Many types of geometric matches are available in the prior art. These include key feature algorithms; generalized Hough algorithms; search trees and geometric hashing. Key feature algorithms search for a small number of highly distinctive local geometric features which indicate the placement of an object in an image. Generalized Hough algorithms employ voting schemes to search all possibilities in a pose space. Tree search algorithms expand a tree of potential matches between a model and image features using local geometric consistencies constraints for pruning. Geometric hashing first creates a hash table of all subsets of image features and then at run time selects sets of data features within an acquired image and looks up their correspondence in the hash table. These prior art techniques are described in an article entitled “
Local Search Algorithms for Geometric Object Recognition: Optimal Correspondence and Pose
, J. Ross Beveridge, University of Massachusetts at Amherst, Ph.D. Dissertation, June 1993, (Also
UM Mass Techreport
93-71), which is incorporated herein by reference.
Of the many prior art techniques, tree searches examine the most features and is thus the most computationally intensive. Because of the enormous amount of data which may be compared the search tree and other geometric matching techniques are often slow.
Because of its comparatively slower speed to provide high accuracy, geometric matches are not always well suited to the requirements of the integrated circuit chips industry. Therefore a need has arisen to provide a method to quickly locate an object within an image where the object is rotated.
SUMMARY OF THE INVENTION
The first aspect of the present invention provides for a method for locating a polygon within an image using a polygon model defined by corner features. An image is captured and corner features are extracted from the image. A geometric match is used to compare the corner features from the polygon model against the corner features extracted from the image to locate a polygon within the image that matches the polygon model.
In a preferred embodiment of the first aspect of the present invention, line edge segments are extracted from the input image and it is determined whether the line edge segments define corners. Corners are formed from the line edge segments where the line segments define corners.
A further aspect of the preferred embodiment of the first aspect of the present invention locates polygons using a search tree including comparing the corner features from the model against the plurality of corners features extracted from the image, calculating a pose and calculating fit errors and match score for each of the comparisons, and; truncating the search tree if the pose fit errors and match score fall outside predefined parameters.
The first aspect of the present invention also provides for an article of manufacture including a computer readable medium bearing computer program code embodied therein for performing a task. The computer readable medium includes means for defining a polygon model defined by corner features, means for activating a camera to capture an image of an object wherein the image includes a polygon, means for extracting corner features from the image, and means for geometrically matching the corner features from the polygon model against the corner features extracted from the image to locate a polyg
Azarian Seyed
Electro Scientific Industries Inc.
Patel Jayanti K.
Young & Basile PC
LandOfFree
Polygon finder and pruned tree geometric match method does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Polygon finder and pruned tree geometric match method, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Polygon finder and pruned tree geometric match method will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3219254