Abstract:
A method for searching an image database includes capturing an image of a photograph and a background, determining a boundary of the photograph in the image, cropping the photograph from the image, correcting the perspective of the photograph, compensating colors of the photograph, and matching the photograph with an image in the image database.

Description:
FIELD OF INVENTION  
         [0001]    This invention relates to a method to retrieve an image from a database.  
         DESCRIPTION OF RELATED ART  
         [0002]    With the growing popularity of digital cameras and the rapid increase of storage capacity, it is common for consumers to store thousands of photos on a personal computer or through a photo-sharing website. Content-based image retrieval (CBIR) is therefore becoming a necessity. Although there are various query methods in CBIR systems, query by example has received wide acceptance. Query by example requires the least user interaction and the query image contains more useful information for matching than other forms of query such as query by drawing.  
           [0003]    There are several well-known CBIR systems, such as QBIC (Query By Image Content) of IBM, Photobook of Massachusetts Institute of Technology, VisualSEEk and WebSEEk of Columbia University, and MARS (Multimedia Analysis and Retrieval System) of University of Illinois at Urbana-Champaign. All these systems have query by example function.  
           [0004]    In most CBIR systems, the user selects a query image from by the same database that is to be searched, and the query image is used to search for similar images in the database. This is not useful when the user is looking for a specific image. For example, the user may want to reprint a photograph from a large database. The user has the previously printed photograph on hand and wants to find the same photograph in the database to order reprints. Thus, what is needed is a method for to retrieve a specific image from a database when the user has a hard copy of the image.  
         SUMMARY  
         [0005]    In one embodiment of the invention, a method for searching an image database includes capturing an image of a photograph and a background, determining a boundary of the photograph in the image, cropping the photograph from the image, correcting the perspective of the photograph, compensating colors of the photograph, and matching the photograph with an image in the image database. 
       
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS  
       [0006]    [0006]FIG. 1 illustrates a system for searching images in a database in one embodiment of the invention.  
         [0007]    [0007]FIGS. 2, 4,  7 , and  8  are flowcharts of methods for searching images in a database in embodiments of the invention.  
         [0008]    [0008]FIGS. 3A, 3B,  5 A,  5 B,  6 A, and  6 B illustrate images captured or generated in the methods of FIGS. 2, 4,  7 , and  8  in embodiments of the invention. 
     
    
     DETAILED DESCRIPTION  
       [0009]    In accordance with the invention, a method is provided to (1) detect a photograph from a complicated background in an image captured by a camera, and (2) search for images similar to the photograph in a database.  
         [0010]    [0010]FIG. 1 illustrates an image retrieval system  10  in one embodiment of the invention. System  10  includes a camera  12  that captures an image of a query photograph  14  and a background  16 . Camera  12  can be a digital video camera (e.g., a WebCam) or a digital still camera. Alternatively, a scanner or another type of image input device can be used instead of camera  12 .  
         [0011]    Camera  12  outputs the captured image to a computer  18 . Camera  12  can be coupled to computer  18  as a peripheral device or over a network connection (e.g., through a client computer that is connected to a server computer  18  over the Internet). Accordingly, computer  18  can be a local desktop or a remote server used to search images in a database  19 . Database  19  can be part of computer  18  or an independent device coupled to computer  18 .  
         [0012]    [0012]FIG. 2 is a flowchart of a method  50  implemented by system  10  to search images in database  19  in one embodiment. In step  52 , camera  12  captures background  16  in an image  20  (FIG. 3A).  
         [0013]    In step  54 , camera  12  captures photograph  14  and background  16  in an image  22  (FIG. 3B). Typically the user holds up photograph  14  with his or her hand  24 . Photograph  14  and hand  24  make up the foreground in image  22  against background  16  in image  22 . For a good result, photograph  14  is substantially centered and within the field of view of camera  12  and makes up the principal portion of image  22 . Image  22  is then transmitted to computer  18 . If computer  18  is a server computer, image  22  is transmitted from the user&#39;s computer (e.g., a client computer) to a server computer  18  over a network (e.g., the Internet).  
         [0014]    In step  56 , computer  18  separates photograph  14  from the background of image  22 . Typically, Hough Transformation is used to detect straight lines that form the boundary of an object. However, lines in photograph  14  and background  16  may be mistaken for the boundary of photograph  14 . One embodiment of step  56  that addresses these problems is described in more detail later in reference to FIG. 4.  
         [0015]    If a scanner instead of camera  12  is used, the scanner may come with software that separates photography  14  from the scanner cover that makes up background  16 . This is a simple step since the scanner cover provides a consistent white background. Alternatively, photography  14  is placed in a designated area for the software to crop.  
         [0016]    In step  58 , computer  18  rotates photograph  14  to compensate the perspective at which camera  12  captured photograph  14 . Computer  18  can rotate photograph  14  by Affine Transformation as shown in the transition from FIG. 6A to FIG. 6B.  
         [0017]    In step  59 , computer  18  resizes photograph  14  to a resolution that matches the resolution of the images in database  19 . A set of the images in database  19  saved at a low resolution (e.g., 96 by 96 pixels resolution) can also be used to speed up the matching process.  
         [0018]    In step  60 , computer  18  adjusts the color of photograph  14  to compensate the environment (e.g., lighting, distance, and angle) under which camera  12  captured photograph  14 . If the color of photograph  14  is not adjusted, it may be difficult to find similar images using color feature matching because the color of photograph  14  in image  22  depends on the environment. One embodiment of step  60  is described later in reference to FIG. 7.  
         [0019]    In step  62 , computer  18  searches for one or more images  168  (FIG. 1) in database  19  that are similar to photograph  14 . Computer  18  can search for similar images by comparing edge features, texture features, color features, or a combination thereof. Furthermore, computer  18  can receive relevance feedback from the user. According to the relevance feedback from the user, computer  18  can adjust the weight of the edge features, texture features, and color features to produce a better search result. Images  168  that match photograph  14  are provided to the user. If computer  18  is a desktop, the result is displayed to the user. If computer  18  is a server computer, the result is transmitted to the user&#39;s computer (e.g., a client computer) over a network (e.g., the Internet).  
         [0020]    [0020]FIG. 4 is a flowchart of step  56  that determines the boundary of photograph  14  in one embodiment. As described above, this embodiment of step  56  reduces the influence of the photograph and background content.  
         [0021]    In step  82 , computer  18  removes the content of the background from image  22 . To do so, computer  18  compares images  20  and  22  to determine a region  26  (FIG. 5A) on image  22  where the pixels have changed in their RGB values. Assuming background  16  is static, region  26  should be the foreground that includes photograph  14  and hand  24  that is holding photograph  14 . Computer  18  thus removes all the pixels outside of region  26 . The removed portion of the background is shown in black in FIG. 5A.  
         [0022]    In step  84 , computer  18  removes the content inside region  26 . To do so, computer  18  scans region  26  line by line, first vertically and then horizontally. For each line, computer  18  preserves the first pixel and the last pixel, and removes the intermediate pixels. Thus, only the pixels that make up a perimeter  28  (FIG. 5B) of region  26  remains and all other pixels that make up the content of region  26  are removed. The removed portion of region  26  is shown in black in FIG. 5B.  
         [0023]    In step  86 , computer  18  determines a boundary  30  (FIG. 6A) of photograph  14  from perimeter  28  (FIG. 5B). In this step, photograph  14  is assumed to be a rectangular print that is titled at an angle no more than 45 degrees. Computer  18  can determine boundary  30  by Hough Transformation. In Hough Transformation, a straight line is represented by the following formula:  
           x  cos θ+ y  sin θ=π  (1)  
         [0024]    where x and y are the coordinates of a pixel that form part of the line, θ is the normal angle of the line to the origin, and π is the normal distance of the line to the origin.  
         [0025]    The Hough Transformation is performed in the following fashion. First, computer  18  assigns the origin of the coordinates to the center of image  22 . Second, computer  18  quantizes angle θ and distance π for the pixels that make up perimeter  28  (FIG. 5B). The results are stored as Hough accumulators. Third, the value pairs (θ, π) of the four largest accumulators are used as the parameters of the four straight lines that make up boundary  30  (FIG. 6A) of photograph  14 .  
         [0026]    When searching for the left and right boundary lines, angle θ is only quantized between 45° to 135°, and distance π is only quantized between 0 to half the width of image  22 . Similarly, when searching for the top and bottom boundary lines, angle θ is only quantized between −45° to 45°, and distance π is only quantized between 0 to half the height of image  22 .  
         [0027]    In step  87 , computer  18  validates the four boundary lines determined by Hough Transformation. This may be necessary because the result may degrade when (1) a boundary line is located too close to, or occluded by, an edge of image  22 , or (2) when user hand  24  is mixed in region  26 . This embodiment is described later in reference to FIG. 8.  
         [0028]    In step  88 , computer  18  crops photograph  14  from image  22 .  
         [0029]    [0029]FIG. 7 is a flowchart of step  60  that adjusts the color of photograph  14  in one embodiment. As described above, this step may be necessary to compensate for the different environments under which camera  12  captures photograph  14 .  
         [0030]    In step  112 , computer  18  adjusts the color levels of photograph  14  by histogram equalization to uniformly distribute the color levels of photograph  14 . This will compensate changes in the distance and angle at which photographs are captured by camera  12 .  
         [0031]    In step  114 , computer  18  adjusts the RGB values of photograph  14  to maintain color constancy. To do this, system  10  is first calibrated with an image  170  (FIG. 1) with a reference color pattern. In one embodiment, the reference color pattern consists of individual square blocks of different colors. The colors of the square block range from a warm color to a cold color (e.g., from red to purple). In one embodiment, color numbers  18  to  25  are used. The neighboring blocks should have large intensity differences so that computer  18  can detect every color easily and accurately without user intervention.  
         [0032]    Image  170  can be stored in database  19 . Image  170  is assumed to be captured under standard (i.e., canonical) lighting. A hard copy of image  170  is captured as image  170 A with camera  12  under an unknown lighting. The unknown lighting is assumed to be the environment under which all the photographs are captured by camera  12 . Computer  18  then determines a homography matrix that transforms the RGB values of image  170  to the RGB values of image  170 A. The inverse of the homography matrix is subsequently used to transform other images captured by camera  12  to approximate their RGB values under canonical lighting.  
         [0033]    The determination of the homography matrix is now described in detail. Assume the relationship between the unknown and canonical lighting can be modeled by the following formula:  
           U   (21)   =MU   (11)   +λC    (2)  
         [0034]    where U (21)  is the RBG value of a pixel under the unknown lighting, M is the homography miatrix, U (11)  is the RGB value of the corresponding pixel under the canonical lighting, C is the illuminant parameter, and λ is a scaling factor for illuminant parameter C. Equation (2) can be rewritten as follows:  
                 [         R           G           B         ]       (   21   )       =           [           m   11           m   12           m   13               m   21           m   22           m   23               m   31           m   32           m   33           ]          [         R           G           B         ]         (   11   )       +     λ        [           C   1               C   2               C   3           ]                 (   3   )                               
 
         [0035]    or  
           R   (21)   =m   11   R   (11)   +m   12   G   (11)   +m   13   B   (11)   +λC   1    (4)  
           G   (21)   =m   21   R   (11)   +m   22   G   (11)   +m   23   B   (11)   +λC   2    (5)  
           B   (21)   =m   31   R   (11)   +m   32   G   (11)   +m   33   B   (11)   +λC   3    (6)  
         [0036]    Equations (4), (5), and (6) can be written as follows:  
           A   m = b   (7)  
         [0037]    For n point correspondences, the (3n×12)-matrix can be expressed as:  
               A   _     =           [           R   1     (   11   )             G   1     (   11   )             B   1     (   11   )           0       0       0       0       0       0       1       0       0           0       0       0         R   1     (   11   )             G   1     (   11   )             B   1     (   11   )           0       0       0       0       1       0           0       0       0       0       0       0         R   1     (   11   )             G   1     (   11   )             B   1     (   11   )           0       0       1           ⋮       ⋮       ⋮       ⋮       ⋮       ⋮       ⋮       ⋮       ⋮       ⋮       ⋮       ⋮             R   n     (   11   )             G   n     (   11   )             B   n     (   11   )           0       0       0       0       0       0       1       0       0           0       0       0         R   n     (   11   )             G   n     (   11   )             B   n     (   11   )           0       0       0       0       1       0           0       0       0       0       0       0         R   n     (   11   )             G   n     (   11   )             B   n     (   11   )           0       0       1         ]               (   8   )                               
 
         [0038]    The vector  m  of unknowns m ij  and λC i  can be expressed as:  
           m =[m 11  m 12  . . . m 33  λC 1  λC 2  λC 3 ] T    (9)  
         [0039]    The (3n)-vector can be expressed as:  
           b =[R 1   (21)  G 1   (21)  B 1   (21)  . . . R n   (21)  G n   (21)  B n   (21) ] T    (10)  
         [0040]    The solution for  m  is given by  
           m =( A   T    A+EE) −1 (A   T   b )  (11)  
         [0041]    After finding vector  m , it is assumed that this homography (equation (2)) is valid not only to transform the reference image  170  under canonical lighting to what it will appear under the unknown lighting, but also to convert images of photographs under the canonical lighting to what they will appear under the same unknown lighting. Consequently, the inverse of matrix M in equation (2) can be calculated to convert the RGB values of all the pixels of the photography captured under unknown lighting to their corresponding RGB values under the canonical lighting as follows:  
           U   (11)   =M   −1  ( U   (21)   −λC )  (12)  
         [0042]    [0042]FIG. 8 is a flowchart of one embodiment of step  87  that validates the boundary lines determined from Hough Transformation. As described above, step  87  may be necessary when (1) a boundary line is located too close to, or occluded by, an edge of image  22 , or (2) when user hand  24  is mixed in region  26 . Step  87  is performed for each of the boundary lines.  
         [0043]    In step  142 , computer  18  determines if the boundary line is too close to the corresponding edge (e.g., if the left boundary line is too close the left edge of image  22 ). A boundary line is too close to the corresponding edge when the shortest distance between them is less than a threshold. In one embodiment, the boundary line is too close to the corresponding edge when the shortest distance between the boundary line and the corresponding edge is less than 8 pixels. If so, step  142  is followed by step  144 . If the boundary line is not too close to the corresponding edge, then step  144  is followed by  150 .  
         [0044]    In step  144 , computer  18  determines if the boundary line is substantially parallel to the corresponding edge. In one embodiment, the boundary line is substantially parallel to the corresponding edge when their angles are within 3 degrees. If so, step  144  is followed by step  146 . If the boundary line is not substantially parallel to the corresponding edge, then step  146  is followed by  150 .  
         [0045]    In step  146 , computer  18  determines if the confidence (i.e., the Hough accumulator value) of the boundary line&#39;s subtense is high enough. A boundary line&#39;s subtense is the opposite boundary line in perimeter  30  of region  26 . In one embodiment, the confidence of the boundary line&#39;s subtense is high enough when it is greater than 60. If so, step  146  is followed by step  148 . If the confidence of the boundary line&#39;s subtense is not high enough, step  146  is followed by step  150 .  
         [0046]    In step  148 , computer  18  invalidates the boundary line and searches for a new boundary line. For the new boundary line, computer  18  can limits its search to lines having angles θ between ±30° of the angle θ of the invalid boundary line&#39;s subtense.  
         [0047]    In step  150 , computer  18  validates the boundary line.  
         [0048]    Various other adaptations and combinations of features of the embodiments disclosed are within the scope of the invention. Numerous embodiments are encompassed by the following claims.