Segmentation-based object categorization

The image segmentation problem is concerned with partitioning an image into multiple regions according to some homogeneity criterion. This article is primarily concerned with graph theoretic approaches to image segmentation applying graph partitioning via minimum cut or maximum cut. Segmentation-based object categorization can be viewed as a specific case of spectral clustering applied to image segmentation. 
Segmentation using normalized cuts.
Graph theoretic formulation.
The set of points in an arbitrary feature space can be represented as a weighted undirected complete graph G = (V, E), where the nodes of the graph are the points in the feature space. The weight formula_1 of an edge formula_2 is a function of the similarity between the nodes formula_3 and formula_4. In this context, we can formulate the image segmentation problem as a graph partitioning problem that asks for a partition formula_5 of the vertex set formula_6, where, according to some measure, the vertices in any set formula_7 have high similarity, and the vertices in two different sets formula_8 have low similarity.
Normalized cuts.
Let "G" = ("V", "E", "w") be a weighted graph. Let formula_9 and formula_10 be two subsets of vertices.
Let:
In the normalized cuts approach, for any cut formula_14 in formula_15, formula_16 measures the similarity between different parts, and formula_17 measures the total similarity of vertices in the same part.
Since formula_18, a cut formula_19 that minimizes formula_16 also maximizes formula_17.
Computing a cut formula_19 that minimizes formula_16 is an NP-hard problem. However, we can find in polynomial time a cut formula_14 of small normalized weight formula_16 using spectral techniques.
The ncut algorithm.
Let:
Also, let "D" be an formula_27 diagonal matrix with formula_28 on the diagonal, and let formula_29 be an formula_27 symmetric matrix with formula_31.
After some algebraic manipulations, we get:
subject to the constraints:
Minimizing formula_36 subject to the constraints above is NP-hard. To make the problem tractable, we relax the constraints on formula_37, and allow it to take real values. The relaxed problem can be solved by solving the generalized eigenvalue problem formula_38 for the second smallest generalized eigenvalue.
The partitioning algorithm:
Computational Complexity.
Solving a standard eigenvalue problem for all eigenvectors (using the QR algorithm, for instance) takes formula_43 time. This is impractical for image segmentation applications where formula_44 is the number of pixels in the image.
Since only one eigenvector, corresponding to the second smallest generalized eigenvalue, is used by the uncut algorithm, efficiency can be dramatically improved if the solve of the corresponding eigenvalue problem is performed in a matrix-free fashion, i.e., without explicitly manipulating with or even computing the matrix W, as, e.g., in the Lanczos algorithm. Matrix-free methods require only a function that performs a matrix-vector product for a given vector, on every iteration. For image segmentation, the matrix W is typically sparse, with a number of nonzero entries formula_45, so such a matrix-vector product takes formula_45 time.
For high-resolution images, the second eigenvalue is often ill-conditioned, leading to slow convergence of iterative eigenvalue solvers, such as the Lanczos algorithm. Preconditioning is a key technology accelerating the convergence, e.g., in the matrix-free LOBPCG method. Computing the eigenvector using an optimally preconditioned matrix-free method takes formula_45 time, which is the optimal complexity, since the eigenvector has formula_44 components.
OBJ CUT.
OBJ CUT is an efficient method that automatically segments an object. The OBJ CUT method is a generic method, and therefore it is applicable to any object category model.
Given an image D containing an instance of a known object category, e.g. cows, the OBJ CUT algorithm computes a segmentation of the object, that is, it infers a set of labels "m".
Let m be a set of binary labels, and let formula_49 be a shape parameter(formula_49 is a shape prior on the labels from a layered pictorial structure (LPS) model). An energy function formula_51 is defined as follows.
The term formula_53 is called a unary term, and the term formula_54 is called a pairwise term.
A unary term consists of the likelihood formula_55 based on color, and the unary potential formula_56 based on the distance from formula_49. A pairwise term consists of a prior formula_58 and a contrast term formula_59.
The best labeling formula_60 minimizes formula_61, where formula_62 is the weight of the parameter formula_63.