]> mj.ucw.cz Git - libucw.git/blob - images/dup-cmp.c
decreased duplicate images threshold; disabled rotations/flips
[libucw.git] / images / dup-cmp.c
1 /*
2  *      Image Library -- Duplicates Comparison
3  *
4  *      (c) 2006 Pavel Charvat <pchar@ucw.cz>
5  *
6  *      This software may be freely distributed and used according to the terms
7  *      of the GNU Lesser General Public License.
8  */
9
10 #undef LOCAL_DEBUG
11
12 #include "sherlock/sherlock.h"
13 #include "lib/mempool.h"
14 #include "lib/fastbuf.h"
15 #include "images/images.h"
16 #include "images/duplicates.h"
17
18 #include <fcntl.h>
19
20 static uns image_dup_ratio_threshold = 140;
21 static uns image_dup_error_threshold = 100;
22
23 static inline uns
24 err (int a, int b)
25 {
26   a -= b;
27   return a * a;
28 }
29
30 static inline u64
31 err_sum(byte *pos1, byte *pos2, uns count)
32 {
33   uns e64 = 0;
34   while (count--)
35     {
36       uns e = err(*pos1++, *pos2++);
37       e += err(*pos1++, *pos2++);
38       e += err(*pos1++, *pos2++);
39       e64 += e;
40     }
41   return e64;
42 }
43
44 static inline u64
45 err_sum_transformed(byte *pos1, byte *pos2, uns cols, uns rows, int row_step_1, int col_step_2, int row_step_2)
46 {
47   DBG("err_sum_transformed(pos1=%p pos2=%p cols=%u rows=%u row_step_1=%d col_step_2=%d row_step_2=%d)",
48       pos1, pos2, cols, rows, row_step_1, col_step_2, row_step_2);
49   u64 e64 = 0;
50   for (uns j = rows; j--; )
51     {
52       byte *p1 = pos1;
53       byte *p2 = pos2;
54       uns e = 0;
55       for (uns i = cols; i--; )
56       {
57         e += err(p1[0], p2[0]);
58         e += err(p1[1], p2[1]);
59         e += err(p1[2], p2[2]);
60         p1 += 3;
61         p2 += col_step_2;
62       }
63       pos1 += row_step_1;
64       pos2 += row_step_2;
65       e64 += e;
66     }
67   return e64;
68 }
69
70 static inline int
71 aspect_ratio_test(uns cols1, uns rows1, uns cols2, uns rows2)
72 {
73   DBG("aspect_ratio_test(cols1=%u rows1=%u cols2=%u rows2=%u)", cols1, rows1, cols2, rows2);
74   uns r1 = cols1 * rows2;
75   uns r2 = rows1 * cols2;
76   return
77     r1 <= ((r2 * image_dup_ratio_threshold) >> 7) &&
78     r2 <= ((r1 * image_dup_ratio_threshold) >> 7);
79 }
80
81 static inline int
82 average_compare(struct image_dup *dup1, struct image_dup *dup2)
83 {
84   byte *block1 = image_dup_block(dup1, 0, 0);
85   byte *block2 = image_dup_block(dup2, 0, 0);
86   uns e =
87     err(block1[0], block2[0]) +
88     err(block1[1], block2[1]) +
89     err(block1[2], block2[2]);
90   return e <= image_dup_error_threshold;
91 }
92
93 static int
94 blocks_compare(struct image_dup *dup1, struct image_dup *dup2, uns tab_col, uns tab_row, uns trans)
95 {
96   DBG("blocks_compare(tab_col=%d tab_row=%d trans=%d)", tab_col, tab_row, trans);
97   byte *block1 = image_dup_block(dup1, tab_col, tab_row);
98   byte *block2;
99   int col_step, row_step;
100   if (trans < 4)
101     block2 = image_dup_block(dup2, tab_col, tab_row);
102   else
103     block2 = image_dup_block(dup2, tab_row, tab_col);
104   switch (trans)
105     {
106       case 0: ;
107         uns err = (err_sum(block1, block2, 1 << (tab_col + tab_row)) >> (tab_col + tab_row));
108         DBG("average error=%d", err);
109         return err <= image_dup_error_threshold;
110       case 1:
111         col_step = -3;
112         row_step = (3 << tab_col);
113         block2 += row_step - 3;
114         break;
115       case 2:
116         col_step = 3;
117         row_step = -(3 << tab_col);
118         block2 += (3 << (tab_col + tab_row)) + row_step;
119         break;
120       case 3:
121         col_step = -3;
122         row_step = -(3 << tab_col);
123         block2 += (3 << (tab_col + tab_row)) - 3;
124         break;
125       case 4:
126         col_step = (3 << tab_row);
127         row_step = 3;
128         break;
129       case 5:
130         col_step = -(3 << tab_row);
131         row_step = 3;
132         block2 += (3 << (tab_col + tab_row)) + col_step;
133         break;
134       case 6:
135         col_step = (3 << tab_row);
136         row_step = -3;
137         block2 += col_step - 3;
138         break;
139       case 7:
140         col_step = -(3 << tab_row);
141         row_step = -3;
142         block2 += (3 << (tab_col + tab_row)) - 3;
143         break;
144       default:
145         ASSERT(0);
146     }
147   uns err = (err_sum_transformed(block1, block2, (1 << tab_col), (1 << tab_row), (3 << tab_col), col_step, row_step) >> (tab_col + tab_row));
148   DBG("average error=%d", err);
149   return err <= image_dup_error_threshold;
150 }
151
152 static int
153 same_size_compare(struct image_dup *dup1, struct image_dup *dup2, uns trans)
154 {
155   struct image *img1 = dup1->image;
156   struct image *img2 = dup2->image;
157   byte *block1 = img1->pixels;
158   byte *block2 = img2->pixels;
159   int col_step, row_step;
160   DBG("same_size_compare(trans=%d)",  trans);
161   switch (trans)
162     {
163       case 0: ;
164         col_step = 3;
165         row_step = img2->row_size;
166         break;
167       case 1:
168         col_step = -3;
169         row_step = img2->row_size;
170         block2 += 3 * (img2->cols - 1);
171         break;
172       case 2:
173         col_step = 3;
174         row_step = -img2->row_size;
175         block2 += img2->row_size * (img2->rows - 1);
176         break;
177       case 3:
178         col_step = -3;
179         row_step = -img2->row_size;
180         block2 += img2->row_size * (img2->rows - 1) + 3 * (img2->cols - 1);
181         break;
182       case 4:
183         col_step = img2->row_size;
184         row_step = 3;
185         break;
186       case 5:
187         col_step = -img2->row_size;
188         row_step = 3;
189         block2 += img2->row_size * (img2->rows - 1);
190         break;
191       case 6:
192         col_step = img2->row_size;
193         row_step = -3;
194         block2 += 3 * (img2->cols - 1);
195         break;
196       case 7:
197         col_step = -img2->row_size;
198         row_step = -3;
199         block2 += img2->row_size * (img2->rows - 1) + 3 * (img2->cols - 1);
200         break;
201       default:
202         ASSERT(0);
203     }
204   uns err = (err_sum_transformed(block1, block2, img1->cols, img1->rows, img1->row_size, col_step, row_step) / ((u64)img1->cols * img1->rows));
205   DBG("average error=%d", err);
206   return err <= image_dup_error_threshold;
207 }
208
209 uns
210 image_dup_compare(struct image_dup *dup1, struct image_dup *dup2, uns flags)
211 {
212   DBG("image_dup_compare()");
213   if (!average_compare(dup1, dup2))
214     return 0;
215   struct image *img1 = dup1->image;
216   struct image *img2 = dup2->image;
217   if (flags & IMAGE_DUP_SCALE)
218     {
219       DBG("Scale support");
220       if (!aspect_ratio_test(img1->cols, img1->rows, img2->cols, img2->rows))
221         flags &= ~0x0f;
222       if (!aspect_ratio_test(img1->cols, img1->rows, img2->rows, img2->cols))
223         flags &= ~0xf0;
224     }
225   else
226     {
227       DBG("No scale support");
228       if (!(img1->cols == img2->cols && img1->rows == img2->rows))
229         flags &= ~0x0f;
230       if (!(img1->cols == img2->rows && img1->rows == img2->cols))
231         flags &= ~0xf0;
232     }
233   if (!(flags & 0xff))
234     return 0;
235   uns result = 0;
236   if (flags & 0x0f)
237     {
238       uns cols = MIN(dup1->tab_cols, dup2->tab_cols);
239       uns rows = MIN(dup1->tab_rows, dup2->tab_rows);
240       for (uns t = 0; t < 4; t++)
241         if (flags & (1 << t))
242           {
243             DBG("Testing trans %d", t);
244             for (uns i = MAX(cols, rows); i--; )
245               {
246                 uns col = MAX(0, (int)(cols - i));
247                 uns row = MAX(0, (int)(rows - i));
248                 if (!blocks_compare(dup1, dup2, col, row, t))
249                   break;
250                 if (!i &&
251                     (img1->cols != img2->cols || img1->rows != img2->rows ||
252                     same_size_compare(dup1, dup2, t)))
253                   {
254                     result |= 1 << t;
255                     if (!(flags & IMAGE_DUP_WANT_ALL))
256                       return result;
257                     else
258                       break;
259                   }
260               }
261           }
262     }
263   if (flags & 0xf0)
264     {
265       uns cols = MIN(dup1->tab_cols, dup2->tab_rows);
266       uns rows = MIN(dup1->tab_rows, dup2->tab_cols);
267       for (uns t = 4; t < 8; t++)
268         if (flags & (1 << t))
269           {
270             DBG("Testing trans %d", t);
271             for (uns i = MAX(cols, rows); i--; )
272               {
273                 uns col = MAX(0, (int)(cols - i));
274                 uns row = MAX(0, (int)(rows - i));
275                 if (!blocks_compare(dup1, dup2, col, row, t))
276                   break;
277                 if (!i &&
278                     (img1->cols != img2->rows || img1->rows != img2->cols ||
279                     same_size_compare(dup1, dup2, t)) )
280                   {
281                     result |= 1 << t;
282                     if (!(flags & IMAGE_DUP_WANT_ALL))
283                       return result;
284                     else
285                       break;
286                   }
287               }
288           }
289     }
290   return result;
291 }