Segmentation-based object categorization

• Image compression
• Segment the image into homogeneous components, and use the most suitable compression algorithm for each component to improve compression.
• Medical diagnosis
• Automatic segmentation of MRI images for identification of cancerous regions.
• Mapping and measurement
• Automatic analysis of remote sensing data from satellites to identify and measure regions of interest.
• Transportation
• Partition a transportation network makes it possible to identify regions characterized by homogeneous traffic states.{{Cite journal|last1=Lopez|first1=Clélia|last2=Leclercq|first2=Ludovic|last3=Krishnakumari|first3=Panchamy|last4=Chiabaut|first4=Nicolas|last5=Van Lint|first5=Hans|date=25 October 2017|title=Revealing the day-to-day regularity of urban congestion patterns with 3D speed maps|journal=Scientific Reports|volume=7 |issue=14029|pages=14029|doi=10.1038/s41598-017-14237-8|pmid=29070859|pmc=5656590|bibcode=2017NatSR...714029L }}

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 $w\_\{ij\}$ of an edge $(i,\; j)\; \backslash in\; E$ is a function of the similarity between the nodes $i$ and $j$. In this context, we can formulate the image segmentation problem as a graph partitioning problem that asks for a partition $V\_1,\; \backslash cdots,\; V\_k$ of the vertex set $V$, where, according to some measure, the vertices in any set $V\_i$ have high similarity, and the vertices in two different sets $V\_i,\; V\_j$ have low similarity.

Let G = (V, E, w) be a weighted graph. Let $A$ and $B$ be two subsets of vertices.

Let:

: $w(A,\; B)\; =\; \backslash sum\; \backslash limits\_\{i\; \backslash in\; A,\; j\; \backslash in\; B\}\; w\_\{ij\}$

: $\backslash operatorname\{ncut\}(A,\; B)\; =\; \backslash frac\{w(A,\; B)\}\{w(A,\; V)\}\; +\; \backslash frac\{w(A,\; B)\}\{w(B,\; V)\}$

: $\backslash operatorname\{nassoc\}(A,\; B)\; =\; \backslash frac\{w(A,\; A)\}\{w(A,\; V)\}\; +\; \backslash frac\{w(B,\; B)\}\{w(B,\; V)\}$

In the normalized cuts approach,Jianbo Shi and Jitendra Malik (1997): "Normalized Cuts and Image Segmentation", IEEE Conference on Computer Vision and Pattern Recognition, pp 731–737 for any cut $(S,\; \backslash overline\{S\})$ in $G$, $\backslash operatorname\{ncut\}(S,\; \backslash overline\{S\})$ measures the similarity between different parts, and $\backslash operatorname\{nassoc\}(S,\; \backslash overline\{S\})$ measures the total similarity of vertices in the same part.

Since $\backslash operatorname\{ncut\}(S,\; \backslash overline\{S\})\; =\; 2\; -\; \backslash operatorname\{nassoc\}(S,\; \backslash overline\{S\})$, a cut $(S^\{*\},\; \{\backslash overline\{S\}\}^\{*\})$ that minimizes $\backslash operatorname\{ncut\}(S,\; \backslash overline\{S\})$ also maximizes $\backslash operatorname\{nassoc\}(S,\; \backslash overline\{S\})$.

Computing a cut $(S^\{*\},\; \{\backslash overline\{S\}\}^\{*\})$ that minimizes $\backslash operatorname\{ncut\}(S,\; \backslash overline\{S\})$ is an NP-hard problem. However, we can find in polynomial time a cut $(S,\; \backslash overline\{S\})$ of small normalized weight $\backslash operatorname\{ncut\}(S,\; \backslash overline\{S\})$ using spectral techniques.

Let:

: $d(i)\; =\; \backslash sum\; \backslash limits\_j\; w\_\{ij\}$

Also, let D be an $n\; \backslash times\; n$ diagonal matrix with $d$ on the diagonal, and let $W$ be an $n\; \backslash times\; n$ symmetric matrix with $w\_\{ij\}\; =\; w\_\{ji\}$.

After some algebraic manipulations, we get:

: $\backslash min\; \backslash limits\_\{(S,\; \backslash overline\{S\})\}\; \backslash operatorname\{ncut\}(S,\; \backslash overline\{S\})\; =\; \backslash min\; \backslash limits\_y\; \backslash frac\{y^T\; (D\; -\; W)\; y\}\{y^T\; D\; y\}$

subject to the constraints:

• $y\_i\; \backslash in\; \backslash \{1,\; -b\; \backslash \}$, for some constant $-b$
• $y^t\; D\; 1\; =\; 0$

Minimizing $\backslash frac\{y^T\; (D\; -\; W)\; y\}\{y^T\; D\; y\}$ subject to the constraints above is NP-hard. To make the problem tractable, we relax the constraints on $y$, and allow it to take real values. The relaxed problem can be solved by solving the generalized eigenvalue problem $(D\; -\; W)y\; =\; \backslash lambda\; D\; y$ for the second smallest generalized eigenvalue.

The partitioning algorithm:

1. Given a set of features, set up a weighted graph $G\; =\; (V,\; E)$, compute the weight of each edge, and summarize the information in $D$ and $W$.
2. Solve $(D\; -\; W)y\; =\; \backslash lambda\; D\; y$ for eigenvectors with the second smallest eigenvalues.
3. Use the eigenvector with the second smallest eigenvalue to bipartition the graph (e.g. grouping according to sign).
4. Decide if the current partition should be subdivided.
5. Recursively partition the segmented parts, if necessary.

Solving a standard eigenvalue problem for all eigenvectors (using the QR algorithm, for instance) takes $O(n^3)$ time. This is impractical for image segmentation applications where $n$ 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 $O(n)$, so such a matrix-vector product takes $O(n)$ 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 $O(n)$ time, which is the optimal complexity, since the eigenvector has $n$ components.

scikit-learn{{Cite web|url=https://scikit-learn.org/stable/modules/clustering.html#spectral-clustering|title=Spectral Clustering — scikit-learn documentation}} uses LOBPCG from SciPy with algebraic multigrid preconditioning for solving the eigenvalue problem for the graph Laplacian to perform image segmentation via spectral graph partitioning as first proposed in {{Cite conference | url = https://www.researchgate.net/publication/343531874 | title = Modern preconditioned eigensolvers for spectral image segmentation and graph bisection | conference = Clustering Large Data Sets; Third IEEE International Conference on Data Mining (ICDM 2003) Melbourne, Florida: IEEE Computer Society| editor = Boley| editor2 = Dhillon| editor3 = Ghosh| editor4 = Kogan | pages = 59–62| year = 2003| last1 = Knyazev| first1 = Andrew V.}} and actually tested in {{Cite conference | url = https://www.researchgate.net/publication/354448354 | title = Multiscale Spectral Image Segmentation Multiscale preconditioning for computing eigenvalues of graph Laplacians in image segmentation | conference = Fast Manifold Learning Workshop, WM Williamburg, VA| year = 2006| last1 = Knyazev| first1 = Andrew V. | doi=10.13140/RG.2.2.35280.02565}} and.{{Cite conference | url = https://www.researchgate.net/publication/343531874 | title = Multiscale Spectral Graph Partitioning and Image Segmentation | conference = Workshop on Algorithms for Modern Massive Datasets Stanford University and Yahoo! Research| year = 2006| last1 = Knyazev| first1 = Andrew V.}}

OBJ CUTM. P. Kumar, P. H. S. Torr, and A. Zisserman. Obj cut. In Proceedings of IEEE Conference on Computer Vision and Pattern Recognition, San Diego, pages 18–25, 2005. 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 $\backslash Theta$ be a shape parameter($\backslash Theta$ is a shape prior on the labels from a layered pictorial structure (LPS) model). An energy function $E(m,\; \backslash Theta)$ is defined as follows.

: $E(m,\; \backslash Theta)\; =\; \backslash sum\; \backslash phi\_x(D|m\_x)\; +\; \backslash phi\_x(m\_x|\backslash Theta)\; +\; \backslash sum\; \backslash Psi\_\{xy\}(m\_x,\; m\_y)\; +\; \backslash phi(D|m\_x,\; m\_y)$ (1)

The term $\backslash phi\_x(D|m\_x)\; +\; \backslash phi\_x(m\_x|\backslash Theta)$ is called a unary term, and the term $\backslash Psi\_\{xy\}(m\_x,\; m\_y)\; +\; \backslash phi(D|m\_x,\; m\_y)$ is called a pairwise term.

A unary term consists of the likelihood $\backslash phi\_x(D|m\_x)$ based on color, and the unary potential $\backslash phi\_x(m\_x|\backslash Theta)$ based on the distance from $\backslash Theta$. A pairwise term consists of a prior $\backslash Psi\_\{xy\}(m\_x,\; m\_y)$ and a contrast term $\backslash phi(D|m\_x,\; m\_y)$.

The best labeling $m^\{*\}$ minimizes $\backslash sum\; \backslash limits\_i\; w\_i\; E(m,\; \backslash Theta\_i)$, where $w\_i$ is the weight of the parameter $\backslash Theta\_i$.

: $m^\{*\}\; =\; \backslash arg\; \backslash min\; \backslash limits\_m\; \backslash sum\; \backslash limits\_i\; w\_i\; E(m,\; \backslash Theta\_i)$ (2)

1. Given an image D, an object category is chosen, e.g. cows or horses.
2. The corresponding LPS model is matched to D to obtain the samples $\backslash Theta\_1,\; \backslash cdots,\; \backslash Theta\_s$
3. The objective function given by equation (2) is determined by computing $E(m,\; \backslash Theta\_i)$ and using $w\_i\; =\; g(\backslash Theta\_i|Z)$
4. The objective function is minimized using a single MINCUT operation to obtain the segmentation m.

• Jigsaw approachE. Borenstein, S. Ullman: [http://www.csd.uwo.ca/~olga/Courses/Fall2007/840/StudentPapers/BorensteinUllman2002.pdf Class-specific, top-down segmentation]. In Proceedings of the 7th European Conference on Computer Vision, Copenhagen, Denmark, pages 109–124, 2002.
• Image parsing Z. Tu, X. Chen, A. L. Yuille, S. C. Zhu: [https://cloudfront.escholarship.org/dist/prd/content/qt8n57f107/qt8n57f107.pdf Image Parsing: Unifying Segmentation, Detection, and Recognition]. Toward Category-Level Object Recognition 2006: 545–576
• Interleaved segmentation B. Leibe, A. Leonardis, B. Schiele: [http://www.vision.ee.ethz.ch/en/publications/papers/bookchapters/eth_biwi_00421.pdf An Implicit Shape Model for Combined Object Categorization and Segmentation]. Toward Category-Level Object Recognition 2006: 508–524
• LOCUS J. Winn, N. Joijic. [http://people.eecs.berkeley.edu/~efros/courses/AP06/Papers/winn-iccv-05.pdf Locus: Learning object classes with unsupervised segmentation]. In Proceedings of the IEEE International Conference on Computer Vision, Beijing, 2005.
• LayoutCRF J. M. Winn, J. Shotton: [http://www.wisdom.weizmann.ac.il/~/vision/courses/2007_2/files/LCRF.pdf The Layout Consistent Random Field for Recognizing and Segmenting Partially Occluded Objects]. CVPR (1) 2006: 37–44
• Minimum spanning tree-based segmentation

{{reflist|32em}}

Category:Object recognition and categorization

Category:Image segmentation