C++14

Consider the following code:

void f(const int &) { cout << 1; }
void f(int&&) { cout << 2; }

template<typename T>
void g(const T&) { cout << 1; }
template<typename T>
void g(T&&) { cout << 2; }

int main()
{
  f(1);
  g(1);

  int i;
  f(i);
  g(i);
}

What will the code print? The answer is “2212,” which can be quite surprising.

Rounding of strings

Consider the following program:

int main()
{
auto f = 1.0f;
printf(“%f\n”, f / 0);
printf(“%.1f\n”, f / 0);
printf(“%.2f\n”, f / 0);
printf(“%.3f\n”, f / 0);
printf(“\n”);

f = 0.0f;
printf(“%f\n”, f / 0);
printf(“%.1f\n”, f / 0);
printf(“%.2f\n”, f / 0);
printf(“%.3f\n”, f / 0);
}

With Visual Studio 2012, it outputs the following:

1.#INF00
1.$
1.#J
1.#IO

-1.#IND00
-1.$
-1.#J
-1.#IO

The strings are also rounded! That is, ‘#’ + 1 == ‘$’. This can be a bit surprising.

 

Graph cuts in nVidia’s NPP toolbox (imageSegmentationNPP)

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.

GridCut

I have briefly tried the GridCut code (http://gridcut.com) 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

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 randomly selected images from one class. Click to enlarge.

Maximum flow for vision

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

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.

Example

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

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.

Generalized Roof Duality: Experiments

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.

ICCV 2011: Generalized Roof Duality

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- polynomials of the form:

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.