Case ID: 30-020

Web Published: Mar 01, 2011

Intellectual Property Status: The software is copyright protected and is available for licensing both under GPL and under proprietary commercial licence via the UCLB online licensing portal: www.uclb-elicensing.com/optimisation_software/

Description:

Boykov / Kolmogorov MaxFlow Software

Available for: Non-exclusive licensing

Summary

This software implements the popular maxflow algorithm described by Boykov and Kolmogorov in the paper:

“An Experimental Comparison of Min-Cut/Max-Flow Algorithms for Energy Minimization in Computer Vision”, published in IEEE Transactions on Pattern Analysis and Machine Intelligence, September 2004. It is found to be particularly effective in computer vision applications.

The Technology and its Advantages

Minimum cut/maximum flow algorithms on graphs emerged as an increasingly useful tool for exact or approximate energy minimization in  low-level vision. The combinatorial optimization literature provides many min-cut/max-flow algorithms with different polynomial time complexity. Their practical efficiency, however, has to date been studied mainly outside the scope of computer vision. The goal of the referenced IEEE paper was to provide an experimental comparison of the efficiency of min-cut/max-flow algorithm for applications in vision, using several standard algorithm developed by the authors. In many case the Boykov / Kolmogorov algorithm worked several times faster than any other methods, making near real-time performance possible. Note that the experimental results reported in this IEEE paper are based on the original implementation of the algorithm as developed by the authors. The algorithm has since been fully re-coded.

Market Opportunity

This implementation of the MaxFlow/MinCut algorithms has been found to produce excellent results in a number of machine vision problems and has been licensed to a wide variety of commercial companies for integration into their software.

Further Information

Please contact Marina Santilli, Business Manager T: +44 (0)20 7679 9000 E: m.santilli@uclb.com

  • 0
    Bio
  • 0
    Eng
  • 0
    MeD
  • 0
    PhS