by Zoltan Kato, Mark Berthod, Josiane Zerubia
Abstract:
In this paper, we are interested in massively parallel multiscale relaxation algorithms applied to image classification. It is well known that multigrid methods can improve significantly the convergence rate and the quality of the final results of iterative relaxation techniques. First, we present a classical multiscale model which consists of a label pyramid and a whole observation field. The potential functions of coarser grids are derived by simple computations. The optimization problem is first solved at the higher scale by a parallel relaxation algorithm, then the next lower scale is initialized by a projection of the result. Second, we propose a hierarchical Markov Random Field model based on this classical model. We introduce new interactions between neighbor levels in the pyramid. It can also be seen as a way to incorporate cliques with far apart sites for a reasonable price. This model results in a relaxation algorithm with a new annealing scheme: The Multi-Temperature Annealing (MTA) scheme, which consists of associating higher temperatures to higher levels, in order to be less sensitive to local minima at coarser grids. The convergence to the global optimum is proved by a generalisation of the annealing theorem of Geman and Geman.
Reference:
Zoltan Kato, Mark Berthod, Josiane Zerubia, A Hierarchical Markov Random Field Model and Multi-Temperature Annealing for Parallel Image Classification, In Computer Vision, Graphics and Image Processing: Graphical Models and Image Processing, volume 58, no. 1, pp. 18-37, 1996.
Bibtex Entry:
@string{cvgipgmip="Computer Vision, Graphics and Image Processing: Graphical Models and Image Processing"}
@Article{Kato-etal96,
author = {Kato, Zoltan and Berthod, Mark and Zerubia, Josiane},
title = {A Hierarchical {M}arkov Random Field Model and
Multi-Temperature Annealing for Parallel Image
Classification},
journal = cvgipgmip,
year = 1996,
volume = 58,
number = 1,
pages = {18--37},
month = jan,
ps = {papers/cvgip.ps},
pdf = {papers/cvgip.pdf},
abstract = {In this paper, we are interested in massively
parallel multiscale relaxation algorithms applied to
image classification. It is well known that
multigrid methods can improve significantly the
convergence rate and the quality of the final
results of iterative relaxation techniques. First,
we present a classical multiscale model which
consists of a label pyramid and a whole observation
field. The potential functions of coarser grids are
derived by simple computations. The optimization
problem is first solved at the higher scale by a
parallel relaxation algorithm, then the next lower
scale is initialized by a projection of the
result. Second, we propose a hierarchical Markov
Random Field model based on this classical model. We
introduce new interactions between neighbor levels
in the pyramid. It can also be seen as a way to
incorporate cliques with far apart sites for a
reasonable price. This model results in a relaxation
algorithm with a new annealing scheme: The
Multi-Temperature Annealing (MTA) scheme, which
consists of associating higher temperatures to
higher levels, in order to be less sensitive to
local minima at coarser grids. The convergence to
the global optimum is proved by a generalisation of
the annealing theorem of Geman and Geman.}
}