Method, system and controller for searching a database

• US 8,775,417 B2
• Filed: 08/10/2010
• Issued: 07/08/2014
• Est. Priority Date: 08/11/2009
• Status: Active Grant

• Current Assignee: Someones Group Intellectual Property Holdings Pty Limited
• Original Assignee: Someones Group Intellectual Property Holdings Pty Limited ACN 131 335 325
• Inventors: Gronow, Brett James, Deverell, Keith David, Pak, Jonathan David, Bates, Christopher Glendon, Wolf, David Peter
• Primary Examiner(s): Mofiz, Apu
• Assistant Examiner(s): BIBBEE, JARED M
• Application Number:
  US13/389,007
• Publication Number:
  US 20120143857A1
• Time in Patent Office: 1,428 Days
• Field of Search: 707/723, 707/724, 707/706
• US Class Current: 707/723
• CPC Class Codes: G06F 16/532 Query formulation, e.g. graphical querying
• CPC Class Codes: G06F 16/54 Browsing; Visualisation therefor
• CPC Class Codes: G06F 16/904 Browsing; Visualisation therefor for navigating the web G06F16/954; browsing optimisation for the web G06F16/957

Abstract

A database searching system, method and controller is provided for interactively searching a database of data items in a descriptor space with a user, comprising a display for viewing by the user; a position selector for manipulation and activation by the user; a reference set selector for selecting a reference set (64a-64d) of two or more data items; a reference set coordinate obtainer for obtaining descriptor coordinates for each of the reference data items; a search results identifier for identifying a search results set of data items in the database which are close to or between one or more members of the reference set in the descriptor space; and a search results display controller for displaying the search results set on the display so that closeness on the display between particular data items is generally indicative of closeness in the descriptor space.

Claims

1. A method of searching, with a user via a user interface, a database containing data items in a descriptor space, the method comprising the steps of:

selecting, via the user interface, a reference set of four reference images corresponding to four data items in the descriptor space;

obtaining descriptor coordinates for each of the four reference data items;

identifying a search results set of plural images corresponding to plural data items in the database which are close to one or more members of the reference set data items in the descriptor space; and

displaying on a display (i) the four reference set images at respective four corners of the display, with distances therebetween, and (ii) the search results set plural images on the display between the four corners of the display, such that respective two-dimensional distances on the display between each of the four displayed reference set images and each of the plural displayed search results images corresponds to their respective closeness in the descriptor space.

2. The method as claimed in claim 1, wherein the displaying step includes the step of displaying another search results image between only two of the four corners of the display.

3. The method as claimed in claim 2, further comprising the step of enabling the user to select a reference data item by the user dragging an image corresponding to the reference data item to one of the four corners of the display.

4. The method as claimed in claim 1, further comprising the step of selecting one or more of the reference data items automatically from the database.

5. The method as claimed in claim 4, further comprising the step of using a random element for automatically selecting the one or more reference data items.

6. The method as claimed in claim 1, further comprising the step of creating a display pane when displaying the search results set images and the reference set images on the display.

7. The method as claimed in claim 1, further comprising the step of dragging a search results image to a corner of the display to create a new reference data set image.

8. The method as claimed in claim 1, further comprising the step of organizing the search results set images and the reference set images on the display so that a position of each search results set image on the display reflects the position of the corresponding search results set data item in the descriptor space.

9. The method as claimed in claim 1, further comprising the steps of:

using a defined grid of corresponding locations for display of the reference data set images and the search results data set images; and

wherein the step of identifying a search set data item comprises the steps of;

computing a weight for each reference data item as a function of relative distance on the display between each of the corresponding locations for display of each of the reference data items and the each of the corresponding locations for display of each data item in the search results set of data items;

using the weight to compute a target position in the descriptor space as a weighted average of the descriptor coordinates of each reference data item; and

identifying the search set data item as closest in the database to the target position.

10. The method as claimed in claim 9, wherein the function for computing the weight for each reference data item is the same for each reference data item and is the inverse square of the relative distance.

11. The method as claimed in claim 1, wherein the reference data items and the search results set of data items comprise digital media.

12. The method as claimed in claim 11, wherein the digital media comprise images.

13. The method as claimed in claim 11, wherein the digital media comprise audio media.

14. The method as claimed in claim 1, further comprising the step of enabling the user to select from outside the database one or more of the reference data items.

15. The method as claimed in claim 1, further comprising the steps of:

receiving a restriction criterion from the user; and

restricting the search results set to data items that satisfy or are close to the restriction criterion.

19. A computer readable medium comprising non-transitory program code which, when executed by at least one processor performs the functions set forth in claim 1.

20. The method according to claim 1, wherein the descriptor space comprises one or more tables storing, for each of the search results set plural images, at least one color histogram.

21. The method according to claim 20, wherein the one or more descriptor tables store, for each of the plural images, at least one of SIFT edge detection, SURF edge detection, and Canny edge detection.

22. The method according to claim 21, wherein the one or more descriptor tables store, for each of the plural images, at least one of Tamura texture features and Gabor texture features.

23. The method according to claim 1, wherein the descriptor space comprises one or more tables storing, for each of the search results set plural images, at least one reduced set of descriptors derived by single value decomposition of multiple values in an uncompressed descriptor set.

16. A database searching system for interactively searching a database of data items in a descriptor space with a user, the database searching system comprising:

a display for viewing by the user;

a position selector for manipulation and activation by the user; and

at least one processor configured to perform the functions of;

a reference set selector for selecting a reference set of four reference images corresponding to four data items in the descriptor space;

a reference set coordinate obtainer for obtaining descriptor coordinates for each of the four reference data items;

a search results identifier for identifying a search results set of plural images corresponding to plural data items in the database which are close to one or more members of the reference set data items in the descriptor space; and

a search results display controller for displaying on a display (i) the four reference set images at respective four corners of the display, with distances therebetween, and (ii) the search results set plural images on the display, such that respective two-dimensional distances on the display between each of the four displayed reference set images and each of the plural displayed search results images corresponds to their respective closeness in the descriptor space.

18. A image searching system as claimed in claim 16, further comprising a processor executing code stored in memory wherein at least one of the reference set selector, reference set display controller, reference set coordinate obtainer, search results identifier and search results display controller is implemented at least in part, by said processor executing said code stored in a memory.

17. A database searching controller for interactively searching a database of data items in a descriptor space with a user viewing a display and having a position selector for manipulation and activation, the database searching controller comprising at least one processor configured to perform the functions of:

a reference set selector for selecting a reference set of four reference images corresponding to four data items in the descriptor space;

a reference set coordinate obtainer for obtaining descriptor coordinates in a descriptor space for each of the reference data items;

a search results identifier for identifying a search results set of plural images corresponding to data items in the database which are close to or between one or more members of the reference set data items in the descriptor space; and

a search results display controller for displaying on the display (i) four reference set images at respective four corners of the display with distances therebetween, and (ii) the search results set of plural images on the display between the four corners of the display, such that respective two-dimensional distances on the display between each of the four displayed reference set images and each of the plural displayed search results images corresponds to their respective closeness in the descriptor space.

24. A method of searching, with a user via a user interface, a database containing data items in a descriptor space, the method comprising the steps of:

selecting a reference set of two or more reference data items;

obtaining descriptor coordinates for each of the reference data items;

identifying a search results set of plural data items in the database which are close to one or more members of the reference set in the descriptor space; and

displaying on a display images corresponding to (i) the two or more reference data items with distance therebetween, and (ii) the search results set of data items on the display between the two or more reference data items, such that closeness on the display between each displayed reference data item and each displayed search results data item corresponds to their respective closeness in the descriptor space,

wherein the step of identifying the search results set includes the steps of;

providing a grid for the display;

for each display position in the grid, compute distances to each reference data item location;

for said each display position in the grid, compute a weight from each computed distance by taking an inverse square;

normalize the computed weights to sum to unity;

compute a target position in the descriptor space as the weighted average of descriptor coordinates for each reference set;

search the database for a data item having the most similar descriptor coordinates to the target position;

display the data item on the display as a member of the search results set; and

repeat the search and display steps until the grid has been populated with the search results set.