Tricks to Implementing QPBO and the ELC: MRF optimisation library

It seems that many people are having trouble compiling Kolmogorov’s QPBO MRF optimisation library for Mac OS, and clang. So, I thought I’d post some tips on how I did it, albeit with considerable help from those more knowledgeable in good c++ practice than myself!

There seems to be a problem with the implementation of templating, which leads to linking errors:

ld: symbol(s) not found for architecture x86_64

To get round this, we converted QPBO to a header only library and moved all code, including the instantiations in to a single QPBO.hpp file, as hinted to in this stackoverflow page

My efforts in getting QPBO running, were motivated from a desire to using the Excludable Local Configuation (ELC) software [1], created by Hiroshi Ishikawa ( This reduces higher-order (in my case tri-clique) node configurations to pairwise terms that can be solved using QPBO. It is an approximation approach built upon the Higher-Order Clique Reduction (HOCR) approach first proposed in [2].

My application is cortical mesh alignment. For this I have triangulated meshes with irregularly numbered nodes. On the other hand, most MRF optimisation libraries are designed for use in image processing, where pixels are defined on a regular image grid. As such I have subsequently run into implementation problems associated with node numbering and labeling assignments.

The ELC library has a series of asserts in the code that can be disabled by compiling with flag -DNDEBUG. However, if the following are not addressed the code crashes at the max flow stage:

  1. assert(v1 < v2) in ELC0.h: This refers to node ordering (v1 and v2)  are the node indexes for two nodes in a term.
  2. user_assert(i >= 0 && i < node_num) (in QPBO AddUnaryTerm). This tracks back to the fact that ELC can’t manage a zero labelling initialisation.

The first assert means that node configurations (i.e. pairs, triplets and quadruplets) have to be passed to the ELC in ascending order. This means that when you define pair/triplets in your own code you must define them as such.

The second is a problem because ELCReduce::reduceHigher (int) shrinks all terms with zero coefficients reducing node_num to zero.   Then, when the conversion to a QPBO object is run, it crashes. For some applications you might be able to avoid this by randomly initialising the labeling. However, as I have an application where I need to have the option that no labels  change  I simply ignored the zero labelling on the first sweep.

Finally, I changed references in ELC.h to abs(c) to fabs(c) as the resulting variable is float. It is not clear at this point whether this was intentional or a bug. However, without the change ELC_APPROX does not run on MacOS. I

If anyone else reading this encounters similar issues I would really like to hear about them.

NOTE ***** Importantly these restrictions are not present for the HOCR code, if anybody is migrating from this.***********************************************


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s