Computing convexity properties of images on a pyramid computer | Algorithmica Skip to main content
Springer Nature Link
Log in

Computing convexity properties of images on a pyramid computer

  • Published:
Algorithmica Aims and scope Submit manuscript

Abstract

We present efficient parallel algorithms for using a pyramid computer to determine convexity properties of digitized black/white pictures and labeled figures. Algorithms are presented for deciding convexity, identifying extreme points of convex hulls, and using extreme points in a variety of fashions. For a pyramid computer with a base ofn simple processing elements arranged in ann 1/2 ×n 1/2 square, the running times of the algorithms range from Θ(logn) to find the extreme points of a convex figure in a digitized picture, to Θ(n 1/6) to find the diameter of a labeled figure, Θ(n 1/4 logn) to find the extreme points of every figure in a digitized picture, to Θ(n 1/2) to find the extreme points of every labeled set of processing elements. Our results show that the pyramid computer can be used to obtain efficient solutions to nontrivial problems in image analysis. We also show the sensitivity of efficient pyramid-computer algorithms to the rate at which essential data can be compressed. Finally, we show that a wide variety of techniques are needed to make full and efficient use of the pyramid architecture.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. N. Ahuja and S. Swamy, Multiprocessor pyramid architectures for bottom-up image analysis,IEEE Trans. Pattern. Anal. Mach. Intell.,6 (1984), 463–474.

    Google Scholar 

  2. P. Hurt, The pyramid as a structure for efficient computation, inMultiresolution Image Processing and Analysis (A. Rosenfield, ed), Springer-Verlag, Berlin, 1984, pp. 6–35.

    Google Scholar 

  3. P. J. Burt and G. S. van der Wal, Iconic image analysis with the pyramid vision machine (PVM),Proc. IEEE 1987 Workshop on Pattern Analysis and Machine Intelligence, pp. 137–144.

  4. V. Cantoni, M. Ferretti, S. Levialdi, and R. Stefanelli, Papia: pyramidal architecture for parallel image processing,Proc. Computer Arithmetic Conf., Urgana, Ill. (1985).

    Google Scholar 

  5. Ph. Clermont and A. Merigot, Real time synchronization in a multi-SIMD massively parallel machine,Proc. IEEE 1987 Workshop on Pattern Analysis and Machine Intelligence, pp. 131–136.

  6. L. Dorst and W. M. Smeulders, Discrete representation of straight lines,IEEE Trans. Pattern Anal. Mach. Intell.,6 (1984), 450–463.

    MATH  Google Scholar 

  7. C. R. Dyer, A VLSI pyramid machine for hierarchical parallel image processing,Proc. IEEE Conf. on Pattern Recognition and Image Processing, (1981), pp. 381–386.

  8. C. R. Dyer, A Quadtree Machine for Parallel Image Processing, Tech. Report KSL 51, University of Illinois at Chicago Circle, 1981.

    Google Scholar 

  9. C. R. Dyer, Pyramid algorithms and machines, inMulticomputers and Image Processing Algorithms and Programs (K Preston and L. Uhr, eds.), Academic Press, New York, 1982, pp. 409–420.

    Google Scholar 

  10. C. R. Dyer and A. Rosenfeld, Parallel image processing by memory augmented cellular automata,IEEE Trans. Pattern. Anal. Mach. Intell.,3 (1981), 29–41.

    MATH  Google Scholar 

  11. H. Freeman and R. Shapira, Determining the minimal-area enclosing rectangle for an arbitrary closed curve,Comm. ACM,18 (1975), 409–413.

    Article  MATH  MathSciNet  Google Scholar 

  12. G. Fritschet al, EMSY85—the Erlangen multi-processor system for a broad spectrum of applications,Proc. 1983 Int. Conf. on Parallel Processing, pp. 325–330.

  13. M. Gaafar, Convexity verification, block-chords, and digital straight lines,Comput. Graphics Image Process.,6 (1977), 361–370.

    Article  Google Scholar 

  14. C. E. Kirn, On the cellular convexity of complexes,IEEE Trans. Pattern. Anal. Mach. Intell,3 (1981), 617–625.

    Article  Google Scholar 

  15. C. E. Kim, Digital convexity, straightness, and convex polygons,IEEE Trans. Pattern Anal Mach. Intell, 4 (1982), 618–626.

    MATH  Google Scholar 

  16. C. E. Kim, Three-dimensional digital line segments,IEEE Trans. Pattern Anal. Mach. Intell,5 (1983), 231–234.

    MATH  Google Scholar 

  17. C. E. Kim and A. Rosenfeld, Digital straight lines and convexity of digital regions,IEEE Trans. Pattern Anal Mach. Intell,4 (1982), 149–153.

    MATH  Google Scholar 

  18. C. E. Kim and A. Rosenfeld, Convex digital solids,IEEE Trans. Patterns Anal. Mach. Intell.,4 (1982), 612–618.

    MATH  Google Scholar 

  19. C. E. Kim and J. Sklansky, Digital and cellular convexity,Pattern Recognition,15 (1982), 359–387.

    Article  MATH  MathSciNet  Google Scholar 

  20. J. J. Koenderink and A. J. van Dorn, New type of raster scan preserves the topology of the image,Proc. IEEE,67 (1979); 1465–1466.

    Article  Google Scholar 

  21. A. Lempel and J. Ziv, Compression of two-dimensional data,IEEE Trans. Inform. Theory,32 (1986), 2–8.

    Article  Google Scholar 

  22. R. Miller, Ph.D. thesis, State University of New York at Binghamton, 1985.Pyramid Computer Algorithms.

    Google Scholar 

  23. R. Miller and Q. F. Stout, The pyramid computer for image processing,Proc. 7th Int. Conf. on Pattern Recognition, (1984), pp. 240–242.

  24. R. Miller and Q. F. Stout, Convexity algorithms for pyramid computers,Proc. 1984 Int. Conf. on Parallel Processing, pp. 177–184.

  25. R. Miller and Q. F. Stout, Geometric algorithms for digitized pictures on a mesh-connected computer,IEEE Trans. Pattern Anal. Mach. Intell.,7 (1985), 216–228.

    Google Scholar 

  26. R. Miller and Q. F. Stout, Data movement techniques for the pyramid computer,SIAM J. Comput.,16 (1987), 38–60.

    Article  MATH  MathSciNet  Google Scholar 

  27. R. Miller and Q. F. Stout, Some graph and image processing algorithms for the hypercube,Hypercube Multiprocessors 1987, SIAM, Philadelphia, Pa., pp. 418–425.

  28. R. Miller and Q. F. Stout, Simulating essential pyramids,IEEE Trans. Comput.,37 (1988), 1642–1648.

    Article  MathSciNet  Google Scholar 

  29. R. Miller and Q. F. Stout,Parallel Algorithms for Regular Architectures, MIT Press, Cambridge, Mass, 1992.

    Google Scholar 

  30. R. Miller, V. K. Prasanna Kumar, D. Reisis, and Q. F. Stout, Image computations on reconfigurable VLSI arrays,Proc. IEEE Conf. on Computer Vision and Pattern Recognition, (1988), pp. 925–930.

  31. R. Miller, V. K. Prasanna Kumar, D. Reisis, and Q. F. Stout, Data movement operations and applications on reconfigurable VLSI arrays,Proc. 1988 Int. Conf. on Parallel Processing, Vol. I, pp. 205–208.

  32. D. Nassimi and S. Sahni, Finding connected components and connected ones on a mesh-connected parallel computer,SIAM J. Comput.,9 (1980), 744–757.

    Article  MATH  MathSciNet  Google Scholar 

  33. A. Rosenfeld, Digital straight line segments,IEEE Trans. Comput.,23 (1974), 1264–1269.

    Article  MATH  MathSciNet  Google Scholar 

  34. A. Rosenfeld, Digital topology,Amer. Math. Monthly,86 (1979), 621–630.

    Article  MATH  MathSciNet  Google Scholar 

  35. A. Rosenfeld (ed.),Multiresolution Image Processing and Analysis, Springer-Verlag, Berlin, 1984.

    MATH  Google Scholar 

  36. A. Rosenfeld and C. E. Kim, How a digital computer can tell whether a line is straight,Amer. Math. Monthly,89 (1982), 230–235.

    Article  MATH  MathSciNet  Google Scholar 

  37. B. Sakoda, Parallel Construction of Polygonal Boundaries from Given Vertices on a Raster, Tech. Report CS81 1-21, Department of Computer Science, Pennsylvania State University, 1981.

  38. D. H. Schaeferet al, The PMMP—a pyramid of MPP processing elements,Proc. 18th Hawaiian Int. Conf. on Systems Science, Vol. 1 (1985), pp. 178–184.

    Google Scholar 

  39. D. H. Schaefer, P. Ho, J. Boyd, and C. Vallejos, The GAM pyramid, inParallel Computer Vision (L. Uhr, ed.), Academic Press, New Yorks, 1987, pp. 15–42.

    Google Scholar 

  40. J. Sklansky, Recognition of convex blobs,Pattern Recognition,2 (1970), 3–10.

    Article  Google Scholar 

  41. Q. F. Stout, Drawing straight lines with a pyramid cellular automation,Inform. Process. Lett.,15 (1982), 233–237.

    Article  MathSciNet  Google Scholar 

  42. Q. F. Stout, Sorting, merging, selecting, and filtering on tree and pyramid machines,Proc. 1983 Int. Conf. on Parallel Processing, pp. 214–221.

  43. Q. F. Stout, Pyramid computer algorithms optimal for the worst-case, inParallel Computer Vision (L. Uhr, Ed.), Academic Press, New York, 1987, pp. 147–168.

    Google Scholar 

  44. S. L. Tanimoto, Towards Hierarchical Cellular Logic: Design Considerations for Pyramid Machines, Tech. Report 81-02-01, Department of Computer Science, University of Washington, 1981.

  45. S. L. Tanimoto, Programming techniques for hierarchical parallel image processors, inMulticomputers and Image Processing Algorithms and Programs (K. Preston and L. Uhr, eds.), Academic Press, New York, 1982, pp. 421–429.

    Google Scholar 

  46. S. L. Tanimoto, Sorting, Histogramming, and Other Statistical Operations on a Pyramid Machine, Tech. Report 82-08-02, Department of Computer Science, University of Washington, 1982.

  47. S. L. Tanimoto and A. Klinger,Structured Computer Vision: Machine Perception Through Hierarchical Computation Structures, Academic Press, New Yorks, 1980.

    Google Scholar 

  48. C. D. Thompson and H. T. Kung, Sorting on a mesh-connected parallel computer,Comm. ACM,20 (1977), 263–271.

    Article  MATH  MathSciNet  Google Scholar 

  49. G. T. Toussaint, Pattern recognition and geometrical complexity,Proc. 5th Int. Conf. on Pattern Recognition, (1980), pp. 1324–1347.

  50. L. Uhr, Layered “recognition cone” networks that preprocess, classify, and describe,IEEE Trans. Comput.,21 (1972), 758–768.

    Article  MATH  Google Scholar 

  51. L. Uhr,Algorithm-Structured Computer Arrays and Networks, Academic Press, New York, 1984.

    MATH  Google Scholar 

  52. J. D. Ullman,Computational Aspects of VLSI, Computer Science Press, Rockville, Md., 1984.

    MATH  Google Scholar 

  53. K. Voss and R. Klette, On the Maximum Number Edges of Convex Digital Polygons Included into a Square, Forschungsergebnisse Nr. N/82/6, Friedrich-Schiller Universitat, Jena, 1982.

Download references

Author information

Authors and Affiliations

  1. Department of Computer Science, State University of New York, 226 Bell Hall, 14260, Buffalo, NY, USA

    Russ Miller

  2. Department of Electrical Engineering and Computer Science, University of Michigan, 48109-2122, Ann Arbor, MI, USA

    Quentin F. Stout

Authors
  1. Russ Miller
    View author publications

    You can also search for this author inPubMed Google Scholar

  2. Quentin F. Stout
    View author publications

    You can also search for this author inPubMed Google Scholar

Additional information

Communicated by Frank Dehne.

This research was partially supported by National Science Foundation Grants MCS-83-01019, DCR-8507851, DCR-8608640, IRI-8800514 and an Incentives for Excellence Award from the Digital Equipment Corporation.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Miller, R., Stout, Q.F. Computing convexity properties of images on a pyramid computer. Algorithmica 6, 658–684 (1991). https://doi.org/10.1007/BF01759066

Download citation

  • Received:

  • Revised:

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF01759066

Key words