![\"\"](\"https:\/\/picmatch.io\/home3\/picmatch\/public_html\/wp-content\/uploads\/2014\/03\/Blog-Principle-1.png\")
<\/p>\nMARCH 27TH, 2014<\/p>\n
At A.N.Lab, we develop various applications based on the image-matching and AR (Augmented Reality) technology.<\/p>\n
For example, we have developed applications to detect celebrities\u2019 faces from recorded TV programmes, to do book stocktaking from bookshelf pictures, or to recognize corporate logos on paper printings.<\/p>\n
<\/p>\n
<\/p>\n
The base technology for these application is image-matching.<\/p>\n
Here I would like to introduce certain basics of the technology.
\nDon\u2019t expect to be able to build commercial-level products just by reading these basics, but at least these will give you an idea of how the technology works.<\/p>\n
Please look at the below two images.<\/p>\n
![\"\"](\"https:\/\/picmatch.io\/home3\/picmatch\/public_html\/wp-content\/uploads\/2015\/02\/6.png\")
<\/p>\n
You can see that the mountain on the right side of the first image and the mountain on the left side of the second image are actually the same one.<\/p>\n
Where does a human look at to determine these two mountains are the same ? The image-matching method simulates this behavior. It uses \u201cfeature points<\/span>\u201d that combine the concepts of shapes and colors. By matching these feature points, we can see the similarities between the two images.<\/p>\n There are two main steps in the image-matching process. The shape of the building in this image could be sketched with the positions of the\u00a0corners<\/span>\u00a0(in yellow).<\/p>\n The image-matching method uses these\u00a0corners<\/span>\u00a0as the feature points.<\/p>\n There are algorithms to extract such corner points. Let me skip the mathematical details. Essentially, when we apply the Harris corner function to the below images,<\/p>\n we will get the following results.<\/p>\n Corners<\/span>\u00a0would have positive values (red colors). The\u00a0local maxima<\/span> (red points) in this image become the \u201cfeature points\u201d.<\/p>\n Note: A local maximum is a point that has the value higher than any neighboring points. You can see these local maxima points somehow describe the shape of the object in the image.<\/p>\n In the below image, not the shapes but the colors actually describe the characteristics of the image better. In this case, we use\u00a0color areas<\/span>\u00a0as the image features.<\/p>\n <\/p>\n This method is called \u201cblob detection\u201d.<\/p>\n <\/p>\n <\/p>\n <\/p>\n <\/p>\n <\/p>\n <\/p>\n <\/p>\n The areas of the same colors are approximated into\u00a0circles<\/span>, and the centers of the circles become the feature points.<\/p>\n Assume that we have extracted the feature points from the two images.<\/p>\n The more matching feature points are there, the more \u201csimilar\u201d the two images are.<\/p>\n The steps for matching feature points are as follows: ii) Compute the\u00a0transformation<\/span>\u00a0from\u00a0a<\/i>\u00a0to\u00a0b<\/i>. iii) Apply the above transformation to\u00a0other<\/span>\u00a0feature points in image A. For each of the feature point in image A be transformed, look into image B to see if there is any feature point in B are \u201cclose\u201d to the transform point.<\/p>\n The definition of being \u201cclose\u201d will be explained later.<\/p>\n \u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014<\/p>\n The above example shows the results after the feature points in image A are transformed.<\/p>\n At the position where a feature point is transformed to, if there is a feature point of B that is \u201cclose\u201d to the transformed point, then we say the two points are \u201cmatching\u201d.<\/p>\n iv) Repeat steps i) to iii) with different initiating pairs in step i), in order to search for the transformation that produces most matching pairs.<\/p>\n v) With the\u00a0transformation that produces the most matching pairs<\/span>, we look at how many pairs there are and how much \u201cclose\u201d the pairs are to determine whether the two images \u201cmatch\u201d.<\/p>\n Practically, there would be thresholds for the number of the pairs and the \u201cclose\u201d-ness.<\/p>\n So, how do we define that two feature points are \u201cclose\u201d ?<\/p>\n A simple way is to take the\u00a0neighboring points<\/span>\u00a0of each feature point, and compare their color values correspondingly.<\/p>\n However, if the images are somehow stretched as in the following examples, comparing point-to-point would not work.<\/p>\n These are the same image patterns, but with slightly different stretch directions. Therefore, we need to do some\u00a0direction alignment (normalization)<\/span>.<\/p>\n We compute the\u00a0color gradients <\/span>in each direction and resize the images so that the color gradients are the same.<\/p>\n Since the brightness of the images may differ, instead of comparing the absolute color values, it is better to compare the differences in color values with neighboring points.<\/p>\n The result of the normalization looks like the following.<\/p>\n <\/p>\n (The left ones are the original images. The middle ones are the images after being resized. The right ones are the color differences with the neighboring points.)<\/p>\n <\/p>\n <\/p>\n Even though the area around feature points in the original images are stretched in different directions, after normalization you could see that they have approximately the same color values and therefore are essentially the same image.<\/p>\n \u2014<\/p>\n Above was the introduction to the basics of image-matching technology.<\/p>\n This article used examples from\u00a0The University of Illinois<\/a>.<\/p>\n
\nMost of the time, humans look at the\u00a0shapes<\/span>\u00a0and the\u00a0colors<\/span>.<\/p>\n
\nFeature points essentially describe the shapes and the colors of the images.<\/p>\n![\"\"](\"https:\/\/picmatch.io\/home3\/picmatch\/public_html\/wp-content\/uploads\/2015\/02\/8.png\")
<\/p>\n
\nA. Extracting feature points from the images.
\nB. Matching the feature points.<\/p>\n
\nA. Extracting feature points<\/span><\/h3>\n
![\"\"](\"https:\/\/picmatch.io\/home3\/picmatch\/public_html\/wp-content\/uploads\/2015\/02\/9.png\")
<\/p>\n
\nFor example, \u201cHarris corner response function<\/a>\u201d is a well-known one.<\/p>\n![\"\"](\"https:\/\/picmatch.io\/home3\/picmatch\/public_html\/wp-content\/uploads\/2015\/02\/10.png\")
<\/p>\n![\"\"](\"https:\/\/picmatch.io\/home3\/picmatch\/public_html\/wp-content\/uploads\/2015\/02\/11.png\")
<\/p>\n
\nLines<\/span>\u00a0would have negative values (deep-blue colors).
\nFlat areas<\/span>\u00a0would have values close to zero (light-blue colors).<\/p>\n![\"\"](\"https:\/\/picmatch.io\/home3\/picmatch\/public_html\/wp-content\/uploads\/2015\/02\/12.png\")
<\/p>\n
\nA local maximum is not necessarily the point with the highest value in the whole image.<\/p>\nNot only corners could be used as feature points<\/h4>\n
![\"\"](\"http:\/\/192.168.1.7\/wp-content\/uploads\/2015\/02\/13.png\")
<\/p>\n
\nB. Matching the feature points<\/span><\/h3>\n
![\"\"](\"https:\/\/picmatch.io\/home3\/picmatch\/public_html\/wp-content\/uploads\/2015\/02\/14.png\")
<\/p>\n
\n\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014
\ni) Choose two feature points (one from each image) that are \u201c<\/strong>close<\/span>\u201c<\/strong>, and make them to\u00a0one pair<\/span>.
\nLet the feature point from image A be\u00a0a<\/i>, feature point from image B be\u00a0b<\/i>.<\/p>\n
\nThe transformation is something like \u201crotate xx degrees, move to left yy pixels, move upper zz pixels \u2026\u201d.<\/p>\n![\"\"](\"https:\/\/picmatch.io\/home3\/picmatch\/public_html\/wp-content\/uploads\/2015\/02\/15.png\")
<\/p>\n\u201cClose\u201d-ness definition<\/h4>\n
![\"\"](\"https:\/\/picmatch.io\/home3\/picmatch\/public_html\/wp-content\/uploads\/2015\/02\/16.png\")
<\/p>\n
\nIn this case, it is not easy to find the corresponding points to compare.<\/p>\n![\"\"](\"https:\/\/picmatch.io\/home3\/picmatch\/public_html\/wp-content\/uploads\/2015\/02\/17-300x171.png\")
<\/p>\n