Circle location
First Claim
1. An apparatus for locating a curvilinear symbol comprising:
- a. means for generating a grey scale model of a segment of an idealized curvilinear symbol by interpolating curvature at the periphery by assigning foreground pixel values to those pixels located entirely within said grey scale model of said segment of said idealized curvilinear symbol, assigning background pixel values to those pixels located entirely outside said grey scale model of said segment of said idealized curvilinear symbol, and approximately pixel values for boundary pixels of said grey scale model of said segment of said idealized curvilinear symbol by selecting a number of points n, along an arc of said idealized curvilinear symbol that is smaller than the total number of points in said arc, connecting said points n, by straight lines to create an angular feature in each pixel boundary, computing the area of each such angular feature, and computing a grey scale level for each boundary pixel by scaling the grey value by the percentage of said pixel occupied by said angular feature;
b. means for generating a full size model by reflecting said grey scale model of said segment of an idealized curvilinear symbol around the axes of symmetry of said idealized curvilinear symbol;
c. means for searching a digitized image for the location of shapes corresponding to said full size model; and
d. means for generating subfeature models from said full size model.
1 Assignment
0 Petitions
Accused Products
Abstract
This invention provides an apparatus and method for locating a curvilinear symbol by generating a grey scale model of a segment of a curvilinear symbol and interpolating curvature at the segment'"'"'s periphery; reflecting this segment around the axes of symmetry to generate a full size model; generating full resolution subfeature models; assigning coordinate axes weighting to each subfeature model x and y axis; defining tolerance thresholds for deviations from an idealized curvilinear symbol; searching a digitized image for shapes corresponding to the subfeature models; assigning weights to scores returned for positions found corresponding to the subfeature models; producing weighted positions combining both coordinate axis weighting and score weighting; computing a best fit for the image found; comparing the positions found to tolerance thresholds and discarding those positions outside the thresholds; substituting and weighting alternate positions found, if any, to compute the location of the curvilinear symbol from remaining positions within the threshold.
48 Citations
14 Claims
-
1. An apparatus for locating a curvilinear symbol comprising:
-
a. means for generating a grey scale model of a segment of an idealized curvilinear symbol by interpolating curvature at the periphery by assigning foreground pixel values to those pixels located entirely within said grey scale model of said segment of said idealized curvilinear symbol, assigning background pixel values to those pixels located entirely outside said grey scale model of said segment of said idealized curvilinear symbol, and approximately pixel values for boundary pixels of said grey scale model of said segment of said idealized curvilinear symbol by selecting a number of points n, along an arc of said idealized curvilinear symbol that is smaller than the total number of points in said arc, connecting said points n, by straight lines to create an angular feature in each pixel boundary, computing the area of each such angular feature, and computing a grey scale level for each boundary pixel by scaling the grey value by the percentage of said pixel occupied by said angular feature;
b. means for generating a full size model by reflecting said grey scale model of said segment of an idealized curvilinear symbol around the axes of symmetry of said idealized curvilinear symbol;
c. means for searching a digitized image for the location of shapes corresponding to said full size model; and
d. means for generating subfeature models from said full size model. - View Dependent Claims (4, 5)
a. means for searching a digitized image for the location of shapes corresponding to said subfeature model;
b. means for returning x,y coordinates of locations found in said digitized image which correspond to said subfeature model;
c. means for assigning weighting values to said returned x,y coordinates corresponding to the likelihood that each coordinate will contribute usefully to the search, is capable of being computed at the time subfeature models are generated and minimized discontinuities by using the following formula;
-
-
5. The method of any of claims 1, 2 or 3 wherein the step of generating a subfeature model further comprises:
-
a. searching a digitized image for the location of shapes corresponding to said subfeature model;
b. returning x,y coordinates of locations found in said digitized image which correspond to said subfeature model;
c. assigning weighting values to said returned x,y coordinates corresponding to the likelihood that each coordinate will contribute usefully to the search, is capable of being computed at the time subfeature models are generated and minimizes discontinuities by using the following formula;
-
-
2. An apparatus for locating a curvilinear symbol comprising:
-
a. means for generating a grey scale model of a segment of an idealized curvilinear symbol by interpolating curvature at the periphery by assigning foreground pixel values to those pixels located entirely within said grey scale model of said segment of said idealized curvilinear symbol, assigning background pixel values to those pixels located entirely outside said grey scale model of said segment of said idealized curvilinear symbol, and approximating pixel values for boundary pixels of said grey scale model of said segment of said idealized curvilinear symbol by substituting triangles and rectangles for the area occupied by a boundary pixel containing an arc of said curvilinear feature, such that a proportional rectangle and a proportioned triangle represent a boundary pixel having entry and exit point points at opposite sides of said pixel and a proportional triangle represents a boundary pixel having entry and exit points on adjacent sides of said pixel, computing the area of said triangles and rectangles, computing the percentage of said boundary pixel by occupied by said area and assigning a grey value to said pixel corresponding to said percentage;
b. means for generating a full size model by reflecting said grey scale model of said segment of an idealized curvilinear symbol around the axes of symmetry of said idealized curvilinear symbol;
c. means for searching a digitized image for the location of shapes corresponding to said full size model; and
d. means for generating subfeature models from said full size model.
-
-
3. An apparatus for locating a curvilinear symbol comprising:
-
a. means for generating a grey scale model of a segment of an idealized curvilinear symbol by interpolating curvature at the periphery by assigning foreground pixel values to those pixels located entirely within said grey scale model of said segment of said idealized curvilinear symbol, assigning background pixel values to those pixels located entirely outside said grey scale model of said segment of said idealized curvilinear symbol, and approximately pixel values for boundary pixels of said grey scale model of said segment of said idealized curvilinear symbol by selecting a boundary pixel containing an arc of said idealized curvilinear symbol, locating entry and exit points of said arc in said boundary pixel, computing substituted shapes for said boundary pixel such that;
entry and exit points extending from opposite sides of said boundary pixel are represented by rectangles and triangles, whereby said exit points serve as vertices of a rectangle and a triangle tangent to each other;
entry and exit points extending from adjacent sides of said boundary pixel are represented by triangles having a vertex at said entry point and at said exit point, computing the area of said triangles and rectangles, and computing the proportion of said boundary pixel occupied by said area and assigning a grey value to said boundary pixel corresponding to said proportion;
b. means for generating a full size model by reflecting said grey scale model of said segment of an idealized curvilinear symbol around the axes of symmetry of said idealized curvilinear symbol;
c. means for searching a digitized image for the location of shapes corresponding to said full size model; and
d. means for generating subfeature models from said full size model.
-
-
6. An apparatus for locating a curvilinear symbol, comprising:
-
a. means for generating a grey scale model of an arc of an idealized curvilinear symbol;
b. means for interpolating curvature at the periphery of said arc;
c. means for reflecting said grey scale model of said arc around the axes of symmetry of said idealized curvilinear symbol to generate a full size model of said idealized curvilinear symbol;
d. means for generating a partial resolution model of said full size model;
e. means for generating a full resolution subfeature model from said full size model;
f. means for assigning coordinate axes weighting to each axis of each subfeature model;
g. means for defining a tolerance threshold for deviations from an idealized curvilinear symbol;
h. means for searching said digitized image using said partial resolution model to find a coarse location of a corresponding shape;
i. means for defining a region of interest within said digitized image using x,y coordinates of said coarse location;
j. means for searching said region of interest for the location of shapes corresponding to said subfeature model;
k. means for returning x,y coordinates for the locations of shapes corresponding to said subfeature model;
l. means for returning scores indicating the correlation between said shapes found and said subfeature model;
m. means for assigning axes weighting values to each axis of x,y coordinates returned for locations corresponding to said subfeature model;
n. means for assigning score weighting values for scores returned;
o;
means for summing the axis weighting values;
p. means for summing the score weighting values;
q. means for dividing the sum of the weighting values by said sum of the weights to produce weighted positions corresponding to said subfeature model;
r. means for discarding positions outside said tolerance thresholds;
s. means for computing the location of said curvilinear symbol from remaining weighted positions. - View Dependent Claims (7, 8)
a. means for computing the location of at least two x,y coordinate positions corresponding to two subfeature models opposite each other;
b. means for deriving a scale factor to be applied to a third subfeature model position;
c. means for reflecting said third subfeature model position about the diameter, using the computed scale factor.
-
-
9. A method for locating a curvilinear symbol comprising the steps of:
-
a. generate a grey scale model of a segment of an idealized curvilinear symbol by interpolating curvature at the periphery by assigning foreground pixel values to those pixels located entirely within said grey scale model of said segment of said idealized curvilinear symbol, assigning background pixel values to those pixels located entirely outside said grey scale model of said segment of said idealized curvilinear symbol, and approximating pixel values for boundary pixels of said grey scale model of said segment of said idealized curvilinear symbol by selecting a number of points, n, along an arc of said idealized curvilinear symbol that is smaller than the total number of points in said arc, connecting said points n, by straight lines to create an angular feature in each pixel boundary, computing the area of each such angular feature, and computing a grey scale level for each boundary pixel by scaling the grey value by the percentage of said pixel occupied by said angular feature;
b. generating a full size model by reflecting said grey scale model of said segment of an idealized curvilinear symbol around the axes of symmetry of said idealized curvilinear symbol;
c. searching a digitized image for the location of shapes corresponding to said full size model; and
d. generating subfeature models from said full size model.
-
-
10. A method for locating a curvilinear symbol comprising the steps of:
-
a. generating a grey scale model of a segment of an idealized curvilinear symbol by interpolating curvature at the periphery by assigning foreground pixel values to those pixels located entirely within said grey scale model of said segment of said idealized curvilinear symbol, assigning background pixel values to those pixels located entirely outside said grey scale model of said segment of said idealized curvilinear symbol, and approximately pixel values for boundary pixels of said grey scale model of said segment of said idealized curvilinear symbol by substituting triangles and rectangles for the area occupied by a boundary pixel containing an arc of said curvilinear feature, such that a proportioned rectangle and a proportioned triangle represent a boundary pixel having entry and exit point points at opposite sides of said pixel and a proportioned triangle represents a boundary pixel having entry and exit points on adjacent sides of said pixel, computing the area of said triangles and rectangles, computing the percentage of said boundary pixel by occupied by said area and assigning a grey value to said pixel corresponding to said percentage;
b. generating a full size model by reflecting said grey scale model of said segment of an idealized curvilinear symbol around the axes of symmetry of said idealized curvilinear symbol;
c. searching a digitized image for the location of shapes corresponding to said full size model; and
d. generating subfeature models from said full size model.
-
-
11. A method for locating a curvilinear symbol comprising the steps of:
-
a. generating a grey scale model of a segment of an idealized curvilinear symbol by interpolating curvature at the periphery by assigning foreground pixel values to those pixels located entirely within said grey scale model of said segment of said idealized curvilinear symbol, assigning background pixel values to those pixels located entirely outside said grey scale model of said segment of said idealized curvilinear symbol, and approximately pixel values for boundary pixels of said grey scale model of said segment of said idealized curvilinear symbol by selecting a boundary pixel containing an arc of said idealized curvilinear symbol, locating entry and exit points of said arc in said boundary pixel, computing substitute shapes for said boundary pixel such that;
entry and exit points extending from opposite sides of said boundary pixel are represented by rectangles and triangles, whereby said exit points serve as vertices of a rectangle and a triangle tangent to each other;
entry and exit points extending from adjacent sides of said boundary pixel are represented by triangles having a vertex at said entry point and at said exit point, computing the area of said triangles and rectangles, and computing the proportion of said boundary pixel occupied by said area and assigning a grey value to said boundary pixel corresponding to said proportion;
b. generating a full size model by reflecting said grey scale model of said segment of an idealized curvilinear symbol around the axes of symmetry of said idealized curvilinear symbol;
c. searching a digitized image for the location of shapes corresponding to said full size model; and
d. generating subfeature models from said full size model.
-
-
12. A method for locating a curvilinear symbol, comprising:
-
a. generating a grey scale model of an arc of an idealized curvilinear symbol;
b. interpolating curvature at the periphery of said arc;
c. reflecting said grey scale model of said arc around the axes of symmetry of said idealized curvilinear symbol to generate a full size model of said idealized curvilinear symbol;
d. generating a partial resolution model of said full size model;
e. generating a full resolution subfeature model from said full size model;
f. assigning coordinate axes weighting to each axis of each subfeature model;
g. defining a tolerance threshold for deviations from an idealized curvilinear symbol;
h. searching said digitized image using said partial resolution model to find a coarse location of a corresponding shape;
i. defining a region of interest within said digitized image using x,y coordinates of said coarse location;
j. searching said region of interest for the location of shapes corresponding to said subfeature model;
k. returning x,y coordinates for the locations of shapes corresponding to said subfeature model l. returning scores indicating the correlation between said shapes found and said subfeature model;
m. assigning axes weighting values to each axis of x,y coordinates returned for locations corresponding to said subfeature model;
n. assigning score weighting values for scores returned;
o;
summing the axis weighting values;
p. summing the score weighting values;
q. dividing the sum or the weighting values by said sum of the weights to produce weighted positions corresponding to said subfeature model;
r. discarding positions outside said tolerance thresholds;
s. computing the location of said curvilinear symbol from remaining weighted positions. - View Dependent Claims (13, 14)
a. computing the location of at least two x,y coordinate positions corresponding to two subfeature models opposite each other;
b. deriving a scale factor to be applied to a third subfeature model position;
c. reflecting said third subfeature model position about the diameter, using the computed scale factor.
-
Specification