Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Fast Global Image Smoothing via Quasi Weighted Least Squares

  • Published:
International Journal of Computer Vision Aims and scope Submit manuscript

Abstract

Image smoothing is a long-studied research area with tremendous approaches proposed. However, how to perform high-quality image smoothing with less computational cost still remains a challenging problem. In this paper, we try to solve this problem with a newly proposed global optimization based method named quasi weighted least squares. In our method, the 2D image is first re-ordered into a 1D vector via a newly proposed 2D-to-1D transformation. We then properly remove some original 2D neighborhood connections. The remaining neighboring pixels can simply form 1D neighborhood connections in the transformed 1D vector while they still contain the 2D neighborhood information in the original 2D image space. These together result in a quite compact linear system that can be easily and efficiently solved, which makes our method a fast global image smoothing approach. Our method is on par with the fastest approaches in terms of processing speed, however, it is able to yield comparable performance with the state-of-the-art ones in terms of smoothing quality. Our method can also work as a solver to approximate the weighted least squares problem in complex systems, and it can achieve similar results but runs much faster. The efficiency and effectiveness of our method are validated through comprehensive experiments in several tasks. Our code is publicly available at: https://github.com/wliusjtu/Q-WLS.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9
Fig. 10
Fig. 11
Fig. 12
Fig. 13
Fig. 14
Fig. 15
Fig. 16
Fig. 17
Fig. 18
Fig. 19
Fig. 20
Fig. 21
Fig. 22
Fig. 23
Fig. 24

Similar content being viewed by others

Explore related subjects

Discover the latest articles, news and stories from top researchers in related subjects.

Notes

  1. The incomplete Cholesky decomposition of the coefficient matrix (\(I+\lambda L\)) is adopted as the pre-conditioner.

  2. The symmetric property is straightforward. For the positive definite property, we can simply prove this by the definition: for any vector x, we always have \(x^TA^qx>0.\)

  3. https://github.com/jimmy-ren/vcnn_double-bladed/tree/master/applications/deep_edge_aware_filters, https://github.com/Liusifei/caffe-lowlevel, https://github.com/CQFIO/FastImageProcessing, https://github.com/fqnchina/DecoupleLearning, https://github.com/DmitryUlyanov/deep-image-prior, https://github.com/Yijunmaverick/DeepJointFilter, https://github.com/lime-j/DeepFSPIS.

  4. http://people.csail.mit.edu/sparis/bf/.

  5. AMF: amFilter() DTF: dtFilter(), GF: guidedFilter(), FGS: fastGlobalSmootherFilter(), FBS: fastBilateralSolverFilter().

  6. MATLAB build-in function locallapfilt().

  7. EAW: https://www.cs.huji.ac.il/~raananf/projects/eaw/, SG-WLS: https://github.com/wliusjtu/Semi-Global-Weighted-Least-Squares-in-Image-Filtering, WLS: https://www.cs.huji.ac.il/~danix/epd/wlsFilter.m, \(L_0\) norm: http://www.cse.cuhk.edu.hk/~leojia/projects/L0smoothing/, ILS: https://github.com/wliusjtu/Real-time-Image-Smoothing-via-Iterative-Least-Squares, fast WMF: https://jiaya.me/projects/fastwmedian/index.htm, SGF: http://www.feihuzhang.com/SGF.html, PTF: https://github.com/RewindL/pyramid_texture_filtering.

  8. The “NumIntensityLevel” option in locallapfilt().

  9. https://people.csail.mit.edu/sparis/publi/2011/siggraph/.

  10. https://www.cs.huji.ac.il/~danix/epd/.

References

  • Abadi, M., Agarwal, A., Barham, P., Brevdo, E., Chen, Z., Citro, C., Corrado, G. S., Davis, A., Dean, J., Devin, M., Ghemawat, S., Goodfellow, I., Harp, A., Irving, G., Isard, M., Jia, Y., Jozefowicz, R., Kaiser, L., Kudlur, M., Levenberg, J., Mané, D., Monga, R., Moore, S., Murray, D., Olah, C., Schuster, M., Shlens, J., Steiner, B., Sutskever, I., Talwar, K., Tucker, P., Vanhoucke, V., Vasudevan, V., Viégas, F., Vinyals, O., Warden, P., Wattenberg, M., Wicke, M., Yu, Y., & Zheng, X. (2015). TensorFlow: Large-scale machine learning on heterogeneous systems. http://tensorflow.org/, software available from tensorflow.org

  • Adams, A., Baek, J., & Davis, M. A. (2010). Fast high-dimensional filtering using the permutohedral lattice. Computer Graphics Forum, Wiley Online Library, 29, 753–762.

  • Aubry, M., Paris, S., Hasinoff, S. W., Kautz, J., & Durand, F. (2014). Fast local Laplacian filters: Theory and applications. ACM Transactions on Graphics (TOG), 33(5), 167.

    Article  Google Scholar 

  • Bao, L., Song, Y., Yang, Q., Yuan, H., & Wang, G. (2014). Tree filtering: Efficient structure-preserving smoothing with a minimum spanning tree. IEEE Transactions on Image Processing (TIP), 23(2), 555–569.

    Article  MathSciNet  Google Scholar 

  • Barron, J. T., Adams, A., Shih, Y., & Hernández, C. (2015). Fast bilateral-space stereo for synthetic defocus. In Computer vision and pattern recognition (CVPR) (pp. 4466–4474).

  • Barron, J. T., & Poole, B. (2016). The fast bilateral solver. In European conference on computer vision (ECCV) (pp. 617–632). Springer.

  • Chen, J., Paris, S., & Durand, F. (2007). Real-time edge-aware image processing with the bilateral grid. ACM Transactions on Graphics, 26, 103.

    Article  Google Scholar 

  • Chen, Q., Xu, J., & Koltun, V. (2017). Fast image processing with fully-convolutional networks. IEEE International Conference on Computer Vision (ICCV), 9, 2516–2525.

    Google Scholar 

  • Dai, L., Yuan, M., Zhang, F., & Zhang, X. (2015). Fully connected guided image filtering. In IEEE international conference on computer vision (ICCV) (pp. 352–360).

  • Dong, X., Yokoya, N., Wang, L., & Uezato, T. (2022). Learning mutual modulation for self-supervised cross-modal super-resolution. In European conference on computer vision (ECCV) (pp. 1–18). Springer.

  • Durand, F., & Dorsey, J. (2002). Fast bilateral filtering for the display of high-dynamic-range images. ACM Transactions on Graphics, 21, 257–266.

    Article  Google Scholar 

  • Eisemann, E., & Durand, F. (2004). Flash photography enhancement via intrinsic relighting. ACM Transactions on Graphics, 23, 673–678.

    Article  Google Scholar 

  • Fan, Q., Chen, D., Yuan, L., Hua, G., Yu, N., & Chen, B. (2018a). Decouple learning for parameterized image operators. In Proceedings of the European conference on computer vision (ECCV) (pp. 442–458).

  • Fan, Q., Chen, D., Yuan, L., Hua, G., Yu, N., & Chen, B. (2019). A general decoupled learning framework for parameterized image operators. IEEE Transactions on Pattern Analysis and Machine Intelligence (TPAMI), 43(1), 33–47.

    Article  Google Scholar 

  • Fan, Q., Yang, J., Wipf, D., Chen, B., & Tong, X. (2018b). Image smoothing via unsupervised learning. ACM Transactions on Graphics (TOG), 37(6), 1–14.

  • Farbman, Z., Fattal, R., Lischinski, D., & Szeliski, R. (2008). Edge-preserving decompositions for multi-scale tone and detail manipulation. ACM Transactions on Graphics, 27, 67.

    Article  Google Scholar 

  • Fattal, R. (2009). Edge-avoiding wavelets and their applications. ACM Transactions on Graphics, 28, 22.

    Article  Google Scholar 

  • Fattal, R., Agrawala, M., & Rusinkiewicz, S. (2007). Multiscale shape and detail enhancement from multi-light image collections. ACM Transactions on Graphics (TOG), 26(3), 51.

    Article  Google Scholar 

  • Ferstl, D., Reinbacher, C., Ranftl, R., Rüther, M., & Bischof, H. (2013). Image guided depth upsampling using anisotropic total generalized variation. In International conference on computer vision (ICCV) (pp. 993–1000).

  • Ferstl, D., Reinbacher, C., Riegler, G., Rüther, M., & Bischof, H. (2015). Learning depth calibration of time-of-flight cameras. In British machine vision conference (BMVC) (pp. 102–1).

  • Gastal, E. S., & Oliveira, M. M. (2011). Domain transform for edge-aware image and video processing. ACM Transactions on Graphics, 30, 69.

    Article  Google Scholar 

  • Gastal, E. S., & Oliveira, M. M. (2012). Adaptive manifolds for real-time high-dimensional filtering. ACM Transactions on Graphics, 31(4), 33.

    Article  Google Scholar 

  • Gu, S., Meng, D., Zuo, W., & Zhang, L. (2017). Joint convolutional analysis and synthesis sparse representation for single image layer separation. In Proceedings of the IEEE international conference on computer vision (ICCV) (pp. 1708–1716).

  • Guo, X., Li, Y., Ma, J., & Ling, H. (2018). Mutually guided image filtering. IEEE Transactions on Pattern Analysis and Machine Intelligence (TPAMI), 42(3), 694–707.

    Article  Google Scholar 

  • Ham, B., Cho, M., & Ponce, J. (2015). Robust image filtering using joint static and dynamic guidance. In IEEE conference on computer vision and pattern recognition (CVPR) (pp. 4823–4831).

  • Ham, B., Cho, M., & Ponce, J. (2018). Robust guided image filtering using nonconvex potentials. IEEE Transactions on Pattern Analysis and Machine Intelligence (TPAMI), 40(1), 192–207.

    Article  Google Scholar 

  • He, K., Sun, J., & Tang, X. (2013). Guided image filtering. IEEE Transactions on Pattern Analysis and Machine Intelligence (TPAMI), 35(6), 1397–1409.

    Article  Google Scholar 

  • Holland, P. W., & Welsch, R. E. (1977). Robust regression using iteratively reweighted least-squares. Communications in Statistics-Theory and Methods, 6(9), 813–827.

    Article  Google Scholar 

  • Jia, Y., Shelhamer, E., Donahue, J., Karayev, S., Long, J., Girshick, R., Guadarrama, S., & Darrell, T. (2014). Caffe: Convolutional architecture for fast feature embedding. arXiv preprint arXiv:1408.5093

  • Kim, B., Ponce, J., & Ham, B. (2021). Deformable kernel networks for joint image filtering. International Journal of Computer Vision (IJCV), 129(2), 579–600.

    Article  Google Scholar 

  • Kopf, J., Cohen, M. F., Lischinski, D., & Uyttendaele, M. (2007). Joint bilateral upsampling. ACM Transactions on Graphics, 26, 96.

    Article  Google Scholar 

  • Lanckriet, G., & Sriperumbudur, B. K. (2009). On the convergence of the concave–convex procedure. Advances in Neural Information Processing Systems (NeurIPS), 22, 1759–1767.

    Google Scholar 

  • LeCun, Y., Bengio, Y., & Hinton, G. (2015). Deep learning. Nature, 521(7553), 436–444.

    Article  Google Scholar 

  • Li, M., Fu, Y., Li, X., & Guo, X. (2022). Deep flexible structure preserving image smoothing. In Proceedings of the 30th ACM international conference on multimedia (pp. 1875–1883).

  • Li, Y., Huang, J. B., Ahuja, N., & Yang, M. H. (2019). Joint image filtering with deep convolutional networks. IEEE Transactions on Pattern Analysis and Machine Intelligence (TPAMI), 41(8), 1909–1923.

    Article  Google Scholar 

  • Li, Y., Min, D., Do, M. N., & Lu, J. (2016). Fast guided global interpolation for depth and motion. In European conference on computer vision (ECCV) (pp. 717–733). Springer.

  • Liu, S., Pan, J., & Yang, M. H. (2016). Learning recursive filters for low-level vision via a hybrid neural network. In European conference on computer vision (ECCV) (pp 560–576). Springer.

  • Liu, W., Chen, X., Shen, C., Liu, Z., & Yang, J. (2017). Semi-global weighted least squares in image filtering. In IEEE International Conference on Computer Vision (ICCV) (Vol. 2).

  • Liu, W., Zhang, P., Huang, X., Yang, J., Shen, C., & Reid, I. (2020). Real-time image smoothing via iterative least squares. ACM Transactions on Graphics, 39(3), 1–24.

    Article  Google Scholar 

  • Liu, W., Zhang, P., Lei, Y., Huang, X., Yang, J., & Reid, I. (2020). A generalized framework for edge-preserving and structure-preserving image smoothing. Proceedings of the AAAI Conference on Artificial Intelligence (AAAI), 34, 11620–11628.

    Article  Google Scholar 

  • Liu, W., Zhang, P., Lei, Y., Huang, X., Yang, J., & Ng, M. (2021). A generalized framework for edge-preserving and structure-preserving image smoothing. IEEE Transactions on Pattern Analysis and Machine Intelligence (TPAMI), 44(10), 6631–6648.

    Article  Google Scholar 

  • Lu, J., Shi, K., Min, D., Lin, L., & Do, M. N. (2012). Cross-based local multipoint filtering. In Computer vision and pattern recognition (CVPR) (pp. 430–437). IEEE.

  • Ma, Z., He, K., Wei, Y., Sun, J., & Wu, E. (2013). Constant time weighted median filtering for stereo matching and beyond. In IEEE International Conference on Computer Vision (ICCV) (pp. 49–56). IEEE.

  • Mairal, J. (2015). Incremental majorization–minimization optimization with application to large-scale machine learning. SIAM Journal on Optimization, 25(2), 829–855.

    Article  MathSciNet  Google Scholar 

  • Mazumdar, A., Alaghi, A., Barron, J. T., Gallup, D., Ceze, L., Oskin, M., & Seitz, S. M. (2017). A hardware-friendly bilateral solver for real-time virtual reality video. In Proceedings of high performance graphics (p. 13). ACM.

  • Min, D., Choi, S., Lu, J., Ham, B., Sohn, K., & Do, M. N. (2014). Fast global image smoothing based on weighted least squares. IEEE Transactions on Image Processing (TIP), 23(12), 5638–5653.

    Article  MathSciNet  Google Scholar 

  • Paris, S., & Durand, F. (2006). A fast approximation of the bilateral filter using a signal processing approach. In European conference on computer vision (ECCV) (pp. 568–580).

  • Paris, S., Hasinoff, S. W., & Kautz, J. (2011). Local Laplacian filters: Edge-aware image processing with a Laplacian pyramid. ACM Transactions on Graphics, 30(4), 68.

    Article  Google Scholar 

  • Park, J., Kim, H., Tai, Y. W., Brown, M. S., & Kweon, I. (2011). High quality depth map upsampling for 3d-tof cameras. In IEEE international conference on computer vision (ICCV) (pp. 1623–1630). IEEE.

  • Paszke, A., Gross, S., Massa, F., Lerer, A., Bradbury, J., Chanan, G., Killeen, T., Lin, Z., Gimelshein, N., Antiga, L., Desmaison, A., Kopf, A., Yang, E., DeVito, Z., Raison, M., Tejani, A., Chilamkurthy, S., Steiner, B., Fang, L., et al. (2019). Pytorch: An imperative style, high-performance deep learning library. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d’Alché-Buc, E. Fox, & R. Garnett (Eds.), Advances in Neural Information Processing Systems (NeurIPS) (pp. 8024–8035). Curran Associates Inc.

    Google Scholar 

  • Petschnigg, G., Szeliski, R., Agrawala, M., Cohen, M., Hoppe, H., & Toyama, K. (2004). Digital photography with flash and no-flash image pairs. ACM Transactions on Graphics, 23(3), 664–672.

    Article  Google Scholar 

  • Porikli, F. (2008). Constant time o (1) bilateral filtering. In Computer Vision and Pattern Recognition (CVPR) (pp. 1–8). IEEE.

  • Riegler, G., Ferstl, D., Rüther, M., & Bischof, H. (2016a). A deep primal–dual network for guided depth super-resolution. In British machine vision conference (BMVC). The British Machine Vision Association.

  • Riegler, G., Ranftl, R., Rüther, M., Pock, T., & Bischof, H. (2015). Depth restoration via joint training of a global regression model and cnns. In British machine vision conference (BMVC). The British Machine Vision Association.

  • Riegler, G., Rüther, M., & Bischof, H. (2016b). Atgv-net: Accurate depth super-resolution. In European conference on computer vision (ECCV) (pp. 268–284). Springer.

  • Riegler, G., Ulusoy, A. O., Bischof, H., & Geiger, A. (2017). Octnetfusion: Learning depth fusion from data. In 2017 International conference on 3D vision (3DV) (pp. 57–66). IEEE.

  • Scharstein, D., & Pal, C. (2007). Learning conditional random fields for stereo. In 2007 IEEE conference on computer vision and pattern recognition (CVPR) (pp. 1–8). IEEE.

  • Shen, X., Yan, Q., Xu, L., Ma, L., & Jia, J. (2015). Multispectral joint image restoration via optimizing a scale map. IEEE Transactions on Pattern Analysis and Machine Intelligence (TPAMI), 37(12), 2518–2530.

    Article  Google Scholar 

  • Shen, X., Zhou, C., Xu, L., & Jia, J. (2015b). Mutual-structure for joint filtering. In IEEE international conference on computer vision (ICCV) (pp. 3406–3414).

  • Sweldens, W. (1998). The lifting scheme: A construction of second generation wavelets. SIAM Journal on Mathematical Analysis, 29(2), 511–546.

    Article  MathSciNet  Google Scholar 

  • Tan, X., Sun, C., & Pham, T. D. (2014). Multipoint filtering with local polynomial approximation and range guidance. In IEEE conference on computer vision and pattern recognition (CVPR) (pp. 2941–2948). IEEE.

  • Tomasi, C., & Manduchi, R. (1998). Bilateral filtering for gray and color images. In International conference on computer vision (ICCV) (pp. 839–846). IEEE.

  • Ulyanov, D., Vedaldi, A., & Lempitsky, V. (2018). Deep image prior. In Proceedings of the IEEE conference on computer vision and pattern recognition (CVPR) (pp. 9446–9454).

  • Vedaldi, A., & Lenc, K. (2015). Matconvnet: Convolutional neural networks for matlab. In Proceedings of the 23rd ACM international conference on multimedia (pp. 689–692).

  • Vinker, Y., Huberman-Spiegelglas, I., & Fattal, R. (2021). Unpaired learning for high dynamic range image tone mapping. In Proceedings of the IEEE/CVF international conference on computer vision (ICCV) (pp. 14,657–14,666).

  • Wang, H., Yang, M., Zhu, C., & Zheng, N. (2023). Rgb-guided depth map recovery by two-stage coarse-to-fine dense crf models. IEEE Transactions on Image Processing (TIP), 32, 1315–1328.

    Article  Google Scholar 

  • Watkins, D. S. (2004). Fundamentals of matrix computations (Vol. 64). Wiley.

    Google Scholar 

  • Xu, L., Lu, C., Xu, Y., & Jia, J. (2011). Image smoothing via l 0 gradient minimization. ACM Transactions on Graphics, 30, 174.

    Article  Google Scholar 

  • Xu, L., Ren, J., Yan, Q., Liao, R., & Jia, J. (2015). Deep edge-aware filters. In IEEE international conference on machine learning (ICML) (pp. 1669–1678).

  • Xu, L., Yan, Q., Xia, Y., & Jia, J. (2012). Structure extraction from texture via relative total variation. ACM Transactions on Graphics, 31(6), 139.

    Article  Google Scholar 

  • Yang, J., Ye, X., Li, K., Hou, C., & Wang, Y. (2014). Color-guided depth recovery from rgb-d data using an adaptive autoregressive model. IEEE Transactions on Image Processing (TIP), 23(8), 3443–3458.

    Article  MathSciNet  Google Scholar 

  • Yang, Q., Tan, K. H., & Ahuja, N. (2009). Real-time o (1) bilateral filtering. In Computer vision and pattern recognition (CVPR) (pp. 557–564). IEEE.

  • Yeganeh, H., & Wang, Z. (2012). Objective quality assessment of tone-mapped images. IEEE Transactions on Image Processing (TIP), 22(2), 657–667.

    Article  MathSciNet  Google Scholar 

  • Zhang, F., Dai, L., Xiang, S., & Zhang, X. (2015). Segment graph based image filtering: Fast structure-preserving smoothing. In IEEE international conference on computer vision (ICCV) (pp. 361–369).

  • Zhang, Q., Jiang, H., Nie, Y., & Zheng, W. S. (2023). Pyramid texture filtering. ACM Transactions on Graphics (TOG), 42(4), 1–11.

    Google Scholar 

  • Zhang, Q., Shen, X., Xu, L., & Jia, J. (2014a). Rolling guidance filter. In European conference on computer vision (ECCV) (pp. 815–830). Springer.

  • Zhang, Q., Xu, L., & Jia, J. (2014b). 100+ times faster weighted median filter (wmf). In IEEE conference on computer vision and pattern recognition (CVPR) (pp. 2830–2837). IEEE.

  • Zhang, Z., Kwok, J. T., & Yeung, D. Y. (2004). Surrogate maximization/minimization algorithms for adaboost and the logistic regression model. In Proceedings of international conference on machine learning (ICML) (p. 117).

Download references

Acknowledgements

This work is partly supported by NSFC (No. 24Z990200676, 62376153, 62101092, 62272071), Pujiang Progam (No. 22PJ1406600), National Key Research Development Project (2023YFF1104202), Shanghai Municipal Science and Technology Research Program (22511105600) and Major Project (2021SHZDZX0102), HKRGC GRF (No. 17201020, 17300021, C7004-21GF) and Joint NSFC-RGC (No. N-HKU76921).

Author information

Authors and Affiliations

  1. Department of Automation, Institute of Image Processing and Pattern Recognition, Shanghai Jiao Tong University, Shanghai, China

    Wei Liu, Xiaolin Huang & Jie Yang

  2. School of Artificial Intelligence, Dalian University of Technology, Dalian, China

    Pingping Zhang

  3. School of Computer Science, Chongqing University, Chongqing, China

    Hongxing Qin

  4. Department of Mathematics, Hong Kong Baptist University, Hong Kong, China

    Michael Ng

Authors
  1. Wei Liu
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Pingping Zhang
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Hongxing Qin
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Xiaolin Huang
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Jie Yang
    View author publications

    You can also search for this author in PubMed Google Scholar

  6. Michael Ng
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Wei Liu.

Additional information

Communicated by Minsu Cho.

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Liu, W., Zhang, P., Qin, H. et al. Fast Global Image Smoothing via Quasi Weighted Least Squares. Int J Comput Vis 132, 6039–6068 (2024). https://doi.org/10.1007/s11263-024-02105-8

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11263-024-02105-8

Keywords

Search

Navigation