Sparse PDF Maps for Non-Linear Multi-Resolution Image Operations
Siggraph Asia 2012
Markus Hadwiger Ronell Sicat Johanna Beyer Jens Krüger Torsten Möller
KAUST KAUST KAUST IVDA, DFKI, Intel VCI Simon Fraser University
We introduce a new type of multi-resolution image pyramid for high-resolution images called sparse pdf maps (sPDF-maps). Each pyramid level consists of a sparse encoding of continuous probability density functions (pdfs) of pixel neighborhoods in the original image. The encoded pdfs enable the accurate computation of non-linear image operations directly in any pyramid level with proper pre-filtering for anti-aliasing, without accessing higher or lower resolutions. The sparsity of sPDF-maps makes them feasible for gigapixel images, while enabling direct evaluation of a variety of non-linear operators from the same representation. We illustrate this versatility for anti-aliased color mapping, O(n) local Laplacian filters, smoothed local histogram filters (e.g., median or mode filters), and bilateral filters.


author = {M. Hadwiger and R. Sicat and J. Beyer
and J. Kr{\"u}ger and T. M{\"o}ller},
title = {Sparse PDF Maps for Non-Linear
Multi-Resolution Image Operations},
journal = {ACM Transactions on Graphics
(Proceedings of Siggraph Asia 2012)},
year = {2012},
volume = {31},
number = {6},
pages = {133:1--133:12},



Sparse PDF Maps sPDF-maps are a compact multi-resolution image pyramid data structure that sparsely encodes pre-computed pixel neighborhood probability density functions (pdfs) for all pixels in the pyramid. They enable the accurate, anti-aliased evaluation of non-linear image operators directly at any output resolution. A variety of operators can be computed at run time from the same pre-computed data structure in a way that scales to gigapixel images, such as local Laplacian filters for (b,d) detail enhancement or (c,e) smoothing, (f) median filters, (g) dominant mode filters, (h) maximum mode filters, (i) bilateral filters. The original image (a) has resolution 16, 898 × 14, 824 (250 Mpixels). Color Mapping Color mapping. (Top row) Gray-scale 21, 601 × 10, 801 (233 MPixels) bathymetry image from the NASA Blue Marble collection [NASA 2005]. (Center row) Anti-aliased color mapping computed from the sPDF-map; (Bottom row) Standard pre-filtering and downsampling followed by color mapping: coarser resolutions introduce wrong colors, and whole structures are changing or disappearing. Local Laplacian Filtering Local Laplacian filtering with an sPDF-map in O(n) time. (Top row) Night scene of resolution 47, 908 × 7, 531 (361 Mpixels). The top third of the image is shown with detail enhancement (σr = 0.2, α = 0.25), the center third is the original image, and the bottom third is shown with smoothing (σr = 0.2, α = 3.0). (Bottom row) Images used by Paris et al. [2011]: left-hand image of each pair with detail enhancement (σr = 0.4, α = 0.25), right-hand image with smoothing (σr = 0.2, α = 2.0). RGB color channels were computed separately. Local Laplacian Smoothing Local Laplacian smoothing. sPDF-map results vs. the original implementation of Paris et al. (σr = 0.2, α = 2.0). (a,b) level 0 (1, 744 × 1, 160); (c,d) level 3 (218 × 145). (a,c) Paris et al.; (b,d) sPDF-map. Luminance PSNR [dB] between (a,b) 35, (c,d) 36. Local Laplacian Detail Enhancement Local Laplacian detail enhancement. sPDF-map re- sults vs. the original implementation of Paris et al. (σr = 0.2, α = 0.5). Flower (800 × 533) level 0: (a) Paris et al. (b) sPDF-maps. Luminance PSNR between (a,b) 37 dB. Smoothed Local Histogram Filtering Smoothed local histogram filtering. (a,b) Beach image in (a) dominant mode-filtered (luminance only) in (b). (f,g) Rock image in HSV color model: Standard downsampling introduces strong haloes of the wrong color around the rock (f), whereas dominant mode-filtering the H and V channels correctly preserves the circular domain of the hue channel (g). (c,d,e) and (h,i,j): Median filtering (luminance only) using sPDF-maps vs. downsampling and then filtering. (c,h) Original zoom-ins of the Night Scene (c) and the Machu Picchu (h) images. (d,i) Median filtering with sPDF-maps prevents over-smoothing by properly preserving the non-linearity of the image operation. (e,j) Median filtering after downsampling introduces strong over-smoothing that cannot be reversed by the median filter applied directly at the coarser resolution. Median Filtering Median filtering. (a) Original image (320 × 428) with salt and pepper noise. (b) Ground truth 5 × 5 median applied to level 0, then downsampled to level 1. (g) Naive equivalent median computed in level 1. sPDF-map where Wj is a Gaussian of size (c,d,e) 3 × 3, (h,i,j) 5 × 5. Median from sPDF-map with (c,h) 1 coefficient chunk, (d,i) 2 chunks. (f) Gaussian pyramid level 1 (160 × 214). (e,j) E[Xp] of sPDF-map level 1 (top half: 1 coefficient chunk, bottom half: 2 chunks). PSNR [dB] between (g,b): 30, (c,b): 30, (d,b): 36, (h,b): 38, (i,b): 39. Bilateral Filtering Bilateral Filtering Bilateral filtering. (Top row) Zoom-ins of original 16, 898 × 14, 824 image (a) at level 4: (b) Ground truth bilateral, (c) sPDF-map bilateral, (d) Naive bilateral. Luminance PSNR [dB] between (c,b) 43, (d,b) 41. (Bottom row) (e) Original image (512 × 512). The sPDF-map of (e) uses a Wj of size 3 × 3 and two coefficient chunks. Zoom-ins from (f,g,h,i) level 1, (j,k,l,m) level 2. (f,j) Downsampled image, no bilateral filtering. (g,k) Ground truth bilateral. (h,l) sPDF-map bilateral. (i,m) Naive bilateral. PSNR [dB] between (h,g) 37, (i,g) 35, (l,k) 38, (m,k) 37.