GraphCuts Using NPP

snowboarder_cutHave you ever wished you could change the background on an existing photo with you and your friends for fun or on a professional photo for publishing? If so, you’ll want to read on and learn about Graph Cut running on a GPU. This blog post will talk about the exciting new features and improvements that we did with the Graph Cut primitives in the CUDANPP signal and imaging library in the CUDA 4.1 Toolkit.

Consider you want to remove the background from an image with your friend and replace it with something more interesting like the top of Mount Everest. To get there you could take a bottom up approach: for each pixel decide if that pixel is depicting your friend or the background.

snowboarder_fullOnce all pixels are classified you could replace all pixels that are part of the background and be done. While this approach is simple it has a fundamental flaw. There will always be some pixels that you are not sure about. Unfortunately, wrong decisions even on a few pixels lead to very visible problems like holes and other artifacts in your final result. To resolve these ambiguities properly, one has to look at neighbor pixels and base the decision for each pixel also on those. In other words you need to consider the context to do the right thing. But adding context to your solution strategy means that every decision per pixel now also depends on the decision you are making on its neighbors. This leaves us with a much more complex problem that we need to solve. And this is where Graph Cut enters the scene.

Image credits: Creative Commons, Flickr user bobaliciouslondon (Snowboarder) & rupertuk {Mt. Everest}  

In my opinion Graph Cut is one of the greatest mathematical tools in image processing. I think it is safe to say that the current best tools available for image selection and panorama stitching are all using Graph Cuts in one way or the other. The reason why Graph Cuts have become so popular is that they elegantly solve complex optimization problems like the one we discussed. And they are very fast to compute, especially on the GPU. This combination makes them such a huge success.

fig1left fig1right
4 Neighborhood 8 Neighborhood, notice the higher accuracy along the edge

I am excited to announce that in the new CUDA 4.1 release we were able to improve the performance of the existing GPU Graph Cut primitive by a factor of 2.5x on average on standard datasets.  Also we added a new primitive which can now handle 8 neighborhoods. This can significantly improve the quality of your results due to higher accuracy in aligning to image boundaries as shown in the example.

To give you a quick and interesting way to play around and see for yourself we added a new SDK sample called “grabcutNPP”.  It is our implementation of the popular approach to object segmentation in images, published by Rother et al. at SIGGRAPH 2004. The way it works is that you pass your image file as argument on the command line to the sample. Then place a rectangle around the area you want to cut out in the GUI. The sample then computes a high quality, pixel accurate mask in just fractions of a second using the new and improved NPP Graph Cut primitive. When you are happy with what you got press “s” to save the result as PNG with alpha to disk.

I hope you enjoy the improvements to the Graph Cut primitives with the new release. If you are interested in more technical details, please check out also the chapter “Fast Graph Cut for Computer Vision” in GPU Computing Gems, Emerald Edition.

∥∀

About Mark Harris

Mark is Chief Technologist for GPU Computing Software at NVIDIA. Mark has fifteen years of experience developing software for GPUs, ranging from graphics and games, to physically-based simulation, to parallel algorithms and high-performance computing. Mark has been using GPUs for general-purpose computing since before they even supported floating point arithmetic. While a Ph.D. student at UNC he recognized this nascent trend and coined a name for it: GPGPU (General-Purpose computing on Graphics Processing Units), and started GPGPU.org to provide a forum for those working in the field to share and discuss their work. Follow @harrism on Twitter