Two-dimensional generalisations of dynamic programming for image analysis

Dynamic programming (DP) is a fast, elegant method for solving many one-dimensional optimisation problems but, unfortunately, most problems in image analysis, such as restoration and warping, are two-dimensional. We consider three generalisations of DP. The first is iterated dynamic programming (IDP...

Full description

Saved in:
Bibliographic Details
Published in:Statistics and computing 2009-03, Vol.19 (1), p.49-56
Main Author: Glasbey, C. A.
Format: Article
Language:English
Subjects:
Algorithms
Artificial Intelligence
Computation
Dynamic programming
Mathematics and Statistics
Probability and Statistics in Computer Science
Simulated annealing
Statistical Theory and Methods
Statistics
Statistics and Computing/Statistics Programs
Stochasticity
Synthetic aperture radar
Two dimensional
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Dynamic programming (DP) is a fast, elegant method for solving many one-dimensional optimisation problems but, unfortunately, most problems in image analysis, such as restoration and warping, are two-dimensional. We consider three generalisations of DP. The first is iterated dynamic programming (IDP), where DP is used to recursively solve each of a sequence of one-dimensional problems in turn, to find a local optimum. A second algorithm is an empirical, stochastic optimiser, which is implemented by adding progressively less noise to IDP. The final approach replaces DP by a more computationally intensive Forward-Backward Gibbs Sampler, and uses a simulated annealing cooling schedule. Results are compared with existing pixel-by-pixel methods of iterated conditional modes (ICM) and simulated annealing in two applications: to restore a synthetic aperture radar (SAR) image, and to warp a pulsed-field electrophoresis gel into alignment with a reference image. We find that IDP and its stochastic variant outperform the remaining algorithms.
ISSN:0960-3174
1573-1375
DOI:10.1007/s11222-008-9068-9