9.6.1
Multi-resolution methods provide a means for improving the convergence of iterative relaxation procedures [Hackbusch 1985]. It is shown by [Terzopoulos 1986a ] that multi-resolution relaxation can be used to solve efficiently a number of low level vision problems. This class of techniques has been used for MRF computation by many authors [Konrad and Dubois 1988b,Barnard 1989,Bouman and Liu 1991,Kato et al. 1993b,Bouman and Shapiro]. Gidas (1990) proposes a method which uses the renormalization group theory, MRFs and Metropolis algorithm for global optimization. How to preserve the inter-relationships between objects in the scene using the renormalization group transformation are studied in [Geiger and Kogler Jr. 1993,Hurn and Gennison 1993,Petrou 1993].
An important issue in multi-resolution computation of MRFs is how to preserve the Markovianity and define consistent model descriptions at different resolutions. In general, the local Markovian property is not preserved at the coarse levels after a sub-sampling. In [Jeng 1992], two theorems are given on a periodic sub-sampling of MRFs. One gives necessary and sufficient conditions for preserving the Markovianity and the other state that there is at least one sub-sampling scheme by which the Markovianity is preserved. A multi-resolution treatment is presented by [Lakshmanan and Derin 1993] in which (possibly) non-Markov Gaussian fields are approximated by linear Gaussian MRFs. In [Heitz and Bouthemy 1994], a consistent set of parameters are determined for objective functions at different resolutions; a nonlinear multi-resolution relaxation algorithm, which has fast convergence towards quasi-optimal solutions, is developed. A general transformation model is considered in [Perez and Heitz 1994] as the ``restriction'' of an MRF, defined on a finite arbitrary non-directed graph, to a subset of its original sites; several results are derived for the preservation of the Markovianity which may be useful for designing consistent and tractable multi-resolution relaxation algorithms.