Distributed vision with smart pixels - Fey, Dietmar; Reichenbach, Marc; Fekete, Sandor; Komann, Marcus; Kröller, Alexander; Schmidt, Christiane (Proc. of the 25th Annual ACM Symposium on Computational Geometry, 2009)
We study a problem related to computer vision: How can a éld 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 éld 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(√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). © 2009 ACM.
UnivIS-Import:2015-04-16:Pub.2009.tech.IMMD.IMMD3.distri
Keywords: Distributed algorithms; Distributed vision; Principal component analysis; Sublinear algorithms; Sweepline algorithms