Webbläsaren som du använder stöds inte av denna webbplats. Alla versioner av Internet Explorer stöds inte längre, av oss eller Microsoft (läs mer här: * https://www.microsoft.com/en-us/microsoft-365/windows/end-of-ie-support).

Var god och använd en modern webbläsare för att ta del av denna webbplats, som t.ex. nyaste versioner av Edge, Chrome, Firefox eller Safari osv.

Parallel and Distributed Graph Cuts by Dual Decomposition

In English

Författare

  • Petter Strandmark
  • Fredrik Kahl

Summary, in English

Graph cuts methods are at the core of many state-of-the-art algorithms in computer vision due to their efficiency in computing globally optimal solutions. In this paper, we solve the maximum flow/minimum cut problem in parallel by splitting the graph into multiple parts and hence, further increase the computational efficacy of graph cuts. Optimality of the solution is guaranteed by dual decomposition, or more specifically, the solutions to the subproblems are constrained to be equal on the overlap with dual variables.



We demonstrate that our approach both allows

(i) faster processing on multi-core computers and

(ii) the capability to handle larger problems by splitting the graph across multiple computers on a distributed network.

Even though our approach does not give a theoretical guarantee of speed-up, an extensive empirical evaluation on several applications with many different data sets consistently shows good performance. An open source C++ implementation of the dual decomposition method is also made publicly available.

Publiceringsår

2010

Språk

Engelska

Sidor

2085-2092

Publikation/Tidskrift/Serie

IEEE Conference on Computer Vision and Pattern Recognition

Dokumenttyp

Konferensbidrag

Förlag

IEEE - Institute of Electrical and Electronics Engineers Inc.

Ämne

  • Computer Vision and Robotics (Autonomous Systems)
  • Mathematics

Nyckelord

  • mpi
  • supercomputer
  • parallel
  • graph cuts

Conference name

IEEE Computer Society Conference on Computer Vision and Pattern Recognition Workshops (CVPRW), 2010

Conference date

2010-06-13 - 2010-06-18

Conference place

San Francisco, United States

Status

Published

Forskningsgrupp

  • Mathematical Imaging Group

ISBN/ISSN/Övrigt

  • ISSN: 1063-6919
  • ISBN: 978-1-4244-6984-0