Abstract
This paper describes a graph-based approach to image processing, intended for use with images obtained from sensors having space variant sampling grids. The connectivity graph (CG) is presented as a fundamental framework for posing image operations in any kind of space variant sensor. Partially motivated by the observation that human vision is strongly space variant, a number of research groups have been experimenting with space variant sensors. Such systems cover wide solid angles yet maintain high acuity in their central regions. Implementation of space variant systems pose at least two outstanding problems. First, such a system must be active, in order to utilize its high acuity region; second, there are significant image processing problems introduced by the non-uniform pixel size, shape and connectivity. Familiar image processing operations such as connected components, convolution, template matching, and even image translation, take on new and different forms when defined on space variant images. The present paper provides a general method for space variant image processing, based on a connectivity graph which represents the neighbor-relations in an arbitrarily structured sensor. We illustrate this approach with the following applications: (1) Connected components is reduced to its graph theoretic counterpart. We illustrate this on a logmap sensor, which possesses a difficult topology due to the branch cut associated with the complex logarithm function. (2) We show how to write local image operators in the connectivity graph that are independent of the sensor geometry. (3) We relate the connectivity graph to pyramids over irregular tessalations, and implement a local binarization operator in a 2-level pyramid. (4) Finally, we expand the connectivity graph into a structure we call a transformation graph, which represents the effects of geometric transformations in space variant image sensors. Using the transformation graph, we define an efficient algorithm for matching in the logmap images and solve the template matching problem for space variant images. Because of the very small number of pixels typical of logarithmic structured space variant arrays, the connectivity graph approach to image processing is suitable for real-time implementation, and provides a generic solution to a wide range of image processing applications with space variant sensors.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.References
Dana Ballard and Christopher Brown.Computer Vision. Prentice-Hall, 1982.
Aijaz A. Baloch and Allen M. Waxman. A neural system for behavioral conditioning of mobile robots.International Joint Conference on Neural Networks, pages 723–728, June 1990.
Benjamin B. Bederson.A miniature space-variant active vision system: Cortex-I. PhD thesis, New York University, Courant Institute, 1992.
Benjamin B. Bederson. A miniature space-variant active vision system: Cortex-I. Technical Report 266, New York University, Computer Science, Robotics Research, June 1992.
Benjamin B. Bederson, Richard S. Wallace, and Eric L. Schwartz. A miniaturized active vision system. Technical Report 255, New York University, Computer Science, Robotics Research, October 1991.
Benjamin B. Bederson, Richard S. Wallace, and Eric L. Schwartz. Calibration of the spherical pointing motor. InSPIE Conference on Intelligent Robots and Computer Vision, November 1992.
Benjamin B. Bederson, Richard S. Wallace, and Eric L. Schwartz. A miniature pan-tilt actuator: The spherical pointing motor. Technical Report 264, Courant Institute, NYU, April 1992.
Benjamin B. Bederson, Richard S. Wallace, and Eric L. Schwartz. A miniaturized active vision system. In11th International Conference on Pattern Recognition, August 1992.
Benjamin B. Bederson, Richard S. Wallace, and Eric L. Schwartz. Two miniature pantilt devices. InIEEE International Conference on Robotics and Automation, May 1992.
C. Braccini, G. Gambardella, G. Sandini, and V. Tagliasco. A model of the early stages of the human visual system: Functional and topological transformations performed in the peripheral visual field.Biological Cybernetics, pages 57–58, 1982.
David Casasent and Demetri Psaltis. Position, rotation, and scale invariant optical correlation.Applied Optics, 15(7):1795–1799, July 1976.
G. M. Chaikin and C. F. R. Weiman. Image processing system. U.S. Patent No. 4,267,573, May 1981.
N. Deo.Graph Theory with Applications to Engineering and Computer Science. Prentice-Hall, 1974.
Eric L. Schwartz (ed.). Computational neuroscience: Applications of computer graphics and image processing to two and three dimensional modeling of the functional architecture of the visual cortex.IEEE Computer Graphics and Applications, 8(4), July 1988.
Mark S. Franzblau. Log mapped focal driven procedural rendering: an application of the complex log map to ray tracing. Master's thesis, Courant Institute, New York University, 1991.
J. Frazier and R. Nevatia. Detecting moving objects from a moving platform. InIEEE International Conference on Robotics and Automation, May 1992.
B.K. P. Horn.Robot Vision. MIT Press, 1986.
Hurlbert and T. Poggio. Do computers need attention?Nature, 321:651–652, June 1986.
G. Kreider, J. Van der Spiegel, I. Born, C. Claeys, I. Debusschere, G. Sandini, P. Dario, and F. Fantini. A retina like space variant ccd sensor.SPIE/Charge-Coupled Devices and Solid State Optical Sensors, 1242, 1990.
Marc Levoy and Ross Whitaker. Gaze-directed volume rendering.Computer Graphics, 24(2):217–223, 1991.
R. A. Messner and H. H. Szu. An image processing architecture for real time generation of scale and rotation invariant patterns.Computer Vision, Graphics, and Image Processing, 31:50–66, 1985.
A. Montanvert, P. Meer, and A. Rosenfeld. Hierarchical image analysis using irregular tesselations.IEEE Transactions on Pattern Analysis and Machine Intelligence, 13(4):307–316, 1991.
C. Narathong, R.M. Inigo, J.F. Doner, and E.S. McVey. Motion-vision architectures. InProceedings of Computer Vision and Pattern Recognition, pages 411–416, 1988.
Ping-Wen Ong.Image Processing, Pattern Recognition and Attentional Algorithms in a Space-Variant Active Vision System. PhD thesis, New York University, Courant Institute, 1992.
Ping-Wen Ong, Richard S. Wallace, and Eric L. Schwartz. Space-variant optical character recognition. In11th International Conference on Pattern Recognition, August 1992.
Pietro Perona and Jitendra Malik. Scale-space and edge detection using anisotropic diffusion.IEEE Transactions on Pattern Analysis and Machine Intelligence, 12(7):629–639, 1990.
Alan Rojer and Eric L. Schwartz. Design of a space-variant sensor having a complex log geometry. In10th International Conference on Pattern Recognition Volume 2, 1990.
Alan S. Rojer.Space-variant computer vision with a complex-logarithmic sensor geometry. PhD thesis, New York University, Courant Institute, 1989.
A. Rosenfeld. Connectivity in digital pictures.Journal of the ACM, 17(l):146–160, 1970.
Azriel Rosenfeld and Avinash C. Kak.Digital Picture Processing, 2nd Edition. Academic Press, 1982.
H. Samet. Region representation: quadtrees from boundary codes.CACM, 23:163–170, March 1980.
Giulio Sandini, Paolo Dario, and I. Debusschere. Active vision based on space-variant sensing. In5th International Symposium on Robotics Research, August 1989.
Gulio Sandini, Paolo Dario, and I. Debusschere. The use of an anthropomorphic visual sensor for motion estimation and and object tracking. InProc. OSA Topical Meeting on Image Understanding, 1989.
Eric L. Schwartz. Spatial mapping in primate sensory perception.Biological Cybernetics, 25, 1977.
Akio Shio. An automatic thresholding algorithm based on an illumination-independent contrast measure. InConference on Computer Vision and Pattern Recognition, pages 632–637, 1989.
Michael J. Swain and Markus Stricker Ed. Promising directions in active vision. Technical report, University of Chicago, Chicago, August 1991.
Akira Tonomo, Muneo Iida, and Yukio Kobayashi. A tv camera system which extracts feature points for non-contact eye movement detection.SPIE Optics, Illumination and Image Sensing for machine vision, 1194, 1989.
Douglas B. Tweed and Tutis Vilis. The superior colliculus and spatiotemporal translation in the saccadic system.Neural Networks, 3: 75–86, 1990.
J. van der Spiegel et. al. A foveated retina-like sensor using ccd technology. In C. Mean and M. Ismail, editors,Analog VLSI Implementations of Neural Networks. Kluwer, 1989.
Richard S. Wallace, Benjamin B. Bederson, and Eric L. Schwartz. Voice bandwidth visual communication through logmaps: The telecortex. InProceedings of the IEEE Workshop on Applications of Computer Vision, November 1992.
Richard S. Wallace, Ping-Wen Ong, Benjamin B. Bederson, and Eric L. Schwartz. Connectivity graphs for space-variant image processing. Technical Report VAI-1, Vision Applications, Inc., 1991.
Richard S. Wallace, Ping-Wen Ong, Benjamin B. Bederson, and Eric L. Schwartz. Space-variant image processing. Technical Report 256, New York University, Computer Science, Robotics Research, October 1991.
Richard S. Wallace, Ping-Wen Ong, Benjamin B. Bederson, and Eric L. Schwartz. Connectivity graphs for space-variant active vision. In George A. Bekey and Kenneth Y. Goldberg, editors,Neural Networks in Robotics, pages 347–374. Kluwer Academic Publishers, 1992.
Carl Weiman and George Chaikin. Logarithmic spiral grids for image processing and display.Computer Graphics and Image Processing, 11, 1979.
Carl F. R. Weiman. 3-d sensing with polar exponential sensor arrays.SPIE Conference on Digital and Optical Shape Representation and Pattern Recognition, April 1988.
Carl F. R. Weiman. Exponential sensor array geometry and simulation. InSPIE Conference on Digital and Optical Shape Representation and Pattern Recognition, April 1988.
Carl F. R. Weiman. Polar exponential sensor arrays unify iconic and hough space representation. InSPIE: Intelligent Robots and Computer Vision VIII: Algorithms and Techniques, pages 832–841, 1989.
Hiroyuki Yamaguchi, Muneo Iida, Akira Tonomo, and Fumio Kishino. Picture quality of a large field visual field display with selective high resolution in foveal vision region.ITEJ Technical Report, 14(12), 1990. in Japanese.
Hiroyuki Yamaguchi, Akira Tonomo, and Yukio Kobayashi. Proposal for a large field visual display employing eye movement tracking.SPIE Optics, Illumination and Image Sensing for machine vision, 1194, 1989.
Isamu Yorizawa and Makato Kosugi. Depth image reconstruction from motion vectors using cortical image mapping. InProceedings of 1991 Electronics, Information and Communications Society Fall National Conference, 1991. in Japanese.
Author information
Authors and Affiliations
Additional information
This research was supported by DARPA/ONR #N00014-90-C-0049 and AFOSR Life Sciences #88-0275. Please address all correspondence to Richard S. Wallace, NYU Robotics Research Laboratory, 715 Broadway 12th Floor, New York, NY 10003. This report is copyright ©1993 by the authors. This report is a revised draft of a report published as New York University Courant Institute of Mathematical Sciences Computer Science Technical Report (No. 589 and Robotics Report No. 256), October, 1991. Last revised October.
Rights and permissions
About this article
Cite this article
Wallace, R.S., Ong, PW., Bederson, B.B. et al. Space variant image processing. Int J Comput Vision 13, 71–90 (1994). https://doi.org/10.1007/BF01420796
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01420796