Abstract:
A method exploits user labels in image segmentation. The user labels are propagated with respect to image intensity information. Propagated user labels are included in a cost function of level set evolution. The level set represents a probability of the object segment.

Description:
FIELD OF THE INVENTION 
     This invention relates generally to image processing, and more particularly to image segmentation. 
     BACKGROUND OF THE INVENTION 
     Conventional image processing can use a level set and user information to segment an image, e.g., see U.S. Pat. No. 7,277,582, “User interactive level set methods for image segmentation.” The level set is evolved to minimize a cost function, wherein variances of image intensities object pixels and background pixels are used in cost function. The user can label pixels as object or background pixels and penalize deviations of the sign of the evolving level set from the sign of the user-labeled pixels, and nearby pixels with an isotropic weighting, i.e., the weighting is uniform in all directions. 
     However, conventionally, the user labels do not incorporate image intensity information. The variance terms in the level set evolution dominate and only pixels near user selected background locations remain as background. 
       FIG. 1  shows an image that has a failure of the segmentation with conventional user interaction. The correct segmentation shown in  FIG. 2  is difficult to achieve. 
     It is an object of the invention to produce a segmentation that approximated the correct segmentation. 
     SUMMARY OF THE INVENTION 
     The embodiments of the invention provide a method for segmenting an input image using level sets and user labels. The method propagates the labels based on image intensity information, and combines the information with a probabilistic level set representation. The method improves increases accuracy, while reducing processing time. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         FIG. 1  is an image of a failed segmentation with conventional methods; 
         FIG. 2  is the correct segmentation for the image in  FIG. 1 ; 
         FIG. 3  is a block diagram of a method for segmenting an image according to embodiments of the invention; 
         FIG. 4  is an image with labeled pixels according to embodiments of the invention; and 
         FIG. 5  is a schematic of an image grid graph according to embodiments of the invention; and 
         FIG. 6  is an image of a segment according to embodiments of the invention. 
     
    
    
     DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS 
       FIG. 3  shows a method  300  for segmenting an input image  301  according to embodiments of our invention to produces a segment  309  in an output image  309 , see  FIG. 6 . The steps of the method can be performed in a processor including memory and input/output interfaces connected by a bus as known in the art. 
     A user supplies a set of labels  310 . The set of labels identifies object pixels  311  and background pixels  312 , see  FIG. 4 . The labels are propagated  310  to produce an initial level set  303 . Then, the level set is evolved, using a cost function J described in detail below, to produce a segment  309  in and output image. 
     The level set represents the segmentation of the input image in a spatial domain with functions Ω 1 , Ω 2  and C, where
 
Ω 1 ={( x,y ): ƒ( x,y )&gt;0},
 
Ω 2 ={( x,y ): ƒ( x,y )&lt;0},
 
 C ={( x,y ): ƒ( x,y )=0},
 
where the function Ω 1  identifies a background region of the object pixels, the function Ω 2  identifies a background region of the background pixels, and the function C identifies boundary pixels between the object and the background regions, and (x, y) are coordinates of locations of the pixels in the input image.
 
     A region-based level set cost function J o  of the cost function J is 
     
       
         
           
             
               
                 
                   
                     
                       J 
                       0 
                     
                     = 
                     
                       
                         ∑ 
                         
                           i 
                           = 
                           1 
                         
                         2 
                       
                       ⁢ 
                       
                         
                           ∫ 
                           Ω 
                         
                         ⁢ 
                         
                           
                             
                               ( 
                               
                                 
                                   u 
                                   ⁡ 
                                   
                                     ( 
                                     
                                       x 
                                       , 
                                       y 
                                     
                                     ) 
                                   
                                 
                                 - 
                                 
                                   
                                     u 
                                     _ 
                                   
                                   i 
                                 
                               
                               ) 
                             
                             2 
                           
                           ⁢ 
                           
                             
                               χ 
                               i 
                             
                             ⁡ 
                             
                               ( 
                               
                                 f 
                                 ⁡ 
                                 
                                   ( 
                                   
                                     x 
                                     , 
                                     y 
                                   
                                   ) 
                                 
                               
                               ) 
                             
                           
                           ⁢ 
                           
                             ⅆ 
                             x 
                           
                           ⁢ 
                           
                             ⅆ 
                             y 
                           
                         
                       
                     
                   
                   , 
                 
               
               
                 
                   ( 
                   4 
                   ) 
                 
               
             
           
         
       
     
     where u is an intensity of the pixel at image location (x, y), and 
                         u   _     i     =         ∫   Ω     ⁢       u   ⁡     (     x   ,   y     )       ⁢     χ   i     ⁢           ⁢     (     f   ⁡     (     x   ,   y     )       )     ⁢     ⅆ   x     ⁢     ⅆ   y             ∫   Ω     ⁢         χ   i     ⁡     (     f   ⁡     (     x   ,   y     )       )       ⁢     ⅆ   x     ⁢     ⅆ   y             ,           (   5   )               
are means of the pixel intensities of each region, and
 
                         χ   1     ⁡     (   z   )       =     H   ⁡     (   z   )         ,         χ   2     ⁡     (   z   )       =     1   -     H   ⁡     (   z   )           ,     
     ⁢   where           (   6   )                 H   ⁡     (   z   )       =     {         0           if   ⁢           ⁢   z     &lt;   0             1             if   ⁢           ⁢   z     ≥   0     ,                     (   7   )               
is a Heaviside step function. The Heaviside step function H, also called a unit step function, is a discontinuous function whose value is zero for negative argument, and one for positive arguments.
 
     Our cost function J also includes a user label cost function J U  and a maximum belief cost function J B  as described below. 
     The set of user labels is encoded using a function 
     
       
         
           
             
               
                 
                   
                     L 
                     ⁢ 
                     
                       ( 
                       
                         x 
                         , 
                         y 
                       
                       ) 
                     
                   
                   = 
                   
                     { 
                     
                       
                         
                           1 
                         
                         
                           
                             
                               
                                 
                                   if 
                                   ⁢ 
                                   
                                       
                                   
                                   ⁢ 
                                   the 
                                   ⁢ 
                                   
                                       
                                   
                                   ⁢ 
                                   pixel 
                                   ⁢ 
                                   
                                       
                                   
                                   ⁢ 
                                   at 
                                   ⁢ 
                                   
                                       
                                   
                                   ⁢ 
                                   the 
                                   ⁢ 
                                   
                                       
                                   
                                   ⁢ 
                                   location 
                                   ⁢ 
                                   
                                       
                                   
                                   ⁢ 
                                   
                                     ( 
                                     
                                       x 
                                       , 
                                       y 
                                     
                                     ) 
                                   
                                 
                               
                             
                             
                               
                                 
                                   
                                     is 
                                     ⁢ 
                                     
                                         
                                     
                                     ⁢ 
                                     one 
                                     ⁢ 
                                     
                                         
                                     
                                     ⁢ 
                                     of 
                                     ⁢ 
                                     
                                         
                                     
                                     ⁢ 
                                     the 
                                     ⁢ 
                                     
                                         
                                     
                                     ⁢ 
                                     object 
                                     ⁢ 
                                     
                                         
                                     
                                     ⁢ 
                                     pixels 
                                   
                                   , 
                                 
                               
                             
                           
                         
                       
                       
                         
                           0 
                         
                         
                           
                             
                               
                                 
                                   if 
                                   ⁢ 
                                   
                                       
                                   
                                   ⁢ 
                                   the 
                                   ⁢ 
                                   
                                       
                                   
                                   ⁢ 
                                   pixel 
                                   ⁢ 
                                   
                                       
                                   
                                   ⁢ 
                                   at 
                                   ⁢ 
                                   
                                       
                                   
                                   ⁢ 
                                   the 
                                   ⁢ 
                                   
                                       
                                   
                                   ⁢ 
                                   location 
                                   ⁢ 
                                   
                                       
                                   
                                   ⁢ 
                                   
                                     ( 
                                     
                                       x 
                                       , 
                                       y 
                                     
                                     ) 
                                   
                                 
                               
                             
                             
                               
                                 
                                   
                                     is 
                                     ⁢ 
                                     
                                         
                                     
                                     ⁢ 
                                     one 
                                     ⁢ 
                                     
                                         
                                     
                                     ⁢ 
                                     of 
                                     ⁢ 
                                     
                                         
                                     
                                     ⁢ 
                                     the 
                                     ⁢ 
                                     
                                         
                                     
                                     ⁢ 
                                     background 
                                     ⁢ 
                                     
                                         
                                     
                                     ⁢ 
                                     pixels 
                                   
                                   , 
                                   and 
                                 
                               
                             
                           
                         
                       
                       
                         
                           0.5 
                         
                         
                           
                             otherwise 
                             . 
                           
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   8 
                   ) 
                 
               
             
           
         
       
     
     As shown in  FIG. 5 , the label propagation  310  determines a minimum distance D along a path  501  in an image grid graph from each unlabeled pixel  510  to one of the labeled pixel  511 . In the image grid graph, each pixel is a node and edges connect each node with eight nearest neighboring pixels as shown only for pixel  510 . 
     The minimum distance is 
                         D   k     ⁡     (     x   ,   y     )       =       min       (       x   1     ,     y   1       )     ,     (       x   2     ,     y   2       )     ,           ⁢   …   ⁢           ,     (       x   m     ,     y   m       )         ⁢       ∑     i   =   1     m     ⁢     d   ⁢     (       (       x     i   -   1       ,     y     i   -   1         )     ,     (       x   i     ,     y   i       )       )             ,           (   9   )               
where L(x m , y m )=k, for k=0, 1, and where m is an index of the pixel (x m , y m ).
 
     That is, D 0 (x, y) is the minimum distance from the unlabeled pixel at location (x, y) to one of the labeled pixels that is similar in intensity. The corresponding path is
 
( x, y ),( x   1   , y   1 ), ( x   2   , y   2 ), . . . , ( x   m   , y   m ),
 
where L(x m , y m )=0. The index m changes for every pixel location (x, y).
 
     In other words, unlabeled pixels at different locations have different paths to one of the labeled pixel, and hence different path lengths m.
 
 d (( X   i−1   , Y   i−1 ),( X   i   , Y   i ))=∥ U ( X   i−1   , Y   i−1 )− U ( X   i   , Y   i )∥  (10)
 
     The minimum distances initialize a probabilistic level set as 
     
       
         
           
             
               
                 
                   
                     
                       
                         f 
                         0 
                       
                       ⁡ 
                       
                         ( 
                         
                           x 
                           , 
                           y 
                         
                         ) 
                       
                     
                     = 
                     
                       1 
                       - 
                       
                         
                           
                             D 
                             1 
                           
                           ⁡ 
                           
                             ( 
                             
                               x 
                               , 
                               y 
                             
                             ) 
                           
                         
                         
                           
                             
                               D 
                               1 
                             
                             ⁡ 
                             
                               ( 
                               
                                 x 
                                 , 
                                 y 
                               
                               ) 
                             
                           
                           + 
                           
                             
                               D 
                               0 
                             
                             ⁡ 
                             
                               ( 
                               
                                 x 
                                 , 
                                 y 
                               
                               ) 
                             
                           
                         
                       
                     
                   
                   , 
                   and 
                 
               
               
                 
                   ( 
                   11 
                   ) 
                 
               
             
             
               
                 
                   
                     J 
                     U 
                   
                   = 
                   
                     - 
                     
                       
                         ∫ 
                         Ω 
                       
                       ⁢ 
                       
                         
                           
                             ( 
                             
                               
                                 f 
                                 ⁡ 
                                 
                                   ( 
                                   
                                     x 
                                     , 
                                     y 
                                   
                                   ) 
                                 
                               
                               - 
                               
                                 
                                   f 
                                   0 
                                 
                                 ⁡ 
                                 
                                   ( 
                                   
                                     x 
                                     , 
                                     y 
                                   
                                   ) 
                                 
                               
                             
                             ) 
                           
                           2 
                         
                         ⁢ 
                         
                           ⅆ 
                           x 
                         
                         ⁢ 
                         
                           
                             ⅆ 
                             y 
                           
                           . 
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   12 
                   ) 
                 
               
             
           
         
       
     
     The probabilistic level sets is used in the maximum belief cost function: 
     
       
         
           
             
               
                 
                   
                     
                       J 
                       B 
                     
                     = 
                     
                       
                         
                           ∫ 
                           Ω 
                         
                         ⁢ 
                         
                           
                             f 
                             ⁡ 
                             
                               ( 
                               
                                 x 
                                 , 
                                 y 
                               
                               ) 
                             
                           
                           ⁢ 
                           
                             H 
                             ⁡ 
                             
                               ( 
                               
                                 f 
                                 ⁡ 
                                 
                                   ( 
                                   
                                     x 
                                     , 
                                     y 
                                   
                                   ) 
                                 
                               
                               ) 
                             
                           
                           ⁢ 
                           
                             ⅆ 
                             x 
                           
                           ⁢ 
                           
                             ⅆ 
                             y 
                           
                         
                       
                       N 
                     
                   
                   , 
                 
               
               
                 
                   ( 
                   13 
                   ) 
                 
               
             
           
         
       
     
     where
 
 N=∫   Ω   H (ƒ( x, y )) dxdy  
 
is a number of the object pixels.
 
     Thus, the cost function used during the evolution is the sum of the region-based cost function J o , the user cost function J U , and the maximum belief cost function J B :
 
 J=J   O +λ U   J   U +λ B   J   B   (14)
 
where λ U _and λ B  are scalar parameters to control a relative importance of the user cost function J U  and the maximum belief cost function J B , respectively.
 
     The level set is evolved using Euler-Lagrange equations of the cost function until a local minimum is reached. The EulerLagrange equations are differentiable and stationary at the local minimum. 
       FIG. 6  shows the segment  309  produce by the method described above, which is visible more accurate than the segmentation shown in  FIG. 1  with conventional methods. 
     Although the invention has been described by way of examples of preferred embodiments, it is to be understood that various other adaptations and modifications may be made within the spirit and scope of the invention. Therefore, it is the object of the appended claims to cover all such variations and modifications as come within the true spirit and scope of the invention.