Please include the following reference when citing GRAPHGEN:

• Bolelli, Federico; Allegretti, Stefano; Grana, Costantino "One DAG to Rule Them All" IEEE Transactions on Pattern Analysis and Machine Intelligence, 2021. BibTex. PDF.

GRAPHGEN is an open-source framework for optimizing algorithms that can be modeled with decision tables, such as Connected Components Labeling, Thinning (Skeletonization), Chain-Code (Contour Tracing), and Morphological Operators. The framework allows to automatically apply many different optimization strategies to a given problem, taking as input its definition in terms of conditions to be checked and actions to be performed, and directly producing the C++ code including those optimizations as output.

In short, GRAPHGEN is able to:

• Generate the Optimal Decision Tree (ODTree) associated to a given problem [1];

• Compress the ODTree into a Directed Rooted Acyclic Graph (DRAG), in order to better fit instruction cache [2];

• Apply pixel (or state) prediction [3], [4] thus generating a Forest of Decision Trees (FDTrees) from the original ODTtree. Prediction allows to recycle information obtained in the previous step, thus saving memory accesses and reducing total execution time [5];

• Remove boundary checks by generating special Decision Trees (DTtrees) for the start/end of the line and special FDTrees for the first/last line [6];

• Compress the FDT into a multi-rooted acyclic graph in order to better fit instruction cache;

• Introduce pattern frequencies in the generation of ODTs to better fit real data and improve the performance of algorithms over a particular use-case scenario.

As mentioned, the generation process is only related to the definition of the problem, meaning that the same problem can be solved using different definitions such as exploiting different scanning masks [4], [7], [8], [9].

For all the aforementioned optimization strategies GRAPHGEN is able to generate both the visual representation of the Decision Tree/Forest/DRAG and the C++ code implementing it.

Tested Platforms: Windows (VS2017), Linux (GCC 9.x or later).

How to Run GRAPHGEN

Requirements (Windows)

• For compiling: Visual Studio 2017 or later;
• CMake 3.12 or later;
• OpenCV 3.x (optional, only needed for frequency calculation);
• graphviz (included in the repository as executable);
• yaml-cpp (included in the repository as submodule).

Requirements (Linux)

• For compiling: GCC 9.x or later (for full std::filesystem support);
• CMake 3.12 or later;
• graphviz for producing SVG representations of the generated graphs, using the dot command;
• OpenCV 3.x (optional, only needed for frequency calculation);
• yaml-cpp (included in the repository as submodule).

Setup

• Install the requirements as described above;
• Open CMake and point it to the root directory of this repository. The build folder can be e.g. a subfolder called bin or build.
• Select "Configure";
• Important variables to set:
  • GRAPHGEN_FREQUENCIES_ENABLED: enables frequency calculation and corresponding build targets (e.g. Spaghetti_FREQ). If enabled: OpenCV_DIR points to the build folder of an OpenCV 3.x installation with identical architecture and compiler, and GRAPHGEN_FREQUENCIES_DATASET_DOWNLOAD must be enabled if you wish to download the datasets used in frequency calculation (archive size: ca. 2-3 GB). This flag is mandatory for frequency calculation if you have not downloaded the dataset before.
  • On Linux: if you wish to change the architecture to 64-bit (default is 32-bit), change occurences of -m32 to -m64 in CMAKE_CXX_FLAGS and CMAKE_C_FLAGS;
  • On Linux: you can adjust the build type by setting CMAKE_BUILD_TYPE (Release preferred for faster decision tree and forest calculation).
• Select "Generate" to generate the project.
• Build and execute the project:
  • On Windows: open the generated project solution, select the desired start-up target, build and execute either in Debug or Release mode.
  • On Linux: cd into the build folder, run make command and then execute one of the built targets (e.g. ./SAUF).
• The outputs (generated code and graphs) of the executables will be stored inside the build folder in a subfolder called outputs (e.g. GRAPHGEN/build/outputs/SAUF/SAUF_tree.svg).

Configuring GRAPHGEN

Some application behaviors can be configured by changing the config.yaml in the build folder.

• force_odt_generation - boolean value that forces the optimal decision tree to be (re)generated with every execution. This may be necessary for debug purposes:

force_odt_generation: false

• datasets - list of datasets to be used for frequency calculation. All the YACCLAB datasets are available if the GRAPHGEN_FREQUENCIES_DATASET_DOWNLOAD flag was set during the configuration:

datasets: ["fingerprints", "hamlet", "3dpes", "xdocs", "tobacco800", "mirflickr", "medical", "classical"]

• paths - dictionary with both input (folder containing the datasets used for frequency calculation) and output (where output code, graphs, and frequenices will be stored) paths. It is automatically initialized by CMake:

paths: {input: "<datasets_path>", output: "<output_results_path>"}

• dot - dictionary to configure dot output format. Three different configuration parameters are available:
  • out_format - output format of the generated graphs. Currently supported formats are "pdf", "png", and "svg";
  • background - background color of the generated graphs. It can be one of the colors supported by dot, such as "white", "red", "turquoise", "sienna", "transparent", etc;
  • ranksep - vertical separation for objects belonging to two consecutive lines of the output graph.

dot: {out_format: "svg", background: "transparent", ranksep: "0.5"}

Code Structure

The source code contains the library itself and dozens of example targets specific for different algorithms, already available in literature or newly generated with GRAPHGEN (the latter are identified with a *). A complete description follows.

Connected Components Labeling (Labeling)

• SAUF reproduces the Scan Array-based Union Find algorithm generating the optimal decision tree for the Rosenfeld scanning mask [7];
• PRED reproduces the algorithm proposed in [5], generating the optimal decision tree for the Rosenfeld scanning mask and then applying prediction;
• PRED++* applies the code compression strategy to the forest of PRED;
• SAUF3D* generates the optimal decision tree for the 3D Rosenfeld scanning mask;
• SAUF++3D* generates the optimal decision tree for the 3D Rosenfeld scanning mask and applies compression, converting the tree into a Directed Rooted Acyclic Graphs (DRAG);
• BBDT reproduces the Block-Based approach with Decision Trees, generating the optimal decision tree for the Grana scanning mask [8];
• BBDT_FREQ is the optimal decision tree generated from the Grana scanning mask considering pattern frequency [10].
• DRAG reproduces the connected components labeling on DRAG ([ˈdrʌg]) algorithm, which employs the optimal decision tree of BBDT converted into a Directed Rooted Acyclic Graph (DRAG) and compressed [2];
• DRAG_FREQ* the same as DRAG but generated considering pattern frequency;
• Spaghetti reproduces the Spaghetti algorithm proposed in [6], generating the optimal decision tree associated to the Grana scanning mask and applying prediction and compression;
• Spaghetti_FREQ the same as Spaghetti but considering pattern frequency;
• Tagliatelle* generates the optimal decision tree for the Grana scanning mask and applies prediction;
• PRED3D* generates the optimal decision tree for the 3D Rosenfeld scanning mask and applies prediction;
• PRED++3D* generates the optimal decision tree for the 3D Rosenfeld scanning mask and applies prediction and compression.

Image Skeletonization (Thinning)

• ZS_TREE reproduces the algorithm presented in [10] generating the optimal decision tree for the Zhang and Suen [11] approach;
• ZS_Spaghetti* generates the optimal decision tree for the Zhang and Suen [11] approach applying both prediction and compression;
• ZS_Spaghetti_FREQ* the same as ZS_Spaghetti but considering pattern frequency;
• GH_TREE* generates the optimal decision tree for the Guo and Hall [12] approach;
• GH_Spaghetti* generates the optimal decision tree for the Guo and Hall [12] approach, applying also prediction and compression.
• GH_Spaghetti_FREQ* the same as GH_Spaghetti but considering pattern frequency;
• CH_TREE* generates the optimal decision tree for the Chen and Hsu [13] approach;
• CH_Spaghetti* generates the optimal decision tree for the Chen and Hsu [13], applying also prediction and compression;
• CH_Spaghetti_FREQ* the same as CH_Spaghetti but considering pattern frequency.

Chain Code

• Cederberg_TREE* generates the optimal decision tree for the Cederberg [14] algorithm;
• Cederberg_Spaghetti* generates the optimal decision tree for the Cederberg [14] algorithm, applying also prediction and compression;
• Cederberg_Spaghetti_FREQ* the same as Cederberg_Spaghetti but considering pattern frequency.

Contributors

Thanks go to these wonderful people (emoji key):

Federico Bolelli 💻 📆 🚧 🚇 🤔 📖

Stefano Allegretti 💻 🚧 🚇

Costantino Grana 💻 📆 🤔 🚇

This project follows the all-contributors specification. Contributions of any kind welcome.

References

[1]	H. Schumacher and K. C. Sevcik, "The synthetic approach to decision table conversion," Communications of the ACM, vol. 19, no. 6., pp. 343–351, 1976.
[2]	F. Bolelli, L. Baraldi, M. Cancilla, C. Grana, "Connected Components Labeling on DRAGs," in International Conference on Pattern Recognition, 2018, pp. 121-126.
[3]	L. He, Y. Chao, and K. Suzuki, "An efficient first-scan method for label-equivalence-based labeling algorithms," Pattern Recognition Letters, vol. 31, no. 1, pp. 28–35, 2010.
[4]	L. He, X. Zhao, Y. Chao, and K. Suzuki, "Configuration-Transition-Based Connected-Component Labeling," IEEE Transactions on Image Processing, vol. 23, no. 2, pp. 943–951, 2014.
[5]	C. Grana, L. Baraldi, and F. Bolelli, "Optimized Connected Components Labeling with Pixel Prediction", in Advanced Concepts for Intelligent Vision Systems, 2016, pp. 431-440.
[6]	F. Bolelli, S. Allegretti, L. Baraldi, and C. Grana, "Spaghetti Labeling: Directed Acyclic Graphs for Block-Based Bonnected Components Labeling," IEEE Transactions on Image Processing, vol. 29, no. 1, pp. 1999-2012, 2019.
[7]	K. Wu, E. Otoo, and K. Suzuki, "Optimizing two-pass connected-component labeling algorithms," Pattern Analysis and Applications, vol. 12, no. 2, pp. 117–135, 2009.
[8]	C. Grana, D. Borghesani, and R. Cucchiara, "Optimized Block-based Connected Components Labeling with Decision Trees," IEEE Transactions on Image Processing, vol. 19, no. 6, pp. 1596–1609, 2010.
[9]	W.-Y. Chang, C.-C. Chiu, and J.-H. Yang, "Block-based connected-component labeling algorithm using binary decision trees," Sensors, vol. 15, no. 9, pp. 763–23, 2015.
[10]	C. Grana, M. Montangero, and D. Borghesani, "Optimal decision trees for local image processing algorithms,"Pattern Recognition Letters, vol. 33, no. 16, pp. 2302–2310, 2012.
[11]	T.Y. Zhang, and C. Y. Suen, "A Fast Parallel Algorithm for Thinning Digital Patterns," Communications of the ACM, vol. 27, no. 3, pp. 236–239, 1984.
[12]	Z. Guo, and R. W. Hall, "Parallel Thinning with Two-Subiteration Algorithms," Communications of the ACM, vol. 32, no. 3, pp. 359–373, 1989.
[13]	Y.-S. Chen and W.-H. Hsu, "A modified fast parallel algorithm for thinning digital patterns," Pattern Recognition Letters, vol. 7, no. 2, pp. 99–106, 1988.
[14]	R. L., Cederberg "Chain-link coding and segmentation for raster scan devices," Computer Graphics and Image Processing, vol. 10, no. 3, pp. 224-234, 1979.