Method and apparatus for detecting edge spectral features

• US 4,685,143 A
• Filed: 03/21/1985
• Issued: 08/04/1987
• Est. Priority Date: 03/21/1985
• Status: Expired due to Fees

• Current Assignee: Texas Instruments, Inc.
• Original Assignee: Texas Instruments, Inc.
• Inventors: Choate, William C.
• Primary Examiner(s): NOT, DEFINED
• Assistant Examiner(s): Skinner, A. Anne
• Application Number:
  US06/714,659
• Time in Patent Office: 866 Days
• Field of Search: 382/22, 382/21, 382/18, 382/25, 343/5 SA, 343/5 CM, 343/5 MM, 356/376
• US Class Current: 382/170
• CPC Class Codes: G06V 10/478 Contour-based spectral representations or scale-space representations, e.g. by Fourier analysis, wavelet analysis or curvature scale-space [CSS]

Abstract

Edge maps (40) derived from images are used to compute edge spectra (44), an edge spectrum having a plurality of components (41, 43) corresponding to the angular bins (60) of edge vectors having equal angular widths. Various feature detectors (56) process the edge spectrum to yield information identifying the image. A linear detector correlates a shifted prototype edge spectrum (45) to an input spectrum (44). Nonlinear detectors analyze edge spectra to detect mutually orthogonal edges and edge reversal features (90). Higher level logic (30) is used to select certain detected edge reversal features (90) as the ends of an object (16) depicted in the image.

Claims

1. An apparatus for the automatic recognition of images wherein characteristics of at least one prototype edge spectrum are compared with like characteristics at least partly derived from at least one input edge spectrum, the apparatus comprising;

means for retrieving an image;

means for deriving an edge map from said image, the edge map comprising an array of edge elements each having a direction;

means for computing an input edge spectrum at a selected point on said edge map from a surrounding neighborhood of edge elements, said edge spectrum being divided into a plurality of spectrum components, each component representing the number of edge elements within said neighborhood having a direction within a specific angular range;

a feature detector means for detecting mutally orthogonal edges present in said neighborhood and for correlating characteristics of an image prototype and an input spectrum;

wherein for a set of first angularly adjacent spectrum components, said feature detector means adds to each first component a second component roughly colinear to said first component, to obtain a plurality of first sums, wherein said feature detector means adds to a third component of said spectrum roughly orthogonal to said first component a fourth component of said spectrum roughly colinear to said third component, to obtain a plurlaity of second sums, wherein said feature detector means multiplies said first sums by said second sums to obtain a plurality of products, and wherein said feature detector means sums the products to obtain an orthogonal edge activity magnitude, said magnitude being used to determine the relative number of mutually orthogonal edges in said neighborhood; and

means for generating an indication of recognition of said image in response to the result from said feature detector means.

2. An apparatus for the automatic recognition of images wherein characteristics of at least one prototype edge spectrum are compared with like characteristics at least partly derived from at least one input edge spectrum, the apparatus comprising;

means for retrieving an image;

means for deriving an edge map from said image, the edge map comprising an array of edge elements each having a direction;

means for computing an input edge spectrum at a selected point on said edge map from a surrounding neighborhood of edge elements, said edge spectrum being divided into a plurality of spectrum components, each component representing the number of edge elements within said neighborhood having a direction within a specific angular range;

a feature detector means for detecting mutually orthogonal edges present in said neighborhood and for correlating characteristics of an input spectrum and an image prototype;

wherein said feature detector means multiplies the magnitude of each component of said spectrum by a magnitude of a second, roughly orthogonal angular component to obtain a plurality of products equal to the number of said components in said spectrum, and wherein the feature detector means sums said products to obtain an orthogonal edge activity magnitude for said neighborhood, said magnitude thereafter being used to determine whether said neighborhood contains a relatively large number of mutually orthogonal edges; and

means for generating an indication of recognition of said image in response to output from said detector.

3. An apparatus for the automatic recognition of images wherein characteristics of at least one prototype edge spectrum are compared with like characteristics at least partly derived from at least one input edge spectrum, the apparatus comprising:

means for retrieving an image;

means for deriving an edge map from said image, the edge map comprising an array of edge elements each having a direction;

means for computing an input edge spectrum at a selected point on said edge map from a surrounding neighborhood of edge elements, said edge spectrum being divided into a plurality of spectrum components, each component representing the number of edge elements within said neighborhood having a direction within a specific angular range;

a feature detector means for detecting edge directional reverals within said neighborhood, wherein said feature detector means finds a gap, said gap being comprised of a plurality of angularly adjacent components of said input spectrum each having a relatively low magnitude as compared to other components of said input spectrum angularly bounding said gap. wherein said feature detector means finds an edge reversal feature direction as a function of the average direction of said gap as rotated by 90°

;

, wherein said feature detector means calculates a size discriminant, the size discriminatn being a function of the total magnitude of said input spectrum and the number of pixels in said neighborhood, wherein said feature detector means calculates a symmetry discriminant, the symmetry discriminant being related to the difference in magnitude of said bounding components and wherein said feature detector means derives an edge reversal feature magnitude as a function of the size discriminant and the symmetry discriminant, the edge reversal feature magnitude and edge reversal direction being used to determine the existence and direction of an edge reversal feature within said neighborhood; and

means for generating an indication of recognition of said image.

4. The apparatus of claim 3, wherein:

said gap components have magnitudes near zero, the detector calculating subcomponents of said bounding components which are parallel to said edge reversal feature direction, said detector summing said subcomponents of those bounding components closer to one side of said gap into a first symmetry discriminant operand, said detector summing said subcomponents of the bounding components closer to a second side of said gap into a second symmetry discriminant operand;

said first and second symmetry discriminant operands thereafter being used to calculate said symmetry discriminant.

5. The apparatus of claim 3, wherein:

said edge directional reversal detector further includes a preliminary binary indicator;

said binary indicator comprising a number of addressed entries representable by n bits, where n is the number of angular bins, each angular bin corresponding to the angular range of edge directions represented by a spectrum component;

said spectrum being quantized into a binary address of n bits, each of said gap components of said input spectrum having a relatively low magnitude being represented by a first binary bit value, each of said components of said spectrum having a relatively high magnitude being represented by a second binary bit value, angularly adjacent components of said spectrum being represented by adjacent bits in the address;

each of said addressed entries having either a first or a second return bit, a first return bit being preassigned to an addressed entry only upon the corresponding type of spectrum having certain characteristics, said characteristics including only one plurality of adjacent spectrum components having a relatively low magnitude with respect to angularly bounding spectrum components, a second return bit being preassigned to an addressed entry where the corresponding quantized spectrum does not possess said characteristics;

said edge directional reversal feature detector not computing said edge reversal feature direction and computing said edge feature magnitude as zero if the binar indicator returns said second return bit.

6. The apparatus of claim 5, wherein:

said characteristics of said quantized spectrum necessary for said binary indicator to return said first return bit include;

only one instance of an integral number of adjacent gap components, said number ranging from (3n/8) to (n/2);

at least (3n/8) and no more than (5n/8) spectrum components having a nonzero magnitude; and

if said quantized spectrum has a number of nonzero spectrum components equal to (3n/8), the nonzero spectrum components occur in adjacent angular bins.

7. In an apparatus for the automatic recognition of images wherein edge maps are analyzed for the occurrence of orthogonal edge features, the improvement comprising:

means for storing an edge contained within a neighborhood of image pixels as an edge vector having magnitude and direction;

means for accumulating edge vectors into an edge spectrum for said neighborhood, said spectrum having a plurality of components equal to a number of angular bins, each bin being of equal angular width;

a feature detector means for detecting mutually orthogonal edges present within said neighborhood wherein said feature detector means, for a set of angularly adjacent first components, adds the magnitude of a roughly colinear second component to the magnitude of each of said first components to obtain a set of first sums wherein said feature detector means, for each of said first set of components, adds the magnitude of a thurd component orthogonal to one of said first components to the magnitude of a fourth component also orthogonal to said first component, to obtain a set of second sums and wherein said feature detector means calculates the minimum of each of said first sums and a corresponding second sum to obtain a set of orthogonal pair values, the feature detector means summing the orthogonal pair values to obtain an orthogonal edge activity feature magnitude for said neighborhood; and

means for using said orthogonal edge activity feature magnitude to determine the relative number of mutually orthogonal edges present in said neighborhood.

8. In an apparatus for the automatic recognition of images wherein edge maps are analyzed for the occurrence of edge reversal features, the improvement comprising:

means for storing a number of edges contained within a neighborhood of image pixels as corresponding edge vectors having magnitude and direction;

means for accumulating a plurality of said edge vectors into an input edge spectrum for said neighborhood, said spectrum being divided into a plurality of components equal to a number of angular bins, each bin being of equal angular width;

a feature detector means for detecting edge directional reversals within said neighborhood for finding a gap, said gap being a plurality of angularly adjacent components of said spectrum, said adjacent components having a relatively low magnitude with respect to other components of said spectrum angularly bounding said gap;

wherein said feature detector means finds a direction of an adge reversal feature as a function of the average of the angular bin number of each component in said gap as rotated by a number of bins equivalent to 90°

;

wherein said feature detector means calculates size discriminant as a function of the total magnitude of said spectrum and the number of pixels within the image area represented by said neighborhood, said function reaching its greatest value when said spectrum magnitude equals a predetermined fraction of said area pixel number;

wherein said feature detector means calculates a symmetry discriminant as a function of the difference of the magnitudes of said bounding components; and

wherein said feature detector means derives a nonzero edge reversal feature magnitude as a fuction of the size descriminant and the symmetry discriminant; and

means for using the edge reversal feature magnitude and direction to determine the existence and direction of an edge reversal within said neighborhood.

9. The apparatus of claim 8, wherein:

said feature detector means, after determining said direction of said edge reversal feature, determines the subcomponents of said bounding components which are parallel to said direction;

wherein said feature detector means sums said subcomponents of those bounding components closer to a first side of said gap into a first symmetry discriminant operand and sums the bounding components closer to a second side of said gap into a second symmetry discriminat operand;

wherein said symmetry discriminant is calculated as a function of the minimum of sayd symmetry discriminant operands divided by the maximum of said symmetry discriminant operands.

10. The apparatus of claim 8, wherein said feature detector means includes a preliminary binary indicator,

said binary indicator comprising a number of addressed entries representable by n binary bits, where n is the number of said angular bins;

said input spectrum being quantized into a binary address of n bits, each of said spectrum components having a relatively low magnitude being represented by a first binary bit value, each of said spectrum components having a relatively high magnitude being represented by a second binary bit value, angularly adjacent components being represented by adjacent bits in the address,

each of said addressed entries having either a first or a second return bit, a first return bit being preassingned to an addressed entry only upon a corresponding type of spectrum having certain characteristics, said characteristics including only one gap formed from three or more adjacent spectrum components, a second return bit being preassigned to an addressed entry where the corresponding type of spectrum does not possess said characteristics;

wherein said feature detector means does not compute said edge reversal feature direction, and computes said edge feature magnitude as zero if the binary indicator returns said second return bit.

11. An apparatus for the detection of opposite ends of an at least roughly symmetrical object contained within an image, comprising:

means for detecting and storing edge elements contained within a neighborhood of image pixels in said image, each said edge element being represented by an edge vector having magnitude and direction, said edge-storing means storing edge vectors for a plurality of neighborhoods within said image as an edge map;

means for accumulating said edge vectors for each neighborhood into an edge spectrum, each said spectrum being divided into a plurality of components equal to a number of angular bins, said bins being of equal angular width, each said component representing edge vectors having directions falling into said component'"'"'s angular bin;

a detector for processing the edge spectrum for each neighborhood to find an edge directional reversal feature therewithin;

means in said detector, for testing for a gap in each spectrum, said gap comprising a plurality of angularly adjacent components having relatively low magnitudes with respect to the components angularly bounding said gap;

means in said detector for testing said spectrum for certain other characteristics, deriving a direction for an edge reversal feature as a function of the average of the angular bin numbers of said gap components, as rotated by a number of bins equivalent to 90°

;

means in said detector for calculating a size discriminant for each edge reversal feature as a function of the total magnitude of said edge spectrum and the number of pixels in the corresponding neighborhood, and a symmetry discriminant related to the difference between the magnitudes of components bounding said gap;

said detector deriving an edge reversal feature magnitude as a function of said size discriminant and said symmetry discriminant;

said detector assigning a location to said edge reversal feature corresponding to the central pixel of the image neighborhood from which said edge reversal feature is derived;

said apparatus further comprising means for purging all edge reversal features having submaximal magnitudes within a predetermined area of said edge map to leave one maximum edge reversal feature per area, said means purging a plurality of said areas comprising said edge map;

means for choosing a first maximum edge reversal feature and searching for a second maximum edge reversal feature having an opposite direction, said first maximum edge reversal feature being purged if a corresponding second maximum edge reversal feature is not found, said last means testing each maximum edge reversal feature in like manner until only pairs of maximum edge reversal features of opposite directions remain; and

means for choosing one of said pairs of said maximal edge reversal features as the ends of said object.

12. The apparatus of claim 11, wherein:

said edge reversal feature detector includes a preliminary binary indicator comprising a number of addressed entries representable by n bits, where n is the number of angular bins in an edge spectrum;

said feature detector quantizing said spectrum into a binary address of n bits, each of said spectrum components having a relatively low magnitude being represented by a first binary bit value, each of said spectrum components having a relatively high magnitude being represented by a second binary bit Value, angularly adjacent spectrum components being represented by adjacent bits in the address,

each of said addressed entries having either a first or a second return bit, a first return bit being preassigned to an addressed entry only upon the corresponding quantized spectrum having certain characteristics, said characteristics including

only one instance of a gap comprising an integral number of adjacent spectrum components, said number ranging from (3n/8) to (n/2) of said input spectrum;

at least (3n/8) and no more than (5n/8) spectrum components leaving a nonzero magnitude; and

if said quantized spectrum has an integral number of nonzero spectrum components equal to (3n/8), the nonzero spectrum components occurring in adjacent angular bins;

a second return bit being preassigned to an addressed entry where the corresponding quantized spectrum does not possess said characteristics;

said edge directional reversal detector not computing said edge reversal feature direction and computing said edge feature magnitude as zero if the binary indicator returns said second return bit.

13. The apparatus of claim 11, wherein:

said means for choosing one of said pairs of said maximal edge reversal features as the ends of said object includes;

means for measuring the distance between the members of each pair;

means for comparing said distance to a predetermined distance value range; and

means for selecting one of said pairs as the ends of said object, the pair having a distance within said predetermined distance range.

14. The apparatus of claim 13, wherein said distance range is derived from a stored absolute distance range and the range of said object as found by a range finder.

15. In a method for the automatic recognition of images wherein characteristics derived from at least one prototype image are compared to like characteristics of at least one input spectrum constructed from an input image, the steps of;

storing selected characteristics of said prototype image;

retrieving an input image;

converting said input image into an edge map, the edge map comprising a plurality of edge vectors each having an edge magnitude and an edge direction;

computing an input edge spectrum at a selected point on said edge map from a surrounding neighborhood of edge vectors, said edge spectrum comprising a plurality of components each representing a number of edge vectors within said neighborhood, said edge vectors having directions falling within a specified angular range corresponding to one of said components;

shifting an edge spectrum of said prototype by an angular lag;

comparing said shifted prototype spectrum to said input spectrum;

for each shift, calculating a correlation factor equal to the vector inner product of said shifted prototype spectrum and said input spectrum minus the norm of the difference of the squares of said shifted prototype spectrum and said input spectrum; and

repeating the steps if shifting said prototype spectrum and calculating said correlation factor for a number of different consecutive angular lags equal to the number of components in said input spectrum and

selecting the largest of said correlation factors to produce a correlation magnitude between the compared edge spectra thereby detecting a structural feature of said image within said neighborhood; and

generating an indication of recognition of said image in response to said detection of said structural feature.

16. In a method for the automatic recognition of images wherein characteristics derived from at least one prototype image are compared to like characteristics of at least one input spectrum constructed from an input image, the steps of;

storing selected characteristics of said prototype image;

retrieving an input image;

converting said input image into an edge map, the edge map comprising a plurality of edge vectors each having an edge magnitude and an edge direction;

computing an input edge spectrum at a selected point on said edge map from a surrounding neighborhood of edge vectors, said edge spectrum comprising a plurality of components each representing a number of edge vectors within said neighborhood, said edge vectors having directions falling within a specified angular range corresponding to one of said components;

for a set of first, adjacent components comprising a first portion of said input spectrum, adding the magnitude of a roughly colinear second component to the magnitude of a first component, to obtain a plurality of first sums;

for each first componenet, adding the magnitude of a roughly orthogonal third component of said input spectrum to the magnitude of a fourth component also roughly orthogonal to said first component, to obtain a set of second sums;

thereafter taking the minimum of each of said first sums and a corresponding second sum to obtain a plurality of orthogonal edge pair values;

summing the edge pair values to obtain an orthogonal edge activity magnitude;

using said orthogonal edge activity magnitude to ascertain if said neighborhood has a relatively large number of mutually orthogonal edges, thereby detecting structural feature of said image within said neighborhood; and

generating an indication of recognition of said image in resonse to said detection of said structural feature.

17. In a method for the automatic recognition of images wherein characteristics derived from at least one prototype image are compared to like characteristics of at least one input spectrum constructed from an input image, the steps of:

storing selected characteristics of said prototype image;

retrieving an input image;

converting said input image into an edge map, the edge map comprising a plurality of edge vectors each having an edge magnitude and an edge direction;

suppressing those of said edge vectors having magnitudes below a selected threshold wherein the threshold is chosen so as to reject a constant percentage of said vectors for any edge map, thereby making said input spectrum independent of those changes of contrast with are uniform across said image;

computing an input edge spectrum at a selected point on said edge map from a surrounding neighborhood of edge vectors, not including the suppressed edge vectors, said edge spectrum comprising a plurality of components each representing a number of edge vectors within said neighborhood, said edge vectors having directions falling within a specified angular range corresponding to one of said components;

finding a gap composed of a plurality of angularly adjacent components of said input spectrum, each of said gap components having relatively low magnitudes as compared to other components angularly bounding said gap;

testing said input spectrum for the existence of other characteristics based on the magnitude and angular location of said spectrum components;

if said input spectrum passes said test, deriving an edge reversal feature direction as a function of an average of the direction of said gap as rotated by 90°

;

for each edge reversal feature direction, calculating an edge reversal feature magnitude as a function of a size discriminant and a symmetry discriminant, said size discriminant being a function of the total magnitude of said spectrum and the number of image pixels represented by said neighborhood, the symmetry discriminant being calculated as a function of the difference of the magnitudes of said bounding components;

using the edge reversal feature magnitude and the edge reversal feature direction to determine the existence and direction of an edge reversal within said neighborhood; and

generating an indication of recognition of said image in response to the determination of the edge reversal.

18. The method of claim 17, wherein said gap components have magnitudes near zero, said step of calculating an edge reversal feature magnitude further including the steps of:

calculating subcomponents of said bounding components which are parallel to said edge reversal feature direction;

summing said subcomponents of those bounding components closer to one side of said gap into a first symmetry discriminant operand;

summing said subcomponents of the components closer to a second side of said gap into a second symmetry discriminant operand; and

using said first and second symmetry discriminant operands to calculate said symmetry discriminant.

19. The method of claim 17, wherein the steps of testing said input spectrum for the existence of other characteristics includes the steps of:

forming a preliminary binary indicator having a number of addressed entries representable by the number of bits equal to the number of angular bins, each angular bin corresponding to a spectrum component and to a range of edge vector angles, each bin being of equal angular width;

preassigning a first return bit to an addressed entry only upon the corresponding type of spectrum having certain characteristics, including only one gap of three or more adjacent spectrum components;

preassigning a second return bit to an addressed entry where the corresponding type of spectrum does not possess said characteristics;

quantizing said edge spectrum into a binary address of n bits in being the number of angular bins, said address being formed by representing each of said components of said spectrum having a relatively low magnitude by a first binary bit value, representing each of said components of said spectrum having a relatively high magnitude by a second binary bit value and representing angularly adjacent components of said spectrum by adjacent bits in said address;

returning said first return bit or said second return bit upon accessing said binary address of said binary indicator corresponding to said quantized spectrum address; and

not computing said edge reversal feature direction and computing said edge reversal feature magnitude as zero if said binary indicator returns said second return bit.

20. The method of claim 19 wherein said step of forming said binary indicator includes the steps of:

preassigning said second return bit if said corresponding addressed spectrum type has more than one gap composed of three or more adjacent spectrum components;

preassigning said second return bit to an address where said corresponding spectrum type has a gap comprising a number of adjacent spectrum components outside the range of (3n/8) to (n/2);

preassigning said second return bit to an indicator address if said corresponding spectrum type does not have a range of nonzero spectrum components from (3n/8) to (5n/8); and

preassigning said second bit to an indicator address if the corresponding spectrum type has a number of nonzero spectrum components equal to (3n/8), but said nonzero spectrum components are not adjacent.

21. The method of claim 17, further including the steps of:

finding all edge reversal features within said edge map by moving said neighborhood to successive locations on said edge map;

purging all edge reversal features having submaximal magnitudes within each of several predetermined areas of said edge map to leave one maximum edge reversal feature per area;

choosing a first maximum edge reversal feature;

searching for a second maximum edge reversal feature having a direction opposite to said first maximum edge reversal feature;

if no said second maximum edge reversal feature is found, purging said first maximum edge reversal feature;

repeating the above said choosing, searching and purging steps until only pairs of maximum edge reversal features remain; and

choosing one of said pairs as the ends of an object depicted in said image.

22. The method of claim 21, wherein the step of choosing one of said pairs as the ends of said object further includes the steps of:

measuring the distance between the members of each of said pairs;

comparing said distance to a predetermined distance range; and

rejecting as said object ends any pair having a distance outside of said predetermined distance range.

23. The method of claim 22, further including the step of deriving said predetermined distance range from a stored absolute distance range and the range of said object as found by a range finder.

24. The method of claim 23, further including the steps of:

deriving the roll of said object with respect to the horizontal from the amount of angular shift of an edge spectrum for a portion of said object;

calculating the required edge feature directions of said ends from said roll; and

purging all edge reversal features not having one of said required edge reversal feature directions.