{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,1]],"date-time":"2025-11-01T02:46:42Z","timestamp":1761965202621,"version":"3.37.3"},"reference-count":23,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2020,6,1]],"date-time":"2020-06-01T00:00:00Z","timestamp":1590969600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2020,6,16]],"date-time":"2020-06-16T00:00:00Z","timestamp":1592265600000},"content-version":"vor","delay-in-days":15,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100007051","name":"Uppsala University","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100007051","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Math Imaging Vis"],"published-print":{"date-parts":[[2020,6]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Many problems in applied computer science can be expressed in a graph setting and solved by finding an appropriate vertex labeling of the associated graph. It is also common to identify the term \u201cappropriate labeling\u201d with a labeling that optimizes some application-motivated objective function. The goal of this work is to present two algorithms that, for the objective functions in a general format motivated by image processing tasks, find such optimal labelings. Specifically, we consider a problem of finding an optimal binary labeling for the objective function defined as the max-norm over a set of <jats:italic>local costs<\/jats:italic> of a form that naturally appears in image processing. It is well known that for a limited subclass of such problems, globally optimal solutions can be found via <jats:italic>watershed cuts<\/jats:italic>, that is, by the cuts associated with the optimal spanning forests of a graph. Here, we propose two new algorithms for optimizing a broader class of such problems. The first algorithm, that works for all considered objective functions, returns a globally optimal labeling in quadratic time with respect to the size of the graph (i.e., the number of its vertices and edges) or, for an image associated graph, the size of the image. The second algorithm is more efficient, with quasi-linear time complexity, and returns a globally optimal labeling provided that the objective function satisfies certain given conditions. These conditions are analogous to the submodularity conditions encountered in max-flow\/min-cut optimization, where the objective function is defined as sum of all local costs. We will also consider a refinement of the max-norm measure, defined in terms of the lexicographical order, and examine the algorithms that could find minimal labelings with respect to this refined measure.<\/jats:p>","DOI":"10.1007\/s10851-020-00963-8","type":"journal-article","created":{"date-parts":[[2020,6,16]],"date-time":"2020-06-16T08:03:03Z","timestamp":1592294583000},"page":"737-750","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Two Polynomial Time Graph Labeling Algorithms Optimizing Max-Norm-Based Objective Functions"],"prefix":"10.1007","volume":"62","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-4980-2755","authenticated-orcid":false,"given":"Filip","family":"Malmberg","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Krzysztof Chris","family":"Ciesielski","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2020,6,16]]},"reference":[{"key":"963_CR1","doi-asserted-by":"crossref","unstructured":"Abbas, A., Swoboda, P.: Bottleneck potentials in Markov random fields. In: Proceedings of the IEEE International Conference on Computer Vision, pp. 3175\u20133184 (2019)","DOI":"10.1109\/ICCV.2019.00327"},{"key":"963_CR2","unstructured":"All\u00e8ne, C., Audibert, J.Y., Couprie, M., Cousty, J., Keriven, R., et\u00a0al.: Some links between min-cuts, optimal spanning forests and watersheds. Math. Morphol. Its Appl. Image Signal Process. 253\u2013264 http:\/\/mtc-21b.sid.inpe.br\/col\/dpi.inpe.br\/ismm@80\/2007\/07.16.14.39\/doc\/book.pdf (2007)"},{"issue":"3","key":"963_CR3","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1016\/0020-0190(79)90002-4","volume":"8","author":"B Aspvall","year":"1979","unstructured":"Aspvall, B., Plass, M.F., Tarjan, R.E.: A linear-time algorithm for testing the truth of certain quantified Boolean formulas. Inf. Process. Lett. 8(3), 121\u2013123 (1979)","journal-title":"Inf. Process. Lett."},{"issue":"11","key":"963_CR4","doi-asserted-by":"publisher","first-page":"1222","DOI":"10.1109\/34.969114","volume":"23","author":"Y Boykov","year":"2001","unstructured":"Boykov, Y., Veksler, O., Zabih, R.: Fast approximate energy minimization via graph cuts. IEEE Trans. Pattern Anal. Mach. Intell. 23(11), 1222\u20131239 (2001)","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"issue":"1","key":"963_CR5","doi-asserted-by":"publisher","first-page":"146","DOI":"10.1016\/j.cviu.2009.09.006","volume":"114","author":"KC Ciesielski","year":"2010","unstructured":"Ciesielski, K.C., Udupa, J.K.: Affinity functions in fuzzy connectedness based image segmentation I: equivalence of affinities. Comput. Vis. Image Underst 114(1), 146\u2013154 (2010)","journal-title":"Comput. Vis. Image Underst"},{"issue":"3","key":"963_CR6","doi-asserted-by":"publisher","first-page":"375","DOI":"10.1007\/s10851-012-0333-3","volume":"44","author":"KC Ciesielski","year":"2012","unstructured":"Ciesielski, K.C., Udupa, J.K., Falc\u00e3o, A.X., Miranda, P.A.: Fuzzy connectedness image segmentation in graph cut formulation: a linear-time algorithm and a comparative analysis. J. Math. Imaging Vis. 44(3), 375\u2013398 (2012)","journal-title":"J. Math. Imaging Vis."},{"key":"963_CR7","volume-title":"Introduction to Algorithms","author":"TH Cormen","year":"2009","unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms. MIT Press, Cambridge (2009)"},{"issue":"7","key":"963_CR8","doi-asserted-by":"publisher","first-page":"1384","DOI":"10.1109\/TPAMI.2010.200","volume":"33","author":"C Couprie","year":"2011","unstructured":"Couprie, C., Grady, L., Najman, L., Talbot, H.: Power watershed: a unifying graph-based optimization framework. IEEE Trans. Pattern Anal. Mach. Intell. 33(7), 1384\u20131399 (2011)","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"issue":"8","key":"963_CR9","doi-asserted-by":"publisher","first-page":"1362","DOI":"10.1109\/TPAMI.2008.173","volume":"31","author":"J Cousty","year":"2009","unstructured":"Cousty, J., Bertrand, G., Najman, L., Couprie, M.: Watershed cuts: minimum spanning forests and the drop of water principle. IEEE Trans. Pattern Anal. Mach. Intell. 31(8), 1362\u20131374 (2009)","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"issue":"5","key":"963_CR10","doi-asserted-by":"publisher","first-page":"925","DOI":"10.1109\/TPAMI.2009.71","volume":"32","author":"J Cousty","year":"2009","unstructured":"Cousty, J., Bertrand, G., Najman, L., Couprie, M.: Watershed cuts: thinnings, shortest path forests, and topological watersheds. IEEE Trans. Pattern Anal. Mach. Intell. 32(5), 925\u2013939 (2009)","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"issue":"1","key":"963_CR11","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1007\/BF01386390","volume":"1","author":"EW Dijkstra","year":"1959","unstructured":"Dijkstra, E.W.: A note on two problems in connexion with graphs. Numer. Math. 1(1), 269\u2013271 (1959)","journal-title":"Numer. Math."},{"issue":"4","key":"963_CR12","first-page":"57","volume":"6","author":"V Jarn\u00eck","year":"1930","unstructured":"Jarn\u00eck, V.: O jist\u00e9m probl\u00e9mu minim\u00e1l\u00edm (On a certain problem of minimization). Pr\u00e1ce moravsk\u00e9 p\u0159\u00edrodov\u011bdeck\u00e9 spole\u010dnosti 6(4), 57\u201363 (1930)","journal-title":"Pr\u00e1ce moravsk\u00e9 p\u0159\u00edrodov\u011bdeck\u00e9 spole\u010dnosti"},{"issue":"2","key":"963_CR13","doi-asserted-by":"publisher","first-page":"147","DOI":"10.1109\/TPAMI.2004.1262177","volume":"26","author":"V Kolmogorov","year":"2004","unstructured":"Kolmogorov, V., Zabih, R.: What energy functions can be minimized via graph cuts? IEEE Trans. Pattern Anal. Mach. Intell. 26(2), 147\u2013159 (2004)","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"issue":"1","key":"963_CR14","doi-asserted-by":"publisher","first-page":"48","DOI":"10.1090\/S0002-9939-1956-0078686-7","volume":"7","author":"JB Kruskal","year":"1956","unstructured":"Kruskal, J.B.: On the shortest spanning subtree of a graph and the traveling salesman problem. Proc. Am. Math. Soc. 7(1), 48\u201350 (1956)","journal-title":"Proc. Am. Math. Soc."},{"issue":"6","key":"963_CR15","first-page":"185","volume":"33","author":"Z Levi","year":"2014","unstructured":"Levi, Z., Zorin, D.: Strict minimizers for geometric optimization. ACM Trans. Gr. (TOG) 33(6), 185 (2014)","journal-title":"ACM Trans. Gr. (TOG)"},{"key":"963_CR16","doi-asserted-by":"crossref","unstructured":"Malmberg, F., Ciesielski, K.C., Strand, R.: Optimization of max-norm objective functions in image processing and computer vision. In: International Conference on Discrete Geometry for Computer Imagery, pp. 206\u2013218. Springer (2019)","DOI":"10.1007\/978-3-030-14085-4_17"},{"key":"963_CR17","doi-asserted-by":"crossref","unstructured":"Malmberg, F., Strand, R.: When can $$l_p$$-norm objective functions be minimized via graph cuts? In: International Workshop on Combinatorial Image Analysis. Springer (2018)","DOI":"10.1007\/978-3-030-05288-1_9"},{"issue":"4","key":"963_CR18","doi-asserted-by":"publisher","first-page":"2275","DOI":"10.1137\/17M1118580","volume":"10","author":"L Najman","year":"2017","unstructured":"Najman, L.: Extending the power watershed framework thanks to $$\\gamma $$-convergence. SIAM J. Imaging Sci. 10(4), 2275\u20132292 (2017)","journal-title":"SIAM J. Imaging Sci."},{"issue":"6","key":"963_CR19","doi-asserted-by":"publisher","first-page":"1389","DOI":"10.1002\/j.1538-7305.1957.tb01515.x","volume":"36","author":"RC Prim","year":"1957","unstructured":"Prim, R.C.: Shortest connection networks and some generalizations. Bell Syst. Techn. J. 36(6), 1389\u20131401 (1957)","journal-title":"Bell Syst. Techn. J."},{"key":"963_CR20","doi-asserted-by":"crossref","unstructured":"Sinop, A.K., Grady, L.: A seeded image segmentation framework unifying graph cuts and random walker which yields a new algorithm. In: 2007 IEEE 11th International Conference on Computer Vision, pp. 1\u20138. IEEE (2007)","DOI":"10.1109\/ICCV.2007.4408927"},{"key":"963_CR21","doi-asserted-by":"crossref","unstructured":"Wolf, S., Bailoni, A., Pape, C., Rahaman, N., Kreshuk, A., K\u00f6the, U., Hamprecht, F.A.: The mutex watershed and its objective: efficient, parameter-free image partitioning. arXiv preprint arXiv:1904.12654 (2019)","DOI":"10.1109\/TPAMI.2020.2980827"},{"key":"963_CR22","doi-asserted-by":"crossref","unstructured":"Wolf, S., Pape, C., Bailoni, A., Rahaman, N., Kreshuk, A., Kothe, U., Hamprecht, F.: The mutex watershed: efficient, parameter-free image partitioning. In: Proceedings of the European Conference on Computer Vision (ECCV), pp. 546\u2013562 (2018)","DOI":"10.1007\/978-3-030-01225-0_34"},{"key":"963_CR23","doi-asserted-by":"crossref","unstructured":"Wolf, S., Schott, L., Kothe, U., Hamprecht, F.: Learned watershed: end-to-end learning of seeded segmentation. In: Proceedings of the IEEE International Conference on Computer Vision, pp. 2011\u20132019 (2017)","DOI":"10.1109\/ICCV.2017.222"}],"container-title":["Journal of Mathematical Imaging and Vision"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10851-020-00963-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10851-020-00963-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10851-020-00963-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,6,15]],"date-time":"2021-06-15T23:46:34Z","timestamp":1623800794000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10851-020-00963-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,6]]},"references-count":23,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2020,6]]}},"alternative-id":["963"],"URL":"https:\/\/doi.org\/10.1007\/s10851-020-00963-8","relation":{},"ISSN":["0924-9907","1573-7683"],"issn-type":[{"type":"print","value":"0924-9907"},{"type":"electronic","value":"1573-7683"}],"subject":[],"published":{"date-parts":[[2020,6]]},"assertion":[{"value":"27 June 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 May 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"16 June 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}