Fast 3D Stereo Vision

Recently, I started looking at faster ways to perform dense stereo matching for some work with 3D video. After some experimentation, I found out that by using a selective mode filter paired with naive correspondence matching, I was able to get satisfactory results very quickly. Check out the slide show below for some results!



[red indicates close, blue indicates far away]

 

Here is a download-able Matlab demo, which should work on any pre-aligned stereo image pairs:

stereo_modefilt.zip

The entire code is written in Matlab/C++/MEX. The stereo matching is all in Matlab, and the selective mode filter is coded in C++ and callable from Matlab (meaning it must be compiled before it can run). Currently, the correspondence is the major bottleneck, so anyone who can improve this, please let me know.

This code can be used according to the MIT license. As long as this work is appropriately cited and attributed, and not being used for proprietary or commercial purposes, I’m fully supportive of you using it. Please drop me a line if it helps you!

Selective Mode filter in Matlab

The median filter is a well-known image processing filter. It provides a very nice way to smooth an image while preserving edges. The median filter replaces each pixel in the image with the median value of its neighboring pixels. A similar non-linear filter with slightly different properties is the mode filter which replaces each pixel with the mode of its neighboring pixels. I additionally make a slight modification so that “bad” pixels are ignored entirely in the computation of the mode.

This idea arose when I was trying to de-noise some images as well as do some in-painting of “bad” pixels (that have no value). Consider the image below. The darkest-blue areas are bad pixels. We have no information for those pixels. The other pixels are colored to show how far that pixel is from the camera. (see the post on Stereo Vision) However, some of the good pixels still have the wrong value. These are the noise pixels.


original data
[Initial Image]

In the rest this post I talk about how we use a selective mode filter to convert the above image into the one below. (There’s also download-able Matlab/C++ code)


selective modefilt
[Final Result of Selective Mode Filter]

Continue reading “Selective Mode filter in Matlab”

Brain Science and Computer Vision

Everyone talks about like the brain like its a computer. Well, in some ways its similar. There are nerve cells that act like “wires” and run from one part of the brain to another. With the advent of a new kind of medical imaging technology called “Diffusion Weighted MRI” (DW-MRI), it is possible to find these wires using computer vision. Many people claim that it is important to find whole bundles of these wires in addition to the individual wires.

Recently, I’ve been working on a way to do this using partial differential equations (PDEs). Below you can see some of the results. First, thin white tubes are shown. These represent a single “wires” called fibers. From these single fibers, we determine the boundary of the whole bundle. We then show this as thick yellow tubes.

By studying the shape and size of these bundles, doctors may be able to detect mental illness early and improve the understanding of the brain! Hopefully I can help by making these pretty pictures : )

Active Contour Matlab Code Demo

UPDATE:
My new post: Sparse Field Active Contours
implements quicker, more accurate active contours.

Today, I added demo code for the Hybrid Segmentation project. This segmentation algorithm (in the publications section) can be used to find the boundary of objects in images. This approach uses localized statistics and sometimes gets better results than classic methods. For an example, see the video below: The contour begins as a rectangle, but deforms over time so that it finally forms the outline of the monkey.

This can be used to segment many different classes of image. To try it out, download the demo below and run >>localized_seg_demo

localized_seg.zip

This code is based on a standard level set segmentation; it just optimizes a different energy. I’ve also made a demo which implements the well-known Chan-Vese segmentation algorithm. This technique is similar to the one above, but it looks at global statistics. This makes it more robust to initialization, but it also means that more constraints are placed on the image. Download it and see what you think! Again, unzip the file and run >>region_seg_demo

sfm_chanvese_demo.zip (New! Described Here)
regionbased_seg.zip (old and slow)

This code can be used according to the MIT license. As long as this work is appropriately cited and attributed, and not being used for proprietary or commercial purposes, I’m fully supportive of you using it. Please drop me a line if it helps you!

A Short MEX Tutorial and Demo

Matlab is a great programming language/environment because of its ease of use, great visualization, and rapid prototyping abilities. Raw speed is not one of its strong suits. MEX (Matlab Executables) are the answer. These functions allow you to program in C or C++ (ultra fast languages), but be able to call and use them from Matlab programs. This post is a short intro to mex files which should get you up and running.

What This Post Teaches

In this post, I show how to create a mex file, how to set up inputs and outputs, how to get access to Matlab objects, and how to manipulate them. I also give a skeleton mex program that might be helpful. There is a lot more to learn, and I’d refer you to the mex manual regardless.

Continue reading “A Short MEX Tutorial and Demo”

GrowCut Segmentation In Matlab

I came across a cute segmentation idea called “Grow Cut” [pdf]. This paper by Vladimir Vezhnevets and Vadim Konouchine presents a very simple idea that has very nice results. I always feel that the simplest ideas are the best! Below I give a brief description of the algorithm and link to the Matlab/C/mex code.

GrowCut Region Growing Algorithm

This algorithm is presented as an alternative to graph-cuts. The operation is very simple, and can be thought of with a biological metaphor: Imagine each image pixel is a “cell” of a certain type. These cells can be foreground, background, undefined, or others. As the algorithm proceeds, these cells compete to dominate the image domain. The ability of the cells to spread is related to the image pixel intensity.

The authors give some pseudocode that very concisely describes the algorithm.


//for every cell p
for all p in image
  //copy previous state
  labels_new = labels;
  strength_new = strength;
  // all neighbors q of p attack
  for all q neighbors
    if(attack_force*strength(q)>strength_new(p))
      labels_new(p) = labels(q)
      strength(p) = strength_new(q)
    end if
  end for
end for

Segmentation Results

Once implemented, this is a nice way to get segmentations. It is quite fast, and the initialization is very intuitive. Consider this picture of a lotus flower:

growcut image

I made an initialization by clicking 20 points in the flower and 30 points outside. I then made a “label map” where unlabeled pixels are 0 (gray), foreground pixels are 1 (white) and background pixels are -1 (black).

growcut seeds

Based on this simple initialization, we obtain a very decent segmentation:

growcut output

As you can see, it isn’t perfect, but it is quite good. Its possible to interactively refine the seed points to improve the segmentation, but I didn’t do that here.

Matlab Code Downloads

I implemented this code in Matlab (using mex files due to the extensive use of for loops). You can download this below with compiled binaries for mac, linux, and windows. Unzip the file and run >>growcut_test for a demo.

UPDATE: I’ve fixed some bugs thanks to reader, Lin. The code works much better now!

Source & Compiled Binaries (96k) [zip]
“GrowCut” Paper [pdf]

Please let me know if you find this useful, and if you make improvements! Also, check out these related segmentation posts:

Related Segmentation Posts

Use that Sweet Spot

With the easy availability of scientific papers through the internet, it is easy to quickly get your hands on tons of pdfs. Then what? I look through the pile very quickly and pick out the one or two papers that look the most relevant. This quick pass consists of glancing at the abstract and the figures.

Knowing that this quick and dirty scan is probably becoming the norm, I’ve started including a telling graphic right in the Sweet Spot. This is a term my colleagues and I have come up with for the top of the right column on the first page. Check it out:

sweet spot papers

Including the Sweet Spot graphic may get your paper read more, it may get your paper read less. Either way, it helps the reader make a snap decision about whether or not your paper is of interest to them. I feel like it makes the paper visually more attractive and inviting, too.

Any other Sweet-Spotters out there?

Beamer and Latex With Keynote Theme

LaTeX is a typsetting system that allows you to make great-looking documents, and is well-used to make academic papers. I even use it for homeworks and other documents. There are also packages that allow it to make fantastic posters and slide presentations as well. I spent the last few days getting caught up on this, and want to share what I’ve figured out:

  • A sexy Beamer theme that looks like Keynote
  • How to format the footer
  • How to make slide numbers
  • How to remove the navigation symbols
  • How to make movies show up in presentations
  • The best references

I’ll talk about each of these briefly and give links to download a demo presentation and the .tex and .sty files that made it. Here’s a sneak peek of what it looks like!

keynote beamer presentation

Continue reading “Beamer and Latex With Keynote Theme”

Quick and simple derivatives in Matlab

Ever try to compute the directional derivatives on a matrix? Google turn up menacing formulas for Taylor expansions, grid spacing, and boundary conditions?

A quick and simple way of computing derivatives is to perform arithmetic on shifted versions of the matrix, and vectorized indexing help Matlab speed things up. For example, use the following for the (central) x-derivative:

dx = (M(:,[2:end end]) - M(:,[1 1:end-1]))/2

You can even define inline functions to perform the shift and derivative operations. Below are definitions for the shift operations and first and second order derivatives.

% shift operations
shiftD = @(M) M([1 1:end-1],:);
shiftL = @(M) M(:,[2:end end]);
shiftR = @(M) M(:,[1 1:end-1]);
shiftU = @(M) M([2:end end],:);

% derivatives
Dx = @(M) (shiftL(M) - shiftR(M))/2;
Dy = @(M) (shiftU(M) - shiftD(M))/2;
Dxx = @(M) (shiftL(M) - 2*M + shiftR(M));
Dyy = @(M) (shiftU(M) - 2*M + shiftD(M));
Dxy = @(M) (shiftU(M) - shiftD(M) + shiftL(M) - shiftR(M))/4;

And use them like this:
>> Ax = Dx(A)
Ax =
-7.0000 -6.5000 5.5000 5.0000
3.0000 2.5000 -1.5000 -1.0000
-1.0000 -1.5000 2.5000 3.0000
5.0000 5.5000 -6.5000 -7.0000

>> Ayy = Dyy(A)
Ayy =
-11 9 7 -5
15 -13 -11 9
-9 11 13 -15
5 -7 -9 11