Method for Identifying Pairs of Derivative and Original Images

• US 20120328189A1
• Filed: 06/26/2012
• Published: 12/27/2012
• Est. Priority Date: 06/27/2011
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Usher, Mark
• Granted Patent: US 8,879,837 B2
• Time in Patent Office: Days
• US Class Current: 382/165
• CPC Class Codes: G06F 16/5838 using colour

Abstract

The invention provides for a computer-implemented method for detecting one or more archive images matching a search image, each matching archive image being a derivative of the search image or being an original image the search image was derived from accessing a plurality of the archive images. For each of said archive images, a respective archive image histogram may be calculated, wherein each archive image histogram includes a plurality of combination micro-feature values. The archive image histogram may be stored to a database.

Claims

1. A computer-implemented method of detecting one or more archive images matching a search image, each matching archive image being a derivative of the search image or being an original image the search image was derived from, the method comprising:

accessing a plurality of the archive images;

for each of said archive images, computing a respective archive image histogram, each archive image histogram comprising a plurality of combination micro-feature values, and storing said archive image histogram to a database;

receiving a search image;

computing a search image histogram from said search image, the search image histogram comprising a set of combination micro-feature values;

comparing the combination micro-feature values of the search image histogram with the combination micro-feature values of the archive image histograms to identify one or more candidate archive image histograms; and

respectively comparing the one or more candidate archive image histograms with the search image histogram to identify one or more matching archive images as being a derivative of the search image or as being the original image the search image was derived from.

2. The computer-implemented method of claim 1, wherein computing an image histogram from an image, the image being one of the archive images or being the search image, includes:

converting the image into pixel data according to a color model, wherein each pixel of the image is represented by one numerical value for each color category of the color model;

calculating an integral image from said pixel data;

moving a window over the integral image, the movement comprising a plurality of movement steps, wherein the scale of the moving window is different in at least some of the movement steps;

for each of the movement steps, using the window of the current step as current window, and;

calculating a plurality of micro-feature values from the current window, wherein each micro-feature value is a result of a comparison between a first data value derived from the pixel data of a first segment of the current window with one second data value derived from the pixel data of a second segment of the current window, the first and second segment being of equal size;

combining the plurality of micro-feature values to form one combination micro-feature value for the current window;

calculating one image histogram for the image, wherein the image histogram is calculated by;

extracting all unique combination micro-feature values from the formed combination micro-feature values; and

determining an occurrence frequency for each unique combination micro-feature value within all combination micro-feature values calculated for said image, wherein the color model is an RGB color model.

3. The computer-implemented method of claim 2, wherein the current window is a square and wherein the compared first and second segments either consist of a first and a second half or a first and a second quadrant of said current window.

4. The computer-implemented method of claim 3, wherein the first and the second segments are selected from a group of first and second segments consisting of:

the upper half and the lower half of the window, the window being divided horizontally;

the left half and the right half of the window, the window being divided vertically;

the right lower quadrant and the left upper quadrant of the window, the window being divided vertically and horizontally; and

the left lower quadrant and the right upper quadrant of the window, the window being divided vertically and horizontally.

5. The computer-implemented method of claim 4,

wherein the color model is an RGB color model,

wherein each micro-feature value is calculated by a comparing function comparing the first and the second data value,

wherein the first data value is a sum of the RGB-values of a first color of all pixels of the first segment, the first color being red, green or blue,

wherein the second data value is the sum of the rgb-values of a second color of all pixels of the second segment, the second color being red, green or blue,

wherein at least six different micro-features are calculated based on a comparison of at least three pairs of first and second colors evaluated on at least two pairs of first and second segments,

wherein said at least three pairs of first and second colors comprise:

red and red,

green and green, and

blue and blue,

wherein said at least two pairs of first and second segments comprise;

right lower quadrant and left upper quadrant, and

left lower quadrant and right upper quadrant.

6. The computer-implemented method of claim 5, wherein in addition or alternatively to said at least six micro-features, at least one grey-scale micro-feature is calculated,

wherein the first data value is a grey value calculated by summing up all RGB-values for the colors red, green and blue of all pixels of the first segment, and dividing said sum by three,

wherein the second data value is a background value calculated by determining the number of pixels within the second segment and multiplying said number by 128,

wherein each of the at least one grey-scale micro-features is calculated based on a comparison of the grey value and the background value, said comparison being executed for a pair of first and second segments being selected from the group comprising:

left upper quadrant and left upper quadrant,

right upper quadrant and right upper quadrant,

left lower quadrant and left lower quadrant, and

right lower quadrant and right lower quadrant.

7. The computer-implemented method of claim 5, wherein the comparison function for comparing the first data value (ARG1) and the second data value (ARG2) is selected from the group comprising:

ARG1>

ARG2,

ARG1×

c1>

ARG2, wherein c1 is a constant larger than one,

ARG1×

c2>

ARG2, wherein c2 is a constant larger than zero and smaller than one,

ARG1+c3>

ARG2, wherein c3 is a constant,

(ARG1×

c1)+c3>

ARG2, and

(ARG1×

c2)+c3>

ARG2.

8. The computer-implemented method of claim 2, wherein the window is a square and wherein the number of movement steps comprises:

specifying a proportion factor (SR), SR being a value between zero and one,

specifying a shifting factor (DR),

determining a variable (MWS) as a length of the shortest side of the image,

determining a height and width (IWS) of an initial window as IWS=MWS×

SR,

a) choosing a starting point of the image as a left upper corner of the initial window,

b) after having calculated combination micro-feature values for the initial window, shifting the window DX pixels one or more of horizontally and vertically until every pixel of the integral window was covered by at least one of the windows, wherein DX=IWS×

DR, and wherein upon each window movement a combination micro-feature value is calculated for the corresponding current window,

c) after having executed steps a) and b), increasing the height and width of the window by multiplying the IWS value of the window used previous by a scale factor SF, such that IWS′

IWS×

SF; and

d) repeating steps a) to c) until the height and width of the increased window exceeds MWS.

9. The computer-implemented method of claim 1, wherein comparing the combination micro-feature values of the search image histogram with the combination micro-feature values of the archive image histograms comprises:

storing individual combination micro-feature values of each archive image histogram in an index of the database, the index comprising a unique set of combination micro-feature values having been calculated for said archive image, wherein each index entry references one or more identifiers of archive image histograms that comprise a combination micro-feature value being identical to the referencing index entry;

using each of the combination micro-feature values of the search image histogram as keys on said index for retrieving archive image micro-feature values being identical to said combination micro-feature value of the search image;

determining all archive image histograms referenced by said retrieved archive image micro-feature values;

assigning to each of said determined archive image histograms a count score value (CSV), said count score value being indicative of the number of retrieved archive image micro-feature values referencing the identifier of said archive image histogram; and

reading all archive image histograms whose count score value exceeds a key threshold (KT) as the candidate archive image histograms.

10. The computer-implemented method of claim 9, wherein comparing the one or more candidate archive image histograms with the search image histogram comprises, for each of the candidate archive image histograms:

calculating a distance score value (DSV), the distance score value indicating a distance between the candidate archive image histogram and the search image histogram,

determining all candidate archive image histograms whose distance score is lower than a distance threshold (DT),

mapping the count score value to a mapped count score value (MCSV), the MCSV lying within an inclusive range of 0.5-1, wherein KM is a predefined constant representing a maximum possible CSV value in all candidate archive image histograms and wherein MCSV=0.5+min(0.5, ((CSV−

KT)/(KM−

KT));

mapping the distance score value to a mapped distance score value (MDSV), the MDSV lying within an inclusive range of 0.5-1, wherein DM is a predefined constant representing a maximum possible DSV value in all candidate archive image histograms and wherein MDSV=0.5+min(0.5, ((1−

DSV)−

(1−

DT))/(DM−

(1−

DT)));

calculating a final score SC=(MCSV+MDSV)/2;

identifying the one or more archive images if the final score value SC exceeds a cutoff threshold.

11. The computer-implemented method of claim 1, wherein each micro-feature value combined for providing the combination micro-feature values is a zero or one value, and wherein the combination micro-feature value is stored in the form of a 32-bit integer or a 64-bit long data type in the database, whereby each micro-feature value is stored at a bit position within said data structure being particular to one type of micro-feature.

12. The computer-implemented method of claim 2, further comprising:

specifying a plurality of different reference points within the integral image,

wherein one image histogram is calculated for each of said reference points,

wherein creating the one image histogram for each of said reference points further includes;

determining a normalization factor (T), T being calculated as a Manhattan distance between a top left corner and a bottom left corner of the integral image,

for each of the movement steps;

determining a center point Z of the current window and calculating the Manhattan distance (dRP, Z) between said center point and the reference point, and

calculating a weight we=1.0−

dRP, Z/T,

wherein after having calculated all combination micro-feature values for said image histogram, for each of the calculated combination micro-feature values of said histogram, a weighted frequency value is calculated by summing up all weights having been calculated for the combination micro-feature values of all respective current windows of said image histogram.

13. The computer-implemented method of claim 1,

wherein each of the archive image histograms is stored in the database in a form of an array, the dimension of the array being equal to a number of archive images, wherein the position number of each image histogram within said array is used as a unique identifier of said image histogram and of the corresponding image within the database, and

wherein in case the plurality of different reference points were specified, each array element comprises one stacked archive histogram, and wherein the stack archive histogram is a single data structure comprising one archive image histogram for each of the number of different reference points, the stack archive histogram enabling individualization of each of its archive image histograms.

14. A computer-system comprising:

a processor,

a computer-readable, non-transitory storage medium the storage medium comprising computer-interpretable instructions that, when executed by the processor, cause the processor to perform the method according to claim 1.

15. A computer-readable, non-transitory storage medium, the storage medium comprising computer-interpretable instructions that, when executed by a processor, cause the processor to perform the method according to claim 1.