Scribble segmentation method and apparatus

Abstract

An apparatus and method of segmenting an image using scribble segmentation is provided. An image is segmented by constraining the membership value of a subset of image elements, solving a weighted biharmonic equation subject to the constrained membership values wherein the weights are determined from similarities between image elements, and determining the final segmentation based on the membership value of each image element. An image may also be segmented by constraining a membership value of a subset of image elements, determining the unknown membership values given the constraints by solving a linear equation system using a multigrid technique, and updating a coarser level of the multigrid hierarchy to account for additional constraints using patch matrices.

1 . A method of segmenting a digitized image, the method comprising:
 constraining a membership value u of a subset of image elements within the digitized image;   solving a weighted biharmonic equation, wherein the biharmonic equation is represented by the equation ∇ 4 u=0 and is subject to the constrained membership values and wherein the weights are determined from similarities between the image elements within the digitized image; and   determining the final segmentation based on the membership value of each image element.   
     
     
         2 . The method of  claim 1 , wherein the image elements are one of pixels or voxels. 
     
     
         3 . The method of  claim 1 , wherein the membership value constraints are derived from a subset of assigned inside, outside, and edge labels. 
     
     
         4 . The method of  claim 1 , wherein the biharmonic equation is solved using an algebraic multigrid technique. 
     
     
         5 . The method of  claim 4 , wherein the biharmonic equation is reformulated into the coupled problem represented by 
       
         
           
             
               
                 
                   ∇ 
                   4 
                 
                  
                 u 
               
               = 
               
                 0 
                 ⇔ 
                 
                   { 
                   
                     
                       
                         
                           
                             
                               ∇ 
                               2 
                             
                              
                             v 
                           
                           = 
                           0 
                         
                       
                     
                     
                       
                         
                           v 
                           = 
                           
                             
                               ∇ 
                               2 
                             
                              
                             u 
                           
                         
                       
                     
                   
                 
               
             
           
         
       
       and solved using multigrid. 
     
     
         6 . The method of  claim 5 , wherein the v-value of a labeled image element is estimated from the u-values. 
     
     
         7 . The method of  claim 4 , wherein the multigrid adapts a restrictor and an interpolator based upon the varying weights in the biharmonic equation. 
     
     
         8 . The method of  claim 4 , wherein the selection of a coarse node is based upon the varying weights in the biharmonic equation. 
     
     
         9 . The method of  claim 5 , wherein the relaxation in the multigrid solver performs collective relaxation of the u or v values corresponding to constrained image elements. 
     
     
         10 . A method of segmenting a digitized image, the method comprising:
 constraining a membership value u of a subset of image elements within the digitized image;   determining an unknown membership value given the constraints by solving a linear equation system, wherein the linear equation system is solved using a multigrid technique; and   updating a coarser level of the multigrid hierarchy to account for additional constraints using a patch matrix.   
     
     
         11 . The method of  claim 10 , wherein the constraints are derived from a subset of assigned inside, outside and edge labels. 
     
     
         12 . The method of  claim 11 , wherein the equation system is either a Laplace or biharmonic equation. 
     
     
         13 . The method of  claim 12 , wherein the equation system that incorporates the additional constraints is expressed as A h =A h   0 +ΔA h , wherein A h   0  is the equation system without the additional constraints, ΔA h  is the patch matrix, and the coarser level is obtained by the equation A 2h =A 2h   0 +I h   2h ΔA h I 2h   h , where I h   2h  is a multigrid restrictor and I 2h   h  is a multigrid interpolator. 
     
     
         14 . The method of  claim 11 , wherein the patch matrix accounts for new constraints resulting from a new scribble annotation. 
     
     
         15 . A system for segmenting a digitized image, the system comprising:
 a display;   a data storage module;   an user interface;   a processor, wherein the processor segments the digitized image by
 constraining a membership value u of a subset of image elements within the digitized image; 
 solving a weighted biharmonic equation represented by the equation ∇ 4 u=0, wherein the biharmonic equation is subject to the constrained membership values and wherein the weights are determined from similarities between the image elements within the digitized image; and 
 determining the final segmentation based on the membership value of each image element. 
   
     
     
         16 . A system for segmenting a digitized image, the system comprising:
 a display;   a data storage module;   an user interface;   a processor, wherein the processor segments the digitized image by
 constraining a membership value u of a subset of image elements within the digitized image; 
 determining an unknown membership value given the constraints by solving a linear equation system, wherein the linear equation system is solved using a multigrid technique; and 
 updating a coarser level of the multigrid hierarchy to account for additional constraints using a patch matrix. 
   
     
     
         17 . An article of manufacture having computer-readable program portions embodied thereon for segmenting a digitized image, the article comprising computer-readable instructions for segmenting the digitized image by
 constraining a membership value u of a subset of image elements within the digitized image;   solving a weighted biharmonic equation represented by the equation ∇ 4 u=0, wherein the biharmonic equation is subject to the constrained membership values and wherein the weights are determined from similarities between the image elements within the digitized image; and   determining the final segmentation based on the membership value of each image element.   
     
     
         18 . An article of manufacture having computer-readable program portions embodied thereon for segmenting a digitized image, the article comprising computer-readable instructions for segmenting the digitized image by
 constraining a membership value u of a subset of image elements within the digitized image;   determining an unknown membership value given the constraints by solving a linear equation system, wherein the linear equation system is solved using a multigrid technique; and   updating a coarser level of the multigrid hierarchy to account for additional constraints using a patch matrix.