isk-daemon: Content-based image database server

Visual image similarity considers the basic shape and color information of the query when looking through the database for potential matches.

isk-daemon uses wavelet algorithms, metric and query ideas based on the paper “Fast Multiresolution Image Querying” by Charles E. Jacobs, Adam Finkelstein and David H. Salesin.

The core image similarity algorithm uses a multi-resolution wavelet decomposition approach for solving the problem of determining the top-k similar images to a target among a pre-indexed database. Among some of it’s advantages, this approach allows queries to be specified at any resolution (possibly different from that of the target); moreover, the running time and storage of our method are independent of the resolutions of the database images.

The signature information for each image computed by isk-daemon can be extracted from a wavelet-compressed version of the image directly, allowing the signature database to be created conveniently from a set of compressed (low-resolution) images.

Why using wavelets: Wavelet decompositions allow for very good image approximation with just a few coefficients. As such, this property has been exploited for lossy image compression. Typically, in these schemes, just the wavelet coefficients with the largest magnitude are used. Wavelet decompositions can be used to extract and encode edge information. When doing query-by-sketches, edges from user drawn strokes are likely to be among the key features. The coefficients of a wavelet decomposition provide information that is independent of the original image resolution. Thus, a wavelet-based scheme allows the resolutions of the query and the target to be effectively decoupled. Wavelet decompositions are fast and easy to compute, requiring linear time in the size of the image and very little code. See more scalability details.

The diagram above depicts the interaction between an existing web application and a cluster of isk-daemon instances.

All isk-daemon instances communicate to each other automatically balancing the load of adding images to its database and querying for similarity. This way, the web server(s) acting as a client to the isk-daemon cluster is isolated from the fact that there is a cluster of image similarity engines and can make calls to any instance.

Optionally, isk-daemon can make use of memcached instances to cache query requests in order to increase querying throughput.

This diagram (click for bigger version) shows how the web server (Apache etc), web programming code (PHP, ASP etc) and the content-based image database (isk-daemon) interacts.

It depicts the two most common processes (shown as the two vertical lanes):

1. Adding images to your existing image database (a process you probably already have in place) followed by getting it indexed by isk-daemon
2. Querying for similar images.

This architecture assumes that the following components (brown boxes on the diagram) are already implemented by you:

• Web server: for handling user input and running PHP or your web application logic for presenting search results and helping the user perform queries.
  
• Image meta-data engine: be it a PHP module or some logic embedded on your pages to query a relational database management system for any image meta-data needed on your application. The architecture assumes you have such a database in place in order to store image IDs associated to its location in order to present search results and know which ID to supply to the image similarity engine given user input.
• Image meta-data: a relational database with additional data for each image stored on disk. Would typically associate image IDs to its location on disk, title, dimensions, etc.
• images: stored on a hard disk drive, readable from the web server and from the “Image similarity engine”. The image similarity engine only makes use of image pixel data when adding images to its database. Which means that right after processing, these images can be deleted from disk.

The processes for indexing and querying are detailed below:

Index images into your website:

1) Site administrator submits a request to add an image. Again, this is a process that is probably already implemented as part of your content publishing system. Alternatively, images may be getting into your system from user submission forms. In this case, the server side logic for handling these submissions should be extended to also do step 2.c) below.

2) PHP class or page handles the admin user (or an end-user request from a photo submission HTML form) request and does the following:

• a) Save image metadata on RDBMS, determining this image unique id;
• b) Save image thumbnail to disk;
• c) Request image to be indexed by isk-daemon

3) An XML-RPC or SOAP call is made to isk-daemon service interface asking it to index an image. This call should supply an image ID (an integer - probably the same unique image id generated on step 2) and a file path for the image thumbnail.

4) Image thumbnail is loaded from disk. Pixel data is summarized and a very small signature is calculated

5) Visual signature is efficiently stored on main memory

6) And later persisted to disk. This has a configurable behavior: either have them saved after the Nth image is added, or saved every N minutes or have it manually saved from a service call or manual action from the isk-daemon admin interface.

7) User requests random image by clicking on a button at your Flash or HTML interface. This click translates into a remote call as follows.

8 ) XML or JSon HTTP POST is made to an image controller (some logic you have running on the HTTP server). Probably a PHP, ASP class/page or a plain servlet.

9) Your image controller makes a request to the isk-daemon service interface for random image ids for all indexed images. This request could also be made to the RDBMS holding image metadata since only random image IDs are necessary.

10) Image controller wraps image ids and thumbnail URLs into JSon or XML data which is returned to and interpreted by a Flash applet.

11) User requests images similar to one he is currently seeing in details

12) PHP code calls isk-daemon service interface asking for the most similar images by supplying an image id.

13) isk-daemon checks if this query is already cached, if not, proceeds to step 14

14) all images are scored according to their similarity to the query target image

15) PHP code receives XML-RPC results and wraps all the results image ids and thumbnail URLs into JSon or XML data to be returned to a Flash applet.

16) Flash applet shows query results.