Fast Weighted Histograms for Bilateral Filtering and Nearest Neighbor Searching
Authors:
- 7 May 2015
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Circuits and Systems for Video Technology
- Vol. 26 (5) , 891-902
Abstract
The locality sensitive histogram (LSH) injects spatial information into the local histogram in an efficient manner, and has been demonstrated to be very effective for visual tracking. In this paper, we explore the application of this efficient histogram in two important problems. We first extend the LSH to linear time bilateral filtering, and then propose a new type of histogram for efficiently computing edge-preserving nearest neighbor fields (NNFs). While the existing histogram-based bilateral filtering methods are the state of the art for efficient grayscale image processing, they are limited to box spatial filter kernels only. In our first application, we address this limitation by expressing the bilateral filter as a simple ratio of linear functions of the LSH, which is able to extend the box spatial kernel to an exponential kernel. The computational complexity of the proposed bilateral filter is linear in the number of image pixels. In our second application, we derive a new bilateral weighted histogram (BWH) for NNF. The new histogram maintains the efficiency of LSH, which allows approximate NNF to be computed independent of patch size. In addition, BWH takes both spatial and color information into account, and thus provides higher accuracy for histogram-based matching, especially around color edges.Keywords
Funding Information
- General Research Fund
- Early Career Scheme through the Research Grants Council, Hong Kong (CityU 115112, CityU 21201914)
- National Science Foundation (NSF) CAREER (1149783)
- NSF Information and Intelligent Systems (1152576)
This publication has 35 references indexed in Scilit:
- Domain transform for edge-aware image and video processingACM Transactions on Graphics, 2011
- Bilateral Filtering: Theory and ApplicationsFoundations and Trends in Computer Graphics and Vision, 2009
- PatchMatchACM Transactions on Graphics, 2009
- Gaussian KD-trees for fast high-dimensional filteringACM Transactions on Graphics, 2009
- Edge-avoiding wavelets and their applicationsACM Transactions on Graphics, 2009
- Video enhancement using per-pixel virtual exposuresACM Transactions on Graphics, 2005
- Digital photography with flash and no-flash image pairsACM Transactions on Graphics, 2004
- Kernel-based object trackingIEEE Transactions on Pattern Analysis and Machine Intelligence, 2003
- Fast bilateral filtering for the display of high-dynamic-range imagesACM Transactions on Graphics, 2002
- An Algorithm for Finding Best Matches in Logarithmic Expected TimeACM Transactions on Mathematical Software, 1977