Fast techniques for searching images using the Hausdorff distance

• US 5,999,653 A
• Filed: 04/16/1996
• Issued: 12/07/1999
• Est. Priority Date: 01/19/1996
• Status: Expired due to Term

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Jaquith, Eric W., Rucklidge, William J.
• Primary Examiner(s): Au, Amelia
• Assistant Examiner(s): Prikockis, Larry J.
• Application Number:
  US08/633,240
• Time in Patent Office: 1,330 Days
• Field of Search: 382/226, 382/227, 382/228, 382/224, 382/308, 382/217, 382/218-221, 382/209, 382/257
• US Class Current: 382/227
• CPC Class Codes: G06V 10/757 Matching configurations of points or features

Abstract

Fast, low-overhead implementations of a powerful, reliable image matching engine based on the Hausdorff distance are disclosed. In one such implementation, a method is provided in which a processor receives two inputs. The first input is a pattern to be recognized in an image; the second, a digital image in which the pattern is to be recognized. The digital image is preprocessed with the processor using various morphological dilation operations so as to produce a set of preprocessed digital images. Thereafter, the processor performs a hierarchical search for the pattern in the digital image. The hierarchical search is performed over a search space, and includes a series of decisions, each decision indicating whether a portion of the search space can be eliminated from the search. Each decision is made by performing a plurality of comparisons between the pattern and the preprocessed digital images of the set and analyzing the results of these comparisons. Once the search is complete, the processor outputs a search outcome indicating, for example, whether (and where) the pattern has been found in the image. Any application domain wherein images are searched for instances of patterns can benefit from this invention. Document analysis applications provide one such domain.

Claims

1. A method comprising the steps of:

receiving as a first input to a processor a pattern to be recognized in an image;

receiving as a second input to the processor a digital image in which the pattern is to be recognized;

performing a preprocessing of the digital image with the processor so as to produce a set of preprocessed digital images, the preprocessing including a plurality of morphological dilation operations, wherein at least one of the plurality of morphological dilation operations calculates a preprocessed digital image representative of a thresholded distance transform of the digital image;

performing a hierarchical search for the pattern in the preprocessed digital image with the processor, the hierarchical search producing an outcome, the hierarchical search being performed over a search space, the hierarchical search comprising a plurality of decisions, each decision indicating whether a portion of the search space can be eliminated from the search, each decision being made by performing a plurality of comparisons between the pattern and the preprocessed digital images of the set to produce a plurality of comparison results and analyzing the comparison results thus produced; and

outputting from the processor an outcome of the hierarchical search.

2. The method of claim 1 wherein the comparisons performed during the hierarchical search step are nonpointwise comparisons.

3. The method of claim 1 wherein:

the pattern comprises a plurality of words of binary data, each word comprising a fixed number of bits, each bit having a value selected from the group 0 or 1; and

each comparison performed during the hierarchical search step comprises a wordwise comparison operation, the wordwise comparison operation providing a comparison between an entire word of binary data of the pattern and a portion of one of the preprocessed digital images, all the bits of the entire word being processed by the processor together during the wordwise comparison, without any individual consideration by the processor of the value of any individual bit of the entire word.

4. The method of claim 3 wherein the wordwise comparison operation comprises:

a logical AND operation performed on first and second operands, the first operand being the entire word, the second operand being a portion of one of the preprocessed digital images, the logical AND operation yielding a first result; and

a bit count operation performed on the first result, the bit count operation comprising a count of how many bits in the first result have a value of 1, the bit count operation yielding a second result.

5. The method of claim 1 wherein one of the morphological dilation operations of the plurality of morphological dilation operations used to calculate the thresholded distance transform comprises a morphological dilation with a circular structuring element.

6. The method of claim 5 wherein the circular structuring element has an associated radius, and additionally comprising the steps of:

accepting into the processor a threshold distance as an input value from the user; and

setting the radius of the circular structuring element with the processor according to the input value thus accepted.

7. The method of claim 1 wherein one of the morphological dilation operations of the plurality of morphological dilation operations comprises a morphological dilation with a rectangular structuring element.

8. The method of claim 7 wherein the rectangular structuring element has an associated linear dimension, the hierarchical search traverses a search tree having a plurality of levels, the preprocessing step includes a step of automatically determining a collection of parameter values associated with a level of the hierarchical search to be performed during the search step;

and additionally comprising the steps of;

computing with the processor a linear dimension value according to the parameter values of the collection; and

setting the linear dimension of the rectangular structuring element according to the linear dimension value thus computed.

9. The method of claim 1 wherein the comparisons performed during the hierarchical search step are performed in an order dependent on a density ordering of the pattern.

10. A method comprising the steps of:

receiving as a first input to a processor a pattern to be recognized in an image;

receiving as a second input to the processor a digital image in which the pattern is to be recognized;

performing a preprocessing of the digital image with the processor so as to produce a set of preprocessed digital images;

performing a hierarchical search for the pattern in the digital image with the processor, the hierarchical search producing an outcome, the hierarchical search being performed over a search space, the hierarchical search comprising a plurality of decisions, each decision indicating whether a portion of the search space can be eliminated from the search, each decision being made by performing a plurality of nonpointwise comparisons between the pattern and the preprocessed digital images of the set producing aplurality of comparison results and analyzing the comparison results thus produced, the comparisons for each decision being performed in an order dependent on a density ordering of the pattern, with the results of early comparisons for the decision being used to determine whether to perform later comparisons for the decision; and

outputting a result of the search from the processor.

11. The method of claim 10 wherein:

the pattern includes a plurality of pixel groups, each pixel group of the pattern having a population density; and

the density ordering comprises an ordering of the groups according to the population density of each group.

12. The method of claim 11 wherein the density ordering comprises an ordering of the groups according to decreasing population density, such that a first group precedes a second group in the ordering if and only if the population density of the first group is not less than the population density of the second group.

13. The method of claim 10 wherein the preprocessing step includes a plurality of morphological dilation operations.

14. The method of claim 13 wherein one of the morphological dilation operations of the plurality of morphological dilation operations comprises a morphological dilation with a circular structuring element.

15. The method of claim 13 wherein one of the morphological dilation operations of the plurality of morphological dilation operations comprises a morphological-dilation with a rectangular structuring element.

16. The method of claim 10 wherein the preprocessing step includes a thresholded distance transform operation.

17. A method comprising the steps of:

receiving as a first input to a processor a pattern to be recognized in an image;

receiving as a second input to the processor a digital image in which the pattern is to be recognized, the digital image comprising an array of image elements;

performing a dilation of the digital image with the processor so as to produce a dilated digital image;

determining with the processor from the dilated image a set of densities;

performing a nonhierarchical search for the pattern in the digital image with the processor, the search comprising a plurality of evaluations carried out to evaluate transformations of the pattern with respect to the digital image, each evaluation comprising a density checking test and optionally further comprising a plurality of comparisons between the pattern and the dilated digital image, the density checking test being carried out by the processor with reference to the set of densities, the plurality of comparisons between the pattern and the dilated digital image being performed if and only if the density checking test is passed; and

outputting a result of the search from the processor.

18. The method of claim 17 wherein the step of performing the dilation of the digital image comprises performing a plurality of morphological dilation operations.

19. The method of claim 18 wherein one of the morphological dilation operations of the plurality of morphological dilation operations comprises a morphological dilation with a circular structuring element.

20. The method of claim 17 wherein the step of performing the dilation of the digital image comprises performing a thresholded distance transform operation.

21. The method of claim 17 wherein the comparisons performed are non-pointwise comparisons.

22. The method of claim 21 wherein the comparisons of the plurality are performed in an order dependent on a density ordering of the pattern.

23. A system comprising:

a processor;

a memory operatively coupled to the processor;

a user interface operatively coupled to the processor;

first input means for receiving in the memory and making available to the processor a pattern to be recognized;

second input means for receiving in the memory and making available to the processor a digital image in which the pattern is to be recognized;

means for preprocessing the digital image with the processor by applying a plurality of morphological dilation operations to the digital image, thereby producing a set of preprocessed digital images representative of at least one thresholded distance transform of the digital image;

means for performing a hierarchical search for the pattern in the digital image with the processor, the hierarchical search producing an outcome, the hierarchical search being performed over a search space, the hierarchical search comprising a plurality of decisions, each decision indicating whether a portion of the search space can be eliminated from the search, each decision being made by performing a plurality of comparisons between the pattern and the preprocessed digital images of the set to produce a plurality of comparison results and analyzing the comparison results thus produced; and

means for outputting the search outcome by providing the search outcome from the processor to the user interface.