3D image analysis
From Intelligent Perception
Project by James Molchanoff, supervised by Peter Saveliev
Image analysis and computer vision is the extraction of meaningful information from digital images. Some of the most prominent application is in cell analysis, medical image processing, and industrial machine vision.
There exists an abundance of methods for solving various well-defined computer vision tasks, where the methods are very task specific and seldom can be reused in a wide range of applications. Our goal is to design a computer vision system that uses the techniques of algebraic topology.
While people can easily point out important objects and ignore noise within photographs and other every day images, it becomes increasingly more difficult to do so with anything observed using scientific tools such as x-rays, microscopes, etc. To ease this process, it is necessary to program computers to accomplish these tasks. My project incorporates ideas found in the field of topology and integrates the software of the Computational Homology Project, CHomP.
The main objective is to modify CHomP so that it is capable of filtering the topological features of the image in order to determine what is noise and what is important. The approach is based on dilation and homology maps.
A cubical complex is any collection of cells - vertices, edges, faces, and voxels - satisfying the following condition:
If a cell belongs to the complex then so does any of its boundary cells.
From the field of topology, we must determine the Betti numbers of the given image. Betti numbers are labeled B0, B1, B2.
B0 shows the number of separate components in an image. B1 shows the number of tunnels an image contains. B2 shows the number of voids, or “bubbles” within an image.
This shape was generated using the “showcubes” software included in CHomP.
The image of an alloy requires computing to find the homology.
B0 = 1 (one object) B1 = 1059 (1059 tunnels) B2 = 0 (no enclosed voids)
Dilation is used to expand the features of an image by adding cubes along the boundaries of each existing cube in order to find the persistence (lifetime) of the image’s features.
5 Homology maps
f(x1) -> y1 -> y1 -> 0 f(x2) -> y2 -> 0 f(x3) -> 0
With regard to B1 shows 3 tunnels (x1,x2,x3) that are closing over the span of three dilations. Each y value specifies that the tunnel “survived” the dilation and the 0 means that the tunnel closed. This format works for all homology classes of all dimensions and will also display results to identify new components/tunnels/voids that are formed or even if two merge together.
Determining the “size” of a feature can often be difficult and time-consuming. Voids have volume and components have areas, but tunnels are formed with an open area and have debatable “volumes”. Therefore their persistence is calculated as a way to evaluate their importance. It is found by counting the “lifetime” of the feature within the homology mapping. it is called the persistence of the homology class.
In the previous example:
x1 has a persistence of 3 x2 has a persistence of 2 x3 has a persistence of 1
After these values are calculated, it can be left to the user to determine whether persistence is too small to be considered important to the overall image and is to be removed from the result.
There is a variety of valid formats for use with the CHomP program. Bitmap images that are not in a binary form need to have a threshold filter applied. The bmp2pset program included with the advanced version of CHomP can give the user a valid cubicle set for any threshold value.
The main part of the new code was in maphomol.cpp that, in a cycle, computes the homology of the elements of the filtration and the homology map for the inclusion. It was necessary, also, to code a data dilation program in order to calculate the filtration.
The program is given a series of data points or an image and then:
- Converts it into a usable format;
- Creates an identity mapping;
- Dilates the image one step;
- Finds the homology mapping between the image and its dilation;
- Repeats the process by comparing the 1st dilation and the 2nd, etc.;
- Calculates and returns the persistence values.
The main parts of the screenshots are shown below. Each part corresponds to a round of dilation and shows what happens to the homology classes.
The files are here. These are just the executables. For the source code contact James Molchanoff.
- The persistence is the easiest way to find the size of the image features.
- Dilation allows for a consistent change in data to allow for step-by-step evaluation.
- Computational Homology appears to be necessary for evaluating complicated images, especially with 3-dimensional imagery.
- Topology: an introduction
- Homology as an equivalence relation
- Cell decomposition of digital images
- Cubical complexes
- Homology of cubical complexes
- Betti numbers
- Chain complexes and Chain maps
- Homology in dimension 1, Homology in dimension 2
- Chain complexes, cycle groups, boundary groups as vector spaces
- Homology as a vector space
- Properties of homology groups
- Homology of surfaces