A Comparative Review of Component Tree Computation Algorithms
From LRDE
- Authors
- Edwin Carlinet, Thierry Géraud
- Journal
- IEEE Transactions on Image Processing
- Type
- article
- Projects
- Olena
- Keywords
- Image
- Date
- 2014-06-16
Abstract
Connected operators are morphological tools that have the property of filtering images without creating new contours and without moving the contours that are preserved. Those operators are related to the max-tree and min-tree repre- sentations of images, and many algorithms have been proposed to compute those trees. However, no exhaustive comparison of these algorithms has been proposed so farand the choice of an algorithm over another depends on many parameters. Since the need for fast algorithms is obvious for production code, we present an in-depth comparison of the existing algorithms in a unique framework, as well as variations of some of them that improve their efficiency. This comparison involves both sequential and parallel algorithms, and execution times are given with respect to the number of threads, the input image size, and the pixel value quantization. Eventually, a decision tree is given to help the user choose the most appropriate algorithm with respect to the user requirements. To favor reproducible research, an online demo allows the user to upload an image and bench the different algorithms, and the source code of every algorithms has been made available.
Documents
Dataset
Download the image dataset used in this comparison to bench the algorithms (26 Mb).
On-line application.
Compare the performance of the algorithms on an image of your choice and plot the performance curves.
Demo page url: http://olena.lrde.epita.fr/demos/maxtree_comparison.php
Status
Under development. For now, you can only plot curves and show performance of the algorithms on a pre-defined dataset. Benching the algorithms on your own images is still not possible.
Figures
Some results extracted from the paper. Tests conducted on Intel i7 (Intel(R) Core(TM) i7-2600 CPU @ 3.40GHz)
Comparison of the algorithms on 8-bit images as a function of the size.
Comparison of the algorithms on 8 Mega-pixels images as a function of the quantization.
Comparison of the parallel algorithms on a 6.8 Mega-pixels 8-bits image as a function of number of threads. Wall clock time.
Comparison of the parallel algorithms on a 6.8 Mega-pixels 8-bits image as a function of number of threads. Speedup w.r.t the sequential version.
Comparison of the parallel algorithms using 8 threads on a 6.8 Mega-pixels image as a function of the quantization.
Figures to answer reviewers requests about:
- Parallel algorithms behaviour on a machine with more cores. It has been tested on a 12-cores (24 logical cores) machine where each processor is an Intel(R) Xeon(R) CPU E5-2620 0 @ 2.00GHz.
- Parallel algorithms behaviour on an AMD processor since some algorithms seem to be more efficient on those architectures. Tests have been conducted on a AMD quad-core AMD Phenom(tm) II X4 945 Processor.
Comparison of the parallel algorithms on a 8-bit 6.8 Mega-pixels image as a function of the number of thread on the 12-cores Intel(R) Xeon(R).
Comparison of the parallel algorithms on a 8-bit 6.8 Mega-pixels image as a function of the number of thread on the quad-core AMD Phenom(tm).
Source files
You can download the archive with the source code.
Dependencies
The applications rely on those external libraries:
- Boost
- libfreeimage
- Intel TBB
You need a c++ 11 compliant compiler (applications have been successfully built with gcc > 4.7 and icc
Building maxtree executables
> tar xjf maxtree-review.tar.bz2 && cd maxtree-review > mkdir build && cd build > cmake .. > make -C apps/maxtree_comparison
It outputs the following executables:
- maxtree_serial_hqueue: Salembier (sequential)
- maxtree_serial_pqueue: Nister (<18bits) / Wilkinson (>18 bits) (sequential)
- maxtree_serial_berger: Berger et al.
- maxtree_serial_ufind_wlc: Berger + level compression
- maxtree_serial_ufind: Berger + level compression enabled if < 18bits
- maxtree_serial_unfindrank: Berger + rank
- maxtree_serial_najman: Najman and Couprie
- maxtree_parallel_hqueue: Salembier (parallel)
- maxtree_parallel_pqueue: Nister (<18bits) / Wilkinson (>18 bits) (parallel)
- maxtree_parallel_ufind: Berger + level compression enabled if < 18bits (parallel)
- maxtree_parallel_unfindrank: Berger + rank (parallel)
- maxtree_parallel_ufind_line: Matas et al. (parallel)
The binaries are then located in apps/maxtree_comparison. For usage and available options, run appname --help where appname is the name of the maxtree algorithm.
$ ./apps/maxtree_comparison/maxtree_serial_berger --help Usage: ./apps/maxtree_comparison/maxtree_serial_berger inputfile Allowed options: --help produce help message --nthread arg (=-1) set number of thread (default: auto) --nbits arg (=8) Set number of bits (default: 8). Quantization of the original is changed. Upper bits are moved left and missing lower bits are generated at random. --ntest arg (=3) set number of runs (default: 3) --sz arg (=0) Set size (number of pixels) (0: original). Resize the image by tiling or cropping the original until matching the number of pixel required. Original ratio width/height is kept.
Bibtex (lrde.bib)
@Article{ carlinet.14.itip,
author = {Edwin Carlinet and Thierry G\'eraud},
title = {A Comparative Review of Component Tree Computation
Algorithms},
journal = {IEEE Transactions on Image Processing},
year = 2014,
volume = {23},
number = {9},
month = sep,
pages = {3885--3895},
abstract = {Connected operators are morphological tools that have the
property of filtering images without creating new contours
and without moving the contours that are preserved. Those
operators are related to the max-tree and min-tree repre-
sentations of images, and many algorithms have been
proposed to compute those trees. However, no exhaustive
comparison of these algorithms has been proposed so far,
and the choice of an algorithm over another depends on many
parameters. Since the need for fast algorithms is obvious
for production code, we present an in-depth comparison of
the existing algorithms in a unique framework, as well as
variations of some of them that improve their efficiency.
This comparison involves both sequential and parallel
algorithms, and execution times are given with respect to
the number of threads, the input image size, and the pixel
value quantization. Eventually, a decision tree is given to
help the user choose the most appropriate algorithm with
respect to the user requirements. To favor reproducible
research, an online demo allows the user to upload an image
and bench the different algorithms, and the source code of
every algorithms has been made available.},
url = {10.1109/TIP.2014.2336551}
}