Segmentation-based object categorization: Difference between revisions

Revision as of 22:46, 5 June 2012

Revision as of 12:56, 11 December 2012

Line 21:

==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 <math>w_{ij}</math> of an edge <math>(i, j) \in E</math> is a function of the similarity between the nodes <math>i</math> and <math>j</math>. In this context, we can formulate the image segmentation problem as a graph partitioning problem that asks for a partition <math>V_1, \cdots, V_k</math> of the vertex set <math>V</math>, where, according to some measure, the vertices in any set <math>V_i</math> have high similarity, and the vertices in two different sets <math>V_i, V_j</math> have low similarity.

===Normalized cuts===

Line 35 ⟶ 36:

: <math>\operatorname{nassoc}(A, B) = \frac{w(A, A)}{w(A, V)} + \frac{w(B, B)}{w(B, V)}</math>

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

Since <math>\operatorname{ncut}(S, \overline{S}) = 2 - \operatorname{nassoc}(S, \overline{S})</math>, a cut <math>(S^{*}, {\overline{S}}^{*})</math> that minimizes <math>\operatorname{ncut}(S, \overline{S})</math> also maximizes <math>\operatorname{nassoc}(S, \overline{S})</math>.

Line 97 ⟶ 98:

==Other approaches==

* Jigsaw approach<ref> E. Borenstein, S. Ullman: Class-specic, top-down segmentation. In Proceedings of the 7th European Conference on Computer Vision, Copenhagen, Denmark, pages 109–124, 2002.</ref>

* Image parsing <ref>Z. Tu, X. Chen, A. L. Yuille, S. C. Zhu: Image Parsing: Unifying Segmentation, Detection, and Recognition. Toward Category-Level Object Recognition 2006: 545–576</ref>

* Interleaved segmentation <ref>B. Leibe, A. Leonardis, B. Schiele: An Implicit Shape Model for Combined Object Categorization and Segmentation. Toward Category-Level Object Recognition 2006: 508–524</ref>

* LOCUS <ref> J. Winn, N. Joijic. Locus: Learning object classes with unsupervised segmentation. In Proceedings of the IEEE International Conference on Computer Vision, Beijing, 2005.</ref>

* LayoutCRF <ref>J. M. Winn, J. Shotton: The Layout Consistent Random Field for Recognizing and Segmenting Partially Occluded Objects. CVPR (1) 2006: 37–44</ref>

* [[Minimum spanning tree-based segmentation]]