Closest Paths in Graph Drawings under an Elastic Metric

Mateusz Baran

doi:10.2478/amcs-2018-0029

Abstract

This work extends the dynamic programming approach to calculation of an elastic metric between two curves to finding paths in pairs of graph drawings that are closest under this metric. The new algorithm effectively solves this problem when all paths between two given nodes in one of these graphs have the same length. It is then applied to the problem of pattern recognition constrained by a superpixel segmentation. Segmentations of test images, obtained without statistical modeling given two shape endpoints, have good accuracy.

References

Bernal, J., Dŏgan, G. and Hagwood, C.R. (2016). Fast dynamic programming for elastic registration of curves, 2016 IEEE Conference on Computer Vision and Pattern Recognition Workshops (CVPRW), Las Vegas, NV, USA, pp. 1066-1073, DOI: 10.1109/CVPRW.2016.137.10.1109/CVPRW.2016.137
Open DOI Search in Google Scholar Back to article
Cootes, T.F., Edwards, G.J. and Taylor, C.J. (2001). Active appearance models, IEEE Transactions on Pattern Analysis and Machine Intelligence 23(6): 681-685, DOI: 10.1109/34.927467.10.1109/34.927467
Open DOI Search in Google Scholar Back to article
Cootes, T.F., Taylor, C.J., Cooper, D.H. and Graham, J. (1995). Active shape models-Their training and application, Computer Vision and Image Understanding 61(1): 38-59, DOI: 10.1006/cviu.1995.1004.10.1006/cviu.1995.1004
Open DOI Search in Google Scholar Back to article
Dice, L.R. (1945). Measures of the amount of ecologic association between species, Ecology 26(3): 297-302, DOI: 10.2307/1932409.10.2307/1932409
Open DOI Search in Google Scholar Back to article
Dijkstra, E.W. (1959). A note on two problems in connexion with graphs, Numerische Mathematik 1(1): 269-271, DOI: 10.1007/BF01386390.10.1007/BF01386390
Open DOI Search in Google Scholar Back to article
Dŏgan, G., Bernal, J. and Hagwood, C.R. (2015). A fast algorithm for elastic shape distances between closed planar curves, Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, Boston, MA, USA, pp. 4222-4230, DOI: 10.1109/CVPR.2015.7299050.10.1109/CVPR.2015.7299050
Open DOI Search in Google Scholar Back to article
Dryden, I.L. and Mardia, K.V. (1998). Statistical Shape Analysis, 1st Edn., Wiley, Chichester.
Search in Google Scholar Back to article
Fáry, I. (1948). On straight line representation of planar graphs, Acta Scientiarum Mathematicarum (Szeged) 11(4-4): 229-233.
Search in Google Scholar Back to article
Fredman, M.L. and Tarjan, R.E. (1987). Fibonacci heaps and their uses in improved network optimization algorithms, Journal of the ACM 34(3): 596-615, DOI: 10.1145/28869.28874.10.1145/28869.28874
Open DOI Search in Google Scholar Back to article
Freeman, H. (1961). On the encoding of arbitrary geometric configurations, IRE Transactions on Electronic Computers EC-10(2): 260-268, DOI: 10.1109/TEC.1961.5219197.10.1109/TEC.1961.5219197
Open DOI Search in Google Scholar Back to article
Joshi, S.H., Klassen, E., Srivastava, A. and Jermyn, I. (2007). A novel representation for Riemannian analysis of elastic curves in Rn, IEEE Computer Society Conference on Computer Vision and Pattern Recognition, Minneapolis, MN, USA, pp. 1-7, DOI: 10.1109/CVPR.2007.383185.10.1109/CVPR.2007.383185303532221311729
Open DOI Search in Google Scholar Back to article
Kowal, M. and Filipczuk, P. (2014). Nuclei segmentation for computer-aided diagnosis of breast cancer, International Journal of Applied Mathematics and Computer Science 24(1): 19-31, DOI: 10.2478/amcs-2014-0002.10.2478/amcs-2014-0002
Open DOI Search in Google Scholar Back to article
Mehrotra, R. and Gary, J.E. (1995). Similar-shape retrieval in shape data management, Computer 28(9): 57-62, DOI: 10.1109/2.410154.10.1109/2.410154
Open DOI Search in Google Scholar Back to article
Meyer, F. and Beucher, S. (1990). Morphological segmentation, Journal of Visual Communication and Image Representation 1(1): 21-46, DOI: 10.1016/1047-3203(90)90014-M.10.1016/1047-3203(90)90014-
Open DOI Search in Google Scholar Back to article
Michor, P.W. and Mumford, D.B. (2006). Riemannian geometries on spaces of plane curves, Journal of the European Mathematical Society 8(1): 1-48, DOI: 10.4171/JEMS/37.10.4171/JEMS/37
Open DOI Search in Google Scholar Back to article
Mio, W., Srivastava, A. and Joshi, S. (2007). On shape of plane elastic curves, International Journal of Computer Vision 73(3): 307-324, DOI: 10.1007/s11263-006-9968-0.10.1007/s11263-006-9968-0
Open DOI Search in Google Scholar Back to article
Mori, G., Ren, X., Efros, A.A. and Malik, J. (2004). Recovering human body configurations: Combining segmentation and recognition, Proceedings of the 2004 IEEE Computer Society Conference on Computer Vision and Pattern Recognition, CVPR 2004, Washington, DC, USA, Vol. 2, pp. II-326-II-333, DOI: 10.1109/CVPR.2004.1315182.10.1109/CVPR.2004.1315182
Open DOI Search in Google Scholar Back to article
Neubert, P. and Protzel, P. (2014). Compact watershed and preemptive SLIC: On improving trade-offs of superpixel segmentation algorithms, 22nd International Conference on Pattern Recognition (ICPR), Stockholm, Sweden, pp. 996-1001, DOI: 10.1109/ICPR.2014.181.10.1109/ICPR.2014.181
Open DOI Search in Google Scholar Back to article
Perona, P. and Malik, J. (1990). Scale-space and edge detection using anisotropic diffusion, IEEE Transactions on Pattern Analysis and Machine Intelligence 12(7): 629-639, DOI: 10.1109/34.56205.10.1109/34.56205
Open DOI Search in Google Scholar Back to article
Sobrinho, J.a.L. (2003). Network routing with path vector protocols: Theory and applications, Proceedings of the 2003 Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications, SIGCOMM’03, Karlsruhe, Germany, pp. 49-60, DOI: 10.1145/863955.863963.10.1145/863955.863963
Search in Google Scholar Back to article
Sobrinho, J.L. (2002). Algebra and algorithms for QoS path computation and hop-by-hop routing in the Internet, IEEE/ACM Transactions on Networking 10(4): 541-550, DOI: 10.1109/TNET.2002.801397.10.1109/TNET.2002.801397
Open DOI Search in Google Scholar Back to article
Sobrinho, J.L. (2005). An algebraic theory of dynamic network routing, IEEE/ACM Transactions on Networking 13(5): 1160-1173, DOI: 10.1109/TNET.2005.857111.10.1109/TNET.2005.857111
Open DOI Search in Google Scholar Back to article
Srivastava, A., Klassen, E., Joshi, S.H. and Jermyn, I.H. (2011). Shape analysis of elastic curves in Euclidean spaces, IEEE Transactions on Pattern Analysis and Machine Intelligence 33(7): 1415-1428, DOI: 10.1109/TPAMI.2010.184.10.1109/TPAMI.2010.18420921581
Open DOI Search in Google Scholar Back to article
Srivastava, A. and Klassen, E.P. (2016). Functional and Shape Data Analysis, Springer, New York, NY.10.1007/978-1-4939-4020-2
Search in Google Scholar Back to article
Srivastava, A., Turaga, P. and Kurtek, S. (2012). On advances in differential-geometric approaches for 2D and 3D shape analyses and activity recognition, Image and Vision Computing 30(67): 398-416, DOI: 10.1016/j.imavis.2012.03.006.10.1016/j.imavis.2012.03.006
Open DOI Search in Google Scholar Back to article
Sundaramoorthi, G., Mennucci, A., Soatto, S. and Yezzi, A. (2011). A new geometric metric in the space of curves, and applications to tracking deforming objects by prediction and filtering, SIAM Journal on Imaging Sciences 4(1): 109-145, DOI: 10.1137/090781139.10.1137/090781139
Open DOI Search in Google Scholar Back to article
Tabor, Z. (2009). Statistical estimation of the dynamics of watershed dams, International Journal of Applied Mathematics and Computer Science 19(2): 349-360, DOI: 10.2478/v10006-009-0030-6.10.2478/v10006-009-0030-6
Open DOI Search in Google Scholar Back to article
Tagougui, N., Kherallah, M. and Alimi, A.M. (2013). Online Arabic handwriting recognition: A survey, International Journal on Document Analysis and Recognition 16(3): 209-226, DOI: 10.1007/s10032-012-0186-8.10.1007/s10032-012-0186-8
Open DOI Search in Google Scholar Back to article
Turaga, P.K. and Srivastava, A. (2016). Riemannian Computing in Computer Vision, Springer, Cham.10.1007/978-3-319-22957-7
Search in Google Scholar Back to article
Tutte, W.T. (1960). Convex representations of graphs, Proceedings of the London Mathematical Society s3-10(1): 304-320, DOI: 10.1112/plms/s3-10.1.304.10.1112/plms/s3-10.1.304
Search in Google Scholar Back to article
Tutte, W.T. (1963). How to draw a graph, Proceedings of the London Mathematical Society s3-13(1): 743-767, DOI: 10.1112/plms/s3-13.1.743.10.1112/plms/s3-13.1.743
Open DOI Search in Google Scholar Back to article
Valiant, L. (1979). The complexity of enumeration and reliability problems, SIAM Journal on Computing 8(3): 410-421, DOI: 10.1137/0208032.10.1137/0208032
Open DOI Search in Google Scholar Back to article
Van, T.T. and Le, T.M. (2016). Content-based image retrieval using a signature graph and a self-organizing map, International Journal of Applied Mathematics and Computer Science 26(2): 423-438, DOI: 10.1515/amcs-2016-0030.10.1515/amcs-2016-0030
Open DOI Search in Google Scholar Back to article
Švestka, P. and Overmars, M.H. (1998). Coordinated path planning for multiple robots, Robotics and Autonomous Systems 23(3): 125-152, DOI: 10.1016/S0921-8890(97)00033-X.10.1016/S0921-8890(97)00033-X
Open DOI Search in Google Scholar Back to article
Wang, B., Chua, K.C., Wang, W. and Srinivasan, V. (2005). Worst and best information exposure paths in wireless sensor networks, in X. Jia et al. (Eds.), Mobile Adhoc and Sensor Networks, Lecture Notes in Computer Science, Vol. 3794, Springer, Berlin, pp. 52-62, DOI: 10.1007/115994636.10.1007/115994636
Open DOI Search in Google Scholar Back to article
Wojciechowski, W., Molka, A. and Tabor, Z. (2016). Automated measurement of parameters related to the deformities of lower limbs based on X-rays images, Computers in Biology and Medicine 70: 1-11, DOI: 10.1016/j.compbiomed.2015.12.027.10.1016/j.compbiomed.2015.12.02726773234
Open DOI Search in Google Scholar Back to article
Yang, Y. and Wang, J. (2008). Design guidelines for routing metrics in multihop wireless networks, Proceedings of the IEEE Annual Conference on Computer Communications (INFOCOM), Phoenix, AZ, USA, pp. 1615-1623.10.1109/INFOCOM.2008.222
Search in Google Scholar Back to article
Younes, L. (1998). Computable elastic distances between shapes, SIAM Journal on Applied Mathematics 58(2): 565-586, DOI: 10.1137/S0036139995287685.10.1137/S0036139995287685
Open DOI Search in Google Scholar Back to article
Younes, L. (2012). Spaces and manifolds of shapes in computer vision: An overview, Image and Vision Computing 30(67): 389-397, DOI: 10.1016/j.imavis.2011.09.009.10.1016/j.imavis.2011.09.009
Open DOI Search in Google Scholar Back to article
Zhang, M. and Golland, P. (2016). Statistical shape analysis: From landmarks to diffeomorphisms, Medical Image Analysis 33: 155-158, DOI: 10.1016/j.media.2016.06.025.10.1016/j.media.2016.06.025531015827377332
Open DOI Search in Google Scholar Back to article
Zubor, M., K˝or¨osi, A., Guly´as, A. and R´etv´ari, G. (2014). On the computational complexity of policy routing, in Y.Kermarrec (Ed.), Advances in Communication Networking, Lecture Notes in Computer Science, Vol. 8846, Springer, Cham, pp. 202-214, DOI: 10.1007/978-3-319-13488-8 19.10.1007/978-3-319-13488-819
Open DOI Search in Google Scholar Back to article

Closest Paths in Graph Drawings under an Elastic Metric

Abstract

Paradigm

My account