AU742595B2 - Image search system - Google Patents

Description

I*

S&FRef: 503035

AUSTRALIA

PATENTS ACT 1990 COMPLETE SPECIFICATION FOR A STANDARD PATENT

ORIGINAL

Name and Address of Applicant Canon Kabushiki Kaisha 30-2, Shimomaruko 3-chome, Ohta-ku Tokyo 146 Japan Stephen Leslie Tyler, Ken Carroll, Natasha May Sainty, Jeremy David Michael Thorp Actual Inventor(s): Address for Service: Invention Title: Spruson Ferguson St Martins Tower 31 Market Street Sydney NSW 2000 Image Search System ASSOCIATED PROVISIONAL APPLICATION DETAILS [33] Country [31] Applic. No(s) AU PQ1034 AU PQ1038 AU PQ1037 AU PQ1030 AU PQ1036 AU PQ1039 [32] Application Date 18 Jun 1999 18 Jun 1999 18 Jun 1999 18 Jun 1999 18 Jun 1999 18 Jun 1999 The following statement is a full description of this invention, including the best method of performing it known to me/us:- lP Australia Documents received on: C0 I 6 JUN 2000 5815c Batch No: IMAGE SEARCH SYSTEM Technical Field of the Invention The present invention relates generally to databases and, in particular, to archiving and retrieving objects based on keyword or natural language queries.

The invention has been developed primarily for archiving and retrieving images, and will be described hereafter with reference to this application. However, it will be appreciated that the invention is not limited to this field of use. The invention can be applied to any keyword-categorised objects including movie clips, sound clips, and io written matter, including books and patent specifications.

Background Art Arrangements are known for archiving images and selecting images for retrieval from such archives. With the size of image libraries growing constantly, the importance of an effective method of searching the image libraries for images meeting various criteria Is becomes more evident.

Recently, online image services have become available whereby a customer can search relatively large libraries of images, and order any images they wish to use for their purposes. Such uses may include the creation of publications and the like.

;Often, a prototype publication is created by comping preview images. Comping 20 is a process of assembling a prototype publication using images that are normally not to publication standards or may even be watermarked, thereby creating an incentive to purchase usable images.

However, most systems use a simple keyword search whereby a user inserts one or more keywords and a search engine scans through various keywords on which images 25 were indexed, to find those images with indexing keywords corresponding to the search keywords.

Often, such systems result in either too many or too few images meeting the search criteria. It is then required of the user to alter the search criteria until a manageable number of images are retrieved. A further disadvantage is that often large number of images from the same publisher are grouped together, thereby again reducing the choice of the client. It can even be that several of the retrieved images are from the same photo shoot.

Existing arrangements are very dependent on the search keywords being the same, or similar to the indexing keywords. For example, if the word "dog" is searched for, but the image is indexed under "Scottish Terrier", most search engines would not find 503035AU.doc the image. However, the image may be found when looking for images with keyword "Scottish". This makes such arrangement very language dependent, and they are unable to resolve queries where the query is in a different language than the indexing language.

Most prior art arrangements do not perform any sorting of images meeting the search criteria. They simply present the first predetermined number of images found and in response to an instruction continue to present a further predetermined number of images.

Arrangements that do implement scoring require of the search engine to scan through all the matching records in order to apply the scoring in order to present only the 1o "best" images. It is clear that the time required for such an action is restrictive with very large databases.

Disclosure of the Invention It is an object of the present invention to substantially overcome, or at least ameliorate, one or more disadvantages of existing arrangements.

According to an aspect of the invention, there is provided an image storage and retrieving system comprising: a plurality of images, each stored at a respective location within said system and having at least one associated keyword, each of said keywords having at least one associated meaning reference, each meaning reference being one of a plurality of meaning references obtained from a library of meaning references; a relationship table arranged to associate said meaning references to corresponding ones of said images; and an interpreter for interpreting a user entered query and relating said query to at least one of said meaning references to thereby identify for each said related meaning reference, a predetermined number of said images.

According to another aspect of the invention, there is provided a method of image storage and retrieval comprising the steps of: storing a plurality of images, each image being stored at a respective location and having at least one associated keyword, each of said keywords having at least one associated meaning reference, each meaning reference being one of a plurality of meaning references obtained from a library of meaning references; arranging a relationship table to associate said meaning references to corresponding ones of said images; and 503035AU.doc -3interpreting a user entered query and relating said query to at least one of said meaning references, thereby identifying for each said related meaning reference, a predetermined number of said images.

According to yet another aspect of the invention, there is provided a computer program product including a computer readable medium incorporating a computer program for storing and retrieving images, said computer program product comprising: means for storing a plurality of images, each image being stored at a respective location and having at least one associated keyword, each of said keywords having at least one associated meaning reference, each meaning reference being one of a plurality of meaning references obtained from a library of meaning references; means for arranging a relationship table to associate said meaning references to corresponding ones of said images; and means for interpreting a user entered query and relating said query to at least one of said meaning references, thereby identifying for each said related meaning reference, a predetermined number of said images.

According to yet another aspect of the invention, there is provided a database comprising: a plurality of meaning references obtained from a library of meaning references; ":*"and image pointers associated with at least one of said meaning references for pointing to respective locations of images, wherein each image has at least one associated keyword and each of said keywords has at least one associated meaning reference.

According to yet another aspect of the invention, there is provided a search engine for retrieving at least. one image from a plurality of images, each said image having at least one associated keyword, each of said keywords having at least one associated meaning reference, each meaning reference being one of a plurality of meaning references obtained from a library of meaning references, and each of said meaning references being associated with corresponding ones of said images, said search engine comprising: means for interpreting a user entered query; and means for relating said user entered query to at least one of said meaning references, thereby identifying for each said related meaning reference at least one image for retrieval.

Brief Description of the Drawings 503035AU.doc A number of preferred embodiments of the present invention will now be described with reference to the drawings, in which: Fig. 1 is a schematic block diagram of an image search system according to a preferred embodiment; Fig. 2 is a flow diagram for the search algorithm of the preferred embodiment; Fig. 3 is a parse tree for a simple query; and Fig. 4 is a flow diagram for a ranking algorithm.

Detailed Description including Best Mode Referring to Fig. 1, there is shown a cross vendor image search system 100 1o configured to permit a client 50, utilising an appropriately configured workstation, to send a search query to a search engine 10, the search query specifying criteria for images the client 50 desires to retrieve from an image database 32. The client 50 is indicated generically and may include a client 52 whose workstation is directly coupled to the search engine 10, or a client 51 coupled via a distributed network the Internet) and is an associated server ~The search engine 10 is arranged to process the search query and retrieve images eoee meeting the search query from a database manager 30. The images are then presented as •a response to the query on the client's workstation.

The system 100 includes a number of primary subsystems represented by the search engine 10, a language module 20, a ranking module 11, a learning module 70, the database manager 30 and database construction utilities 40. The ranking module forms part of the search engine The language module 20 manages all aspects of language within the system 100.

The main functionality of the language module 20 is provided by a language module interface 21 which oversees all language operations required by various other processes within the system 100. It parses multiple natural languages, Boolean expressions and performs auxiliary operations such as comparison of sentences and assigning meanings to words.

By parsing a sentence, the language module interface 21 produces a set of related meanings or concepts, termed ConceptIDs. The language module interface 21 returns ConceptIDs to calling modules. ConceptlDs are what the images are indexed on in search and image databases 31 and 32. Thus when parsing a single word sentence (a keyword), a set of ConceptIDs on which to index an image is produced.

503035AU.dc Because the ConceptIDs are language-independent, multiple languages can be facilitated by providing a language thesaurus 22 and a proper noun thesaurus 23 for each language the system 100 wishes to generate the ConceptIDs. The language module interface 21 is able to distinguish between natural language and Boolean expressions in the same sentence. Implicit in the parsing is the need for spelling correction. As an example, the following sentence is a valid input: Man riding horse not show-jumping Initially the parsing involves: performing spelling-correction; 0 recognising Boolean expressions; and 0 forming of compound meanings from associated words.

Compound meanings includes geographical places, proper nouns, and other commonly recognisable constructs. Examples are "Rocky Mountains", "Bill Clinton" and "glass of milk".

The language module interface 21 also has the ability to create entries in the thesauri 22 and 23 when images are supplied with keywords not previously used by creating a new conceptID for each new keyword.

e* The next function of the language module interface 21 is to compare the sentences being parsed and each of the ConceptlDs to produce a score for each ConceptID, the score defining how close the concept(s) defined in the sentences match the ConceptlD. In the preferred embodiment, a natural language parser and disambiguator is used to produce a score for each of the ConceptIDs.

As an alternative method of producing a score for each of the ConceptlDs, ~information contained in the language thesaurus 22 is used. The language thesaurus 22 25 contains two pieces of information that are useful for calculating the score, namely: A polysemy count, which represents a number of dictionary meanings of a word form.

The polysemy count of a word form is used as an approximation of the frequency of usage of that word form. For example, the noun "man" may have 20 dictionary meanings, so it would have a polysemy count of 20. Suppose that the verb "man" has a polysemy count of only 5. It follows from the above that "man" is more commonly used as a noun than a verb, because the noun "man" has a higher familiarity.

A sense number. Within a word form, each meaning is assigned a sense number representing a most common usage of that word within that word form. For example, 503035AU.do the noun "orange" with meaning {orange-fruit} may have a sense number of 1, indicating that that meaning is very common. The noun "orange" with meaning {orange-hue} may have a sense number of 5, indicating that that meaning is very rare.

It is noted that the sense numbers only make sense inside a word form (eg nouns and verbs). Therefore, the adjective "orange" with meaning {orange-colour} may have a sense number of 2, but that does not necessarily indicate that it is less common in usage than the noun "orange" meaning {orange-fruit}.

Using the above polysemy count and sense number, the following estimate of the score of a meaning, say {orange-fruit} for the word orange, may be produced: The polysemy count of the noun "orange" is determined to get a probability that "orange" is a noun by Pm(noun)=polysemy count (noun) sum of polysemy count over all word forms The probability measure that the word "orange" has a meaning {orange-fruit}, given that it is a noun, may be estimated as follows: Pm(orange-fruit noun)=sense number (orange-fruit)/Z(sense numbers of all nouns for orange) o And since: Pm(orange-fruit)=Pm(noun)*Pm(orange-fruit I noun), it follows that the probability measure of the word "orange" having the meaning {orangefruit}can be readily obtained using the above information.

~In one embodiment the score is presented as a probability measure with scores ranging between 0 and 1. In another embodiment the score is presented as a correlation measure with scores ranging between -1 and 1, with negative scores indicating a certainty that the ConceptID does not represent the intended meaning. To accomplish this, the 25 comparison is done on the ConceptIDs, or the semantics of the sentence, instead of the words themselves. This allows an algorithm for performing the comparison to act independently of the source language. The following sentences can thus be determined as meaning the same thing, even though they are written in different languages: Unefemme avec un chien A woman with a dog.

Een vrouw met een hond Thus, a set of language independent ConceptlDs are produced for each sentence, each ConceptID being associated with a score.

503035AU.doc Yet another function of the language module interface 21 is to disambiguate word-senses. This functionality is desired to associate the correct meaning of a keyword with an image so that it can be indexed/retrieved accordingly. For instance, the word 'orange' when used to describe an image is known by a person assigning the keyword but not an automatic indexing program. However, it could be {orange-fruit} or {orangecolour} with either meaning being valid. By examining the caption associated with the image, the language module interface 21 can make an estimation as to a most likely meaning. If for instance the word 'banana' was also provided as another keyword of the image, it is highly probable that {orange-fruit} is intended, rather than {orange-colour}.

1o Although the image is still indexed on both these possible meanings or ConceptIDs, the image can be indexed on the meaning {orange-fruit} with a higher score.

To accomplish these functions the language module interface 21 interacts with language thesauri 22 and proper noun thesauri 23. Each language thesaurus 22 maintains a database of word forms, word meanings and relationships for a specific language. Each language thesaurus 22 is indexed on the same ConceptDs (meanings), irrespective of language. That is, the English word 'head' meaning body-part and the French word 'tete' would generate the same ConceptID. However, the English word 'head' meaning boss or ,chief would generate the same meaning code as the French words 'chef and 'directeur'.

As well as returning the set of ConceptIDs associated with a word, the language °Too thesaurus 22 can also supply a set of other meanings related to a particular ConceptID.

In accordance with an instruction to the language thesaurus 22, the language module interface 21 generates a meaning or a set of possible meanings for an input. This can include: ;:expanding a word or phrase into a list of meanings; °25 returning the direct superordinate of an input, for example a generalisation of 'terrier' is 'dog'; returning the direct subordinates of an input, for example specialisations of 'terrier' are 'scottish terrier', 'Yorkshire terrier' etc.; returning the constituent parts of an input, for example 'hand' will return 'fingers', 'palm', 'thumb' etc.; returning the meaning of which this is part of, for example, 'finger' will return 'hand'; returning a list of meanings composing an input, for example, 'beach' would generate 'sand', 'sea' etc.; 503035AUdoc -8returning the list of meanings for which an input is a compositional substance, for example 'sand' would yield 'beach', 'desert', 'glass', etc.; and returning the most meaningful generalisation of an input, for example 'boy' or 'person' would yield 'human'.

Each proper noun thesaurus 23 takes as input a phrase in a specific language and returns a ConceptID identifying it.

The language module interface 21 also produces a parse tree from a sentence.

The parse tree includes nodes and leaves. Each leaf of the tree is dedicated to a word (or phrase) from the input sentence. Stored at the leaf with the word is a set of related 0o concepts that the word can convey in the language of the sentence. As discussed before, these related meanings include: specialisations eg. terrier is a specialisation of dog; generalisations eg. dog is a generalisation of terrier; coordinate sisters eg. wolf and dog have the same parent (canine); Part Of- eg. paw is a part of dog; and Composed Of- eg. dog is composed of hair (amongst other things).

The nodes are Boolean operators. The Boolean operators are either from the sentence or alternatively are inserted by the language module interface 21.

In summary, the language and proper noun thesauri 22 and 23, enables the language module interface 21 to provide functionality that includes the following: given a list of keywords, caption and language for an item, returns a list of ConceptIDs for each of the keywords together with the score of each ConceptID, the score indicating how closely each ConceptID matches the generating keyword from the keyword list, for the given parameters.

25 As an example, keyword "arm" and caption "tattoo on arm" in the English language will produce for "arm": ConceptID Description (not included Score (0-1) but provided for clarity) 10765:0.60 arm limb (noun) 0.60 10889:0.20 arm weapon (noun) 0.34 10665:0.20 arm to supply with 0.28 weapons (verb) 50035AU.doc -9- In an alternative embodiment, the list of ConceptIDs includes a probability for each ConceptID as follows: ConceptID Description (not included Score (0-100%) but provided for clarity) 10765:0.60 arm limb (noun) 10889:0.20 arm weapon (noun) 10665:0.20 arm to supply with weapons (verb) produces the parse tree from a sentence; and 0 given two sentences, compare them for semantic closeness, that is the proximity in their ConceptIDs. For example 'man riding horse' and 'man riding palomino' gives a very close match, while 'man riding wave' and 'man riding horse' doesn't give so close a match.

The database manager 30 manages an interface to the two databases in the system 100. These databases are the image database 32 and the search database 31.

To manage the separate databases 31 and 32, the database manager 30 utilizes an nimage database manager 34 and a search database manager 33. The image database manager 34 controls access to the image database 32 for construction/update and generation of the search database 31 whereas the search database manager 33 is used to 15 construct and retrieve records from the search database 31.

The database construction utilities 40 are a set of independent processes for creating the databases 31 and 32. An image database creator 41 constructs the image database 32 from vendor supplied volumes or alternatively from WWW acquisition.

Input into the image database 32, which is managed by the image database manager 34, is preferably in the form of a text-file(s). Each input file typically includes a list of images and their meta-data, one image record per line. Each image-record includes at least the following information: Image-name; publisher/volume-information; keywords; and caption.

503035AU.doc In the image database 32, each image is primarily indexed on the list of ConceptIDs. The ConceptIDs are generated by the language module 20 from the keywords included in the image-record. As discussed above, the language module also returns the scores defining how closely the keywords and each of the ConceptID s relate in the meanings they represent.

The caption is encoded into a parse-tree containing the ConceptID's rather than the actual words. The parse tree is also created by the language module 20. Thus, the ConceptIDs and the parse tree are stored along with the image.

Alternatively, images can be acquisitioned from the World Wide Web. Such a ,o file is assembled for the images being fetched. After all the images are fetched, they are entered into the image database 32 in the same way as when they had been loaded from a file.

The search database 31 is an optimised sub-set of the image database 32.

Ultimately the search database 32 is searched by the search engine 10. A search database creator 42 copies the image records from the image database 32 on a per-concept basis.

Secondly, the image records are ordered in descending score. Therefore, associated with each ConceptID is a list of image records associated with that ConceptID and where the image records with keywords and caption closest correspond to that ConceptID appear first in the list. Additionally, to ensure that the user 50 is presented with a selection of S 20o images with multiple variety criteria, the records may be interleaved amongst these criteria. Variety criteria may include publisher/volume, price, image format or licensing conditions. The interleaving may be performed by placing the highest scored image record of each variety criteria first, followed by the second highest scored image record etc. until all the image records of that particular ConceptID are exhausted. This ensures that amongst the first number of image records, all the variety criteria with images on that ConceptD are represented.

The search engine 10 acts as a central interface between the client 50 and the above described search database 31. The search engine 10 returns a set of records from the search database 31 in response to the search query passed to a search engine interface 13 by the client 50. The set of returned records is ordered on relative closeness to the search query. Each returned record may include the following data: publishing information (publisher, volume etc); thumbnail URL of image (if it exists); comping URL of image (if it exists); 503035AUdoc -11caption; indexing keywords; and reason for retrieval, including path from words in query to words in keyword list.

More specifically, the search query in the form of words (a Natural Language query) is processed by a search algorithm 14. In response to the search query the search algorithm 14 produces outputs to the ranking module 11. The outputs includes: Parse Tree; and List of Image Records.

A flow diagram for the search algorithm 14 is presented in Fig. 2. The search algorithm 14, in step 71 fills each leaf of the parse tree, supplied to it by the language module interface 21, with a set of image records based on the ConceptID at that leaf.

Consider for example the following query: tattoo and arm This provides the parse tree shown in Fig. 3. At each leaf of the parse tree, there is provided a ConceptID table. The ConceptID table for 'arm' is as follows: Cl C2 C3

R

R2 R3 R4 R5 R6 R7 60% 25% 15% arm limb Arm weapon arm to supply weapons Knife, gun etc rearm, forearm etc limb Weapon supply leg, thigh Ammunition, gunnery body, human vein, forearm, hand, elbow Percent certainty Concept Specialisation Generalisation Coordinate Sister Is part of Composed of Each cell in the table has an associated image record set. In the example above, the word 'arm' has three different possible meanings associated with it. The table for 'arm' therefore has three columns marked Cl, C2 and C3. Row R2 contains the image record sets for each of the ConceptIDs of 'arm' whereas rows R3 to R7 contain the image record sets for the ConceptIDs related to the ConceptIDs in the row R2.

503035AU.doc -12- In the preferred embodiment the search algorithm 14 is arranged to return not only image records belonging to {arm-limb} above, but also images belonging to the other possible meanings of "arm". Furthermore, the contribution of images by each of the colomns is dependent on the certainty of the intended meaning from the search query. In the example, the Concept {arm-weapon} has a 25% probability that it is the intended meaning. It is therefore preferable that 25% of the images read would be from column C2. The remaining 75% are similarly made up from the concepts in C1 and C3 based on the probability of the remaining meanings.

These image records, read from the image record sets, are already ordered on relative closeness to the ConceptID of the associated cell. Thus, by retrieving the first predetermined number of images for a ConceptID, provides the closest images interleaved by the variety criteria. However, if all the images on one of the ConceptIDs are exhausted, step 71 also goes from row Rn to row Rn+l under that ConceptID in the ConceptID table, thereby adding image records from the related concepts to the exhausted ConceptIDs.

The image records from each of the leaves are combined in step 72 using the boolean operators dictated by the nodes of the parse tree. Implicitly, if more than one image records were read relating to the same image, only one image record is selected ensuring that each image will be presented to the client 50 only once.

20 If, in step 73 it is determined that there are enough image records available after *oo.

they were combined in step 72, the search algorithm 14 passes only these image records to the ranking module 11 in step 75. This ensures that the system 100 is not unnecessarily burdened by passing, say, 1000 image records if only 50 images are to be shown to the .user 50 and that all searches are finite in time, returning the 'best' images.

Inevitably, it may be determined in step 73 that too few records meet the Tf resolved search query. In such a case, the search algorithm 14, in step 74, increments the o number of image records to be read from the search database 31 for each leaf and the search algorithm 14 proceeds to step 71 where more image records are read.

This enables the search algorithm 14 to repeatedly add more image records, and even add image records found on related ConceptiDs until the search algorithm 14 satisfies the image requirements of the ranking module 11.

The ranking module 11 receives from the search algorithm 14 a list of image records and ranks the images found before passing the result to the client via the search 503035AU.doc -13engine interface 13. The ranking is based on data supplied by the client 50 as well as built-in rules.

Fig. 4 shows a ranking algorithm 80 performed by the ranking module 11. The ranking module 11, in step 81, receives from the search algorithm 14 the list of image records and the query in the form of a parse tree that produced the list of image records.

Step 82 scores each image associated with each image record in the list of image records based on the position that image record occupies in the parse tree and the score of that record in the search database 31. This allows for images read from the ConceptID in the first row in the ConceptID table to score higher than images read from related i0 ConceptIDs lower down in the table.

The scoring is preferably modified further by criteria including the client's preferences, the client's history quality of the image and/or popularity of the image. In an alternative embodiment, images included in the image record sets of row R2 that include the search keyword as one of the indexing keywords are scored higher.

In ranking the images, it is desirable to provide to the client 50 a good distribution amongst the variety criteria, including publishers. Step 83 of the ranking algoritmn 80 produces stacks of image records, a stack for each of the variety criteria, the image records being ordered in descending ranking score of the images. Step 84 takes the -top image records from each stack and calculates for each of the image records on top of S 20 their respective stacks a new score. This new score is calculated using its ranking score ooo •and adjusting it according to the number of images already selected for presentation to the client 50 from that variety criteria. On step 85 the image record with the highest new score is selected for the associated image to be presented to the client 50 and the rest of the image records are returned to their respective stacks.

Step 86 determines whether more images are required for presentation to the client 50. With more images required, the ranking algorithm 80 proceeds again to step 84 where the selection process is repeated. With enough images selected for presentation to the client 50, the selected images are passed to the search engine interface 13 in step 89.

Finally, the search engine interface 13 completes the search by sending to a client browser a description of an appearance of an output containing the ranked images.

The appearance can be made dependent on a template, chosen by the client 51 or which specifies a number of thumbnails on the screen, the detail of textual information etc.

503035AU.doc -14- The learning module 70 attempts to improve the results obtained from searches over time. Firstly this is performed by, in the search database 31, keeping a count of how many times an image has been selected. This establishes the relative popularity of an image which modifies the ranking score calculated by the ranking algorithm 80 in step 82.

This modification will normally increase the ranking so that the more popular images are selected over time. However, if the client 50 so desires, popular images can be avoided by using this modification to decrease the ranking.

Secondly, when an image is selected and the learning module 90 has enough information to establish from which of the possible ConceptIDs generated by the same 1o keyword the image was selected, the score in the search database 31 may be adjusted upwards on that ConceptID for the image and downwards on the rest of the ConceptIDs associated with the keyword, for the image and all unselected images and keywords. For example, when an image was given a keyword 'orange', initially the image records indexed on {orange-fruit} and {orange-colour} are given on initial score in the search database 31. The initial score is preferably based on the probability of that meaning associated with the keyword in general usage of the language that the keyword is in.

However, if the image associated with the image records {orange-fruit} and {orangecolour} is chosen when other fruit are included in the search queries, the learning module will adjust the score of {orange-fruit} upwards and the score of {orange-colour} 20 downwards for that image. As another example, when an image was given a keyword 'rock', initially the image records indexed on {rock-music} and {rock-stone} are equally scored in the search database 31. However, if the image associated with the image records {rock-music} and {rock-stone} is chosen when this image was presented to the client because it was related to the ConceptlD in the search query, say for example 'sand' which is a compositional substance of {rock-stone}, the learning module will adjust the :ii! score of {rock-stone} upwards and the score of {rock-music} downwards for that image.

In the preferred embodiment this adjustment is performed when the search database is recreated, avoiding the need to resort all the image records continuously.

Industrial Applicability It is apparent from the above that the embodiments of the invention are applicable to the image database industry.

The foregoing describes only some embodiments of the present invention, and modifications and/or changes can be made thereto without departing from the scope and spirit of the invention, the embodiments being illustrative and not restrictive.

503035AU doc 15 In the context of this specification, the word "comprising" means "including principally but not necessarily solely" or "having" or "including" and not "consisting only of'. Variations of the word comprising, such as "comprise" and "comprises" have corresponding meanings.

e 503035AU.doc

Claims (48)

16- The claims defining the invention are as follows: 1. An image storage and retrieving system comprising: a plurality of images, each stored at a respective location within said system and having at least one associated keyword, each of said keywords having at least one associated meaning reference, each meaning reference being one of a plurality of meaning references obtained from a library of meaning references; a relationship table arranged to associate said meaning references to corresponding ones of said images; and io an interpreter for interpreting a user entered query and relating said query to at least one of said meaning references to thereby identify for each said related meaning reference, a predetermined number of said images. 2. An image storage and retrieving system as claimed in claim 1, wherein said Is relationship table is arranged for each meaning reference to order the corresponding said associated images according to a matching likelihood between said meaning reference and said at least one keyword, and said interpreter identifies said predetermined number of said images having highest said matching likelihood. 20 3. An image storage and retrieving system as claimed in claim 2, wherein said matching likelihood is a probability measure between 0 and 1. S4. An image storage and retrieving system as claimed in claim 2, wherein said matching likelihood is a correlation measure between -1 and 1. An image storage and retrieving system as claimed in claim 3 or 4, said system further comprising a learning module for adjusting said matching probabilities of all the meaning references associated with a selected image. 6. An image storage and retrieving system as claimed in any one of claims 1 to wherein said keywords and said meaning references are language independent. 7. An image storage and retrieving system as claimed in claim 6, wherein said query language is different to said keyword language of said identified image. 503035AU.doc

17- 8. An image storage and retrieving system comprising: a plurality of images, each stored at a respective location within said system and having at least one associated keyword, each of said keywords having at least one s associated meaning reference, each meaning reference being one of a plurality of meaning references obtained from a library of meaning references; a relationship table arranged to associate said meaning references to corresponding ones of said images; and an interpreter for interpreting a user entered query and associating said query to at least one of said meaning references to thereby identify for each said associated meaning reference a predetermined number of said images, and upon there not being said predetermined number of said images available from said at least one meaning references associated to said user entered query, said interpreter is configured to identify more of said images using further meaning references, said further meaning references being related to said at least one meaning references associated to said user entered query. 9. An image storage and retrieving system as claimed in claim 8, wherein said meaning references relate to said at least one meaning references by functions ooo° comprising: 20 specialisations; generalisations; coordinate sisters; part of; and composed of, as herein defined. An image storage and retrieving system comprising: a plurality of images, each stored at a respective location within said system and having at least one associated keyword, each of said keywords having at least one associated meaning reference, each meaning reference being one of a plurality of meaning references obtained from a library of meaning references; a relationship table arranged to associate said meaning references to corresponding ones of said images; and 503035AU.doc -18- an interpreter for interpreting a user entered query and relating said query to at least one of said meaning references, to thereby identify for each said related meaning reference, a number of said images, said number for each said related meaning reference being proportional to a matching probability between said meaning reference relating to said user entered query and said user entered query. 11. An image storage and retrieving system as claimed in claim 10, wherein said interpreter is further arranged to identify for each said related meaning reference images that satisfy a variety measure. 12. An image storage and retrieving system comprising: a plurality of images, each stored at a respective location within said system and having an associated variety measure and at least one associated keyword, each of said keywords having at least one associated meaning reference, each meaning reference being one of a plurality of meaning references obtained from a library of meaning references; a relationship table arranged to associate said meaning references to corresponding ones of said images, said table, for each meaning reference being arranged to order the corresponding said associated images according to a score in a manner whereby said variety measure are interleaved; and an interpreter for interpreting a user entered query and relating said query to at least one of said meaning references to thereby identify for each said related meaning reference, a predetermined number of said images having highest said score. S13. An image storage and retrieving system as claimed in claim 1 wherein said relational table is arranged for each meaning reference to order the corresponding said **associated images according to a matching probability and said interpreter identifies for each said related meaning reference, a predetermined number of said images having highest said matching probability and satisfying a variety measure. 14. An image storage and retrieving system as claimed in any one of claims 11 to 13, wherein said variety measure is selectable from a variety measure set comprising: publisher/volume; price; image format; and 503035AU.doc -19- licencing conditions. An image storage and retrieving system as claimed in any one of claims 1 to 14 wherein said location forms part of a computer system. 16. An image storage and retrieving system as claimed in claim 15, said system being implemented on a distributed computer network. 17. A method of image storage and retrieval comprising the steps of: 1o storing a plurality of images, each image being stored at a respective location and having at least one associated keyword, each of said keywords having at least one associated meaning reference, each meaning reference being one of a plurality of meaning references obtained from a library of meaning references; arranging a relationship table to associate said meaning references to corresponding ones of said images; and interpreting a user entered query and relating said query to at least one of said meaning references, thereby identifying for each said related meaning reference, a :*Goes predetermined number of said images. S 20 18. A method of image storage and retrieval as claimed in claim 17 wherein said 0 0 relationship table is arranged for each meaning reference to order the corresponding said associated images according to a matching likelihood between said meaning reference and said at least one keyword and identifying said predetermined number of said images having highest said matching likelihood. .9

19. A method of image storage and retrieval as claimed in claim 18, wherein said matching likelihood is a probability measure between 0 and 1. A method of image storage and retrieval as claimed in claim 18, wherein said matching likelihood is a correlation measure between -1 and 1.

21. A method of image storage and retrieval as claimed in claim 19' or 20, said method comprising the further step of adjusting said matching probabilities of all the meaning references associated with a selected image. 503035AU.doc

22. A method of image storage and retrieval as claimed in any one of claims 17 to 21, with said keywords and said meaning references are language independent.

23. A method of image storage and retrieval as claimed in claim 22, wherein said query language is different to said keyword language of said identified image.

24. A method of image storage and retrieval comprising: storing a plurality of images, each stored at a respective location and having at 1o least one associated keyword, each of said keywords having at least one associated meaning reference, each meaning reference being one of a plurality of meaning references obtained from a library of meaning references; arranging a relationship table to associate said meaning references to corresponding ones of said images; and interpreting a user entered query and associating said query to at least one of said meaning references to thereby identify for each said associated meaning reference a predetermined number of said images, and upon there not being said predetermined *6oo number of said images available from said at least one meaning references associated to said user entered query, said interpreter is configured to identify more of said images 20o using further meaning references, said further meaning references being related to said at least one meaning references associated to said user entered query. 0@ A method of image storage and retrieval as claimed in claim 24, wherein said meaning references relate to said at least one meaning references by functions comprising: Dole specialisations; generalisations; coordinate sisters; part of; and composed of, as herein defined.

26. A method of image storage and retrieval comprising: 50303SAUdoc -21 storing a plurality of images, each stored at a respective location and having at least one associated keyword, each of said keywords having at least one associated meaning reference, each meaning reference being one of a plurality of meaning references obtained from a library of meaning references; arranging a relationship table to associate said meaning references to corresponding ones of said images; and interpreting a user entered query and relating said query to at least one of said meaning references, to thereby identify for each said related meaning reference, a number of said images, said number for each said related meaning reference being proportional to 1o a matching probability between said meaning reference relating to said user entered query and said user entered query.

27. A method of image storage and retrieval as claimed in claim 26, comprising the further step of identifying for each said related meaning reference images that satisfy a 5is variety measure. ooo

28. A method of image storage and retrieval comprising: *storing a plurality of images, each stored at a respective location and having an associated variety measure and at least one associated keyword, each of said keywords having at least one associated meaning reference, each meaning reference being one of a plurality of meaning references obtained from a library of meaning references; arranging a relationship table to associate said meaning references to corresponding ones of said images, said table, for each meaning reference being arranged to order the corresponding said associated images according to a score in a manner whereby said variety measure are interleaved; and interpreting a user entered query and relating said query to at least one of said meaning references to thereby identify for each said related meaning reference, a predetenrmined number of said images having highest said score.

29. A method of image storage and retrieval as claimed in claim 17 comprising the further steps of: ordering the corresponding said associated images according to a matching probability; and 503035AU.doc 22 identifying for each said related meaning reference a predetermined number of said images having highest said matching probability and satisfying a variety measure. A method of image storage and retrieval as claimed in any one of claims 27 to 29, wherein said variety measure is selectable from a variety measure set comprising: publisher/volume; price; image format; and licencing conditions.

31. A method of image storage and retrieval as claimed in any one of claims 17 to wherein said location forms part of a computer system.

32. A method of image storage and retrieval as claimed in claim 31, said system o.. 15 being implemented on a distributed computer network. o o0 S 33. A computer program product including a computer readable medium incorporating a computer program for storing and retrieving images, said computer program product comprising: o 20 means for storing a plurality of images, each image being stored at a respective location and having at least one associated keyword, each of said keywords having at least one associated meaning reference, each meaning reference being one of a plurality of meaning references obtained from a library of meaning references; means for arranging a relationship table to associate said meaning references to corresponding ones of said images; and means for interpreting a user entered query and relating said query to at least one of said meaning references, thereby identifying for each said related meaning reference, a predetermined number of said images.

34. A computer program product as claimed in claim 33 wherein said relationship table is arranged for each meaning reference to order the corresponding said associated images according to a matching likelihood between said meaning reference and said at least one keyword and identifying said predetermined number of said images having highest said matching likelihood. S0303AU.doc 23 A computer program product as claimed in claim 34, wherein said matching likelihood is a probability measure between 0 and 1. s 36. A computer program product as claimed in claim 34, wherein said matching likelihood is a correlation measure between -1 and 1.

37. A computer program product as claimed in claim 35 or 36, said product further comprising means for adjusting said matching probabilities of all the meaning references 1o associated with a selected image.

38. A computer program product as claimed in any one of claims 33 to 37, with said keywords and said meaning references are language independent. o

39. A computer program product as claimed in claim 38, wherein said query language is different to said keyword language of said identified image.

40. A computer program product including a computer readable medium incorporating a computer program for storing and retrieving images, said computer program product comprising: means for storing a plurality of images, each stored at a respective location and having at least one associated keyword, each of said keywords having at least one associated meaning reference, each meaning reference being one of a plurality of meaning o.references obtained from a library of meaning references; means for arranging a relationship table to associate said meaning references to corresponding ones of said images; and means for interpreting a user entered query and associating said query to at least one of said meaning references to thereby identify for each said associated meaning reference a predetermined number of said images, and upon there not being said predetermined number of said images available from said at least one meaning references associated to said user entered query, said interpreter is configured to identify more of said images using further meaning references, said further meaning references being related to said at least one meaning references associated to said user entered query. 50JO3SAU.doc 24-

41. A computer program product as claimed in claim 40, wherein said meaning references relate to said at least one meaning references by functions comprising: specialisations; generalisations; coordinate sisters; part of; and composed of, as herein defined. 1o 42. A computer program product including a computer readable medium incorporating a computer program for storing and retrieving images, said computer program product comprising: means for storing a plurality of images, each stored at a respective location and having at least one associated keyword, each of said keywords having at least one associated meaning reference, each meaning reference being one of a plurality of meaning references obtained from a library of meaning references; :means for arranging a relationship table to associate said meaning references to corresponding ones of said images; and means for interpreting a user entered query and relating said query to at least one of said meaning references, to thereby identify for each said related meaning reference, a number of said images, said number for each said related meaning reference being proportional to a matching probability between said meaning reference relating to said user entered query and said user entered query.

43. A computer program product as claimed in claim 42, further comprising means for identifying for each said related meaning reference images that satisfy a variety measure.

44. A computer program product including a computer readable medium incorporating a computer program for storing and retrieving images, said computer program product comprising: means for storing a plurality of images, each stored at a respective location and having an associated variety measure and at least one associated keyword, each of said 50303AUdoc 25 keywords having at least one associated meaning reference, each meaning reference being one of a plurality of meaning references obtained from a library of meaning references; means for arranging a relationship table to associate said meaning references to corresponding ones of said images, said table, for each meaning reference being arranged to order the corresponding said associated images according to a score in a manner whereby said variety measure are interleaved; and means for interpreting a user entered query and relating said query to at least one of said meaning references to thereby identify for each said related meaning reference, a predetermined number of said images having highest said score. I0 A computer program product as claimed in claim 33 further comprising: means for ordering the corresponding said associated images according to a matching probability; and means for identifying for each said related meaning reference a predetermined eooe is number of said images having highest said matching probability and satisfying a variety measure. ee

46. A computer program product as claimed in any one of claims 43 to 45, wherein said variety measure is selectable from a variety measure set comprising: 20 publisher/volume; price; image format; and licencing conditions.

47. A computer program product as claimed in any one of claims 33 to 46 wherein said location forms part of a computer system.

48. A computer program product as claimed in claim 47, said system being implemented on a distributed computer network.

49. A database comprising: a plurality of meaning references obtained from a library of meaning references; and 50O03SAUAd 26 image pointers associated with at least one of said meaning references for pointing to respective locations of images, wherein each image has at least one associated keyword and each of said keywords has at least one associated meaning reference.

50. A database as claimed in claim 49 wherein said image pointers associated with each meaning reference are ordered according to a matching likelihood between said meaning reference and said associated keyword.

51. A database as claimed in claim 50, wherein said matching likelihood is a io probability measure between 0 and 1.

52. A database as claimed in claim 50, wherein said matching likelihood is a correlation measure between -1 and 1. :*oooo Is 53. A database as claimed in any one of claims 49 to 52, wherein said keywords and said meaning references are language independent.

54. A database as claimed in claim 49 wherein each image has an associated variety measure and said image pointers associated with each meaning reference are ordered S 20 according to a score in a manner whereby said variety measures are interleaved.

55. A database as claimed in claim 54, wherein said variety measure is selectable from a variety measure set comprising: publisher/volume; price; image format; and licencing conditions.

56. A database as claimed in any one of claims 49 to 55 wherein said location forms part of a computer system.

57. A database as claimed in claim 56, said system being implemented on a distributed computer network. 50303AUdoc 27

58. A search engine for retrieving at least one image from a plurality of images, each said image having at least one associated keyword, each of said keywords having at least one associated meaning reference, each meaning reference being one of a plurality of meaning references obtained from a library of meaning references, and each of said meaning references being associated with corresponding ones of said images, said search engine comprising: means for interpreting a user entered query; and means for relating said user entered query to at least one of said meaning references, thereby identifying for each said related meaning reference at least one image io for retrieval.

59. A search engine as claimed in claim 58 wherein each of said meaning references are associated with corresponding ones of said images according to a matching likelihood between said meaning reference and said at least one keyword, and said image retrieval ooeo system identifies said images having highest said matching likelihood. A search engine as claimed in claim 59, wherein said matching likelihood is a probability measure between 0 and 1.

61. A search engine as claimed in claim 59, wherein said matching likelihood is a correlation measure between -1 and 1.

62. A search engine as claimed in any one of claims 58 to 61, wherein said keywords and said meaning references are language independent.

63. A search engine as claimed in claim 62, wherein said query language is different to said keyword language of said identified image.

64. A search engine for retrieving a predetermined number of images from a plurality of images, each said image having at least one associated keyword, each of said keywords having at least one associated meaning reference, each meaning reference being one of a plurality of meaning references obtained from a library of meaning references, and each of said meaning references being associated with corresponding ones of said images, said search engine comprising: 503035AUdoc -28- interpreting means for interpreting a user entered query; and relating means for relating said user entered query to at least one of said meaning references to thereby identify for each said associated meaning reference a predetermined number of said images, and upon there not being said predetermined number of said images available from said at least one meaning references associated to said user entered query, said relating means is configured to identify more of said images using further meaning references, said further meaning references being related to said at least one meaning references associated to said user entered query.

65. A search engine as claimed in claim 64, wherein said meaning references relate to said at least one meaning references by functions comprising: specialisations; generalisations; coordinate sisters; 6s15 part of; and .composed of, as herein defined.

66. A search engine for retrieving at least one image from a plurality of images, each said image having at least one associated keyword, each of said keywords having at least one associated meaning reference, each meaning reference being 6ne of a plurality of meaning references obtained from a library of meaning references, and each of said meaning references being associated with corresponding ones of said images, said search *engine comprising: interpreting means for interpreting a user entered query; and relating means for relating said user entered query to at least one of said meaning references, thereby identifying for each said related meaning reference, a number of said images, said number for each said related meaning reference being proportional to a matching probability between said meaning reference relating to said user entered query and said user entered query.

67. A search engine as claimed in claim 66, wherein said search engine further identifies for each said related meaning reference images that satisfy a variety measure. 503035AU.doc -29-

68. A search engine for retrieving at least one image from a plurality of images, each said image having an associated variety measure and at least one associated keyword, each of said keywords having at least one associated meaning reference, each meaning reference being one of a plurality of meaning references obtained from a library of meaning references, and each of said meaning references being associated with corresponding ones of said images according to a score in a manner whereby said variety measure are interleaved, said search engine comprising: means for interpreting a user entered query; and means for relating said user entered query to at least one of said meaning 1o references to thereby identify for each said related meaning reference, a predetermined number of said images having highest said score.

69. A search engine as claimed in claim 68, wherein said variety measure is selectable from a variety measure set comprising: 1 5 publisher/volume; ~price; image fonrmat; and licencing conditions.

70. An image storage and retrieving system substantially as described herein in relation to any one of the embodiments with reference to the accompanying drawings.

71. A method of image storage and retrieval substantially as described herein in relation to any one of the embodiments with reference to the accompanying drawings.

72. A computer program product including a computer readable medium substantially as described herein in relation to any one of the embodiments with reference to the accompanying drawings.

73. A database substantially as described herein with reference to Fig. 1 of the accompanying drawings. 503035AU.doc 30

74. A search engine substantially as described herein in relation to any one of thle embodiments with reference to the accompanying drawings. DATED this Sixteenth Day of June, 2000 Canon Kabushiki Kaisha Patent Attorneys for the Applicant SPRUSON FERGUSON 60*0 50303