Normalized Cuts has successfully been applied to a wide range of tasks in computer vision, it is indisputably one of the most popular segmentation algorithms in use today. A number of extensions to this approach have also been proposed, ones that can deal with multiple classes or that can incorporate a priori information in the form of grouping constraints. It was recently shown how a general linearly constrained Normalized Cut problem can be solved. This was done by proving that strong duality holds for the Lagrangian relaxation of such problems. This provides a principled way to perform multi-class partitioning while enforcing any linear constraints exactly.

    The Lagrangian relaxation requires the maximization of the algebraically smallest eigenvalue over a one-dimensional matrix sub-space. This is an unconstrained, piece-wise differentiable and concave problem. In this paper we show how to solve this optimization efficiently even for very large-scale problems. The method has been tested on real data with convincing results.


    Access

    Check access

    Check availability in my library

    Order at Subito €


    Export, share and cite



    Title :

    Efficiently Solving the Fractional Trust Region Problem


    Contributors:

    Conference:

    Asian Conference on Computer Vision ; 2007 ; Tokyo, Japan November 18, 2007 - November 22, 2007


    Published in:

    Computer Vision – ACCV 2007 ; Chapter : 78 ; 796-805


    Publication date :

    2007-01-01


    Size :

    10 pages





    Type of media :

    Article/Chapter (Book)


    Type of material :

    Electronic Resource


    Language :

    English




    Solving the Infeasible Trust-Region Problem Using Approximations

    Perez, Victor / Eldred, Michael / Renaud, John | AIAA | 2004





    Problem Solving

    Lapesa Barrera, David | Springer Verlag | 2022