US6415282B1
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and apparatus for query refinement
Assignee: NEC Corp
•
Filing: 1998-04-22
•
Granted: 2002-07-02
•
Expires: 2018-04-22
Abstract
Abstract A method and apparatus for providing a user interface for refining a query applied to a database of images, where a Query Result Visualization Environment allows the user to organize the search results using various techniques. For example, the search results may be clustered on the basis of text, image or URL. The members of the resulting clusters may then be utilized by the user to refine the query to be applied to the database of images.
Inventors
- 👤 Sougata Mukherjea
- 👤 Kyogi Hirata
- 👤 Yoshinori Hara
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-07 23:39
CPC Classifications
G; G06; G06F; G06F16/00; G06F16/50; G06F16/58; G06F16/583; G06F16/5838; G06F16/5854; Y; Y10; Y10S; Y10S707/00; Y10S707/912; Y10S707/913; Y10S707/914; Y10S707/99931; Y10S707/99933; Y10S707/99936
Claims Analysis
Total Claims: 42
Claim 1
Independent Claim
275 words
A method for refining a first query applied to a database of images, the method comprising the steps of: selecting one of a plurality of modes of clustering results of the first query, wherein the modes of clustering include clustering by one of text, image and Universal Resource Locator (URL); and retrieving cluster groups containing the results of the first query, the cluster groups having been clustered in accordance with the selected mode of clustering, wherein when the selected mode of clustering is clustering by text, the cluster groups have been formed in a preprocessing procedure comprising the steps of: (a) representing each of the images in the database in a vector space model, where V represents a unique set of keywords assigned to the images, where each of the images is represented by a vector of length |V|; (b) calculating a similarity value between each pair of the images, thereby forming a similarity matrix, wherein the similarity value is measured by the cosine of the angle between the vector of the respective images, the similarity value being further normalized to a value between 0 and 1; (c) storing the similarity value in the similarity matrix only when the similarity value is greater than a first threshold value; (d) clustering the images based on the normalized similarity value; and (e) determining a topic for each of the cluster groups; and the method for refining a first query filer comprising displaying the cluster groups, each of the cluster groups being visually represented by a graphical element; and refining the results of the first query using members of the cluster groups as elements of a refined query.
Claim 2
Independent Claim
275 words
A method for refining a first query applied to a database of images, the method comprising the steps of: selecting one of a plurality of modes of clustering results of the first query, wherein the modes of clustering include clustering by one of text, image and Universal Resource Locator (URL); and retrieving cluster groups containing the results of the first query, the cluster groups having been clustered in accordance with the selected mode of clustering, wherein when the selected mode of clustering is clustering by text, the cluster groups have been formed in a preprocessing procedure comprising the steps of: (a) representing each of the images in the database in a vector space model, where V represents a unique set of keywords assigned to the images, where each of the images is represented by a vector of length |V|; (b) calculating a similarity value between each pair of the images, thereby forming a similarity matrix, wherein the similarity value is measured by the cosine of the angle between the vector of the respective images, the similarity value being further normalized to a value between 0 and 1; (c) storing the similarity value in the similarity matrix only when the similarity value is greater than a first threshold value; (d) clustering the images based on the normalized similarity value; and (e) determining a topic for each of the cluster groups; and the method for refining a first query filer comprising displaying the cluster groups, each of the cluster groups being visually represented by a graphical element; and refining the results of the first query using members of the cluster groups as elements of a refined query.
Claim 3
Dependent Claim
16 words
The method according to claim 1 , wherein the database of images is a multimedia database.
Claim 4
Dependent Claim
18 words
The method according to claim 1 , wherein te database of images is on the World Wide Web.
Claim 5
Dependent Claim
15 words
The method according to claim 1 , wherein clustering by image includes clustering by color.
Claim 6
Dependent Claim
16 words
The method according to claim 1 , wherein clustering by image includes clustering by primary shape.
Claim 7
Dependent Claim
57 words
The method according to claim 1 , wherein the length |V| is calculated so that the absence of one of the keywords is indicated by a 0 and the presence of one of the keywords is indicated by a positive number representing the importance of the keyword, the frequency of assignment of the keyword in the image.
Claim 8
Dependent Claim
135 words
The method according to claim 1 , wherein the preprocessing step further comprises the steps of: (a) determining linking nodes, where each of the images is represented by a node, wherein nodes are linking nodes when the normalized similarity value between the pair of images is greater than a second threshold value; (b) determining a set of connected components, the set of connected components being a set of the nodes where each of the nodes is linked to at least one other member of the set of nodes, the set of nodes in a connected component forming a cluster; and (c) repeating steps (a) and (b) by increasing the second threshold value when the cluster contains a large number of the images and the second threshold value is less than a maximum value of 1.0.
Claim 9
Dependent Claim
35 words
The method according to claim 1 , wherein the step of determining a topic for each of the cluster groups comprises determining the keywords which are assigned to most of the images of the cluster.
Claim 10
Dependent Claim
53 words
The method according to claim 1 , wherein the step of refining further comprises the steps of: (a) selecting the graphical element representing a desired cluster group; (b) displaying the members of the selected cluster group; and (c) selecting one of the displayed members as one of the elements of the refined query.
Claim 11
Dependent Claim
88 words
The method according to claim 1 , wherein, when the selected mode of clustering is clustering by image, the cluster groups have been formed in a preprocessing procedure comprising the steps of: (a) detecting edge images of each of the images in the database; (b) comparing the edge images of each of the images with primary shape cluster templates; and (c) grouping the images into cluster groups by primary shape based upon similarity between the edge images of each of the images and the primary shape cluster templates.
Claim 12
Dependent Claim
39 words
The method according to claim 10 , wherein the step of comparing compensates for unevenness in the edge images, small size differences between the edge images and the primary object cluster templates and shifting of objects in the images.
Claim 13
Dependent Claim
27 words
The method according to claim 10 , wherein the step of grouping further comprises grouping into cluster groups by different sizes of the primary shape cluster templates.
Claim 14
Dependent Claim
37 words
The method according to claim 12 , wherein the step of refining further comprises the step of selecting the graphical element representing a desired cluster group indicating a desired size of a desired primary shape cluster template.
Claim 15
Dependent Claim
46 words
The method according to claim 1 , wherein when the selected mode of clustering is clustering by URL, the cluster groups have been formed by grouping the results by web sites from which the results come, wherein each web site represents one of the cluster groups.
Claim 16
Dependent Claim
27 words
The method according to claim 14 , wherein a directory structure is shown for the web site represented by the graphical element representing a selected cluster group.
Claim 17
Dependent Claim
53 words
The method according to claim 14 , wherein the step of refining further comprises the steps of: (a) selecting the graphical element representing a desired cluster group; (b) displaying the members of the selected cluster group; and (c) selecting one of the displayed members as one of the elements of the refined query.
Claim 18
Dependent Claim
32 words
The method according to claim 1 , wherein the graphical element is a first shape when it is not selected and the graphical element is a second shape when it is selected.
Claim 19
Dependent Claim
31 words
The method according to claim 1 , wherein a size of the graphical clement is proportional to the number of the members in the cluster group represented by the graphical element.
Claim 20
Dependent Claim
78 words
The method according to claim 1 , wherein the graphical element is comprised of a first color component and a second color component, where the first color component is proportional to a maximum number of desired keywords in the members of the cluster group represented by the graphical element and where the second color component is proportional to a maximum image similarity between the first query and the members of the cluster group represented by the graphical element.
Claim 21
Independent Claim
305 words
A system for refining a first query applied to a database of images, the system comprising: a first computer, including a display; and a second computer executing an application program for providing a user of the computer with an option of selecting one of a plurality of modes of clustering results of the first query, wherein the modes of clustering include clustering by one of text, image and Universal Resource Locator (URL); wherein the first query is executed and the cluster groups containing the results of the first query are retrieved, the cluster groups having been clustered in accordance with the selected mode of clustering; wherein, the cluster groups are displayed on the display, each of the cluster groups being visually represented by a graphical element; wherein the user may refine the results of the first query using members of the cluster groups as elements of a refined query; and wherein, when the selected mode of clustering is clustering by text, in the application program, the cluster groups have been formed in a preprocessing procedure by: (a) representing each of the images in the database in a vector space model, where V represents a unique set of keywords assigned to the images, where each of the images is represented by a vector of length |V|; (b) calculating a similarity value between each pair of the images, thereby forming a similarity matrix, wherein the similarity value is measured by the cosine of the angle between the vector of the respective images, the similarity value being further normalized to a value between 0 and 1; (c) storing the similarity value in the similarity matrix only when the similarity value is greater than a first threshold value, (d) clustering the images based on the normalized similarity value; and (e) determining a topic for each of the cluster groups.
Claim 22
Independent Claim
305 words
A system for refining a first query applied to a database of images, the system comprising: a first computer, including a display; and a second computer executing an application program for providing a user of the computer with an option of selecting one of a plurality of modes of clustering results of the first query, wherein the modes of clustering include clustering by one of text, image and Universal Resource Locator (URL); wherein the first query is executed and the cluster groups containing the results of the first query are retrieved, the cluster groups having been clustered in accordance with the selected mode of clustering; wherein, the cluster groups are displayed on the display, each of the cluster groups being visually represented by a graphical element; wherein the user may refine the results of the first query using members of the cluster groups as elements of a refined query; and wherein, when the selected mode of clustering is clustering by text, in the application program, the cluster groups have been formed in a preprocessing procedure by: (a) representing each of the images in the database in a vector space model, where V represents a unique set of keywords assigned to the images, where each of the images is represented by a vector of length |V|; (b) calculating a similarity value between each pair of the images, thereby forming a similarity matrix, wherein the similarity value is measured by the cosine of the angle between the vector of the respective images, the similarity value being further normalized to a value between 0 and 1; (c) storing the similarity value in the similarity matrix only when the similarity value is greater than a first threshold value, (d) clustering the images based on the normalized similarity value; and (e) determining a topic for each of the cluster groups.
Claim 23
Dependent Claim
19 words
The system according to claim 20 , wherein the first computer and the second computer are the same computer.
Claim 24
Dependent Claim
28 words
The system according to claim 20 , wherein the first computer is a client computer and the second computer is a host computer connected to the client computer.
Claim 25
Dependent Claim
16 words
The system according to claim 20 , wherein the database of images is a multimedia database.
Claim 26
Dependent Claim
18 words
The system according to claim 20 , wherein the database of images is on the World Wide Web.
Claim 27
Dependent Claim
15 words
The system according to claim 20 , wherein clustering by image includes clustering by color.
Claim 28
Dependent Claim
16 words
The system according to claim 20 , wherein clustering by image includes clustering by primary shape.
Claim 29
Dependent Claim
57 words
The system according to claim 20 , wherein the length |V| is calculated so that the absence of one of the keywords is indicated by a 0 and the presence of one of the keywords is indicated by a positive number representing the importance of the keyword, the frequency of assignment of the keyword in the image.
Claim 30
Dependent Claim
135 words
The system according to claim 20 , wherein in the application program, the preprocessing procedure further comprises: (a) determining linking nodes, where each of the images is represented by a node, wherein nodes are linking nodes when the normalized similarity value between the pair of images is greater than a second threshold value; (b) determining a set of connected components, the set of connected components being a set of the nodes where each of the nodes is linked to at least one other member of the set of nodes, the set of nodes in a connected component forming a cluster; and (c) repeating (a) and (b) by increasing the second threshold value when the cluster contains a large number of the images and the second threshold value is less than a maximum value of 1.0.
Claim 31
Dependent Claim
32 words
The system according to claim 20 , wherein a topic for each of the cluster groups is created by determining keywords which are assigned to most of the images of the cluster.
Claim 32
Dependent Claim
56 words
The system according to claim 20 , wherein in the application program, the results are refined by: (a) selecting the graphical element representing a desired cluster group; (b) displaying the members of the selected cluster group on the display; and (c) selecting one of the displayed members as one of the elements of the refined query.
Claim 33
Dependent Claim
88 words
The system according to claim 20 , wherein, when the selected mode of clustering is clustering by image, in the application program the cluster groups have been formed in preprocessing procedure by: (a) detecting edge images of each of the images in the database; (b) comparing the edge images of each of the images with primary shape cluster templates; and (c) grouping the images into cluster groups by primary shape based upon similarity between the edge images of each of the images and the primary shape cluster templates.
Claim 34
Dependent Claim
37 words
The system according to claim 31 , wherein the comparing compensates for unevenness in the edge images, small size differences between the edge images and the primary object cluster templates and shifting of objects in the images.
Claim 35
Dependent Claim
23 words
The system according to claim 31 , wherein the grouping groups into cluster groups by different sizes of the primary shape cluster templates.
Claim 36
Dependent Claim
33 words
The system according to claim 33 , wherein results are refined by further selecting the graphical element representing a desired cluster group indicating a desired size of a desired primary shape cluster template.
Claim 37
Dependent Claim
50 words
The system according to claim 20 , wherein when the selected mode of clustering is clustering by URL, in the application program, the cluster groups have been formed by grouping the results by web sites from which the results come, wherein each web site represents one of the cluster groups.
Claim 38
Dependent Claim
30 words
The system according to claim 35 , wherein a directory structure is displayed on the display for the web site represented by the graphical element representing a selected cluster group.
Claim 39
Dependent Claim
55 words
The system according to claim 35 , in the application program, the results are refined by: (a) selecting the graphical element representing a desired cluster group; (b) displaying the members of the selected cluster group on the display; and (c) selecting one of the displayed members as one of the elements of the refined query.
Claim 40
Dependent Claim
32 words
The system according to claim 20 , wherein the graphical element is a first shape when it is not selected and the graphical element is a second shape when it is selected.
Claim 41
Dependent Claim
31 words
The system according to claim 20 , wherein a size of the graphical element is proportional to the number of the members in the cluster group represented by the graphical element.
Claim 42
Dependent Claim
78 words
The system according to claim 20 , wherein the graphical element is comprised of a first color component and a second color component where the first color component is proportional to a maximum number of desired keywords in the members of the cluster group represented by the graphical element and where the second color component is proportional to a maximum image similarity between the first query and the members of the cluster group represented by the graphical clement.
References Cited (Backward Citations)
US5751286A
Cited
JPH07271801A
Cited
JPH08153121A
Cited
US5821945A
Cited
JPH08221439A
Cited
JPH08235160A
Cited
JPH08329106A
Cited
JPH09179707A
Cited
US5852823A
Cited
US5920856A
Cited
US6088483A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2005-07-01 | 2005-12-31 | 2006-07-02 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2009-07-01 | 2009-12-31 | 2010-07-02 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2013-07-01 | 2013-12-31 | 2014-07-02 | $7700.00 | Window Closed / Lapsed |