The complexity of retina operators

[摘要] An artificial retina is a plane circuit, consisting of a matrixof photocaptors; each has its own memory, consisting in a smallnumber of cells (3 to 5), arranged in parallel planes. Thetreatment consists in logical operations between planes, plustranslations of any plane: they are called “elementaryoperations” (EO). A retina operator (RO) is a transformation ofthe image, defined by a specific representation of a Booleanfunction ofnvariables(nis the number of neighboring cellstaken into account). What is the best way to represent an RO bymeans of EO, considering the strong limitation of memory? Formost retina operators, the complexity (i.e., the number of EOneeded) is exponential, no matter what representation is used,but, for specific classes, threshold functions and more generallysymmetric functions, we obtain a result several orders ofmagnitude better than previously known ones. It uses a newrepresentation, called “Block Addition of Variables.” Forinstance, the threshold functionT 25,12(find if at least 12pixels are at 1 in a square of5×5) required 62 403 599EO to be performed. With our method, it requires only 38 084operations, using three memory cells.

[学科分类] 应用数学