Machine vision methods and articles of manufacture for determination of convex hull and convex hull angle
First Claim
1. A machine vision image processing method for identifying in an image a convex hull around a set of points whose respective locations are defined by at least a pair of coordinates, the method comprisingfinding in the set a plurality of extreme points that expected to reside on the convex hull,ordering, in a succession that defines a hull, points in the set that are outside a closed polygon defined by the extreme points,the ordering step includingsorting the points that are outside the closed polygon using a first coordinate as a primary key and using a second coordinate as a secondary key,identifying a line defined by points in the set having minimum and maximum values as to the first coordinate,ordering the points that are outside the closed polygon according to their position with respect to that line as to the second coordinate, andtesting successive points on the hull to remove those that do not define a convex hull.
1 Assignment
0 Petitions
Accused Products
Abstract
A machine vision method for identifying a convex hull (i.e., a perimeter) around a set of points (e.g., such as may be found in an image of a ball grid array, or BGA, device) involves finding several "extreme" points on the convex hull. Points in the set that are outside a closed polygon defined by those extreme points are ordered to form a hull by, sorting them, identifying a line defined certain minimum and maximum coordinate values, and re-ordering the sorted points according to their position with respect to that line. The method further calls for testing successive points on the hull and removing those that do not define a convex hull using aspects of a Graham scan technique. The invention also provides a method for finding the angular orientation of a convex hull. The methods of the invention can be beneficially applied to the inspection of images of ball grid array devices, as well as other machine vision applications.
64 Citations
18 Claims
-
1. A machine vision image processing method for identifying in an image a convex hull around a set of points whose respective locations are defined by at least a pair of coordinates, the method comprising
finding in the set a plurality of extreme points that expected to reside on the convex hull, ordering, in a succession that defines a hull, points in the set that are outside a closed polygon defined by the extreme points, the ordering step including sorting the points that are outside the closed polygon using a first coordinate as a primary key and using a second coordinate as a secondary key, identifying a line defined by points in the set having minimum and maximum values as to the first coordinate, ordering the points that are outside the closed polygon according to their position with respect to that line as to the second coordinate, and testing successive points on the hull to remove those that do not define a convex hull.
-
7. An article of manufacture comprising a computer usable medium embodying program code for causing a digital data processor to carry out a method of identifying a convex hull around a set of points whose respective locations are defined by at least a pair of coordinates, the method comprising
finding in the set a plurality of extreme points that expected to reside on the convex hull, ordering, in a succession that defines a hull, points in the set that are outside a closed polygon defined by the extreme points, the ordering step including sorting the points that are outside the closed polygon using a first coordinate as a primary key and using a second coordinate as a secondary key, identifying a line defined by points in the set having minimum and maximum values as to the first coordinate, ordering the points that are outside the closed polygon according to their position with respect to that line as to the second coordinate, and testing successive points on the hull to remove those that do not define a convex hull.
-
13. A machine vision method of identifying in an image a convex hull around a set of points representing the solder bumps of ball grid array (BGA) device having locations defined by at least a pair of coordinates, the method comprising
finding in the set of points representing the solder bumps a plurality of extreme points that are expected to reside on the convex hull, ordering, in a succession that defines a hull, points in the set representing the solder bumps that are outside a closed polygon defined by the extreme points, the ordering step including sorting the points that are outside the closed polygon using a first coordinate as a primary key and using a second coordinate as a secondary key, identifying a line defined by points in the set having minimum and maximum values as to the first coordinate, ordering the points that are outside the closed polygon according to their position with respect to that line as to the second coordinate, and testing successive points on the hull to remove those that do not define a convex hull of the set representing the solder bumps.
Specification
-
- Resources
-
Current AssigneeCognex Corporation
-
Original AssigneeCognex Corporation
-
InventorsOhashi, Yoshikazu
-
Primary Examiner(s)Cosimano, Edward R.
-
Application NumberUS08/506,295Time in Patent Office1,135 DaysField of Search364/559, 382/145, 382/146, 382/147, 382/199, 382/203US Class Current702/152CPC Class CodesG01B 11/24 for measuring contours or c...
