{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,3,30]],"date-time":"2022-03-30T03:37:12Z","timestamp":1648611432996},"reference-count":38,"publisher":"Cambridge University Press (CUP)","issue":"10","license":[{"start":{"date-parts":[[2015,2,24]],"date-time":"2015-02-24T00:00:00Z","timestamp":1424736000000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Robotica"],"published-print":{"date-parts":[[2016,10]]},"abstract":"<jats:title>SUMMARY<\/jats:title><jats:p>In the context of topological mapping, the automatic segmentation of an environment into meaningful and distinct locations is still regarded as an open problem. This paper presents an algorithm to extract places online from image sequences based on the algebraic connectivity of graphs or Fiedler value, which provides an insight into how well connected several consecutive observations are. The main contribution of the proposed method is that it is a theoretically supported alternative to tuning thresholds on similarities, which is a difficult task and environment dependent. It can accommodate any type of feature detector and matching procedure, as it only requires non-negative similarities as input, and is therefore able to deal with descriptors of variable length, to which statistical techniques are difficult to apply. The method has been validated in an office environment using exclusively visual information. Two different types of features, a bag-of-words model built from scale invariant feature transform (SIFT) keypoints, and a more complex fingerprint based on vertical lines, color histograms, and a few Star keypoints, are employed to demonstrate that the method can be applied to both fixed and variable length descriptors with similar results.<\/jats:p>","DOI":"10.1017\/s0263574715000053","type":"journal-article","created":{"date-parts":[[2015,2,24]],"date-time":"2015-02-24T10:37:39Z","timestamp":1424774259000},"page":"2400-2413","source":"Crossref","is-referenced-by-count":0,"title":["Online topological segmentation of visual sequences using the algebraic connectivity of graphs"],"prefix":"10.1017","volume":"34","author":[{"given":"Jaime","family":"Boal","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"\u00c1lvaro","family":"S\u00e1nchez-Miralles","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2015,2,24]]},"reference":[{"key":"S0263574715000053_ref29","unstructured":"E. Billauer , \u201cpeakdet: Peak detection using MATLAB,\u201d (2012). Available at: http:\/\/billauer.co.il\/peakdet.html, accessed Apr. 27, 2014."},{"key":"S0263574715000053_ref3","unstructured":"D. Kortenkamp and T. Weymouth , \u201cTopological Mapping for Mobile Robots using a Combination of Sonar and Vision Sensing,\u201d Proceedings of the AAAI 12th National Conference on Artificial Intelligence, Seattle, WA, USA (1994) pp. 979\u2013984."},{"key":"S0263574715000053_ref34","doi-asserted-by":"publisher","DOI":"10.1177\/0278364909103912"},{"key":"S0263574715000053_ref22","doi-asserted-by":"crossref","first-page":"298","DOI":"10.21136\/CMJ.1973.101168","article-title":"Algebraic connectivity of graphs","volume":"23","author":"Fiedler","year":"1973","journal-title":"Czech. Math. J."},{"key":"S0263574715000053_ref4","doi-asserted-by":"crossref","unstructured":"B. Kuipers , J. Modayil , P. Beeson , M. MacMahon and F. Savelli , \u201cLocal Metrical and Global Topological Maps in the Hybrid Spatial Semantic Hierarchy,\u201d Proceedings of the IEEE International Conferemce on Robotics and Automation, New Orleans, LA, USA, vol. 5 (2004) pp. 4845\u20134851.","DOI":"10.1109\/ROBOT.2004.1302485"},{"key":"S0263574715000053_ref33","doi-asserted-by":"crossref","unstructured":"J. Luo , A. Pronobis , B. Caputo and P. Jensfelt , \u201cIncremental Learning for Place Recognition in Dynamic Environments,\u201d Proceedings of the IEEE\/RSJ International Conference Intelligent Robots and Systems, San Diego, CA, USA (2007) pp. 721\u2013728.","DOI":"10.1109\/IROS.2007.4398986"},{"key":"S0263574715000053_ref24","doi-asserted-by":"publisher","DOI":"10.1016\/j.laa.2006.07.020"},{"key":"S0263574715000053_ref19","doi-asserted-by":"publisher","DOI":"10.1162\/089976603321780317"},{"key":"S0263574715000053_ref28","doi-asserted-by":"publisher","DOI":"10.1109\/TVCG.2013.181"},{"key":"S0263574715000053_ref16","doi-asserted-by":"crossref","unstructured":"A. Angeli , S. Doncieux , J.-A. Meyer and D. Filliat , \u201cIncremental Vision-Based Topological SLAM,\u201d Proceedings of the IEEE\/RSJ International Conference Intelligent Robots and Systems, Nice, France (2008) pp. 1031\u20131036.","DOI":"10.1109\/IROS.2008.4650675"},{"key":"S0263574715000053_ref13","doi-asserted-by":"crossref","unstructured":"M. Liu and R. Siegwart , \u201cDP-FACT: Towards Topological Mapping and Scene Recognition with Color for Omnidirectional Camera,\u201d Proceedings of the IEEE International Conference on Robotics and Automation, Saint Paul, MN, USA (2012) pp. 3503\u20133508.","DOI":"10.1109\/ICRA.2012.6225040"},{"key":"S0263574715000053_ref7","doi-asserted-by":"crossref","unstructured":"A. Ranganathan and F. Dellaert , \u201cBayesian Surprise and Landmark Detection,\u201d Proceedings of the IEEE International Conference on Robotics and Automation, Kobe, Japan (2009) pp. 2017\u20132023.","DOI":"10.1109\/ROBOT.2009.5152376"},{"key":"S0263574715000053_ref32","unstructured":"C. Sanderson , \u201cArmadillo: An open source C++ linear algebra library for fast prototyping and computationally intensive experiments,\u201d Technical report, NICTA (2010). Available at: http:\/\/arma.sourceforge.net, accessed Apr. 27, 2014."},{"key":"S0263574715000053_ref26","first-page":"108","volume-title":"Lecture Notes in Computer Science","author":"Szyma\u0144ski","year":"2011"},{"key":"S0263574715000053_ref23","volume-title":"Spectral Graph Theory","author":"Chung","year":"1997"},{"key":"S0263574715000053_ref8","doi-asserted-by":"crossref","unstructured":"L. Itti and P. Baldi , \u201cA Principled Approach to Detecting Surprising Events in Video,\u201d Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition, San Diego, CA, USA, vol. 1 (2005) pp. 631\u2013637.","DOI":"10.1109\/CVPR.2005.40"},{"key":"S0263574715000053_ref1","doi-asserted-by":"publisher","DOI":"10.1109\/70.928558"},{"key":"S0263574715000053_ref30","first-page":"378","article-title":"Acquisition of structural versus object landmark knowledge","volume":"33","author":"Stankiewicz","year":"2007","journal-title":"J. Exp. Psychol.: Human Perception Perform."},{"key":"S0263574715000053_ref37","doi-asserted-by":"crossref","unstructured":"J. Boal , \u00c1. S\u00e1nchez-Miralles and M. Alvar , \u201cMatching monocular lightweight features using n-gram techniques for topological location identification,\u201d Robotica FirstView, 1\u201315 (2014).","DOI":"10.1017\/S0263574714001076"},{"key":"S0263574715000053_ref36","doi-asserted-by":"publisher","DOI":"10.1023\/B:VISI.0000029664.99615.94"},{"key":"S0263574715000053_ref18","doi-asserted-by":"crossref","unstructured":"M. Liu , F. Colas and R. Siegwart , \u201cRegional Topological Segmentation based on Mutual Information Graphs,\u201d Proceedings of the IEEE International Conference Robotics and Automation, Shanghai, China (2011) pp. 3269\u20133274.","DOI":"10.1109\/ICRA.2011.5979672"},{"key":"S0263574715000053_ref31","unstructured":"G. Bradski , \u201cThe OpenCV library,\u201d (2000). Available at: http:\/\/www.opencv.org, accessed Apr. 27, 2014."},{"key":"S0263574715000053_ref35","unstructured":"J. Luo , A. Pronobis , B. Caputo and P. Jensfelt , \u201cThe KTH-IDOL2 database,\u201d Technical Report CVAP304, KTH Royal Institute of Technology, CVAP\/CAS, Stockholm, Sweden (2006)."},{"key":"S0263574715000053_ref10","doi-asserted-by":"crossref","unstructured":"A. Ranganathan , \u201cPLISS: Detecting and Labeling Places using Online Change-Point Detection,\u201d Proceedings of the Robotics: Science and Systems, Zaragoza, Spain (2010).","DOI":"10.15607\/RSS.2010.VI.024"},{"key":"S0263574715000053_ref21","doi-asserted-by":"publisher","DOI":"10.1007\/s11222-007-9033-z"},{"key":"S0263574715000053_ref15","unstructured":"A. Chapoulie , P. Rives and D. Filliat , \u201cAppearance-Based Segmentation of Indoors\/Outdoors Sequences of Spherical Views,\u201d Proceedings of the IEEE\/RSJ International Conference on Intelligent Robots and Systems, Tokyo, Japan (2013) pp. 1946\u20131951."},{"key":"S0263574715000053_ref6","doi-asserted-by":"publisher","DOI":"10.1007\/s10339-012-0502-8"},{"key":"S0263574715000053_ref14","doi-asserted-by":"publisher","DOI":"10.1109\/TRO.2013.2272250"},{"key":"S0263574715000053_ref12","unstructured":"R. P. Adams and D. J. C. MacKay , \u201cBayesian online changepoint detection,\u201d Technical Report. University of Cambridge, Cambridge, UK (2007). arXiv:0710.3742v1 [stat.ML]."},{"key":"S0263574715000053_ref11","doi-asserted-by":"publisher","DOI":"10.1007\/s10514-012-9273-4"},{"key":"S0263574715000053_ref2","doi-asserted-by":"crossref","unstructured":"P. Beeson , N. K. Jong and B. Kuipers , \u201cTowards Autonomous Topological Place Detection using the Extended Voronoi Graph,\u201d Proceedings of the IEEE International Conference on Robotics and Automation, Barcelona, Spain (2005) pp. 4373\u20134379.","DOI":"10.1109\/ROBOT.2005.1570793"},{"key":"S0263574715000053_ref9","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2008.111"},{"key":"S0263574715000053_ref27","first-page":"1963","article-title":"Learning spectral clustering, with application to speech separation","volume":"7","author":"Bach","year":"2006","journal-title":"J. Mach. Learn. Res."},{"key":"S0263574715000053_ref38","doi-asserted-by":"publisher","DOI":"10.1177\/0278364910393287"},{"key":"S0263574715000053_ref17","first-page":"300","article-title":"Comprehensive survey on distance\/similarity measures between probability density functions","volume":"1","author":"Cha","year":"2007","journal-title":"Int. J. Math. Models Methods Appl. Sci."},{"key":"S0263574715000053_ref20","first-page":"849","article-title":"On spectral clustering: Analysis and an algorithm","volume":"14","author":"Ng","year":"2002","journal-title":"Adv. Neural Inform. Process. Syst."},{"key":"S0263574715000053_ref5","unstructured":"A. Tapus and R. Siegwart , \u201cIncremental Robot Mapping with Fingerprints of Places,\u201d Proceedings of the IEEE\/RSJ International Conference on Intelligent Robots and Systems, Edmonton, AB, Canada (2005) pp. 2429\u20132434."},{"key":"S0263574715000053_ref25","first-page":"868","volume-title":"Encyclopedia of Algorithms","author":"New","year":"2008"}],"container-title":["Robotica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0263574715000053","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,8,30]],"date-time":"2020-08-30T07:41:03Z","timestamp":1598773263000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0263574715000053\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,2,24]]},"references-count":38,"journal-issue":{"issue":"10","published-print":{"date-parts":[[2016,10]]}},"alternative-id":["S0263574715000053"],"URL":"https:\/\/doi.org\/10.1017\/s0263574715000053","relation":{},"ISSN":["0263-5747","1469-8668"],"issn-type":[{"value":"0263-5747","type":"print"},{"value":"1469-8668","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,2,24]]}}}