Skip to main content
SpringerLink
Log in

Recursive-in-order least-squares parameter estimation algorithm for 2-D noncausal Gaussian Markov random field model

  • Published:
Circuits, Systems and Signal Processing Aims and scope Submit manuscript

Abstract

We present in this paper a recursive-in-order least-squares (LS) algorithm to compute efficiently the parameters of a 2-D Gaussian Markov random field (GMRF) model. The algorithm is based on the fact that the least-squares estimation of the parameters of a 2-D noncausal GMRF model is consistent and the coefficient matrix in the normal equation has near-to-block-Toeplitz structure. Hence, it has a Levinson-like form for the updating of model parameters by introducing auxiliary variables. Moreover, this paper proposes the concept ofrecursive path for 2-D recursive-in-order algorithms, and points out that there exists a tradeoff between fast computation of the parameters and accurate choice of model support; a compromise recursive path is then suggested where the orders change alternately in two directions. The computational complexity of the developed algorithm is analyzed, and the results show that the algorithm is more efficient when either the image size or the model support is larger. It is found that the total number of multiplications (mps) involved in the new algorithm is only about 14% of that in the conventional LS method when the image size is 512 × 512 and the neighbor set of the model is a 17 × 17 window. Computer simulation results using the recursive-in-order algorithm developed in this paper and the conventional LS method are given to verify the correctness of the new algorithm.

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

Access this article

Log in via an institution

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

Instant access to the full article PDF.

Similar content being viewed by others

References

  1. C. Therien, T. Quatieri, and D. Dudgeon, Statistical model-based algorithms for image analysis,Proc. IEEE, Vol. 74, pp. 532–551, April, 1986.

    Google Scholar 

  2. A. Rosenfeld (editor),Image Models, Academic Press, New York, 1981.

    Google Scholar 

  3. R. Chellappa and A. A. Sawchuk (editors),Digital Image Processing and Analysis: Vols. 1 and 2, IEEE Computer Society Press, 1985.

  4. R. Chellappa, Two-dimensional discrete Gaussian Markov random field models for image processing,Progress in Pattern Recognition 2, L. N. Kanal and A. Rosenfeld, eds., North Holland Publ. Co., New York, NY, 1985, pp. 79–112.

    Google Scholar 

  5. R. Chellappa and R. L. Kashyap, Digital image restoration using spatial interaction models,IEEE Trans. Acoustics Speech Signal Processing, Vol. ASSP-30, No. 3, pp. 461–472, 1982.

    Google Scholar 

  6. S. Geman and G. Geman, Stochastic relaxation: Gibbs distribution, and the Bayesian restoration of images,IEEE Trans. Pattern Analysis and Machine Intelligence, Vol. PAMI-6, No. 6, pp. 721–741, 1984.

    Google Scholar 

  7. G. R. Cross and A. K. Jain, Markov random field texture models,IEEE Trans. Pattern Analysis and Machine Intelligence, Vol. PAMI-5, pp. 25–39, 1983.

    Google Scholar 

  8. M. Hassner and H. Elliott, Image segmentation using simple Markov random field models,Computer Graphics and Image Processing, Vol. 20, pp. 357–370, April, 1980.

    Google Scholar 

  9. H. Derin, H. Elliot, R. Cristi, and D. Geman, Bayes smoothing algorithms for segmentation of binary images modeled by Markov random fields,IEEE Trans. Pattern Analysis and Machine Intelligence, Vol. PAMI-6, No. 6, pp. 707–720, 1984.

    Google Scholar 

  10. M. Hassner and J. Sklansky, The use of Markov random field as model of textures,Computer Graphics and Image Processing, Vol. 12, pp. 357–370, April, 1980.

    Google Scholar 

  11. P. Bouthemy and P. Lalaande, Motion detection in a sequence using Gibbs distributions,Proc. of ICASSP, pp. 1651–1654, 1989.

  12. B. Chalmond, Image restoration using an estimated Markov model,Signal Processing, Vol. 15, pp. 115–129, 1988.

    Google Scholar 

  13. R. L. Kashyap and R. Chellappa, Estimation and choice of neighbors in spatial-interaction models of images,IEEE Trans. Information Theory, Vol. IT-29, No. 1, pp. 60–72, January, 1983.

    Google Scholar 

  14. P. Y. Zhao and Z. Y. He, Efficient order recursive LS algorithms for 2D SAR model fitting,Proc. of ICASSP, pp. 1200–1203,1988.

  15. N. Kalouptsidis, G. Carayannis, D. Manolakis, and E. Koukoutsis, Efficient recursive in order least squares FIR filtering and prediction,IEEE Trans. Acoustics Speech Signal Processing, Vol. ASSP-33, No. 4, pp. 1175–1186, October, 1985.

    Google Scholar 

  16. G. A. Glentis and N. Kalouptsidis, Efficient order recursive algorithms for multichannel least squares filtering,IEEE Trans. Signal Processing, Vol. 40, No. 6, pp. 1354–1374, June, 1992.

    Google Scholar 

  17. C. R. Zou,Two-dimensional random field models — recursive least squares parameter estimation algorithms and applications to image processing, Doctoral dissertation of Southeast University, Nanjing, China, 1990.

Download references

Author information

Authors and Affiliations

  1. Division of Digital Signal Processing, Department of Radio Engineering, Southeast University, 210018, Nanjing, People's Republic of China

    C. R. Zou & Z. Y. He

  2. Center for Signal Processing and Communications, Department of Electrical and Computer Engineering, Concordia University, H3G 1M8, Montreal, Quebec, Canada

    E. I. Plotkin & M. N. S. Swamy

Authors
  1. C. R. Zou
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. E. I. Plotkin
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. M. N. S. Swamy
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Z. Y. He
    View author publications

    You can also search for this author in PubMed Google Scholar

Additional information

This work was supported by the NSERC under Grants A-4070 and A-7739, and by the FCAR, Grant H-70.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Zou, C.R., Plotkin, E.I., Swamy, M.N.S. et al. Recursive-in-order least-squares parameter estimation algorithm for 2-D noncausal Gaussian Markov random field model. Circuits Systems and Signal Process 14, 87–110 (1995). https://doi.org/10.1007/BF01183750

Download citation

  • Received:

  • Accepted:

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF01183750

Keywords

Search

Navigation