Journal of Applied Mathematics
Volume 2 (2002), Issue 1, Pages 23-50
doi:10.1155/S1110757X02111107
The complexity of retina operators
Société de Calcul Mathématique, SA, 111 Faubourg Saint Honoré, Paris 75008, France
Received 8 November 2001
Copyright © 2002 Bernard Beauzamy. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
Abstract
An artificial retina is a plane circuit, consisting of a matrix
of photocaptors; each has its own memory, consisting in a small
number of cells (3 to 5), arranged in parallel planes. The
treatment consists in logical operations between planes, plus
translations of any plane: they are called “elementary
operations” (EO). A retina operator (RO) is a transformation of
the image, defined by a specific representation of a Boolean
function of n variables (n is the number of neighboring cells
taken into account). What is the best way to represent an RO by
means of EO, considering the strong limitation of memory? For
most retina operators, the complexity (i.e., the number of EO
needed) is exponential, no matter what representation is used,
but, for specific classes, threshold functions and more generally
symmetric functions, we obtain a result several orders of
magnitude better than previously known ones. It uses a new
representation, called “Block Addition of Variables.” For
instance, the threshold function T 25,12 (find if at least 12
pixels are at 1 in a square of 5×5) required 62 403 599
EO to be performed. With our method, it requires only 38 084
operations, using three memory cells.