Image Processing and Analysis with Graphs

2

Graph Cuts—Combinatorial Optimization in Vision

Hiroshi Ishikawa

Department of Computer Science and EngineeringWaseda UniversityTokyo, Japan

Email: [e-mail]

CONTENTS

2.1    Introduction

2.1.1    Chapter Summary

2.2    Markov Random Field

2.2.1    Labeling Problem: A Simple Example

2.2.1.1    Denoising Problem

2.2.1.2    Image Similarity

2.2.1.3    Denoising Criterion

2.2.2    Markov Random Field

2.2.2.1    Order of an MRF

2.2.2.2    Energy of an MRF

2.2.2.3    Bayesian Inference

2.3    Basic Graph Cuts: Binary Labels

2.3.1    Minimum-Cut Algorithms

2.3.2    The Graph Cuts

2.3.3    Submodularity

2.3.4    Nonsubmodular Case: The BHS Algorithm

2.3.5    Reduction of Higher-Order Energies

2.4    Multi-Label Minimization

2.4.1    Globally ...