A Comparative Review of Component Tree Computation Algorithms

From LRDE

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)

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.

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}
}