Cache-Efficient Graph Cuts on Structured Grids

Project Members

Daniel Sykora (Czech Technical University in Prague)
Alexander Sorkine-Hornung (Disney Research Zurich)


Minimal cuts on graphs have been studied over decades and have developed into a fundamental solution to problems in various disciplines. In computer vision and graphics, applications range from segmentation, stereo and shape reconstruction, editing and synthesis, ļ¬tting and registration to pose estimation and more.

Typically, in those application domains the underlying graph structures can be characterized as regular N-D grids, where all nodes have topologically identical neighborhood systems, i.e., each node is connected in a uniform fashion to all other nodes lying within a given radius. However, computation speed and memory consumption often times limit the effective use in applications requiring high resolution grids or interactive response. In particular, memory bandwidth represents one of the major bottlenecks even in today’s most efficient implementations. We propose a compact data structure with cache-efficient memory layout for the representation of graph instances that are based on regular N-D grids with topologically identical neighborhood systems. For this common class of graphs, our data structure allows for 3 to 12 times higher grid resolutions and a 3- to 9-fold speedup compared to existing approaches. Our design is agnostic to the underlying algorithm, and hence orthogonal to other optimizations such as parallel and hierarchical processing.

In video-related applications such as segmentation, colorization, and stereo reconstruction, the developed technology enables much more efficient processing of high resolution content


Cache-Efficient Graph Cuts on Structured Grids-Thumbnail

Cache-Efficient Graph Cuts on Structured Grids
June 18, 2012
IEEE Conference on Computer Vision Pattern Recognition (CVPR) 2012
Paper File [pdf, 331.28 KB]

Copyright Notice

The documents contained in these directories are included by the contributing authors as a means to ensure timely dissemination of scholarly and technical work on a non-commercial basis. Copyright and all rights therein are maintained by the authors or by other copyright holders, notwithstanding that they have offered their works here electronically. It is understood that all persons copying this information will adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.