Luke Francl (firstname.lastname@example.org)
February 16, 2002
Eikon is an image query system. It might seem a little strange for CodeCon. It's not decentralized. It's not related to privacy, cryptography, security, etc. Instead, think of it as a prototype for what could be built on top of a decentralized system -- it performs binary relevance calculations for images, like Relatable does for sound.
Eikon searches by image similarity using wavelets. It's based on (i.e., blatantly stolen from) research by Adam Finkelstein, Charles Jacobs, and David Salesinin, in which they develop a multiresolution image querying algorithm. The best reference for learning how to use wavelets for image processing (including a chapter on image querying) is Wavelets for Computer Graphics.
The first step in the image query algorithm is to pre-process a number of images to form the database. Each image is converted to a 128x128 pixel thumbnail and converted to the YIQ color space. YIQ encodes all luminance information in the Y channel, which useful for image query. Each color channel is then decomposed using a Haar wavelet. Think of the Haar decomposition as a successive averaging process, which also saves enough detail coeffients to reconstruct the original image. When it is complete, we are left with the average color for each channel in the (0,0) position and 16,384 wavelet coeffients per channel. The largest 60 coeffients from each color channel are saved and quantized (changed to +/-1), and the others are thrown away. At this point, the original image can no longer be reconstructed.
These 180 coeffients are inserted into search arrays. There is one search array for each of the six sign/color channel combinations. Each search array has 16,384 bins which hold the resource IDs of all the images that match at that (x,y) coordinate. By using this design, it's possible to retrieve a list of all the matches for a certain pixel very quickly.
To query the database, the query image is decomposed as described above. Scores are computed using the image querying metric discussed by Finkelstein, et al. Briefly: using the average color for each channel, each image in the database is as assigned an initial score; then, for each of the top 180 coeffients in the query image, all the matching resource IDs are retrieved from the search arrays and scored. The results are then sorted. The lowest scores are the closest matches. If you want more details on the querying algorithm, please refer to the original paper.
The Query Algorithm
Pre-process query image Q (see above)
Set initial score for each target image using average color
For each color in Q
For each coeffient in Q
if coeffient > 0
list ß getMatches(color, positive, x, y)
list ß getMatches(color, negative, x, y)
for each element of list
adjust score for target image
I think assigning a score to all the images in the database as a first step is probably unnecessary. When there are a large number of images, many of them will not be relevant and won't turn up in the search arrays. Instead, find all the matches from the search arrays first, and then calculate the score for the average color for images that are already likely matches.
With 16,384 possible bins per color, selecting any image that matches the query in the 60 target bins is sure to reduce the total number of images that need to be scored. Furthermore, images that don't match in any of the target bins are unlikely to score highly anyway. The real benefit is reducing the number of target images that must be sorted to find the top matches.
Eikon is written using Java 1.4's new imageio package. I saved a lot of time by using imageio for image conversion, and it makes it easy to support many different types of images without any extra work on my part. Currently, I support JPEG, GIF, and PNG.
Since the code is written in Java, servlets are used to handle web-based queries. I used the Jakarta Tomcat servlet container. After developing many websites using scripting languages, this was an exercise in frustration. But it works.
Eikon supports pluggable databases that implement its Database interface. The Database interface provides methods for adding, removing, updating and searching for images. The current database is implemented as an object which is serialized to disk on server shutdown.
Output is in an undocumented XML format, which is transformed to HTML by the client using my favorite language, XSL!
No images are stored on my server. Only the metadata and the search arrays are stored. However, I might be violating copyright by including the search results on my page! See: http://www.newsbytes.com/news/02/174326.html
Errors are reported by HTTP error codes. It's oh-so-RESTy! Oh, wait, I was just trying to avoid defining XML for error conditions.
Eikon works, but it could clearly be much better. Here are some of its limitations:
There is no caching of downloaded images, so each time a query is performed, the image must be downloaded again. Implementing this would make the searches much faster, but would require some checking to make sure the original image is still there.
User errors are not the best :)
It's impossible to search for text related to images. A combination of Google’s image query with Eikon-style similar image search would be really cool!
Even though images are keyed to SHA-1 hash, each image can only be associated with one URL. Without being able to associate an image with multiple URLs, metadata is rather limited. Fixing this will be easy, but it needs to be done.
Most of the framework for using multiple color spaces or wavelet bases or decomposed image sizes is there, but it wouldn't work now. Only the Haar wavelet basis, YIQ color space, and 128x128 image size is implemented.
There are a few things that need to be finished before Eikon can be considered a finished system. These include a formalized data interchange format for image signatures so any client application can generate a signature and query the database. The ResourceIdQueryServlet and the SignatureQueryServlet need to be implemented so images can be looked up by resource IDs and wavelet signatures as well as by URL. Finally, to make Eikon a usable system, I need to implement robust file-based (for desktops) and PostgreSQL (for servers) databases.
There are also several areas of research I want to explore to expand the functionality of the system. I want to define a good XML-RPC interface so Eikon can be accessed programmatically. I also want to work on connecting desktop Eikon nodes using a decentralized network, experiment with the modified scoring algorithm described above, and try to implement infra-image searching.
Carlos Vitor Alencar, et al. Multiresolution Query by Image Content. http://www.visgraf.impa.br/Courses/ipcg-query-1998/image_query.html
Tony D. Derose, Eric J. Stollnitz, and David H. Salesin. Wavelets for Computer Graphics. Morgan Kaufmann, 1996.
Adam Finkelstien, Charels E. Jacobs, and David H. Salesin. Fast multiresolution image query. http://grail.cs.washington.edu/projects/query/
D.P. Huijsmans, Michael S. Lew, and Nicu Sebe. Multi-Scale Sub-Image Search. http://www.kom.e-technik.tu-darmstadt.de/acmmm99/ep/sebe/
Eugene Vishnevsky. Introduction to Color. http://www.cs.rit.edu/~ncs/color/