Image analysis – Image enhancement or restoration – Edge or contour enhancement
Reexamination Certificate
1999-11-24
2004-02-24
Patel, Jayanti K. (Department: 2625)
Image analysis
Image enhancement or restoration
Edge or contour enhancement
C382S151000, C382S168000, C382S199000, C345S427000, C345S629000
Reexamination Certificate
active
06697535
ABSTRACT:
FIELD
This invention relates to machine vision, and particularly to methods and apparatuses for interpretation of edge point data from an image.
BACKGROUND
Dispersion of data is a common problem in many fields, including image processing. In image processing, data fails to converge to one grouping for numerous reasons, such as, imperfections in the imaging environment, the algorithm(s) employed, and/or the discrete nature of processing the data using a computer. Data dispersion detrimentally affects some types of image processing more than others. For instance, finding lines in images is more detrimentally effected by dispersion than finding regions. Typically, the integrity of smaller groupings of data, such as lines, relative to the remainder of the image, suffer more from dispersion effects. It is also difficult to identify elements composed of a relatively small amount of data because of confusing appropriate data with superfluous data.
An example of dispersion of edge points of a line is illustrated using
FIG. 1
, not drawn to scale, which depicts an imaged line
102
having multiple edge-point directions
100
, shown schematically. An edge point is derived from underlying image pixels, where an image pixel is a picture element characterized by a grey value, where an image can be represented as an array of image pixels. A plurality of connected edge points creates a contour, such as a line or boundary
200
between two regions
202
and
204
, illustrated in FIG.
2
. The direction of an edge point
210
is perpendicular to the line
200
upon which the edge point
208
resides. Turning back to
FIG. 1
, the edge points
110
of the line
102
do not share a common direction
100
, but are distributed about a peak angle, as shown in the discrete-angle histogram
104
. The edge-point directions
100
fall into multiple discrete bins
108
that are distributed around a peak bin
106
, where the peak bin
106
represents the mode of the histogram (i.e. the primary direction of the edge points
110
in the line
102
). The lack of convergence of all the edge points
110
to the peak bin
106
illustrates the typical data dispersion present for lines in images. Lines detected using the Hough line-transform method also suffer from this problem.
The majority of line finding algorithms in machine-vision applications, are variations of the Hough line-transform method, described in U.S. Pat. No. 3,069,654. The Hough line-transform method transforms characteristics of edge points into line characteristics, and represents the line characteristics on a Hough space, where a point in the Hough space represents a line.
The characteristics of the edge points include the edge-point position, denoted (x, y), edge-point direction, denoted &thgr;, and optionally, edge-point magnitude, denoted M, which are all measured in Cartesian space. The edge-point position is typically a function of the position of a neighborhood of the underlying image pixels. The edge-point magnitude and direction are a function of the change in grey value of the image pixels that contribute to the edge point.
The characteristics of an edge point, (&thgr;, x, y, and optionally M) are transformed into line characteristics (d, c, and &agr;) Typically, the characteristics of edge points in a contour are called features (such as position), while characteristics derived from the features are called parameters (such as line angle).
The line characteristics are illustrated in Cartesian space in FIG.
3
. The line characteristics include a line angle
302
, denoted &agr;, which is the angle of the line
300
from the horizontal, a distance-vector
304
, denoted d, which is the shortest distance from the origin of a coordinate system
314
to the line
300
, and, optionally, a collinear distance
306
, denoted c, which is the distance from the edge point
308
to the place where d touches the line
300
, in Cartesian space, d is signed to differentiate between lines with identical &agr; and d parameters on opposite sides of the origin
314
. More specifically, the sign of d is negative if the angle
312
of d from the horizontal in Cartesian coordinates is less than 180° and greater than, or equal to, zeros (i.e., 180°>&bgr;≧0); and positive when the angle
312
of d is less than 360°, and greater than, or equal to, 180° (i.e., 360°>⊖≧180°).
d, c, and &agr; are generated from the following Hough-transform equations:
d =x
·sin(&thgr;)−
y
·cos(&thgr;) [1]
c =x
·cos(&thgr;)+
y
·sin(&thgr;) [2]
&agr;
degrees
=[&thgr;+90]
mod180
[3]
d and &agr; are stored on a Hough space.
FIG. 4A
depicts an instance of a Hough space
400
for lines. The Hough space for lines is a two-dimensional space in which lines from an image are recorded. The Hough space is adequately represented as a two-dimensional array of bins
402
. One axis
404
represents the line-angle, &agr;, and the other axis
406
represents the distance vectors, d. A point on a Hough space represents a line.
During the transformation, for each edge point in an input image: the values of d and &agr; are calculated, and the bin of the Hough space, whose range includes the value of d and &agr; for each edge point, is incremented. Once all the edge points in the input image have been examined, the Hough space is searched for maximum values, using peak detection, a method known in the art. The bin having the highest value in the Hough space represents the strongest line detected in the input image, the second highest local maxima represents the second strongest line detected, and so forth.
Each bin
402
in the Hough space represents a discrete range of angles and a discrete range of distance vectors.
FIG. 5
shows an instance of a quantization of the angles for a Hough space, where 360° is divided into 64 bins. Each of the 64 bins has a range of 5.62 degrees per bin, where the first bin accommodates the angles within 0-5.62°, the second bin accommodates the angles within 5.62°-11.24°, and so on.
Typically, the line-angle range and/or distance-vector range for each bin in the Hough space, and the divisions of ranges between the bins, are driven by system and application parameters, and often do not exactly represent the line angles or distance vectors in a given image. Thus, the partitioning of the line angle and the distance vector into discrete bins hinders detecting lines whose edge points straddle the boundaries, such as lines with a line angle of 5.62°, in the above example. The edge points of such lines, typically, transform into more than one bin, thus, it is more difficult to detect these lines, as is further discussed in J. Brian Burns, Allen R. Hanson, and Edward M. Riseman, “Extracting Straight Lines”, IEEE Transactions on Pattern Analysis and Machine Intelligence, 8(4), 1986.
The effects of dispersion and the number of partitions in an axis are decreased by increasing the range of data accepted in each bin. However, increasing the range decreases precision of the line angles and/or distance vectors. As illustrated using
FIG. 6
, which depicts a 59° line
600
and a 51° line
610
and their respective discrete-angle histograms
602
and
612
derived from a Hough space. A Hough space created using a four-bit representation for angle partitions the line-angle axis of the Hough space so that the edge points
604
and
614
of both lines
600
and
610
all map to bin two in the Hough space. Thus, the ability is lost to distinguish between a 51° line and 59° line in Hough space.
Other techniques known in the art, such as a Point Spread Function update method, for example, also decrease dispersion effects. For each edge point, the Point Spread Function update method increments more than one bin with a partial weighting. Although the edge points do not contribute 100% to the weight of the appropriate bin, it is less likely any edge points fail completely to contribute to the weight of the appropriate bin. Although the Point Spread Function
Calabresi Tracy
Chawan Sheela
Cognex Technology and Investment Corporation
Patel Jayanti K.
LandOfFree
Method for refining a parameter of a contour in an image does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method for refining a parameter of a contour in an image, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for refining a parameter of a contour in an image will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3278300