Abstract:
The proliferation of digital devices has favored an explosion of the amount of image data stored by a user, and it is quite easy for a user to end up with many image duplicates in the user&#39;s image library. Prior art solutions can still be optimized with regard to detection of duplicate images in data storage. Notably, user intervention is to be restricted. A correspondence is detected between a first and a second image of the collection, and metadata is associated with the second image that characterizes the detected correspondence. Then, a predetermined image collection management action is applied to second images according to the associated metadata.

Description:
FIELD OF INVENTION 
       [0001]    The present invention relates to the field of management of image data in data storage. In particular, the present invention relates to a method and device for automatic detection of duplicate images in data storage and corresponding device, which method and device are particularly efficient with regard to the automatic management of large amounts of dispersed image data. 
       TECHNICAL BACKGROUND 
       [0002]    The proliferation of digital devices that comprise a photo camera has favored an explosion of the volume of image data stored by a user, and it is quite easy for a user to end up with many image duplicates in the user&#39;s image library. 
         [0003]    This situation can be even worse in the case of a home network environment, where several users can add images to an image library, the library possibly being physically distributed on several, dispersed storage devices, for example on hard drives of different PCs, on a NAS (Network Attached Storage), on USB keys, etc.). 
         [0004]    The reasons why an image library can end up by containing many duplicate images are diverse. Unintentional duplicate images are produced through copy actions. For example, a user who organizes photos in different directories does not move the photos, which would have been appropriate, but unintentionally rather copies them; a user that wishes to transfer photos via e-mail adapts the photo resolution for including them in his e-mail but unintentionally keeps the low-resolution copies; a user that views images with a viewer application modifies these by rotation, or modification of color and contrast and unintentionally keeps the unmodified copy in addition to the modified copy. Other copy actions are intentional and are due to the fact that the user has no longer an overview of the data that he has stored, a situation that is getting worse when the user has multiple storage devices and many images, and gets even worse when multiple users add and copy data to the multitude of images stored. The user, knowing that he does not have a clear overview of the images stored, worsens this situation by preferring finally to copy rather than to move or replace images, by fear of deleting them. This creates a situation where the user no longer knows which images are disposable copies and which are not. 
         [0005]    In all these scenarios, a duplicate detection tool can be necessary, or at least useful, to assist the user with the cleanup or management tasks of the user&#39;s image library. 
         [0006]    Prior-art detection of image duplicates detects duplicates according to criteria such as checksum data, creation data, file name, file size, and image format. Such criteria allows only detection of identical copies of an original image but not the copies that have been slightly or largely modified in order to enhance the visual perception of the image on a particular display. Moreover, if more than one criterion for the duplicates detection is specified, duplicates are detected that comply with any of the selected criteria and user intervention is needed to determine if the user wishes to delete the detected duplicates from the image library. Other duplicate detection methods are capable to detect near-duplicate images by comparing image pixel data. A user is required to specify a matching percentage of pixel data of two images to mark and detect an image as being a duplicate image. The detection then detects these near-duplicates as it detects strictly identical images without distinction. 
         [0007]    Thus, prior art solutions can still be optimized with regard to detection of duplicate images in data storage. Notably, a method is needed that reduces user intervention to the strictly needed. 
       SUMMARY OF THE INVENTION 
       [0008]    The invention reduces the complexity of maintaining a collection of images. 
         [0009]    When near duplicates are found according to the method of the invention, associated metadata resumes the reason why these are considered as being duplicates (exact, near, far), for example low resolution copy, zoom, copy stored in a backup zone, etc. A set of management action rules that are associated to this metadata then allows managing the image library automatically according to these management action rules. Automatic management actions are taken for images which are considered as corresponding by the method of the invention based on the discussed metadata and associated rules. These management actions are for example delete, keep, or replace-by-link to the original image. The latter option can be required when the existence of identical copies is to be avoided for reasons of efficiency. 
         [0010]    The discussed advantages and other advantages not mentioned here, that make the device and method of the invention advantageously well suited for automatic management of a collection of images, will become clear through the detailed description of the invention that follows. 
         [0011]    In order to automatically manage a collection of images, the invention proposes a method comprising a step of detection of correspondence between a first image and at least a second image in the collection of images according to at least one criterion for correspondence between the first image and the at least one second image, and a step of association of metadata to the at least a second image when the correspondence is detected, the metadata being representative of a relation between the first image and the at least one second image and comprising the at least one criterion for correspondence between the first image and the at least one second image which has lead to the detection of correspondence. 
         [0012]    According to a variant embodiment of the invention, the method further comprises a step of automatic determination and application of one of a set of predetermined actions for processing of the at least one second image according to the associated metadata. 
         [0013]    According to a variant embodiment of the invention, the metadata further comprises information representative of a level of correspondence between the first image and the at least one second image. 
         [0014]    According to a variant embodiment of the invention, the set of predetermined actions comprise an action of replacement of the at least one second image with a link to the first image. 
         [0015]    According to a variant embodiment of the invention, the set of predetermined actions comprise an action of deletion of the at least one second image. 
         [0016]    According to a variant embodiment of the invention, the set of predetermined actions comprise an action of transferring the at least one second image to a storage. 
         [0017]    According to a variant embodiment of the invention, the set of predetermined actions comprise an action of renaming the at least one second image. 
         [0018]    The invention also concerns a device for automatic management of a collection of images, the device comprising means for detection of correspondence between a first image and at least a second image in the collection of images according to at least one criterion for correspondence between the first image and the at least one second image, and means for association of metadata to the at least one second image when the correspondence is detected, the metadata being representative of a relation between the first image and the at least one second image and comprising the at least one criterion for correspondence between the first image and the at least one second image which has lead to the detection of correspondence. 
     
    
     
       LIST OF FIGURES 
         [0019]    More advantages of the invention will appear through the description of particular, non-restricting embodiments of the invention. The embodiments will be described with reference to the following figures: 
           [0020]      FIG. 1  shows a method for association of metadata to one or more images when a correspondence is detected. 
           [0021]      FIG. 2  shows a detection of correspondence according to a variant embodiment of the invention. 
           [0022]      FIG. 3  shows an application of actions associated to the detection according to the invention. 
           [0023]      FIG. 4  illustrates the notion of normalized fingerprint distance (NFD) between two images and the relation between NFD and discussed thresholds. 
           [0024]      FIG. 5  shows an example device implementing a variant embodiment of the invention. 
       
    
    
     DETAILED DESCRIPTION OF THE INVENTION 
       [0025]      FIG. 1  shows a method for association of metadata to one or more images when a correspondence is detected. 
         [0026]    In a first initialization step  100 , variables are initialized for the functioning of the method. When the method is implemented in a device such as device  400  of  FIG. 4 , this may comprise copying of data from non-volatile memory to volatile memory and initialization of memory. In a next step  101 , a first image, “a”, is fetched in data storage. In a next step  102 , a second image, “b”, is fetched from data storage. In a step  104 , a detection of correspondence between the two images is done according to different criteria. In a test step  105 , it is determined if such detection is affirmative (i.e. a correspondence between the two images is detected according to one or more of the criteria for correspondence) or not. If the detection is affirmative, metadata is associated to the second image in a step  107 . This metadata comprises information on a relation between the second and the first image and information about the one or more criteria of correspondence that has lead to the detection of the correspondence. When no correspondence can be detected, step  107  is not executed. In a next step  110 , it is verified if there are any second (“b”) image left that have not been compared to the “a” image. If so, a next second (“b”) image is selected in step  102  and the steps of detection (dotted rectangle  113 ) are repeated. If not, it is verified in a step  111  if there are any first images (“a”) left which have not yet been processed by the detection method of the invention. If so, a next first (“a”) image is selected in step  101 , a next second “b” image is selected in step  102  and the steps of detection ( 113 ) are repeated. If all first “a” images of the image collection in data storage have been processed by the method of the invention, point  112  is reached, which links the detection method of the invention to an automatic determination and application of one of a set of predetermined actions for processing of all second images (“b” images) according to the associated metadata, described by means of  FIG. 3 . 
         [0027]    According to the described embodiment, the images in the data storage are first completely processed by the detection method, before being processed by the automatic determination and application of predetermined actions. According to a variant embodiment, the latter automatic determination is done immediately following the discussed association of metadata. This variant has an advantage in processing time because the mass of images to be processed by the detection method can be reduced; each time when images that are deleted by delete actions the mass of images to process is reduced. An intelligent selection method for first (“a”) and second “b” images can further reduce the processing time needed. For example, a step is added to the method that excludes detection of correspondence of two images that have already been passed through the detection process. According to this variant, the detection method associates metadata to each image that has been completely processed by the detection process which metadata indicates that the image has already been processed as a first “a” image, and in each next iteration of the detection method where a next first “a” image is selected, already processed first “a” images are not being processed in the detection method again, i.e. they are not selected as second (“b”) images. 
         [0028]      FIG. 2  shows a detection of correspondence according to a particular embodiment of the invention. The method starts at point  103  and ends at point  109  and corresponds to a detailed view of the detection method  113  of  FIG. 1 . Variant embodiments of the method of the invention are possible. Notably the steps of the method can be executed in a different order; more or less criteria (and thus tests) can be added to/removed from the detection of correspondence while still using the method of automatic management of a collection of images according to the invention. 
         [0029]    In a first test step  200 , it is determined if a checksum calculated over the first (“a”) image is the same as a checksum calculated over the second (“b”) image. Checksum calculation is done through known methods, such as SHA (Secure Hash Algorithm) or MD5 (Message Digest 5). If the calculated checksum is the same, the two images are considered as being identical and a decisional step  201  is done, in which it is determined if the location where the second (“b”) image is stored is a location for storage of backup. If so, metadata is added in step  203  to the identical second (“b”) image that indicates that the second image is a backup copy of the first image. If not, metadata is added in step  202  to the identical second image that indicates that the second image is an identical copy. As will be handled further on, it is possible to automatically delete identical images that are not backup copies by execution of actions associated to metadata. If, as an outcome of test step  200  it is on the contrary determined that the checksums of the first and the second images are different, a test step  204  is executed, in which it is determined if a normalized distance d between fingerprints of the first “a” image fp(a) and of the second “b” image fp(b) is below a first threshold th 2  d(fp(a),fp(b)) &lt;th 2 ; th 2  is a threshold that is chosen such that if d(fp(a),fp(b)) &lt;th 2 , the second image “b” can be considered as being a modified copy of the first image “a”. If d(fp(a),fp(b)) is not inferior to th 2 , the first and the second images are considered as being different by the method of the invention and the method continues with step  109 . But if d(fp(a),fp(b)) is inferior to th 2 , we are dealing with a modified copy and it can be determined in following steps how the difference between the two images can be characterized. Notably, in a next step  205 , the previously calculated normalized fingerprint distance is compared with a next threshold th 1 . If d(fp(a),fp(b)) is superior to th 1 , the second image “b” is characterized in a step  206  as being a largely modified copy of the first image “a” and corresponding metadata is associated to the second image for example according to table 1, first row (LMC, &lt;path&gt;/a). If on the contrary d(fp(a),fp(b)) is inferior to th 1 , a test step  207  is executed, in which it is verified if the first image (“a”) has the same resolution as the second image “b”. Image resolution can be compared based on prior-art file metadata that is present in prior-art file systems, such as EXIF (Exchangeable Image File Format). If the image resolutions differ, a step  208  is executed in which metadata is associated to the second image that indicates that the second image is a different resolution copy of the first image; e.g. a tag ‘DRC’ is added to metadata associated to image b together with the storage path of image a: (DRC, &lt;path&gt;/a). If on the contrary the resolution of the first image differs from that of the second image, a next test step  209  is executed, in which the encoding methods of the two images are compared. This comparison is done according to known methods as for example by comparing file extensions (e.g. *.jpg, *.tiff). If the two images are encoded with a different encoding method, a step  210  is executed in which corresponding metadata is associated to the second image, e.g. a tag ‘DEC’ is added to image b together with the storage path of image a: (DEC, &lt;path&gt;/a). If on the contrary the two images are encoded with different encoding methods, step  211  is executed in which metadata (SMC, &lt;path/a&gt;) is associated to the second image. After steps  202 ,  203 ,  206 ,  208 ,  210  and  211 , step  109  is executed, returning to  FIG. 1 , where the steps of the method are iterated until all images have been processed. Table 1 hereunder resumes example types of metadata tags, their meaning and their means of determination. 
         [0000]    
       
         
               
               
               
             
           
               
                 TABLE 1 
               
               
                   
               
               
                 Tag 
                 Meaning 
                 Means for determination 
               
               
                   
               
             
             
               
                 IDC 
                 Image ‘b’ is an Identical Copy of 
                 Checksum 
               
               
                   
                 image ‘a’ 
               
               
                 BC 
                 Image ‘b’ is a Backup Copy of 
                 Checksum and storage 
               
               
                   
                 image ‘a’ 
                 location 
               
               
                 LMC 
                 Image ‘b’ is a Largely Modified 
                 Normalized image 
               
               
                   
                 Copy of image ‘a’ 
                 fingerprint distance 
               
               
                   
                   
                 (th1 &lt; NFD &lt; th2) 
               
               
                 DRC 
                 Image ‘b’ is a Different Resolution 
                 Image resolution 
               
               
                   
                 Copy of image ‘a’ 
               
               
                 DEC 
                 Image ‘b’ is a Different Encoding 
                 Image encoding method 
               
               
                   
                 Copy of image ‘a’ 
               
               
                 SMC 
                 Image ‘b’ is a Slightly Modified 
                 Normalized image 
               
               
                   
                 Copy of image ‘a’ 
                 fingerprint distance 
               
               
                   
                   
                 (NFD &lt; th1) 
               
               
                   
               
             
          
         
       
     
         [0030]      FIG. 3  shows an application of actions associated to the detection according to an example embodiment of the invention. According to a variant embodiment of the invention as illustrated in  FIG. 3 , these actions are done following the execution of the detection steps of  FIGS. 1 and 2  (see pointer  112  in  FIGS. 1 and 3 ). According to yet another variant embodiment, actions are executed as soon as metadata has been associated to an image, which is advantageous in terms of resources used for execution of the method. This latter variant is possible for actions that are not delete actions, such as actions creating a link, the creation of the link reduces the amount of data to be processed by subsequent iterations of the method. 
         [0031]    In a first step  300 , a next second image is chosen (“b” image). Its associated metadata is read in step  301  and in a step  302  an action is determined for the associated metadata, for example, according to the actions as defined in table 3. In a test  303 , it is determined if the action associated to the metadata is the creation of a file link. If so, a file link is created in a step  306 , from the second image to the first image. The metadata remains associated to the link, so that for future iterations of the method of the invention, a trace is kept. If the action is not a create link, it is verified in a test  304  if the action is a delete image; if so, the second image is deleted in a step  307 . If the action is not a delete image action neither, it is verified in a test  305  if the action is an ask action, and if so, the second image is transferred to a temporary storage in a step  308 , where images are stored for which a user decision is needed. If not, the action steps are repeated with a selection of a next second image in step  300 . This is also the case after steps  306 ,  307  and  308 . The processing ends when all images have been processed. 
         [0032]    Variant embodiments of the discussed application of actions are possible. Notably the steps of the method can be executed in a different order; more or less actions (and thus tests) can be added/removed. 
         [0033]    The method of the invention can be applied as a background task or as a clean-up tool that is more or less regularly executed. The method can be enhanced with a monitoring feature that monitors creation, deletion and copying of images so as to keep the metadata updated as soon as a creation, deletion or copying is executed. 
         [0034]    Table 2 hereunder illustrates an example lookup table for looking up actions that are associated to a tag type. The tags types are those of the example implementation illustrated by means of  FIGS. 1 and 2 . For a tag type ‘IDC’ (Identical Copy) the associated action executed by the method of the invention is to replace the second image (“b”) by a link to the first image (“a”). When a second image has a metadata tag BC or LMC, no action is associated since it is wished to keep the second image. When the second image has a tag ‘DRC’, the associated action is to delete the second image only when the second image has a lower resolution than the first image. 
         [0035]    When the second image has an associated metadata tag ‘DEC’, the associated action is to delete the second image only if the first image is of the ‘png’ encoding type. When the second image has an associated tag ‘SMC’, the associated action is to ask the user to decide what to do. According to a variant embodiment of the invention, images with associated action ‘Ask’ are grouped in temporary storage and the user is only bothered once for a review of all images in this temporary storage with associated action ‘Ask’ for which the user&#39;s decision is required. Such a review can for example be done through a visual presentation of the corresponding first and second images image pair and with a possibility for un-checking a ‘keep’ checkbox related to each second image of the image pair. 
         [0036]    According to a variant embodiment of the invention, multiple metadata tags can be associated to a single image. For example, a same image can have both DRC and DEC tags, meaning that the image is a different resolution copy but also a different encoding copy. In this case, the steps of the method are not executed as depicted in  FIG. 2 , but in parallel or in a different order. This variant embodiment has the advantage to allow a more extensive association of metadata, which is advantageous for fine-tuning of the associated actions. Using the previous example of an image that has both DRC and DEC tags and referring to table 2, an associated action is to only delete the image if both action conditions apply, i.e. to delete the second image the resolution of the second must be lesser than that of the first image AND the first image is encoded according to the PNG (Portable Network Graphics) encoding method. 
         [0037]    According to a variant embodiment of the invention, the actions are user-configurable. 
         [0000]    
       
         
               
               
               
             
           
               
                   
                 TABLE 2 
               
               
                   
                   
               
               
                   
                 Tag 
                 Action 
               
               
                   
                   
               
             
             
               
                   
                 IDC 
                 Replace b by link to a 
               
               
                   
                 BC 
                 None 
               
               
                   
                 LMC 
                 None 
               
               
                   
                 DRC 
                 Delete b if res (b) &lt; res (a) 
               
               
                   
                 DEC 
                 Delete b if enc (a) = *.png 
               
               
                   
                 SMC 
                 Ask 
               
               
                   
                   
               
             
          
         
       
     
         [0038]      FIG. 4  illustrates the notion of normalized fingerprint distance (NFD) between two images and the relation between NFD and discussed thresholds. To be able to classify an image by its differences with another image, NFD is one of the ‘tools’ used by the method. Two fixed thresholds (th 1  and th 2 ) are used representing certain values of normalized distances between fingerprint vectors of the second (‘b’) image and the first (‘a’) image. This normalized distance can be expressed as: 
         [0000]    
       
         
           
             
               Δ 
                
               
                 ( 
                 
                   a 
                   , 
                   b 
                 
                 ) 
               
             
             = 
             
               
                  
                 
                   a 
                   - 
                   b 
                 
                  
               
               
                  
                 
                   a 
                   + 
                   b 
                 
                  
               
             
           
         
       
     
         [0039]    Where ∥.∥ represents an L 2  norm of a vector, i.e. its Euclidian distance. 
         [0040]    An image fingerprint, constructed according to known prior-art methods, can be represented as an n-dimensional vector. “n” can have a value of hundred or even thousand. In our example and for simplicity of illustration, we assume that n=2. The center of  FIG. 4  ( 400 ) represents the image fingerprint of image ‘a’, i.e. fp(a). The zone  401  in the first circle around fp(a) corresponds to the fingerprints of the ‘b’ images whose distance to the fingerprint of the ‘a’ image is lower than the first threshold th 1  ( 402 ), and represents ‘b’ images that have been slightly modified with regard to the ‘a’ image. Zone  403  in the second circle around fp(a) corresponds to fingerprints of ‘b’ images whose distance to the fingerprint of the ‘a’ image is higher than the first threshold th 1  ( 402 ) but lower than the second threshold th 2  ( 404 ), and represents ‘b’ images that have been largely modified with regard to the ‘a’ image. The zone  405  outside of the second circle corresponds to fingerprints of ‘b’ images whose distance to the fingerprint of the ‘a’ image is higher than the second threshold th 2  ( 404 ), and represents ‘b’ images that can be considered to be different with regard to the ‘a’ image. 
         [0041]      FIG. 5  shows an example device  500  that implements a variant of the method of the invention. The device  500  comprises the following components, interconnected by a digital data- and address bus  514 :
       a processing unit  511  (or CPU for Central Processing Unit);   a non-volatile memory NVM  510 ;   a volatile memory VM  520 ;   a clock  512 , providing a reference clock signal for synchronization of operations between the components of the device  500  and for timing purposes;   a network interface  513 , for interconnection of device  500  to other devices connected in a network via connection  515 .       
 
         [0047]    It is noted that the word “register” used in the description of memories  510  and  520  designates in each of the mentioned memories, a low-capacity memory zone capable of storing some binary data, as well as a high-capacity memory zone, capable of storing an executable program, or a whole data set. 
         [0048]    Processing unit  511  can be implemented as a microprocessor, a custom chip, a dedicated (micro-) controller, and so on. Non-volatile memory NVM  510  can be implemented in any form of non-volatile memory, such as a hard disk, non-volatile random-access memory, EPROM (Erasable Programmable ROM), and so on. 
         [0049]    The Non-volatile memory NVM  510  comprises notably a register  5201  that holds a program representing an executable program comprising the method according to the invention. When powered up, the processing unit  511  loads the instructions comprised in NVM register  5101 , copies them to VM register  5201 , and executes them. 
         [0050]    The VM memory  520  comprises notably:
       a register  5201  comprising a copy of the program ‘prog’ of NVM register  5101 ;   a register  5202  comprising an iterator variable allowing an iteration over the first (‘a’) images;   a register  5203  comprising an iterator variable allowing an iteration over the second (‘b’) images;   a register  5204  for storing of one or more references to backup storage, so that the method can recognize when a storage location is a backup storage location;   a register  5205  for storing of the first and the second thresholds for NFD calculation;   a register  5206  holding a table of metadata tags that is to be used for association of metadata.       
 
         [0057]    A device such as device  500  is suited for implementing the method of the invention of automatic management of a collection of images, the device comprising 
         [0058]    means for detection (CPU  511 , VM register  5205 ) of correspondence between a first image and a second image(s) in said collection of images according to a criterion(s) for correspondence between said first image and the second image(s); 
         [0059]    means for association of metadata (CPU  511 , register  5206 ) to the second image(s) when said correspondence is detected, the metadata being representative of a relation between the first image and the second image(s) and comprising the criterion(s) for correspondence between the first image and the second image(s) which has lead to the detection of the correspondence. 
         [0060]    Other device architectures than illustrated by  FIG. 5  are possible and compatible with the method of the invention. Notably, according to variant embodiments, the invention is implemented as a pure hardware implementation, for example in the form of a dedicated component (for example in an ASIC, FPGA or VLSI, respectively meaning Application Specific Integrated Circuit, Field-Programmable Gate Array and Very Large Scale Integration), or in the form of multiple electronic components integrated in a device or in the form of a mix of hardware and software components, for example a dedicated electronic card in a personal computer.