Cellular Model for Image Processing and Shape Recognition

This application illustrates the use of Morphogenesis as a computational model for image processing.

What is Morphogenesis?
Morphogenesis is the process by which shape is generated. The term is commonly used in Embryology to refer to the generation of shape in organisms. However, biological morphogenesis is not limited to embryology. It is an endless process by which organisms modify their shape continuously through their lives [1].

A large number of applications in Medical Image Processing and Analysis are related with biological shape. Understanding Morphogenesis helps to address the essential aspects of the description, analysis and recognition of biological shape needed for medical applications.

The biological basis of morphogenesis are related with information encoded in DNA and instantiated by molecular interactions between proteins. These protein interactions modify cellular behavior and produce emergent multi-cellular phenomena that result in the formation of tissues and organs with particular shapes [2].

What is the Purpose of this Application?
This application shows how to use the itk::Mesh class for implementing an image analysis application.

The itk::Mesh class is used here as a support for representing a biological tissue. Every node of the mesh is associated with a biological cell. Cells reproduce by division, migrate and communicate with their peers by exchanging molecular signals. Based on the information obtained from the substrate and from neighbors, cells make decisions and execute specific portions of their genetic program. A dynamic mesh (defined by using the itk::DefaultDynamicMeshTraits) is used in this application in order to support the insertion of new biological cells and the removal of dead cells.

NOTE: There is also an itk::Cell class that should not be confused with a biological cell. The itk::Cell represents a N-Dimensional region of space in the itk::Mesh.

The sequence of images below illustrate the execution of the Morphogenesis application for a species that is sensitive to pressure. In the first image a single egg-cell is created. This cell reproduces by division and give rise to a cell population. Pressure exerted by neighbor pushes cells and results in the expansion of the cellular colony.

Cells are colored according to pressure. Blue cells are in low pressure zone while red cells are located in a high pressure zone.

Input Image Output Image Output Image
Output Image Output Image Output Image

How Can This Be Used for Images Analysis?
One of the characteristics of image processing is it suitability for distributed processing. This characteristic has been exploited by Cellular Automata approaches to image processing. The historic evolution of Cellular Automata have left the wrong impression that they have to be restricted to a regular grid and that they have to use uniform transition rules during their evolution. These apparent restrictions have only been the consequence of the reduced capabilities of computers in the 60's to 80's [3][4].

Cell populations can be used for image analysis by letting them grow on top of an image. The image is assimilated to a chemical substrate in which the cells lay. The behavior of cells can be programmed in order to react to the content of the substrate (the image) and the state of the neighbor cells.

The following example shows another species of cells that is sensitive to gradients.

Input Image Output Image Output Image
Output Image Output Image Output Image
Output Image Output Image Output Image


The similarity with mathematical morphology is evident at this point. In fact, the mathematical morphology approach is nothing but a particular type of Cellular Atomata [5][6]. This is also the case for:

  • Markov random fields
  • Region growing methods
  • Watershed methods.
States are defined for each one of the cells and transitions between states are performed according to the input data coming from the substrate (the image) and the state of neighbor cells.

Segmentation Using Bacterial Colonies
The image below illustrates the process of segmentation of brain ventricles using a bacterial colony endowed with a simple reproduction algorithm. The bacteria reproduce as long as the gray level intensities on the image correspond to a pre-specified threshold. Bacterial division produce new cells inside the colony and their natural growth produce internal pressure that push the external cells outwards. Bacteria entering the region were the image values are not appropriate stop reproducing and simultaneously anchor themselves to the substrate (the image). As a result these outside cells act as a wall containing the progression of the colony. All bacteria in this colony are programmed to stop reproduction when the internal pressure exceed a nominal threshold. The combination of this rules produce a behavior similar to the ones of region-growing algorithms. The versatility of this methodology come from the simplicity with which the behavioral rules can be defined. Interactions between artificial genes and proteins are simulated in the cells in order to drive the transition rules of the cellular automata.

Input Image Output Image Output Image
Output Image Output Image Output Image
Output Image Output Image Output Image

A MPEG animation of the growing bacterial colony can be seen here.

Using Cells in 3D
The following sequence of images illustrate the use of bio-cells for analyzing a 3D image. This also shows the versatility of ITK's N-Dimensional design. The full application can be commuted from 2D to 3D by changing a single line in the Cell.h header file.

Input Image Output Image
Output Image Output Image

References
[1] D'Arcy Thompson, On Growth and Form, Cambridge University Press, 1992.

[2] Alan Turing, The Chemical Basis of Morphogenesis, Philosophical Transactions of the Royal Society, Vol.237, pp.37-72, 1952.

[3] S.M. Ulam, On some mathematical problems connected with patterns of growth of figures, Proceedings of symposia in applied mathematics, American Mathematical Society, Vol.14, pp.215-224, 1962.

[4] R. Schrandt, S.M. Ulam, On recursively defined geometrical objects and patterns of growth, Essays on cellular automata, University of Illinois Press, pp.232-243, 1970.

[5] J. von Neumann, Theory of self-reproducing automata, University of Illinois Press, 1966.

[6] J. Serra, Image analysis and Mathematical morphology, Academic Press Inc., 1982.


Go to next application.