On the Computation of the Euler Characteristic of Binary Images in the Triangular Grid

摘要

Apart from the widely used square grid, other regular grids (hexagonal and triangular) are gaining prominence in topological data analysis and image analysis/processing communities. One basic but important integer-valued topological descriptor of binary images in these grids is the Euler characteristic. We extend two algorithms for the computation of the Euler characteristic from the square to the triangular grid, taking into account specific properties of the triangular grid. The first algorithm is based on simple cell counting, and the second is based on critical point approach. Both algorithms iterate over the grid vertices. We extend also their improvement based on reusing information common to the previous and the next vertex in the scan order. Our experiments show that the critical point based algorithms outperform the naive cell-counting ones, with the improved versions reducing the average runtime further.