会员体验
专利管家(专利管理)
工作空间(专利管理)
风险监控(情报监控)
数据分析(专利分析)
侵权分析(诉讼无效)
联系我们
交流群
官方交流:
QQ群: 891211   
微信请扫码    >>>
现在联系顾问~
热词
    • 3. 发明申请
    • OPTIMIZING COMPUTATION OF MINIMUM CUT IN GRAPHS WITH GRID TOPOLOGY
    • 最佳切割的优化计算与GRID拓扑学
    • US20130060724A1
    • 2013-03-07
    • US13226109
    • 2011-09-06
    • Ondrej JamriskaDaniel Sýkora
    • Ondrej JamriskaDaniel Sýkora
    • G06N5/02
    • G06N5/02
    • 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—a main 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 optimality of 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 that enables 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-flow computation systems to further improve their performance.
    • 公开了用于优化包括具有格子状拓扑的多个节点和边缘的图上的最小切割或最大流量计算的方法。 实施例利用输入图的常规结构来减少存储器带宽 - 基于在残差图上寻找增加路径(例如Ford-Fulkerson [1956]或Boykov-Kolmogorov]的流行的最大流/最小切割算法的主要瓶颈, 2004])。 公开的实施例允许超过200%的加速而不牺牲最终解决方案的最优性,这对于许多计算机视觉和图形应用至关重要。 方法和系统实施例用具有阻塞的存储器布局的一组紧凑数据结构来代替一般图表的标准链表,其使能边缘的固定排序和节点的隐式无分支寻址。 这些实施例与诸如并行处理或分层方法的其他优化正交,并且可以容易地插入到现有的最小切割/最大流量计算系统中以进一步提高其性能。