Computational Topology

Software Prototype

Pixcavator Image Analysis and Simplification Program   This program was written to illustrate and test how homology theory, can be used in image processing. The idea is to build more advanced image analysis applications on this simple platform. These applications are in the areas of image recognition and search. For more on this, well as to download the software and the SDK, visit Pixcavator.com. Pixcavator computes the number of dark and light objects in the processed image as 0th and 1st homology groups of the gray-scale image. These notions are defined in the book draft. The color version has been developed but only partially implemented. Even with all the mathematics worked out, the implementation for 3D images will be a challenge. This approach may be called “loss-less image processing”. This term is justified by the fact that nothing is removed from the image unless specifically requested by the user. The user retains complete control of what happens to the image! What the user chooses to keep is preserved without deformation, blurring, etc. There is also no iteration, no approximation, and no floating point arithmetic. This is what differentiates our approach from those common in the image processing industry.

PASS - Partition, Analysis, and Simplification System Pixcavator is just a part of a system of partition, analysis, and simplification of images. The method is implemented as a C++ program called PASS (Partition, Analysis, and Simplification System). Currently, PASS processes black-and-white and color images, as well as sequences of images, as bitmap files. Still images are partitioned into collections of connected regions. Then, the image is simplified by removing regions that are small in terms of their sizes  or contrasts. The applications are in image enhancement, computer vision, surface and curve reconstruction, scientific image analysis, image recognition and matching. The algorithm is also designed to conduct motion tracking and analysis of sequences of images.  The result is real time identification of objects in each frame, following each object from frame to frame, computation of locations and velocities of these objects, as well as their measurements (areas, volumes, moments, etc). An example of image simplification

CHomP, Computational Homology Project. This is a software package
developed by Computational Homology Project group at Georgia Tech.
CHomP runs in Windows and consists of 38 individual programs for
homology computations in n-dimensions. CHomP can compute the Betti
numbers and homology of a simplicial and cubical complex as well as the
maps induced in homology. All the algorithms are also explained in detail
in T. Kaczynski, K. Mischaikow, and M. Mrozek, Computational Homology,
Appl. Math. Sci. Vol. 157, Springer Verlag, NY 2004. It is a very powerful,
yet very easy package to use, with no installation necessary. The
programs are called from a command prompt.

PLEX. This is a set of routines written for MATLAB, developed by Vin de
Silva at Stanford University with the help of Gunnar Carlson. PLEX
computes the Betti numbers of simplicial complexes as well as the Betti
numbers of maps. One may only enter data as a list of vertices. After
defining an epsilon value (similar to the alpha-value discussed earlier),
PLEX calculates the appropriate edges for the vertex set.

Alpha Shapes. The package consists of several programs (Pdb2alf, Delcx,
Mkalf, Alvis, Volbl) by the National Center for Supercomputing
Applications and the Department of Computer Science at the University
of Illinois at Urbana-Champaign. This program runs only in
Linux/Unix/Sun. These programs have been used in the study of
proteins, and have also been modified for commercial use in surface
reconstruction by Geomagic. Alpha Shapes can compute the Betti
numbers of a complex, but only in dimension three.  For the purpose of
computing the Betti numbers, this software has a weakness in that you
can only look at one Betti number at a time. This means that if you want
to look at how the Betti number change as alpha grows, you must enter
the values in another program by hand. This can be a very time
consuming process.

CGAL, Computational Geometry Algorithms Library. This is a geometry
software package created as a collaborative effort from several sites in
Europe and Israel. CGAL is basically code to be used in C++ under
IRIX/Linux/Unix/Windows. CGAL is freely available at http://cgal.org/.
CGAL does not directly compute homology, but can provide the tools
necessary to compute triangulations and alpha complexes from which
homology can easily be calculated incrementally. However, CGAL can
only be used in dimensions two and three.

GAP homology package. It runs only on Linux/Unix. The two purposes
behind this project were to implement efficient algorithms for the
calculation of Smith Normal Forms of sparse matrices with integer entries
and simplicial homology of simplicial complexes. Three uses have been
suggested for this program. 1. Calculation of homology groups for a
large, complex simplicial complex. 2. Calculation of homology for many
small simplicial complexes. 3. Use as a teaching aide in homology course.

Moise - a topology package for Maple