skip to main content
10.1145/1366230.1366271acmconferencesArticle/Chapter ViewAbstractPublication PagescfConference Proceedingsconference-collections
research-article

Emergent algorithms for centroid and orientation detection in high-performance embedded cameras

Published: 05 May 2008 Publication History

Abstract

Due to increasing speed and capabilities of production machines, the need for extremely fast and robust observation, classification, and error handling is vital to industrial image processing. We present an emergent algorithmic computing scheme and a corresponding embedded massively-parallel hardware architecture for these problems. They offer the potential to turn CMOS-camera-chips into intelligent vision devices which carry out tasks without help of a central processor, only based on local interaction of agents crawling on a large field of processing elements. It also constitutes a breakthrough for understanding sensor devices as a decentralized concept, resulting in much faster computation evading communication bottlenecks of classic approaches that become an ever-growing impediment to scalability. Here, in contrast, the number of agents and the field size and thus the computable image resolution is extremely scalable and therefore promises even more benefit with future hardware development. The results are based on novel algorithmic solutions allowing processor elements to compute center points, moments, and orientation of multiple image objects in parallel, which is of central importance to e.g. robotics. We finally present the algorithm's capabilities if realized in state-of-the-art FPGAs and ASICs.

References

[1]
A. Adamatzky. Reaction-diffusion navigation robot control: From chemical to VLSI analogic processors. IEEE Trans on Circuits and Systems, 51(5):926--938, 2004.
[2]
Gustavo Liñan Cembrano, Ángel Rodríguez-Vázquez, Servando Espejo-Meana, and Rafael Domínguez-Castro. Ace16k: A 128x128 focal plane analog processor with digital i/o. Int. J. Neural Syst., 13(6):427--434, 2003.
[3]
Marco Dorigo and Christian Blum. Ant colony optimization theory: a survey. Theor. Comput. Sci., 344(2-3):243--278, 2005.
[4]
D. Fey and D. Schmidt. Marching-pixels: a new organic computing paradigm for smart sensor processor arrays. In Proceedings of the 2nd conference on Computing Frontiers CF?05, ACM press, pages 1--9, 2005.
[5]
D. Fey and D. Schmidt. Marching pixels: A new organic computing principle for smart cmos camera chips. In Proc. Workshop on Self-Organization and Emergence ? Organic Computing and its Neighboring Disciplines, LNI, pages 123--130, 2005.
[6]
M. Halbach, R. Hoffmann, and L. Both. Optimal 6-state algorithms for the behavior of several moving creatures. In 7th Int. Conf. on Cellular Automata for Research and Industry, ACRI 2006, LNCS 4173, pages 571--581, 2006.
[7]
M. Komann and D. Fey. Realising emergent image pre-processing tasks in cellular-automaton-alike massively parallel hardware. Int. Journ. of Parallel, Emergent and Distributed Systems, 22:79--89, 2007.
[8]
Marcus Komann, Andreas Mainka, and Dietmar Fey. Comparison of evolving uniform, non-uniform cellular automaton, and genetic programming for centroid detection with hardware agents. In PaCT, volume 4671 of Lecture Notes in Computer Science, pages 432--441. Springer, 2007.
[9]
N. Minar, R. Burkhart, C. Langton, and M. Askenazi. The swarm simulation system: A toolkit for building multi-agent simulations. 1996.
[10]
Tamás Roska and Leon O. Chua. The cnn universal machine: 10 years later. Journal of Circuits, Systems, and Computers, 12(4):377--387, 2003.
[11]
B. Scheuermann. Fpga implementation of population-based ant colony optimization. Applied Soft Computing, 4:303--322, 2004.
[12]
H. Schmeck. Organic computing ? a new vision for distributed embedded systems. In Proc. of the Eighth IEEE International Symposium on Object-Oriented Real-Time Distributed Computing (ISORC 2005) Los Alamitos, CA, USA, pages 201--203, 2005.
[13]
T. De Wolf and T. Holvoet. Emergence versus self-organisation: Different concepts but promising when combined. Engineering Self Organising Systems: Methodologies and Applications, LNCS, 3464:1--15, 2005.
[14]
W. Wolf, B. Ozer, and T. Lv. Smart cameras as embedded systems. IEEE Computer, pages 48--53, 2002.

Cited By

View all
  • (2018)Distributed Object Characterization with Local Sensing by a Multi-robot SystemDistributed Autonomous Robotic Systems10.1007/978-3-319-73008-0_15(205-218)Online publication date: 14-Mar-2018
  • (2015)Framework for parameter analysis of FPGA-based image processing architectures2015 International Conference on Embedded Computer Systems: Architectures, Modeling, and Simulation (SAMOS)10.1109/SAMOS.2015.7363664(96-102)Online publication date: Jul-2015
  • (2014)Fast image processing for optical metrology utilizing heterogeneous computer architecturesComputers and Electrical Engineering10.1016/j.compeleceng.2013.09.00840:4(1158-1170)Online publication date: 1-May-2014
  • Show More Cited By

Index Terms

  1. Emergent algorithms for centroid and orientation detection in high-performance embedded cameras

        Recommendations

        Reviews

        Jason J. Corso

        Emergent image-analysis algorithms on embedded high-performance hardware have the potential to help machine vision scale to present difficult real-time application demands, but there is a long way to go before this potential will be realized. This research paper takes a step toward a practical parallel-embedded smart complementary metal-oxide-semiconductor (CMOS) camera for computing object moments (first and second order). The methodology builds emergent behavior based on distributed processor elements (PEs): one per pixel in the CMOS chip, and a construct called marching pixels (MPs) that march along the pixel array according to programmed logic specifically designed for moment calculation. Each PE has a minimum amount of memory and logic to store the local state of the calculation and guide the MPs in their calculation. All computation is done locally on PEs and their immediate neighbors; the object moments result from the emergent logic. Komann et al. extend their past work to handle concave objects and show that their logic will yield correct moment calculations. The algorithm scales with the object size rather than the pixel-array size. However, the immediate usefulness of the proposed algorithm is questionable: the method is limited in pixel resolution and cannot guarantee proper moment calculation in the case of multiple objects. The authors do project a plausible pixel resolution to be achieved within five years, but one guesses rival technology will also scale in the same length of time. Online Computing Reviews Service

        Access critical reviews of Computing literature here

        Become a reviewer for Computing Reviews.

        Comments

        Information & Contributors

        Information

        Published In

        cover image ACM Conferences
        CF '08: Proceedings of the 5th conference on Computing frontiers
        May 2008
        334 pages
        ISBN:9781605580777
        DOI:10.1145/1366230
        Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

        Sponsors

        Publisher

        Association for Computing Machinery

        New York, NY, United States

        Publication History

        Published: 05 May 2008

        Permissions

        Request permissions for this article.

        Check for updates

        Author Tags

        1. emergent algorithms
        2. image processing
        3. marching pixels
        4. massively-parallel
        5. object detection

        Qualifiers

        • Research-article

        Conference

        CF '08
        Sponsor:
        CF '08: Computing Frontiers Conference
        May 5 - 7, 2008
        Ischia, Italy

        Acceptance Rates

        Overall Acceptance Rate 273 of 785 submissions, 35%

        Upcoming Conference

        CF '25

        Contributors

        Other Metrics

        Bibliometrics & Citations

        Bibliometrics

        Article Metrics

        • Downloads (Last 12 months)1
        • Downloads (Last 6 weeks)0
        Reflects downloads up to 12 Feb 2025

        Other Metrics

        Citations

        Cited By

        View all
        • (2018)Distributed Object Characterization with Local Sensing by a Multi-robot SystemDistributed Autonomous Robotic Systems10.1007/978-3-319-73008-0_15(205-218)Online publication date: 14-Mar-2018
        • (2015)Framework for parameter analysis of FPGA-based image processing architectures2015 International Conference on Embedded Computer Systems: Architectures, Modeling, and Simulation (SAMOS)10.1109/SAMOS.2015.7363664(96-102)Online publication date: Jul-2015
        • (2014)Fast image processing for optical metrology utilizing heterogeneous computer architecturesComputers and Electrical Engineering10.1016/j.compeleceng.2013.09.00840:4(1158-1170)Online publication date: 1-May-2014
        • (2012)Heterogeneous computer architectures: An image processing pipeline for optical metrology2012 International Conference on Reconfigurable Computing and FPGAs10.1109/ReConFig.2012.6416755(1-8)Online publication date: Dec-2012
        • (2011)ASIC Architecture to Determine Object Centroids from Gray-Scale Images Using Marching PixelsAdvances in Wireless, Mobile Networks and Applications10.1007/978-3-642-21153-9_22(234-249)Online publication date: 2011
        • (2009)Distributed vision with smart pixelsProceedings of the twenty-fifth annual symposium on Computational geometry10.1145/1542362.1542410(257-266)Online publication date: 8-Jun-2009

        View Options

        Login options

        View options

        PDF

        View or Download as a PDF file.

        PDF

        eReader

        View online with eReader.

        eReader

        Figures

        Tables

        Media

        Share

        Share

        Share this Publication link

        Share on social media