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

Slide Note
Embed
Share

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.


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


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

  2. 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

  3. 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

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

  5. 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

  6. 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

  7. 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

  8. 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

  9. 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

  10. 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

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

  12. 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

  13. 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

  14. Embed to the permutohedral lattice Embed each downsampled points to the lattice 14

  15. Embed to the permutohedral lattice Embed each downsampled points to the lattice 15

  16. Embed to the permutohedral lattice Embed each downsampled points to the lattice 16

  17. Embed to the permutohedral lattice Embed each downsampled points to the lattice 17

  18. Gaussian blurring Apply Gaussian blurring along axes 18

  19. Gaussian blurring Apply Gaussian blurring along axes 19

  20. Gaussian blurring Apply Gaussian blurring along axes 20

  21. Slicing Upsample the points 21

  22. Slicing Upsample the points 22

  23. Final upsampled points 23

  24. Results and Comparisons - Running times and memory 24

  25. The fastest method for a variety of dimensionalities and filter sizes 25

Related


More Related Content