DOCUMENT IMAGING

Pattern matching using the blur hit–miss transform

[+] Author Affiliations
Dan S. Bloomberg, Luc Vincent

Xerox Palo Alto Research Center, Palo Alto, California?94304

J. Electron. Imaging. 9(2), 140-150 (Apr 01, 2000). doi:10.1117/1.482734
History: Received July 30, 1997; Revised Feb. 21, 2000; Accepted Mar. 10, 2000
Text Size: A A A

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. © 2000 SPIE and IS&T.

© 2000 SPIE and IS&T

Citation

Dan S. Bloomberg and Luc Vincent
"Pattern matching using the blur hit–miss transform", J. Electron. Imaging. 9(2), 140-150 (Apr 01, 2000). ; http://dx.doi.org/10.1117/1.482734


Figures

Tables

Access This Article
Sign in or Create a personal account to Buy this article ($20 for members, $25 for non-members).

Some tools below are only available to our subscribers or users with an online account.

Related Content

Customize your page view by dragging & repositioning the boxes below.

Related Proceedings Articles

Related Book Chapters

Topic Collections

PubMed Articles
Advertisement
  • Don't have an account?
  • Subscribe to the SPIE Digital Library
  • Create a FREE account to sign up for Digital Library content alerts and gain access to institutional subscriptions remotely.
Access This Article
Sign in or Create a personal account to Buy this article ($20 for members, $25 for non-members).
Access This Proceeding
Sign in or Create a personal account to Buy this article ($15 for members, $18 for non-members).
Access This Chapter

Access to SPIE eBooks is limited to subscribing institutions and is not available as part of a personal subscription. Print or electronic versions of individual SPIE books may be purchased via SPIE.org.