Graph cuts in nVidia’s NPP toolbox (imageSegmentationNPP)

February 18, 2013

Note: This post has been updated after I received some help from nVidia’s Timo Stich. It turned out that some weights have to be set to zero; otherwise, CUDA gives an incorrect answer.

Today, I downloaded the latest version of nVidia’s CUDA to try out the graph cut segmentation present in NPP.

There is an example called “imageSegmentationNPP” which solves a two-dimensional (4-connected) problem. These are the results I got:

GPU: 84 ms.
CPU (GridCut): 24 ms.
Read the rest of this entry »


June 15, 2012

I have briefly tried the GridCut code ( and performed the same experiments as in the previous post. Below are the updated graphs.

The GridCut code performs very well for graphs with a reasonable amount of regularization, but becomes very slow for a high amount of regularization, just as BK.

Cell Classification

May 10, 2012

Johannes Ulén, Fredrik Kahl and I recently worked on a data set from the ICPR Contest on HEp-2 Cells Classification. The task is to classify images of cells as one of six possible categories. The image below show examples from the data set:

Each row shows images from one class.

Each row shows randomly selected images from one class. Click to enlarge.

Read the rest of this entry »

Maximum flow for vision

January 30, 2012

Last week, I decided to try out the IBFS maximum flow algorithm for vision applications for the first time. The algorithm is due to A.V. Goldberg, S.Hed, H. Kaplan, R.E. Tarjan, and R.F. Werneck, who have released an implementation which uses the same interface as the commonly used algorithm by Boykov and Kolmogorov.

My test was very simple, I generated a 128×128 8-connected grid graph, with source and sink arcs computed from the ‘cameraman’ image. I then let the weights of the arcs between the nodes vary several orders of magnitude. The result is quite telling:

The BK algorithm takes over 100 seconds to compute the maximum flow when the regularization is high. By contrast, the IBFS algorithm always uses less than 1 second. Here is the logarithmic plot:

Inpainting with coherency sensitive hashing

December 12, 2011

Coherency Sensitive Hashing (CSH) is a method to find corresponding patches between images quickly. It was introduced at this year’s ICCV. Since the authors have made their source code available, I decided to spend Sunday afternoon to play a little with their code.

Since there is no inpainting experiments in their paper and I could not find any example code for inpainting with PatchMatch either, I decided to implement this. The result was a Matlab function, which, given an RGB image and a mask, tries to fill the region specified by the mask with content from the rest of the image.


My source code is available on Github.

The results are not quite as good as shift-map inpainting, which we have implemented before.

Optimization for Multi-Region Segmentation of Cardiac MRI

August 22, 2011

Johannes Ulén, Fredrik Kahl and I have a paper accepted to STACOM, a workshop held in conjunction with MICCAI 2011 in Toronto.

The paper, “Optimization for Multi-Region Segmentation of Cardiac MRI”, is based on Andrew Delong and Yuri Boykov’s multi-region paper from ICCV 2009. We segment the left and right ventricles, myocardium and the papillary muscles jointly.

Read the rest of this entry »

Generalized Roof Duality: Experiments

August 17, 2011

This is a follow-up to the previous post about generalized roof duality and will contain some experimental results.

We have performed experiments with polynomials of degree 3 and 4. While these two cases are very similar in concept, implementing the degree 3 case is considerably easier.

Read the rest of this entry »

ICCV 2011: Generalized Roof Duality

August 7, 2011

Fredrik Kahl and I have a paper accepted to ICCV titled Generalized Roof Duality for Pseudo-Boolean Optimization.

Just as in the previous post, the problem of interest is to minimize degree-{m} polynomials {f: \mathbf{B}^n \rightarrow \bf \mathbf{R}} of the form:

\displaystyle  	f(\boldsymbol{x}) = \sum_i a_ix_i + \sum_{i<j} a_{ij}x_ix_j + \sum_{i<j<k} a_{ijk}x_ix_jx_k + \ldots.

The previous post showed that many different reductions to the quadratic case are possible. Our paper describes a generalization of roof duality which does not rely on reductions and is in a suitable sense optimal.

Read the rest of this entry »

Source code on Github

July 14, 2011

I have recently uploaded some source code to Github. Hopefully, this will make it easier to maintain and update the source code if necessary. Users who do not wany to use Git can still download an automatically generated .zip file of the entire repository.

regioncurv – 2D curvature regularization (main author: Thomas Schoenemann)

surfaces- 3D curvature regularization

Reductions in Pseudo-Boolean Optimization

May 21, 2011

This post is about reduction methods in pseudo-Boolean optimization and a recent paper to appear at CVPR 2011.

Read the rest of this entry »