Optimizing Computation of Minimum Cut in Graphs with Grid Topology

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21230%2F13%3A00192353" target="_blank" >RIV/68407700:21230/13:00192353 - isvavai.cz</a>

Výsledek na webu

<a href="http://patft.uspto.gov/netacgi/nph-Parser?Sect1=PTO1&Sect2=HITOFF&d=PALL&p=1&u=%2Fnetahtml%2FPTO%2Fsrchnum.htm&r=1&f=G&l=50&s1=8,533,139.PN.&OS=PN/8,533,139&RS=PN/8,533,139" target="_blank" >http://patft.uspto.gov/netacgi/nph-Parser?Sect1=PTO1&Sect2=HITOFF&d=PALL&p=1&u=%2Fnetahtml%2FPTO%2Fsrchnum.htm&r=1&f=G&l=50&s1=8,533,139.PN.&OS=PN/8,533,139&RS=PN/8,533,139</a>

DOI - Digital Object Identifier

—

Jazyk výsledku

angličtina

Název v původním jazyce

Optimizing Computation of Minimum Cut in Graphs with Grid Topology

Popis výsledku v původním jazyce

Approaches for optimizing computation of minimum cut or maximum flow on graphs comprising a plurality of nodes and edges with grid-like topologies are disclosed. Embodiments exploit the regular structure of input graphs to reduce the memory bandwidth - amain bottleneck of popular max-flow/min-cut algorithms based on finding augmenting paths on a residual graph (such as Ford-Fulkerson [1956] or Boykov-Kolmogorov [2004]). Disclosed embodiments allow more than 200% speed-up without sacrificing optimalityof the final solution, which is crucial for many computer vision and graphics applications. Method and system embodiments replace standard linked list representation of general graphs with a set of compact data structures with blocked memory layout thatenables fixed ordering of edges and implicit branchless addressing of nodes. The embodiments are orthogonal to other optimizations such as parallel processing or hierarchical methods and can be readily plugged into existing min-cut/max-fl

Název v anglickém jazyce

Optimizing Computation of Minimum Cut in Graphs with Grid Topology

Popis výsledku anglicky

Approaches for optimizing computation of minimum cut or maximum flow on graphs comprising a plurality of nodes and edges with grid-like topologies are disclosed. Embodiments exploit the regular structure of input graphs to reduce the memory bandwidth - amain bottleneck of popular max-flow/min-cut algorithms based on finding augmenting paths on a residual graph (such as Ford-Fulkerson [1956] or Boykov-Kolmogorov [2004]). Disclosed embodiments allow more than 200% speed-up without sacrificing optimalityof the final solution, which is crucial for many computer vision and graphics applications. Method and system embodiments replace standard linked list representation of general graphs with a set of compact data structures with blocked memory layout thatenables fixed ordering of edges and implicit branchless addressing of nodes. The embodiments are orthogonal to other optimizations such as parallel processing or hierarchical methods and can be readily plugged into existing min-cut/max-fl

Druh

P - Patent

CEP obor

JC - Počítačový hardware a software

OECD FORD obor

—

Projekt

<a href="/cs/project/TE01020415" target="_blank" >TE01020415: Centrum kompetence ve zpracování vizuálních informací (V3C - Visual Computing Competence Center)</a><br>

Návaznosti

S - Specificky vyzkum na vysokych skolach

Rok uplatnění

2013

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Číslo patentu nebo vzoru

US8,533,139

Vydavatel

US001 -

Název vydavatele

United States Patent and Trademark Office (USPTO)

Místo vydání

Alexandria

Stát vydání

US - Spojené státy americké

Datum přijetí

10. 9. 2013

Název vlastníka

ČVUT FEL (DCGI)

Způsob využití

B - Výsledek je využíván orgány státní nebo veřejné správy

Druh možnosti využití

A - K využití výsledku jiným subjektem je vždy nutné nabytí licence