Closest paths in graph drawings under an elastic metric

• Autorzy: Baran M.

Identyfikatory

DOI

10.2478/amcs-2018-0029

• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

elastic shape analysis; pattern recognition; superpixel segmentation

PL

analiza kształtu; rozpoznawanie wzorca; segmentacja obrazu; superpiksel

• Wydawca: Oficyna Wydawnicza Uniwersytetu Zielonogórskiego
• Czasopismo: International Journal of Applied Mathematics and Computer Science
• Rocznik: 2018
• Tom: Vol. 28, no. 2
• Strony: 387--397
• Opis fizyczny: Bibliogr. 41 poz., rys., tab.

Twórcy

autor

Baran M.

• Faculty of Physics, Mathematics and Computer Science, Cracow University of Technology, ul. Warszawska 24, 31-155 Kraków, Poland

Bibliografia

• [1] Bernal, J., Doğan, 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.
• [2] 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.
• [3] 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.
• [4] Dice, L.R. (1945). Measures of the amount of ecologic association between species, Ecology 26(3): 297–302, DOI: 10.2307/1932409.
• [5] Dijkstra, E.W. (1959). A note on two problems in connexion with graphs, Numerische Mathematik 1(1): 269–271, DOI: 10.1007/BF01386390.
• [6] Doğan, 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.
• [7] Dryden, I.L. and Mardia, K.V. (1998). Statistical Shape Analysis, 1st Edn., Wiley, Chichester.
• [8] Fáry, I. (1948). On straight line representation of planar graphs, Acta Scientiarum Mathematicarum (Szeged) 11(4–4): 229–233.
• [9] 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] 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.
• [11] 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.
• [12] 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.
• [13] Mehrotra, R. and Gary, J.E. (1995). Similar-shape retrieval in shape data management, Computer 28(9): 57–62, DOI: 10.1109/2.410154.
• [14] 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.
• [15] 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.
• [16] 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.
• [17] 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.
• [18] 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.
• [19] 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.
• [20] 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.
• [21] 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.
• [22] 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.
• [23] 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.
• [24] Srivastava, A. and Klassen, E.P. (2016). Functional and Shape Data Analysis, Springer, New York, NY.
• [25] 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.
• [26] 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.
• [27] 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.
• [28] 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.
• [29] Turaga, P.K. and Srivastava, A. (2016). Riemannian Computing in Computer Vision, Springer, Cham.
• [30] 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.
• [31] 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.
• [32] Valiant, L. (1979). The complexity of enumeration and reliability problems, SIAM Journal on Computing 8(3): 410–421, DOI: 10.1137/0208032.
• [33] 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.
• [34] Š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.
• [35] 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/11599463 6.
• [36] 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.
• [37] 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.
• [38] Younes, L. (1998). Computable elastic distances between shapes, SIAM Journal on Applied Mathematics 58(2): 565–586, DOI: 10.1137/S0036139995287685.
• [39] 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.
• [40] 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.
• [41] Zubor, M., Kőrösi, A., Gulyás, A. and Rétvári, 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.

Uwagi

PL

Opracowanie rekordu w ramach umowy 509/P-DUN/2018 ze środków MNiSW przeznaczonych na działalność upowszechniającą naukę (2018).