A (fair ?) comparison of many max-tree algorithms


Revision as of 14:04, 12 November 2014 by Bot (talk | contribs) (Don't include the menu if the page is used included in another page)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)


The appendix of the article submitted to ISMM'13 is available here.

Extended version

An extended version of the article submitted to ISMM'13 is available on arXiv.


The poster presented at ISMM'13 is available here.

On-line application.

Submit your image and run max-tree algorithms to compare their performance.


This demo allows to upload an image of your choice and computes a max-tree using the different algorithms proposed in the submitted paper "A fair comparison of many max-tree algorithms" at ISMM 2013. Available algorithms are:

  • Sequentials algorithms
    • Salembier et al.
    • Berger et al.
    • Najman, Couprie
    • Berger + level compression
    • Berger + union-by-rank
    • Nistér and Stewénius
  • Parallel algorithms
    • all above
    • Matas et al.


You can run algorithms and display running time curves as a function of:

  • image size
  • image quantization
  • number of threads

The running time of a single algorithm cannot exceed 5 seconds.


Under development.


We will never use/read/save any uploaded data for personal use. Only the last uploaded file and its results are stored in our servers during 15min for technical reasons.

Terms and conditions

You are free to use the generated results for any usage. However, if they are used for research purpose, please refer to our library by citing the following paper: ``A (fair ?) comparison of many max-tree algorithms.

Source files

Source files are available in this archive.


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-comparison.tar.bz2 && cd Maxtree-comparison
> mkdir build && cd build
> cmake ..
> make maxtree_parallel_hqueue maxtree_parallel_pqueue maxtree_parallel_ufind maxtree_parallel_ufind_line
		 maxtree_parallel_ufindrank maxtree_serial_berger maxtree_serial_hqueue maxtree_serial_najman
		 maxtree_serial_pqueue maxtree_serial_ufind maxtree_serial_ufindrank

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)

Executables are then located in tests/morpho/. For usage and available options, run appname --help where appname is the name of the maxtree algorithm.

> ./tests/morpho/maxtree_serial_berger
Usage: ./tests/morpho/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.