| | This Article | |
| |
| |
| | Share | |
| |
| |
| | Bibliographic References | |
| |
| |
| | Add to: | |
| |
 Digg
 Furl
 Spurl
 Blink
 Simpy
 Google
 Del.icio.us
 Y!MyWeb
| |
| | Search | |
| |
| |
| | |
Multiple Paths Extraction in Images Using a Constrained Expanded Trellis
December 2005 (vol. 27 no. 12)
pp. 1923-1933
Single shortest path extraction algorithms have been used in a number of areas such as network flow and image analysis. In image analysis, shortest path techniques can be used for object boundary detection, crack detection, or stereo disparity estimation. Sometimes one needs to find multiple paths as opposed to a single path in a network or an image where the paths must satisfy certain constraints. In this paper, we propose a new algorithm to extract multiple paths simultaneously within an image using a constrained expanded trellis (CET) for feature extraction and object segmentation. We also give a number of application examples for our multiple paths extraction algorithm.
[1] 1923 C. Sun and S. Pallottino, “Circular Shortest Path on Regular Grids,” Proc. Asian Conf. Computer Vision, pp. 852-857, Jan. 2002.[2] M. Barzohar and D.B. Cooper, “Automatic Finding of Main Roads in Aerial Images by Using Geometric-Stochastic Models and Estimation,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 18, no. 7, pp. 707-721, July 1996.[3] S. Lloyd, “Stereo Matching Using Intra- and Inter-Row Dynamic Programming,” Pattern Recognition Letters, vol. 4, pp. 273-277, Sept. 1986.[4] Y. Ohta and T. Kanade, “Stereo by Intra- and Inter-Scanline Search Using Dynamic Programming,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 7, no. 2, pp. 139-154, Mar. 1985.[5] C. Sun, “Fast Stereo Matching Using Rectangular Subregioning and 3D Maximum-Surface Techniques,” Int'l J. Computer Vision, vol. 47, nos. 1/2/3, pp. 99-117, Apr.-June 2002.[6] C. Sun, “Fast Optical Flow Using 3D Shortest Path Techniques,” Image and Vision Computing, vol. 20, no. 13/14, pp. 981-991, Dec. 2002.[7] C. Sun and S. Pallottino, “Circular Shortest Path in Images,” Pattern Recognition, vol. 36, no. 3, pp. 711-721, Mar. 2003.[8] R.K. Ahuja, T.L. Magnanti, and J.B. Orlin, Network Flows: Theory, Algorithms, and Applications. Englewood Cliffs, N.J.: Prentice Hall, 1993.[9] Q.-P. Gu and S. Peng, “An Efficient Algorithm for the $k\hbox{-}{\rm{Pairwise}}$ Disjoint Paths Problem in Hypercubes,” J. Parallel and Distributed Computing, vol. 60, no. 6, pp. 764-774, June 2000.[10] R. Perry, A. Vaddiraju, and K. Buckley, “Trellis Structure Approach to Multitarget Tracking,” Proc. Sixth Ann. Workshop Adaptive Sensor Array Processing, Mar. 1999.[11] W.-T. Chan and F.Y. Chin, “Efficient Algorithms for Finding the Maximum Number of Disjoint Paths in Grids,” J. Algorithms, vol. 34, no. 2, pp. 337-369, Feb. 2000.[12] S.-W. Lee and C.-S. Wu, “A $K\hbox{-}{\rm{Best}}$ Paths Algorithm for Highly Reliable Communication Networks,” IEICE Trans. Comm., vol. E82-B, no. 4, pp. 586-590, Apr. 1999.[13] D.A. Castañon, “Efficient Algorithms for Finding the $K$ Best Paths through a Trellis,” IEEE Trans. Aerospace and Electronic Systems, vol. 26, no. 2, pp. 405-410, Mar. 1990.[14] J.K. Wolf, A.M. Viterbi, and G.S. Dixon, “Finding the Best Set of $K$ Paths through a Trellis with Application to Multitarget Tracking,” IEEE Trans. Aerospace and Electronic Systems, vol. 25, no. 2, pp. 287-296, Mar. 1989.[15] S.D. Nikolopoulos and G. Samaras, “Sub-Optimal Solutions to Track Detection Problem Using Graph Theoretic Concepts,” J. Systems Architecture vol. 42, no. 9/10, pp. 743-760, Feb. 1997.[16] M. Buckley and J. Yang, “Regularised Shortest-Path Extraction,” Pattern Recognition Letters, vol. 18, no. 7, pp. 621-629, July 1997.[17] P. Bamford and B. Lovell, “Unsupervised Cell Nucleus Segmentation with Active Contours,” Signal Processing, special issue on deformable models and techniques for image and signal processing, vol. 71, no. 2, pp. 203-213, Dec. 1998.[18] L.D. Cohen and R. Kimmel, “Global Minimum for Active Contour Models: A Minimal Path Approach,” Int'l J. Computer Vision, vol. 24, no. 1, pp. 57-78, Aug. 1997.[19] V. Caselles, R. Kimmel, and G. Sapiro, “Geodesic Active Contours,” Int'l J. Computer Vision, vol. 22, no. 1, pp. 61-79, Feb./Mar. 1997.[20] C. Leung, B. Appleton, and C. Sun, “Fast Stereo Matching by Iterated Dynamic Programming and Quadtree Subregioning,” Proc. British Machine Vision Conf., A. Hoppe, S. Barman, and T. Ellis, eds., vol. 1, pp. 97-106, Sept. 2004.[21] Y. Boykov and V. Kolmogorov, “Computing Geodesics and Minimal Surfaces via Graph Cuts,” Proc. Int'l Conf. Computer Vision, vol. I, pp. 26-33, Oct. 2003.[22] B. Appleton and C. Sun, “Circular Shortest Paths by Branch and Bound,” Pattern Recognition, vol. 36, no. 11, pp. 2513-2520, Nov. 2003.[23] B. Appleton and H. Talbot, “Globally Optimal Geodesic Active Contours,” J. Math. Imaging and Vision, vol. 23, no. 1, pp. 67-86, July 2005.[24] R. Sedgewick, Algorithms in C++, third ed., nos. 1-4, Addison-Wesley, 1998.[25] M.B. Stegmann, R. Fisker, and B.K. Ersboll, “Extending and Applying Active Appearance Models for Automated, High Precision Segmentation in Different Image Modalities,” Proc. 12th Scandinavian Conf. Image Analysis, vol. 1, pp. 90-97, June 2001.
Index Terms:
Index Terms- Multiple paths extraction, constrained expanded trellis, feature extraction, object segmentation.
Citation:
Changming Sun, Ben Appleton, "Multiple Paths Extraction in Images Using a Constrained Expanded Trellis," IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 27, no. 12, pp. 1923-1933, Dec. 2005, doi:10.1109/TPAMI.2005.247
