Version: 1.0 |
Please include the following reference when citing GRAPHGEN:
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:
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).
dot
command; bin
or build
. 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. -m32
to -m64
in CMAKE_CXX_FLAGS
and CMAKE_C_FLAGS
; CMAKE_BUILD_TYPE
(Release
preferred for faster decision tree and forest calculation). cd
into the build folder, run make
command and then execute one of the built targets (e.g. ./SAUF
). outputs
(e.g. GRAPHGEN/build/outputs/SAUF/SAUF_tree.svg
). 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"}
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.
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. 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. 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. 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.