“Smoothed local histogram filters” by Kass and Solomon

  • ©Michael Kass and Justin M. Solomon




    Smoothed local histogram filters



    Local image histograms contain a great deal of information useful for applications in computer graphics, computer vision and computational photography. Making use of that information has been challenging because of the expense of computing histogram properties over large neighborhoods. Efficient algorithms exist for some specific computations like the bilateral filter, but not others. Here, we present an efficient and practical method for computing accurate derivatives and integrals of locally-weighted histograms over large neighborhoods. The method allows us to compute the location, height, width and integral of all local histogram modes at interactive rates. Among other things, it enables the first constant-time isotropic median filter, robust isotropic image morphology operators, an efficient “dominant mode” filter and a non-iterative alternative to the mean shift. In addition, we present a method to combat the over-sharpening that is typical of histogram-based edge-preserving smoothing. This post-processing step should make histogram-based filters not only fast and efficient, but also suitable for a variety of new applications.


    1. Adams, A., Gelfand, N., Dolson, J., and Levoy, M. 2009. Gaussian kd-trees for fast high-dimensional filtering. ACM Trans. on Graphics 28, 3, 1–12. Google ScholarDigital Library
    2. Babaud, J., Witkin, A., Baudin, M., and Duda, R. 1986. Uniqueness of the Gaussian kernel for scale-space filtering. IEEE Trans. Pattern Anal. Mach. Intell. 8, 1, 26–33. Google ScholarDigital Library
    3. Barash, D., and Comaniciu, D. 2004. A common framework for nonlinear diffusion, adaptive smoothing, bilateral filtering and mean shift. Image and Vision Computing 22, 73–81.Google ScholarCross Ref
    4. Bousseau, A., Neyret, F., Thollot, J., and Salesin, D. 2007. Video watercolorization using bidirectional texture advection. ACM Trans. on Graphics 26, 3, 104. Google ScholarDigital Library
    5. Burt, P. J., and Adelson, E. H. 1983. The Laplacian pyramid as a compact image code. IEEE Trans. on Communications COM-31, 4, 532–540.Google ScholarCross Ref
    6. Burt, P. 1983. Fast filter transforms for image processing. Computer Graphics and Image Processing 16, 532–540.Google Scholar
    7. Chen, J., Paris, S., and Durand, F. 2007. Real-time edge-aware image processing with the bilateral grid. ACM Trans. on Graphics 23, 3 (July), 103. Google ScholarDigital Library
    8. Comaniciu, D., and Meer, P. 2002. Mean shift: A robust approach toward feature space analysis. IEEE Trans. on Pattern Analysis and Machine Intelligence 24, 5, 603–619. Google ScholarDigital Library
    9. Deriche, R. 1993. Recursively implementing the Gaussian and its derivatives. Tech. Rep. 1893, INRIA, Unit de Recherche Sophia-Antipolis.Google Scholar
    10. Dominguez, G., Bischof, H., and Beichel, R. 2003. Fast 3d mean shift filter for CT images. In Image Analysis, Proc. SCIA ‘2003, Springer, 59–97. Google ScholarDigital Library
    11. Duda, R., and Hart, P. 1973. Pattern Classification and Scene Analysis. Wiley.Google Scholar
    12. Durand, F., and Dorsey, J. 2002. Fast bilateral filtering for the display of high-dynamic-range images. In Proc. SIGGRAPH ’02, 257–266. Google ScholarDigital Library
    13. Farbman, Z., Fattal, R., Lischinski, D., and Szeliski, R. 2008. Edge-preserving decompositions for multi-scale tone and detail manipulation. ACM Trans. on Graphics 27, 3. Google ScholarDigital Library
    14. Fattal, R., Agrawala, M., and Rusinkiewicz, S. 2008. Multiscale shape and detail enhancement from multi-light image collections. ACM Trans. on Graphics 26, 3. Google ScholarDigital Library
    15. Felsberg, M., Forsséen, P.-E., and Scharr, H. 2006. Channel smoothing: Efficient robust smoothing of low-level signal features. IEEE Trans. on Pattern Analysis and Machine Intelligence 28, 2, 209–222. Google ScholarDigital Library
    16. Fukunaga, K., and Hostetler, L. D. 1975. The estimation of the gradient of a density function, with applications in pattern recognition. IEEE Trans. on Information Theory 21, 32–40.Google ScholarDigital Library
    17. Haralick, R., Sternberg, S., and Zhuang, X. 1987. Image analysis using mathematical morphology. IEEE Trans. Pattern Analysis and Machine Intelligence 9, 4 (July), 532–550. Google ScholarDigital Library
    18. Huang, T. 1975. Two-Dimensional Signal Processing II: Transforms and Median Filters. Springer Verlag, Berlin. Google ScholarDigital Library
    19. Koenderink, J. J., and Doorn, A. J. V. 1999. The structure of locally orderless images. International Journal of Computer Vision 31, 2–3, 159–168. Google ScholarDigital Library
    20. Paris, S., and Durand, F. 2006. A fast approximation of the bilateral filter using a signal processing approach. In Proc. European Conference on Computer Vision (ECCV ’06), 568–580. Google ScholarDigital Library
    21. Paris, S., and Durand, F. 2007. A topological approach to hierarchical segmentation using mean shift. In Proc. IEEE conference on Computer Vision and Pattern Recognition (CVPR’07).Google Scholar
    22. Paris, S., Kornprobst, P., Tumblin, J., and Durand, F. 2007. A gentle introduction to bilateral filtering and its applications. In SIGGRAPH ’07: ACM SIGGRAPH 2007 courses. Google ScholarDigital Library
    23. Parzen, E. 1962. On estimation of a probability density function and mode. Ann. Math. Stat. 33, 1065–1076.Google ScholarCross Ref
    24. Perreault, S., and Hebert, P. 2007. Median filtering in constant time. IEEE Trans. on Image Processing 16, 9 (Sep.), 2389–2394. Google ScholarDigital Library
    25. Porikli, F. 2005. Integral histogram: A fast way to extract histograms in cartesian spaces. In IEEE Conference on Computer Vision and Pattern Recognition (CVPR ’05), 829–836. Google ScholarDigital Library
    26. Porikli, F. 2008. Constant time o(1) bilateral filtering. In IEEE Conference on Computer Vision and Pattern Recognition (CVPR ’08), 1–8.Google ScholarCross Ref
    27. Subr, K., Soler, C., and Durand, F. 2009. Edge-preserving multiscale image decomposition based on local extrema. In SIGGRAPH Asia ’09: ACM SIGGRAPH Asia 2009 papers, 1–9. Google ScholarDigital Library
    28. Tumblin, J., and Turk, G. 1999. LCIS: A boundary hierarchy for detail-preserving contrast reduction. In Proc. SIGGRAPH ’99, 83–90. Google ScholarDigital Library
    29. van Herk, M. 1992. A fast algorithm for local minimum and maximum filters on rectangular and octagonal kernels. Pattern Recognition Letters 13, 7, 517–521. Google ScholarDigital Library
    30. Weiss, B. 2006. Fast median and bilateral filtering. In Proc. SIGGRAPH ’06, 519–526. Google ScholarDigital Library

ACM Digital Library Publication:

Overview Page: