2 * Image Library -- Duplicates Comparison
4 * (c) 2006 Pavel Charvat <pchar@ucw.cz>
6 * This software may be freely distributed and used according to the terms
7 * of the GNU Lesser General Public License.
11 * - many possible optimization
12 * - compare normalized pictures (brightness, ...)
13 * - better image scale... now it can completely miss some rows/cols of pixels
14 * - maybe better/slower last step
15 * - different thresholds for various transformations
16 * - do not test all transformations for symetric pictures
17 * - ... secret ideas :-)
22 #include "sherlock/sherlock.h"
23 #include "lib/mempool.h"
24 #include "images/images.h"
25 #include "images/dup-cmp.h"
27 static uns image_dup_scale_min_size = 16;
28 static uns image_dup_ratio_threshold = 140;
29 static uns image_dup_error_threshold = 50;
32 image_dup_block(struct image_dup *dup, uns col, uns row)
34 ASSERT(col <= dup->cols && row <= dup->rows);
35 return dup->buf + (dup->line << row) + (3 << (row + col));
39 pixels_average(byte *dest, byte *src1, byte *src2)
41 dest[0] = ((uns)src1[0] + (uns)src2[0]) >> 1;
42 dest[1] = ((uns)src1[1] + (uns)src2[1]) >> 1;
43 dest[2] = ((uns)src1[2] + (uns)src2[2]) >> 1;
47 image_dup_init(struct image_dup *dup, struct image *image, struct mempool *pool)
49 ASSERT(image->width && image->height);
52 dup->width = image->width;
53 dup->height = image->height;
54 for (dup->cols = 0; (uns)(2 << dup->cols) < image->width; dup->cols++);
55 for (dup->rows = 0; (uns)(2 << dup->rows) < image->height; dup->rows++);
56 dup->buf = mp_alloc(pool, dup->buf_size = (12 << (dup->cols + dup->rows)));
57 dup->line = 6 << dup->cols;
59 if (image->width >= image_dup_scale_min_size && image->height >= image_dup_scale_min_size)
60 dup->flags |= IMAGE_DUP_FLAG_SCALE;
62 /* Scale original image to right bottom block */
64 byte *d = image_dup_block(dup, dup->cols, dup->rows);
65 uns width = 1 << dup->cols;
66 uns height = 1 << dup->rows;
67 uns line_size = 3 * image->width;
69 for (uns y = 0; y < height; y++)
71 byte *line = image->pixels + line_size * (src_y >> dup->rows);
73 for (uns x = 0; x < width; x++)
75 byte *s = line + 3 * (src_x >> dup->cols);
80 src_x += image->width;
82 src_y += image->height;
86 /* Complete bottom row */
87 for (uns i = dup->cols; i--; )
89 byte *d = image_dup_block(dup, i, dup->rows);
90 byte *s = image_dup_block(dup, i + 1, dup->rows);
91 for (uns y = 0; y < (uns)(1 << dup->rows); y++)
92 for (uns x = 0; x < (uns)(1 << i); x++)
94 pixels_average(d, s, s + 3);
100 /* Complete remaining blocks */
101 for (uns i = 0; i <= dup->cols; i++)
103 uns line_size = (3 << i);
104 for (uns j = dup->rows; j--; )
106 byte *d = image_dup_block(dup, i, j);
107 byte *s = image_dup_block(dup, i, j + 1);
108 for (uns y = 0; y < (uns)(1 << j); y++)
110 for (uns x = 0; x < (uns)(1 << i); x++)
112 pixels_average(d, s, s + line_size);
130 err_sum(byte *pos1, byte *end1, byte *pos2)
134 e += err(*pos1++, *pos2++);
139 err_sum_transformed(byte *pos1, byte *end1, byte *pos2, uns width, int add1, int add2)
141 DBG("err_sum_transformed(): %p %p %p %d %d %d", pos1, end1, pos2, width, add1, add2);
145 for (uns i = 0; i < width; i++, pos2 += add1)
147 e += err(pos1[0], pos2[0]);
148 e += err(pos1[1], pos2[1]);
149 e += err(pos1[2], pos2[2]);
158 aspect_ratio_test(uns width1, uns height1, uns width2, uns height2)
160 uns r1 = width1 * height2;
161 uns r2 = height1 * width2;
163 r1 <= ((r2 * image_dup_ratio_threshold) >> 5) &&
164 r2 <= ((r1 * image_dup_ratio_threshold) >> 5);
168 average_compare(struct image_dup *dup1, struct image_dup *dup2)
170 byte *block1 = image_dup_block(dup1, 0, 0);
171 byte *block2 = image_dup_block(dup2, 0, 0);
173 err(block1[0], block2[0]) +
174 err(block1[1], block2[1]) +
175 err(block1[2], block2[2]);
176 return e <= image_dup_error_threshold;
180 blocks_compare(struct image_dup *dup1, struct image_dup *dup2, uns col, uns row, uns trans)
182 DBG("blocks_compare(): col=%d row=%d trans=%d", col, row, trans);
183 byte *block1 = image_dup_block(dup1, col, row);
184 byte *block2 = (trans < 4) ? image_dup_block(dup2, col, row) : image_dup_block(dup2, row, col);
189 uns err = (err_sum(block1, block1 + (3 << (col + row)), block2) >> (col + row));
190 DBG("average error=%d", err);
191 return err <= image_dup_error_threshold;
195 block2 += (3 << col) - 3;
200 block2 += (3 << (col + row)) - (3 << col);
205 block2 += (3 << (col + row)) - 3;
209 add2 = -(3 << (col + row)) + 3;
213 add2 = (3 << (col + row)) + 3;
214 block2 += (3 << (col + row)) - (3 << col);
218 add2 = -(3 << (col + row)) - 3;
219 block2 += (3 << col) - 3;
223 add2 = (3 << (col + row)) - 3;
224 block2 += (3 << (col + row)) - 3;
229 uns err = (err_sum_transformed(block1, block1 + (3 << (col + row)), block2, (1 << col), add1, add2) >> (col + row));
230 DBG("average error=%d", err);
231 return err <= image_dup_error_threshold;
235 same_size_compare(struct image_dup *dup1, struct image_dup *dup2, uns trans)
237 byte *block1 = dup1->image->pixels;
238 byte *block2 = dup2->image->pixels;
239 DBG("same_size_compare(): trans=%d", trans);
244 uns err = (err_sum(block1, block1 + 3 * dup1->width * dup1->height, block2) / (dup1->width * dup1->height));
245 DBG("average error=%d", err);
246 return err <= image_dup_error_threshold;
249 add2 = 6 * dup1->width;
250 block2 += 3 * (dup1->width - 1);
254 add2 = -6 * dup1->width;
255 block2 += 3 * dup1->width * (dup1->height - 1);
260 block2 += 3 * (dup1->width * dup1->height - 1);
263 add1 = 3 * dup1->width;
264 add2 = -3 * (dup1->width * dup1->height - 1);
267 add1 = -3 * dup1->width;
268 add2 = 3 * (dup1->width * dup1->height + 1);
269 block2 += 3 * dup1->width * (dup1->height - 1);
272 add1 = 3 * dup1->width;
273 add2 = -3 * (dup1->width * dup1->height + 1);
274 block2 += 3 * (dup1->width - 1);
277 add1 = -3 * dup1->width;
278 add2 = 3 * (dup1->width * dup1->height - 1);
279 block2 += 3 * (dup1->width * dup1->height - 1);
284 uns err = (err_sum_transformed(block1, block1 + 3 * dup1->width * dup1->height, block2, dup1->width, add1, add2) / (dup1->width * dup1->height));
285 DBG("average error=%d", err);
286 return err <= image_dup_error_threshold;
290 image_dup_compare(struct image_dup *dup1, struct image_dup *dup2, uns trans)
292 if (!average_compare(dup1, dup2))
294 if ((dup1->flags & dup2->flags) & IMAGE_DUP_FLAG_SCALE)
296 DBG("Scale support");
297 if (!aspect_ratio_test(dup1->width, dup1->height, dup2->width, dup2->height))
299 if (!aspect_ratio_test(dup1->width, dup1->height, dup2->height, dup2->width))
304 DBG("No scale support");
305 if (!(dup1->width == dup2->width && dup1->height == dup2->height))
307 if (!(dup1->width == dup2->height && dup1->height == dup2->width))
314 uns cols = MIN(dup1->cols, dup2->cols);
315 uns rows = MIN(dup1->rows, dup2->rows);
316 for (uns t = 0; t < 4; t++)
317 if (trans & (1 << t))
319 DBG("Testing trans %d", t);
320 for (uns i = MAX(cols, rows); i--; )
322 uns col = MAX(0, (int)(cols - i));
323 uns row = MAX(0, (int)(rows - i));
324 if (!blocks_compare(dup1, dup2, col, row, t))
327 (dup1->width != dup2->width || dup1->height != dup2->height ||
328 same_size_compare(dup1, dup2, t)))
335 uns cols = MIN(dup1->cols, dup2->rows);
336 uns rows = MIN(dup1->rows, dup2->cols);
337 for (uns t = 4; t < 8; t++)
338 if (trans & (1 << t))
340 DBG("Testing trans %d", t);
341 for (uns i = MAX(cols, rows); i--; )
343 uns col = MAX(0, (int)(cols - i));
344 uns row = MAX(0, (int)(rows - i));
345 if (!blocks_compare(dup1, dup2, col, row, t))
348 (dup1->width != dup2->height || dup1->height != dup2->width ||
349 same_size_compare(dup1, dup2, t)) )