ALGORITHMS

Fast parallel shrinking to residues

[+] Author Affiliations
Richard W. Hall

University of Pittsburgh, Department of Electrical Engineering, Pittsburgh, Pennsylvania?15261

J. Electron. Imaging. 8(4), 446-456 (Oct 01, 1999). doi:10.1117/1.482713
History: Received May 6, 1998; Revised June 15, 1999; Accepted June 18, 1999
Text Size: A A A

Abstract

The problem of shrinking the connected components of binary images to small residues is addressed. A new parallel algorithm is presented with the lowest known worst case time complexity as measured by iteration counts, i.e., ⌊(nc+nr)/2⌋ iterations where the foreground of the image is contained within a rectangular region of size nc×nr pixels. The new algorithm also demonstrates superior average iteration counts in comparison with other shrinking algorithms on test images. The new algorithm uses a fully parallel application of an operator with an 8 pixel support. It reduces all connected components in any two-dimensional (2D) binary image to certain small 1, 2, or 3 pixel residues. It is potentially useful for component counting, as a fundamental step in connected component labeling algorithms implemented with fine grain realizations in 2D mesh computing architectures, and in other applications requiring preservation of foreground topology (connectivity). © 1999 SPIE and IS&T.

© 1999 SPIE and IS&T

Citation

Richard W. Hall
"Fast parallel shrinking to residues", J. Electron. Imaging. 8(4), 446-456 (Oct 01, 1999). ; http://dx.doi.org/10.1117/1.482713


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.

Topic Collections

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.