From 44088b65c56a3051f4e31b2369927ff30c32d983 Mon Sep 17 00:00:00 2001 From: Pavel Charvat Date: Mon, 7 Aug 2006 01:08:28 +0200 Subject: [PATCH] sources backup... changed: - added thumbnail's fastbuf to analyser iface... it should be better to compute the signature directly in gather/format/image.c instead of gatherer's analyser (to save one image decompression and hide compression errors when possible), but we still need analyser in the scanner - cards contain base224-encoded signatures to save some space - unfinished algorithm for computing and comparing signatures - some bugfixes - and more ... :-) --- images/Makefile | 14 +- images/image-dup-test.c | 2 +- images/image-obj.c | 518 ---------------------------- images/image-obj.h | 53 --- images/image-sig.c | 137 -------- images/image-sim-test.c | 167 +++++++++ images/object.c | 108 ++++++ images/object.h | 26 ++ images/sig-cmp.c | 111 ++++++ images/sig-dump.c | 52 +++ images/sig-init.c | 386 +++++++++++++++++++++ images/{image-sig.h => signature.h} | 66 ++-- 12 files changed, 902 insertions(+), 738 deletions(-) delete mode 100644 images/image-obj.c delete mode 100644 images/image-obj.h delete mode 100644 images/image-sig.c create mode 100644 images/image-sim-test.c create mode 100644 images/object.c create mode 100644 images/object.h create mode 100644 images/sig-cmp.c create mode 100644 images/sig-dump.c create mode 100644 images/sig-init.c rename images/{image-sig.h => signature.h} (54%) diff --git a/images/Makefile b/images/Makefile index 692a89c8..5c60744b 100644 --- a/images/Makefile +++ b/images/Makefile @@ -2,11 +2,11 @@ DIRS+=images -PROGS+=$(addprefix $(o)/images/,image-tool image-dup-test) +PROGS+=$(addprefix $(o)/images/,image-tool image-dup-test image-sim-test) -LIBIMAGES_MODS=image scale color alpha io-main dup-cmp -LIBIMAGES=$(o)/images/libimages.$(LS) -LIBIMAGES_LIBS= +LIBIMAGES_MODS=image scale color alpha io-main dup-cmp sig-dump sig-init sig-cmp object + +LIBIMAGES_LIBS=-lm ifdef CONFIG_IMAGES_LIBJPEG LIBIMAGES_MODS+=io-libjpeg @@ -45,6 +45,9 @@ $(o)/images/image-tool: LIBS+=$(LIBIMAGES_LIBS) $(o)/images/image-dup-test: $(o)/images/image-dup-test.o $(LIBIMAGES) $(LIBUCW) $(o)/images/image-dup-test: LIBS+=$(LIBIMAGES_LIBS) +$(o)/images/image-sim-test: $(o)/images/image-sim-test.o $(LIBIMAGES) $(LIBUCW) +$(o)/images/image-sim-test: LIBS+=$(LIBIMAGES_LIBS) + TESTS+=$(o)/images/image-test.test $(o)/images/image-test: $(o)/images/image-test.o $(LIBIMAGES) $(LIBUCW) $(o)/images/image-test: LIBS+=$(LIBIMAGES_LIBS) @@ -58,9 +61,6 @@ TESTS+=$(o)/images/color.test $(o)/images/color-t: LIBS+=-lm $(o)/images/color.test: $(o)/images/color-t -#$(o)/images/image-test: $(o)/images/image-test.o $(LIBIMAGES) $(LIBUCW) -#$(o)/images/image-test: LIBS+=$(LIBIMAGES_LIBS) - #$(o)/images/image-idx: $(o)/images/image-idx.o $(o)/images/image-obj.o $(o)/images/dup-cmp.o $(o)/indexer/iconfig.o $(o)/images/image-sig.o $(o)/images/kd-tree.o $(o)/images/color.o $(o)/images/image-io.o $(LIBSH) $(LIBLANG) $(LIBCHARSET) #$(o)/images/image-idx: LIBS+=-lGraphicsMagick -ljpeg -lpng diff --git a/images/image-dup-test.c b/images/image-dup-test.c index 488ccfda..e0d0558c 100644 --- a/images/image-dup-test.c +++ b/images/image-dup-test.c @@ -22,7 +22,7 @@ static void NONRET usage(void) { fputs("\ -Usage: image-tool [options] image1 image2 \n\ +Usage: image-dup-test [options] image1 image2 \n\ \n\ -q --quiet no progress messages\n\ -f --format-1 image1 format (jpeg, gif, png)\n\ diff --git a/images/image-obj.c b/images/image-obj.c deleted file mode 100644 index 58230487..00000000 --- a/images/image-obj.c +++ /dev/null @@ -1,518 +0,0 @@ -/* - * Image Library -- Image Cards Manipulations - * - * (c) 2006 Pavel Charvat - * - * This software may be freely distributed and used according to the terms - * of the GNU Lesser General Public License. - * - * FIXME: - * - improve thumbnail creation in gatherer... faster compression, - * only grayscale/RGB colorspaces and maybe fixed headers (abbreviated datastreams in libjpeg) - * - hook memory allocation managers, get rid of multiple initializations - * - supply background color to transparent PNG images - * - optimize decompression parameters - * - create interface for thumbnail compression (for gatherer) and reading (MUX) - * - benchmatk libraries - */ - -#undef LOCAL_DEBUG - -#include "sherlock/sherlock.h" -#include "lib/base224.h" -#include "lib/mempool.h" -#include "sherlock/object.h" -#include "images/images.h" -#include "images/image-obj.h" - -#include -#include - -/* Selection of libraries to use */ -#define USE_LIBPNG -#define USE_LIBJPEG -#define USE_MAGICK - -#if defined(USE_LIBPNG) && defined(USE_LIBJPEG) -#undef USE_MAGICK -#endif - - -/********************************* LIBPNG Library ****************************************/ - -#ifdef USE_LIBPNG - -#include -#include - -static struct mempool *libpng_pool; -static byte *libpng_buf; -static uns libpng_len; - -static png_voidp -libpng_malloc(png_structp png_ptr UNUSED, png_size_t size) -{ - DBG("libpng_malloc(): size=%d", (uns)size); - return mp_alloc(libpng_pool, size); -} - -static void -libpng_free(png_structp png_ptr UNUSED, png_voidp ptr UNUSED) -{ - DBG("libpng_free()"); -} - -static void NONRET -libpng_error(png_structp png_ptr, png_const_charp msg UNUSED) -{ - DBG("libpng_error(): msg=%s", (byte *)msg); - longjmp(png_jmpbuf(png_ptr), 1); -} - -static void -libpng_warning(png_structp png_ptr UNUSED, png_const_charp msg UNUSED) -{ - DBG("libpng_warning(): msg=%s", (byte *)msg); -} - -static void -libpng_read_data(png_structp png_ptr UNUSED, png_bytep data, png_size_t length) -{ - DBG("libpng_read_data(): len=%d", (uns)length); - if (unlikely(libpng_len < length)) - png_error(png_ptr, "Incomplete data"); - memcpy(data, libpng_buf, length); - libpng_buf += length; - libpng_len -= length; -} - -static inline void -libpng_decompress_thumbnails_init(void) -{ -} - -static inline void -libpng_decompress_thumbnails_done(void) -{ -} - -static int -libpng_decompress_thumbnail(struct image_obj *imo) -{ - /* create libpng read structure */ - DBG("Creating libpng read structure"); - libpng_pool = imo->pool; - libpng_buf = imo->thumb_data; - libpng_len = imo->thumb_size; - png_structp png_ptr = png_create_read_struct_2(PNG_LIBPNG_VER_STRING, - NULL, libpng_error, libpng_warning, - NULL, libpng_malloc, libpng_free); - if (unlikely(!png_ptr)) - return 0; - png_infop info_ptr = png_create_info_struct(png_ptr); - if (unlikely(!info_ptr)) - { - png_destroy_read_struct(&png_ptr, NULL, NULL); - return 0; - } - png_infop end_ptr = png_create_info_struct(png_ptr); - if (unlikely(!end_ptr)) - { - png_destroy_read_struct(&png_ptr, &info_ptr, NULL); - return 0; - } - if (setjmp(png_jmpbuf(png_ptr))) - { - DBG("Libpng failed to read the image, longjump saved us"); - png_destroy_read_struct(&png_ptr, &info_ptr, &end_ptr); - return 0; - } - png_set_read_fn(png_ptr, NULL, libpng_read_data); - - /* Read image info */ - DBG("Reading image info"); - png_read_info(png_ptr, info_ptr); - png_uint_32 width, height; - int bit_depth, color_type; - png_get_IHDR(png_ptr, info_ptr, &width, &height, &bit_depth, &color_type, NULL, NULL, NULL); - ASSERT(width == imo->thumb.width && height == imo->thumb.height); - - /* Apply transformations */ - imo->thumb.flags = 0; - if (bit_depth == 16) - png_set_strip_16(png_ptr); - switch (color_type) - { - case PNG_COLOR_TYPE_PALETTE: - png_set_palette_to_rgb(png_ptr); - png_set_strip_alpha(png_ptr); - break; - case PNG_COLOR_TYPE_GRAY: - imo->thumb.flags |= IMAGE_GRAYSCALE; - png_set_gray_to_rgb(png_ptr); - break; - case PNG_COLOR_TYPE_GRAY_ALPHA: - imo->thumb.flags |= IMAGE_GRAYSCALE; - png_set_gray_to_rgb(png_ptr); - png_set_strip_alpha(png_ptr); - break; - case PNG_COLOR_TYPE_RGB: - break; - case PNG_COLOR_TYPE_RGB_ALPHA: - png_set_strip_alpha(png_ptr); - break; - default: - ASSERT(0); - } - png_read_update_info(png_ptr, info_ptr); - ASSERT(png_get_channels(png_ptr, info_ptr) == 3); - - /* Read image data */ - DBG("Reading image data"); - byte *pixels = imo->thumb.pixels = mp_alloc(imo->pool, imo->thumb.size = width * height * 3); - png_bytep rows[height]; - for (uns i = 0; i < height; i++, pixels += width * 3) - rows[i] = (png_bytep)pixels; - png_read_image(png_ptr, rows); - png_read_end(png_ptr, end_ptr); - - /* Destroy libpng read structure */ - png_destroy_read_struct(&png_ptr, &info_ptr, &end_ptr); - return 1; -} - -#endif /* USE_LIBPNG */ - - - -/******************************* LIBJPEG Library *************************************/ - -#ifdef USE_LIBJPEG - -#include -#include - -struct libjpeg_err { - struct jpeg_error_mgr pub; - jmp_buf setjmp_buf; -}; - -static void NONRET -libjpeg_error_exit(j_common_ptr cinfo) -{ - DBG("libjpeg_error_exit()"); - longjmp(((struct libjpeg_err *)(cinfo)->err)->setjmp_buf, 1); -} - -static void -libjpeg_emit_message(j_common_ptr cinfo UNUSED, int msg_level UNUSED) -{ - DBG("libjpeg_emit_message(): level=%d", msg_level); - /* if (unlikely(msg_level == -1)) - longjmp(((struct libjpeg_err *)(cinfo)->err)->setjmp_buf, 1); */ -} - -static void -libjpeg_init_source(j_decompress_ptr cinfo UNUSED) -{ - DBG("libjpeg_init_source()"); -} - -static boolean NONRET -libjpeg_fill_input_buffer(j_decompress_ptr cinfo) -{ - DBG("libjpeg_fill_input_buffer()"); - longjmp(((struct libjpeg_err *)(cinfo)->err)->setjmp_buf, 1); -} - -static void -libjpeg_skip_input_data(j_decompress_ptr cinfo, long num_bytes) -{ - DBG("libjpeg_skip_input_data(): len=%d", (int)num_bytes); - if (num_bytes > 0) - { - cinfo->src->next_input_byte += num_bytes; - cinfo->src->bytes_in_buffer -= num_bytes; - } -} - -static inline void -libjpeg_decompress_thumbnails_init(void) -{ -} - -static inline void -libjpeg_decompress_thumbnails_done(void) -{ -} - -static int -libjpeg_decompress_thumbnail(struct image_obj *imo) -{ - /* Create libjpeg read structure */ - DBG("Creating libjpeg read structure"); - struct jpeg_decompress_struct cinfo; - struct libjpeg_err err; - cinfo.err = jpeg_std_error(&err.pub); - err.pub.error_exit = libjpeg_error_exit; - err.pub.emit_message = libjpeg_emit_message; - if (setjmp(err.setjmp_buf)) - { - DBG("Libjpeg failed to read the image, longjump saved us"); - jpeg_destroy_decompress(&cinfo); - return 0; - } - jpeg_create_decompress(&cinfo); - - /* Initialize source manager */ - struct jpeg_source_mgr src; - cinfo.src = &src; - src.next_input_byte = imo->thumb_data; - src.bytes_in_buffer = imo->thumb_size; - src.init_source = libjpeg_init_source; - src.fill_input_buffer = libjpeg_fill_input_buffer; - src.skip_input_data = libjpeg_skip_input_data; - src.resync_to_restart = jpeg_resync_to_restart; - src.term_source = libjpeg_init_source; - - /* Read JPEG header and setup decompression options */ - DBG("Reading image header"); - jpeg_read_header(&cinfo, TRUE); - imo->thumb.flags = 0; - if (cinfo.out_color_space == JCS_GRAYSCALE) - imo->thumb.flags |= IMAGE_GRAYSCALE; - else - cinfo.out_color_space = JCS_RGB; - - /* Decompress the image */ - DBG("Reading image data"); - jpeg_start_decompress(&cinfo); - ASSERT(imo->thumb.width == cinfo.output_width && imo->thumb.height == cinfo.output_height); - ASSERT(sizeof(JSAMPLE) == 1); - byte *pixels = imo->thumb.pixels = mp_alloc(imo->pool, imo->thumb.size = cinfo.output_width * cinfo.output_height * 3); - if (cinfo.out_color_space == JCS_RGB) - { /* Read RGB pixels */ - uns size = cinfo.output_width * 3; - while (cinfo.output_scanline < cinfo.output_height) - { - jpeg_read_scanlines(&cinfo, (JSAMPLE **)&pixels, 1); - pixels += size; - } - } - else - { /* Read grayscale pixels */ - JSAMPLE buf[cinfo.output_width], *buf_end = buf + cinfo.output_width; - while (cinfo.output_scanline < cinfo.output_height) - { - JSAMPLE *p = buf; - jpeg_read_scanlines(&cinfo, &p, 1); - for (; p != buf_end; p++) - { - pixels[0] = pixels[1] = pixels[2] = p[0]; - pixels += 3; - } - } - } - jpeg_finish_decompress(&cinfo); - - /* Destroy libjpeg object and leave */ - jpeg_destroy_decompress(&cinfo); - return 1; -} - -#endif /* USE_LIBJPEG */ - - - -/****************************** GraphicsMagick Library ******************************/ - -#ifdef USE_MAGICK - -#include - -static ExceptionInfo magick_exception; -static QuantizeInfo magick_quantize; -static ImageInfo *magick_info; - -static void -magick_decompress_thumbnails_init(void) -{ - DBG("Initializing magick thumbnails decompression"); - InitializeMagick(NULL); - GetExceptionInfo(&magick_exception); - magick_info = CloneImageInfo(NULL); - magick_info->subrange = 1; - GetQuantizeInfo(&magick_quantize); - magick_quantize.colorspace = RGBColorspace; -} - -static void -magick_decompress_thumbnails_done(void) -{ - DBG("Finalizing magick thumbnails decompression"); - DestroyImageInfo(magick_info); - DestroyExceptionInfo(&magick_exception); - DestroyMagick(); -} - -static int -magick_decompress_thumbnail(struct image_obj *imo) -{ - DBG("Reading image data"); - Image *image = BlobToImage(magick_info, imo->thumb_data, imo->thumb_size, &magick_exception); - if (unlikely(!image)) - return 0; - ASSERT(image->columns == imo->thumb.width && image->rows == imo->thumb.height); - DBG("Quantizing image"); - QuantizeImage(&magick_quantize, image); - DBG("Converting pixels"); - PixelPacket *pixels = (PixelPacket *)AcquireImagePixels(image, 0, 0, image->columns, image->rows, &magick_exception); - ASSERT(pixels); - uns size = image->columns * image->rows; - byte *p = imo->thumb.pixels = mp_alloc(imo->pool, imo->thumb.size = size * 3); - for (uns i = 0; i < size; i++) - { - p[0] = pixels->red >> (QuantumDepth - 8); - p[1] = pixels->green >> (QuantumDepth - 8); - p[2] = pixels->blue >> (QuantumDepth - 8); - p += 3; - pixels++; - } - DestroyImage(image); - return 1; -} - -#endif /* USE_MAGICK */ - - - -/*************************************************************************************/ - -static int -extract_image_info(struct image_obj *imo) -{ - DBG("Parsing image info attribute"); - ASSERT(!(imo->flags & IMAGE_OBJ_VALID_INFO)); - imo->flags |= IMAGE_OBJ_VALID_INFO; - byte *info = obj_find_aval(imo->obj, 'G'); - if (!info) - { - DBG("Attribute G not found"); - return 0; - } - uns colors; - byte color_space[MAX_ATTR_SIZE], thumb_format[MAX_ATTR_SIZE]; - UNUSED uns cnt = sscanf(info, "%d%d%s%d%d%d%s", &imo->width, &imo->height, color_space, &colors, &imo->thumb.width, &imo->thumb.height, thumb_format); - ASSERT(cnt == 7); - switch (*thumb_format) - { - case 'j': - imo->thumb_format = IMAGE_OBJ_FORMAT_JPEG; - break; - case 'p': - imo->thumb_format = IMAGE_OBJ_FORMAT_PNG; - break; - default: - ASSERT(0); - } - return 1; -} - -static int -extract_thumb_data(struct image_obj *imo) -{ - DBG("Extracting thumbnail data"); - ASSERT(!(imo->flags & IMAGE_OBJ_VALID_DATA) && - (imo->flags & IMAGE_OBJ_VALID_INFO)); - imo->flags |= IMAGE_OBJ_VALID_DATA; - struct oattr *attr = obj_find_attr(imo->obj, 'N'); - if (!attr) - { - DBG("There is no thumbnail attribute N"); - return 0; - } - uns count = 0; - for (struct oattr *a = attr; a; a = a->same) - count++; - byte b224[count * MAX_ATTR_SIZE], *b = b224; - for (struct oattr *a = attr; a; a = a->same) - for (byte *s = a->val; *s; ) - *b++ = *s++; - ASSERT(b != b224); - uns size = b - b224; - imo->thumb_data = mp_alloc(imo->pool, size); - imo->thumb_size = base224_decode(imo->thumb_data, b224, size); - DBG("Thumbnail data size is %d", imo->thumb_size); - return 1; -} - -static int -extract_thumb_image(struct image_obj *imo) -{ - DBG("Decompressing thumbnail image"); - ASSERT(!(imo->flags & IMAGE_OBJ_VALID_IMAGE) && - (imo->flags & IMAGE_OBJ_VALID_INFO) && - (imo->flags & IMAGE_OBJ_VALID_DATA)); - imo->flags |= IMAGE_OBJ_VALID_IMAGE; - switch (imo->thumb_format) - { - case IMAGE_OBJ_FORMAT_JPEG: -#if defined(USE_LIBJPEG) - return libjpeg_decompress_thumbnail(imo); -#elif defined(USE_MAGICK) - return magick_decompress_thumbnail(imo); -#else - DBG("JPEG not supported"); - return 0; -#endif - case IMAGE_OBJ_FORMAT_PNG: -#if defined(USE_LIBPNG) - return libpng_decompress_thumbnail(imo); -#elif defined(USE_MAGICK) - return magick_decompress_thumbnail(imo); -#else - DBG("PNG not supported"); - return 0; -#endif - default: - ASSERT(0); - } -} - -void -imo_decompress_thumbnails_init(void) -{ -#ifdef USE_LIBPNG - libpng_decompress_thumbnails_init(); -#endif -#ifdef USE_LIBJPEG - libjpeg_decompress_thumbnails_init(); -#endif -#ifdef USE_MAGICK - magick_decompress_thumbnails_init(); -#endif -} - -void -imo_decompress_thumbnails_done(void) -{ -#ifdef USE_MAGICK - magick_decompress_thumbnails_done(); -#endif -#ifdef USE_LIBJPEG - libjpeg_decompress_thumbnails_done(); -#endif -#ifdef USE_LIBPNG - libpng_decompress_thumbnails_done(); -#endif -} - -int -imo_decompress_thumbnail(struct image_obj *imo) -{ - return - extract_image_info(imo) && - extract_thumb_data(imo) && - extract_thumb_image(imo); -} - diff --git a/images/image-obj.h b/images/image-obj.h deleted file mode 100644 index 95976bc8..00000000 --- a/images/image-obj.h +++ /dev/null @@ -1,53 +0,0 @@ -/* - * Image Library -- Image Cards Manipulations - * - * (c) 2006 Pavel Charvat - * - * This software may be freely distributed and used according to the terms - * of the GNU Lesser General Public License. - */ - -#ifndef _IMAGES_IMAGE_OBJ_H -#define _IMAGES_IMAGE_OBJ_H - -#include "images/images.h" - -struct mempool; -struct odes; - -enum image_obj_format { - IMAGE_OBJ_FORMAT_JPEG, - IMAGE_OBJ_FORMAT_PNG -}; - -enum image_obj_flag { - IMAGE_OBJ_VALID_INFO = 0x1, - IMAGE_OBJ_VALID_DATA = 0x2, - IMAGE_OBJ_VALID_IMAGE = 0x4 -}; - -struct image_obj { - struct odes *obj; - struct mempool *pool; - uns flags; - uns width; - uns height; - uns thumb_format; - byte *thumb_data; - uns thumb_size; - struct image thumb; -}; - -static inline void -imo_init(struct image_obj *imo, struct mempool *pool, struct odes *obj) -{ - imo->obj = obj; - imo->pool = pool; - imo->flags = 0; -} - -void imo_decompress_thumbnails_init(void); -void imo_decompress_thumbnails_done(void); -int imo_decompress_thumbnail(struct image_obj *imo); - -#endif diff --git a/images/image-sig.c b/images/image-sig.c deleted file mode 100644 index cd07b8a3..00000000 --- a/images/image-sig.c +++ /dev/null @@ -1,137 +0,0 @@ -#undef LOCAL_DEBUG - -#include "sherlock/sherlock.h" -#include "lib/math.h" -#include "lib/fastbuf.h" -#include "images/images.h" -#include "images/image-obj.h" -#include "images/image-sig.h" -#include "images/color.h" - -#include - -struct block { - uns l, u, v; /* average Luv coefficients */ - uns lh, hl, hh; /* energies in Daubechies wavelet bands */ -}; - -int -compute_image_signature(struct image_data *image, struct image_signature *sig) -{ - uns width = image->width; - uns height = image->height; - - if (width < 4 || height < 4) - { - DBG("Image too small... %dx%d", width, height); - return 0; - } - - uns w = width >> 2; - uns h = height >> 2; - DBG("Computing signature for image %dx%d... %dx%d blocks", width, height, w, h); - uns blocks_count = w * h; - struct block *blocks = xmalloc(blocks_count * sizeof(struct block)), *block = blocks; /* FIXME: use mempool */ - - /* Every 4x4 block (FIXME: deal with smaller blocks near the edges) */ - byte *p = image->pixels; - for (uns block_y = 0; block_y < h; block_y++, p += 3 * ((width & 3) + width * 3)) - for (uns block_x = 0; block_x < w; block_x++, p -= 3 * (4 * width - 4), block++) - { - int t[16], s[16], *tp = t; - - /* Convert pixels to Luv color space and compute average coefficients - * FIXME: - * - could be MUCH faster with precomputed tables and integer arithmetic... - * I will propably use interpolation in 3-dim array */ - uns l_sum = 0; - uns u_sum = 0; - uns v_sum = 0; - for (uns y = 0; y < 4; y++, p += 3 * (width - 4)) - for (uns x = 0; x < 4; x++, p += 3) - { - byte luv[3]; - srgb_to_luv_pixel(luv, p); - l_sum += *tp++ = luv[0]; - u_sum += luv[1]; - v_sum += luv[2]; - } - - block->l = (l_sum >> 4); - block->u = (u_sum >> 4); - block->v = (v_sum >> 4); - - /* Apply Daubechies wavelet transformation - * FIXME: - * - MMX/SSE instructions or tables could be faster - * - maybe it would be better to compute Luv and wavelet separately because of processor cache or MMX/SSE - * - eliminate slow square roots - * - what about Haar transformation? */ - -#define DAUB_0 31651 /* (1 + sqrt 3) / (4 * sqrt 2) */ -#define DAUB_1 54822 /* (3 + sqrt 3) / (4 * sqrt 2) */ -#define DAUB_2 14689 /* (3 - sqrt 3) / (4 * sqrt 2) */ -#define DAUB_3 -8481 /* (1 - sqrt 3) / (4 * sqrt 2) */ - - /* ... to the rows */ - uns i; - for (i = 0; i < 16; i += 4) - { - s[i + 0] = (DAUB_0 * t[i + 2] + DAUB_1 * t[i + 3] + DAUB_2 * t[i + 0] + DAUB_3 * t[i + 1]) / 0x10000; - s[i + 1] = (DAUB_0 * t[i + 0] + DAUB_1 * t[i + 1] + DAUB_2 * t[i + 2] + DAUB_3 * t[i + 3]) / 0x10000; - s[i + 2] = (DAUB_3 * t[i + 2] - DAUB_2 * t[i + 3] + DAUB_1 * t[i + 0] - DAUB_0 * t[i + 1]) / 0x10000; - s[i + 3] = (DAUB_3 * t[i + 0] - DAUB_2 * t[i + 1] + DAUB_1 * t[i + 2] - DAUB_0 * t[i + 3]) / 0x10000; - } - - /* ... and to the columns... skip LL band */ - for (i = 0; i < 2; i++) - { - t[i + 8] = (DAUB_3 * s[i + 8] - DAUB_2 * s[i +12] + DAUB_1 * s[i + 0] - DAUB_0 * s[i + 4]) / 0x1000; - t[i +12] = (DAUB_3 * s[i + 0] - DAUB_2 * s[i + 4] + DAUB_1 * s[i + 8] - DAUB_0 * s[i +12]) / 0x1000; - } - for (; i < 4; i++) - { - t[i + 0] = (DAUB_0 * s[i + 8] + DAUB_1 * s[i +12] + DAUB_2 * s[i + 0] + DAUB_3 * s[i + 4]) / 0x1000; - t[i + 4] = (DAUB_0 * s[i + 0] + DAUB_1 * s[i + 4] + DAUB_2 * s[i + 8] + DAUB_3 * s[i +12]) / 0x1000; - t[i + 8] = (DAUB_3 * s[i + 8] - DAUB_2 * s[i +12] + DAUB_1 * s[i + 0] - DAUB_0 * s[i + 4]) / 0x1000; - t[i +12] = (DAUB_3 * s[i + 0] - DAUB_2 * s[i + 4] + DAUB_1 * s[i + 8] - DAUB_0 * s[i +12]) / 0x1000; - } - - /* Extract energies in LH, HL and HH bands */ - block->lh = CLAMP((int)(sqrt(t[8] * t[8] + t[9] * t[9] + t[12] * t[12] + t[13] * t[13]) / 16), 0, 255); - block->hl = CLAMP((int)(sqrt(t[2] * t[2] + t[3] * t[3] + t[6] * t[6] + t[7] * t[7]) / 16), 0, 255); - block->hh = CLAMP((int)(sqrt(t[10] * t[10] + t[11] * t[11] + t[14] * t[14] + t[15] * t[15]) / 16), 0, 255); - } - - /* FIXME: simple average is for testing pusposes only */ - uns l_sum = 0; - uns u_sum = 0; - uns v_sum = 0; - uns lh_sum = 0; - uns hl_sum = 0; - uns hh_sum = 0; - for (uns i = 0; i < blocks_count; i++) - { - l_sum += blocks[i].l; - u_sum += blocks[i].u; - v_sum += blocks[i].v; - lh_sum += blocks[i].lh; - hl_sum += blocks[i].hl; - hh_sum += blocks[i].hh; - } - - sig->vec.f[0] = l_sum / blocks_count; - sig->vec.f[1] = u_sum / blocks_count; - sig->vec.f[2] = v_sum / blocks_count; - sig->vec.f[3] = lh_sum / blocks_count; - sig->vec.f[4] = hl_sum / blocks_count; - sig->vec.f[5] = hh_sum / blocks_count; - - sig->len = 0; - - xfree(blocks); - - DBG("Resulting signature is (%s)", stk_print_image_vector(&sig->vec)); - return 1; -} - diff --git a/images/image-sim-test.c b/images/image-sim-test.c new file mode 100644 index 00000000..a9be56e9 --- /dev/null +++ b/images/image-sim-test.c @@ -0,0 +1,167 @@ +/* + * Image similarity testing + * + * (c) 2006 Pavel Charvat + * + * This software may be freely distributed and used according to the terms + * of the GNU General Public License. + */ + +#include "lib/lib.h" +#include "lib/getopt.h" +#include "lib/fastbuf.h" +#include "images/images.h" +#include "images/color.h" +#include "images/signature.h" +#include +#include +#include +#include +#include +#include +#include + +static void NONRET +usage(void) +{ + fputs("\ +Usage: image-sim-test [options] image1 image2 \n\ +\n\ +-q --quiet no progress messages\n\ +-f --format-1 image1 format (jpeg, gif, png)\n\ +-F --format-2 image2 format\n\ +-g --background background color (hexadecimal RRGGBB)\n\ +", stderr); + exit(1); +} + +static char *shortopts = "qf:F:g:t:" CF_SHORT_OPTS; +static struct option longopts[] = +{ + CF_LONG_OPTS + { "quiet", 0, 0, 'q' }, + { "format-1", 0, 0, 'f' }, + { "format-2", 0, 0, 'F' }, + { "background", 0, 0, 'g' }, + { NULL, 0, 0, 0 } +}; + +static uns verbose = 1; +static byte *file_name_1; +static byte *file_name_2; +static enum image_format format_1; +static enum image_format format_2; +static struct color background_color; + +#define MSG(x...) do{ if (verbose) log(L_INFO, ##x); }while(0) + +static void +dump_signature(struct image_signature *sig) +{ + byte buf[MAX(IMAGE_VECTOR_DUMP_MAX, IMAGE_REGION_DUMP_MAX)]; + image_vector_dump(buf, &sig->vec); + MSG("vector: %s", buf); + for (uns i = 0; i < sig->len; i++) + { + image_region_dump(buf, sig->reg + i); + MSG("region %u: %s", i, buf); + } +} + +int +main(int argc, char **argv) +{ + log_init(argv[0]); + int opt; + while ((opt = cf_getopt(argc, argv, shortopts, longopts, NULL)) >= 0) + switch (opt) + { + case 'q': + verbose = 0; + break; + case 'f': + if (!(format_1 = image_extension_to_format(optarg))) + usage(); + break; + case 'F': + if (!(format_2 = image_extension_to_format(optarg))) + usage(); + break; + case 'g': + { + if (strlen(optarg) != 6) + usage(); + errno = 0; + char *end; + long int v = strtol(optarg, &end, 16); + if (errno || *end || v < 0) + usage(); + color_make_rgb(&background_color, (v >> 16) & 255, (v >> 8) & 255, v & 255); + } + break; + default: + usage(); + } + + if (argc != optind + 2) + usage(); + file_name_1 = argv[optind++]; + file_name_2 = argv[optind]; + +#define TRY(x) do{ if (!(x)) die("Error: %s", it.err_msg); }while(0) + MSG("Initializing image library"); + srandom(time(NULL) ^ getpid()); + srgb_to_luv_init(); + struct image_thread it; + struct image_io io; + image_thread_init(&it); + + struct image *img1, *img2; + + image_io_init(&it, &io); + MSG("Reading %s", file_name_1); + io.fastbuf = bopen(file_name_1, O_RDONLY, 1 << 18); + io.format = format_1 ? : image_file_name_to_format(file_name_1); + TRY(image_io_read_header(&io)); + io.flags = COLOR_SPACE_RGB | IMAGE_IO_USE_BACKGROUND; + if (background_color.color_space) + io.background_color = background_color; + else if (!io.background_color.color_space) + io.background_color = color_black; + TRY(image_io_read_data(&io, 1)); + bclose(io.fastbuf); + img1 = io.image; + MSG("Image size=%ux%u", img1->cols, img1->rows); + + image_io_reset(&io); + MSG("Reading %s", file_name_2); + io.fastbuf = bopen(file_name_2, O_RDONLY, 1 << 18); + io.format = format_2 ? : image_file_name_to_format(file_name_2); + TRY(image_io_read_header(&io)); + io.flags = COLOR_SPACE_RGB | IMAGE_IO_USE_BACKGROUND; + if (background_color.color_space) + io.background_color = background_color; + else if (!io.background_color.color_space) + io.background_color = color_black; + TRY(image_io_read_data(&io, 1)); + bclose(io.fastbuf); + img2 = io.image; + image_io_cleanup(&io); + MSG("Image size=%ux%u", img2->cols, img2->rows); + + MSG("Computing signatures"); + struct image_signature sig1, sig2; + TRY(compute_image_signature(&it, &sig1, img1)); + TRY(compute_image_signature(&it, &sig2, img2)); + dump_signature(&sig1); + dump_signature(&sig2); + + uns dist = image_signatures_dist(&sig1, &sig1); + MSG("dist=%.6f", dist / (double)(1 << IMAGE_SIG_DIST_SCALE)); + + image_destroy(img1); + image_destroy(img2); + image_thread_cleanup(&it); + MSG("Done."); + return 0; +} diff --git a/images/object.c b/images/object.c new file mode 100644 index 00000000..0d6a146f --- /dev/null +++ b/images/object.c @@ -0,0 +1,108 @@ +/* + * Image Library -- Image cards manipulations + * + * (c) 2006 Pavel Charvat + * + * This software may be freely distributed and used according to the terms + */ + +#define LOCAL_DEBUG + +#include "sherlock/sherlock.h" +#include "lib/base224.h" +#include "lib/mempool.h" +#include "lib/fastbuf.h" +#include "sherlock/object.h" +#include "images/images.h" +#include "images/object.h" +#include "images/color.h" +#include "images/signature.h" +#include +#include + +uns +get_image_obj_info(struct image_obj_info *ioi, struct odes *o) +{ + byte *v = obj_find_aval(o, 'G'); + if (!v) + { + DBG("Missing image info attribute"); + return 0; + } + byte color_space[MAX_ATTR_SIZE], thumb_format[MAX_ATTR_SIZE]; + UNUSED uns cnt = sscanf(v, "%d%d%s%d%d%d%s", &ioi->cols, &ioi->rows, color_space, + &ioi->colors, &ioi->thumb_cols, &ioi->thumb_rows, thumb_format); + ASSERT(cnt == 7); + ioi->thumb_format = (*thumb_format == 'p') ? IMAGE_FORMAT_PNG : IMAGE_FORMAT_JPEG; + DBG("Readed image info attribute: dim=%ux%u", ioi->cols, ioi->rows); + return 1; +} + +uns +get_image_obj_thumb(struct image_obj_info *ioi, struct odes *o, struct mempool *pool) +{ + struct oattr *a = obj_find_attr(o, 'N'); + if (!a) + { + DBG("Missing image thumbnail attribute"); + return 0; + } + uns count = 0; + for (struct oattr *b = a; b; b = b->same) + count++; + byte buf[count * MAX_ATTR_SIZE], *b = buf; + for (; a; a = a->same) + b += base224_decode(buf, a->val, strlen(a->val)); + ASSERT(b != buf); + ioi->thumb_data = mp_alloc(pool, ioi->thumb_size = b - buf); + memcpy(ioi->thumb_data, buf, ioi->thumb_size); + DBG("Readed thumbnail of size %u", ioi->thumb_size); + return 1; +} + +struct image * +read_image_obj_thumb(struct image_obj_info *ioi, struct fastbuf *fb, struct image_io *io, struct mempool *pool) +{ + struct fastbuf tmp_fb; + if (!fb) + fbbuf_init_read(fb = &tmp_fb, ioi->thumb_data, ioi->thumb_size, 0); + io->format = ioi->thumb_format; + io->fastbuf = fb; + if (!image_io_read_header(io)) + goto error; + io->pool = pool; + io->flags = COLOR_SPACE_RGB | IMAGE_IO_USE_BACKGROUND; + if (!io->background_color.color_space) + io->background_color = color_white; + struct image *img; + if (!(img = image_io_read_data(io, 0))) + goto error; + ASSERT(img->cols == ioi->thumb_cols && img->rows == ioi->thumb_rows); + DBG("Decompressed thumbnail: size=%ux%u", img->cols, img->rows); + return img; +error: + DBG("Failed to decompress thumbnail: %s", io->thread->err_msg); + return NULL; +} + +void +put_image_obj_signature(struct odes *o, struct image_signature *sig) +{ + /* signatures should be short enough to fit one attribute */ + ASSERT(MAX_ATTR_SIZE > BASE224_ENC_LENGTH(sizeof(struct image_vector) + 4 + sig->len * sizeof(struct image_region))); + byte buf[MAX_ATTR_SIZE], *b = buf; + memcpy(b, &sig->vec, sizeof(struct image_vector)); + b += sizeof(struct image_vector); + *b++ = sig->len; + *b++ = sig->df; + *(u16 *)b++ = sig->dh; + for (uns i = 0; i < sig->len; i++) + { + memcpy(b, sig->reg + i, sizeof(struct image_region)); + b += sizeof(struct image_region); + } + uns len = b - buf; + byte b224[MAX_ATTR_SIZE]; + b224[base224_encode(b224, buf, len)] = 0; + obj_set_attr(o, 'H', b224); +} diff --git a/images/object.h b/images/object.h new file mode 100644 index 00000000..58e789d6 --- /dev/null +++ b/images/object.h @@ -0,0 +1,26 @@ +#ifndef _IMAGES_OBJECT_H +#define _IMAGES_OBJECT_H + +#include "images/images.h" + +struct image_obj_info { + uns cols; + uns rows; + uns colors; + enum image_format thumb_format; + uns thumb_cols; + uns thumb_rows; + uns thumb_size; + byte *thumb_data; +}; + +struct odes; +struct mempool; +struct image_signature; + +uns get_image_obj_info(struct image_obj_info *ioi, struct odes *o); +uns get_image_obj_thumb(struct image_obj_info *ioi, struct odes *o, struct mempool *pool); +struct image *read_image_obj_thumb(struct image_obj_info *ioi, struct fastbuf *fb, struct image_io *io, struct mempool *pool); +void put_image_obj_signature(struct odes *o, struct image_signature *sig); + +#endif diff --git a/images/sig-cmp.c b/images/sig-cmp.c new file mode 100644 index 00000000..d5d3fb71 --- /dev/null +++ b/images/sig-cmp.c @@ -0,0 +1,111 @@ +/* + * Image Library -- Comparitions of image signatures + * + * (c) 2006 Pavel Charvat + * + * This software may be freely distributed and used according to the terms + * of the GNU Lesser General Public License. + */ + +#define LOCAL_DEBUG + +#include "lib/lib.h" +#include "lib/math.h" +#include "images/images.h" +#include "images/signature.h" +#include + +uns +image_signatures_dist(struct image_signature *sig1, struct image_signature *sig2) +{ + DBG("image_signatures_dist()"); + + uns cnt1 = sig1->len; + uns cnt2 = sig2->len; + struct image_region *reg1 = sig1->reg; + struct image_region *reg2 = sig2->reg; + uns mf[IMAGE_REG_MAX][IMAGE_REG_MAX], mh[IMAGE_REG_MAX][IMAGE_REG_MAX]; + uns lf[IMAGE_REG_MAX * 2], lh[IMAGE_REG_MAX * 2]; + uns df = sig1->df + sig2->df, dh = sig1->dh + sig2->dh; + + /* Compute distance matrix */ + for (uns i = 0; i < cnt1; i++) + for (uns j = i + 1; j < cnt2; j++) + { + uns d = 0; + for (uns k = 0; k < IMAGE_REG_F; k++) + { + int dif = reg1[i].f[k] - reg2[j].f[k]; + d += dif * dif; + } + mf[i][j] = d; + d = 0; + for (uns k = 0; k < IMAGE_REG_H; k++) + { + int dif = reg1[i].h[k] - reg2[j].h[k]; + d += dif * dif; + } + mh[i][j] = d; + } + + uns lfs = 0, lhs = 0; + for (uns i = 0; i < cnt1; i++) + { + uns f = mf[i][0], h = mh[i][0]; + for (uns j = 1; j < cnt2; j++) + { + f = MIN(f, mf[i][j]); + h = MIN(h, mh[i][j]); + } + lf[i] = (df * 0x10000) / (df + (int)sqrt(f)); + lh[i] = (dh * 0x10000) / (dh + (int)sqrt(h)); + lfs += lf[i] * (6 * reg1[i].wa + 2 * reg1[i].wb); + lhs += lh[i] * reg1[i].wa; + } + for (uns i = 0; i < cnt2; i++) + { + uns f = mf[0][i], h = mh[0][i]; + for (uns j = 1; j < cnt1; j++) + { + f = MIN(f, mf[j][i]); + h = MIN(h, mh[j][i]); + } + lf[i + cnt1] = (df * 0x10000) / (df + (int)sqrt(f)); + lh[i + cnt1] = (dh * 0x10000) / (dh + (int)sqrt(h)); + lfs += lf[i] * (6 * reg2[i].wa + 2 * reg2[i].wb); + lhs += lh[i] * reg2[i].wa; + } + + uns measure = lfs * 6 + lhs * 2 * 8; + +#ifdef LOCAL_DEBUG + /* Display similarity vectors */ + byte buf[2 * IMAGE_REG_MAX * 16 + 3], *b = buf; + for (uns i = 0; i < cnt1 + cnt2; i++) + { + if (i) + *b++ = ' '; + if (i == cnt1) + *b++ = '~', *b++ = ' '; + b += sprintf(b, "%.4f", (double)lf[i] / 0x10000); + } + *b = 0; + DBG("Lf=(%s)", buf); + b = buf; + for (uns i = 0; i < cnt1 + cnt2; i++) + { + if (i) + *b++ = ' '; + if (i == cnt1) + *b++ = '~', *b++ = ' '; + b += sprintf(b, "%.4f", (double)lh[i] / 0x10000); + } + *b = 0; + DBG("Lh=(%s)", buf); + DBG("Lfm=%.4f", lfs / (double)(1 << (3 + 8 + 16))); + DBG("Lhm=%.4f", lhs / (double)(1 << (8 + 16))); + DBG("measure=%.4f", measure / (double)(1 << (3 + 3 + 8 + 16))); +#endif + + return measure; +} diff --git a/images/sig-dump.c b/images/sig-dump.c new file mode 100644 index 00000000..a150f612 --- /dev/null +++ b/images/sig-dump.c @@ -0,0 +1,52 @@ +/* + * Image Library -- Dumping of image signatures + * + * (c) 2006 Pavel Charvat + * + * This software may be freely distributed and used according to the terms + * of the GNU Lesser General Public License. + */ + +#include "lib/lib.h" +#include "images/images.h" +#include "images/signature.h" +#include + +byte * +image_vector_dump(byte *buf, struct image_vector *vec) +{ + byte *p = buf; + *p++ = '('; + for (uns i = 0; i < IMAGE_VEC_F; i++) + { + if (i) + *p++ = ' '; + p += sprintf(p, "%u", vec->f[i]); + } + *p++ = ')'; + *p = 0; + return buf; +} + +byte * +image_region_dump(byte *buf, struct image_region *reg) +{ + byte *p = buf; + p += sprintf(p, "(txt="); + for (uns i = 0; i < IMAGE_REG_F; i++) + { + if (i) + *p++ = ' '; + p += sprintf(p, "%u", reg->f[i]); + } + p += sprintf(p, " shp="); + for (uns i = 0; i < IMAGE_REG_H; i++) + { + if (i) + *p++ = ' '; + p += sprintf(p, "%u", reg->h[i]); + } + p += sprintf(p, " wa=%u wb=%u)", reg->wa, reg->wb); + *p = 0; + return buf; +} diff --git a/images/sig-init.c b/images/sig-init.c new file mode 100644 index 00000000..17250e68 --- /dev/null +++ b/images/sig-init.c @@ -0,0 +1,386 @@ +/* + * Image Library -- Computation of image signatures + * + * (c) 2006 Pavel Charvat + * + * This software may be freely distributed and used according to the terms + * of the GNU Lesser General Public License. + */ + +#define LOCAL_DEBUG + +#include "sherlock/sherlock.h" +#include "lib/math.h" +#include "lib/fastbuf.h" +#include "images/images.h" +#include "images/color.h" +#include "images/signature.h" +#include + +static double image_sig_inertia_scale[3] = { 3, 1, 0.3 }; + +void +bget_image_signature(struct fastbuf *fb, struct image_signature *sig) +{ + breadb(fb, &sig->vec, sizeof(sig->vec)); + sig->len = bgetc(fb); + breadb(fb, sig->reg, sig->len * sizeof(*sig->reg)); +} + +void +bput_image_signature(struct fastbuf *fb, struct image_signature *sig) +{ + bwrite(fb, &sig->vec, sizeof(sig->vec)); + bputc(fb, sig->len); + bwrite(fb, sig->reg, sig->len * sizeof(*sig->reg)); +} + +struct block { + u32 l, u, v; /* average Luv coefficients */ + u32 lh, hl, hh; /* energies in Daubechies wavelet bands */ + u32 x, y; /* block position */ + struct block *next; +}; + +struct region { + u32 l, u, v; + u32 lh, hl, hh; + u32 sum_l, sum_u, sum_v; + u32 sum_lh, sum_hl, sum_hh; + u32 count; + u64 w_sum; + struct block *blocks; +}; + +static inline uns +dist(uns a, uns b) +{ + int d = a - b; + return d * d; +} + +/* FIXME: SLOW! */ +static uns +compute_k_means(struct block *blocks, uns blocks_count, struct region *regions, uns regions_count) +{ + ASSERT(regions_count <= blocks_count); + struct block *mean[IMAGE_REG_MAX], *b, *blocks_end = blocks + blocks_count; + struct region *r, *regions_end = regions + regions_count; + + /* Select means_count random blocks as initial regions pivots */ + if (regions_count <= blocks_count - regions_count) + { + for (b = blocks; b != blocks_end; b++) + b->next = NULL; + for (uns i = 0; i < regions_count; ) + { + uns j = random_max(blocks_count); + b = blocks + j; + if (!b->next) + b->next = mean[i++] = b; + } + } + else + { + uns j = blocks_count; + for (uns i = regions_count; i; j--) + if (random_max(j) <= i) + mean[--i] = blocks + j - 1; + } + r = regions; + for (uns i = 0; i < regions_count; i++, r++) + { + b = mean[i]; + r->l = b->l; + r->u = b->u; + r->v = b->v; + r->lh = b->lh; + r->hl = b->hl; + r->hh = b->hh; + } + + /* Convergation cycle */ + for (uns conv_i = 4; ; conv_i--) + { + for (r = regions; r != regions_end; r++) + { + r->sum_l = r->sum_u = r->sum_v = r->sum_lh = r->sum_hl = r->sum_hh = r->count = 0; + r->blocks = NULL; + } + + /* Find nearest regions and accumulate averages */ + for (b = blocks; b != blocks_end; b++) + { + uns best_d = ~0U; + struct region *best_r = NULL; + for (r = regions; r != regions_end; r++) + { + uns d = + dist(r->l, b->l) + + dist(r->u, b->u) + + dist(r->v, b->v) + + dist(r->lh, b->lh) + + dist(r->hl, b->hl) + + dist(r->hh, b->hh); + if (d < best_d) + { + best_d = d; + best_r = r; + } + } + best_r->sum_l += b->l; + best_r->sum_u += b->u; + best_r->sum_v += b->v; + best_r->sum_lh += b->lh; + best_r->sum_hl += b->hl; + best_r->sum_hh += b->hh; + best_r->count++; + b->next = best_r->blocks; + best_r->blocks = b; + } + + /* Compute new averages */ + for (r = regions; r != regions_end; r++) + if (r->count) + { + r->l = r->sum_l / r->count; + r->u = r->sum_u / r->count; + r->v = r->sum_v / r->count; + r->lh = r->sum_lh / r->count; + r->hl = r->sum_hl / r->count; + r->hh = r->sum_hh / r->count; + } + + if (!conv_i) + break; // FIXME: convergation criteria + } + + /* Remove empty regions */ + struct region *r2 = regions; + for (r = regions; r != regions_end; r++) + if (r->count) + *r2++ = *r; + return r2 - regions; +} + +int +compute_image_signature(struct image_thread *thread, struct image_signature *sig, struct image *image) +{ + uns cols = image->cols; + uns rows = image->rows; + + /* FIXME: deal with smaller images */ + if (cols < 4 || cols < 4) + { + image_thread_err_format(thread, IMAGE_ERR_INVALID_DIMENSIONS, "Image too small... %ux%u", cols, rows); + return 0; + } + + uns w = cols >> 2; + uns h = rows >> 2; + DBG("Computing signature for image %dx%d... %dx%d blocks", cols, rows, w, h); + uns blocks_count = w * h; + struct block *blocks = xmalloc(blocks_count * sizeof(struct block)), *block = blocks; /* FIXME: use mempool */ + + /* Every block of 4x4 pixels (FIXME: deal with smaller blocks near the edges) */ + byte *p = image->pixels; + for (uns block_y = 0; block_y < h; block_y++, p += 3 * ((cols & 3) + cols * 3)) + for (uns block_x = 0; block_x < w; block_x++, p -= 3 * (4 * cols - 4), block++) + { + block->x = block_x; + block->y = block_y; + + int t[16], s[16], *tp = t; + + /* Convert pixels to Luv color space and compute average coefficients + * FIXME: + * - could be MUCH faster with precomputed tables and integer arithmetic... + * I will propably use interpolation in 3-dim array */ + uns l_sum = 0; + uns u_sum = 0; + uns v_sum = 0; + for (uns y = 0; y < 4; y++, p += 3 * (cols - 4)) + for (uns x = 0; x < 4; x++, p += 3) + { + byte luv[3]; + srgb_to_luv_pixel(luv, p); + l_sum += *tp++ = luv[0]; + u_sum += luv[1]; + v_sum += luv[2]; + } + + block->l = (l_sum >> 4); + block->u = (u_sum >> 4); + block->v = (v_sum >> 4); + + /* Apply Daubechies wavelet transformation + * FIXME: + * - MMX/SSE instructions or tables could be faster + * - maybe it would be better to compute Luv and wavelet separately because of processor cache or MMX/SSE + * - eliminate slow square roots + * - what about Haar transformation? */ + +#define DAUB_0 31651 /* (1 + sqrt 3) / (4 * sqrt 2) */ +#define DAUB_1 54822 /* (3 + sqrt 3) / (4 * sqrt 2) */ +#define DAUB_2 14689 /* (3 - sqrt 3) / (4 * sqrt 2) */ +#define DAUB_3 -8481 /* (1 - sqrt 3) / (4 * sqrt 2) */ + + /* ... to the rows */ + uns i; + for (i = 0; i < 16; i += 4) + { + s[i + 0] = (DAUB_0 * t[i + 2] + DAUB_1 * t[i + 3] + DAUB_2 * t[i + 0] + DAUB_3 * t[i + 1]) / 0x10000; + s[i + 1] = (DAUB_0 * t[i + 0] + DAUB_1 * t[i + 1] + DAUB_2 * t[i + 2] + DAUB_3 * t[i + 3]) / 0x10000; + s[i + 2] = (DAUB_3 * t[i + 2] - DAUB_2 * t[i + 3] + DAUB_1 * t[i + 0] - DAUB_0 * t[i + 1]) / 0x10000; + s[i + 3] = (DAUB_3 * t[i + 0] - DAUB_2 * t[i + 1] + DAUB_1 * t[i + 2] - DAUB_0 * t[i + 3]) / 0x10000; + } + + /* ... and to the columns... skip LL band */ + for (i = 0; i < 2; i++) + { + t[i + 8] = (DAUB_3 * s[i + 8] - DAUB_2 * s[i +12] + DAUB_1 * s[i + 0] - DAUB_0 * s[i + 4]) / 0x1000; + t[i +12] = (DAUB_3 * s[i + 0] - DAUB_2 * s[i + 4] + DAUB_1 * s[i + 8] - DAUB_0 * s[i +12]) / 0x1000; + } + for (; i < 4; i++) + { + t[i + 0] = (DAUB_0 * s[i + 8] + DAUB_1 * s[i +12] + DAUB_2 * s[i + 0] + DAUB_3 * s[i + 4]) / 0x1000; + t[i + 4] = (DAUB_0 * s[i + 0] + DAUB_1 * s[i + 4] + DAUB_2 * s[i + 8] + DAUB_3 * s[i +12]) / 0x1000; + t[i + 8] = (DAUB_3 * s[i + 8] - DAUB_2 * s[i +12] + DAUB_1 * s[i + 0] - DAUB_0 * s[i + 4]) / 0x1000; + t[i +12] = (DAUB_3 * s[i + 0] - DAUB_2 * s[i + 4] + DAUB_1 * s[i + 8] - DAUB_0 * s[i +12]) / 0x1000; + } + + /* Extract energies in LH, HL and HH bands */ + block->lh = CLAMP((int)(sqrt(t[8] * t[8] + t[9] * t[9] + t[12] * t[12] + t[13] * t[13]) / 16), 0, 255); + block->hl = CLAMP((int)(sqrt(t[2] * t[2] + t[3] * t[3] + t[6] * t[6] + t[7] * t[7]) / 16), 0, 255); + block->hh = CLAMP((int)(sqrt(t[10] * t[10] + t[11] * t[11] + t[14] * t[14] + t[15] * t[15]) / 16), 0, 255); + } + + /* FIXME: simple average is for testing pusposes only */ + uns l_sum = 0; + uns u_sum = 0; + uns v_sum = 0; + uns lh_sum = 0; + uns hl_sum = 0; + uns hh_sum = 0; + for (uns i = 0; i < blocks_count; i++) + { + l_sum += blocks[i].l; + u_sum += blocks[i].u; + v_sum += blocks[i].v; + lh_sum += blocks[i].lh; + hl_sum += blocks[i].hl; + hh_sum += blocks[i].hh; + } + + sig->vec.f[0] = l_sum / blocks_count; + sig->vec.f[1] = u_sum / blocks_count; + sig->vec.f[2] = v_sum / blocks_count; + sig->vec.f[3] = lh_sum / blocks_count; + sig->vec.f[4] = hl_sum / blocks_count; + sig->vec.f[5] = hh_sum / blocks_count; + + /* Quantize blocks to image regions */ + struct region regions[IMAGE_REG_MAX]; + sig->len = compute_k_means(blocks, blocks_count, regions, MIN(blocks_count, IMAGE_REG_MAX)); + + /* For each region */ + u64 w_total = 0; + uns w_border = (MIN(w, h) + 3) / 4; + uns w_mul = 127 * 256 / w_border; + for (uns i = 0; i < sig->len; i++) + { + struct region *r = regions + i; + DBG("Processing region %u: count=%u", i, r->count); + ASSERT(r->count); + + /* Copy texture properties */ + sig->reg[i].f[0] = r->l; + sig->reg[i].f[1] = r->u; + sig->reg[i].f[2] = r->v; + sig->reg[i].f[3] = r->lh; + sig->reg[i].f[4] = r->hl; + sig->reg[i].f[5] = r->hh; + + /* Compute coordinates centroid and region weight */ + u64 x_avg = 0, y_avg = 0, w_sum = 0; + for (struct block *b = r->blocks; b; b = b->next) + { + x_avg += b->x; + y_avg += b->y; + uns d = b->x; + d = MIN(d, b->y); + d = MIN(d, w - b->x - 1); + d = MIN(d, h - b->y - 1); + if (d >= w_border) + w_sum += 128; + else + w_sum += 128 + (d - w_border) * w_mul / 256; + } + w_total += w_sum; + r->w_sum = w_sum; + x_avg /= r->count; + y_avg /= r->count; + DBG(" centroid=(%u %u)", (uns)x_avg, (uns)y_avg); + + /* Compute normalized inertia */ + u64 sum1 = 0, sum2 = 0, sum3 = 0; + for (struct block *b = r->blocks; b; b = b->next) + { + uns inc2 = dist(x_avg, b->x) + dist(y_avg, b->y); + uns inc1 = sqrt(inc2); + sum1 += inc1; + sum2 += inc2; + sum3 += inc1 * inc2; + } + sig->reg[i].h[0] = CLAMP(image_sig_inertia_scale[0] * sum1 * ((3 * M_PI * M_PI) / 2) * pow(r->count, -1.5), 0, 65535); + sig->reg[i].h[1] = CLAMP(image_sig_inertia_scale[1] * sum2 * ((4 * M_PI * M_PI * M_PI) / 2) / ((u64)r->count * r->count), 0, 65535); + sig->reg[i].h[2] = CLAMP(image_sig_inertia_scale[2] * sum3 * ((5 * M_PI * M_PI * M_PI * M_PI) / 2) * pow(r->count, -2.5), 0, 65535); + + } + + /* Compute average differences */ + u64 df = 0, dh = 0; + uns cnt = 0; + for (uns i = 0; i < sig->len; i++) + for (uns j = i + 1; j < sig->len; j++) + { + uns d = 0; + for (uns k = 0; k < IMAGE_REG_F; k++) + d += dist(sig->reg[i].f[k], sig->reg[j].f[k]); + df += sqrt(d); + d = 0; + for (uns k = 0; k < IMAGE_REG_H; k++) + d += dist(sig->reg[i].h[k], sig->reg[j].h[k]); + dh += sqrt(d); + cnt++; + } + sig->df = df / cnt; + sig->dh = dh / cnt; + DBG("Average regions difs: df=%u dh=%u", sig->df, sig->dh); + + /* Compute normalized weights */ + uns wa = 128, wb = 128; + for (uns i = sig->len; --i > 0; ) + { + struct region *r = regions + i; + wa -= sig->reg[i].wa = CLAMP(r->count * 128 / blocks_count, 1, (int)(wa - i)); + wb -= sig->reg[i].wb = CLAMP(r->w_sum * 128 / w_total, 1, (int)(wa - i)); + } + sig->reg[0].wa = wa; + sig->reg[0].wb = wb; + + /* Dump regions features */ +#ifdef LOCAL_DEBUG + for (uns i = 0; i < sig->len; i++) + { + byte buf[IMAGE_REGION_DUMP_MAX]; + image_region_dump(buf, sig->reg + i); + DBG("region %u: features=%s", i, buf); + } +#endif + + xfree(blocks); + + return 1; +} + diff --git a/images/image-sig.h b/images/signature.h similarity index 54% rename from images/image-sig.h rename to images/signature.h index 3532262a..2c2ab101 100644 --- a/images/image-sig.h +++ b/images/signature.h @@ -1,36 +1,59 @@ -#ifndef _IMAGES_IMAGE_SIG_H -#define _IMAGES_IMAGE_SIG_H +#ifndef _IMAGES_SIGNATURE_H +#define _IMAGES_SIGNATURE_H -#include "images/images.h" - -#define IMAGE_VEC_K 6 -#define IMAGE_REG_K 9 -#define IMAGE_REG_MAX 4 - -typedef byte image_feature_t; /* 8 or 16 bits precision */ +#define IMAGE_VEC_F 6 +#define IMAGE_REG_F IMAGE_VEC_F +#define IMAGE_REG_H 3 +#define IMAGE_REG_MAX 8 /* K-dimensional feature vector */ struct image_vector { - image_feature_t f[IMAGE_VEC_K]; -}; - -/* K-dimensional interval */ -struct image_bbox { - struct image_vector vec[2]; -}; + byte f[IMAGE_VEC_F]; /* texture features */ +} PACKED; /* Fetures for image regions */ struct image_region { - image_feature_t f[IMAGE_REG_K]; -}; + byte f[IMAGE_VEC_F]; /* texture features */ + u16 h[IMAGE_REG_H]; /* shape features */ + byte wa; /* normalized area percentage */ + byte wb; /* normalized weight */ +} PACKED; /* Image signature */ struct image_signature { - struct image_vector vec; /* Combination of all regions... simplier signature */ - image_feature_t len; /* Number of regions */ + struct image_vector vec; /* Combination of all regions... simple signature */ + byte len; /* Number of regions */ + byte df; /* average f dist */ + u16 dh; /* average h dist */ struct image_region reg[IMAGE_REG_MAX];/* Feature vector for every region */ }; +/* sig-dump.c */ + +#define IMAGE_VECTOR_DUMP_MAX (IMAGE_VEC_F * 16 + 1) +#define IMAGE_REGION_DUMP_MAX ((IMAGE_REG_F + IMAGE_REG_H) * 16 + 100) + +byte *image_vector_dump(byte *buf, struct image_vector *vec); +byte *image_region_dump(byte *buf, struct image_region *reg); + +/* sig-init.c */ + +void bget_image_signature(struct fastbuf *fb, struct image_signature *sig); +void bput_image_signature(struct fastbuf *fb, struct image_signature *sig); +int compute_image_signature(struct image_thread *thread, struct image_signature *sig, struct image *image); + +/* sig-cmp.c */ + +#define IMAGE_SIG_DIST_SCALE (3 + 3 + 8 + 16) + +uns image_signatures_dist(struct image_signature *sig1, struct image_signature *sig2); + +#if 0 +/* K-dimensional interval */ +struct image_bbox { + struct image_vector vec[2]; +}; + /* Similarity search tree... will be changed */ struct image_tree { uns count; /* Number of images in the tree */ @@ -58,8 +81,7 @@ struct image_leaf { #define stk_print_image_vector(v) ({ struct image_vector *_v = v; \ byte *_s = (byte *) alloca(IMAGE_VEC_K * 6), *_p = _s + sprintf(_s, "%d", _v->f[0]); \ for (uns _i = 1; _i < IMAGE_VEC_K; _i++) _p += sprintf(_p, " %d", _v->f[_i]); _s; }) - -int compute_image_signature(struct image *image, struct image_signature *sig); +#endif #endif -- 2.39.2