Constant-time hough transform on the processor arrays with reconfigurable bus systems | Computing Skip to main content
Springer Nature Link
Log in

Constant-time hough transform on the processor arrays with reconfigurable bus systems

Hough Transformation in konstanter Zeit auf Prozessor-Arrays mit rekonfigurierbarem Bussystem

  • Published:
Computing Aims and scope Submit manuscript

Abstract

We develop constant-time algorithms to compute the Hough transform on a processor array with a reconfigurable bus system (abbreviated to PARBS). The PARBS is a comptuation model which consists of a processor array and a reconfigurable bus system. It is a very powerful computation model in that many problems can be solved efficiently. In this paper, we introduce the concept of iterative-PARBS which is similar to the FOR-loop construct in sequential programming languages. The iterative-PARBS is a building block in which the processing data can be routed through it several times. We can think it as a “hardware subroutine”. Based on this scheme, we are able to explore constant-time Hough transform algorithms on PARBS. The following new results are derived in this study:

  1. 1)

    The sum ofn bits can be computed in O(1) times on a PARBS with O(n 1+ɛ) processors for any fixed ɛ>0.

  2. 2)

    The weights of each simple path of ann*n image can be computed in O(1) time on a 3-D PARBS with O(n 2+ɛ) processors for any fixed ɛ>0.

  3. 3)

    Thep angle Hough transform of ann*n image can be computed in O(1) time on a PARBS with O(p*n 2+ɛ) processors for any fixed ɛ>0 withp copies of the image pretiled.

  4. 4)

    Thep angle Hough transform of ann*n image can be computed in O(1) time on a PARBS with O(p*n 3) processors.

Zusammenfassung

Wir entwickeln Algorithmen, mit denen die Hough Transformation auf einem Prozessor-Array mit rekonfigurierbarem Bussystem (PARBS) in konstanter Zeit berechnet werden kann. PARBS ist ein Berechnungsmodell, das aus einem Prozessor-Array und einem rekonfigurierbaren Bussystem besteht. Es handelt sich dabei um ein mächtiges Berechnungsmodell, mit dem viele Probleme effizient gelöst werden können. In dieser Arbeit führen wir das Konzept eines iterativen PARBS ein, das dem FOR-Schleifen Konstrukt in sequentiellen Programmiersprachen ähnlich ist. Wir stellen es uns als “Hardware Unterprogramm” vor. Ausgehend von diesem Schema können wir Hough Transformationsalgorithmen mit konstanter Zeitkomplexität untersuchen. Folgende neue Ergebnisse werden in dieser Studie hergeleitet:

  1. 1)

    Die Summe vonn Bits kann in Zeitkpomplexität O(1) auf einem PARBS mit O(n 1+ɛ) Prozessoren berechnet werden (für jedes feste ɛ>0).

  2. 2)

    Die Gewichte jedes einfachen Weges einesn*n Bildes können in Zeitkpomplexität O(1) auf einem PARBS mit O(n 2+ɛ) Prozessoren berechnet werden (für jedes feste ɛ>0).

  3. 3)

    Diep Winkel Hough Transformation einesn*n Bildes kann in Zeitkpomplexität O(1) auf einem PARBS mit O(p*n 2+ɛ) Prozessoren berechnet werden (für jedes feste ɛ>0), wobeip Kopien des Bildes verwendet werden.

  4. 4)

    Diep Winkel Hough Transformation einesn*n Bildes kann in Zeitkpomplexität O(1) auf einem PARBS mit O(p*n 3) Prozessoren berechnet werden.

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

Explore related subjects

Discover the latest articles, news and stories from top researchers in related subjects.

References

  1. Champion, D. M., Rothstein, J.: Immediate parallel solution of the longest common subsequence problem. Proc. of the International Conference on Parallel Processing, pp. 70–77. Pennsylvania: Penn State Press 1987.

    Google Scholar 

  2. Chen, W. T., Liu, C. C., Fang, M. Y.: The design of an integrated parallel processing unit with a reconfigurable bus system. Proc. of the First Workshop on Parallel Processing, pp. 231–242. Taiwan: Hsinchu 1990.

    Google Scholar 

  3. Elgindy, H., Wegrowicz, P.: Selection on the reconfigurable mesh. Proc. of the International Conference on Parallel Processing, III, pp. 26–33. Boston: CRC Press 1991.

    Google Scholar 

  4. Fisher, A. L., Highnam, P. T.: Computing the Hough transform on a scan line array processor. IEEE Trans. Pattern Anal. Mach. Intell.11, 262–265 (1989).

    Article  Google Scholar 

  5. Furst, M., Saxe, J., Sipser, M.: Parity, circuits and polynomial time hierarchy. Proc. IEEE Foundations on Computer Science, pp. 260–270, 1981.

  6. Horowitz, E., Sahni, S.: Fundamentals of computer algorithms. Maryland: Computer Science Press, 1978.

    Google Scholar 

  7. Jenq, J. F., Sahni, S.: Reconfigurable mesh algorithms for the Hough transform. Proc. of the International Conference on Parallel Processing, III, pp. 34–41. Boston: CRC Press 1991.

    Google Scholar 

  8. Li, H., Lavin, M. A., Master, R. J. L.: Fast Hough transform: a hierarchical approach. Comput Vis. Graphics Image Proc.36, 139–161 (1986).

    Article  Google Scholar 

  9. Li, H., Maresca, M.: Polymorphic-torus network. Proc. of the International Conference on Parallel Processing, pp. 411–414. Pennsylvania: Penn State Press 1987.

    Google Scholar 

  10. Li, H., Maresca, M.: Polymorphic-torus network. IEEE Trans. ComputC-38, 1345–1351 (1989).

    Article  Google Scholar 

  11. Li, H., Maresca, M.: Polymorphic-Torus Architecture for Computer Vision. IEEE Trans. Pattern Anal. Mach. Intell.11, 233–243 (1989).

    Article  Google Scholar 

  12. Li, H., Stout, Q. F.: Reconfigurable SIMD massively parallel computers. Proc. IEEE79, 429–443 (1991).

    Article  Google Scholar 

  13. Little, J. J., Blelloch, G. E., Cass, T. A.: Algorithmic techniques for computer vision on a fine-grained parallel machine. IEEE Trans. Pattern Anal. Mach. Intell.11, 244–257 (1989).

    Article  Google Scholar 

  14. Maresca, M., Li, H.: Connection autonomy in SIMD computers: a VLSI implementation. J. Parallel Dist. Comput.7, 302–320 (1989).

    Article  Google Scholar 

  15. Miller, R., Prasanna, V. K., Reisis, D., Stout, Q. F.: Data movement Operations and applications on reconfigurable VLSI arrays. Proc. of the International Conference on Parallel Processing, pp. 205–208. Pennsylvania: Penn State Press 1988.

    Google Scholar 

  16. Miller, R., Stout, Q. F.: Efficient parallel convex hull algorithms. IEEE Trans. Comput.C-37, 1605–1618 (1988).

    Article  Google Scholar 

  17. Moshell, J. M., Rothstein, J.: Bus automata and immediate languages. Inform. Cont.40, 88–121 (1979).

    Article  Google Scholar 

  18. Pan, Y., Chuang, H. Y. H.: Parallel Hough transform algorithms on SIMD hypercube arrays. Proc. of the International Conference on Parallel Processing, III, pp. 83–86. Pennsylvania: Penn State Press 1990.

    Google Scholar 

  19. Rosenfeld, A., Ornelas, J., Jr., Hung, Y.: Hough transform algorithms for mesh-connected SIMD parallel processors. Comput. Vis. Graphics Image Proc.41, 293–305 (1986).

    Article  Google Scholar 

  20. Rothstein, J.: On the ultimate limitations of parallel processing. Proc. of the International Conference on Parallel Processing, pp. 206–212. California: IEEE Computer Society 1976.

    Google Scholar 

  21. Wang, B. F.: Configurational computation: a new algorithm design strategy on processor arrays with reconfigurable bus systems. Ph. D. Dissertation, The National Taiwan University, Taiwan, R.O.C. 1991.

    Google Scholar 

  22. Wang, B. F., Chen, G. H., Li, H.: Configurational computation: a new computation method on processor arrays with reconfigurable bus systems. Proc. of the International Conference on Parallel Processing, III, pp. 42–49. Boston: CRC Press 1991.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Computer Science, University of Illinois at Urbana-Champaign, 1304 West Springfield Avenue, 61801, Urbana, IL, USA

    S. -S. Lin

Authors
  1. S. -S. Lin
    View author publications

    You can also search for this author in PubMed Google Scholar

Additional information

This work was done while the author was visiting the University of Illinois at Urbana-Champaign. The author is with the Department of Information and Computer Education, National Taiwan Normal University, Taipei, Taiwan, R.O.C.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Lin, S.S. Constant-time hough transform on the processor arrays with reconfigurable bus systems. Computing 52, 1–15 (1994). https://doi.org/10.1007/BF02243392

Download citation

  • Received:

  • Issue Date:

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

AMS Subject Classifications

Key words

Search

Navigation