This is way back in 2006 when this idea first came into my mind. Google was then the most popular search engine over the internet (it is even today). Google was very effective for text-based search. It had its own algorithm to suggest you the search items when you type few words - it had a strong algorithm to bring the search result in very useful order of relevance. Everyone was amazed by its search power.
However, I always felt the need of another dimension. Google is good about text search. But how do I search an image ? For example, say I have one pic of a famous actress, but it is of low resolution. How do I search the same pic or similar pics of higher resolution ? Moreover, lets say I don't know the name of the actress, I only have the pic. How do I know whose pic is this ?
I always used to think over it... and in 2006 first an Idea came into my mind - well, how to search the internet "by image", not just "by text" ? I thought of few basic algorithms... to do a search by pixel-based pattern. I did not put any serious thought around this, but let me discuss how I initially designed it.
How
When we intend to do a search by Image, we must keep in mind that the same image might be available over internet in various sizes. So we must compare the relative value of each pixel instead of a direct pixel by pixel comparison. This can be achieved by making a Color Map of the principle diagonal of the image and using that instead of the whole image. It is explained in details in the following sections:
Let us take the following pic of Monalisa. Our target is to look for images similar to this pic over the internet. We have drawn the diagonal on this pic from top-left corner to the bottom-right corner. This is our principle diagonal. Now we will take several points on this diagonal at equal distances. In this example I have taken 7 points. When this is done by the computer, we can actually take 100 points to make a finer calculation.
For each point on the diagonal, we take the color value of the corresponding pixel. It can be any number between 0 to 255 where 0 is for complete black and 255 is for intense white. Once we get all these values, we will draw a curve as shown in the below image. We will call it the Color Map of the diagonal. It is to be noted that any image same or similar to this pic will have very similar Color Map. And a different image will have a different Color Map. This is the principle of our "search by image" algorithm.
Next, we need to compare this Color Map with the stored maps of millions of pics. For those who are new to search engine technologies, every search engine periodically crawls the internet for files and data and creates a master index document. This is not achieved in a day, it is a time-taking and continuous process which keeps running in the backend. When we search the internet, the search engine actually looks for matches within its stored index document - it does not actually goes out to look for the data in the internet. This is a reason why you do not find your website in the search result immediately after you publish it. There is a time lag associated with it. Until the crawler of the search engine finds your website and includes it into the master index document, it won't appear in the search result.
So in our case, the crawler has to be a different one that keeps tracking all images over the internet and, most importantly, stores their Color Maps in the index document. When we want to search for the images similar to the Monalisa pic, our search engine has to just compare its Color Map with the stored maps. There are pretty simple and effective techniques for comparing two curves with minor deviations. I will not cover the same in this article but it is an interesting topic too which you can explore on your own.
Limitations
Yes, the above algorithm is just a basic idea. It has many flaws and it needs a lot of improvements. For example, if the image is flipped vertically or horizontally, the associated Color Map will change drastically. It would not only fail to search the images which are actually similar but upside down, it will bring some completely irrelevant results too. To protect this, we need to consider both the diagonals - major and minor - and either compare both or take a blend of them.
Another scenario could be, if a pic is similar but is in monochrome or some color adjustments are done on it - our basic search algorithm may fail to detect it. We need to make adjustments into our logic for the same. In fact, this is only a beginning. We must go through a lot of iterations to bring the best algorithm in place.
Anyway, this is a history today. Before I could start any real work on this, in 2011 Google finally launched its most powerful "Search by Image" technology. And I must say, it has all the basic functionality that I thought of. Today I use it very often and I found it one of the cool tools over internet. Hats off to Google :)
Future Thoughts
I am now thinking in a similar line - How to do a "search by video" ? Let's say I have a low resolution video. Or I have a 2-minutes clip of a stage show. How do I find if there is a better resolution clip or a long duration clip of the same video in the internet ? Also is it possible to find some video similar to the one I have ?
Let's say I uploaded a small portion of a stage show or a video song and I searched internet for that. The search result will then bring more clips of the same stage show or it will display the movie name and the download link of the movie from where the song is taken. That will be really cool.
Currently I have done nothing on this apart from just having a dream concept. I am sure Google will also implement this feature in next few years. And if it does not, I will try. Let's see what is kept in our future :)
For each point on the diagonal, we take the color value of the corresponding pixel. It can be any number between 0 to 255 where 0 is for complete black and 255 is for intense white. Once we get all these values, we will draw a curve as shown in the below image. We will call it the Color Map of the diagonal. It is to be noted that any image same or similar to this pic will have very similar Color Map. And a different image will have a different Color Map. This is the principle of our "search by image" algorithm.
Next, we need to compare this Color Map with the stored maps of millions of pics. For those who are new to search engine technologies, every search engine periodically crawls the internet for files and data and creates a master index document. This is not achieved in a day, it is a time-taking and continuous process which keeps running in the backend. When we search the internet, the search engine actually looks for matches within its stored index document - it does not actually goes out to look for the data in the internet. This is a reason why you do not find your website in the search result immediately after you publish it. There is a time lag associated with it. Until the crawler of the search engine finds your website and includes it into the master index document, it won't appear in the search result.
So in our case, the crawler has to be a different one that keeps tracking all images over the internet and, most importantly, stores their Color Maps in the index document. When we want to search for the images similar to the Monalisa pic, our search engine has to just compare its Color Map with the stored maps. There are pretty simple and effective techniques for comparing two curves with minor deviations. I will not cover the same in this article but it is an interesting topic too which you can explore on your own.
Limitations
Yes, the above algorithm is just a basic idea. It has many flaws and it needs a lot of improvements. For example, if the image is flipped vertically or horizontally, the associated Color Map will change drastically. It would not only fail to search the images which are actually similar but upside down, it will bring some completely irrelevant results too. To protect this, we need to consider both the diagonals - major and minor - and either compare both or take a blend of them.
Another scenario could be, if a pic is similar but is in monochrome or some color adjustments are done on it - our basic search algorithm may fail to detect it. We need to make adjustments into our logic for the same. In fact, this is only a beginning. We must go through a lot of iterations to bring the best algorithm in place.
Anyway, this is a history today. Before I could start any real work on this, in 2011 Google finally launched its most powerful "Search by Image" technology. And I must say, it has all the basic functionality that I thought of. Today I use it very often and I found it one of the cool tools over internet. Hats off to Google :)
Future Thoughts
I am now thinking in a similar line - How to do a "search by video" ? Let's say I have a low resolution video. Or I have a 2-minutes clip of a stage show. How do I find if there is a better resolution clip or a long duration clip of the same video in the internet ? Also is it possible to find some video similar to the one I have ?
Let's say I uploaded a small portion of a stage show or a video song and I searched internet for that. The search result will then bring more clips of the same stage show or it will display the movie name and the download link of the movie from where the song is taken. That will be really cool.
Currently I have done nothing on this apart from just having a dream concept. I am sure Google will also implement this feature in next few years. And if it does not, I will try. Let's see what is kept in our future :)
No comments:
Post a Comment