Image analysis – Image segmentation – Using projections
Reexamination Certificate
1999-10-21
2002-11-05
Chang, Jon (Department: 2623)
Image analysis
Image segmentation
Using projections
C382S201000, C382S288000
Reexamination Certificate
active
06477273
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Technical Field
The present invention relates to methods and systems for identifying objects in an image, and in particular, to methods and systems for identifying lines, curves or similar shapes in an image or graphical representation of a dataset.
2. Description of the Related Art
There are many applications for machine vision and analysis in which it is useful to find the location of lines, curves or similar shapes in an image. 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 such a use, it is helpful to be able to identify the position of the rows and columns of the sample grids on the plates, gels and blots.
Similarly, there are many manufactured products which include arrays, cross hatching or other regular patterns, such as printed or micro-replicated materials, and chip sockets. Machine vision is a useful way of inspecting such products, but, again, there often must be some ability to determine the orientation and position of the shapes in the image for this to be useful.
Many tests also vary with time, and it is important to be able to track the location of specific peaks or bands in the data as they move over time. For example, a graph showing the time variability in the strength of signal at particular wavelengths for nuclear magnetic resonance (NR) or infrared (IR) peak data sometimes will drift, and it is desirable to accurately identify the different peaks even as they shift around.
Still further, recent approaches to data mining and knowledge engineering seek out unrecognized patterns in data. For any data which can be represented graphically, finding lines, curves or other shapes in the resulting image can be a way to identify hidden patterns.
SUMMARY OF THE INVENTION
The present invention addresses these problems through a new technique called “centroid integration”.
Centroid integration starts by obtaining an image or other graphical representation of the data to be analyzed, and digitizing the image into pixels. Using any suitable algorithm, individual features in the image are identified. The centroid position of each feature, and characteristic values of each 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 values corresponding to the characteristic values. Any value appropriate to the application may be used as a characteristic value. For example, the area of the feature and the integrated intensity of the feature over its entire area would be typical characteristic values.
The detail level of the collapsed image can be controlled by using appropriate algorithms to distinguish between different features. Alternatively, the manner in which a particular algorithm distinguishes between different features can be adjusted, e.g., by requiring more or less discrimination in a chosen value in adjacent pixels to qualify as the boundary of a particular feature.
Once the collapsed image is produced, an integration line is established at an appropriate location in the collapsed image, such as at one edge. This integration line is swept across at least the relevant portion of the collapsed image in steps. At each step, the sum of a characteristic value, e.g., 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 feature (or a band of features, if the features happen to lie on the same integration line).
Note that this process is different from simply integrating the image intensity along the search line. Due to the use of a collapsed image, each feature effectively has its characteristic values concentrated at its centroid.
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 an image with significant 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.
The size of the steps (or “smoothing window”) by which the integration line is moved can be important in some settings. For example, if the image is expected to include regularly spaced lines, optimum results often can be obtained by setting a smoothing window that is proportional to the spacing of the lines. The use application of centroid integration to images containing lines or grids of features is discussed in more detail in a co-assigned U.S. patent application Ser. No. 09/422,535, filed Oct. 21, 1999, entitled, “Autogrid Analisis”, which is incorporated herein by reference.
If the characteristics of the data in the image are not known, and particularly if the objective is-to find hidden patterns in the data, it may be desirable to test a variety of smoothing window sizes to find one that maximizes the peak differentiation resulting from the centroid integration.
Similarly, the size of the predetermined region on either side of the integration line in which the characteristic values are summed may be varied. Typically, it will match the size of the smoothing window, but in some situations different sizes may be desirable. For example, it may be useful always to move the line in one pixel steps, but analyze the resulting data for different sized regions on either side of the integration line.
Centroid integration is not limited to integrating using straight lines or lines parallel to the sides of the image. Curves or other shapes can be used instead of a straight line to perform the integration, especially if the data is expected to be curved or if one is attempting to identify patterns in the image or data set matching the curve or other shape. It also often will be desirable to test the lines, curves or other shapes at a variety of orientations.
The image being analyzed can be virtually anything, ranging from a photograph of an object to a mathematical representation of a large dataset. In a photograph, the shape found by centroid integration will often be the actual shape of the object, but in a mathematical representation of a dataset, the shape may actually represent a pattern in the data.
Centroid integration also can be applied to higher dimensional analysis. In this situation, instead of moving a line or other one dimensional shape across a two-dimensional graph or image of data, a plane, hyperplane or other multi-dimensional shape is moved through a graph or other representation of data having one more dimension than the plane, hyperplane or other multi-dimensional shape. The characteristic values are summed to a particular point on the plane, hyperplane or other shape.
As will be apparent, centroid integration has a very wide range of potential applications to identify patterns and shapes.
REFERENCES:
patent: 4513438 (1985-04-01), Graham et al.
patent: 5621811 (1997-04-01), Roder et al.
patent: 5872870 (1999-02-01), Michael
patent: 6100901 (2000-08-01), Mohda et al.
patent: 6199986 (2001-03-01), Williams et al.
patent: 0 176 910 (1986-04-01), None
patent: 0 617 380 (1994-09-01), None
patent: 2 294 319 (1996-04-01), None
patent: 2318637 (1998-04-01), None
patent: WO 99/08233 (1999-02-01), None
Jarreau et al. “2-Dimensional Object Recognition for the ISAC System.” Proc. IEEE, Southeastcon '92, vol. 1, Apr. 1992, pp. 27 30.*
Farrow, G. S. D. et al., “Detecting The Skew Angle In Document Images”,Signal Processing, Image Communication, NL, Elsevier Science Publishers, Amsterdam, vol. 6, No. 2, May 1, 1994, pp. 101-114.
Yu, B. et al., “A Robust And Fast Skew Detection Algorithm For Generic Documents”,Pattern Recognition, US, Pergamon Press Inc., Elmsford, NY, vol. 29, No. 10, Oct. 1, 1996, pp. 1599-1629.
Srihari, et al., “Analysis Of Textual Ima
3M Innovative Properties Company
Chang Jon
Dahl Philip Y.
Dennis II Charles L.
LandOfFree
Centroid integration does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Centroid integration, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Centroid integration will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2915478