We are now at the final step of building an image search engine — accepting a query image and performing an actual search.
Let’s take a second to review how we got here:
- Step 1: Defining Your Image Descriptor. Before we even consider building an image search engine, we need to consider how we are going to represent and quantify our image using only a list of numbers (i.e. a feature vector). We explored three aspects of an image that can easily be described: color, texture, and shape. We can use one of these aspects, or many of them.
- Step 2: Indexing Your Dataset. Now that we have selected a descriptor, we can apply the descriptor to extract features from each and every image in our dataset. The process of extracting features from an image dataset is called “indexing”. These features are then written to disk for later use. Indexing is also a task that is easily made parallel by utilizing multiple cores/processors on our machine.
- Step 3: Defining Your Similarity Metric. In Step 1, we defined a method to extract features from an image. Now, we need to define a method to compare our feature vectors. A distance function should accept two feature vectors and then return a value indicating how “similar” they are. Common choices for similarity functions include (but are certainly not limited to) the Euclidean, Manhattan, Cosine, and Chi-Squared distances.
Finally, we are now ready to perform our last step in building an image search engine: Searching and Ranking.
Before we can perform a search, we need a query.
The last time you went to Google, you typed in some keywords into the search box, right? The text you entered into the input form was your “query”.
Google then took your query, analyzed it, and compared it to their gigantic index of webpages, ranked them, and returned the most relevant webpages back to you.
Similarly, when we are building an image search engine, we need a query image.
Query images come in two flavors: an internal query image and an external query image.
As the name suggests, an internal query image already belongs in our index. We have already analyzed it, extracted features from it, and stored its feature vector.
The second type of query image is an external query image. This is the equivalent to typing our text keywords into Google. We have never seen this query image before and we can’t make any assumptions about it. We simply apply our image descriptor, extract features, rank the images in our index based on similarity to the query, and return the most relevant results.
You may remember that when I wrote the How-To Guide on Building Your First Image Search engine, I included support for both internal and external queries.
Why did I do that?
Let’s think back to our similarity metrics for a second and assume that we are using the Euclidean distance. The Euclidean distance has a nice property called the Coincidence Axiom, implying that the function returns a value of 0 (indicating perfect similarity) if and only if the two feature vectors are identical.
If I were to search for an image already in my index, then the Euclidean distance between the two feature vectors would be zero, implying perfect similarity. This image would then be placed at the top of my search results since it is the most relevant. This makes sense and is the intended behavior.
How strange it would be if I searched for an image already in my index and did not find it in the #1 result position. That would likely imply that there was a bug in my code somewhere or I’ve made some very poor choices in image descriptors and similarity metrics.
Overall, using an internal query image serves as a sanity check. It allows you to make sure that your image search engine is functioning as expected.
Once you can confirm that your image search engine is working properly, you can then accept external query images that are not already part of your index.
So what’s the process of actually performing a search? Checkout the outline below:
1. Accept a query image from the user
A user could be uploading an image from their desktop or from their mobile device. As image search engines become more prevalent, I suspect that most queries will come from devices such as iPhones and Droids. It’s simple and intuitive to snap a photo of a place, object, or something that interests you using your cellphone, and then have it automatically analyzed and relevant results returned.
2. Describe the query image
Now that you have a query image, you need to describe it using the exact same image descriptor(s) as you did in the indexing phase. For example, if I used a RGB color histogram with 32 bins per channel when I indexed the images in my dataset, I am going to use the same 32 bin per channel histogram when describing my query image. This ensures that I have a consistent representation of my images. After applying my image descriptor, I now have a feature vector for the query image.
3. Perform the Search
To perform the most basic method of searching, you need to loop over all the feature vectors in your index. Then, you use your similarity metric to compare the feature vectors in your index to the feature vectors from your query. Your similarity metric will tell you how “similar” the two feature vectors are. Finally, sort your results by similarity.
If you would like to see the “Performing the Search” step in action, head on over to my How-To Guide on Building Your First Image Search Engine post. On Step #3, I give you Python code that can be used to perform a search.
Looping over your entire index may be feasible for small datasets. But if you have a large image dataset, like Google or TinEye, this simply isn’t possible. You can’t compute the distance between your query features and the billions of feature vectors already present in your dataset.
For the readers that have experience in information retrieval (traditionally focused on building text search engines), we can also use tf-idf indexing and an inverted index to speedup the process. However, in order to use this method, we need to ensure our features can fit into the vector space model and are sufficiently sparse. Building an image search engine that utilizes this method is outside the scope of this post; however, I will certainly be revisiting it in the future when we start to build more complex search engines.
4. Display Your Results to the User
Now that we have a ranked list of relevant images we need to display them to the user. This can be done using a simple web interface if the user is on a desktop, or we can display the images using some sort of app if they are on a mobile device. This step is pretty trivial in the overall context of building an image search engine, but you should still give thought to the user interface and how the user will interact with your image search engine.
So there you have it, the four steps of building an image search engine, from front to back:
- Define your image descriptor.
- Index your dataset.
- Define your similarity metric.
- Perform a search, rank the images in your index in terms of relevancy to the user, and display the results to the user.
So what did you think of this series of posts? Was it informative? Did you learn anything? Or do you prefer posts that have more code examples, like Hobbits and Histograms?
Please leave a comment below, I would love to hear your thoughts.
And as always, be sure to sign up below to download my image search engine Resource Guide PDF. You’ll receive exclusive tips, tricks, and hacks that I don’t publish in this blog. And you’ll be the first to know about my upcoming book launch!