Distance Transforms of Sampled Functions

by Pedro F. Felzenszwalb and Daniel P. Huttenlocher

Theory of Computing, Volume 8(19), pp. 415-428, 2012

Bibliography with links to cited articles

[1]   Alok Aggarwal, Maria M. Klawe, Shlomo Moran, Peter Shor, and Robert Wilber: Geometric applications of a matrix-searching algorithm. Algorithmica, 2:195–208, 1987. Preliminary version in SCG’86. [doi:10.1007/BF01840359]

[2]   Richard Bellman and William Karush: Functional equations in the theory of dynamic programming XII: An application of the maximum transform. J. Mathematical Analysis and Applications, 6(1):155–157, 1963. [doi:10.1016/0022-247X(63)90099-4]

[3]   Dimitri Bertsekas: Dynamic Programming and Optimal Control. Athena Scientific, 2001.

[4]   Harry Blum: Biological shape and visual science (part I). J. Theoretical Biology, 38(2):205–287, 1973. [doi:10.1016/0022-5193(73)90175-6]

[5]   Gunilla Borgefors: Distance transformations in digital images. Computer Vision, Graphics, and Image Processing, 34(3):344–371, 1986. [doi:10.1016/S0734-189X(86)80047-0]

[6]   Gunilla Borgefors: Hierarchical chamfer matching: A parametric edge matching algorithm. IEEE Trans. Pattern Anal. Mach. Intell., 10(6):849–865, 1988. [doi:10.1109/34.9107]

[7]   Heinz Breu, Joseph Gil, David Kirkpatrick, and Michael Werman: Linear time Euclidean distance algorithms. IEEE Trans. Pattern Anal. Mach. Intell., 17(5):529–533, 1995. [doi:10.1109/34.391389]

[8]   Olivier Devillers and Mordecai J. Golin: Incremental algorithms for finding the convex hulls of circles and the lower envelopes of parabolas. Information Processing Letters, 56(3):157–164, 1995. Preliminary version in CCCG’94. [doi:10.1016/0020-0190(95)00132-V]

[9]   David A. Eppstein: Efficient algorithms for sequence analysis with concave and convex gap costs. PhD thesis, Columbia University, 1989.

[10]   Pedro F. Felzenszwalb and Daniel P. Huttenlocher: Distance transforms of sampled functions. Technical Report 2004-1963, Cornell University, 2004. eCommons@Cornell.

[11]   Pedro F. Felzenszwalb and Daniel P. Huttenlocher: Pictorial structures for object recognition. Internat. J. Computer Vision, 61(1):55–79, 2005. Preliminary version in CVPR’00. [doi:10.1023/B:VISI.0000042934.15159.49]

[12]   Pedro F. Felzenszwalb and Daniel P. Huttenlocher: Efficient belief propagation for early vision. Internat J. Computer Vision, 70(1):41–54, 2006. Preliminary version in CVPR’04. [doi:10.1007/s11263-006-7899-4]

[13]   Pedro F. Felzenszwalb, Daniel P. Huttenlocher, and Jon M. Kleinberg: Fast algorithms for large-state-space HMMs with applications to web usage analysis. In Advances in Neural Information Processing Systems 16 (NIPS’03), 2003. NIPS.

[14]   Joseph Gil and Michael Werman: Computing 2-D min, median, and max filters. IEEE Trans. Pattern Anal. Mach. Intell., 15(5):504–507, 1993. [doi:10.1109/34.211471]

[15]   Alex Hagen-Zanker and Harry Timmermans: A metric of compactness of urban change illustrated to 22 European countries. In Proc. 11th Conf. Association of Geographic Information Laboratories for Europe (AGILE’08), pp. 181–200. Springer, 2008. [doi:10.1007/978-3-540-78946-8_10]

[16]   Daniel P. Huttenlocher, Gregory A. Klanderman, and William Rucklidge: Comparing images using the Hausdorff distance. IEEE Trans. Pattern Anal. Mach. Intell., 15(9):850–863, 1993. [doi:10.1109/34.232073]

[17]   Calvin R. Maurer Jr., Rensheng Qi, and Vijay Raghavan: A linear time algorithm for computing exact Euclidean distance transforms of binary images in arbitrary dimensions. IEEE Trans. Pattern Anal. Mach. Intell., 25(2):265–270, 2003. Preliminary version in IPMI’01. [doi:10.1109/TPAMI.2003.1177156]

[18]   Alexander V. Karzanov: Quick algorithm for determining the distances from the points of the given subset of an integer lattice to the points of its complement. Cybernetics and System Analysis, pp. 177–181, 1992. Translation from the Russian.

[19]   Mike Klaas, Dustin Lang, and Nando de Freitas: Fast maximum a posteriori inference in Monte Carlo state spaces. In Proc. 10th Internat. Workshop on Artificial Intelligence and Statistics, 2005. (AISTATS’05).

[20]   Maria M. Klawe and Daniel J. Kleitman: An almost linear time algorithm for generalized matrix searching. SIAM J. Discrete Math., 3(1):81–97, 1990. [doi:10.1137/0403009]

[21]   Petros Maragos: Differential morphology. In Mitra and Sicuranza, editors, Nonlinear Image Processing, pp. 289–329. Academic Press, 2001. [doi:10.1016/B978-012500451-0/50010-2]

[22]   George Papandreou and Petros Maragos: Multigrid geometric active contour models. IEEE Trans. Image Processing, 16(1):229–240, 2007. [doi:10.1109/TIP.2006.884952]

[23]   Judea Pearl: Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference. Morgan Kaufmann, 1988.

[24]   Lawrence R. Rabiner: A tutorial on hidden Markov models and selected applications in speech recognition. Proc. IEEE, 77(2):257–289, 1989. [doi:10.1109/5.18626]

[25]   Nathan Ratliff, Matt Zucker, J. Andrew Bagnell, and Siddhartha Srinivasa: CHOMP: Gradient optimization techniques for efficient motion planning. In 2009 IEEE Internat. Conf. on Robotics and Automation (ICRA’09), pp. 489–494. IEEE Comp. Soc. Press, 2009. [doi:10.1109/ROBOT.2009.5152817]

[26]   Christophe Restif: Towards safer, faster prenatal genetic tests: Novel unsupervised, automatic and robust methods of segmentation of nuclei and probes. In European Conf. on Computer Vision, number 3954 in Lecture Notes in Computer Science, pp. 437–450. Springer, 2006. [doi:10.1007/11744085_34]

[27]   Azriel Rosenfeld and John L. Pfaltz: Sequential operations in digital picture processing. J. ACM, 13(4):471–494, 1966. [doi:10.1145/321356.321357]

[28]   Denis Rutovitz: Data structures for operations on digital images. In Cheng et al., editor, Pictorial Pattern Recognition, pp. 105–133. Thomson Book, WA, 1968.

[29]   Jamie Shotton, Andrew Blake, and Roberto Cipolla: Contour-based learning for object detection. In 10th IEEE Internat. Conf. on Computer Vision (ICCV’05), pp. 503–510. IEEE Comp. Soc. Press, 2005. [doi:10.1109/ICCV.2005.63]

[30]   Tsubasa Yoshida, Kris M. Kitani, Hideki Koike, Serge Belongie, and Kevin Schlei: EdgeSonic: image feature sonification for the visually impaired. In Proc. 2nd Augmented Human Internat. Conf., pp. 11:1–11:4. ACM Press, 2011. [doi:10.1145/1959826.1959837]