Current Work

Minimizing Dynamic and Hierarchical Energy Functions using Multiresolution MRFs.

My current work focuses on processing of high resolution images and high definition video. I have modelled the problem on multiresolution MRF framework, which is assisted by a gamut of energy minimization methods basically dynamic and active graph cut methods, fusion move method, alpha-matting, reparameterization method from optimization theory. We propose a pyramid based optimization method which solves a minimization problem at the coarser level of pyramid to dynamically update the optimization instance for the next level for better initialization. We asymptotically decrease overall computation cost and memory requirement. We use our Pyramid Reparameterization method to solve different low-level problems like image segmentation, stereo correspondence and image denoising problems. We achieve 2-5 times of speed-up for segmentation problems on higher resolution images. For multilabel problems like stereo and denoising, we do multiresolution in not in graph space but also in label space. For stereo correspondece problem, we achieve 4-6 times speedup for higher resolution images.

Pyramid Segmentation for Interactive Global Segmentation of Large Images.

Global and local optimization methods have been suggested to interactively separate a foreground layer of an im- age. Global schemes are computationally expensive, diminishing the interactive experience on large images. Local, painting based methods provide interactivity but may require excessive interaction when processing images with a complex and distributed foreground layer. We present the Pyramid Segmentation method to perform fast, global optimization on large images while maintaining an interactive response. We use a novel coarse-to-fine processing of images, using pyramid reparametrization to propagate the mincut across pyramid levels. Our method is fast and accurate and has been adapted to run on the GPU. Our scheme displays the image at a resolution that shows it in its entirety. We provide a quick feedback to the user at this resolution, while processing the image at full resolution. This simultaneously achieves the performance advantage of global optimization based methods and the interactivity of painting based methods. The quick segmentation results are available in 2-3 seconds on the average on images with 10 million pixels and in under 1 second when using the GPU. The time to segment such images using Pyramid Segmen- tation is less by a factor of 3 to 4 than global methods like GrabCut and painting-based methods like Quick Selection.

Designing efficient algorithm to minimize energy functions.

Currently I am also trying to desing an efficient algorithm to minimize the energy functions arising in Computer Vision and Machine Learning by sub-dividing the label space and the energy space.

Past Projects

Real-time solving MRF problems on the GPUs

Pixel grey levels and orientations of the edges in an image can be viewed as the states of the image. As in the atomic(physical) level, these states of an atom can be specified by energy and random-ness of the system. Due to MRF and GRF equivalence, MAP estimation of the MRF can be formulated in terms of the minimizing an energy function. Graph cuts has become a powerful and popular optimization tool for energies defined over an MRF and have found applications in stereo vision, image restoration, photomontage, image segmentation etc. In recent years, few sophisticated algorithms, alpha-expansion, swap and Log-Cut, based on graph cuts have been popular to solve different multilabeling problems. We are trying to optimize the alpha-expansion using GPUs. We are also using the stochastic nature of the MRF.

Tracking Tracking

CUDA Cuts: Fast Graph Cuts on the GPU

Graph cuts has become a powerful and popular optimization tool for energies defined over an MRF and have found applications in stereo vision, image restoration, photomontage, image segmentation etc. The maxflow/mincut algorithm to compute graph-cuts is computationally expensive. They cannot be used for real-time applications or when iterated applications are needed. In this work, we present a fast and efficient method to to solve the push-relabel algorithm for graph cuts on the GPU. The time for each complete graph-cut is few milliseconds when only a few edge-weights change from the previous graph, as on dynamic graphs resulting from videos. We solved dynamic graph cuts for this purpose. We are also solving multiway cut based on the graph cuts on the GPUs/


Accelerating large graph algorithms on the GPU using CUDA

Large graphs involving millions of vertices are common in many practical applications and are challenging to process. Practical-time implementations using high-end computers are reported but are accessible only to a few. The G80 line of Nvidia GPUs can be treated as a SIMD processor array using the CUDA programming model. We present a few fundamental algorithms including breadth first search, single source shortest path, and all-pairs shortest path using CUDA on large graphs. We can compute the single source shortest path on a 10 million vertex graph in 1:5 seconds. We also give a block based method to solve the all pair shortest path algorithm. This new approach can solve APSP for a graph of 5000 nodes in 0.45 ms.