Image Search Explained – 2 More Methods

In an earlier article titled "Image Search Explained – Method 1", we introduced a method explaining how tools search for similar images. In this post we discuss two more methods, the color distribution and the content feature method.

Color distribution method

You can generate a color histogram for each image. If the color histograms of two images are very close to each other, they are deemed similar.

Every color is made up of the three primary colors, red, green and blue (RGB). As such, four histograms exist (RGB histogram + the synthetic histogram).

If we successfully retrieve 256 values for every primary color, there will be 16 million different colors in the entire color space (256x256x256). It would involve a huge amount of computation to compare the histograms of these 16 million colors. We need a simplified method. We can divide the 0 - 255 range into four zones: 0 - 63 as Zone 0, 64 - 127 as Zone 1, 128 - 191 as Zone 2, and 192 - 255 as Zone 3. Ideally, this means that there are four zones for each of the red, green and blue color, so there are 64 combinations (4x4x4).

Any color must fall into one of the 64 combinations so that we can calculate the number of pixels contained in each combination.

The above table shows the color distribution of an image. Extract the bottom row of the table to form a 64-D vector (7414, 230, 0, 0, 8...109, 0, 0, 3415, 53929). This vector serves as the feature value of this image, also referred to as the image's "fingerprint."

Therefore, searching for similar images turns into finding out the similar vector. This is achievable by using the Pearson's correlation coefficient or cosine similarity.

Content feature method

Apart from color composition, we can also compare the similarity of image content.

First, convert the original image into a smaller grayscale image, 50*50 pixels for example. Then determine a threshold value and convert the grayscale image into a black-and-white image.

If the two images are similar, their black-and-white outlines should be very close. As a result, the problem becomes how to identify a reasonable threshold value to present the outlines in the image correctly.

Apparently, the greater the contrast between the foreground and background colors, the clearer the outlines. This means we can find a value with which to minimize, or maximize, the intra-class variance of the foreground and background colors, and this value is the ideal threshold value.

In 1979, a Japanese scholar, Otsu, proved that the value minimizing the intra-class variance and that maximizing the inter-class variance refer to the same thing, namely the threshold value. He proposed a simple algorithm to evaluate this threshold value, known as the "Otsu's method". Here is how it works.

Suppose there are a total of n pixels in an image, among which n1 pixels have grayscale values smaller than the threshold value, and n2 pixels have grayscale values equal to or greater than the threshold value (n1 + n2 = n). W1 and W2 stand for the respective proportions of these two categories of pixels.

w1 = n1 / n

w2 = n2 / n

Now suppose the average value and variance of all pixels with the grayscale values smaller than the threshold value are μ1 and σ1 respectively, and those of all pixels with the grayscale values equal to or greater than the threshold value are μ2 and σ2 respectively. So we get:

Intra-class variance = w1 (σ1 squared) + w2 (σ2 squared)

Inter-class variance = w1w2 (μ1-μ2)^2

This proves that the two formulas are equivalent. The minimum value of "intra-class variance" is equal to the maximum value of "inter-class variance." However, the latter is easier to calculate.

Next, we will use the "method of exhaustion" to retrieve the threshold value from the minimum and maximum grayscale values and feed them into the formula above one by one. The specific example and Java algorithm is accessible here.

The 50x50 pixels black-and-white thumbnail serves as a 50x50 0-1 matrix. Every value in the matrix corresponds to a pixel in the original image, with 0 representing black, and 1 representing white. This matrix is a feature matrix of the image.

Comparing the feature matrices of two images can help determine whether the images are similar. This can be achieved by using the "Exclusive - OR", or XOR operations. Following is the output table for this operation.

As you can see, when the input values are same (either 0 or both 1), the output is 1, and when the input values are different, the output is 0.

Run the XOR operation for the feature matrices of different images. Imagine that the corresponding elements of the two feature matrices are the respective inputs A and B. Hence, more the "1s" in the result (indicating both matrices have 0 or 1), the more similar the images are.

时间: 2024-04-05 19:39:55

Image Search Explained – 2 More Methods的相关文章

Google Image Search Explained

Image Search Explained Here are the questions we hear most. How does it work? How does the computer know that two images are similar? The principle is easy to understand and is reliant on what Dr. Neal Krawetz calls a fast algorithm. Or more specific

Java 8 Default Methods Explained in 5 minutes

In my previous articles, we have looked at Java 8 Lambda Expressions and Streams. In this article will be looking at Defaults Methods which is another cool feature of Java 8. Default methods enable us to add new functionalities to interfaces without

Refactoring Notes-Refactoring Methods(3)

5.Introduce Explaining Variable    If you have a complicated expression,put the result of the expression, or parts of the expression , in a temporary variable with a name that explains the purpose.   Introduce Explaining Variable is particulaly valua

HTTP - Methods Request methods[edit] An HTTP 1.1 request made using telnet. The request message, responseheader section, and response body

Top Ten One-Liners from CommandLineFu Explained

I love working in the shell. Mastery of shell lets you get things done in seconds, rather than minutes or hours, if you chose to write a program instead. In this article I'd like to explain the top one-liners from the It's a user-d

转 关闭Windows8的Windows Search服务

默认情况下,Windows8附带的一些程序和功能处于打开状态,其中包括Windows Search.此功能带来了快捷方便强大的搜索功能,但可能有人不需要此功能,或者很少用到此功能,或许还有人认为其在后台建立索引耗费了大量资源并且可能会硬盘产生伤害.如果不使用Windows Search,其实可以将其关闭.当然关闭Windows Search会将其从Windows中删除,但不会减少Windows占用的硬盘空间量,Windows Search仍将存储在硬盘中,因此,您可以根据需要将它重新打开. 首先


郑昀 20100929   应用入口: 简单介绍下我们这个榜单与新浪自己的热门转发榜区别: 微博锐推榜 将无视明星推名人推,更关注草根推,更关注社会民生推,屏蔽无营养推. 微博锐推榜 将聚合以新浪微博为首的国内各大微博网站的热门转发消息.     1.新浪的接口 新浪微博的API提供了Search方法,如它的文档所示: URL: 格式: 仅支持json  GET 是否需要登录:true

围观一个People Search

郑昀@玩聚RT 20091210 1. 请打开链接: 尝试People Search. 2. 请注意上面这个页面的底端写着: This service is powered by Google AJAX Sea

利用Yahoo! Search API开发自已的搜索引擎-javascript版

javascript|yahoo|搜索引擎 美国东部时间3月1日,雅虎公司联合创始人之一的杨致远将宣布公司的搜索网络将进入Web服务.雅虎公司在网站建立了Yahoo Search Developer Network,公司计划在此纽约举行的搜索引擎战略大会(Search Engine Strategies Conference)上推出这一计划.该网络将允许开发者在雅虎搜索之上建立新的应用程序,其中包括图像.视频.新闻以及地区搜索等内容.想要使用这项服务