Part of becoming familiar with a new field is figuring out who the major figures are, and their relationships. This page is intended to save you some time in getting oriented; after that, I expect you'll form your own opinions and most likely disagree with mine. Thass cool.

Apologies to everyone left out — what can I say, I'm a lazy bum.

**Robert Tarjan**: It isn't really fair to compare mere mortal
computer vision researchers with Robert Tarjan; he's one of the
all-time computer science theory greats, who walks with the gods,
revolutionizes entire fields before breakfast, and occasionally drops
by to do the same for computer vision, probably while actually eating
breakfast.

Tarjan is **The Hacker's Friend** because whereas other great
theoreticians tend to spend their time proving that given problems are
undecidable or such, which is interesting but doesn't help one ship
code by dawn, Tarjan particularly delights in finding algorithms for
practically important problems which run in linear time, or
near-linear time. Consequently, it is hard to write a significant
application without using a Tarjan algorithm — and I cannot
imagine why anyone would try. When a new Tarjan paper comes out, you
should cancel your appointments, lock the door, unplug the phone, and
settle down for another real treat.

For additional general background on Tarjan see his Wikipedia entry.

Tarjan papers of specific relevance to computer vision include:

- Babe07: Experimental Evaluation of Parametric Max-Flow Algorithms
- Gold88: A New Approach to the Maximum-Flow Problem
- Fred87: Fibonacci heaps and their uses in improved network optimization algorithms
- Slea83: A data structure for dynamic trees

Tarjan's mortal manifestation has a home page here.

There are probably dozens of pages like this honoring him.

**Vladimir Kolmogorov** and **Yuri Boykov** are the
*enfants terrible* of the breakthrough 1998-2008
period in computer vision, together being author or co-author
on perhaps two-thirds of the the core ground-breaking papers
of the period. Any paper with either of their names on it
deserves careful reading; when they write a paper together
you should unplug the phone, make tea, and settle down in an
easy chair.

Kolmogorov got his degree in computer vision in 2003 -- see his dissertation.

Computer vision isn't even Boykov's primary field -- Olga Veksler mentions in her dissertation that she dragged him into the field.

NB:Try not confuse Vladimir Kolmogorov with Andrey Kolmogorov, born in 1903 and famed for such foundational work as Kolmogorov Complexity.

Papers they are co-authors on include:

- Kolm07: Applications of parametric maxflow in computer vision
- Boyk06: An Integral Solution to Surface Evolution PDEs via Geo-Cuts
- Boyk03: Computing geodesics and minimal surfaces via graph cuts
- Boyk02: An Experimental Comparison of Min-Cut/Max-Flow Algorithms for Energy Minimization in Vision

Other papers Boykov is author or co-author on include:

- Juan07: Capacity Scaling for Graph Cuts in Vision
- Lemp07: Global Optimization for Shape Fitting
- Boyk06b: From Photohulls to Photoflux Optimization
- Boyk06b: From Photohulls to Photoflux Optimization
- Juan06: Active Graph Cuts
- Lemp06: Oriented visibility for multiview reconstruction
- Boyk04: Optimal Object Extraction via Constrained Graph-Cuts
- Boyk01: Interactive Graph Cuts for Optimal Boundary & Region Segmentation of Objects in NDImages
- Boyk01b: A New Algorithm for Energy Minimization with Discontinuities
- Boyk99: Fast Approximate Energy Minimization via Graph Cuts
- Boyk99b: A New Bayesian Framework for Object Recognition
- Boyk98: Markov Random Fields with Efficient Approximations
- Boyk98b: A Variable Window Approach to Early Vision

Boykov has a home page here.

Other papers Kolmogorov is author or co-author on include:

- Kohl08b: On Partial Optimality in Multilabel MRFs.
- Kuma07: An Analysis of Convex Relaxations for MAP Estimation
- Roth07: Optimizing Binary MRFs via Extended Roof Duality
- Kolm06: Comparison of energy minimization algorithms for highly connected graphs
- Kolm06b: Minimizing Nonsubmodular Functions with Graph Cuts -- A Review
- Roth06: Cosegmentation of Image Pairs by Histogram Matching -- Incorporating a Global Constraint into MRFs
- Kolm05: Probabilistic fusion of stereo with color and contrast for bi-layer segmentation
- Kolm05b: Convergent Tree-Reweighted Message Passing for Energy Minimization
- Kolm05c: What Metrics Can Be Approximated by Geo-Cuts, or Global Optimization of Length/Area and Flux
- Kolm05d: Kolm05d: On the optimality of tree-reweighted max-product message passing
- Kolm05e: Bi-layer segmentation of binocular stereo video
- Kolm05f: Primal-dual Algorithm for Convex Markov Random Fields:
*"for the panoramic stitching problem our method outperforms other techniques"* - Kolm05g: Graph Cut Algorithms for Binocular Stereo with Occlusions
- Roth05: Digital Tapestry: Extending expansion move with non-metric hard and soft constraints.
- Kolm04: What Energy Functions Can Be Minimized via Graph Cuts?
- Zabi04: Spatially coherent clustering using graph cuts:
*"operates simultaneously in feature and image space"* - Kolm03: Graph based algorithms for scene reconstruction from two or more views (
**dissertation**) - Kolm03b: Generalized multi-camera scene reconstruction using graph cuts
- Kolm02: Multi-camera Scene Reconstruction via Graph Cuts
- Kolm01: Computing Visual Correspondence with Occlusions via Graph Cuts

Kolmogorov has a home page here.

**Pushmeet Kohli** is a recent arrival who already has his name on
a great string of papers including his 2007
dissertation:

- Alah08: Reduce, Reuse & Recycle: Efficiently Solving Multilabel MRFs.
- Kohl08: Robust Higher Order Potentials for Enforcing Label Consistency.
- Khol08a: Graph cuts for minimizing robust higher order potentials.
- Kohl08b: On Partial Optimality in Multilabel MRFs.
- Rama08: Exact Inference in Multi-label CRFs with Higher Order Cliques
- Rava08: Unwrap Mosaics: A new representation for video editing
- Kohl07: P3 & Beyond: Solving Energies with Higher Order Cliques
- Kohl07b: Dynamic Graph Cuts for Efficient Inference in Markov Random Fields
- Kohl07c: Minimizing Dynamic and Higher Order Energy Functions using Graph Cuts (
**dissertation**) - Bray06: PoseCut: Simultaneous Segmentation and 3D Pose Estimation of Humans using Dynamic Graph-Cuts.
- Kohl06: Measuring Uncertainty in Graph Cut Solutions
- Riha06: OBJCUT for face detection
- Sun06: Using Strong Shape Priors for Stereo
- Kohl05: Efficiently Solving Dynamic Markov Random Fields Using Graph Cuts

Kohli has a homepage here.

**Andrew Delong** hasn't even completed his dissertation, yet
has already cranked out great stuff, co-authored with the
likes of Boykov and Kolmogorov no less! He seems to have an
indecent amount of fun in the process -- I'm jealous.
I'm also a bit impatient to read his dissertation and his computer
vision library. :-)

Papers already graced by his name include:

- Delo08: A Scalable Graph-Cut Algorithm for N-D Grids.
- Boyk06: An Integral Solution to Surface Evolution PDEs via Geo-Cuts

Delong has a home page here.

Back to Cynbe's Computer Vision Papers by Topic.

Cynbe ru Taren Last modified: Fri Jul 11 23:52:29 CDT 2008