X-Git-Url: http://mj.ucw.cz/gitweb/?a=blobdiff_plain;ds=sidebyside;f=images%2Fdup-cmp.c;h=c0232a4d4813c7d5e8b95447eb166811fdc3442c;hb=77c84c65dc22afe21bc52d95cd3996b8e1c7d065;hp=35e1ec8e99d992b9be072502dee5c28f31cb0300;hpb=f8eb8bab9f7a35b8c3249517715134693e5920dc;p=libucw.git diff --git a/images/dup-cmp.c b/images/dup-cmp.c index 35e1ec8e..c0232a4d 100644 --- a/images/dup-cmp.c +++ b/images/dup-cmp.c @@ -5,124 +5,18 @@ * * This software may be freely distributed and used according to the terms * of the GNU Lesser General Public License. - * - * - * FIXME: - * - many possible optimization - * - compare normalized pictures (brightness, ...) - * - a blur should help to deal with scaling errors - * - maybe better/slower last step - * - different thresholds for various transformations - * - do not test all transformations for symetric pictures - * - allocated memory could be easily decreased to about 1/3 - * for aspect ratio threshold near one */ #undef LOCAL_DEBUG -#include "sherlock/sherlock.h" -#include "lib/mempool.h" -#include "images/images.h" -#include "images/dup-cmp.h" +#include +#include +#include +#include +#include -#include "lib/mempool.h" -#include "lib/fastbuf.h" #include -static uns image_dup_ratio_threshold = 140; -static uns image_dup_error_threshold = 800; -static uns image_dup_tab_limit = 8; - -static inline byte * -image_dup_block(struct image_dup *dup, uns tab_col, uns tab_row) -{ - return dup->tab_pixels + (dup->tab_row_size << tab_row) + (3 << (tab_row + tab_col)); -} - -static inline struct image * -image_dup_subimage(struct image_thread *thread, struct image_dup *dup, struct image *block, uns tab_col, uns tab_row) -{ - return image_init_matrix(thread, block, image_dup_block(dup, tab_col, tab_row), - 1 << tab_col, 1 << tab_row, 3 << tab_col, COLOR_SPACE_RGB); -} - -static inline void -pixels_average(byte *dest, byte *src1, byte *src2) -{ - dest[0] = ((uns)src1[0] + (uns)src2[0]) >> 1; - dest[1] = ((uns)src1[1] + (uns)src2[1]) >> 1; - dest[2] = ((uns)src1[2] + (uns)src2[2]) >> 1; -} - -uns -image_dup_estimate_size(uns cols, uns rows) -{ - uns tab_cols, tab_rows; - for (tab_cols = 0; (uns)(2 << tab_cols) < cols && tab_cols < image_dup_tab_limit; tab_cols++); - for (tab_rows = 0; (uns)(2 << tab_rows) < rows && tab_rows < image_dup_tab_limit; tab_rows++); - return sizeof(struct image) + cols * rows * 3 + sizeof(struct image_dup) + (12 << (tab_cols + tab_rows)) + 64; -} - -uns -image_dup_init(struct image_thread *thread, struct image_dup *dup, struct image *img, struct mempool *pool) -{ - DBG("image_dup_init()"); - - ASSERT((img->flags & IMAGE_PIXEL_FORMAT) == COLOR_SPACE_RGB); - - dup->image = img; - for (dup->tab_cols = 0; (uns)(2 << dup->tab_cols) < img->cols && dup->tab_cols < image_dup_tab_limit; dup->tab_cols++); - for (dup->tab_rows = 0; (uns)(2 << dup->tab_rows) < img->rows && dup->tab_rows < image_dup_tab_limit; dup->tab_rows++); - dup->tab_pixels = mp_alloc(pool, dup->tab_size = (12 << (dup->tab_cols + dup->tab_rows))); - dup->tab_row_size = 6 << dup->tab_cols; - - /* Scale original image to right bottom block */ - { - struct image block; - if (!image_dup_subimage(thread, dup, &block, dup->tab_cols, dup->tab_rows)) - return 0; - if (!image_scale(thread, &block, img)) - return 0; - } - - /* Complete bottom row */ - for (uns i = dup->tab_cols; i--; ) - { - byte *d = image_dup_block(dup, i, dup->tab_rows); - byte *s = image_dup_block(dup, i + 1, dup->tab_rows); - for (uns y = 0; y < (uns)(1 << dup->tab_rows); y++) - for (uns x = 0; x < (uns)(1 << i); x++) - { - pixels_average(d, s, s + 3); - d += 3; - s += 6; - } - } - - /* Complete remaining blocks */ - for (uns i = 0; i <= dup->tab_cols; i++) - { - uns line_size = (3 << i); - for (uns j = dup->tab_rows; j--; ) - { - byte *d = image_dup_block(dup, i, j); - byte *s = image_dup_block(dup, i, j + 1); - for (uns y = 0; y < (uns)(1 << j); y++) - { - for (uns x = 0; x < (uns)(1 << i); x++) - { - pixels_average(d, s, s + line_size); - d += 3; - s += 3; - } - s += line_size; - } - } - } - - return 1; -} - static inline uns err (int a, int b) { @@ -171,18 +65,18 @@ err_sum_transformed(byte *pos1, byte *pos2, uns cols, uns rows, int row_step_1, } static inline int -aspect_ratio_test(uns cols1, uns rows1, uns cols2, uns rows2) +aspect_ratio_test(struct image_dup_context *ctx, uns cols1, uns rows1, uns cols2, uns rows2) { DBG("aspect_ratio_test(cols1=%u rows1=%u cols2=%u rows2=%u)", cols1, rows1, cols2, rows2); uns r1 = cols1 * rows2; uns r2 = rows1 * cols2; return - r1 <= ((r2 * image_dup_ratio_threshold) >> 7) && - r2 <= ((r1 * image_dup_ratio_threshold) >> 7); + r1 <= ((r2 * ctx->ratio_threshold) >> 7) && + r2 <= ((r1 * ctx->ratio_threshold) >> 7); } static inline int -average_compare(struct image_dup *dup1, struct image_dup *dup2) +average_compare(struct image_dup_context *ctx, struct image_dup *dup1, struct image_dup *dup2) { byte *block1 = image_dup_block(dup1, 0, 0); byte *block2 = image_dup_block(dup2, 0, 0); @@ -190,13 +84,14 @@ average_compare(struct image_dup *dup1, struct image_dup *dup2) err(block1[0], block2[0]) + err(block1[1], block2[1]) + err(block1[2], block2[2]); - return e <= image_dup_error_threshold; + return e <= ctx->error_threshold; } static int -blocks_compare(struct image_dup *dup1, struct image_dup *dup2, uns tab_col, uns tab_row, uns trans) +blocks_compare(struct image_dup_context *ctx, struct image_dup *dup1, struct image_dup *dup2, uns tab_col, uns tab_row, uns trans) { DBG("blocks_compare(tab_col=%d tab_row=%d trans=%d)", tab_col, tab_row, trans); + ctx->sum_pixels += 1 << (tab_col + tab_row); byte *block1 = image_dup_block(dup1, tab_col, tab_row); byte *block2; int col_step, row_step; @@ -209,7 +104,8 @@ blocks_compare(struct image_dup *dup1, struct image_dup *dup2, uns tab_col, uns case 0: ; uns err = (err_sum(block1, block2, 1 << (tab_col + tab_row)) >> (tab_col + tab_row)); DBG("average error=%d", err); - return err <= image_dup_error_threshold; + ctx->error = err; + return err <= ctx->error_threshold; case 1: col_step = -3; row_step = (3 << tab_col); @@ -249,14 +145,18 @@ blocks_compare(struct image_dup *dup1, struct image_dup *dup2, uns tab_col, uns } uns err = (err_sum_transformed(block1, block2, (1 << tab_col), (1 << tab_row), (3 << tab_col), col_step, row_step) >> (tab_col + tab_row)); DBG("average error=%d", err); - return err <= image_dup_error_threshold; + ctx->error = err; + return err <= ctx->error_threshold; } static int -same_size_compare(struct image_dup *dup1, struct image_dup *dup2, uns trans) +same_size_compare(struct image_dup_context *ctx, struct image_dup *dup1, struct image_dup *dup2, uns trans) { - struct image *img1 = dup1->image; - struct image *img2 = dup2->image; + struct image *img1 = &dup1->image; + struct image *img2 = &dup2->image; + if (!img1->pixels || !img2->pixels) + return 1; + ctx->sum_pixels += img1->cols * img1->rows; byte *block1 = img1->pixels; byte *block2 = img2->pixels; int col_step, row_step; @@ -306,23 +206,25 @@ same_size_compare(struct image_dup *dup1, struct image_dup *dup2, uns trans) } uns err = (err_sum_transformed(block1, block2, img1->cols, img1->rows, img1->row_size, col_step, row_step) / ((u64)img1->cols * img1->rows)); DBG("average error=%d", err); - return err <= image_dup_error_threshold; + ctx->error = err; + return err <= ctx->error_threshold; } uns -image_dup_compare(struct image_dup *dup1, struct image_dup *dup2, uns flags) +image_dup_compare(struct image_dup_context *ctx, struct image_dup *dup1, struct image_dup *dup2) { - DBG("image_dup_compare()"); - if (!average_compare(dup1, dup2)) + DBG("image_dup_compare(%p, %p)", dup1, dup2); + if (!average_compare(ctx, dup1, dup2)) return 0; - struct image *img1 = dup1->image; - struct image *img2 = dup2->image; + struct image *img1 = &dup1->image; + struct image *img2 = &dup2->image; + uns flags = ctx->flags; if (flags & IMAGE_DUP_SCALE) { DBG("Scale support"); - if (!aspect_ratio_test(img1->cols, img1->rows, img2->cols, img2->rows)) + if (!aspect_ratio_test(ctx, img1->cols, img1->rows, img2->cols, img2->rows)) flags &= ~0x0f; - if (!aspect_ratio_test(img1->cols, img1->rows, img2->rows, img2->cols)) + if (!aspect_ratio_test(ctx, img1->cols, img1->rows, img2->rows, img2->cols)) flags &= ~0xf0; } else @@ -344,15 +246,17 @@ image_dup_compare(struct image_dup *dup1, struct image_dup *dup2, uns flags) if (flags & (1 << t)) { DBG("Testing trans %d", t); - for (uns i = MAX(cols, rows); i--; ) + uns i = MAX(cols, rows), depth = 1; + while (i--) { + depth++; uns col = MAX(0, (int)(cols - i)); uns row = MAX(0, (int)(rows - i)); - if (!blocks_compare(dup1, dup2, col, row, t)) + if (!blocks_compare(ctx, dup1, dup2, col, row, t)) break; if (!i && (img1->cols != img2->cols || img1->rows != img2->rows || - same_size_compare(dup1, dup2, t))) + same_size_compare(ctx, dup1, dup2, t))) { result |= 1 << t; if (!(flags & IMAGE_DUP_WANT_ALL)) @@ -361,6 +265,7 @@ image_dup_compare(struct image_dup *dup1, struct image_dup *dup2, uns flags) break; } } + ctx->sum_depth += depth; } } if (flags & 0xf0) @@ -371,15 +276,17 @@ image_dup_compare(struct image_dup *dup1, struct image_dup *dup2, uns flags) if (flags & (1 << t)) { DBG("Testing trans %d", t); - for (uns i = MAX(cols, rows); i--; ) + uns i = MAX(cols, rows), depth = 1; + while (i--) { + depth++; uns col = MAX(0, (int)(cols - i)); uns row = MAX(0, (int)(rows - i)); - if (!blocks_compare(dup1, dup2, col, row, t)) + if (!blocks_compare(ctx, dup1, dup2, col, row, t)) break; if (!i && (img1->cols != img2->rows || img1->rows != img2->cols || - same_size_compare(dup1, dup2, t)) ) + same_size_compare(ctx, dup1, dup2, t)) ) { result |= 1 << t; if (!(flags & IMAGE_DUP_WANT_ALL)) @@ -388,6 +295,7 @@ image_dup_compare(struct image_dup *dup1, struct image_dup *dup2, uns flags) break; } } + ctx->sum_depth += depth; } } return result;