Segmentation-based object categorization: Difference between revisions

Revision as of 23:33, 12 February 2014

Revision as of 19:26, 13 February 2014

Line 69:

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 ncut 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 computing and manipulating with or even computing the matrix W, as, e.g., in the [[Lanczos algorithm]]. [[Matrix-free methods]] require only thea function that performes a matrix-vector product for a given vector, on every iteration. For image segmentaion, 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.

==OBJ CUT==