This work presents a framework for testing the runtime and results of fractal dimension computation algorithms. Included are two such algorithms by Juan Ruiz de Miras and Miguel Ángel Posadas. The first box-counting algorithm can be found here. The differential box-counting algorithm does not have a proper source code link from the authors. They have been re-written and edited as described in their paper, which can be found here. A Jupyter Notebook file through which you can generate input data and run the built executables of the algorithms is also attached.
- sequential Fast Box Counting algorithm running on CPU;
- parallelized Fast Box Counting algorithm running on GPU;
- sequential Differential Box Counting algorithm running on CPU;
- parallelized Differential Box Counting algorithm running on GPU;
- Jupyter Notebook Wrapper file used for image generation and test results.
CMake may be used to build both the CPU and GPU versions of the algorithms. Due to the GPU versions of the algorithms specifically using the CUDA framework, which is only available on certain nVidia GPUs, we have two separate make commands.
They each generate one directory and each generate an executable with the name FractalDimensionComputation, though there is a distinction for the GPU executable having "_GPU" appended at the end of the file name.
If, for whatever reason, you would like to delete the build directories, you can do so with the
make cleancommand. Please keep in mind that the deletion of these directories is afterwards immediate and cannot be reverted.
The CPU versions of the algorithms require OpenCV for image reading and edge detection purposes.
make build_cpuThe GPU versions of the algorithms require OpenCV for image reading and edge detection purposes, as well as the CUDA framework for allowing the CUDA kernels to properly compile.
make build_gpuWhichever IDE of your choosing which is able to run Jupyter Notebooks will suffice. The requirements are listed within the Notebook. Simply run the first cell for them to be installed. The code was tested only on Visual Studio Code and Python version 3.13.0.
The Notebook is capable of generating four different kinds of fractals:
- Julia Sets
- Sierpinski Triangles
- Sierpinski Pentagons
- Koch Curves
To generate one such image, the PIL, tkinter and turtle packages are used for screenshots, window generation, respectively drawing the fractal itself.
Simply run the imports cell, the code cell under "Draw Image", and lastly the cells under the image which you wish to generate. You may modify any relevant parameters, such as cX and cY for your Julia set
- images (must be explicitly created by you)
- {filename} (created by the Jupyter Notebook if it doesn't exist)
Below are the arguments given to the executable, and what you should be setting them to according to your wants and needs:
runTimes = 10 # How many times should the algorithm run? If you don't wish to benchmark the running times, you should leave this as "1", given that the resulting dimension does not change between runs over the same file. One "results" file will be generated for each run.
filename = "Triangle" # This should be the same name as the image which you wish to use. Do NOT add the extension, though keep in mind it HAS to be a .png file. A directory will be created with the name of this string if it hasn't already been created.
algorithm = "DBC" # Value can be either "BC" for the Fast Box Counting algorithm, or "DBC" for the Differential Box Counting algorithm.
runOn = "CPU" # This helps make benchmarking easier by allowing you to specify the ending of the executable name. For example, if you rename your CPU build of the program to "Fast Box Counting CPU" and your GPU build of the program to "Fast Box Counting GPU", runOn may be either "CPU" or "GPU". This is not actually an argument used when calling the executable, merely a way to differentiate between the two executables.If everything runs correctly, you should get a return value of 0. Otherwise, there is a problem with your executable or with how you are calling the executable. If the problem lies in your argument usage, a text file called "errors.txt" will be generated in your working directory, detailing all errors which lead to the premature stop of the executable.
- Week 9 - Created README.md and LICENSE files.
- Week 12 - Added DBC (differential box-counting) algorithm.
- Week 13 - Added enhancements to the Jupyter Notebook Wrapper file.
- Week 14 - Updated README.md and pushed changes on GitHub.
The project is licensed under [the MIT license.](./LICENSE).
The Fast Box Counting algorithm has been licensed under CC-BY-SA-4.0 by Juan Ruiz de Miras and Miguel Ángel Posadas. The original code can be found here. Their code may be found within the following files:
- bcCPU.cpp
- bcCPU.h
- main.cpp
- bcCUDA2D.cu
- bcCUDA2D.cuh
- mainGPU.cpp