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.

Source code on Github

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

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

Curvature Regularization

Today, Fredrik Kahl and I got a paper accepted to EMMCVPR titled Curvature Regularization for Curves and Surfaces in a Global Optimization Framework. The focus of this paper is not theoretical contributions, but to improve the performance of curvature regularization in image analysis and computer vision in practice.

The problem we are interested in solving amounts to minimizing the following energy functional:

where is the 2D (or 3D) foreground region with boundary . Here is the data term, which may take many forms depending on the application, is a positive weighting factor for length (or area) regularization, and controls the amount of curvature regularization, denoted . Note that the domain may be a 2D image region or a 3D region. In the former case, the boundary is a curve and the notion of curvature is the usual one, while in the latter, the boundary is a surface and refers to the mean curvature.

The work by Schoenemann, Kahl and Cremers from ICCV 2009 showed how this functional can be discretized and a global minimum computer via an LP relaxation. The present paper builds heavily upon this and improves the framework in several aspects:

• We show that additional linear constraints are needed to prevent spurious contours, which result in incorrect solutions. As an additional benefit, these new constraints greatly decrease the computational time (at the cost of some additional memory).
• We introduce and evaluate hexagonal meshes and show that they are preferred over square ones.
• Instead of having dense meshes, adaptive meshes are evaluated to decrease the huge memory requirements. Note that a reasonable heuristic is needed to generate these meshes.
• Finally, we generalize the framework to three dimensions and perform some simple experiments in this setting.

The final version of the paper will be posted online when ready.

New blog

So I am creating this blog. Time will tell how useful it will be.