Patent ID: 7889924

Claim:
A method of segmenting a rectilinear object in an image forming a graph based on cuts of the object in the image, the method comprising: (a) obtaining the image; (b) calculating edge weights in accordance with w ij = { 1 2 , if ⁢ ⁢ nodes ⁢ ⁢ v i ⁢ ⁢ and ⁢ ⁢ v j ⁢ ⁢ are ⁢ ⁢ adjacent ⁢ ⁢ in ⁢ ⁢ the ⁢ ⁢ grid , 0 , Otherwise } , on a four-connected grid for L 1 and, for L 2 , connect each node to every node within a radius of four pixels with edge weights equal to w i = δ 2 ⁢ Δ ⁢ ⁢ ϕ k 2 ⁢  e i  , ⁢ for ⁢ ⁢ e i ∈ E k , where δ is grid spacing, Δφ k is the angle between two edges in E k , E k ⊂ E indicates the edge family incident on node v k , i and j represent pixels in the image, and |e i | is the magnitude of this edge's direction; (c) approximating a ratio of perimeter metrics arg ⁢ ⁢ min x ⁢ x T ⁢ L 1 ⁢ x x T ⁢ L 2 ⁢ x , subject to [x ε{0,1} N ], where N is the size of the graph, for the object by constructing Laplacian matrices L 1 and L 2 for the image; (d) relaxing an integer constraint on the ratio of perimeter metrics, resulting in a generalized eigenvector problem; (e) solving the generalized eigenvector problem; and (f) finding a binary segmentation from the eigenvector solution by thresholding the eigenvector to produce a binary indicator vector that minimizes said ratio of perimeter metrics, wherein said step of approximating the ratio of perimeter metrics includes modulating each edge weight of L 2 -graph.