Fast techniques for searching images using the Hausdorff distance
First Claim
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.
4 Assignments
0 Petitions
Accused Products
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.
46 Citations
23 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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9)
-
-
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. - View Dependent Claims (11, 12, 13, 14, 15, 16)
-
-
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. - View Dependent Claims (18, 19, 20, 21, 22)
-
-
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.
-
Specification