skip to main content
10.1145/1542362.1542410acmconferencesArticle/Chapter ViewAbstractPublication PagessocgConference Proceedingsconference-collections
research-article

Distributed vision with smart pixels

Published: 08 June 2009 Publication History

Abstract

We study a problem related to computer vision: How can a field of sensors compute higher-level properties of observed objects deterministically in sublinear time, without accessing a central authority? This issue is not only important for real-time processing of images, but lies at the very heart of understanding how a brain may be able to function. In particular, we consider a quadratic field of n "smart pixels" on a video chip that observe a B/W image. Each pixel can exchange low-level information with its immediate neighbors. We show that it is possible to compute the centers of gravity along with a principal component analysis of all connected components of the black grid graph in time O(sqrt(n)), by developing appropriate distributed protocols that are modeled after sweepline methods. Our method is not only interesting from a philosophical and theoretical point of view, it is also useful for actual applications for controling a robot arm that has to seize objects on a moving belt. We describe details of an implementation on an FPGA; the code has also been turned into a hardware design for an application-specific integrated circuit (ASIC).

References

[1]
K. Asanovic, R. Bodik, B. C. Catanzaro, J. J. Gebis, P. Husbands, K. Keutzer, D. A. Patterson, W. L. Plishker, J. Shalf, S. W. Williams, and K. A. Yelick. The landscape of parallel computing research: A view from Berkeley. Technical Report UCB/EECS-2006-183, EECS Department, University of California, Berkeley, Dec 2006.
[2]
B. Awerbuch. Optimal distributed algorithms for minimum weight spanning tree, counting, leader election, and related problems.In STOC '87: Proceedings of the Nineteenth Annual ACM Symposium on Theory of Computing, pages 230--240, New York, NY, USA, 1987. ACM.
[3]
B. Awerbuch, B. Berger, L. Cowen, and D. Peleg. Fast distributed network decompositions and covers. Journal of Parallel and Distributed Computing, 39:105--114, 1996.
[4]
D. H. Ballard and C. M. Brown. Computer Vision. Prentice Hall, 1982.
[5]
C. Chaplin. Modern times, 1936.
[6]
B. Chazelle. Triangulating a simple polygon in linear time. Discrete & Computational Geometry, 6:485--524, 1991.
[7]
B. Chazelle. Who says you have to look at the input? The brave new world of sublinear computing. In SODA '04: Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, page 141, Philadelphia, PA, USA, 2004. Society for Industrial and Applied Mathematics.
[8]
B. Chazelle, D. Liu, and A. Magen. Sublinear geometric algorithms. SIAM J. Comput., 35(3):627--646, 2005.
[9]
M. Elkin. A faster distributed protocol for constructing a minimum spanning tree. J. of Computer and System Sciences, 72(8):1282--1308, 2006.
[10]
A. Ferencz, E. G. Learned-Miller, and J. Malik. Learning hyper-features for visual identification. In Neural Information Processing Systems, 2004.
[11]
D. Fey, L. Hoppe, A. Loos, M. Foertsch, and H. Zimmermann. Parallel optical interconnects with mixed-signal OEIC and fibre arrays for high-speed communication. In Proceedings of SPIE, volume 5453 of Micro-Optics, VCSELs and Photonic Interconnects, Strasbourg, France, 2004. Photonics Europe.
[12]
R. Goldstein. Herb score, pitcher derailed by line drive, dies at 75. International Herald Tribune, Nov 12, 2008.
[13]
R. C. Gonzalez and R. E. Woods. Digital image processing. Prentice-Hall, third edition, 2008.
[14]
I. T. Jolliffe. Principal Component Analysis. Springer, second edition, 2002.
[15]
M. Komann, A. Kroeller, C. Schmidt, D. Fey, and S. P. Fekete. Emergent algorithms for centroid and orientation detection in high-performance embedded cameras. In CF '08: Proceedings of the 2008 conference on Computing frontiers, pages 221--230, New York, NY, USA, 2008. ACM.
[16]
D. Marr. Vision: A computational investigation into the human representation and processing of visual information. Freeman, 14th edition, 2000.
[17]
D. Peleg. Distributed computing: a locality-sensitive approach. Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 2000.
[18]
G. Ryle. The concept of mind. University of Chicago Press, 1949.
[19]
J. Shlens. A tutorial on principal component analysis, 2005.
[20]
B. Steckemetz. Quality control of ready-made food. In DAGM-Symposium, pages 153--159, 1995.
[21]
M. E. Wall, A. Rechtsteiner, and L. M. Rocha. Singular value decomposition and principal component analysis. In Daniel P. Berrar, Werner Dubitzky, and Martin Granzow, editors, A Practical Approach to Microarray Data Analysis, pages 91--109. Springer, 2003.

Cited By

View all
  • (2018)Distributed camouflage for swarm robotics and smart materialsAutonomous Robots10.1007/s10514-018-9717-642:8(1635-1650)Online publication date: 21-Feb-2018
  • (2018)Distributed Camouflage for Swarm Robotics and Smart MaterialsDistributed Autonomous Robotic Systems10.1007/978-3-319-73008-0_25(359-371)Online publication date: 14-Mar-2018
  • (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
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
SCG '09: Proceedings of the twenty-fifth annual symposium on Computational geometry
June 2009
426 pages
ISBN:9781605585017
DOI:10.1145/1542362
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: 08 June 2009

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. distributed algorithms
  2. distributed vision
  3. principle component analysis
  4. sublinear algorithms
  5. sweepline algorithms

Qualifiers

  • Research-article

Conference

SoCG '09

Acceptance Rates

Overall Acceptance Rate 625 of 1,685 submissions, 37%

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 camouflage for swarm robotics and smart materialsAutonomous Robots10.1007/s10514-018-9717-642:8(1635-1650)Online publication date: 21-Feb-2018
  • (2018)Distributed Camouflage for Swarm Robotics and Smart MaterialsDistributed Autonomous Robotic Systems10.1007/978-3-319-73008-0_25(359-371)Online publication date: 14-Mar-2018
  • (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
  • (2011)Geometric computation with smart pixelsProceedings of the twenty-seventh annual symposium on Computational geometry10.1145/1998196.1998239(285-286)Online publication date: 13-Jun-2011
  • (2011)Realizing real-time centroid detection of multiple objects with marching pixels algorithms on programmable customizing hardwareConcurrency and Computation: Practice and Experience10.1002/cpe.179324:16(1821-1839)Online publication date: 6-Jul-2011
  • (2010)Realizing Real-Time Centroid Detection of Multiple Objects with Marching Pixels AlgorithmsProceedings of the 2010 13th IEEE International Symposium on Object/Component/Service-Oriented Real-Time Distributed Computing Workshops10.1109/ISORCW.2010.26(98-107)Online publication date: 4-May-2010

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