Cache-Efficient Graph Cuts on Structured Grids
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