Method of storing and retrieving images of people, for example, in photographic archives and for the construction of identikit images

• US 5,764,790 A
• Filed: 08/29/1995
• Issued: 06/09/1998
• Est. Priority Date: 09/30/1994
• Status: Expired due to Term

• Current Assignee: Fondazione Bruno Kessler
• Original Assignee: Istituto Trentino Di Cultura
• Inventors: Brunelli, Roberto, Mich, Ornella
• Primary Examiner(s): Boudreau, Leo
• Assistant Examiner(s): KELLEY, CHRISTOPHER S
• Application Number:
  US08/520,479
• Time in Patent Office: 1,015 Days
• Field of Search: 382/115, 382/117, 382/118, 382/190, 382/254, 382/306, 395/141, 395/143
• US Class Current: 382/118
• CPC Class Codes: G06F 16/532 Query formulation, e.g. graphical querying
• CPC Class Codes: G06T 11/00 2D [Two Dimensional] image generation
• CPC Class Codes: G06V 40/16 Human faces, e.g. facial parts, sketches or expressions

Abstract

In a method of storing and retrieving images of people, for example, in photographic archives and for the construction of identikit images, each characteristic (or feature) of the images to be stored is associated with a region the size of which corresponds to the average size of the feature in the images stored. If {F_i }_i=1 . . . , N is a set of images of the feature, where F_i is the image associated with each of the N people in the data base, on the basis of these images, a new set of images {Φ_j }_j=0, 1, . . . N of the type ##EQU1## is generated, of which a subset {Φ}_i=0 . . . K can be used to approximate, encode, compare and construct images of the type in question in an interactive manner. The method is particularly applicable to techniques for searching photographic archives and for the construction of identikit images.

Claims

1. A method of storing a plurality of N images of people, particularly but not exclusively in order to form photographic archives or identikit systems in which the images to be stored are distinguished by sets of features F, wherein said method comprises the steps of:

analysing said images, each of said features having a respective image _i in each of said images, then associating with each feature an average region the size of which corresponds to the average size of the feature in the plurality of images,

generating from said respective images a set of new images according to the expansion;

##EQU13## in which ##EQU14##

space="preserve" listing-type="equation">C.sub.Fij =(F.sub.i -Φ

.sub.0)·

Φ

.sub.j

space="preserve" listing-type="equation">Φ

.sub.j ·

Φ

.sub.t =δ

.sub.jt j, t=1 , . . . , N ##EQU15## and selecting those new images Φ

.sub.j in which 1≦

j ≦

N as eigenvectors of the covariance matrix in the set {F.sub.i -Φ

.sub.0 } so that the respective eigenvalue λ

.sub.Fj can be associated with each eigenvector, the set of new images then being arranged in a manner such that λ

.sub.Fj ≧

λ

.sub.Ft when j>

XFt when j <

t, and

storing said respective images in the form of vectors

space="preserve" listing-type="equation">C.sub.Fi ={C.sub.Fil, . . . , C.sub.Fik }, k<

N

where k is a number usually much less than N so that a set of vectors, one for each of the regions of the face used in the method, is associated with each of the images of the plurality.

2. A method according to claim 1, wherein each image is reconstructed according to the equation ##EQU16## in order to reconstruct each of the images from the respective set of vectors.

3. A method according to claim 2, wherein said vectors have co-ordinates the values of the which are selected by moving cursors to positions with which values for the corresponding co-ordinates are associated.

4. A method according to claim 2, wherein said images are reconstructed by operating on a region with larger dimensions than the average region, the calculation of said covariance matrix and of the values of said expansion being limited to the average region, the region outside the average region, and inside the enlarged used for connecting the various features.

5. A method according to claim 1, wherein said method further comprises the step of identifying images having a disparity of less than a predetermined threshold disparity to reduce said plurality of images.

6. A method according to claim 5, wherein said disparity is calculated by an equation of the type ##EQU17## where T represents the number of pixels of the image considered as a vector, X and Y being the two images between which the disparity is calculated.

7. A method according to claim 5, wherein said disparity is calculated according to the equation

8. A method according to claim 1, wherein said plurality of images is divided into subsets of images having substantially similar features, the method being applied to these subsets separately.

9. A method according to claim 1, wherein said plurality of images is subjected to geometric standardization so that the images of said plurality are of uniform size and orientation, before the analysis is begun.

10. A method according to claim 9, wherein said geometric standardization operation comprises the step of identifying the position of each pupil of each of said images and the operation of bringing said position to a predetermined reference position.

11. A method according to claim 1, wherein the images (F) of said plurality are subjected to a standardization of their intensity values before the analysis is begun.

12. A method according to claim 11, wherein said standardization of the intensity values is carried out by causing the average intensity value of a specific region of the image to assume a predetermined value.

13. A method according to claim 1, wherein each image F of said plurality are subjected to a transformation of the type ##EQU20## where ##EQU21## and F is the original image and the symbol * represents the convolution operation, K_Gδ

represents a Gaussan convolution kernel, the parameter a (standard deviation) of which is correlated with the interocular distance of said image before the analysis is begun.

14. A method according to claim 2, wherein, in the reconstruction step, the images are reconstructed as the sum of the features available and of an average image corresponding to an arithmetic mean of the images stored.

15. A method according to claim 1, wherein said method further comprises the step of associating, with each of the features, a respective priority and a respective map of values the size of which corresponds to that of the overall image, in which are identified:

a region outside the respective feature,

an inner region of the respective feature, corresponding to the average region used for calculating the covariance matrix and the expansion values, and

a transition region,

and the step of setting the map values to 1 in the inner region, to 0 in the outer region and to an intermediate value in the transition region, thus achieving a blending of the features.

16. A method according to claim 15, wherein the transitional region is one-dimensional and said intermediate value is selected by a law of the type:

##EQU22## where x is the one-dimensional coordinate with the one-dimensional region being defined as

space="preserve" listing-type="equation">r.sub.F = X.sub.1, X.sub.2 !

space="preserve" listing-type="equation">R.sub.F = X.sub.0, X.sub.j)

where r_F is the inner region, (R_F -r_F) is the transition region,

where X₀ <

₁ <

X₂ <

X₃.

17. A method according to claim 15, wherein the transitional region is two-dimensional and the intermediate value is the product of the functions W_F of the x-co-ordinate and y-co-ordinate, respectively, the reconstruction value being given by

18. A method according to claim 1, wherein said method further comprises the step of comparing the images stored with an additional image in the course of formation, generating a respective similarity parameter, then sorting the set of images stored in order of increasing disparity or dissimilarity values with respect to the image in the course of construction, and the step of displaying a certain number of stored images having a certain degree of similarity to the images in the course of construction.

19. A method according to claim 18, wherein said disparity or dissimilarity is defined according to an equation of the type ##EQU23## where Q is the number of features which can be selected;

a_F =1 or 0 according to whether the feature has been selected or not, the quantity ##EQU24## and represents a standardization factor with which to weight the various features, and the vectors C_F, C_Fi the image being constructed and the image i of the data base, respectively, within the limits of the feature F.

20. A method according to claim 19, wherein pointing to (selecting) one of the images displayed replaces the descriptive components of the feature selected in the image being constructed with those of the image selected.

21. A method according to claim 19, wherein said set of images in the data base is organized and presented in a hierarchical manner, and wherein pointing to (selecting) one of the images displayed replaces the descriptive components of the features selected in the image being constructed with those of the image selected.

22. A system for storing a plurality of N images of people, particularly but not exclusively in order to form photographic archives or identikit systems, in which the images to be stored are distinguished by sets of features F, characterized in that it comprises:

acquisition and analysis means for analyzing the images, each of the features having a respective image F_i in each of the images, and then for associating with each feature an average region, the size of which corresponds to the average size of the feature in the plurality of images,

processor means for generating, from the respective images, a set of new images such that ##EQU25## where ##EQU26##

space="preserve" listing-type="equation">C.sub.Fij =(F.sub.i -Φ

.sub.0)Φ

.sub.j

space="preserve" listing-type="equation">Φ

.sub.j ·

Φ

.sub.t =δ

.sub.jt j, t=1, . . . , N ##EQU27## the new images Φ

.sub.j in which 1<

j<

N being selected as eigenvectors of the covariance matrix in the set {F.sub.i -Φ

.sub.0 } so that a respective eigenvalue λ

.sub.Fj can be associated with each eigenvector, the processing means then sorting the set of new images in a manner such that λ

.sub.Fj ≧

λ

.sub.Ft when j<

t and storing the respective images in the form of vectors

space="preserve" listing-type="equation">C.sub.Fi ={C.sub.Fil, . . . , C.sub.Fik }

so that a set of vectors, one for each of the regions of the face used in the system, is associated with each image of the plurality.

23. A system according to claim 22, wherein it comprises restoring means for reconstructing each of the images from the respective set of vectors, the restoring means reconstructing each image according to the equation ##EQU28## where K is a number much less than N.

24. A system according to claim 23, wherein it comprises cursor means for selecting the co-ordinates of the vectors, the position of the cursor means being associated with a value for the corresponding co-ordinate.

25. A system according to claim 23, wherein said restoring means operate on a region with larger dimensions than the average region, the calculation of the covariance matrix and of the values of said equation being limited to the average region, the region outside the average region and inside the enlarged region being used for connecting the various features.

26. A system according to claim 22, wherein said processing means reduce the plurality of images by identifying amongst them the images the disparity of which is less than a predetermined threshold disparity.

27. A system according to claim 26, wherein said processing means calculate the disparity with an equation of the type ##EQU29## where T represents the number of pixels of the image considered as a vector, X and Y being the two images between which the disparity is calculated.

28. A system according to claim 26, wherein said processing means calculate the disparity according to the equation

29. A system according to claim 22, wherein said processing means divide the plurality of images into subsets of images having substantially similar features.

30. A system according to claim 22, wherein it comprises pre-processing means which act between the acquisition and analysis means and the processing means, and in which the plurality of images is subjected to geometric standardization so that the images of the plurality are of uniform size and orientation.

31. A system according to claim 30, wherein said pre-processing means identify the position of each pupil of each of said images, the pre-processing means bringing this position to a predetermined reference position.

32. A system according to claim 22, wherein it comprises pre-processing means which act between the acquisition and analysis means and the processing means, and in which the images of the plurality are subjected to a standardization of their intensity values.

33. A system according to claim 32, wherein the preprocessing means cause the average intensity value of a specific region of the image to assume a predetermined value during the standardization of the intensity values.

34. A system according to claim 22, wherein it comprises pre-processing means which act between the acquisition and analysis means and the processing means, and in which each image F of the plurality is subjected to a transformation of the type ##EQU32## where ##EQU33## F is the original image and the symbol * represents the convolution operation, K_G(δ

) represents a Gaussian convolution kernel the parameter δ

(standard deviation) of which is correlated to the interocular distance.

35. A system according to claim 23, wherein said restoring means reconstruct the images as the sum of the features available and of an average image corresponding to an arithmetic mean of the images stored.

36. A system according to claim 22, wherein said processing means associate with each of the features a respective priority and a respective map of values the size of which corresponds to that of the overall image, in which are identified:

a region outside the respective feature,

an inner region of the respective feature corresponding to the average region used for calculating the covariance matrix and the expansion values, and

a transition region,

and wherein the processing means set the map values to 1 in the inner region, to 0 in the outer region and to an intermediate value in the transition region so that the restoring means achieve a blending of the features.

37. A system according to claim 36, wherein the transitional region is one-dimensional and said intermediate value is selected by a law of the type:

##EQU34## where x is the one-dimensional coordinate the one-dimensional region being defined as

space="preserve" listing-type="equation">r.sub.F = X.sub.1, X.sub.2 !

space="preserve" listing-type="equation">R.sub.F X.sub.0, X.sub.3 !

where X₀ <

X₁ <

X₂,X₃ and r_F is the inner region, (R_F -r_F) is the transition region.

38. A system according to claim 36, wherein the transitional region is two-dimensional, the processing means process the intermediate value using the product of the functions W_F of the x-co-ordinate and the y-coordinate, respectively, the restored value being given by

39. A system according to claim 23, wherein said processing means compare the images stored with an additional image in the course of formation to generate a respective similarity parameter, and then sort the set of images stored in order of increasing values of disparity or dissimilarity with respect to the images in the course of construction, the system also comprising restoring means for displaying a certain number of stored images having a certain degree of similarity to the images in the course of construction.

40. A system according to claim 39, wherein said disparity or dissimilarity is defined according to an equation of the type ##EQU35## where Q is the number of features which can be selected, a_F =1 or 0 according to whether the feature has been selected or not, the quantity ##EQU36## and represents a standardization factor with which to weight the various features/ and the vectors C_F, C_Fi represent the image being constructed and the image i of the data base, respectively, within the limits of the feature F.

41. A system according to claim 40, wherein said system comprises means for pointing to (selecting) one of the images displayed and means for replacing the descriptive components of the features selected in the image being formed with those of the image selected.

42. A system according to claim 40, wherein said set of images of the data base is organized and presented in a hierarchical manner, and wherein pointing to (selecting) one of the images displayed replaces the descriptive components of the features selected in the image being constructed with those of the image selected.