Abstract:
A system for implementing a method for searching multimedia contents uses a pictorial edit distance to compare a search query consisting of an image to a database of images to determine the ranking of matches from closest match to least closest match between the search image and the images in the database or portions of the images in the database.

Description:
CROSS-REFERENCE TO RELATED APPLICATIONS 
     This application claims benefit of U.S. provisional patent application Ser. No. 60/861,686, filed on Nov. 29, 2006, which is herein incorporated by reference, and U.S. non-provisional patent application Ser. No. 11/619,092 filed on Jan. 2, 2007. 
    
    
     FIELD OF THE INVENTION 
     The present invention relates generally to the field of techniques for analyzing multimedia data and, in particular, methods and systems for searching a multimedia content for graphical objects of interest. 
     BACKGROUND OF THE INVENTION 
     Recognition of objects of interest (referred to herein as “targets”) in graphical contents of 2D images is used by military, law enforcement, commercial, and private entities, as well as individuals. Typically, the goal of target recognition is identification or monitoring of one or more targets depicted in images produced by surveillance apparatuses or in images stored in respective databases or archives. In some instances, portions of the images may be accompanied or substituted with respective annotating texts and, as such, represent a multimedia content (i.e., combination of graphics and text). 
     It has been recognized in the art that there are difficulties associated with computerized comparing of the graphical contents of images and, specifically, with searching multimedia contents. In particular, many challenges in the field of computerized target recognition relate to identification more than one target or targets that change their appearance due to orientation, lighting conditions, or partial occlusions. 
     Despite the considerable effort in the art devoted to techniques for computerized searching of multimedia contents, further improvements would be desirable. 
     SUMMARY OF THE INVENTION 
     One aspect of the invention provides a method for searching a multimedia content that includes pluralities of content images and text documents. The method is based on an assessment of a similarity score between the compared images and/or annotating texts and uses a multimedia user graphical interface (MGUI). The similarity score is defined as a complement to a pictorial edit distance (PED), which is asserted as a weighted sum of a 2D representation of Insertion, Deletion, and Substitution Error terms of the Levenshtein algorithm for matching or searching one-dimensional data strings. 
     In one embodiment, the method comprises the steps of indexing content images using similarity score metric, developing the MGUI, providing query data including query images and/or query texts, and searching the multimedia content using the MGUI for information relevant to the query data based on similarity scores between the query data and the content images. 
     Other aspects of the present invention provide an apparatus and system using the inventive method for searching a multimedia content. 
     Various other aspects and embodiments of the invention are described in further detail below. 
     The Summary is neither intended nor should it be construed as being representative of the full extent and scope of the present invention, which these and additional aspects will become more readily apparent from the detailed description, particularly when taken together with the appended drawings. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         FIG. 1  is a flow diagram illustrating a method for searching a multimedia content in accordance with one embodiment of the present invention. 
         FIG. 2  is a schematic diagram depicting exemplary query and content images compared using the method of  FIG. 1 . 
         FIG. 3  is a schematic diagram illustrating an image search engine used by the method of  FIG. 1   
         FIG. 4  is a schematic diagram illustrating an embodiment of a multimedia user graphical interface used by the method of  FIG. 1 . 
         FIG. 5  is a high-level, schematic diagram of an exemplary apparatus using the method of  FIG. 1 . 
     
    
    
     To facilitate understanding, identical reference numerals have been used, where possible, to designate similar elements that are common to the figures, except that suffixes may be added, when appropriate, to differentiate such elements. The images in the drawings are simplified for illustrative purposes and have not necessarily been drawn to scale. 
     The appended drawings illustrate exemplary embodiments of the invention and, as such, should not be considered as limiting the scope of the invention that may admit to other equally effective embodiments. It is contemplated that features or steps of one embodiment may beneficially be incorporated in other embodiments without further recitation. 
     DETAILED DESCRIPTION 
     Referring to the figures,  FIG. 1  depicts a flow diagram illustrating a method  100  for searching a multimedia content in accordance with one embodiment of the present invention,  FIG. 2  depicts a schematic diagram  200  illustrating exemplary query and content images compared using the method  100 , and  FIGS. 3-4  depict an image search engine (ISE) and a multimedia user graphical interface (MGUI), respectively, which are used in an embodiment of the method  100 . To best understand the invention, the reader should refer to  FIGS. 1-4  simultaneously. 
     In various embodiments, method steps of the method  100  are performed in the depicted order or at least two of these steps or portions thereof may be performed contemporaneously, in parallel, or in a different order. For example, portions of steps  130  and  140  or steps  150  and  160  may be performed contemporaneously or in parallel. Those skilled in the art will readily appreciate that the order of executing at least a portion of other discussed below processes or routines may also be modified. 
     Aspects of the present invention are illustratively described below within the context of images depicting live objects such as humans or body parts thereof. The invention may also be utilized within context of images depicting material objects, such as missiles or their plumes, vehicles, objects floating in air, free space, or liquid, beams of light, and the like, as well as images depicting a combination of various live or material objects. It has been contemplated and is within the scope of the invention that the method  100  is utilized within the context of such images. 
     At step  110 , pictorial edit distance (PED) and similarity score metrics are provided for a multimedia content that may include a graphical content (referred hereafter to as “content images”), text documents, or a combination thereof. Some content images may selectively include textual annotations, which allow association of such images with particular key words. 
     The PED is asserted as a weighted sum of a 2D representation of Insertion, Deletion, and Substitution Error terms of the Levenshtein algorithm for matching or searching one-dimensional data strings, and the similarity score is defined as a complement to the PED. Techniques for determining the PEDs and similarity scores and comparing images using these properties are disclosed in commonly assigned U.S. patent application Ser. No. 11/619,133 filed on Jan. 2, 2007, Ser. No. 11/619,092, filed on Jan. 2, 2007 and Ser. No. 11/619,121, filed on Jan. 2, 2007, all of which are herein incorporated by reference. Techniques for determining PEDs and similarity scores and comparing images using these properties are further disclosed in the commonly assigned U.S. patent applications by C. Podilchuk entitled “Method and System for Comparing Images Using a Pictorial Edit Distance,” filed simultaneously herewith on this date, and “Method and System for Image Recognition Using a Similarity Inverse Matrix,” simultaneously filed herewith on this date, the contents all of which are incorporated herein by reference. Salient features of these techniques are briefly discussed below. 
     Referring to  FIG. 2 , M exemplary content images  220  may be analyzed using a similarity matrix SM, 
     
       
         
           
             
               
                 
                   SM 
                   = 
                   
                     
                       ( 
                       
                         
                           
                             
                               S 
                               11 
                             
                           
                           
                             … 
                           
                           
                             
                               S 
                               
                                 1 
                                 ⁢ 
                                 
                                     
                                 
                                 ⁢ 
                                 M 
                               
                             
                           
                         
                         
                           
                             ⋮ 
                           
                           
                             ⋱ 
                           
                           
                             ⋮ 
                           
                         
                         
                           
                             
                               S 
                               
                                 M 
                                 ⁢ 
                                 
                                     
                                 
                                 ⁢ 
                                 1 
                               
                             
                           
                           
                             … 
                           
                           
                             
                               S 
                               MM 
                             
                           
                         
                       
                       ) 
                     
                     . 
                   
                 
               
               
                 
                   ( 
                   
                     Eq 
                     . 
                     
                         
                     
                     ⁢ 
                     1 
                   
                   ) 
                 
               
             
           
         
       
     
     Matrix elements S ij  of the similarity matrix SM are defined as similarity scores between content images  220   i  and  220   j , where i and j are integers and i+j=M. In the similarity matrix SM, each content image  220  forms a diagonal matrix element, and similarity scores of the content images  220  one versus another form non-diagonal matrix elements. 
     Diagonal matrix elements (i.e., matrix elements S ii  or S jj ) relate to similarity scores of the respective content images versus themselves and, as such, are unity matrix elements (i.e., matrix elements which numerical value is equal to 1). Correspondingly, since similarity scores S ij  and S ij  for the respective content images  220   ij  and  220   ji  are equal to one another, the similarity matrix  300  is a symmetric matrix, and numerical values of the non-diagonal matrix elements are disposed in a range from 0 to 1. 
     To determine the similarity score between the content image  220   i  and  220   j , an image disparity map is calculated for these images using a respective block matching algorithm. Using cost functions such as, for example, a mean absolute difference (or L 1  error) or a mean square error (or L 2  error), the image disparity map identifies disparity between pre-selected elementary blocks of pixels in the content images  220   i  and  220   j  as a weighted sum of the one-to-many, one-to-none, and matching error correspondences between the blocks of pixels. 
     These types of correspondences are expressed using terms of the Levenshtein algorithm as follows: (i) one-to-many correspondence between the elementary blocks is asserted as an equivalent of an Insertion term, (ii) one-to-none correspondence between the elementary blocks is asserted as an equivalent of a Deletion term, (iii) partial matching between the elementary blocks is asserted as an equivalent of a Substitution Error term, and (iv) a PED between the compared images is asserted as an equivalent of a Levenshtein&#39;s Edit Distance. 
     Herein, the term “one-to-many correspondence” relates to an elementary block matching, with a cost function smaller than a first pre-determined threshold Q 1 , two or more elementary blocks of the other image. Accordingly, the term “one-to-none correspondence” relates to an elementary block having no match among the elementary blocks of the other image (i.e., elementary block which cost function, with respect to the elementary blocks of the other image, is greater than a second pre-determined threshold Q 2 ). The term “partial matching” relates to the elementary blocks which cost functions, with respect to the elementary blocks of the other image, are disposed between Q 1  and Q 2 , i.e., Q 1 ≦Q≦Q 2 . 
     Referring back to  FIG. 2 , the content images  220  may be compared to or searched for an exemplary query image  210  or one another, when the query image is selected from the content images. Illustratively, each of the content images  220  depicts a respective object  225  that is compared to a target  215  depicted in the query image  210 . Generally, the target  215  and objects  225  are depicted surrounded by live or material elements of their respective conventional habitats, conditions, or environments. For a purpose of graphical clarity, in the images  210  and  220  such elements are not shown. 
     Herein, the method  100  is discussed referring to the content and query images depicting a single object (content images  220 ) or a single target (query image  210 ). In alternate embodiments, content and query images depicting several such objects or targets may similarly be compared using processing steps of the method  100 . 
     In the depicted exemplary embodiment, the query and content images  210 ,  220  are digitized 2D images having the same digital resolution (i.e., number of pixels per unit of area), and their graphical contents (i.e., target  215  and objects  225 ) have approximately the same physical dimensions, or scale factors. 
     Generally, at least a portion of these properties in available samples of the query and content images may differ from one another or at least one of the query and content images  210 ,  220  may be a portion of a larger image plane. In operation, respective properties of such query and content images are normalized. 
     In particular, a normalization process may adjust scale factors or digital resolution of the query or content images, equalize or approximately equalize physical dimensions of particular elements in the images or the images themselves, produce copies of the query and content images having different digital resolutions, and the like. Such normalization of the images increases probability and reduces computational complexity of recognizing the target  215  in graphical contents of the content images  220 . 
     The query and content images  210 ,  220  may be compared using a query vector V, 
                   V   =     [           V     q   ⁢           ⁢   1                 V     q   ⁢           ⁢   2               --             V   qM           ]             (     Eq   .           ⁢   2     )               
or an adjusted query vector V ADJ  calculated as a product of the vector V and the inverse similarity matrix SIM, i.e.,
 
 V   ADJ   =V ·( SIM ).  (Eq. 3)
 
     Herein the inverse similarity matrix SIM is a matrix that, when multiplied by the similarity matrix SM, forms a unitary diagonal identity matrix IM, i.e.,
 
( SIM )·( SM )= IM,   (Eq. 4)
 
and elements S qk  of the query vector V are selectively defined as similarity scores between the query image  210  and a respective content image  220   k , where k is an integer in a range from 1 to M.
 
     In a further embodiment, the query image  210  may be compared to the content images  220  at least a portion of which is morphed, using respective graphics software, to examine how such variations relate to the similarity scores between the target  215  and the objects  225 . In particular, such graphics software may produce morphed content images  220  where lighting conditions, poses, or attributes (for example, clothing, hand-held or wearable objects, and the like) of the objects  225  are selectively modified. 
     In another embodiment, a plurality of the query images  210   n , where n is an integer and n&gt;1, may similarly be compared to the content images  220 . In yet another embodiment, a plurality of thresholds T may be defined to identify particular groups of the content images (for example, groups which similarity scores with the respective query image(s)  210  correspond to pre-selected ranges of the similarity scores). 
     Referring to  FIG. 3 , the content images  220  are indexed, or systemized, using an image search engine (ISE)  300 . The ISE  300  is generally a computer program that may be executed on a computer terminal  500  (discussed in reference to  FIG. 5  below) such as, for example, a general purpose computer, a workstation, or a server. In one embodiment, the ISE  300  generally includes an object identifier module  310 , a generator  320  of matrices SMs and/or SIMs, an image indexing module  330 , and a database  340  of graphical information. 
     In the depicted embodiment, the object identifier module  310  is adapted to identify acquired content images  220  and text documents of the multimedia content. In further embodiments, the object identifier module  310  may also identify a particular graphical content, for example, images of humans, vehicles, and the like. 
     Using the generator  320 , the acquired content images  220  are normalized and the matrices SM and SIM are produced. In some embodiments, using certain pre-determined strategies, the content images  220  are optionally morphed and the matrices SM and SIM for such morphed images are also produced. 
     The image indexing module  330  generally performs docketing, analysis, and systemization of the matrices SM and SIM to define clusters, or classes, of particular types of images, such as, for example, people, cars, scenery, and the like. 
     The database  340  contains the content images  220  and data produced by the object identifier module  310 , generator  320 , and image indexing module  330 . In some embodiments, to accelerate efficiency of particular searches, portions of such data (for example, data corresponding to the multimedia content acquired within specific time interval, relating to specific geographical region, and the like) may form, temporarily or permanently, independently searchable sub-databases. 
     The database  340  and such sub-databases may be searched for particular query images  210  using, for example, techniques disclosed in commonly assigned U.S. patent application Ser. No. 11/619,104, and by the commonly assigned U.S. patent application by C. Podilchuk entitled “Method and System for Searching a Database of Graphical Data” simultaneously filed herewith on this date, the contents of which are herein incorporated by reference. 
     At step  120 , referring to  FIG. 4 , the method  100  develops a multimedia user graphical interface (MGUI)  400 . The MGUI  400  is generally a computer program that, in operation, enables a user to utilize computational resources of the ISE  300 . Features of the MGUI  400  may be activated using a conventional pointing device, such as a computer mouse, touch pad, and the like. 
     Specifically, the MGUI  400  allows the user to search the multimedia content for the query data including (i) one or more query images or (ii) a combination of one or more query images and one or more query texts, such as key words or annotations to particular content or query images. In further embodiments, the MGUI  400  may also facilitate searching the multimedia content for particular image elements (for example, specific face or eye pattern, scenery, and the like), administering manipulating, resizing, or morphing of the images, or perform searches using Boolean operators, among other search strategies. 
     In the depicted exemplary embodiment, the MGUI  400  includes a query image field  410 , a key word search field,  420 , a search menu field  430 , a toolbar field  440  (N tools are shown), a working area field  450 , and a search results field  460 . Illustratively, the fields  450  and  460  are provided with scroll bars  452  and  462  facilitating viewing of large numbers of query and content images. 
     The query image field  410  includes query areas  412  for the selected query images  210  and logic areas  414  for Boolean operators establishing particular logical relationships between the query images  210  (two areas  412  and one area  414  are shown). The respective query images  210  may be placed in the query areas  412  (for example, dragged using a computer mouse) from the working area field  450  including a plurality of pre-selected query images. 
     In one embodiment, the pre-selected query images form a searchable library (i.e., database) of such images and may be retrieved from the library to populate the working area field  450  or the query areas  412 . Searches based on the query images  210  may further be supplemented with or replaced by key word searches. For example, at least some of query images  210  or content images  220  may be replaced with annotated texts describing the contents of these images. 
     The content images  220 , which similarity scores with the respective query data (i.e., query image(s)  210 , query text(s), or combinations thereof) exceeds a pre-selected threshold T, are shown in the search results field  460  (illustratively, in the depicted embodiment, the Boolean operator  414  is “AND”). In one embodiment, the search results field  460  includes areas  464  containing similarity scores of the respective content images and identifying a content image having a highest similarity score with the query data. Such and other specific features of the MGUI  400  may be initiated using the respective tools of the toolbar field  440 , commands listed in the search menu field  430 , a computer pointing device, or a combination thereof. 
     At step  130 , in operation, a multimedia content of interest is acquired by a user of the respective computer terminal  500 . 
     At step  140 , using the ISE  300 , a graphical content of the acquired multimedia content is processed, as discussed above in step  110  in reference to the content images  220 . 
     At step  150 , using the MGUI  400 , the user selectively provides search instructions from the search menu  430 , enables tools of the toolbar  440 , and defines the query data, i.e., selects one or more the key images (i.e., query images  210 ), places them in the query image field  410 , and, in some embodiments, enters in the key word search field  420  a query text including one or more user-defined key words. 
     At step  160 , following the user-selected instructions, the method  100  uses the ISE  300  to perform searching of the multimedia content for the query data of step  150  and, using the MGUI  400 , displays search results. Upon reviewing the search results, the user may modify the search instructions or the query data and repeat the search of the multimedia content using a new set of instructions or the query data. 
     In exemplary embodiments, the method  100  may be implemented in hardware, software, firmware, or any combination thereof in a form of a computer program product comprising computer-executable instructions. When implemented in software, the computer program product may be stored on or transmitted using a computer-readable medium adapted for storing the instructions or transferring the computer program product from one computer to another. 
       FIG. 5  is a high-level, schematic diagram of an exemplary apparatus  500  using the method  100 . The apparatus  500  is generally a computer terminal coupled to a network  550  (for example, the Internet, a wide area network (WAN), a local area network (LAN), and the like), which interconnects pluralities of users  560  and sources  560  of multimedia content. 
     Illustratively, the apparatus  500  is a computer (e.g., general purpose computer or a workstation) comprising a graphics-enabled display  510 , a processor  520 , and a memory unit  530 . In one embodiment, the memory unit  530  includes a MGUI computer program  532 , the ISE  300 , a text search engine  534 , a database  536  of query data, a database  538  of acquired multimedia content (for example, multimedia content acquired from the source(s)  570 ), and an image comparing program  540 . 
     When executed by the processor  520 , the program MGUI computer program  532 , the ISE  300 , and the text search engine  534 , together, facilitate processing steps of the method  100 . In particular, the MGUI computer program  532  enables the MGUI  400 , and a graphical portion of the acquired multimedia content is processed using the ISE  300 . In operation, the MGUI  400  allows a user to search the processed multimedia content as discussed above in reference to  FIGS. 3-4 . 
     In alternate embodiments, at least some of the MGUI computer program  532 , ISE  300 , text search engine  534 , or image comparing program  540 , as well at least one of the databases  536  or  538  may reside on a removable magnetic or optical media (e.g., flash memory card or drive, compact disc (CD), DVD, Blu-Ray and/or HD optical disks and the like), a server (not shown) of the network  150 , or a remote computer (not shown) coupled to the network  150  or any other storage medium (not shown) coupled to the network  150 , including magnetic media such has hard disk drives, tapes, and the like. In other embodiments, some query images  210  may be selected from images contained in the database  538  (i.e., from content images  220 ). 
     Although the invention herein has been described with reference to particular illustrative embodiments, it is to be understood that these embodiments are merely illustrative of the principles and applications of the present invention. Therefore numerous modifications may be made to the illustrative embodiments and other arrangements may be devised without departing from the spirit and scope of the present invention, which is defined by the appended claims.