From 3cbca97fcc3bd2708329315fa60e535ba319b9d2 Mon Sep 17 00:00:00 2001 From: Pavel Charvat Date: Fri, 25 Aug 2006 16:12:43 +0200 Subject: [PATCH] - segmentations are displayed correctly in RGB - improved first phase of segmentation - decreased importance of L coefficient and wavelet energies in image signatures --- cf/images | 2 +- images/color.c | 32 ++++++++++++++ images/color.h | 2 + images/image-sim-test.c | 13 ++++-- images/sig-init.c | 17 ++++---- images/sig-seg.c | 93 ++++++++++++++++++++++++++++------------- 6 files changed, 116 insertions(+), 43 deletions(-) diff --git a/cf/images b/cf/images index de14847d..e6c64fd1 100644 --- a/cf/images +++ b/cf/images @@ -12,7 +12,7 @@ ImageSig { MinWidth 16 MinHeight 16 -PreQuantThresholds 9 9 25 25 100 100 400 400 1000 1000 1000 1000 4000 10000 10000 10000 +PreQuantThresholds 9 9 25 25 100 100 400 400 1000 1000 10000 10000 10000 40000 40000 PostQuantMinSteps 2 PostQuantMaxSteps 10 PostQuantThreshold 2 diff --git a/images/color.c b/images/color.c index 5f41e935..80f48294 100644 --- a/images/color.c +++ b/images/color.c @@ -84,6 +84,21 @@ srgb_to_xyz_slow(double xyz[3], double srgb[3]) xyz[2] = SRGB_XYZ_ZR * a[0] + SRGB_XYZ_ZG * a[1] + SRGB_XYZ_ZB * a[2]; } +/* XYZ to sRGB */ +void +xyz_to_srgb_slow(double srgb[3], double xyz[3]) +{ + double a[3]; + a[0] = 3.2406 * xyz[0] + -1.5372 * xyz[1] + -0.4986 * xyz[2]; + a[1] = -0.9689 * xyz[0] + 1.8758 * xyz[1] + 0.0415 * xyz[2]; + a[2] = 0.0557 * xyz[0] + -0.2040 * xyz[1] + 1.0570 * xyz[2]; + for (uns i = 0; i < 3; i++) + if (a[i] > 0.0031308) + srgb[i] = 1.055 * pow(a[i], 1 / 2.4) - 0.055; + else + srgb[i] = 12.92 * a[i]; +} + /* XYZ to CIE-Luv */ void xyz_to_luv_slow(double luv[3], double xyz[3]) @@ -105,6 +120,23 @@ xyz_to_luv_slow(double luv[3], double xyz[3]) } } +/* CIE-Luv to XYZ */ +void +luv_to_xyz_slow(double xyz[3], double luv[3]) +{ + double var_u = luv[1] / (13 * luv[0]) + (4 * REF_WHITE_X / (REF_WHITE_X + 15 * REF_WHITE_Y + 3 * REF_WHITE_Z)); + double var_v = luv[2] / (13 * luv[0]) + (9 * REF_WHITE_Y / (REF_WHITE_X + 15 * REF_WHITE_Y + 3 * REF_WHITE_Z)); + double var_y = (luv[0] + 16) / 116; + double pow_y = var_y * var_y * var_y; + if (pow_y > 0.008856) + var_y = pow_y; + else + var_y = (var_y - 16 / 116) / 7.787; + xyz[1] = var_y; + xyz[0] = -(9 * xyz[1] * var_u) / ((var_u - 4) * var_v - var_u * var_v); + xyz[2] = (9 * xyz[1] - 15 * var_v * xyz[1] - var_v * xyz[0]) / (3 * var_v); +} + /***************** OPTIMIZED SRGB -> LUV CONVERSION *********************/ diff --git a/images/color.h b/images/color.h index 8ec18e92..d8cee26b 100644 --- a/images/color.h +++ b/images/color.h @@ -55,7 +55,9 @@ void color_put_rgb(byte *dest, struct color *color); /* Exact slow conversion routines */ void srgb_to_xyz_slow(double dest[3], double src[3]); +void xyz_to_srgb_slow(double dest[3], double src[3]); void xyz_to_luv_slow(double dest[3], double src[3]); +void luv_to_xyz_slow(double dest[3], double src[3]); /* Reference white */ #define REF_WHITE_X 0.96422 diff --git a/images/image-sim-test.c b/images/image-sim-test.c index c58c9d08..d8347996 100644 --- a/images/image-sim-test.c +++ b/images/image-sim-test.c @@ -91,10 +91,15 @@ write_segmentation(struct image_sig_data *data, byte *fn) for (uns i = 0; i < data->regions_count; i++) { byte c[3]; - // FIXME: convert from Luv to RGB - c[0] = data->regions[i].a[0]; - c[1] = data->regions[i].a[1]; - c[2] = data->regions[i].a[2]; + double luv[3], xyz[3], srgb[3]; + luv[0] = data->regions[i].a[0] * (2 / 2.55); + luv[1] = ((int)data->regions[i].a[1] - 128) * (4 / 2.55); + luv[2] = ((int)data->regions[i].a[2] - 128) * (4 / 2.55); + luv_to_xyz_slow(xyz, luv); + xyz_to_srgb_slow(srgb, xyz); + c[0] = CLAMP(srgb[0] * 255, 0, 255); + c[1] = CLAMP(srgb[1] * 255, 0, 255); + c[2] = CLAMP(srgb[2] * 255, 0, 255); for (struct image_sig_block *block = data->regions[i].blocks; block; block = block->next) { uns x1 = block->x * 4; diff --git a/images/sig-init.c b/images/sig-init.c index 2c6ca2d4..13f21fce 100644 --- a/images/sig-init.c +++ b/images/sig-init.c @@ -66,7 +66,7 @@ image_sig_preprocess(struct image_sig_data *data) { byte luv[3]; srgb_to_luv_pixel(luv, p2); - l_sum += *tp++ = luv[0]; + l_sum += *tp++ = luv[0] / 2; u_sum += luv[1]; v_sum += luv[2]; } @@ -91,7 +91,7 @@ image_sig_preprocess(struct image_sig_data *data) { byte luv[3]; srgb_to_luv_pixel(luv, p3); - l_sum += *tp++ = luv[0]; + l_sum += *tp++ = luv[0] / 2; u_sum += luv[1]; v_sum += luv[2]; } @@ -137,15 +137,15 @@ image_sig_preprocess(struct image_sig_data *data) /* ... 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]) / 0x2000; - t[i +12] = (DAUB_3 * s[i + 0] - DAUB_2 * s[i + 4] + DAUB_1 * s[i + 8] - DAUB_0 * s[i +12]) / 0x2000; + t[i + 8] = (DAUB_3 * s[i + 8] - DAUB_2 * s[i +12] + DAUB_1 * s[i + 0] - DAUB_0 * s[i + 4]) / 0x4000; + t[i +12] = (DAUB_3 * s[i + 0] - DAUB_2 * s[i + 4] + DAUB_1 * s[i + 8] - DAUB_0 * s[i +12]) / 0x4000; } 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]) / 0x2000; - t[i + 4] = (DAUB_0 * s[i + 0] + DAUB_1 * s[i + 4] + DAUB_2 * s[i + 8] + DAUB_3 * s[i +12]) / 0x2000; - t[i + 8] = (DAUB_3 * s[i + 8] - DAUB_2 * s[i +12] + DAUB_1 * s[i + 0] - DAUB_0 * s[i + 4]) / 0x2000; - t[i +12] = (DAUB_3 * s[i + 0] - DAUB_2 * s[i + 4] + DAUB_1 * s[i + 8] - DAUB_0 * s[i +12]) / 0x2000; + t[i + 0] = (DAUB_0 * s[i + 8] + DAUB_1 * s[i +12] + DAUB_2 * s[i + 0] + DAUB_3 * s[i + 4]) / 0x4000; + t[i + 4] = (DAUB_0 * s[i + 0] + DAUB_1 * s[i + 4] + DAUB_2 * s[i + 8] + DAUB_3 * s[i +12]) / 0x4000; + t[i + 8] = (DAUB_3 * s[i + 8] - DAUB_2 * s[i +12] + DAUB_1 * s[i + 0] - DAUB_0 * s[i + 4]) / 0x4000; + t[i +12] = (DAUB_3 * s[i + 0] - DAUB_2 * s[i + 4] + DAUB_1 * s[i + 8] - DAUB_0 * s[i +12]) / 0x4000; } /* Extract energies in LH, HL and HH bands */ @@ -306,4 +306,5 @@ compute_image_signature(struct image_thread *thread, struct image_signature *sig image_sig_segmentation(&data); image_sig_finish(&data, sig); image_sig_cleanup(&data); + return 1; } diff --git a/images/sig-seg.c b/images/sig-seg.c index 94830573..7e6e09f5 100644 --- a/images/sig-seg.c +++ b/images/sig-seg.c @@ -7,7 +7,7 @@ * of the GNU Lesser General Public License. */ -#undef LOCAL_DEBUG +#define LOCAL_DEBUG #include "sherlock/sherlock.h" #include "lib/conf.h" @@ -26,8 +26,8 @@ dump_segmentation(struct image_sig_region *regions, uns regions_count) for (uns i = 0; i < regions_count; i++) for (struct image_sig_block *b = regions[i].blocks; b; b = b->next) { - cols = MAX(cols, b->x); - rows = MAX(rows, b->y); + cols = MAX(cols, b->x + 1); + rows = MAX(rows, b->y + 1); } uns size = (cols + 1) * rows; byte buf[size]; @@ -79,6 +79,7 @@ prequant_finish_region(struct image_sig_region *region) a += (u64)region->b[i] * region->b[i]; } region->e -= a / region->count; + DBG("Finished region %u", (uns)region->e / region->count); } } @@ -89,9 +90,9 @@ prequant_heap_cmp(struct image_sig_region *a, struct image_sig_region *b) } #define ASORT_PREFIX(x) prequant_##x -#define ASORT_KEY_TYPE u32 +#define ASORT_KEY_TYPE uns #define ASORT_ELT(i) val[i] -#define ASORT_EXTRA_ARGS , u32 *val +#define ASORT_EXTRA_ARGS , uns *val #include "lib/arraysort.h" static uns @@ -99,7 +100,7 @@ prequant(struct image_sig_block *blocks, uns blocks_count, struct image_sig_regi { DBG("Starting pre-quantization"); - uns regions_count, heap_count, axis, cov; + uns regions_count, heap_count, axis; struct image_sig_block *blocks_end = blocks + blocks_count, *block, *block2; struct image_sig_region *heap[IMAGE_REG_MAX + 1], *region, *region2; @@ -127,46 +128,78 @@ prequant(struct image_sig_block *blocks, uns blocks_count, struct image_sig_regi /* Select axis to split - the one with maximum covariance */ axis = 0; - cov = region->count * region->c[0] - region->b[0]; + u64 cov = (u64)region->count * region->c[0] - (u64)region->b[0] * region->b[0]; for (uns i = 1; i < 6; i++) { - uns j = region->count * region->c[i] - region->b[i]; + uns j = (u64)region->count * region->c[i] - (u64)region->b[i] * region->b[i]; if (j > cov) { axis = i; cov = j; } } - DBG("Splitting axis %u with covariance %u", axis, cov / region->count); + DBG("Splitting axis %u with average quadratic error %u", axis, (uns)(cov / (region->count * region->count))); /* Sort values on the split axis */ - u32 val[region->count]; - block = region->blocks; - for (uns i = 0; i < region->count; i++, block = block->next) - val[i] = block->v[axis]; - prequant_sort(region->count, val); - + uns val[256], cnt[256], cval; + if (region->count > 64) + { + bzero(cnt, sizeof(cnt)); + for (block = region->blocks; block; block = block->next) + cnt[block->v[axis]]++; + cval = 0; + for (uns i = 0; i < 256; i++) + if (cnt[i]) + { + val[cval] = i; + cnt[cval] = cnt[i]; + cval++; + } + } + else + { + block = region->blocks; + for (uns i = 0; i < region->count; i++, block = block->next) + val[i] = block->v[axis]; + prequant_sort(region->count, val); + cval = 1; + cnt[0] = 1; + for (uns i = 1; i < region->count; i++) + if (val[i] == val[cval - 1]) + cnt[cval - 1]++; + else + { + val[cval] = val[i]; + cnt[cval] = 1; + cval++; + } + } + /* Select split value - to minimize error */ - uns b1 = 0, c1 = 0, b2 = region->b[axis], c2 = region->c[axis]; - uns i = 0, j = region->count, best_v = 0; - u64 best_err = 0xffffffffffffffff; - while (i < region->count) + uns b1 = val[0] * cnt[0]; + uns c1 = isqr(val[0]) * cnt[0]; + uns b2 = region->b[axis] - b1; + uns c2 = region->c[axis] - c1; + uns i = cnt[0], j = region->count - cnt[0]; + u64 best_err = c1 - (u64)b1 * b1 / i + c2 - (u64)b2 * b2 / j; + uns split_val = val[0]; + for (uns k = 1; k < cval - 1; k++) { - u64 err = (u64)i * c1 - (u64)b1 * b1 + (u64)j * c2 - (u64)b2 * b2; + uns b0 = val[k] * cnt[k]; + uns c0 = isqr(val[k]) * cnt[k]; + b1 += b0; + b2 -= b0; + c1 += c0; + c2 -= c0; + i += cnt[k]; + j -= cnt[k]; + u64 err = (u64)c1 - (u64)b1 * b1 / i + (u64)c2 - (u64)b2 * b2 / j; if (err < best_err) { best_err = err; - best_v = val[i]; + split_val = val[k]; } - uns sqr = isqr(val[i]); - b1 += val[i]; - b2 -= val[i]; - c1 += sqr; - c2 -= sqr; - i++; - j--; } - uns split_val = best_v; DBG("split_val=%u best_err=%Lu b[axis]=%u c[axis]=%u", split_val, (long long)best_err, region->b[axis], region->c[axis]); /* Split region */ @@ -177,7 +210,7 @@ prequant(struct image_sig_block *blocks, uns blocks_count, struct image_sig_regi while (block) { block2 = block->next; - if (block->v[axis] < split_val) + if (block->v[axis] <= split_val) prequant_add_block(region, block); else prequant_add_block(region2, block); -- 2.39.5