From 2f678dc9ccd4cd88531c97ad48375074db3ad8be Mon Sep 17 00:00:00 2001 From: Pavel Charvat Date: Wed, 14 Nov 2007 13:16:55 +0100 Subject: [PATCH] Backuped experiments with image duplicates. --- images/dup-cmp.c | 48 +++++++++++++++++++------------------- images/dup-init.c | 51 ++++++++++++++++++++++++++++++++++++----- images/duplicates.h | 45 ++++++++++++++++++++++-------------- images/image-dup-test.c | 20 ++++++++++++---- 4 files changed, 111 insertions(+), 53 deletions(-) diff --git a/images/dup-cmp.c b/images/dup-cmp.c index 1bee7fa4..e05fae3d 100644 --- a/images/dup-cmp.c +++ b/images/dup-cmp.c @@ -17,9 +17,6 @@ #include -static uns image_dup_ratio_threshold = 140; -static uns image_dup_error_threshold = 100; - static inline uns err (int a, int b) { @@ -68,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); @@ -87,11 +84,11 @@ 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); byte *block1 = image_dup_block(dup1, tab_col, tab_row); @@ -106,7 +103,7 @@ 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; + return err <= ctx->error_threshold; case 1: col_step = -3; row_step = (3 << tab_col); @@ -146,14 +143,14 @@ 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; + 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; byte *block1 = img1->pixels; byte *block2 = img2->pixels; int col_step, row_step; @@ -203,23 +200,24 @@ 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; + 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)) + 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 @@ -245,11 +243,11 @@ image_dup_compare(struct image_dup *dup1, struct image_dup *dup2, uns flags) { 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)) @@ -272,11 +270,11 @@ image_dup_compare(struct image_dup *dup1, struct image_dup *dup2, uns flags) { 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)) diff --git a/images/dup-init.c b/images/dup-init.c index 0fddc40c..bcc392e9 100644 --- a/images/dup-init.c +++ b/images/dup-init.c @@ -1,7 +1,7 @@ /* * Image Library -- Duplicates Comparison * - * (c) 2006 Pavel Charvat + * (c) 2006--2007 Pavel Charvat * * This software may be freely distributed and used according to the terms * of the GNU Lesser General Public License. @@ -18,6 +18,22 @@ #include +void +image_dup_context_init(struct image_context *ic, struct image_dup_context *ctx) +{ + *ctx = (struct image_dup_context) { + .ic = ic, + .flags = IMAGE_DUP_TRANS_ID, + .ratio_threshold = 140, + .error_threshold = 100, + }; +} + +void +image_dup_context_cleanup(struct image_dup_context *ctx UNUSED) +{ +} + static uns image_dup_tab_limit = 8; static inline struct image * @@ -41,21 +57,44 @@ 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 size = sizeof(struct image_dup) + cols * rows * 3 + (12 << (tab_cols + tab_rows)) + 3 * CPU_STRUCT_ALIGN; + return ALIGN_TO(size, CPU_STRUCT_ALIGN); } uns -image_dup_init(struct image_context *ctx, struct image_dup *dup, struct image *img, struct mempool *pool) +image_dup_new(struct image_context *ctx, struct image *img, void *buffer) { DBG("image_dup_init()"); + ASSERT(!((uintptr_t)buffer & (CPU_STRUCT_ALIGN - 1))); + void *ptr = buffer; + + /* Allocate the structure */ + struct image_dup *dup = ptr; + ptr += ALIGN_TO(sizeof(*dup), CPU_STRUCT_ALIGN); + bzero(dup, sizeof(*dup)); ASSERT((img->flags & IMAGE_PIXEL_FORMAT) == COLOR_SPACE_RGB); - dup->image = img; + /* Clone image */ + if (!image_init_matrix(ctx, &dup->image, ptr, img->cols, img->rows, img->cols * 3, COLOR_SPACE_RGB)) + return 0; + uns size = img->rows * img->cols * 3; + ptr += ALIGN_TO(size, CPU_STRUCT_ALIGN); + byte *s = img->pixels; + byte *d = dup->image.pixels; + for (uns row = img->rows; row--; ) + { + memcpy(d, s, img->row_pixels_size); + d += dup->image.row_size; + s += img->row_size; + } + 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; + dup->tab_pixels = ptr; + size = 12 << (dup->tab_cols + dup->tab_rows); + ptr += ALIGN_TO(size, CPU_STRUCT_ALIGN); /* Scale original image to right bottom block */ { @@ -101,5 +140,5 @@ image_dup_init(struct image_context *ctx, struct image_dup *dup, struct image *i } } - return 1; + return ptr - buffer; } diff --git a/images/duplicates.h b/images/duplicates.h index dd07b763..fda8953f 100644 --- a/images/duplicates.h +++ b/images/duplicates.h @@ -1,8 +1,29 @@ -#ifndef _IMAGES_DUP_CMP_H -#define _IMAGES_DUP_CMP_H +#ifndef _IMAGES_DUPLICATES_H +#define _IMAGES_DUPLICATES_H + +enum image_dup_flags { + IMAGE_DUP_TRANS_ID = 0x0001, + IMAGE_DUP_FLIP_X = 0x0002, + IMAGE_DUP_FLIP_Y = 0x0004, + IMAGE_DUP_ROT_180 = 0x0008, + IMAGE_DUP_FLIP_BACK = 0x0010, + IMAGE_DUP_ROT_CCW = 0x0020, + IMAGE_DUP_ROT_CW = 0x0040, + IMAGE_DUP_FLIP_SLASH = 0x0080, + IMAGE_DUP_TRANS_ALL = 0x00ff, + IMAGE_DUP_SCALE = 0x0100, + IMAGE_DUP_WANT_ALL = 0x0200, +}; + +struct image_dup_context { + struct image_context *ic; + uns flags; + uns ratio_threshold; + uns error_threshold; +}; struct image_dup { - struct image *image; + struct image image; byte *tab_pixels; u32 tab_cols; u32 tab_rows; @@ -10,26 +31,16 @@ struct image_dup { u32 tab_size; }; -#define IMAGE_DUP_TRANS_ID 0x01 -#define IMAGE_DUP_FLIP_X 0x02 -#define IMAGE_DUP_FLIP_Y 0x04 -#define IMAGE_DUP_ROT_180 0x08 -#define IMAGE_DUP_FLIP_BACK 0x10 -#define IMAGE_DUP_ROT_CCW 0x20 -#define IMAGE_DUP_ROT_CW 0x40 -#define IMAGE_DUP_FLIP_SLASH 0x80 -#define IMAGE_DUP_TRANS_ALL 0xff -#define IMAGE_DUP_SCALE 0x100 -#define IMAGE_DUP_WANT_ALL 0x200 - /* dup-init.c */ -uns image_dup_init(struct image_context *ctx, struct image_dup *dup, struct image *image, struct mempool *pool); +void image_dup_context_init(struct image_context *ic, struct image_dup_context *ctx); +void image_dup_context_cleanup(struct image_dup_context *ctx); uns image_dup_estimate_size(uns cols, uns rows); +uns image_dup_new(struct image_context *ctx, struct image *image, void *buffer); /* dup-cmp.c */ -uns image_dup_compare(struct image_dup *dup1, struct image_dup *dup2, uns flags); +uns image_dup_compare(struct image_dup_context *ctx, struct image_dup *dup1, struct image_dup *dup2); /* internals */ diff --git a/images/image-dup-test.c b/images/image-dup-test.c index ef1e044d..048b53f3 100644 --- a/images/image-dup-test.c +++ b/images/image-dup-test.c @@ -110,8 +110,10 @@ main(int argc, char **argv) #define TRY(x) do{ if (!(x)) exit(1); }while(0) MSG("Initializing image library"); struct image_context ctx; + struct image_dup_context idc; struct image_io io; image_context_init(&ctx); + image_dup_context_init(&ctx, &idc); struct image *img1, *img2; @@ -146,18 +148,26 @@ main(int argc, char **argv) image_io_cleanup(&io); MSG("Image size=%ux%u", img2->cols, img2->rows); - struct image_dup dup1, dup2; + struct image_dup *dup1, *dup2; struct mempool *pool = mp_new(1 << 18); MSG("Creating internal structures"); - TRY(image_dup_init(&ctx, &dup1, img1, pool)); - TRY(image_dup_init(&ctx, &dup2, img2, pool)); - - MSG("Similarity bitmap %02x", image_dup_compare(&dup1, &dup2, transformations | IMAGE_DUP_SCALE | IMAGE_DUP_WANT_ALL)); + dup1 = mp_start(pool, image_dup_estimate_size(img1->cols, img1->rows)); + uns size = image_dup_new(&ctx, img1, dup1); + TRY(size); + mp_end(pool, (void *)dup1 + size); + dup2 = mp_start(pool, image_dup_estimate_size(img2->cols, img2->rows)); + size = image_dup_new(&ctx, img2, dup2); + TRY(size); + mp_end(pool, (void *)dup2 + size); + + idc.flags = transformations | IMAGE_DUP_SCALE | IMAGE_DUP_WANT_ALL; + MSG("Similarity bitmap %02x", image_dup_compare(&idc, dup1, dup2)); mp_delete(pool); image_destroy(img1); image_destroy(img2); + image_dup_context_cleanup(&idc); image_context_cleanup(&ctx); MSG("Done."); return 0; -- 2.39.5