Autogrid analysis
Assignee3M Innovative Properties Company
InventorMatthew Robert Cole Atkinson
Life of this patent
Estimating the term…
Abstract
A method and apparatus for identifying the orientation and positions of the elements of a grid in an image. The elements of the grid need not be parallel to the sides of the image, and the image need not contain all of the elements of the grid. The method can be applied to multi-sided grids, whether rectilinear or distorted. The addresses of identified grid elements can be used to control, e.g., analytical procedures directed to individual elements.
Claims42
A method of identifying the position in an image of a plurality of features in a substantially four-sided, four-cornered grid of features, each feature having a centroid, comprising:
- a) obtaining an image;
- b) identifying the significant features in the image;
- c) defining centroids for each significant feature;
- d) identifying the centroids at the four corners of the grid and defining a nominal four-sided outline between them;
- e) searching for centroids within a window defined by a predetermined margin of one side of the nominal outline;
- f) determining the distance from each such centroid found in the window to the next such centroids along the one side;
- g) preparing a histogram of such distance for all centroids in the window;
- and
- h) defining a nominal distance between centroids for the one side as the distance represented by the first peak in the histogram.
The method of claim 16, wherein the centroid closest to each identified nominal position of a feature in the grid must also be within one-half of the average distance from that nominal position to the adjacent nominal positions to be defined as the actual position for that feature in the grid.
A method of identifying the position and nominal outline in an image of a multi-sided, multi-cornered grid of features, comprising:
- a) obtaining an image;
- b) identifying the significant features in the image;
- c) defining a centroid for each significant feature;
- d) placing a search line on the perimeter of the image and moving it across the image until it contacts a first centroid;
- e) defining the position of the first centroid as a corner of the grid;
- f) placing a search line at the first corner of the grid, and rotating it toward the center of the image to perform centroid integration;
- g) defining the centroids corresponding to the first peak in the centroid integration as the first side of the grid;
- h) identifying as the next corner that centroid which is along the first side of the grid and farthest from the first corner;
- i) placing a search line at the next corner of the grid, and rotating it toward the center of the image to perform centroid integration;
- j) defining the centroids corresponding to the first peak in the centroid integration conducted in step i) as the next side of the grid;
- and
- k) identifying as the subsequent corner that centroid which is along the next side of the grid and farthest from the next corner.
A system for identifying the position in an image of a plurality of features in a substantially four-sided, four-cornered grid of features, each feature having a centroid, the system comprising:
- a) an image capture device for capturing an image;
- b) a data storage device;
- and
- c) a central processing unit for receiving a captured image from the image capture device and which can write to and read from the data storage unit, the central processing unit being programmed to:
- i) obtain an image;
- ii) identify the significant features in the image;
- iii) define centroids for each significant feature;
- iv) identify the centroids at the four corners of the grid and define a nominal four sided outline between them;
- v) search for centroids within a window defined by a predetermined margin of one side of the nominal outline;
- vi) determine the distance between each such centroid found in window to the next such centroid along the one side;
- vii) prepare a histogram of such distance for all centroids in the window;
- and
- viii) define a nominal distance between centroids for the one side as the distance represented by the first peak in the histogram.
The system of claim 35, wherein the central processing unit further is programmed to iterate steps 92.c)v) through 92.c)viii) and the steps of claims 23 through 25 to identify a nominal curve for each column in the grid, at each iteration using the curve developed from the prior iteration in place of the curve used in the prior iteration.
The system of claim 33 wherein the central processing unit further is programed to iterate steps 92.c)v) through 92.c)viii) and the steps of claims 23 through 35 and claim 33 to identify a nominal curve for each row in the grid by starting from a side of the nominal outline adjacent to the one side.
A system for identifying the position in an image of a plurality of features in a multi-sided, multi-covered cornered grid of features, each feature having a centroid, the system comprising:
- a) an image capture device for capturing an image;
- b) a data storage device;
- and
- c) a central processing unit for receiving a captured image from the image capture device and which can write to and read from the data storage unit, the central processing unit being programmed to:
- i) obtain an image;
- ii) identify the significant features in the image;
- iii) define a centroid for each significant feature;
- iv) place a search line on the perimeter of the image and move it across the image until it contacts a first centroid;
- v) define the position of the first centroid as a corner of the grid;
- vi) place a search line at the first corner of the grid, and rotate it toward the center of the image to perform centroid integration;
- vii) define the centroids corresponding to the first peak in the centroid integration as the first side of the grid;
- viii) identify as the next corner that centroid which is along the first side of the grid and farthest from the first corner;
- ix) place a search line at the next corner of the grid, and rotate it toward the center of the image to perform centroid integration;
- x) define the centroids corresponding to the first peak in the centroid integration conducted in step 52.i) as the next side of the grid;
- and
- xi) identify as the subsequent corner that centroid which is along the next side of the grid and farthest from the next corner.
Dependencies are inferred from the claim text.