Abstract:
Aspects of the present invention are related to systems and methods for automatically determining the content boundaries in a digital image. A gradient field may be generated using an edge detector, and the gradient field may be thresholded, by magnitude, to retain strong edges. The resulting localized edge positions may be projected onto a first direction and a second direction to form two projection histograms. The projection histograms may be analyzed to determine the boundaries of the image content. Corners of a cropping rectangle may be computed, and the digital image may be cropped according to the content boundaries.

Description:
FIELD OF THE INVENTION 
     Embodiments of the present invention comprise methods and systems for automatically determining image-content boundaries. 
     BACKGROUND 
     It may be desirable to crop off extraneous portions of a digital page, also considered a digital image, digital document and image. In particular, in may be desirable to retain the content of the digital page while eliminating extraneous page margins. Exemplary applications in which this may be useful include applications in which the page content may be repositioned on a different size page than the original, applications in which the page content may be composited with additional material and other document layout applications. It may be desirable to perform cropping automatically without user interaction. It also may be desirable to perform cropping on a digital page comprising an arbitrarily shaped content region, and it may be desirable to perform cropping when the digital page content is skewed with respect to the orthogonal image axes. Methods and systems for automatically determining image-content boundaries, therefore, may be desirable. 
     SUMMARY 
     Some embodiments of the present invention comprise methods and systems for determining content boundaries in a digital image. In some embodiments of the present invention, an edge detector based on local gradient computation may be used to generate a gradient field which may thresholded by magnitude to retain strong edges. The resulting localized edge positions may be projected onto a first direction and a second direction, which may be normal to the first direction, to form two projection histograms. In some embodiments of the present invention, the first direction may be related to a skew vector which describes the skew of the image content relative to the image axes. The projection histograms may be analyzed to determine the boundaries of the image content. In some embodiments of the present invention, the corners of a cropping rectangle may be computed, wherein the cropping rectangle may contain the desired content from the image. In some embodiments of the present invention, the digital image may be cropped according to the content boundaries. In some embodiments of the present invention, the digital image may be simultaneously cropped and corrected for skew. 
     The foregoing and other objectives, features, and advantages of the invention will be more readily understood upon consideration of the following detailed description of the invention taken in conjunction with the accompanying drawings. 
    
    
     
       BRIEF DESCRIPTION OF THE SEVERAL DRAWINGS 
         FIG. 1  is a chart showing exemplary embodiments of the present invention comprising extracting edges from an image, forming projection histograms from the edge maps and determining content boundaries from the projection histograms; 
         FIG. 2  is a picture depicting exemplary projection histograms; 
         FIG. 3  is a picture depicting skewed image content; 
         FIG. 4  is a chart showing exemplary embodiments of the present invention comprising forming a low-resolution representation of an input image prior to determining content boundaries; 
         FIG. 5  is a chart showing exemplary embodiments of the present invention comprising smoothing a low-resolution representation of an input image prior to determining content boundaries; 
         FIG. 6  is a chart showing exemplary embodiments of the present invention comprising smoothing an input image prior to determining content boundaries; 
         FIG. 7  is a chart showing exemplary embodiments of the present invention comprising partitioning an image into non-overlapping blocks and determining block content boundaries; and 
         FIG. 8  is a chart showing exemplary embodiments of the present invention comprising partitioning an image into overlapping blocks and determining block content boundaries. 
     
    
    
     DETAILED DESCRIPTION OF EXEMPLARY EMBODIMENTS 
     Embodiments of the present invention will be best understood by reference to the drawings, wherein like parts are designated by like numerals throughout. The figures listed above are expressly incorporated as part of this detailed description. 
     It will be readily understood that the components of the present invention, as generally described and illustrated in the figures herein, could be arranged and designed in a wide variety of different configurations. Thus, the following more detailed description of the embodiments of the methods and systems of the present invention is not intended to limit the scope of the invention but it is merely representative of the presently preferred embodiments of the invention. 
     Elements of embodiments of the present invention may be embodied in hardware, firmware and/or software. While exemplary embodiments revealed herein may only describe one of these forms, it is to be understood that one skilled in the art would be able to effectuate these elements in any of these forms while resting within the scope of the present invention. 
     It may be desirable to crop off extraneous portions of a digital page, also considered a digital image, digital document and image. In particular, in may be desirable to retain the content of the digital page while eliminating extraneous page margins. Exemplary applications in which this may be useful include applications in which the page content may be repositioned on a different size page than the original, applications in which the page content may be composited with additional material and other document layout applications. It may be desirable to perform cropping automatically without user interaction. It also may be desirable to perform cropping on a digital page comprising an arbitrarily shaped content region, and it may be desirable to perform cropping when the digital page content is skewed with respect to the orthogonal image axes. 
     Some embodiments of the present invention described in relation to  FIG. 1  comprise methods and systems for automatically determining the content boundaries in a digital page. In these embodiments, the location of the edges in the digital page may be extracted  4 , also considered detected or determined, thereby producing an edge mask, or other representation, indicating locations of large gradient magnitude in the digital page. The edge mask may be projected on a skew vector and the skew vector normal vector to form  6  two projection histograms. The content boundaries may be detected  8 , also considered determined, from the two projection histograms. 
     In some embodiments of the present invention described in relation to  FIG. 1 , edge-location determination  4  may comprise computing a gradient magnitude at each pixel in the digital page and thresholding the gradient magnitude results to form an edge mask. In some embodiments of the present invention, the gradient field in the x-direction, which may be denoted G x , and the gradient field in the y-direction, which may be denoted G y , may be determined independently, and the gradient magnitude, which may be denoted G, may be determined according to:
 
 G=∥∇∥   1   =|G   x   |+|G   y |,
 
where |•| denotes absolute value.
 
     In some embodiments of the present invention, the digital page, which may be denoted I, may be independently convolved with two edge kernels to determine the gradient fields in the x-direction and the y-direction. In some embodiments the edge kernels may comprise Sobel operators, and the gradient fields may be determined according to: 
     
       
         
           
             
               G 
               x 
             
             = 
             
               
                 
                   [ 
                   
                     
                       
                         1 
                       
                       
                         0 
                       
                       
                         
                           - 
                           1 
                         
                       
                     
                     
                       
                         2 
                       
                       
                         0 
                       
                       
                         
                           - 
                           2 
                         
                       
                     
                     
                       
                         1 
                       
                       
                         0 
                       
                       
                         
                           - 
                           1 
                         
                       
                     
                   
                   ] 
                 
                 * 
                 I 
                 ⁢ 
                 
                     
                 
                 ⁢ 
                 and 
                 ⁢ 
                 
                     
                 
                 ⁢ 
                 
                   G 
                   y 
                 
               
               = 
               
                 
                   [ 
                   
                     
                       
                         1 
                       
                       
                         2 
                       
                       
                         1 
                       
                     
                     
                       
                         0 
                       
                       
                         0 
                       
                       
                         0 
                       
                     
                     
                       
                         
                           - 
                           1 
                         
                       
                       
                         
                           - 
                           2 
                         
                       
                       
                         
                           - 
                           1 
                         
                       
                     
                   
                   ] 
                 
                 * 
                 
                   I 
                   . 
                 
               
             
           
         
       
     
     In alternative embodiments, edge detection may comprise other edge operators and methods known in the art, for example, a Canny edge detector, a Prewitt edge detector, a Roberts Cross kernel and a Hough transform. 
     In some embodiments of the present invention, the gradient magnitude, G, may be thresholded to form a binary image, also considered edge map, which may be denoted G′. In these embodiments, the binary image, G′, may be set equal to one of the binary values when a first condition is satisfied and may be set to the other of the binary values when the first condition is not satisfied. In some embodiments of the present invention, the binary image, G′, may be determined according to: 
                 G   ′     ⁡     (     i   ,   j     )       =     {             1   ,             G   ⁡     (     i   ,   j     )       &gt;   θ               0   ,             G   ⁡     (     i   ,   j     )       ≤   θ           ,             
where θ denotes an adaptive threshold based on the content of the image and (i, j) denotes a location in the gradient-magnitude image, G.
 
     In some embodiments of the present invention, the adaptive threshold, θ, may be determined according to: 
               θ   =       -   μ     ⁢           ⁢     log   (       100   -   p     100     )         ,     
     ⁢     where   ⁢     :                   μ   =       1     w   ·   h       ⁢       ∑     x   ,   y       ⁢     G   ⁡     (     x   ,   y     )                 
in which w is the width of and h is the height of the gradient-magnitude image, G, respectively, and p is a parameter which may control the rejection of the weakest p percentage of edges. In some embodiments, the value of p may be set to 95. In alternative embodiments, p may be set in the range of 93 to 97.
 
     Two projection histograms may be formed  6  by projecting the edge map, G′, onto a skew vector and a vector normal to the skew vector. Two exemplary projection histograms  10 ,  11  are shown in  FIG. 2 . The horizontal axis  12 ,  13  of each histogram  10 ,  11  indicates a coordinate in the direction of the axis, and the vertical axis  14 ,  15  of each histogram  10 ,  11  indicates a pixel count. The content boundaries in the directions of the skew vector and the skew vector normal may be determined  8  by the first and last histogram bins which contain pixel counts. For the exemplary histograms  10 ,  11  shown in  FIG. 2  these bins are indicated  16 ,  17 ,  18 ,  19 . 
     Embodiments of the present invention may be further understood in relation to  FIG. 3 .  FIG. 3  shows an exemplary image  20  comprising a page region  22  which is skewed relative to the image axes. The skew vector  24  and the normal to the skew vector  26  are shown for an exemplary skew angle  28 . The skew vector  24  and the normal to the skew vector  26  are shown relative to an origin  30  which may be the same origin of the image coordinate system. The locations of the first and last histogram bins which contain pixel counts in the projection histogram associated with the skew vector  26  are labeled A  31  and B  32 . The locations of the first and last histogram bins which contain pixel counts in the projection histogram associated with the normal to the skew vector  26  are labeled C  33  and D  34 . In relation to the exemplary histograms  10 ,  11  shown in  FIG. 2 , assuming that the top histogram  10  corresponds to the projection histogram associated with the skew vector  24  and the bottom histogram  11  corresponds to the projection histogram associated with the normal to the skew vector  26 , then A  31  may correspond to the location in the top histogram  10  of the first bin  16  from the origin which has a non-zero pixel count. B  32  may correspond to the location in the top histogram  10  of the last bin  18  from the origin which has a non-zero pixel count. C  33  may correspond to the location in the bottom histogram  11  of the first bin  17  from the origin which has a non-zero pixel count. D  34  may correspond to the location in the bottom histogram  11  of the last bin  19  from the origin which has a non-zero pixel count. 
     In some embodiments of the present invention, the content boundaries may be described by the corners of a bounding rectangle. These corners may be denoted in relation to the locations determined from the projection histograms. Denoting the location of the first and last histogram bins with non-zero count in the projection histogram associated with the skew vector as left and right, respectively, and the location of the first and last histogram bins with non-zero count in the projection histogram associated with the skew vector normal as bottom and top, respectively, then the corners of the bounding rectangle may be given according to: 
     bottom-left corner is (left, bottom) in the skewed coordinate system, 
     bottom-right corner is (right, bottom) in the skewed coordinate system, 
     top-left corner is (left, top) in the skewed coordinate system and 
     top-right corner is (right, top) in the skewed coordinate system. 
     Some embodiments of the present invention may be described in relation to  FIG. 4 . In these embodiments, a low-resolution representation of an image may be derived  42  prior to determining  44  edge locations in the low-resolution representation. Projection histograms may be formed  46  from the edge map, and the content boundaries may be detected  48  using the projection histograms. In some embodiments of the present invention, the low-resolution representation may be derived  42  through sub-sampling and down-sampling techniques known in the art. In some embodiments of the present invention, the low-resolution representation of the input image may be a 75 dots-per-inch image. 
     Some embodiments of the present invention may be described in relation to  FIG. 5 . In these embodiments, a low-resolution representation of an image may be derived  50 , and the low-resolution representation of the image may be smoothed  52  prior to determining  54  edge locations in the low-resolution representation. Projection histograms may be formed  56  from the edge map, and the content boundaries may be detected  58  using the projection histograms. In some embodiments of the present invention, the smoothed version of the low-resolution representation may be derived  52  by smoothing the low-resolution representation of the input image using a 3×3 Gaussian filter. In alternative embodiments, smoothing may comprise Gaussian filters of other size, smoothing filters of other types and other smoothing techniques known in the art. 
     Some embodiments of the present invention may be described in relation to  FIG. 6 . In these embodiments, an input image may be smoothed  62  prior to determining  64  edge locations in the smoothed image. Projection histograms may be formed  66  from the edge map, and the content boundaries may be detected  68  using the projection histograms. In some embodiments of the present invention, the smoothed version of the input image may be derived  62  by smoothing the input image using a 3×3 Gaussian filter. In alternative embodiments, smoothing may comprise Gaussian filters of other size, smoothing filters of other types and other smoothing techniques known in the art. 
     In some embodiments of the present invention described in relation to  FIG. 7 , an image may be partitioned  72  into non-overlapping blocks. The block content boundaries may be determined  74  according to embodiments of the present invention described above. The block boundaries may be combined  76  to generate the content boundary for the image. In some of these embodiments, the corners of the content boundaries for each block may be determined  74  and designated R i =[top i  bottom i  left i  right i ]. The content boundaries, which may be designated by the bounding rectangle corners and denoted R, for the image may be determined  76  from the block boundaries according to:
 
 R =[max(top i ) min(bottom i ) min(left i ) max(right i )]
 
for a coordinate origin in the lower-left of an image, and according to:
 
 R =[min(top i ) max(bottom i ) min(left i ) max(right i )]
 
for a coordinate origin in the upper-left of an image. In some embodiments of the present invention, determination  74  of the block content boundaries may be performed in parallel by a plurality of processors. In alternative embodiments, the determination  74  of the block content boundaries may be performed serially.
 
     In some embodiments of the present invention described in relation to  FIG. 8 , an image may be partitioned  82  into overlapping blocks. The block content boundaries may be determined  84  according to embodiments of the present invention described above. The block boundaries may be combined  86  to generate the content boundary for the image. In some of these embodiments, the corners of the content boundaries for each block may be determined  84  and designated R i =[top i  bottom i  left i  right i ]. The content boundaries, which may be designated by the bounding rectangle corners and denoted R, for the image may be determined  86  from the block boundaries according to:
 
 R =[max(top i ) min(bottom i ) min(left i ) max(right i )]
 
for a coordinate origin in the lower-left of an image, and according to:
 
 R =[min(top i ) max(bottom i ) min(left i ) max(right i )]
 
for a coordinate origin in the upper-left of an image. In some embodiments of the present invention, determination  84  of the block content boundaries may be performed in parallel by a plurality of processors. In alternative embodiments, the determination  84  of the block content boundaries may be performed serially.
 
     In some embodiments of the present invention, the input image may be a color image. In alternative embodiments of the present invention, the input image may be a gray-scale image. In still alternative embodiments of the present invention, the input image may be a binary image. 
     In some embodiments of the present invention, the input image may be a luminance image corresponding to a color image. In alternative embodiments of the present invention, the input image may be a binary image corresponding to a color image. In still alternative embodiments of the present invention, the input image may be a binary image corresponding to a gray-scale image. 
     In some embodiments of the present invention, an image may be cropped according to the determined content boundaries. 
     In some embodiments of the present invention, an image may be simultaneously cropped according to the determined content boundaries and skew corrected. 
     The terms and expressions which have been employed in the foregoing specification are used therein as terms of description and not of limitation, and there is no intention in the use of such terms and expressions of excluding equivalence of the features shown and described or portions thereof, it being recognized that the scope of the invention is defined and limited only by the claims which follow.