IMAGE RETRIEVAL AND AUTHENTICATION USING ENHANCED EXPECTATION MAXIMIZATION (EEM)

• US 20140355880A1
• Filed: 03/08/2012
• Published: 12/04/2014
• Est. Priority Date: 03/08/2012
• Status: Active Grant

• Current Assignee: New Jersey Institute of Technology
• Original Assignee: Empire Technology Development LLC (Allied Inventors Management, LLC)
• Inventors: Xuan, Guorong, Shi, Yun-Qing
• Granted Patent: US 9,158,791 B2
• Time in Patent Office: Days
• US Class Current: 382/170
• CPC Class Codes: G06F 16/50 of still image data
• CPC Class Codes: G06F 16/51 Indexing; Data structures therefor; Storage structures
• CPC Class Codes: G06F 16/53 Querying
• CPC Class Codes: G06F 16/583 using metadata automatically derived from the content
• CPC Class Codes: G06F 18/2415 based on parametric or probabilistic models, e.g. based on likelihood ratio or false acceptance rate versus a false rejection rate
• CPC Class Codes: G06V 10/52 Scale-space analysis, e.g. wavelet analysis multi-scale boundary representations G06V10/42
• CPC Class Codes: G06V 10/764 using classification, e.g. of video objects

Abstract

Technologies are generally presented for employing enhanced expectation maximization (EEM) in image retrieval and authentication. Using uniform distribution as initial condition, the EEM may converge iteratively to a global optimality. If a realization of the uniform distribution is used as the initial condition, the process may also be repeatable. In some examples, a positive perturbation scheme may be used to avoid boundary overflow, often occurring with the conventional EM algorithms. To reduce computation time and resource consumption, a histogram of one dimensional Gaussian Mixture Model (GMM) with two components and wavelet decomposition of an image may be employed.

Claims

1. A method for employing an Enhanced Expectation Maximization (EEM) to determine data uniqueness and similarity, the method comprising:

receiving data to be analyzed;

employing a realization of uniform distribution in an initialization of the EEM on the received data to prevent convergence to a local maximum;

employing a positive perturbation scheme to avoid boundary overflow;

generating a signature vector for the analyzed data; and

employing the signature vector to determine one of uniqueness and similarity of the analyzed data to other data based on a similarity of the signature vector to signature vectors of the other data.

2. The method according to claim 1, wherein the analyzed data is image data.

3. The method according to claim 2, further comprising

employing a histogram of one dimensional Gaussian Mixture Model (GMM) for the image data.

4. The method according to claim 3, further comprising

employing two components of the GMM for histogram.

5. The method according to claim 3, further comprising

applying a multilevel discrete wavelet transform to determine a number of the GMMs to be used.

6. The method according to claim 5, further comprising

selecting one or more parameters of the GMM of image wavelet subbands as the signature vector.

7. The method according to claim 6, wherein the selected parameters are a mean and a variance of the GMM.

8. The method according to claim 2, further comprising

determining the uniqueness of the image data based on a Euclidian distance between two signature vectors being greater than a predefined limit.

9. The method according to claim 2, further comprising

determining the similarity of the image data based on a Euclidian distance between two signature vectors being less than another predefined limit.

10. The method according to claim 2, wherein a size of the signature vector is 128 bits or less.

11. The method according to claim 2, further comprising

employing the similarity of the image data for one of image retrieval and indexing;

and

employing the uniqueness of the image data for authentication.

12. The method according to claim 2, further comprising

generating the signature vector by applying the EEM to color components of the image data.

13. The method according to claim 12, wherein a color space of the image data includes one of HSV, YCrCb, CMYK, and RGB.

14. The method according to claim 2, wherein the positive perturbation scheme includes addition of a denominator factor in goodness calculation of a histogram for the image data.

15. The method according to claim 14, wherein the goodness of the histogram for the image data is determined by:

G=10 log₁₀{ee+A/(ee+MSE)}, where

A={Max[Max(h₁),Max(h)]}² with h and h₁ being histogram values before and after application of the EEM,

MSE=S(h₁−

h)²/M with M being a number of occurrence values in the histogram, and

ee is a very small positive perturbation value.

16. The method according to claim 15, wherein ee is about 10⁻

20.

17. The method according to claim 1, further comprising

generating the signature vector by applying the EEM to one of video data and audio data.

18. A computing device for employing an Enhanced Expectation Maximization (EEM) to determine data uniqueness and similarity, the computing device comprising:

a memory configured to store instructions; and

a processor coupled to the memory and configured to execute a data processing application in conjunction with the instructions stored in the memory, wherein the data processing application is configured to;

receive data to be analyzed;

employ a realization of uniform distribution in an initialization of the EEM on the received data to prevent convergence to a local maximum;

employ a positive perturbation scheme to avoid boundary overflow;

generate a signature vector for the analyzed data; and

employ the signature vector to determine one of uniqueness and similarity of the analyzed data to other data based on a similarity of the signature vector to signature vectors of the other data.

19. The computing device according to claim 18, wherein the analyzed data is image data.

20. The computing device according to claim 19, wherein the data processing application is further configured to

employ a histogram of one dimensional Gaussian Mixture Model (GMM) for the image data.

21. The computing device according to claim 20, wherein the data processing application is further configured to

employ two components of the GMM for histogram.

22. The computing device according to claim 20, wherein the data processing application is further configured to

apply a multilevel discrete wavelet transform to determine a number of the GMMs to be used.

23. The computing device according to claim 22, wherein the data processing application is further configured to

select one or more parameters of the GMM of image wavelet subbands as the signature vector.

24. The computing device according to claim 23, wherein the selected parameters are a mean and a variance of the GMM.

25. The computing device according to claim 19, wherein the data processing application is further configured to

determine the uniqueness of the image data based on a Euclidian distance between two signature vectors being greater than a predefined limit.

26. The computing device according to claim 19, wherein the data processing application is further configured to

determine the similarity of the image data based on a Euclidian distance between two signature vectors being less than another predefined limit.

27. The computing device according to claim 19, wherein a size of the signature vector is 128 bits or less.

28. The computing device according to claim 19, wherein the data processing application is further configured to

employ the similarity of the image data for one of image retrieval and indexing;

and

employ the uniqueness of the image data for authentication.

29. The computing device according to claim 19, wherein the data processing application is further configured to

generate the signature vector by applying the EEM to color components of the image data.

30. The computing device according to claim 29, wherein a color space of the image data includes one of HSV, YCrCb, CMYK, and RGB.

31. The computing device according to claim 19, wherein the positive perturbation scheme includes addition of a denominator factor in goodness calculation of a histogram for the image data.

32. The computing device according to claim 31, wherein the goodness of the histogram for the image data is determined by:

G=10 log₁₀{ee+A/(ee+MSE)}, where

A={Max[Max(h₁),Max(h)]}² with h and h₁ being histogram values before and after application of the EEM,

MSE=S(h₁−

h)²/M with M being a number of occurrence values in the histogram, and

ee is a very small positive perturbation value.

33. The computing device according to claim 32, wherein ee is about 10⁻

20.

34. The computing device according to claim 18, wherein the data processing application is further configured to

generate the signature vector by applying the EEM to one of video data and audio data.

35. A computer-readable storage medium having instructions stored thereon for employing an Enhanced Expectation Maximization (EEM) to determine data uniqueness and similarity, the instructions comprising:

receiving data to be analyzed;

employing a realization of uniform distribution in an initialization of the EEM on the received data to prevent convergence to a local maximum;

employing a positive perturbation scheme to avoid boundary overflow;

generating a signature vector for the analyzed data; and

employing the signature vector to determine one of uniqueness and similarity of the analyzed data to other data based on a similarity of the signature vector to signature vectors of the other data.

36. The computer-readable storage medium according to claim 35, wherein the analyzed data is image data.

37. The computer-readable storage medium according to claim 36, wherein the instructions further comprise

employing a histogram of one dimensional Gaussian Mixture Model (GMM) for the image data.

38. The computer-readable storage medium according to claim 37, wherein the instructions further comprise

employing two components of the GMM for histogram.

39. The computer-readable storage medium according to claim 37, wherein the instructions further comprise

applying a multilevel discrete wavelet transform to determine a number of the GMMs to be used.

40. The computer-readable storage medium according to claim 39, wherein the instructions further comprise

selecting one or more parameters of the GMM of image wavelet subbands as the signature vector.

41. The computer-readable storage medium according to claim 40, wherein the selected parameters are a mean and a variance of the GMM.

42. The computer-readable storage medium according to claim 36, wherein the instructions further comprise

determining the uniqueness of the image data based on a Euclidian distance between two signature vectors being greater than a predefined limit.

43. The computer-readable storage medium according to claim 36, wherein the instructions further comprise

determining the similarity of the image data based on a Euclidian distance between two signature vectors being less than another predefined limit.

44. The computer-readable storage medium according to claim 36, wherein a size of the signature vector is 128 bits or less.

45. The computer-readable storage medium according to claim 36, wherein the instructions further comprise

employing the similarity of the image data for one of image retrieval and indexing;

and

employing the uniqueness of the image data for authentication.

46. The computer-readable storage medium according to claim 36, wherein the instructions further comprise

generating the signature vector by applying the EEM to color components of the image data.

47. The computer-readable storage medium according to claim 46, wherein a color space of the image data includes one of HSV, YCrCb, CMYK, and RGB.

48. The computer-readable storage medium according to claim 36, wherein the positive perturbation scheme includes addition of a denominator factor in goodness calculation of a histogram for the image data.

49. The computer-readable storage medium according to claim 48, wherein the goodness of the histogram for the image data is determined by:

G=10 log₁₀{ee+A/(ee+MSE)}, where

A={Max[Max(h₁),Max(h)]}² with h and h₁ being histogram values before and after application of the EEM,

MSE=S(h₁−

h)²/M with M being a number of occurrence values in the histogram, and

ee is a very small positive perturbation value.

50. The computer-readable storage medium according to claim 49, wherein ee is about 10⁻

20.

51. The computer-readable storage medium according to claim 35, wherein the instructions further comprise

generating the signature vector by applying the EEM to one of video data and audio data.