Methods and systems for determining a perceptual similarity between images

Abstract

Systems, methods and computer program products for determining perceptual similarity between independent images are described. The described systems, methods and computer program products use a similarity distance to determine the perceptual similarity between a first image having a first arrangement of pixels and a second image having a second arrangement of pixels. A processor can determine a first image array corresponding to the first arrangement of pixels and a second image array corresponding of the second arrangement of pixels. The processor can generate a first pixel group set based on the first image array and a second pixel group set based on the second image array. A plurality of pixel group pairs can be generated, and each pixel group pair can be associated with a corresponding pixel group pair distortion. The similarity distance between the first image and the second image can be determined based on the plurality of pixel group pair distortions.

1 . A method for determining a measure of perceptual similarity between a first digitized image having a first arrangement of pixels, each pixel in the first arrangement of pixels having a first pixel value, and a second digitized image having a second arrangement of pixels, each pixel in the second arrangement of pixels having a second pixel value, using a similarity distance determined by a computer module having a memory and a processor module comprising one or more processors, the method comprising:
 operating the processor module to determine a first image array having M pixels by N pixels corresponding to the first arrangement of pixels, where M and N are positive integers;   operating the processor module to determine a second image array having M pixels by N pixels corresponding to the second arrangement of pixels;   operating the processor module to generate a first pixel group set comprising a first plurality of pixel group arrays based on the first image array wherein each pixel group array in the first plurality of pixel group arrays comprises at least two pixels;   operating the processor module to generate a second pixel group set comprising a second plurality of pixel group arrays based on the second image array wherein each pixel group array in the second plurality of pixel group arrays comprises at least two pixels;   operating the processor module to generate a plurality of pixel group pairs, each pixel group pair comprising a first comparison pixel group array from the first plurality of pixel group arrays in the first pixel group set and a second comparison pixel group array from the second plurality of pixel group arrays in the second pixel group set;   operating the processor module to associate each pixel group pair with a pixel group pair distortion, the pixel group pair distortion being a distortion measure between the first comparison pixel group array and the second comparison pixel group array in that pixel group pair; and   operating the processor module to determine the similarity distance between the first digitized image and the second digitized image based on the plurality of pixel group pair distortions.   
     
     
         2 . The method as defined in  claim 1  further comprising
 operating the processor module to identify a first plurality of pixel arrays based on the first image array, each pixel array having a first number of pixels; 
 operating the processor module to generate a first pattern image array having the first number of pixels; and 
 operating the processor module to generate the first plurality of pixel group arrays by, for each pixel array in the first plurality of pixel arrays, superimposing the first pattern image array onto that pixel array such that the first plurality of pixel group arrays comprises a corresponding pixel group array for each pixel array in the first plurality of pixel arrays, wherein superimposing the first pattern image array onto that pixel array comprises a matrix addition of each array element in that pixel array with a corresponding array element in the first pattern image array. 
 
     
     
         3 . The method as defined in  claim 2  wherein the first pattern image array is generated by:
 operating the processor module to identify a first plurality of pixel block arrays in the first image array with each pixel block array having k pixels by l pixels, where k is a positive integer divisor of M with no remainder and I is a positive integer divisor of N with no remainder; 
 operating the processor module to determine a first average pixel block array having k pixels by l pixels based on the first plurality of pixel block arrays, wherein each average pixel block array element in the first average pixel block array is determined based on an average value of an array element from each pixel block array of the first plurality of pixel block arrays having an array location corresponding to that average pixel block array element; and 
 operating the processor module to generate the first pattern image array based on the first average pixel block array. 
 
     
     
         4 . The method as defined in  claim 3  wherein the first pattern image array is k pixels by I pixels and corresponds to the first average pixel block array. 
     
     
         5 . The method as defined in  claim 3  wherein the first pattern image array comprises a plurality of pattern pixel block arrays, where each pattern pixel block array is k pixels by I pixels and each pattern pixel block corresponds to the first average pixel block array. 
     
     
         6 . The method as defined in  claim 1  further comprising
 operating the processor module to identify a first plurality of pixel block arrays in the first image array, with each pixel block array having k pixels by l pixels, where k is a positive integer divisor of M with no remainder and I is a positive integer divisor of N with no remainder; 
 operating the processor module to identify a second plurality of pixel block arrays in the second image array, with each pixel block array having k pixels by l pixels; 
 configuring the processor module to generate a set of related image arrays from an original image array using a set mapping, the set mapping comprising a plurality of pixel block array permutations, such that, for each pixel block array permutation there is a corresponding image array in the set of related image arrays, this corresponding image array being obtained by applying that pixel block array permutation to the original image array, and each related image array in the set of related image arrays has at least as many pixels as the original image array; 
 operating the processor module to generate the first pixel group set using the set mapping, such that the first pixel group set is a first set of related digitized images having a first plurality of related digitized image arrays, each related digitized image array being generated by applying one of the pixel block array permutations to the first plurality of pixel block arrays such that each of the related digitized image arrays comprises an arrangement of the pixel block arrays in the first plurality of pixel block arrays and each of the related digitized image arrays has at least as many pixels as the first image array; and 
 operating the processor module to generate the second pixel group set using the set mapping, such that the second pixel group set is a second set of related digitized images having a second plurality of related digitized image arrays, each related digitized image array being generated by applying one of the pixel block array permutations to the second plurality of pixel block arrays such that each of the related digitized image arrays comprises an arrangement of the pixel block arrays in the second plurality of pixel block arrays and each of the related digitized image arrays has at least as many pixels as the second image array. 
 
     
     
         7 . The method as defined in  claim 6  further comprising
 operating the processor module to determine the plurality of pixel group pairs such that i) for each pixel group pair in the plurality of pixel group pairs, the first comparison pixel group array in that pixel group pair corresponds to one of the related digitized image arrays in the first plurality of related digitized image arrays and the second comparison pixel group array in that pixel group pair corresponds to one of the related digitized image arrays in the second plurality of related digitized image arrays, and ii) each of the related digitized image arrays in the first plurality of related digitized image arrays corresponds to the first comparison pixel group array in a pixel group pair in the plurality of pixel group pairs, and each of the related digitized image arrays in the second plurality of related digitized image arrays corresponds to the second comparison pixel group array in a pixel group pair in the plurality of pixel group pairs; 
 operating the processor module to associate each pixel group pair with a pixel group pair distortion, the pixel group pair distortion being a distortion measure between the first comparison pixel group array and the second comparison pixel group array in that pixel group pair; 
 operating the processor module to identify a lowest pixel group pair distortion based on the plurality of pixel group pair distortions; and 
 operating the processor module to determine the similarity distance between the first digitized image and the second digitized image based on the lowest pixel group pair distortion. 
 
     
     
         8 . The method as defined in  claim 7  wherein the lowest pixel group pair distortion is determined by:
 operating the processor module to generate a bipartite graph G, where G has a plurality of first vertices, each of the first vertices corresponding to one of the pixel block arrays in the first plurality of pixel block arrays, and a corresponding plurality of second vertices, each of the second vertices corresponding to one of the pixel block arrays in the second plurality of pixel block arrays; 
 operating the processor module to determine a plurality of matchings, where each matching is determined such that each of the first vertices is matched with a distinct corresponding one of the second vertices, and wherein each matching corresponds to one of the pixel group pairs; 
 operating the processor module to associate each matching with a matching weight, the matching weight being determined based on a sum of a plurality of vertex distortions, each vertex distortion in the plurality of vertex distortions corresponding to the distortion measure between one of the first vertices in the plurality of first vertices and the corresponding one of the second vertices in the plurality of second vertices; and 
 operating the processor module to identify a matching with a lowest matching weight and set the lowest matching weight as the lowest pixel group pair distortion in the plurality of pixel group pair distortions. 
 
     
     
         9 . The method as defined in  claim 8  wherein the matching with the lowest matching weight is identified by the processor module using a Blossom-V algorithm. 
     
     
         10 . The method as defined in  claim 1  further comprising
 operating the processor module to generate the first plurality of pixel group arrays by identifying a first plurality of pixel block arrays in the first image array, with each pixel block array having k pixels by l pixels, where k is a positive integer divisor of M with no remainder and I is a positive integer divisor of N with no remainder; and 
 operating the processor module to generate the second plurality of pixel group arrays by identifying a second plurality of pixel block arrays in the second image array, with each pixel block array having k pixels by l pixels. 
 
     
     
         11 . The method as defined in  claim 10  further comprising
 operating the processor module to determine the plurality of pixel group pairs such that
 i) for each pixel group pair in the plurality of pixel group pairs, the first comparison pixel group array in that pixel group pair corresponds to one of the pixel block arrays in the first plurality of pixel block arrays and the second comparison pixel group array in that pixel group pair corresponds to one of the pixel block arrays in the second plurality of pixel block arrays; 
 ii) each of the pixel block arrays in the first plurality of pixel block arrays corresponds to the first comparison pixel group array in a pixel group pair in the plurality of pixel group pairs, and each of the pixel block arrays in the second plurality of pixel block arrays corresponds to the second comparison pixel group array in a pixel group pair in the plurality of pixel group pairs; 
 
 operating the processor module to associate each pixel group pair with a pixel group pair distortion, the pixel group pair distortion being a distortion measure between the first comparison pixel group array and the second comparison pixel group array in that pixel group pairs; 
 operating the processor module to determine an average pixel group pair distortion based on the plurality of pixel group pair distortions; and 
 operating the processor module to determine the similarity distance between the first digitized image and the second digitized image based on the average pixel group pair distortion. 
 
     
     
         12 . The method as defined in  claim 11  wherein the average pixel group pair distortion is determined by:
 operating the processor module to determine at least one first distinct arrangement of pixels, wherein the at least one first distinct arrangement of pixels defines a first arrangement of pixels in one or more pixel block arrays in the first plurality of pixel block arrays; 
 operating the processor module to determine a first set of distinct pixel block arrays wherein the first set of distinct pixel block arrays comprises a first distinct pixel block array for each first distinct arrangement of pixels in the at least one first distinct arrangement of pixels; 
 operating the processor module to assign to each distinct pixel block array in the first set of distinct pixel block arrays a first distribution weight, the first distribution weight corresponding to a number of pixel block arrays in the first plurality of pixel block arrays having the first distinct arrangement of pixels corresponding to that distinct pixel block arrays; 
 operating the processor module to generate the first pixel group set based on the first set of distinct pixel block arrays; 
 operating the processor module to determine at least one second distinct arrangement of pixels, wherein the at least one second distinct arrangement of pixels defines a second arrangement of pixels in one or more pixel block arrays in the second plurality of pixel block arrays; 
 operating the processor module to determine a second set of distinct pixel block arrays, wherein the second set of distinct pixel block arrays comprises a second distinct pixel block array for each second distinct arrangement of pixels in the at least one second distinct arrangement of pixels; 
 operating the processor module to assign to each distinct pixel block array in the second set of distinct pixel block arrays a second distribution weight, the second distribution weight corresponding to a number of pixel block arrays in the second plurality of pixel block arrays having the second distinct arrangement of pixels corresponding to that distinct pixel block arrays; 
 operating the processor module to generate the second pixel group set based on the second set of distinct pixel block arrays; 
 operating the processor module to determine the plurality of pixel group pairs such that
 i) for each pixel group pair in the plurality of pixel group pairs, the first comparison pixel group array in that pixel group pair corresponds to one of the first distinct pixel block arrays and the second comparison pixel group array in that pixel group pair corresponds to one of the second distinct pixel block arrays; and 
 ii) each of the first distinct pixel block arrays corresponds to the first comparison pixel group array in a pixel group pair in the plurality of pixel group pairs, and each of the second distinct pixel block arrays corresponds to the second comparison pixel group array in a pixel group pair in the plurality of pixel group pairs; 
 
 operating the processor module to associate each pixel group pair with its distortion measure; 
 operating the processor module to determine a joint distribution weight for each pixel group pair, where the joint distribution weight is determined based on the first distribution weight corresponding to the first comparison pixel group array and the second distribution weight corresponding to the second comparison pixel group array; and 
 operating the processor module to determine the average pixel group pair distortion based on the distortion measure and joint distribution weight for each pixel group pair. 
 
     
     
         13 . A system for determining a measure of perceptual similarity between a first digitized image having a first arrangement of pixels, each pixel in the first arrangement of pixels having a first pixel value, and a second digitized image having a second arrangement of pixels, each pixel in the second arrangement of pixels having a second pixel value, using a similarity distance, the system comprising:
 a data storage module configured to store one of the first arrangement of pixels and the second arrangement of pixels; and   a processor module comprising one or more processors, the processor module being configured to:
 determine a first image array having M pixels by N pixels corresponding to the first arrangement of pixels, where M and N are positive integers; 
 determine a second image array having M pixels by N pixels corresponding to the second arrangement of pixels; 
 generate a first pixel group set comprising a first plurality of pixel group arrays based on the first image array wherein each pixel group array in the first plurality of pixel group arrays comprises at least two pixels; 
 generate a second pixel group set comprising a second plurality of pixel group arrays based on the second image array wherein each pixel group array in the second plurality of pixel group arrays comprises at least two pixels; 
 generate a plurality of pixel group pairs, each pixel group pair comprising a first comparison pixel group array from the first plurality of pixel group arrays in the first pixel group set and a second comparison pixel group array from the second plurality of pixel group arrays in the second pixel group set; 
 associate each pixel group pair with a pixel group pair distortion, the pixel group pair distortion being a distortion measure between the first comparison pixel group array and the second comparison pixel group array in that pixel group pair; and 
 determine the similarity distance between the first digitized image and the second digitized image based on the plurality of pixel group pair distortions. 
   
     
     
         14 . The system as defined in  claim 13  wherein the processor module is further configured to:
 identify a first plurality of pixel arrays based on the first image array, each pixel array having a first number of pixels; 
 generate a first pattern image array having the first number of pixels; and 
 generate the first plurality of pixel group arrays by, for each pixel array in the first plurality of pixel arrays, superimposing the first pattern image array onto that pixel array such that the first plurality of pixel group arrays comprises a corresponding pixel group array for each pixel array in the first plurality of pixel arrays, wherein superimposing the first pattern image array onto that pixel array comprises a matrix addition of each array element in that pixel array with a corresponding array element in the first pattern image array. 
 
     
     
         15 . The system as defined in  claim 14  wherein the processor module is further configured to:
 identify a first plurality of pixel block arrays in the first image array with each pixel block array having k pixels by l pixels, where k is a positive integer divisor of M with no remainder and I is a positive integer divisor of N with no remainder; 
 determine a first average pixel block array having k pixels by l pixels based on the first plurality of pixel block arrays, wherein each average pixel block array element in the first average pixel block array is determined based on an average value of an array element from each pixel block array of the first plurality of pixel block arrays having an array location corresponding to that average pixel block array element; and 
 generate the first pattern image array based on the first average pixel block array. 
 
     
     
         16 . The system as defined in  claim 15  wherein the first pattern image array is k pixels by l pixels and corresponds to the first average pixel block array. 
     
     
         17 . The system as defined in  claim 15  wherein the first pattern image array comprises a plurality of pattern pixel block arrays, where each pattern pixel block array is k pixels by I pixels and each pattern pixel block corresponds to the first average pixel block array. 
     
     
         18 . The system as defined in  claim 13  wherein the processor module is further configured to:
 identify a first plurality of pixel block arrays in the first image array, with each pixel block array having k pixels by l pixels, where k is a positive integer divisor of M with no remainder and I is a positive integer divisor of N with no remainder; 
 identify a second plurality of pixel block arrays in the second image array, with each pixel block array having k pixels by l pixels; 
 generate a set of related image arrays from an original image array using a set mapping, the set mapping comprising a plurality of pixel block array permutations, such that, for each pixel block array permutation there is a corresponding image array in the set of related image arrays, this corresponding image array being obtained by applying that pixel block array permutation to the original image array, and each related image array in the set of related image arrays has at least as many pixels as the original image array; 
 generate the first pixel group set using the set mapping, such that the first pixel group set is a first set of related digitized images having a first plurality of related digitized image arrays, each related digitized image array being generated by applying one of the pixel block array permutations to the first plurality of pixel block arrays such that each of the related digitized image arrays comprises an arrangement of the pixel block arrays in the first plurality of pixel block arrays and each of the related digitized image arrays has at least as many pixels as the first image array; and 
 generate the second pixel group set using the set mapping, such that the second pixel group set is a second set of related digitized images having a second plurality of related digitized image arrays, each related digitized image array being generated by applying one of the pixel block array permutations to the second plurality of pixel block arrays such that each of the related digitized image arrays comprises an arrangement of the pixel block arrays in the second plurality of pixel block arrays and each of the related digitized image arrays has at least as many pixels as the second image array. 
 
     
     
         19 . The system as defined in  claim 18  wherein the processor module is further configured to:
 determine the plurality of pixel group pairs such that
 i) for each pixel group pair in the plurality of pixel group pairs, the first comparison pixel group array in that pixel group pair corresponds to one of the related digitized image arrays in the first plurality of related digitized image arrays and the second comparison pixel group array in that pixel group pair corresponds to one of the related digitized image arrays in the second plurality of related digitized image arrays, and 
 ii) each of the related digitized image arrays in the first plurality of related digitized image arrays corresponds to the first comparison pixel group array in a pixel group pair in the plurality of pixel group pairs, and each of the related digitized image arrays in the second plurality of related digitized image arrays corresponds to the second comparison pixel group array in a pixel group pair in the plurality of pixel group pairs; 
 
 associate each pixel group pair with a pixel group pair distortion, the pixel group pair distortion being a distortion measure between the first comparison pixel group array and the second comparison pixel group array in that pixel group pair; 
 identify a lowest pixel group pair distortion based on the plurality of pixel group pair distortions; and 
 determine the similarity distance between the first digitized image and the second digitized image based on the lowest pixel group pair distortion. 
 
     
     
         20 . The system as defined in  claim 19  wherein the processor module is further configured to:
 generate a bipartite graph G, where G has a plurality of first vertices, each of the first vertices corresponding to one of the pixel block arrays in the first plurality of pixel block arrays, and a corresponding plurality of second vertices, each of the second vertices corresponding to one of the pixel block arrays in the second plurality of pixel block arrays; 
 determine a plurality of matchings, where each matching is determined such that each of the first vertices is matched with a distinct corresponding one of the second vertices, and wherein each matching corresponds to one of the pixel group pairs; 
 associate each matching with a matching weight, the matching weight being determined based on a sum of a plurality of vertex distortions, each vertex distortion in the plurality of vertex distortions corresponding to the distortion measure between one of the first vertices in the plurality of first vertices and the corresponding one of the second vertices in the plurality of second vertices; and 
 identify a matching with a lowest matching weight and set the lowest matching weight as the lowest pixel group pair distortion in the plurality of pixel group pair distortions. 
 
     
     
         21 . The system as defined in  claim 20  wherein the processor module is configured to identify the matching with the lowest matching weight using a Blossom-V algorithm. 
     
     
         22 . The system as defined in  claim 13  wherein the processor module is further configured to:
 generate the first plurality of pixel group arrays by identifying a first plurality of pixel block arrays in the first image array, with each pixel block array having k pixels by I pixels, where k is a positive integer divisor of M with no remainder and I is a positive integer divisor of N with no remainder; and 
 generate the second plurality of pixel group arrays by identifying a second plurality of pixel block arrays in the second image array, with each pixel block array having k pixels by l pixels. 
 
     
     
         23 . The system as defined in  claim 22  wherein the processor module is further configured to:
 determine the plurality of pixel group pairs such that
 i) for each pixel group pair in the plurality of pixel group pairs, the first comparison pixel group array in that pixel group pair corresponds to one of the pixel block arrays in the first plurality of pixel block arrays and the second comparison pixel group array in that pixel group pair corresponds to one of the pixel block arrays in the second plurality of pixel block arrays; 
 ii) each of the pixel block arrays in the first plurality of pixel block arrays corresponds to the first comparison pixel group array in a pixel group pair in the plurality of pixel group pairs, and each of the pixel block arrays in the second plurality of pixel block arrays corresponds to the second comparison pixel group array in a pixel group pair in the plurality of pixel group pairs; 
 
 associate each pixel group pair with a pixel group pair distortion, the pixel group pair distortion being a distortion measure between the first comparison pixel group array and the second comparison pixel group array in that pixel group pair; 
 determine an average pixel group pair distortion based on the plurality of pixel group pair distortions; and 
 determine the similarity distance between the first digitized image and the second digitized image based on the average pixel group pair distortion. 
 
     
     
         24 . The system as defined in  claim 23  wherein the processor module is further configured to:
 determine at least one first distinct arrangement of pixels, wherein the at least one first distinct arrangement of pixels defines a first arrangement of pixels in one or more pixel block arrays in the first plurality of pixel block arrays; 
 determine a first set of distinct pixel block arrays wherein the first set of distinct pixel block arrays comprises a first distinct pixel block array for each first distinct arrangement of pixels in the at least one first distinct arrangement of pixels; 
 assign to each distinct pixel block array in the first set of distinct pixel block arrays a first distribution weight, the first distribution weight corresponding to a number of pixel block arrays in the first plurality of pixel block arrays having the first distinct arrangement of pixels corresponding to that distinct pixel block arrays; 
 generate the first pixel group set based on the first set of distinct pixel block arrays; 
 determine at least one second distinct arrangement of pixels, wherein the at least one second distinct arrangement of pixels defines a second arrangement of pixels in one or more pixel block arrays in the second plurality of pixel block arrays; 
 determine a second set of distinct pixel block arrays, wherein the second set of distinct pixel block arrays comprises a second distinct pixel block array for each second distinct arrangement of pixels in the at least one second distinct arrangement of pixels; 
 assign to each distinct pixel block array in the second set of distinct pixel block arrays a second distribution weight, the second distribution weight corresponding to a number of pixel block arrays in the second plurality of pixel block arrays having the second distinct arrangement of pixels corresponding to that distinct pixel block arrays; 
 generate the second pixel group set based on the second set of distinct pixel block arrays; 
 determine the plurality of pixel group pairs such that
 i) for each pixel group pair in the plurality of pixel group pairs, the first comparison pixel group array in that pixel group pair corresponds to one of the first distinct pixel block arrays and the second comparison pixel group array in that pixel group pair corresponds to one of the second distinct pixel block arrays; and 
 ii) each of the first distinct pixel block arrays corresponds to the first comparison pixel group array in a pixel group pair in the plurality of pixel group pairs, and each of the second distinct pixel block arrays corresponds to the second comparison pixel group array in a pixel group pair in the plurality of pixel group pairs; 
 
 associate each pixel group pair with its distortion measure; 
 determine a joint distribution weight for each pixel group pair, where the joint distribution weight is determined based on the first distribution weight corresponding to the first comparison pixel group array and the second distribution weight corresponding to the second comparison pixel group array; and 
 determine the average pixel group pair distortion based on the distortion measure and joint distribution weight for each pixel group pair. 
 
     
     
         25 . A computer program product for use on a processor module with one or more processors to determine a measure of perceptual similarity between a first digitized image having a first arrangement of pixels, each pixel in the first arrangement of pixels having a first pixel value, and a second digitized image having a second arrangement of pixels, each pixel in the second arrangement of pixels having a second pixel value, using a similarity distance, the computer program product comprising:
 a non-transitory recording medium; and   instructions recorded on the recording medium, the instructions for configuring the processor module to:   determine a first image array having M pixels by N pixels corresponding to the first arrangement of pixels, where M and N are positive integers;   determine a second image array having M pixels by N pixels corresponding to the second arrangement of pixels;   generate a first pixel group set comprising a first plurality of pixel group arrays based on the first image array wherein each pixel group array in the first plurality of pixel group arrays comprises at least two pixels;   generate a second pixel group set comprising a second plurality of pixel group arrays based on the second image array wherein each pixel group array in the second plurality of pixel group arrays comprises at least two pixels;   generate a plurality of pixel group pairs, each pixel group pair comprising a first comparison pixel group array from the first plurality of pixel group arrays in the first pixel group set and a second comparison pixel group array from the second plurality of pixel group arrays in the second pixel group set;   associate each pixel group pair with a pixel group pair distortion, the pixel group pair distortion being a distortion measure between the first comparison pixel group array and the second comparison pixel group array in that pixel group pair; and   determine the similarity distance between the first digitized image and the second digitized image based on the plurality of pixel group pair distortions.