Following from my post last week, I’ll be talking about an example application for Stochastic Diffusion Search, otherwise known as SDS. I believe that this can be used in many different ways, but I will explain how I think it could be implemented in a search by image algorithm.
If you do not know how SDS works, I highly recommend reading my previous post. Link
If, instead, you rather watch a video of me explaining SDS, have no fear! I have made a video explaining how SDS works using an easy to digest metaphor. Link
Now into the problem at hand!
The Problem to Solve
I would like to propose a way to search a large database of images with a single image as an input. Essentially, I would like to create a version of Google’s search by image functionality.
The application I will be explaining will not be going into the intricate detail of how specifically these functions will work. This will also be simplified to extent where I am able to explain how the different functions work without there being too much confusion about what I am talking about.
Google’s Search by Image
I believe in order to understand how the problem could be used in a swarm intelligence manner is to see how the current market is achieving a similar goal.
Now, we all know how to use Google and that it dominates our lives, from the simple search on recipes for dinners to trying to find an image that will fit an article for a blog; all of this achieved with a simple type of the keyboard and click of the mouse. I even used Google to find information about how it works (quite ironic I think).
Google has for quite some time, however, had a slightly different searching method. This is Google’s search by image; drag and drop an image and it will try to find the same image or visually similar images. Now, you might ask me about how this works; well, I am glad you asked random stranger on the internet.
First of all Google requires you to either upload an image or paste in a url of an image, like the cat picture above. Once Google has this they then follow through a series of processes by creating mathematical models of the image based on different properties of the image, like shape, colour, lines, etc. This model is matched along with other images in Google’s database and does page analysis to find images from the websites it finds. This returns images from webpages it has found that either contain your image or similar images to your image.
So from what I have seen, Google doesn’t use a swarm intelligence approach to finding images within their database. They do use image processing techniques that allow them to find similar images based on their mathematical model.
If you would like to find out more about how Google allows us to search, read the Google’s blog about this or this blog from searchengineland.com that explains in more detail how Google search by image works.
When it comes to SDS, the parameters that need to be considered are the search space; the model used; the values needed for the hypothesis; the values for the micro-features, and the method of which the algorithm will produce a value that can be compared against to determine what value is better. This is better known as the ‘fitness function’.
I’ll list what the different parameters are for this problem with an explanation beneath:
- Search Space – Database of Images
- Model – Input Image
- Hypothesis – Image Index
- Micro-Features – X and Y Coordinates
- Fitness Function – Find average colour around X and Y coordinate
1. The search space would be the database of images that the program would be looking through.
2. The model the program would use to compare other images to would be the image that the user has inputted into the system.
3. The hypothesis the agents of the program would make would be the image index. The image index would be the position of the image within the database. The agents would assume that they have found the correct image and would check they have made the right choice with a partial search, using micro-features.
4. The micro-features for this problem would be the X and Y coordinates in the image. This allows the agents to compare they X and Y coordinate on the image they have selected and on the model. This will allow them to check if they have found the correct image.
5. The fitness function would check whether the pixel the agent has chosen is the same as the pixel in the same position in the model. This would, however, not be great as it would only find images that are exactly the same so by making a convolution of pixel and averaging the pixel value, it would give a fuzzier comparison. This would allow us to find visually similar images that have similar colours, in a similar arrangement.
Variations to this Problem
Now the issue with this solution is that the input image would only be fully found if the problem found the same image of the same dimensions. This would mean that you would need an exact match in order to find the image your were looking for.
To keep it a bit loose so that it didn’t matter whether the picture was of a different dimension, a new hypothesis would be selected; scale. The scale for X and Y directions would be randomly chosen as part of the hypothesis so that the when it comes to the fitness function it would take said scale into account and would be able to check if it was the same image bit just stretched.
What if the image that was made the input was taken on an angle? Well, then rotation would have to be taken into account and so the hypothesis would have to choose a random angle. This, like scale, would be calculated in the fitness function to check if the input image has been rotated in the images in the database.
Although, it is nice to add these extra features, the downside to is the program would take longer to converge on the correct answer. As there are many layers, like scale and rotation, just being guessed by the agents, the program would take quite a bit longer to find what the user was looking for.
- Random Cat Image Source – haikudeck.com
- How Google’s Image Search Works – [Matt McGee] [searchengineland.com]
- What algorithm google search by image uses – [Quora.com]
- Google Blog about Search by Image – [search.googleblog.com]