Heat Walk: Robust Salient Segmentation of Non-rigid Shapes

• Published in: Computer graphics forum 2011-09, Vol.30 (7), p.2097-2106
• Main Authors: Benjamin, William, Polk, Andrew Wood, Vishwanathan, S.V.N., Ramani, Karthik
• Format: Article
• Language: English
• Subjects: Accumulators; Algorithms; Analysis; and systems; Computer graphics; Diffusion; Dissipation; Explicit knowledge; Heat conductivity; Heat transfer; Heat transmission; I.3.5 [Computer Graphics]: Computational Geometry and Object Modeling-Geometric algorithms; I.3.5 [Computer Graphics]: Computational Geometry and Object Modeling—Geometric algorithms, languages, and systems; Image processing systems; languages; Segmentation; Short circuits; Studies
• ISSN: 0167-7055; 1467-8659
• DOI: 10.1111/j.1467-8659.2011.02060.x

Segmenting three dimensional objects using properties of heat diffusion on meshes aim to produce salient results. The few existing algorithms based on heat diffusion do not use the full knowledge that can be gained from heat diffusion and are sensitive to varying kinds of perturbations. Our simple algorithm, Heat Walk, converts the implicit information in the heat kernel to explicit knowledge about the pathways for maximum heat flow capacity. We develop a two stage strategy for segmentation. In the first stage we quickly identify regions which are dominated by heat accumulators by employing a greedy algorithm. The second stage partitions out dissipative regions from the previously discovered accumulative regions by using a KL‐divergence based criterion. The resulting algorithm is both independent of human intervention and fast because of the globally aware directed walk along the maximal heat flow capacity. Extensive experimental evidence shows the method is robust to a variety of noise factors including topological short circuits, surface holes, pose variations, variations in tessellation, missing features, scaling, as well as normal and shot noise. Comparison with the Princeton Segmentation Benchmark (PSB) shows that our method is comparable with state of the art segmentation methods and has additional advantages of being robust and self contained. Based upon theoretical insight the convergence and stability of the Heat Walk is shown.