Dynamic maps for exploring and browsing of images

Abstract

A method of mapping a collection of images, or other higher dimensional items including text documents, and three-and-higher dimensional objects, onto a navigable grid for browsing via a user interface comprises obtaining for each of the images a list of nearest neighbor images and similarity scores for each nearest neighbor; placing a first image on a cell within a grid; from a respective list of nearest neighbors of said first image, finding images that maximize a compatibility score with images already placed on the grid and placing resulting images on neighboring cells; and continuing to place further images on the grid until all cells visible to a user are filled with images. As the user pans or zooms the grid, more cells move into the visible area of the screen and are filled with images in the same way.

What is claimed is: 
     
         1 . A method of mapping a collection of items of high dimensional data, said high dimensional data being any of images or text documents or three dimensional objects or higher than three dimensional objects, onto a navigable grid for browsing, said browsing being via a user interface: the method comprising:
 obtaining for respective items of said collection a list of nearest neighbor items and scores indicating degrees of similarity between said respective item and each of said listed nearest neighbors;   placing a first of said items on a cell within a grid;   from a respective list of nearest neighbor items of said first item, finding items that maximize a compatibility score with items already placed on said grid, said maximizing using respective similarity scores; and placing respectively found items on neighboring cells on said grid; and   continuing to place further items on said grid, by said maximizing of respective compatibility scores, until all cells visible to a user are filled with items.   
     
     
         2 . The method of  claim 1 , further comprising only generating a part of said grid currently visible to a user on a screen. 
     
     
         3 . The method of  claim 2 , comprising allowing a user to move said grid to expose further cells, and filling said newly exposed cells with further items maximizing said compatibility score, said filling being carried out dynamically as said user exposes respective cells. 
     
     
         4 . The method of  claim 2 , wherein said moving comprises panning, to expose cells adjacent to current cells. 
     
     
         5 . The method of  claim 2 , wherein said moving comprises zooming in, to expose cells in between current cells, or zooming out, to hide some of said current cells. 
     
     
         6 . The method of  claim 1 , wherein said compatibility score comprises a weighted sum of similarity scores for each neighbor that appears in the respective list of nearest neighbor items. 
     
     
         7 . The method of  claim 6 , wherein said items comprise images and said similarity scores are computed from at least one member of the group consisting of: average color over predefined item segments, a joint color histogram, and a spatial envelope. 
     
     
         8 . The method of  claim 1 , further comprising placing additional items at predefined locations on said grid to constrain said grid, or allowing a user to place additional items at selected locations on said grid to constrain said grid. 
     
     
         9 . The method of  claim 1 , wherein said list of nearest neighbors items is limited to a predetermined number of items irrespective of a total number of items. 
     
     
         10 . The method of  claim 1 , further comprising enhancing said compatibility score for a given item by including neighbors of neighboring cells. 
     
     
         11 . The method of  claim 1 , wherein the items are images, the method further comprising:
 using average color over predefined item segments, a joint color histogram, and a spatial envelope to generate a high dimension image descriptor; and   using a locality sensitive hashing scheme (LSH) based on said high dimension image descriptor to group said images as nearest neighbors.   
     
     
         12 . The method of  claim 1 , further comprising allowing users to reposition items on said grid, said user repositioning being allowed to override said similarity scores, thereby to provide crowdsourcing based enhancement for said grid. 
     
     
         13 . A method of interactively browsing items on a screen, the items being from a collection of high dimensional items including text documents, images, and three-and-higher dimensional objects, and being dynamically mapped to a grid during said browsing, the method comprising:
 In advance of said browsing:
 obtaining for respective items of said collection a list of nearest neighbor items and scores indicating degrees of similarity between said respective item and each of said listed nearest neighbors; 
 placing a first of said items on a cell within a grid; 
   during said browsing providing a subset of cells of said grid on an interactive user screen and for each of said cells placed on said screen and not having items assigned thereto:
 from a respective list of nearest neighbor items of said first item, finding items that maximize a compatibility score with items already placed on said grid, said maximizing using respective similarity scores; and placing respectively found items on neighboring cells on said grid; and 
 continuing to place further items on said grid, by said maximizing of respective compatibility scores, until all cells visible to a user are filled with items. 
   
     
     
         14 . A user interface for browsing items according to similarity comprising:
 an arrangement of positions, each position having a first number of nearest neighbors, a subset of said positions being visible to a user on a screen, said arrangement being navigable via user interaction to reach new positions not currently visible on said screen;   an item placer for placing a seed item in one of said positions and for subsequently placing further items being located in neighboring positions of said visible subset, said further items being selected to minimize a distance metric with currently placed neighboring items, said item placer continuing to place additional items on new positions as the new positions are revealed by said user interaction, said further items also being selected to minimize said distance metric with already placed neighboring items.   
     
     
         15 . The user interface of  claim 14 , wherein said item placer is configured to be provided with items and corresponding k nearest neighbor lists for placing in said positions. 
     
     
         16 . The user interface of  claim 14 , wherein said items are images. 
     
     
         17 . The user interface of  claim 14 , further configured to allow users to reposition items on said positions, said user repositioning being allowed to override said similarity scores, thereby to provide crowdsourcing based enhancement for said images. 
     
     
         18 . The user interface of  claim 14 , further comprising a random jump input for causing said currently visible subset to jump to a new randomly chosen seed image. 
     
     
         19 . The user interface of  claim 14 , configured to carry out zooming by designating high level items for display in a low zoom and inserting items in between said high level items in accordance with said minimizing of said distance metric. 
     
     
         20 . The user interface of  claim 14 , wherein said item placer is configured to use results from a keyword search to carry out said placing of said seed item. 
     
     
         21 . The user interface of  claim 14 , wherein said item placer is configured to use results from a keyword search to filter items placed in said positions.