Segmentation-based object categorization: Difference between revisions

Revision as of 11:09, 12 March 2017

Latest revision as of 16:03, 8 January 2024

(13 intermediate revisions by 11 users not shown)

Line 1:

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.

<!-- Unsourced image removed: [[Image:aenep11.png|right|thumb|Figure 1: Input image.]] -->

<!-- Unsourced image removed: [[Image:aenep12.png|right|thumb|Figure 2: First partition.]] -->

Line 18:

** 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.<ref>{{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 }}</ref>

==Segmentation using normalized cuts==

Line 61 ⟶ 63:

'''The partitioning algorithm:'''

# Given a set of features, set up a weighted graph <math>G = (V, E)</math>, compute the weight of each edge, and summarize the information in <math>D</math> and <math>W</math>.

# Solve <math>(D - W)y = \lambda D y</math> for eigenvectors with the second smallest eigenvalues.

# Use the eigenvector with the second smallest eigenvalue to bipartition the graph (e.g. grouping according to sign).

# Decide if the current partition should be subdivided.

Line 69 ⟶ 71:

Solving a standard eigenvalue problem for all eigenvectors (using the [[QR algorithm]], for instance) takes <math>O(n^3)</math> time. This is impractical for image segmentation applications where <math>n</math> is the number of pixels in the image.

Since only one eigenvector, corresponding to the second smallest generalized eigenvalue, is used by the ncutuncut algorithm, efficiency can be dramatically improved if the solve of the corresponding eigenvalue problem is performed in a [[Matrix-free methods|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 <math>O(n)</math>, so such a matrix-vector product takes <math>O(n)</math> 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]]. [[Preconditioner#Preconditioning for eigenvalue problems|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 <math>O(n)</math> time, which is the optimal complexity, since the eigenvector has <math>n</math> components.

===Software Implementations===

[[scikit-learn]]<ref>{{Cite web|url=https://scikit-learn.org/stable/modules/clustering.html#spectral-clustering|title=Spectral Clustering — scikit-learn documentation}}</ref> uses [[LOBPCG]] from [[SciPy]] with [[Multigrid method#Algebraic multigrid (AMG)|algebraic multigrid preconditioning]] for solving the [[eigenvalue]] problem for the [[graph Laplacian]] to perform [[image segmentation]] via spectral [[graph partitioning]] as first proposed in <ref>{{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.}}</ref> and actually tested in <ref>{{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}}</ref> and.<ref>{{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.}}</ref>

==OBJ CUT==

Line 96 ⟶ 101:

==Other approaches==

* Jigsaw approach<ref>E. Borenstein, S. Ullman: [http://www.csd.uwo.ca/~olga/Courses/Fall2007/840/StudentPapers/BorensteinUllman2002.pdf Class-specicspecific, 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: [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</ref>

* Interleaved segmentation <ref>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</ref>

* LOCUS <ref>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.</ref>

* LayoutCRF <ref>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</ref>

* [[Minimum spanning tree-based segmentation]]

==References==

{{reflist|32em}}

[[Category:Object recognition and categorization]]