Share Email Print

Journal of Electronic Imaging

Pattern matching using the blur hit-miss transform
Author(s): Dan S. Bloomberg; Luc M. Vincent
Format Member Price Non-Member Price
PDF $20.00 $25.00
cover GOOD NEWS! Your organization subscribes to the SPIE Digital Library. You may be able to download this paper for free. Check Access

Paper Abstract

The usefulness of the hit–miss transform (HMT) and related transforms for pattern matching in document image applications is examined. Although the HMT is sensitive to the types of noise found in scanned images, including both boundary and random noise, a simple extension, the blur HMT, is relatively robust. The noise immunity of the blur HMT derives from its ability to treat both types of noise together, and to remove them by appropriate dilations. In analogy with the Hausdorff metric for the distance between two sets, metric generalizations for special cases of the blur HMT are derived. Whereas Hausdorff uses both directions of the directed distances between two sets, a metric derived from a special case of the blur HMT uses just one direction of the directed distances between foreground and background components of two sets. For both foreground and background, the template is always the first of the directed sets. A less-restrictive metric generalization, where the disjoint foreground and background components of the template need not be set complements, is also derived. For images with a random component of noise, the blur HMT is sensitive only to the size of the noise, whereas Hausdorff matching is sensitive to its location. It is also shown how these metric functions can be derived from the distance functions of the foreground (FG) and background (BG) of an image, using dilation by the appropriate templates. The blur HMT can be used as a fast heuristic to avoid more expensive integer-based matching techniques, and it is implemented efficiently with boolean image operations. The FG and BG images are dilated with structuring elements that depend on image noise and pattern variability, and the results are then eroded with templates derived from patterns to be matched. Subsampling the patterns on a regular grid can improve speed and maintain match quality, and examples are given that indicate how to explore the parameter space. Truncated matches give the same result as full erosions, are much faster, and for some applications can be performed at a restricted set of locations.

Paper Details

Date Published: 1 April 2000
PDF: 11 pages
J. Electron. Imag. 9(2) doi: 10.1117/1.482734
Published in: Journal of Electronic Imaging Volume 9, Issue 2
Show Author Affiliations
Dan S. Bloomberg, Xerox Palo Alto Research Ctr. (United States)
Luc M. Vincent, Xerox Palo Alto Research Ctr. (United States)

© SPIE. Terms of Use
Back to Top