Streaming Algorithm for Euler Characteristic Curves of Multidimensional Images
This work addresses the computational bottleneck for researchers and practitioners in computational topology and image analysis who need efficient descriptors for large-scale images, though it is incremental as it builds on existing Euler characteristic concepts.
The authors tackled the problem of computing Euler characteristic curves for large multidimensional images by developing the first streaming algorithm, which eliminates the need to store entire images in RAM and handles terabyte-scale images on commodity hardware with good scalability due to lock-free parallelism.
We present an efficient algorithm to compute Euler characteristic curves of gray scale images of arbitrary dimension. In various applications the Euler characteristic curve is used as a descriptor of an image. Our algorithm is the first streaming algorithm for Euler characteristic curves. The usage of streaming removes the necessity to store the entire image in RAM. Experiments show that our implementation handles terabyte scale images on commodity hardware. Due to lock-free parallelism, it scales well with the number of processor cores. Our software---CHUNKYEuler---is available as open source on Bitbucket. Additionally, we put the concept of the Euler characteristic curve in the wider context of computational topology. In particular, we explain the connection with persistence diagrams.