METHOD AND SYSTEM FOR GENERATING A PICTORIAL REFERENCE DATABASE USING GEOGRAPHICAL INFORMATION

• US 20140207781A1
• Filed: 03/24/2014
• Published: 07/24/2014
• Est. Priority Date: 06/03/2008
• Status: Active Grant

• Current Assignee: Qualcomm, Inc.
• Original Assignee: Qualcomm, Inc.
• Inventors: Quack, Till
• Granted Patent: US 9,489,402 B2
• Time in Patent Office: Days
• US Class Current: 707/738
• CPC Class Codes: G06F 16/29 Geographical information databases
• CPC Class Codes: G06F 16/51 Indexing; Data structures therefor; Storage structures
• CPC Class Codes: G06F 16/56 having vectorial format
• CPC Class Codes: G06F 16/5838 using colour
• CPC Class Codes: G06T 17/05 Geographic models
• CPC Class Codes: G06T 2201/0051 Embedding of the watermark in the spatial domain
• CPC Class Codes: G06V 10/24 Aligning, centring, orientation detection or correction of the image
• CPC Class Codes: G06V 20/10 Terrestrial scenes scenes under surveillance with static cameras G06V20/52; scenes perceived from the exterior of a vehicle G06V20/56; scenes perceived from the interior of a vehicle G06V20/59

Abstract

For generating a pictorial reference database from a plurality of digital images, distributed geographical sub-areas are defined (S1). For the geographical sub-areas, selected (S2) from the plurality of digital images are images with a geo-tag located in the respective geographic sub-area. Feature vectors are generated (S31) for localized visual features of the selected images. Based on the feature vectors, matching features are determined (S32) for pairs of the selected images. For pairs with matching features, in each case, a measure of visual similarity is computed (S33) based on different geometric arrangements of the localized visual features. Based on the visual similarity, clusters of images with matching objects are determined (S5) and stored (S6) in the pictorial reference database. The pictorial reference database can be generated automatically from a huge collection of images by dividing the images into geographical subsets which can be processed individually and possibly in parallel.

Claims

1. Computer-implemented method of generating a pictorial reference database (10) from a plurality of digital images, the method comprising:

defining (S1) a plurality of distributed geographical sub-areas (60, 61, 62, 63, 64);

selecting (S2), for at least one of the geographical sub-areas (60, 61, 62, 63, 64), from the plurality of digital images, selected images with a geo-tag located in the respective geographic sub-area (60, 61, 62, 63, 64);

generating (S31), for the selected images, feature vectors for localized visual features of the selected images;

determining (S32), for pairs of the selected images, matching features based on the feature vectors;

computing (S33), for pairs of the selected images having matching features, in each case, a measure of visual similarity based on different geometric arrangements of the localized visual features;

determining (S5) dusters of images with matching objects based on the measures of visual similarity; and

storing (S6) the clusters of images in the pictorial reference database (10).

2. The method of claim 1, wherein the method further comprises computing (S43), for pairs of the selected images, in each case, a measure of textual similarity based on textual metadata associated with the respective selected images;

and the determining (S5) the clusters of images with matching objects is based on the measures of visual similarity and the measures of textual similarity.

3. The method of claim 2, wherein the method further comprises generating (S41) an image-specific stop list, the stop list including location-specific words depending on the geo-tag associated with a respective image, and filtering words (S42) included in the stop list from metadata associated with the respective image, prior to computing (S43) the measure of textual similarity.

4. The method of one of claims 1 to 3, further comprising classifying (S7) the clusters of images, in each case, as an object type, indicative of a cluster comprising images of objects, or an event type, indicative of a cluster comprising images of events, based on at least one of time stamps, associated with the images, number of different persons having provided the images, textual information associated with the images, and visual features of the images.

5. The method of one of claims 1 to 4, further comprising determining (S8) for the clusters of images, in each case, a textual label by determining statistically from textual metadata associated with the images of the respective cluster word combinations occurring most frequently and with statistical confidence.

6. The method of claim 5, further comprising determining (S9) for the clusters of images, in each case, at least one link to information related to the respective cluster'"'"'s images by searching in one or more Internet-based data collection for the word combinations occurring most frequently for the respective cluster, and keeping from the search result links to pages which include images with at least a defined minimum similarity to images of the respective cluster.

7. The method of one of claims 1 to 6, wherein computing (S33) the measure of visual similarity includes computing multiple view geometry mappings, for the pairs of the selected images having matching features, to determine inlaying feature matches, and generating a dissimilarity matrix based on the number of inlaying feature matches of the pairs of selected images;

and determining the clusters (S5) includes applying a clustering algorithm to the dissimilarity matrix.

8. The method of claim 7, wherein determining the clusters (S5) includes applying a hierarchical agglomerative clustering algorithm to the dissimilarity matrix, the clustering algorithm including at least one of single-link-clustering, complete-link-clustering and average link-clustering.

9. The method of one of claims 1 to 8, wherein defining (S1) a plurality of distributed geographical sub-areas (60, 61, 62, 63, 64) includes defining the sub-areas (60, 61, 62, 63, 64) in each case as a regular geometrical shape, e.g. a square of approximately 200 m by 200 m, defining the geographical sub-areas (60, 61, 62, 63, 64) such that geographical sub-areas (60, 61, 62, 63, 64) with a neighboring centre have a partial overlap, and arranging the centre (Z0, Z1, Z2, Z3, Z4) of the geometrical shape on a different intersection (6′

) of a grid (6) laid over a geographical area, e.g. a grid (6) with square grid cells (6′

″

) having intersections (6′

) spaced at 100 m;

generating the feature vectors (S31) includes generating feature vectors for scale-invariant interest points; and

computing the visual similarity (S33) includes determining numbers of inlaying matches of a geometric transformation between features of the pairs of the selected images having matching features.

10. The method of one of claims 1 to 9, further comprising receiving at an information server (20) an information request from a communication terminal (5), the information request including a digital image;

matching the digital image received to one or more matching images of one of the clusters stored in the reference database (10); and

returning to the communication terminal (5) cluster information associated with the cluster containing the matching images, the cluster information including at least one of textual information, geographical location information and a link for retrieving further related information.

11. The method of one of claims 1 to 10, further comprising determining (S10) for images of a cluster, in each case, at least one user-selectable area in the respective image for activating a link to information associated with the respective cluster, based on locations of matching features having a defined level of occurrence frequency in the respective cluster.

12. The method of one of claims 10 to 11, further comprising generating for image pairs of an image cluster feature constraint pairs, a feature constraint pair indicating in each case a first visual feature in a first image of the image pair matching a second visual feature in a second image of the image pair;

determining clusters of features based on the feature constraint pairs and mutual distances between the feature vectors;

computing from the feature vectors associated with a feature cluster a centroid vector;

storing for each feature cluster its centroid vector and a feature cluster identifier; and

assigning to the images of an image cluster, in each case, the respective feature cluster identifier as the image'"'"'s visual feature information.

13. A computer system (1) for generating a pictorial reference database (10) from a plurality of digital images, the system (1) comprising:

a stored definition (11) of a plurality of distributed geographical sub-areas (60, 61, 62, 63, 64);

a selecting module (12) configured to select, for at least one of the geographical sub-areas (60, 61, 62, 63, 64), from the plurality of digital images, selected images with a geo-tag located in the respective geographic sub-area (60, 51, 62, 63, 64);

an image matching module (13) configured to generate, for the selected images, feature vectors for localized visual features of the selected images, to determine, for pairs of the selected images, matching features based on the feature vectors, and to compute, for pairs of the selected images having matching features, in each case, a measure of visual similarity based on different geometric arrangements of the localized visual features; and

a clustering module (S14) configured to determine clusters of images with matching objects based on the measures of visual similarity, and to store the clusters of images in the pictorial reference database.

14. The system (1) of claim 13, wherein the system (1) further comprises a text matching module (15) configured to compute, for pairs of the selected images, in each case, a measure of textual similarity based on textual metadata associated with the respective selected images;

and the clustering module is configured to determine the clusters of images with matching objects based on the measures of visual similarity and the measures of textual similarity.

15. The system (1) of claim 14, wherein the text matching module (15) is further configured to generate an image-specific stop list, the stop list including location-specific words depending on the geo-tag associated with a respective image, and to filter words included in the stop list from metadata associated with the respective image, prior to computing the measure of textual similarity.

16. The system (1) of one of claims 13 to 15, further comprising a classification module (16) configured to classify the clusters of images, in each case, as an object type, indicative of a cluster comprising images of objects, or an event type, indicative of a cluster comprising images of events, based on at least one of time stamps, associated with the images, number of different persons having provided the images, textual information associated with the images, and visual features of the images.

17. The system (1) of one of claims 13 to 16, further comprising a labeling module (17) configured to determine for the clusters of images, in each case, a textual label by determining statistically from textual metadata associated with the images of the respective cluster word combinations occurring most frequently and with statistical confidence.

18. The system (1) of claim 17, further comprising a linking module (18) configured to determine for the clusters of images, in each case, at least one link to information related to the respective cluster'"'"'s images by searching in one or more internet-based data collection (41) for the word combinations occurring most frequently for the respective cluster, and to keep from the search result links to pages which include images with at least a defined minimum similarity to images of the respective cluster.

19. The system (1) of one of claims 13 to 20, wherein the image matching module (13) is configured to compute the measure of visual similarity by computing multiple view geometric mappings for determining inlaying feature matches for the pairs of the selected images having matching features, and to generate a dissimilarity matrix based on the number of inlaying feature matches of the pairs of selected images;

and the clustering module is configured to determine the clusters by applying a clustering algorithm to the dissimilarity matrix.

20. The system (1) of claim 19, wherein the clustering module (14) is configured to determine the clusters by applying a hierarchical agglomerative clustering algorithm to the dissimilarity matrix, the clustering algorithm including at least one of single-link-clustering, complete-link-clustering and average link-clustering.

21. The system (1) of one of claims 13 to 20, wherein the definition of the plurality of distributed geographical sub-areas (60, 61, 62, 63, 64) is configured to define the sub-areas (60, 61, 62, 63, 64) in each case as a regular geometrical shape, e.g. a square of approximately 200 m by 200 m, to define the geographical sub-areas (60, 61, 62, 63, 64) such that geographical sub-areas (60, 61, 62, 63, 64) with a neighboring centre (Z0, Z1, Z2, Z3, Z4) have a partial overlap, and to arrange the centre (Z0, Z1, Z2, Z3, Z4) of the geometrical shape on a different intersection (6′

) of a grid (6) laid over a geographical area, e.g. a grid (6) with square grid cells (6′

″

) having intersections (6′

) spaced at 100 m; and

wherein the image matching module (S13) is configured to generate the feature vectors for scale-invariant interest points, and to compute the measure of visual similarity by determining numbers of inlaying matches of a geometric transformation between features of the pairs of the selected images having matching features.

22. The system (1) of one of claims 13 to 21, further comprising an information server module (20) configured to receive an information request from a communication terminal (5), the information request including a digital image, to match the digital image received to one or more matching images of one of the clusters stored in the reference database (10), and to return to the communication terminal (5) cluster information associated with the cluster containing the matching images, the cluster information including at least one of textual information, geographical location information and a link for retrieving further related information.

23. The system (1) of one of claims 13 to 22, further comprising a link placement module (19) configured to determine for images of a cluster, in each case, at least one user-selectable area in the respective image for activating a link to information associated with the respective cluster, based on locations of matching features having a defined level of occurrence frequency in the respective cluster.

24. The system (1) of one of claims 13 to 23, further comprising a compression module (21) configured to generate for image pairs of an image cluster feature constraint pairs, a feature constraint pair indicating in each case a first visual feature in a first image of the image pair matching a second visual feature in a second image of the image pair;

to determine clusters of features based on the feature constraint pairs and mutual distances between the feature vectors;

to compute from the feature vectors associated with a feature cluster a centroid vector;

to store for each feature cluster its centroid vector and a feature cluster identifier; and

to assign to the images of an image cluster, in each case, the respective feature cluster identifier as the image'"'"'s visual feature information.

25. A computer program product comprising computer program code means for controlling one or more processors of a computer system (1) such that the computer system (1)

defines (S1) a plurality of distributed geographical sub-areas (60, 61, 62, 63, 64);

selects (S2), for at least one of the geographical sub-areas (60, 61, 62, 63, 64), from a plurality of digital images, selected images with a geo-tag located in the respective geographic sub-area (60, 61, 62, 63, 64);

generates (S31), for the selected images, feature vectors for localized visual features of the selected images;

determines (S32), for pairs of the selected images, matching features based on the feature vectors;

computes (S33), for pairs of the selected images having matching features, in each case, a measure of visual similarity based on different geometric arrangements of the localized visual features;

determines (S5) clusters of images with matching objects based on the measures of visual similarity; and

stores (S6) the clusters of images in a pictorial reference database (10).