Fast Box-Counting Algorithm on GPU

Computer Methods and Programs in Biomedicine vol. 108 (3) pp. 1229–1242

Jiménez, J.; Juan Ruiz-de-Miras


The box-counting algorithm is one of the most widely used methods for calculating the fractal dimension (FD). The FD has many image analysis applications in the biomedical field, where it has been used extensively to characterize a wide range of medical signals. However, computing the FD for large images, especially in 3D, is a time consuming process. In this paper we present a fast parallel version of the box-counting algorithm, which has been coded in CUDA for execution on the Graphic Processing Unit (GPU). The optimized GPU implementation achieved an average speedup of 28 times (28×) compared to a mono-threaded CPU implementation, and an average speedup of 7 times (7×) compared to a multi-threaded CPU implementation. The performance of our improved box-counting algorithm has been tested with 3D models with different complexity, features and sizes. The validity and accuracy of the algorithm has been confirmed using models with well-known FD values. As a case study, a 3D FD analysis of several brain tissues has been performed using our GPU box-counting algorithm.

DOI: 10.1016/j.cmpb.2012.07.005


author = {Jes\'us Jim\'enez-Ib\'añez and Juan Ruiz-de-Miras},
title = {Fast Box-Counting Algorithm on GPU},
journal = {Computer Methods and Programs in Biomedicine},
number = {3},
pages = {1229–1242},
volume = {108},
year = {2012},
doi = {10.1016/j.cmpb.2012.07.005},
issn = {0169-2607}