Image analysis – Image segmentation – Using projections
Reexamination Certificate
1999-10-21
2003-10-14
Chang, Jon (Department: 2623)
Image analysis
Image segmentation
Using projections
C382S174000, C382S201000, C382S288000
Reexamination Certificate
active
06633669
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Technical Field
The present invention relates to methods of identifying objects in an image, and in particular, to identifying the orientation and position of a grid in an image, and using the resulting grid for measurement.
2. Description of the Related Art
Many applications of machine vision and analysis analyze images which contain information arranged in a grid. For example, WO 99/08233 describes a large number of different types of analyses which can be conducted on assay well plates, gels and blots used in chemical, biochemical and physiological analyses. In that use, the positions of elements on a grid are identified and the elements are probed using a wide variety of assays.
WO 98/47006 takes this a step further, by using the image to identify locations of points on a grid, and injecting reagents onto the grid, e.g., with an ink jet sprayer.
In both cases, however, the position and orientation of the grid are generally known. WO 99/08233 suggests allowing for some slight variation in the grid through the use of fuzzy logic, but the nature of the fuzzy logic to be applied is not described in the application. WO 98/47006 simply assumes one knows the orientation and size of the grid.
In addition to these chemical applications, there are many manufactured products which include grid-like arrays or cross hatching, such as printed or micro-replicated materials, and chip sockets. Machine vision is a useful way of inspecting such products, but, again, there must be some ability to determine the orientation and position of each element in the grid for this to be useful.
In addition, most electronic analytical systems conduct measurements for every pixel in the field of view. In non-electronic viewing systems, there has been some suggestion to study only interesting features, e.g., to save the time for cytologists, GB 2,318,627 suggests having a system automatically identify interesting features and move a slide under a microscope to jump from one interesting feature to the next, so that the cytologist need only look at the interesting features. However, past conventional electronic scanning systems generally have scanned and analyzed every pixel in the field of view. Particularly if several measurements are being made, e.g., at different frequencies or under different excitation conditions, this collection of data from every pixel can be quite time consuming, since, for example, even a typical 512×512 pixel image has 262, 144 pixels, and the scanning system must be physically re-adjusted on each pixel in turn.
SUMMARY OF THE INVENTION
The present invention identifies the orientation and position in a field of view of the elements or features of a grid. The grid may have some degree of variance from a purely rectilinear grid, particularly if the variance is generally along a single axis of the grid.
To achieve this according to the present invention, an image of a field of view containing a grid is first obtained and digitized into pixels. Using any suitable algorithm, individual features in the image are identified. The centroid position of each feature, the feature area in pixels and the integrated intensity of the feature all are determined. These are used to produce a “collapsed image,” where each feature is represented by a point object at the centroid location, with the point object having two associated values (area and integrated intensity).
According to a first embodiment of the invention, a search line is created at one side of the image at a base angle &thgr; to the side of the image, and swept across the image in steps. At each step, the integrated intensity of each centroid within a predetermined region on either side of the line is determined and recorded. The result is a two dimensional plot with a series of peaks, each peak corresponding to a column of the grid.
Note that this process is different from simply integrating the image intensity along the search line. Due to the use of collapsed images, each feature effectively has its image intensity and area concentrated at its centroid. This will be referred to herein as “centroid integration”, and is discussed in more detail in a co-assigned patent application filed on even date herewith, 09/422,584, now U.S. Pat. No. 6,477,273, which is incorporated herein by reference.
Centroid integration results in a set of very well defined peaks in the resulting line profile. Regular integration would result in a set of smeared out peaks and, in the case of a grid with some variation in the positions of the individual features, the result would often be unusable. As a result, centroid integration is much more tolerant of local variation in feature positions than conventional integration.
Centroid integration is repeated with two additional search lines starting at a slight variance angle (+&dgr; and −&dgr;) to the original search line and swept across the image.
The slope of the first peak on each of the three search lines is determined. The first peak represents the first column, and the steeper the slope on that peak, the closer that search line was to being parallel to the column of the grid. If the difference between the slopes of the three lines is above a predetermined threshold (i.e., outside a tolerance limit), the line with the steepest first peak slope is identified. If it is the middle line, the process is iterated using a smaller variance angle ±&dgr;. If it is not the middle line, the base angle &thgr; is reset to match the angle of line with the steepest slope, and the process is iterated using the same variance angle ±&dgr; around the new base angle &thgr;. The entire process is iterated until the difference is within the tolerance limit. The angle of the resulting line with the steepest first peak slope will match the angle of the first column of the grid (within the predetermined tolerance limit).
This process is repeated for each peak. For example, the second peak will correspond to the second column, so the search line with the steepest slope on the second peak is the closest to the angle of the second line of the grid. Repeating centroid integration using sweep lines at a base angle &thgr; and variance angles (±&dgr;) to find the slope of the second peak can define the angle of the second column. The process is repeated for each peak.
After the first peak, it is not necessary to start the sweep lines at the side of the image—each sweep line can be started from position of the prior column. In addition, the angle of each column will probably be reasonably close to the angle of the prior column, so the number of sweeps usually can be minimized by starting with a base angle &thgr; matching the angle of the prior column.
Once the position and orientation of each of the columns is identified, the next step is identifying the rows generally orthogonal to the columns just identified. The rows can be identified using substantially the same process as used to identify the columns, but starting from a side of the image adjacent to the side used to find the columns. The intersections of the best fit columns and the best fit rows are determined, and used to define the nominal points in the grid.
The grid of nominal points preferably is “flexed” to define a final grid. To do this, a local search is performed at each nominal grid point for the local centroid, that is, the centroid nearest in position to the nominal grid point. The position of the local centroid is defined as the final grid point.
In some situations, only portions of a single object on a sample will appear in an image, with the results that multiple features are identified instead of a single feature. This might happen, for example, due to the characteristics of the object on the sample, or due to the image capture technique. An alternate aspect of the invention therefore is to find a centroid of the centroids within a predetermined distance of the nominal grid point, and to define this centroid of centroids as the final grid point. As will be apparent, if a single object is represent
3M Innovative Properties Company
Chang Jon
Dahl Philip Y.
Dennis II Charles L.
LandOfFree
Autogrid analysis does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Autogrid analysis, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Autogrid analysis will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3153623