Using dynamic programming for solving variational problems in vision
IEEE Transactions on Pattern Analysis and Machine IntelligencePublished 1 January 1990
Amir A. Amini, Terry E. Weymouth, Ramesh Jain
Citations1,003
SJR quartileQ1
SJR score3.91
SNIP5.99
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
The optimization problem is set up as a discrete multistage decision process and is solved by a time-delayed discrete dynamic programming algorithm, and a parallel procedure for decreasing computational costs is discussed.
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.>
Keywords
Computer ScienceEngineering
IEEE Transactions on Pattern Analysis and Machine IntelligenceA Computational Approach to Edge Detection
29,107 Citations1986John Canny
There is a natural uncertainty principle between detection and localization performance, which are the two main goals, and with this principle a single operator shape is derived which is optimal at any scale.
IEEE Transactions on Pattern Analysis and Machine IntelligenceStochastic Relaxation, Gibbs Distributions, and the Bayesian Restoration of Images
17,980 Citations1984Stuart Geman, Donald Geman
The analogy between images and statistical mechanics systems is made and the analogous operation under the posterior distribution yields the maximum a posteriori (MAP) estimate of the image given the degraded observations, creating a highly parallel ``relaxation'' algorithm for MAP estimation.
International Journal of Computer VisionSnakes: Active contour models
16,951 Citations1988Michael Kass, Andrew Witkin +1 more
This work uses snakes for interactive interpretation, in which user-imposed constraint forces guide the snake near features of interest, and uses scale-space continuation to enlarge the capture region surrounding a feature.
ScienceDynamic Programming
13,088 Citations1966Richard Bellman
The more the authors study the information processing aspects of the mind, the more perplexed and impressed they become, and it will be a very long time before they understand these processes sufficiently to reproduce them.
Artificial IntelligenceDetermining optical flow
9,940 Citations1981Berthold K. P. Horn, Brian G. Schunck
Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE<title>Determining Optical Flow</title>
7,496 Citations1981Berthold K. P. Horn, Brian G. Schunck
An iterative implementation is shown which successfully computes the optical flow for a number of synthetic image sequences and is robust in that it can handle image sequences that are quantized rather coarsely in space and time.
Robot Vision
3,632 Citations1986Berthold K. P. Horn
This book presents a coherent approach to the fast-moving field of computer vision, using a consistent notation based on a detailed understanding of the image formation process, and will provide a useful and current reference for professionals working in the fields of machine vision, image processing, and pattern recognition.
Journal of the Royal Statistical Society Series A (General)Adaptive Control Processes: A Guided Tour.
2,218 Citations1962E. S. Page, Richard Bellman
Princeton University Press eBooksApplied Dynamic Programming
1,956 Citations1962Richard Bellman, Stuart E. Dreyfus
IEEE Transactions on Pattern Analysis and Machine IntelligenceStereo by Intra- and Inter-Scanline Search Using Dynamic Programming
930 Citations1985Yuichi Ohta, Takeo Kanade
This paper presents a stereo matching algorithm using the dynamic programming technique that uses edge-delimited intervals as elements to be matched, and employs the above mentioned two searches: one is inter-scanline search for possible correspondences of connected edges in right and left images and the other is intra-scanlines search for correspondence of edge-Delimited interval on each scanline pair.
IEEE Transactions on Pattern Analysis and Machine IntelligenceRegularization of Inverse Visual Problems Involving Discontinuities
763 Citations1986Demetri Terzopoulos
This paper proposes a general class of controlled-continuity stabilizers which provide the necessary control over smoothness in visual reconstruction problems that involve both continuous regions and discontinuities, for which global smoothness constraints fail.
Proceedings of the IEEEIll-posed problems in early vision
729 Citations1988M. Bertero, Tomaso Poggio +1 more
Journal of the American Statistical AssociationProbabilistic Solution of Ill-Posed Problems in Computational Vision
698 Citations1987José L. Marroquín, Sanjoy K. Mitter +1 more
This work derives efficient algorithms and describes parallel implementations on digital parallel SIMD architectures, as well as a new class of parallel hybrid computers that mix digital with analog components.
Artificial IntelligenceUnderstanding image intensities
693 Citations1977Berthold K. P. Horn
The gradient space, popularized by Huffman and Mackworth in a slightly different context, is a helpful tool in the development of new methods for exploiting three-dimensional shape information in image intensities.
American Journal of PhysicsMethods of Applied Mathematics
689 Citations1953F. B. Hildebrand, David S. Park
IEEE Transactions on Systems Man and CyberneticsOptimum Systems Control
625 Citations1979A.P. Sage, Clive White +1 more
Monthly Weather ReviewSome New Mathematical Methods for Variational Objective Analysis Using Splines and Cross Validation
565 Citations1980Grace Wahba, James Wendelberger
IEEE Transactions on Pattern Analysis and Machine IntelligenceThe computation of visible-surface representations
451 Citations1988Demetri Terzopoulos
A well-posed variational formulation results from the use of a controlled-continuity surface model, and Finite-element shape primitives yield a local discretization of the variational principle, which is an efficient algorithm for visible-surface reconstruction.
Journal of the American Statistical AssociationProbabilistic Solution of Ill-Posed Problems in Computational Vision
367 Citations1987José L. Marroquín, Sanjoy K. Mitter +1 more
Journal of Mathematical Analysis and ApplicationsDynamic programming and the calculus of variations
291 Citations1960Stuart E. Dreyfus
Munich Personal RePEc Archive (Ludwig Maximilian University of Munich)Optimum systems control
271 Citations1977Andrew P. Sage, Chelsea C. White
Using Dynamic Programming For Minimizing The Energy Of Active Contours In The Presence Of Hard Constraints
205 Citations2005Amir A. Amini, S. Tehrani +1 more
The optimization problem is set up as a discrete multi-stage decision process and is solved by a “time-delayed” discrete dynamic programming algorithm, which leads to a stable behavior for the active contours over iterations, in addition to allowing for hard constraints to be enforced on the behavior of the solution.
Munich Personal RePEc Archive (Ludwig Maximilian University of Munich)Ill-Posed Problems and Regularization Analysis in Early Vision
140 Citations1984Tomaso Poggio, Vincent Torre
DSpace@MIT (Massachusetts Institute of Technology)Image Intensity Understanding
104 Citations1975Berthold K. P. Horn
The gradient-space, popularized by Huffman and Mackworth i s a h e l p f u l t o o l i n t h i s regard, is used to segment an image and to process three-dimensional aspects of the image.
Determining The Optimal Weights In Multiple Objective Function Optimization
80 Citations2005Michael A. Gennert, Alan Yuille
The Min-Max Principle, which avoids the problems of extremely low or high weights, is introduced and derived relating the optimal weights, objective function values, and total cost.
Biological CyberneticsEnergy functions for early vision and analog networks
79 Citations1989Alan Yuille
This paper attempts to model the modules of early vision in terms of minimizing energy functions, in particular energy functions allowing discontinuities in the solution, and examines the success of using Hopfield-style analog networks for solving such problems.
IEEE Transactions on Pattern Analysis and Machine IntelligenceOptimal estimation of contour properties by cross-validated regularization
76 Citations1989Behzad Shahraray, David J. Anderson
Experimental results are presented which demonstrate the robustness of the method applied to the estimation of curvature of quantized contours under variable scale, rotation, and partial occlusion and suggest the application of generalized cross-validation to other computer-vision algorithms involving regularization.
Communications in StatisticsPeriodic splines for spectral density estimation: the use of cross validation for determining the degree of smoothing
71 Citations1975Grace Wahba, Svante Wold
The cross validation mean square error technique is shown to be appropriate for choosing the smoothing or “bandwidth” parameter, in estimating the log spectral density with periodic splines.
DSpace@MIT (Massachusetts Institute of Technology)Visual Integration and Detection of Discontinuities: The Key Role of Intensity Edges
70 Citations1987E.B. Gamble, Tomaso Poggio
A scheme to integrate intensity edges with stereo depth and motion field information and results from a Connection Machine algorithm are shown, showing the use of intensity edges to integrate other visual cues and to help discover discontinuities emerges as a general and powerful principle.
IEEE Transactions on Pattern Analysis and Machine IntelligenceRecognition of kidney glomerulus by dynamic programming matching method
31 Citations1988Hiroyuki YAMADA, C. Merritt +1 more
Dynamic programming was applied to locate the glomeruli in microscopic images of kidney tissue section by determining the best match of the model according to a so-called optimum criterion in which all possible shapes were evaluated at all possible positions in the input image.
Deep Blue (University of Michigan)Using dynamic programming for solving variational problems in vision: applications involving deformable models for contours and surfaces.
12 Citations1990Amir A. Amini, Terry E. Weymouth +1 more
Computer Vision Graphics and Image ProcessingEdge detection with image enhancement via dynamic programming
9 Citations1986Miriam Furst, Peter E. Caines
A class of characteristic functions is proposed from which the best “edge function” is chosen for each window by the dynamic programming technique, and a thresholded gradient operator technique is used for edge detection.
Elsevier eBooksThe Main Results of Optimal Control Theory Made Simple
3 Citations1972Stuart E. Dreyfus