Using dynamic programming for solving variational problems in vision
Abstract
Dynamic programming is discussed as an approach to solving variational problems in vision. Dynamic programming ensures global optimality of the solution, is numerically stable, and allows for hard constraints to be enforced on the behavior of the solution within a natural and straightforward structure. As a specific example of the approach's efficacy, applying dynamic programming to the energy-minimizing active contours is described. The optimization problem is set up as a discrete multistage decision process and is solved by a time-delayed discrete dynamic programming algorithm. A parallel procedure for decreasing computational costs is discussed.>
Integrity signals
Registry
Cites
Statistics
Claims the paper makes
Cites
A Computational Approach to Edge Detection
Canny, J. (1986) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.1986.4767851 · Cited by 30,004 · see citing works
Stochastic relaxation, gibbs distributions, and the bayesian restoration of images.
Geman, S., & Geman, D. (1984) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.1984.4767596 · Cited by 17,949 · see citing works
Kass, M., Witkin, A., & Terzopoulos, D. (1988) · International Journal of Computer Vision · doi:10.1007/bf00133570 · Cited by 17,165 · see citing works
Bellman, R. E. (2010) · doi:10.1515/9781400835386 · Cited by 14,588 · see citing works
Horn, B. K. P., & Schunck, B. G. (1981) · Artificial Intelligence · doi:10.1016/0004-3702(81)90024-2 · Cited by 10,312 · see citing works
Horn, B. K. P., & Schunck, B. G. (1981) · Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE · doi:10.1117/12.965761 · Cited by 7,443 · see citing works
Numerical Recipes--The Art of Scientific Computing.
Fritsch, F. N., Press, W. H., Flannery, B. P., Teukolsky, S. A., & Vetterling, W. T. (1988) · Mathematics of Computation · doi:10.2307/2007938 · Cited by 4,846 · see citing works
(1986) · Cited by 3,616 · see citing works
Adaptive Control Processes: A Guided Tour
Bellman, R. E. (1961) · doi:10.1515/9781400874668 · Cited by 2,802 · see citing works
Adaptive Control Processes: A Guided Tour.
Page, E. S., & Bellman, R. (1962) · Journal of the Royal Statistical Society Series A (General) · doi:10.2307/2343225 · Cited by 2,218 · see citing works
Freimer, M. L., Bellman, R., & Dreyfus, S. E. (1964) · Journal of the American Statistical Association · doi:10.2307/2282884 · Cited by 2,173 · see citing works
Blake, A., & Zisserman, A. (1987) · The MIT Press eBooks · doi:10.7551/mitpress/7132.001.0001 · Cited by 2,093 · see citing works
Bellman, R., & Dreyfus, S. E. (1962) · Princeton University Press eBooks · doi:10.1515/9781400874651 · Cited by 1,973 · see citing works
Numerical Recipes in C: The Art of Scientific Computing
Seiler, M. C., & Seiler, F. A. (1989) · Risk Analysis · doi:10.1111/j.1539-6924.1989.tb01007.x · Cited by 1,356 · see citing works
Stereo by Intra- and Inter-Scanline Search Using Dynamic Programming
Ohta, Y., & Kanade, T. (1985) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.1985.4767639 · Cited by 940 · see citing works
Regularization of Inverse Visual Problems Involving Discontinuities
Terzopoulos, D. (1986) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.1986.4767807 · Cited by 768 · see citing works
Methods of mathematical physics, Vol. 2, Partial differential equations
Courant, R., & Hilbert, D. (1989) · Wiley eBooks · doi:10.1002/9783527617234 · Cited by 738 · see citing works
Ill-posed problems in early vision
Bertero, M., Poggio, T., & Torre, V. (1988) · Proceedings of the IEEE · doi:10.1109/5.5962 · Cited by 724 · see citing works
Eslami, M. (1978) · Journal of the Franklin Institute · doi:10.1016/0016-0032(78)90124-2 · Cited by 707 · see citing works
Probabilistic Solution of Ill-Posed Problems in Computational Vision
Marroquin, J. L., Mitter, S. K., & Poggio, T. (1987) · Journal of the American Statistical Association · doi:10.1080/01621459.1987.10478393 · Cited by 701 · see citing works
Understanding image intensities
Horn, B. K. P. (1977) · Artificial Intelligence · doi:10.1016/0004-3702(77)90020-0 · Cited by 694 · see citing works
Methods of Applied Mathematics
Hildebrand, F. B., & Park, D. S. (1953) · American Journal of Physics · doi:10.1119/1.1933516 · Cited by 688 · see citing works
Sage, A. P., White, C., & Siouris, G. M. (1979) · IEEE Transactions on Systems Man and Cybernetics · doi:10.1109/tsmc.1979.4310157 · Cited by 625 · see citing works
The computation of visible-surface representations
Terzopoulos, D. (1988) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/34.3908 · Cited by 450 · see citing works
Probabilistic Solution of Ill-Posed Problems in Computational Vision
Marroquin, J. L., Mitter, S. K., & Poggio, T. (1987) · Journal of the American Statistical Association · doi:10.2307/2289127 · Cited by 367 · see citing works
Methods of Applied Mathematics
Roberts, R. C., & Hildebrand, F. B. (1966) · Mathematics of Computation · doi:10.2307/2004321 · Cited by 349 · see citing works
Dynamic programming and the calculus of variations
Dreyfus, S. E. (1960) · Journal of Mathematical Analysis and Applications · doi:10.1016/0022-247x(60)90024-x · Cited by 296 · see citing works
Sage, A. P., & White, C. C. (1977) · Defense Technical Information Center (DTIC) · Cited by 271 · see citing works
4 Dynamic Programming and the Calculus of Variations
(1964) · Mathematics in Science and Engineering/Mathematics in science and engineering · doi:10.1016/s0076-5392(08)63116-1 · Cited by 264 · see citing works
The art and theory of dynamic programming
Rota, G. (1978) · Advances in Mathematics · doi:10.1016/0001-8708(78)90080-4 · Cited by 243 · see citing works
Amini, A. A., Tehrani, S., & Weymouth, T. E. (2005) · International Conference on Computer Vision · doi:10.1109/ccv.1988.589976 · Cited by 204 · see citing works
Self-citationIll-Posed Problems and Regularization Analysis in Early Vision
Poggio, T., & Torre, V. (1984) · Defense Technical Information Center (DTIC) · Cited by 140 · see citing works
The Art and Theory of Dynamic Programming
Unwin, A. R., Dreyfus, S. E., & Law, A. M. (1979) · Journal of the Operational Research Society · doi:10.2307/3009654 · Cited by 139 · see citing works
Horn, B. K. P. (1975) · Defense Technical Information Center (DTIC) · Cited by 105 · see citing works
Determining The Optimal Weights In Multiple Objective Function Optimization
Gennert, M. A., & Yuille, A. (2005) · International Conference on Computer Vision · doi:10.1109/ccv.1988.589974 · Cited by 82 · see citing works
Energy functions for early vision and analog networks
Yuille, A. (1989) · Biological Cybernetics · doi:10.1007/bf00204595 · Cited by 78 · see citing works
Optimal estimation of contour properties by cross-validated regularization
Shahraray, B., & Anderson, D. J. (1989) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/34.24794 · Cited by 76 · see citing works
Wahba, G., & Wold, S. (1975) · Communications in Statistics · doi:10.1080/03610927508827233 · Cited by 72 · see citing works
Visual Integration and Detection of Discontinuities: The Key Role of Intensity Edges
Gamble, E. B., & Poggio, T. (1987) · DSpace@MIT (Massachusetts Institute of Technology) · Cited by 70 · see citing works
Recognition of kidney glomerulus by dynamic programming matching method
YAMADA, H., Merritt, C., & Kasvand, T. (1988) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/34.6784 · Cited by 31 · see citing works
Amini, A. A., Weymouth, T. E., & Anderson, D. J. (1990) · Deep Blue (University of Michigan) · Cited by 12 · see citing works
Self-citationEdge detection with image enhancement via dynamic programming
Furst, M. A., & Caines, P. E. (1986) · Computer Vision Graphics and Image Processing · doi:10.1016/0734-189x(86)90176-3 · Cited by 9 · see citing works
Pyramid Implementation Of Optimal Step Conjugate Search Algorithms For Some Computer Vision Problems
Simchony, T., Chellappa, R., & Lichtenstein, Z. (2005) · International Conference on Computer Vision · doi:10.1109/ccv.1988.590038 · Cited by 5 · see citing works
The Main Results of Optimal Control Theory Made Simple
Dreyfus, S. E. (1972) · Elsevier eBooks · doi:10.1016/b978-1-4832-2868-6.50017-5 · Cited by 3 · see citing works
Motha (1980) · doi:10.1175/1520-0493(1980)108
Flagged first, then by citations
Cited by
Sorted by citations
Fast approximate energy minimization via graph cuts
Boykov, Y., Veksler, O., & Zabih, R. (2001) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/34.969114 · Cited by 6,988 · see citing works
AI in Medical Imaging Informatics: Current Challenges and Future Directions
Panayides, A. S., Amini, A., Filipovic, N. D., Sharma, A., Tsaftaris, S. A., Young, A., Foran, D., Do, N., Golemati, S., Kurc, T., et al. (2020) · IEEE Journal of Biomedical and Health Informatics · doi:10.1109/jbhi.2020.2991043 · Cited by 713 · see citing works
Self-citation
- Authors
- Amini, A. A., Weymouth, T. E., & Jain, R. C.
- Affiliations
- University of Michigan (US)
- Venue
- IEEE Transactions on Pattern Analysis and Machine Intelligence
- Published
- 1990
- Volume
- 12
- Issue
- 9
- Pages
- 855-867
- ISSN
- 0162-8828 (ISSN-L)
- OpenAlex
- W2131910503
- Cited by
- 1,008
- References
- 45
- Citations by year
- 2026: 2 · 2025: 1 · 2024: 2 · 2023: 3 · 2022: 4 · 2021: 10 · 2020: 9 · 2019: 9 · 2018: 17 · 2017: 24 · 2016: 21 · 2015: 26 · 2014: 35 · 2013: 33 · 2012: 23
- FWCI
- 9.53
- Type
- journal article
- Language
- en
- Open access
- closed
- Locations
- IEEE Transactions on Pattern Analysis and Machine Intelligence (publishedVersion)
- Topics
- Physical Sciences › Computer Science › Computer Vision and Pattern Recognition › Medical Image Segmentation Techniques
- Physical Sciences › Computer Science › Computer Vision and Pattern Recognition › Advanced Vision and Imaging
- Physical Sciences › Computer Science › Computer Vision and Pattern Recognition › Image and Signal Denoising Methods
- Keywords
- dynamic programming, variational problems, snakes, energy minimization, global optimality, hard constraints, multi-stage decision making, parallel computing, image segmentation
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review