Fast High-Dimensional Filtering and Inference in Fully-Connected CRF

Slide Note

This work discusses fast high-dimensional filtering techniques in Fully-Connected Conditional Random Fields (CRF) through methods like Gaussian filtering, bilateral filtering, and the use of permutohedral lattice. It explores efficient inference in CRFs with Gaussian edge potentials and accelerated methods such as Permutohedral lattice, Gaussian KD-Tree, and regular grids. The Permutohedral lattice is highlighted for its projection capabilities in high-dimensional space and tessellation properties. Overall, the research focuses on advancing filtering and inference in complex high-dimensional data for improved processing speed and accuracy.

sclau Follow

Uploaded on Sep 21, 2024 | 0 Views

Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

E N D

Presentation Transcript

Fast High-dimensional Filtering and Inference in Fully-connected CRF 2015. 3. 23. Jeany Son 1

Papers Fast High-Dimensional Filtering Using the Permutohedral Lattice, Adams, A. B., Baek, J. and Davis, M. A., EUROGRAPHICS 2010. Efficient Inference in Fully Connected CRFs with Gaussian Edge Potentials, Philipp Krahenbuhl, Vladlen Koltun, NIPS 2011. 2

High-dimensional Gaussian filtering Gaussian blur : p = 2-dim pixel location Color bilateral filter : p = 5-dim color+pixel location Non-local mean : p = derived from local neighborhoods around each pixel 3

High-dimensional Gaussian filtering can be implemented splat-blur-slice bilateral filter of a one-dimensional signal 4

Recent works For accelerating Bilateral grid : regular grid of samples Gaussian KD-Tree : a cloud of samples stored in a kd-tree Permutohedral Lattice 5

Recent works For accelerating Permutohedral lattice vs. Bilateral grid : exponentially cheaper than the multi-linear interpolation Gaussian KD-Tree : not suffer from the irregularity and parameter-heavy nature of the randomly bifurcating kd-tree queries 6

Permutohedral lattice for high-dimensional filtering Projection of the scaled regular grid (d + 1)Zd+1along the vector 1 1 = [1, ,1] onto the hyperplane Hd: ? 1 1 = 0 Time complexity : O(d2n) Space complexity : O(dn) d=2 7

The Permutohedral Lattice Points in the lattice are those points with integer coordinates that sum to zero and have a consistent remainder modulo d+1 It tessellates high-dimensional space with uniform simplices Simplex vertex d=2 ex) d=4 8

Canonical simplex Translation and permutation invariant a unique simplex determined by l0 and the ordering of the coordinates of l0 ? 2 1 1 0 2 2 1 9

The Permutohedral Lattice - properties The permutohedral lattice tessellates Hdwith uniform simplices. can use barycentric interpolation The vertices of the simplex containing any point in Hdcan be computed in O(d2) time. (splat & slice) The nearest neighbors of a lattice point can be computed in O(d2) time. (blur) 10

Generating position vectors Embed the position vectors in subspace Hd Orthogonal basis O(d) time using the recurrence 11

Splatting (= Slicing) : O(d2n) Each input value splats onto the vertices of its enclosing simplex using barycentric weights Barycentric coordinate The lattice point values are stored in a hash table hash table access cost O(d) * O(d) times access * each pixel n = O(d2n) 12

Blurring : O(d2l) Regular Gaussian blur within the subspace To do this we convolve by the kernel [1 2 1] along each lattice direction O(d2l) Looking up neighbors O(d) * hash table comparison O(d) * each lattice 13