Your browser does not support JavaScript!
http://iet.metastore.ingenta.com
1887

access icon free Fast algorithm for least-squares based image prediction

A new computationally efficient algorithm for two-dimensional sliding-window least-squares prediction is presented in this study. The fast algorithm is based on a recursive update of the Cholesky decomposition. Compared with the state-of-the-art algorithm, the proposed algorithm reduces the computational complexity from O(D 3) to O(D 2 h), where D is the predictor order and h is the height of the prediction patch. The computational improvement is made at the stage of solving the normal equations for which an update algorithm for the Cholesky decomposition of the covariance matrix is proposed. It is shown that a large part of the Cholesky decomposition at location n can be efficiently calculated by performing orthonormal updates on the Cholesky decomposition at n − 1. The computational improvement is made without requiring additional storage space. Extensive experiments using causal and non-causal predictors of varying shapes and sizes have confirmed that the proposed algorithm is consistently faster than the state-of-the-art algorithm and produces identical prediction images. The efficiency of the proposed algorithm is shown to be affected by the order in which pixels are sampled, thus an ordering procedure is proposed to minimise the number of numerical operations.

References

    1. 1)
    2. 2)
    3. 3)
      • 17. Seeger, M.: ‘Low rank updates for the Cholesky decomposition’. University of California at Berkeley, Technical Report, 2008.
    4. 4)
    5. 5)
      • 4. Ye, H.: ‘A study on lossless compression of greyscale images’. PhD thesis, Department of Electronic Engineering, La Trobe University, 2002.
    6. 6)
      • 18. Golub, G.H., Van Loan, C.F.: ‘Matrix computations’ (Johns Hopkins University Press, Maryland, USA, 2012), vol. 3.
    7. 7)
    8. 8)
      • 12. Box, G.E.P., Jenkins, G.M., Reinsel, G.C.: ‘Time series analysis: forecasting and control’ (Holden-Day, Oakland, CA, 1976).
    9. 9)
    10. 10)
    11. 11)
      • 20. Press, W.H.: ‘Numerical recipes: the art of scientific computing’ (Cambridge University Press, New York, USA, 2007).
    12. 12)
      • 11. Björck, Å.: ‘Numerical methods for least squares problems’. (SIAM, Pennsylvania, USA, 1996).
    13. 13)
    14. 14)
    15. 15)
    16. 16)
      • 3. Wu, X., Barthel, K., Zhang, W.: ‘Piecewise 2D autoregression for predictive image coding’. Proc. IEEE ICIP'98, October 1998, vol. 3, pp. 901904.
    17. 17)
      • 1. Kuroki, N., Nomura, T., Tomita, M., et al: ‘Lossless image compression by two-dimensional linear prediction with variable coefficients’, IEICE Trans. Fundam. Electron. Commun. Comput. Sci., 1992, 75, (7), pp. 882889.
    18. 18)
    19. 19)
    20. 20)
      • 6. Zhang, X., Wu, X.: ‘Structure preserving image interpolation via adaptive 2d autoregressive modeling’. Proc. IEEE ICIP'07, October 2007, vol. 4, pp. 193196.
    21. 21)
      • 15. Lawson, C.L., Hanson, R.J.: ‘Solving least squares problems’ (SIAM, Pennsylvania, USA, 1974), vol. 161.
http://iet.metastore.ingenta.com/content/journals/10.1049/iet-ipr.2016.0017
Loading

Related content

content/journals/10.1049/iet-ipr.2016.0017
pub_keyword,iet_inspecKeyword,pub_concept
6
6
Loading
This is a required field
Please enter a valid email address