Method of indexing and comparing multimedia documents

• US 20030101164A1
• Filed: 10/11/2002
• Published: 05/29/2003
• Est. Priority Date: 10/12/2001
• Status: Active Grant

• Current Assignee: Commissariat a L'Energie Atomique (AES Corporation)
• Original Assignee: Commissariat a L'Energie Atomique (AES Corporation)
• Inventors: Essafi, Hassane, Pic, Marc, Gayrard, Michel-Pierre
• Granted Patent: US 6,988,093 B2
• Time in Patent Office: Days
• US Class Current: 707/1
• CPC Class Codes: G06F 16/40 of multimedia data, e.g. slideshows comprising image and additional audio data retrieval of still image data G06F16/50; retrieval of audio data G06F16/60; retrieval of video data G06F16/70
• CPC Class Codes: G06F 16/41 Indexing; Data structures therefor; Storage structures
• CPC Class Codes: Y10S 707/99931 Database or file accessing
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing

Abstract

The method of comparing two composite multimedia documents, each comprising at least two individual media (images, sounds, video signals, animated vector graphics, or texts), comprises the following steps: a) allocating a meta-identifier to each of the multimedia documents, the meta-identifier being in the form of a weighted hypergraph of nodes and relationships between said nodes and including meta-segments unambiguously identifying individual media making up the multimedia document concerned; b) performing recursion on the secondary tree structures of intra-medium relationships for the individual media of each of the documents; c) for the hypergraph of each individual medium of the document, performing an operation of maximizing matching with the hypergraph of an individual medium of the second document; d) for the hypergraph of each individual medium of the first document, determining the costs of edit operations leading to maximum matching with a hypergraph of an individual medium of the second document, and expressing distances between the individual media as a function of these costs; e) performing recursion over the main tree structure for producing inter-media relationships between the individual media of each of the documents; f) for the hypergraph of all of the individual media of the first document, performing an operation of maximizing matching with the hypergraph of all of the individual media of the second document; and g) for the hypergraph of all of the individual media of the first document, determining the costs of the edit operation that produces maximum matching with a hypergraph of all of the individual media of the second document, and expressing the distance between the first and second multimedia documents as a function of said cost.

Claims

1. / A method of comparing first and second composite multimedia documents, each comprising at least two individual media selected from categories comprising images, sounds, video signals, animated vector graphics, and texts,

the method being characterized in that it comprises the following steps:

a) allocating a meta-identifier to each of the first and second composite multimedia documents, which meta-identifier is in the form of a weighted hypergraph of nodes and relationships between said nodes and includes meta-segments unambiguously identifying individual media making up the multimedia document concerned;

b) performing recursion over secondary trees of intra-medium relationships of the individual media of each of the first and second composite multimedia documents;

c) for the hypergraph of each individual medium of the first multimedia document, performing an operation of maximizing matching with the hypergraph of an individual medium of the second multimedia document;

d) for the hypergraph of each individual medium of the first multimedia document, determining the costs of editing operations leading to maximum or quasi-maximum matching with a hypergraph of an individual medium of the second multimedia document, and expressing distances between the individual media as a function of said costs;

e) performing recursion over the main tree for producing inter-media relationships between the individual media of each of the first and second composite multimedia documents;

f) for the hypergraph of all of the individual media of the first multimedia document, performing an operation of maximizing matching with the hypergraph for all of the individual media of the second multimedia document; and

g) for the hypergraph of all of the individual media of the first multimedia document, determining the costs of the edit operation that produces maximum or quasi-maximum matching with a hypergraph of all of the individual media of the second multimedia document, and expressing the distance between the first and second composite multimedia documents as a function of said cost.

2. / A method according to claim 1, characterized in that steps c) and d), themselves comprise the following steps:

c1) for each individual medium of the first multimedia document to be compared with an individual medium of the second multimedia document, defining as a function of the looked-for similarities, an intra-medium cost function based on a principle of editing hypergraphs making reference to a similarity distance between hypergraphs;

c2) exploring all of the possible transformations enabling the hypergraph of each of the individual media of the first multimedia document to be transformed into a hypergraph that is as close as possible to the hypergraph of each of the individual media of the second multimedia document;

d1) determining the cost of each transformation in application of the rules defined in step c1); and

d2) for each of the individual media of the first multimedia document, selecting the transformation of lowest cost.

3. / A method according to claim 1, characterized in that steps f) and g) themselves comprise the following steps:

f1) for all of the individual media of the first multimedia document to be compared with the individual media of the second multimedia document, defining as a function of the looked-for similarities, an inter-media cost function based on a principle of editing hypergraphs with reference to a similarity distance between hypergraphs;

f2) exploring all of the possible transformations enabling the hypergraph of the first composite multimedia document to be transformed into a hypergraph that is as close as possible to the hypergraph of the second composite multimedia document;

g1) determining the cost of each transformation in application of the rules defined in step f1); and

g2) selecting the transformation of lowest cost.

4. / A method according to claim 1, characterized in that steps c) and d) comprise implementing a sub-optimal optimization method such as a genetic algorithm, processing by a neural network or by simulated annealing, thereby producing a transformation whose cost is lowest in the context of the optimization method used.

5. / A method according to claim 1, characterized in that steps f) and g) comprise implementing a sub-optimal optimization method such as a genetic algorithm, processing by a neural network or by simulated annealing, thereby producing a transformation whose cost is lowest in the context of the optimization method used.

6. / A method according to claim 1, characterized in that when comparing a first composite multimedia document to which a meta-identifier is allocated and which is segmented into meta-segments, point-to-point comparison is performed of meta-segments of vector kind by means of a vector distance selected from distances of the Euclidean, Reimann with parameter L, and Mahalanobis types, so as to produce results constituting scores for pairing between meta-segments compared in pairs, and comparing meta-segments of the hypergraphs and producing a synthesized score for the distance between the documents by weighting the results of the point-to-point comparisons of the meta-segments by means of the probability of pairing between each corresponding branch of the trees of the two documents.

7. / A method according to claim 1, characterized in that it is applied to storing multimedia documents in a database, this storage operation comprising organizing hypergraphs representing the meta-identifiers of the multimedia documents to be archived by automatic hierarchical classification of branches that are common, identical, or quasi-identical.

8. / A method according to claim 7, characterized in that the addition of a new meta-identifier corresponding to a multimedia document for archiving in a database already comprising a set of meta-identifiers and a set of intermediate objects representing portions of meta-identifiers designed to be easily recognized comprises the following steps:

i) breaking down the new meta-identifier into individual meta-identifiers encoding the various individual media contained in the multimedia document to be archived;

ii) constructing a tree for producing relationships between individual media; and

iii) recursively applying steps i) and ii) to each individual meta-identifier to produce trees for producing relationships within each of the individual media, the trees being stored independently, but inclusion relationships being added to mark the links between an individual medium described in the tree for producing relationships between the individual media and the components of said individual medium in the tree for producing relationships within said individual medium under consideration.

9. / A method according to claim 8, characterized in that the step of breaking down a new meta-identifier is performed by scanning the entire hypergraph associated with the new meta-identifier and selecting groups of adjacent nodes having an identical medium.

10. / A method according to claim 8, characterized in that the step of constructing a tree for producing relationships between individual media comprises, in particular, the following operations:

constructing a simplified hypergraph by associating a node with each individual meta-identifier and copying the relationships linking the nodes of the individual media to their respective meta-identifiers, while eliminating relationships of the same kind linking the same two nodes;

subdividing the hypergraph into connected sub-hypergraphs by increasing number of nodes;

organizing similar sub-hypergraphs having the same number of nodes into classes;

characterizing each class by a single representative holding average properties for the elements of the class; and

organizing the previously defined classes in hierarchical manner by means of similarity relationships between portions of their representatives.

11. / A method according to claim 1, characterized in that it is applied to searching for a multimedia document archived in a database, and in that it comprises the following steps:

presenting a composite request itself comprising multimedia documents linked together by logical operators;

allocating a meta-identifier to each of the multimedia documents of the database, which meta-identifier is in the form of a weighted hypergraph of nodes and relationships between the nodes and includes meta-segments identifying in unambiguous manner the individual media making up the multimedia document concerned;

allocating a meta-identifier to the composite request, which meta-identifier is in the form of a weighted hypergraph of nodes and relationships between the nodes and includes meta-segments identifying unambiguously the individual media making up the composite request;

performing recursion over secondary trees of intra-medium relationships of the individual media of each of the multimedia documents of the database;

performing recursion over the secondary trees of the intra-medium relationships of the individual media of the composite request;

performing recursion over the main tree for producing inter-media relationships between the individual media of each of the multimedia documents of the database;

performing recursion over the main tree for producing inter-media relationships between the individual media of the composite request;

producing an overall hypergraph combining all of the hypergraphs of the composite request linked by said logic operators; and

comparing said overall hypergraph with the hypergraphs of the multimedia documents of the database in application of the following steps;

for the hypergraph of each individual medium of the composite request, an operation of maximizing matching with the hypergraph of an individual medium of each of the multimedia documents of the database;

for the hypergraph of each individual medium of the composite request, determining the costs of edit operations that lead to maximum or almost maximum matching with a hypergraph of an individual medium of each of the multimedia documents of the database, and expressing distances between the individual media as a function of said costs;

for the hypergraph of all of the individual media of the composite request, an operation of maximizing matching with the hypergraph of all of the individual media of each of the multimedia documents of the database;

for the hypergraph of all of the individual media of the composite request, determining the costs of edit operations leading to maximum or almost maximum matching with a hypergraph of all of the individual media of each of the multimedia documents of the database, and expressing distances between the composite request and each of the multimedia documents of the database as a function of said costs; and

organizing a list of multimedia documents of the database in decreasing order of previously calculated costs.

12. / A method according to claim 11, characterized in that the steps of individually processing multimedia documents of the database are performed prior to presenting a composite request, and the results of said individual processing steps are stored for processing a set of different composite requests, in that the database is organized with storage comprising arranging hypergraphs representing the meta-identifiers of the multimedia documents to be archived by automatic hierarchical classification of identical or almost identical branches they have in common, and in that instead of comparing the full hypergraph of the composite request with the hypergraph of all of the multimedia documents in the database, a hierarchical search is performed in a tree structure of classes of hypergraphs of all of the multimedia documents of the database, and comparisons are performed between the overall hypergraphs of the composite request and the representatives of said classes.

18. / A method according to claim 1, characterized in that at least one individual medium is a monomedium document belonging to a single category of media.

19. / A method according to claim 1, characterized in that at least one individual medium is itself a multimedia document comprising sub-elements belonging to different categories of media.

13. / A method of indexing a composite multimedia document comprising at least two individual media selected from categories comprising images, sounds, video signals, animated vector graphics, and texts, the method being characterized in that it comprises the following steps:

a) allocating a meta-identifier to composite multimedia document, which meta-identifier is in the form of a weighted hypergraph of nodes and relationships between said nodes and includes meta-segments unambiguously identifying the individual media making up the composite request multimedia document;

b) performing recursion over secondary tree structures of intra-medium relationships of the individual media of the composite multimedia document; and

c) performing recursion over the main tree structure for producing inter-media relationships between the individual media of the composite multimedia document.

14. / A method according to claim 13, characterized in that it is applied to storing multimedia documents in a database, this storage operation comprising organizing hypergraphs representing the meta-identifiers of the multimedia documents to be archived by automatic hierarchical classification of branches that are common, identical, or quasi-identical.

15. / A method according to claim 14, characterized in that the addition of a new meta-identifier corresponding to a multimedia document for archiving in a database already comprising a set of meta-identifiers and a set of intermediate objects representing portions of meta-identifiers designed to be easily recognized comprises the following steps:

i) breaking down the new meta-identifier into individual meta-identifiers encoding the various individual media contained in the multimedia document to be archived;

ii) constructing a tree for producing relationships between individual media; and

iii) recursively applying steps i) and ii) to each individual meta-identifier to produce trees for producing relationships within each of the individual media, the trees being stored independently, but inclusion relationships being added to mark the links between an individual medium described in the tree for producing relationships between the individual media and the components of said individual medium in the tree for producing relationships within said individual medium under consideration.

16. / A method according to claim 15, characterized in that the step of breaking down a new meta-identifier is performed by scanning the entire hypergraph associated with the new meta-identifier and selecting groups of adjacent nodes having an identical medium.

17. / A method according to claim 14, characterized in that the step of constructing a tree for producing relationships between individual media comprises, in particular, the following operations:

constructing a simplified hypergraph by associating a node with each individual meta-identifier and copying the relationships linking the nodes of the individual media to their respective meta-identifiers, while eliminating relationships of the same kind linking the same two nodes;

subdividing the hypergraph into connected sub-hypergraphs by increasing number of nodes;

organizing similar sub-hypergraphs having the same number of nodes into classes;

characterizing each class by a single representative holding average properties for the elements of the class; and

organizing the previously defined classes in hierarchical manner by means of similarity relationships between portions of their representatives.