Theoretical Impact of Image Algebra
Algebras of images have been developed and used by many researchers.
The need for precision and concision in image processing and computer
vision image manipulation has led to these developments.
The two specific algebraic systems having the most coherent and formal
descriptions, however, are mathematical morphology and the
image algebra developed by Ritter, et. al., at the University of Florida,
and referred to herein simply as image algebra.
Thge primary distinctions between mathematical morphology and image algebra
are two-fold:
- Images are modeled in mathematical morphology as sets of points in
the n-dimensional Cartesian product space of the reals.
Image algebra, on the other hand, models an image as a maps from a
set of points drawn from an underlying topological space, into
values in an underlying algebraic set.
- All operations of mathematical morphology can be generated from
compositions of two operations, namely dilation and erosion
(corresponding resp. to Minkowski addition and substraction).
Image algebra, on the other hand, generates its operations from
compositions and reductions of operations on the underlying point
and value sets.
Development of image algebra at the University of Florida began in 1984 under
the sponsorship of Eglin Air Force Base and DARPA.
Since that time, numerous results (summarized below) have been derived.
The salient properties of image algebra, however, can be summarized
briefly as follows:
- Image algebra is a translucent notation in which all image processing
and computer vision image transformations may be described.
- Image algebra is based upon well-defined, well-understood mathematical
systems, thus algorithms expressed in image algebra are amenable to
formal analysis.
- Numerous Image Processing and Computer Vision algorithms have been
expressed in image algebra and a compendium
(The Image
Algebra Handbook) describes many of the algorithms and their
variants in image algebra.
- Image algebra is amenable to computer implementation if appropriate
restrictions on pointset topology and value sets are made.
A C++ object library implementing a rich
image algebra subset has been developed and is available for
distribution. Previous implementations have involved preprocessors
for image algebra in FORTRAN and Ada, and interpretive implementations
of image algebra in *lisp (for the Connection Machine CM2) and
C.
The development of a coherent image algebra has led to a number of
theoretical advances in image processing and computer vision. What follows
is a brief chronological summary of milestones in the theoretical
foundations of image algebra at the University of Florida.
- 1982: Foundational Investigation
-
- G.X. Ritter, Development of a Mathematical Foundation
for Cellular Image Processing, Technical Report (34 pages),
USAF/SCEEE Contract AF F49C20-82-0035, Air Force Armament
Division, Eglin AFB.
-
- 1983: Initial Definition of IA Operations Formulated and Presented
-
- G.X. Ritter, S.S. Chen, Image Processing Architectures
and Languages, Proc. IEEE International
Conference on Computer Design: VLSI in Computers, New York, pp.
723--726, 1983.
York, pp. 723-726, 1983.
- G.X. Ritter, The Language of Massively Parallel Image
Processing Computers, Proceedings ACM
SE Conference on Friendly Systems: 1984-2001?, Atlanta, GA,
1984.
- G.X. Ritter, An Algebra of Images, Proc. Conference on
Intelligent Systems and
Machines, Oakland Univ., Rochester, MI, pp. 333-338,
1984.
- Image Algebra research supported by AFOSR (Mathematical
Foundation for Cellular Image Processing - AFOSR Grant
000-82-0065) and Eglin (summer consultant).
- 1984: Establishment of Image Algebra Foundation
-
- Image Processing Language Development Contract (Phase I),
Air Force / DARPA, F08635-84-C-0295.
- G.X. Ritter, P.D. Gader, R. Smith, A Synopsis of Common
Image Transforms and Techniques, TR #1, Image Algebra
Project (203 pages), AF/DARPA Contract F0863-84-0295,
AFATL/DLMI, Eglin AFB, FL, 1984.
- Development of Image Arithmetic and Generalized Convolutions
(linear convolutions, additive max and min convolutions,
multiplicative max and min convolutions)
- Development of translation variant templates
- 1985: Refinement of Image Algebra Foundation
-
- Image Processing Language Development Contract (Phase II),
Air Force / DARPA, F08635-85-C-0295.
- G.X. Ritter, On the Foundation of a Common Image
Processing Algebra, AFATL-TR-84-45 (35 pages), Defense
Technical Information Center, Alexandria VA, 1985.
- G.X. Ritter, P.D. Gader, R. Smith, Image Algebra: Basic
Operators and Relations, TR #2, Image Algebra Project
(64 pages),1985.
1985.
- G.X. Ritter, P.D. Gader, Image Algebra: Processing
Equivalence, TR #3, Image Algebra Project (40 pages),
1985.
- G.X. Ritter, P.D. Gader, Image Algebra Implementation
on Cellular Array Computers, Proc. IEEE
Comp. Soc. Workshop on Computer Architecture for Pattern
Analysis and Image Database Management, pp. 430-437,
Miami Beach, 1985.
- 1986: Image Algebra Comes of Age
-
- P. Gader's Ph.D. Dissertation establishes the following results:
- Isomorphism between Image Subalgebra and Linear Algebra
- Isomorphism between Image Subalgebra and Polynomial
Algebra
- Necessary and Sufficient Conditions for the Local
Decomposition of Templates in the Linear Domain
- Conditions for the Invertability of Templates
- Image Algebra Versions of FFT's
- Derivation of Local FFT's
- 1987: Further Breakthroughs and Publications of Image Algebra
Development
-
- G.X. Ritter, P.D. Gader, J.L. Davidson, Image
Algebra, AFATL-TR-86-79 (151 pages), Defense Technical
Information Center, Alexandria VA, 1987
- G.X. Ritter and P.D. Gader, Image Algebra Techniques
For Parallel Image Processing, Journal
of Parallel and Distributive Computing, 4(5), pp. 7-44,
1987
- G.X. Ritter and J.N. Wilson, Image Algebra: A Unified
Approach to Image Processing, SPIE
Proc. on Medical Imaging, Newport Beach, CA, 1987
- G.X. Ritter, M. Shrader-Frechette, J.N. Wilson, Image
Algebra: A Rigorous and Translucent Way of Expressing All Image
Processing Operations, Proc. SPIE
Southeastern Technical Symposium on Optics, Electro-Optics and
Sensors, Orlando, FL, 116-121, 1987
- M. Shrader-Frechette, G.X. Ritter, Registration and
Rectification of Images using Image Algebra,Proc. IEEE
Southeastcon, Tampa, FL, pp. 16--19, 1987
- G.X. Ritter and J.N. Wilson, The Image Algebra in a
Nutshell, Proceedings First Intern.
Conference on Computer Vision, IEEE Computer Society,
London, England, pp. 641-645, 1987
- G.X. Ritter, J.L. Davidson, and J.N. Wilson, Beyond
Mathematical Morphology, (Invited Paper),Proc. SPIE 1987
Cambridge Symposium on Optics in Medicine
and Visual Image Processing, Cambridge, MA, pp. 260-269,
1987
- J.N. Wilson, G.X. Ritter, Functional Specification of
Neighborhoods in an Image Processing Language,Proc. SPIE
Advances in Image Processing
Conference, The Hague, Netherlands, 1987
- G.X. Ritter, J.N. Wilson, and J.L. Davidson, Data
Compression of Multispectral Images,SPIE Proc. 31st Annual
Intl. Tech.Symposium on Optical and Optoelec. App.
Sci. and Eng., San Diego, CA, pp. 58--64, 1987
- G.X. Ritter, J.N. Wilson, and J.L. Davidson, Standard
Image Processing Algebra Document, Phase II, TR#7,
AFATL/DLMI, Eglin AFB, FL, 1987
- G.X. Ritter and J.N. Wilson, Image Algebra: A New
Approach to Algorithm Development, (Invited Paper),IEEE
Computer Society 16th Workshop on Applied Imagery Pattern
Recognition, pp. 39-83, Washington DC, Oct. 1987
- 1988: Further Breakthroughs and Publications of Image Algebra
Development
-
- Development of Multivalued Image Algebra and the Forward
Convolution Operator. Mapping of Image Algebra to the CM2
Connection Machine in *lisp.
- G.X. Ritter, J.N. Wilson, and J.L. Davidson, Image
Algebra Application to Multisensor and Multidata Image
Manipulation, SPIE Tech. Symposium on Optics, Electro-Optics,
and Sensors, Orlando, FL, pp. 2--7, 1988
- J.N. Wilson, G.X. Ritter, and R. Fischer, Implementation
and use of an Image Processing Algebra for Programming
Massively Parallel Machines, IEEE 2nd Symposium of the
Frontiers of Massively Parallel Computation,
George Mason Univ., Fairfax, VA, pp. 12-31, 1988
- 1989: Start of KBAD Program --- Fine Tuning of Definitions of
Operators and Operands
-
- Development Template Arithmetic (Global Reduce Operations, etc.)
and Feature Extraction Transforms in IA.
- Connection between IA and Artificial Neural Networks Established
- G.X. Ritter, D. Li, Image Algebra and its Relationship
to Neural Networks, SPIE Tech.
Symposium on Optics, Electro-Optics, and Sensors,
Orlando, FL, 1989
- G.X. Ritter, J.N. Wilson, J.L. Davidson, Image Algebra
Application to Feature Measurement Extraction,SPIE Proc. 31st
Annual Intl. Tech. Symposium on Optical
and Optoelec. App. Sci. and Eng., San Diego, CA, 1989
- J. L. Davidson's Ph.D. Dissertation which establishes the
following:
- Isomorphism between an Image Subalgebra and Lattice
Theory (MiniMax Algebra)
- Isomorphism between an Image Subalgebra and Mathematical
Morphology
- Development of Eigenvalue Problems in Nonlinear Image
Algebra
- Necessary and Sufficient Conditions for Template
Decompositions in the Nonlinear Domain
-
- 1990: Continuation of KBAD Program
-
- D. Li's Ph.D. Dissertation which establishes the following:
- The Field of Recursive Image Algebra
- Definition of Recursive Templates
- Operations between Images and Recursive Templates
- Operations between Recursive Templates
- IA Formulation of Linear and Nonlinear Recursive
operations
- Methods for decomposing Separable Templates
- Methods for decomposing Symmetric Convex Templates
- Methods for decomposing Spherical Templates
- Methods for decomposing Symmetric Convex Templates
- Use of Max-Polynomials in Template Decomposition
- Establishment of the annual SPIE sponsored Image Algebra and
Morphological Image Processing Conference
- J.L. Davidson, G.X. Ritter, A Theory of
Morphological Neural Networks, OE/LASE 90 Optics,
Electro-optics, and Laser Appl. in Sci. and Eng.
(SPIE), Los Angeles, CA, pp. 378--388, 1990
- G.X. Ritter, J.N. Wilson, J.L Davidson, Image Algebra:
An Overview, Computer Vision, Graphics,
and Image Processing, 49(3), pp. 297-331, 1990
- D. Li, G.X. Ritter, Recursive Operations in Image
Algebra, SPIE Proceedings on Image
Algebra and Mathematical Morphology, Vol. 1350, San
Diego, CA, 1990
- J.L. Davidson, G.X. Ritter, Recursion and Feedback in
Image Algebra SPIE's 19th AIPR Workshop
on Image Understanding in the 90's, Wash., D.C., Vol.
1406, October, 1990
- D. Li, G.X. Ritter, Decomposition of Separable and
Symmetric Convex Templates, SPIE
Proceedings on Image Algebra and Mathematical
Morphology, Vol. 1350, San Diego, CA, 1990
- Zohra Manseur' Ph.D. Dissertation which establishes the following:
- Several General Methods for the Inversion and
Decomposition of Convolution Operators
- Best Results for decomposing Templates into Templates
- Necessary and Sufficient Conditions for Separability
of Variant Templates
- Use of LU factorization and Grbner bases in Template
Decomposition
- Inversion of von Neumann Templates
- 1991-1992: Further research results
-
- Wei Z. Kitto's Ph.D. Dissertation investigates image algebra on
hexagonal lattices --- specifically hexagonal template
decomposition
- New view of images as functions whose graphs represent the data
structures associated with the images. This provides a more
powerful perspective of IA and image processing in
general.
- Many techniques and transforms such as image interpolation
techniques and spatial transforms can now be expressed in
terms simple composition
of functions instead of exotic generalized convolutions
(Chapter 4 of
Image
Algebra with Applications).
- New results in image-to-graph transforms
- Development of the Minimax Eigenvector Decomposition (MED)
Transform
- Development of the Generalized Matrix Product