-
Notifications
You must be signed in to change notification settings - Fork 3
/
algorithm-for-perceptual-image-comparison.html
117 lines (71 loc) · 6.61 KB
/
algorithm-for-perceptual-image-comparison.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
<!-- Copyright by Vitali Fedulov (fedulov.vitali@gmail.com) 2015-2018 -->
<!DOCTYPE html>
<html lang="en">
<head>
<title>Near duplicate image search algorithm</title>
<meta charset="utf-8">
<meta name="viewport" content="width=device-width, initial-scale=1">
<link rel="icon" type="image/png" href="images/favicon.png">
<link rel="stylesheet" type="text/css" href="css/index.css">
<link rel="stylesheet" href="https://fonts.googleapis.com/css?family=Roboto">
</head>
<body>
<!-- Header -->
<div class="header">
<a href = "index.html" class="logo"><h1>Similar Pictures Search</h1></a>
<h4 class="logo-statement">Find near duplicates on your computer</h4>
</div>
<div class="nav">
<!-- Set manually class "active" for corresponding nav-tab. -->
<div class="nav-tab"><a href="index.html">Home</a></div>
<div class="nav-tab"><a href="duplicate-image-search-example.html">Demo</a></div>
<div class="nav-tab active"><a href="research.html">Research</a></div>
<div class="nav-tab"><a href="tools.html">Tools</a></div>
<div class="nav-tab"><a href="about.html">About</a></div>
<div class="line"></div> <!-- Gray line placeholder. Should stay here. -->
</div>
<!-- Blog organization:
1. Home page navigation links to the latest blog-[date].html file. The pages must never
change file name/address, so if linked by other sites they stay constant.
2. Each blog page will later have a list of all articles linked by html injection,
e.g. secondary navigation menu. Place in upper part of the blog as TOC.
-->
<!-- Contents -->
<p class="published">fedulov.vitali@gmail.com, <time datetime="2022-01-24">24 January 2022</time></p>
<h3 id="2018-10-29">Image comparison algorithm to find near duplicates</h3> <!-- Id used for URL anchors.-->
<p>The image comparison algorithm I developed for the service makes use of perceptual similarity by performing the following set of operations. To understand how the idea evolved, check <a href="algorithm-old-for-perceptual-image-comparison.html" target="_blank">previous version of the algorithm</a>.</p>
<h4>1. Image resizing</h4>
<p>Source images are resized to square images ("icons") of 23x23 pixels. The resizing is done in such a way that color relationships between original image sub-regions are carefully preserved by using high precision values, unlike in common graphic editors. Specifically: float values are used instead of uint8 and pixel values are sampled with high density.</p>
<figure class="blog-img-2022">
<img src="images/2022-image-resizing.png" alt="image resizing">
</figure>
<h4>2. Box blur</h4>
<p>Box blur filter of 3x3 is taken at every 2nd row/column. The final icon size is 11x11.</p>
<figure class="blog-img-2022">
<img src="images/2022-box-blur.png" alt="box blur">
</figure>
<h4>3. Color space modification</h4>
<p>RGB color space of the icon is transformed into YCbCr to give more importance to luma vs chroma components. This step is optional, but works well for cases when a colored and grayscale versions of the same image are compared.</p>
<h4>4. Histogram normalization</h4>
<p>This operation stretches histograms for each color channel of the icon so that [min, max] value range becomes [0.0, 255.0]. This increases the range of pixel values (and increases icon contrast). This step is optional, depending on similarity aspects: but usually same images of different contrast can be considered similar.</p>
<figure class="blog-img-2022">
<img src="images/2022-normalization.png" alt="masks for image comparison">
</figure>
<h4>5. Image comparision (final step)</h4>
<p>The input to this operation is a pair of icons from step (4) and original image sizes.</p>
<p>Image sizes are used as a first step to quickly eliminate possible mismatch. If image proportions are considerably different, images are considered non-similar, so no further checks are performed.</p>
<p>Then the two icons are compared by Euclidean distance. If the distance is larger than a certain threshold, images are considered non-similar.</p>
<br>
<h4>Possible optimizations</h4>
<p><strong>Optimization 1:</strong> To increase precision of the algorithm, one may apply it on image sub-regions (instead of the whole image). If at least one region is not similar, images can be considered distinct.</p>
<p><strong>Optimization 2:</strong> Resizing a rectangular image to a square icon causes proportion changes and allows to preserve information from every region of the input image. Such resizing is optional. Instead it is possible to use exclusively the central square area of the input image for comparison, thus discarding information outside the central square.</p>
<p><strong>Optimization 3a:</strong> In addition to color values for icon generation it is also possible to use filter-based values, e.g. by passing an image through an edge detector. This allows to count additional visual signals within sub-regions. For example a photo of forest will have distinct edge values compared to some smooth background of the same color (because trees have leaves, thus many edges). Such approach allows to distinguish between textures. The challenge is finding an optimal coefficient for perceptual significance of edge information vs. color information during comparison.</p>
<p><strong>Optimization 3b:</strong> Instead of summation of colors within icon sub-regions, it is possible to sum over features extracted with convolutional neural network filter layers.</p>
<p><strong>Optimization 4:</strong> When the number of images is very large (more than millions), using Euclidean metric for search might be slow. It is possible to use hash tables as a preliminary step before checking Euclidean distance. For that a certain number of sample points from the icon can be taken and then a <a href="algorithm-for-hashing-high-dimensional-float-vectors.html" target="_blank">hashing algorithm for floating point vectors</a> can be applied to the sample vector.</p>
<h4>Algorithm implementation</h4>
<p>Written in Golang <a href="https://github.com/vitali-fedulov/images4">image comparison (Github)</a>.</p>
<br>
<p class="published">This is my original research. Please treat it as such for references, provided you do not find an earlier similar research by others, which is possible. Sometimes solutions have to be rediscovered, because either papers are hard to find, or they are difficult to understand.</p>
<div class = "footer">Copyright © 2022 Vitali Fedulov. All rights reserved.</div>
</body>
</html>