ViteBetti

ViteBetti is an algorithm for computing the Betti numbers of a 3D cubical complex. It exploits the Euler-Poincaré characteristic and Alexander duality.

Take a look at our paper in the CTIC 2016 proceedings. We are submitting also an extended version to this Special Issue in "Discrete Geometry and Topology and their Applications to Imaging Sciences".

Data format

The cubical cells of a 3D cubical complex are of the form [x, x+d1]✕[y, y+d2]✕[z, z+d3] where di is 1 or 0. Thus, a cubical cell can be unequivocally identified to a vector (2x+d1, 2y+d2, 2z+d3). Therefore, a 3D cubical complex can be easily encoded as a binary three-dimensional array A where the position A(i,j,k) is 1 if the corresponding cubical cell belongs to the complex or 0 otherwise.

A text file describing a 3D cubical complex consists in:

  1. A first line with the size of the bounding box along each axis;
  2. The content of the tree-dimensional array A running first in the z-coordinate, next in the y-coordinate and last in the x-coordinate.

You can see here a small 3D cubical complex with Betti numbers (1,1,1).

Algorithms

Our software includes four algorithms for computing the Betti numbers:

  1. A sequential algorithm that performs breadth first search in the complex.
  2. A recursive algorithm that use a divide-and-conquer approach. The complex is cut into pieces of size greater than a given threshold.
  3. A parallel implementation of the previous algorithm with TBB.
  4. An algorithm that treats the complex slice by slice.

Download and compile

You can download the source code here. You need to install Threading Building Blocks before compiling. For this, you just need to type sudo apt-get install libtbb-dev

Then, after extracting the source files you can compile them on Linux as follows: g++ main.cpp fullcomplex.cpp scancomplex.cpp unionfind.cpp -ltbb -std=c++11 -O3 -o ViteBetti

Usage

Once you have compiled ViteBetti, you just need to type on your terminal:
./ViteBetti fileName -a algorithm
where fileName is the name of the file encoding the 3D cubical complex and algorithm is the number of the algorithm you want to use.

The threshold for the two recursive algorithms 2 and 3 can be introduced as follows:
./ViteBetti fileName -a 2 -t threshold

The third algorithm is faster than the second, which is faster than the first one. The fourth algorithm is recommended for huge complexes (in the order of 10013), since it consumes less memory.

You can generate random 3D cubical complexes with RandCubComplex in order to test the performance of the algorithms.

License and citation

ViteBetti is a free software: you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, either version 3 of the License, or (at your option) any later version.
This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with this program. If not, see http://www.gnu.org/licenses/.

Please, cite our software if you use it on your research. The theoretical foundation and algorithms 1--3 are described in this paper. You can also download here a BibTeX entry for our software.