{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,8,2]],"date-time":"2023-08-02T16:17:37Z","timestamp":1690993057213},"reference-count":43,"publisher":"World Scientific Pub Co Pte Lt","issue":"11","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Patt. Recogn. Artif. Intell."],"published-print":{"date-parts":[[2019,10]]},"abstract":"<jats:p> Hierarchical image segmentation provides a region-oriented scale-space, i.e. a set of image segmentations at different detail levels in which the segmentations at finer levels are nested with respect to those at coarser levels. However, most image segmentation algorithms, among which a graph-based image segmentation method relying on a region merging criterion was proposed by Felzenszwalb\u2013Huttenlocher in 2004, do not lead to a hierarchy. In order to cope with a demand for hierarchical segmentation, Guimar\u00e3es et al. proposed in 2012 a method for hierarchizing the popular Felzenszwalb\u2013Huttenlocher method, without providing an algorithm to compute the proposed hierarchy. This paper is devoted to providing a series of algorithms to compute the result of this hierarchical graph-based image segmentation method efficiently, based mainly on two ideas: optimal dissimilarity measuring and incremental update of the hierarchical structure. Experiments show that, for an image of size 321 \u00d7 481 pixels, the most efficient algorithm produces the result in half a second whereas the most naive one requires more than 4 h. <\/jats:p>","DOI":"10.1142\/s0218001419400081","type":"journal-article","created":{"date-parts":[[2018,12,27]],"date-time":"2018-12-27T09:48:52Z","timestamp":1545904132000},"page":"1940008","source":"Crossref","is-referenced-by-count":2,"title":["Efficient Algorithms for Hierarchical Graph-Based Segmentation Relying on the Felzenszwalb\u2013Huttenlocher Dissimilarity"],"prefix":"10.1142","volume":"33","author":[{"given":"Edward Cayllahua","family":"Cahuina","sequence":"first","affiliation":[{"name":"Universidade Federal de Minas Gerais, Computer Science Department, 31270-901 Belo Horizonte, Brazil and Universit\u00e9 Paris-Est, ESIEE Paris, F-93162 Noisy-le-Grand, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jean","family":"Cousty","sequence":"additional","affiliation":[{"name":"Universit\u00e9 Paris-Est, LIGM (UMR 8049), CNRS, ENPC, ESIEE Paris, UPEM, F-93162 Noisy-le-Grand, France"},{"name":"Universit\u00e9 Paris Descartes, Laboratoire MAP5 (UMR 8145), 12 Rue de l\u2019\u00c9cole de M\u00e9decine, 75006 Paris, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yukiko","family":"Kenmochi","sequence":"additional","affiliation":[{"name":"Universit\u00e9 Paris-Est, LIGM (UMR 8049), CNRS, ENPC, ESIEE Paris, UPEM, F-93162 Noisy-le-Grand, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Arnaldo","family":"de Albuquerque Ara\u00fajo","sequence":"additional","affiliation":[{"name":"Universidade Federal de Minas Gerais, Computer Science Department, 31270-901 Belo Horizonte, Brazil and Universit\u00e9 Paris-Est, ESIEE Paris, F-93162 Noisy-le-Grand, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Guillermo","family":"C\u00e1mara-Ch\u00e1vez","sequence":"additional","affiliation":[{"name":"Universidade Federal de Ouro Preto, Computer Science Department, 35400-000 Ouro Preto, Brazil"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Silvio Jamil F.","family":"Guimar\u00e3es","sequence":"additional","affiliation":[{"name":"PUC Minas \u2014 ICEI \u2014 Computer Science Department \u2014 VIPLAB, 30535-065 Belo Horizonte, Brazil and Universit\u00e9 Paris-Est, ESIEE Paris, F-93162 Noisy-le-Grand, France"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2019,10,17]]},"reference":[{"key":"S0218001419400081BIB001","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2010.161"},{"key":"S0218001419400081BIB002","doi-asserted-by":"publisher","DOI":"10.1007\/978-94-011-1040-2_10"},{"key":"S0218001419400081BIB003","doi-asserted-by":"publisher","DOI":"10.1109\/TIP.2014.2336551"},{"key":"S0218001419400081BIB004","volume-title":"Int. Conf. Pattern Recognition and Artificial Intelligence","author":"Cayllahua Cahuina E. J. Y.","year":"2018"},{"key":"S0218001419400081BIB005","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-21569-8_24"},{"key":"S0218001419400081BIB006","first-page":"1","author":"Cousty J.","year":"2017","journal-title":"J. Math. Imaging Vision"},{"key":"S0218001419400081BIB007","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-38294-9_8"},{"key":"S0218001419400081BIB008","doi-asserted-by":"publisher","DOI":"10.1023\/B:VISI.0000022288.19776.77"},{"key":"S0218001419400081BIB009","first-page":"1","author":"G\u00f6tz M.","year":"2018","journal-title":"IEEE Trans. Parallel Distribut. Syst."},{"key":"S0218001419400081BIB010","doi-asserted-by":"publisher","DOI":"10.1007\/s11263-005-6299-0"},{"key":"S0218001419400081BIB011","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-34166-3_13"},{"key":"S0218001419400081BIB012","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-23234-8_3"},{"key":"S0218001419400081BIB013","first-page":"1","author":"Guimar\u00e3es S.","year":"2017","journal-title":"Math. Morphol. Theory Appl."},{"key":"S0218001419400081BIB014","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-41181-6_2"},{"key":"S0218001419400081BIB015","first-page":"1","author":"Havel J.","year":"2016","journal-title":"J. Real-Time Image Processing"},{"key":"S0218001419400081BIB016","doi-asserted-by":"publisher","DOI":"10.1007\/s11263-010-0400-4"},{"key":"S0218001419400081BIB017","doi-asserted-by":"publisher","DOI":"10.1016\/j.patcog.2006.02.017"},{"key":"S0218001419400081BIB018","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4613-0469-2_38"},{"key":"S0218001419400081BIB019","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-48236-9_17"},{"key":"S0218001419400081BIB020","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-38294-9_12"},{"key":"S0218001419400081BIB021","doi-asserted-by":"publisher","DOI":"10.1109\/34.546254"},{"key":"S0218001419400081BIB022","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2004.110"},{"key":"S0218001419400081BIB023","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-88304-0"},{"key":"S0218001419400081BIB024","doi-asserted-by":"publisher","DOI":"10.1109\/TIP.2011.2157512"},{"key":"S0218001419400081BIB025","doi-asserted-by":"publisher","DOI":"10.1109\/TIP.2017.2779604"},{"key":"S0218001419400081BIB026","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2014.2366145"},{"key":"S0218001419400081BIB027","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-18720-4_4"},{"key":"S0218001419400081BIB028","volume-title":"Int. Conf. Pattern Recognition and Artificial Intelligence","author":"Pham M.","year":"2018"},{"key":"S0218001419400081BIB029","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2016.2537320"},{"key":"S0218001419400081BIB030","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-33765-9_58"},{"key":"S0218001419400081BIB031","doi-asserted-by":"publisher","DOI":"10.1109\/ICASSP.2012.6288021"},{"key":"S0218001419400081BIB032","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2015.2481406"},{"key":"S0218001419400081BIB033","volume-title":"Int. Conf. Pattern Recognition and Artificial Intelligence (ICPRAI)","author":"Randrianasoa J. F.","year":"2018"},{"key":"S0218001419400081BIB034","first-page":"2011","volume-title":"IEEE Conf. Computer Vision and Pattern Recognition","author":"Ren Z."},{"key":"S0218001419400081BIB035","doi-asserted-by":"publisher","DOI":"10.1109\/TGRS.2016.2566581"},{"key":"S0218001419400081BIB036","doi-asserted-by":"publisher","DOI":"10.1109\/83.841934"},{"key":"S0218001419400081BIB037","doi-asserted-by":"publisher","DOI":"10.1109\/83.663500"},{"key":"S0218001419400081BIB038","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2007.70817"},{"key":"S0218001419400081BIB039","doi-asserted-by":"publisher","DOI":"10.1109\/TIP.2017.2651395"},{"key":"S0218001419400081BIB040","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2007.70836"},{"key":"S0218001419400081BIB041","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2016.2554550"},{"key":"S0218001419400081BIB042","doi-asserted-by":"publisher","DOI":"10.1109\/CVPR.2013.153"},{"key":"S0218001419400081BIB043","doi-asserted-by":"publisher","DOI":"10.5244\/C.29.110"}],"container-title":["International Journal of Pattern Recognition and Artificial Intelligence"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0218001419400081","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,10,17]],"date-time":"2019-10-17T10:19:44Z","timestamp":1571307584000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0218001419400081"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,10]]},"references-count":43,"journal-issue":{"issue":"11","published-print":{"date-parts":[[2019,10]]}},"alternative-id":["10.1142\/S0218001419400081"],"URL":"https:\/\/doi.org\/10.1142\/s0218001419400081","relation":{},"ISSN":["0218-0014","1793-6381"],"issn-type":[{"value":"0218-0014","type":"print"},{"value":"1793-6381","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,10]]}}}