summaryrefslogtreecommitdiffstats
path: root/src/3rdparty/autotrace/image-proc.c
diff options
context:
space:
mode:
Diffstat (limited to '')
-rw-r--r--src/3rdparty/autotrace/image-proc.c493
1 files changed, 493 insertions, 0 deletions
diff --git a/src/3rdparty/autotrace/image-proc.c b/src/3rdparty/autotrace/image-proc.c
new file mode 100644
index 0000000..7709175
--- /dev/null
+++ b/src/3rdparty/autotrace/image-proc.c
@@ -0,0 +1,493 @@
+/* image-proc.c: image processing routines */
+
+#ifdef HAVE_CONFIG_H
+#include "config.h"
+#endif /* Def: HAVE_CONFIG_H */
+
+#include <assert.h>
+#include <math.h>
+#include "xstd.h"
+#include "logreport.h"
+#include "image-proc.h"
+
+#define BLACK 0
+#define WHITE 0xff
+#ifndef M_SQRT2
+#define M_SQRT2 1.41421356237
+#endif
+
+/* Threshold for binarizing a monochrome image */
+#define GRAY_THRESHOLD 225
+
+/* RGB to grayscale */
+#define LUMINANCE(r, g, b) ((r) * 0.30 + (g) * 0.59 + (b) * 0.11 + 0.5)
+
+#if 0
+struct etyp {
+ int t00, t11, t01, t01s;
+};
+
+static gboolean get_edge(bitmap_type, int y, int x, struct etyp *t);
+static void check(int v1, int v2, int v3, struct etyp *t);
+#endif
+
+/* Allocate storage for a new distance map with the same dimensions
+ as BITMAP and initialize it so that pixels in BITMAP with value
+ TARGET_VALUE are at distance zero and all other pixels are at
+ distance infinity. Then compute the gray-weighted distance from
+ every non-target point to the nearest target point. */
+
+at_distance_map new_distance_map(at_bitmap * bitmap, unsigned char target_value, gboolean padded, at_exception_type * exp)
+{
+ signed x, y;
+ float d, min;
+ at_distance_map dist;
+ unsigned char *b = AT_BITMAP_BITS(bitmap);
+ unsigned w = AT_BITMAP_WIDTH(bitmap);
+ unsigned h = AT_BITMAP_HEIGHT(bitmap);
+ unsigned spp = AT_BITMAP_PLANES(bitmap);
+
+ dist.height = h;
+ dist.width = w;
+ XMALLOC(dist.d, h * sizeof(float *));
+ XMALLOC(dist.weight, h * sizeof(float *));
+ for (y = 0; y < (signed)h; y++) {
+ XCALLOC(dist.d[y], w * sizeof(float));
+ XMALLOC(dist.weight[y], w * sizeof(float));
+ }
+
+ if (spp == 3) {
+ for (y = 0; y < (signed)h; y++) {
+ for (x = 0; x < (signed)w; x++, b += spp) {
+ int gray;
+ float fgray;
+ gray = (int)LUMINANCE(b[0], b[1], b[2]);
+ dist.d[y][x] = (gray == target_value ? 0.0F : 1.0e10F);
+ fgray = gray * 0.0039215686F; /* = gray / 255.0F */
+ dist.weight[y][x] = 1.0F - fgray;
+/* dist.weight[y][x] = 1.0F - (fgray * fgray);*/
+/* dist.weight[y][x] = (fgray < 0.5F ? 1.0F - fgray : -2.0F * fgray * (fgray - 1.0F));*/
+ }
+ }
+ } else {
+ for (y = 0; y < (signed)h; y++) {
+ for (x = 0; x < (signed)w; x++, b += spp) {
+ int gray;
+ float fgray;
+ gray = b[0];
+ dist.d[y][x] = (gray == target_value ? 0.0F : 1.0e10F);
+ fgray = gray * 0.0039215686F; /* = gray / 255.0F */
+ dist.weight[y][x] = 1.0F - fgray;
+/* dist.weight[y][x] = 1.0F - (fgray * fgray);*/
+/* dist.weight[y][x] = (fgray < 0.5F ? 1.0F - fgray : -2.0F * fgray * (fgray - 1.0F)); */
+ }
+ }
+ }
+
+ /* If the image is padded then border points are all at most
+ one unit away from the nearest target point. */
+ if (padded) {
+ for (y = 0; y < (signed)h; y++) {
+ if (dist.d[y][0] > dist.weight[y][0])
+ dist.d[y][0] = dist.weight[y][0];
+ if (dist.d[y][w - 1] > dist.weight[y][w - 1])
+ dist.d[y][w - 1] = dist.weight[y][w - 1];
+ }
+ for (x = 0; x < (signed)w; x++) {
+ if (dist.d[0][x] > dist.weight[0][x])
+ dist.d[0][x] = dist.weight[0][x];
+ if (dist.d[h - 1][x] > dist.weight[h - 1][x])
+ dist.d[h - 1][x] = dist.weight[h - 1][x];
+ }
+ }
+
+ /* Scan the image from left to right, top to bottom.
+ Examine the already-visited neighbors of each point (those
+ situated above or to the left of it). Each neighbor knows
+ the distance to its nearest target point; add to this distance
+ the distance from the central point to the neighbor (either
+ sqrt(2) or one) multiplied by the central point's weight
+ (derived from its gray level). Replace the distance already
+ stored at the central point if the new distance is smaller. */
+ for (y = 1; y < (signed)h; y++) {
+ for (x = 1; x < (signed)w; x++) {
+ if (dist.d[y][x] == 0.0F)
+ continue;
+
+ min = dist.d[y][x];
+
+ /* upper-left neighbor */
+ d = dist.d[y - 1][x - 1] + (float)M_SQRT2 *dist.weight[y][x];
+ if (d < min)
+ min = dist.d[y][x] = d;
+
+ /* upper neighbor */
+ d = dist.d[y - 1][x] + dist.weight[y][x];
+ if (d < min)
+ min = dist.d[y][x] = d;
+
+ /* left neighbor */
+ d = dist.d[y][x - 1] + dist.weight[y][x];
+ if (d < min)
+ min = dist.d[y][x] = d;
+
+ /* upper-right neighbor (except at the last column) */
+ if (x + 1 < (signed)w) {
+ d = dist.d[y - 1][x + 1] + (float)M_SQRT2 *dist.weight[y][x];
+ if (d < min)
+ min = dist.d[y][x] = d;
+ }
+ }
+ }
+
+ /* Same as above, but now scanning right to left, bottom to top. */
+ for (y = h - 2; y >= 0; y--) {
+ for (x = w - 2; x >= 0; x--) {
+ min = dist.d[y][x];
+
+ /* lower-right neighbor */
+ d = dist.d[y + 1][x + 1] + (float)M_SQRT2 *dist.weight[y][x];
+ if (d < min)
+ min = dist.d[y][x] = d;
+
+ /* lower neighbor */
+ d = dist.d[y + 1][x] + dist.weight[y][x];
+ if (d < min)
+ min = dist.d[y][x] = d;
+
+ /* right neighbor */
+ d = dist.d[y][x + 1] + dist.weight[y][x];
+ if (d < min)
+ min = dist.d[y][x] = d;
+
+ /* lower-left neighbor (except at the first column) */
+ if (x - 1 >= 0) {
+ d = dist.d[y + 1][x - 1] + (float)M_SQRT2 *dist.weight[y][x];
+ if (d < min)
+ min = dist.d[y][x] = d;
+ }
+ }
+ }
+ return dist;
+}
+
+/* Free the dynamically-allocated storage associated with a distance map. */
+
+void free_distance_map(at_distance_map * dist)
+{
+ unsigned y, h;
+
+ if (!dist)
+ return;
+
+ h = dist->height;
+
+ if (dist->d != NULL) {
+ for (y = 0; y < h; y++)
+ free((gpointer *) dist->d[y]);
+ free((gpointer *) dist->d);
+ }
+ if (dist->weight != NULL) {
+ for (y = 0; y < h; y++)
+ free((gpointer *) dist->weight[y]);
+ free((gpointer *) dist->weight);
+ }
+}
+
+#if 0
+void medial_axis(bitmap_type * bitmap, at_distance_map * dist, const at_color * bg_color)
+{
+ unsigned x, y, test;
+ unsigned w, h;
+ unsigned char *b;
+ float **d, f;
+ at_color bg;
+
+ assert(bitmap != NULL);
+
+ assert(AT_BITMAP_PLANES(*bitmap) == 1);
+
+ b = AT_BITMAP_BITS(*bitmap);
+ assert(b != NULL);
+ assert(dist != NULL);
+ d = dist->d;
+ assert(d != NULL);
+
+ h = AT_BITMAP_HEIGHT(*dist);
+ w = AT_BITMAP_WIDTH(*dist);
+ assert(AT_BITMAP_WIDTH(*bitmap) == w && AT_BITMAP_HEIGHT(*bitmap) == h);
+
+ if (bg_color)
+ bg = *bg_color;
+ else
+ bg.r = bg.g = bg.b = 255;
+
+ f = d[0][0] + 0.5;
+ test = (f < d[1][0]) + (f < d[1][1]) + (f < d[0][1]);
+ if (test > 1)
+ b[0] = bg.r;
+
+ f = d[0][w - 1] + 0.5;
+ test = (f < d[1][w - 1]) + (f < d[1][w - 2]) + (f < d[0][w - 2]);
+ if (test > 1)
+ b[w - 1] = bg.r;
+
+ for (x = 1; x < w - 1; x++) {
+ f = d[0][x] + 0.5;
+ test = (f < d[0][x - 1]) + (f < d[0][x + 1]) + (f < d[1][x - 1])
+ + (f < d[1][x]) + (f < d[1][x + 1]);
+ if (test > 1)
+ b[x] = bg.r;
+ }
+ b += w;
+
+ for (y = 1; y < h - 1; y++) {
+ f = d[y][0] + 0.5;
+ test = (f < d[y - 1][0]) + (f < d[y - 1][1]) + (f < d[y][1])
+ + (f < d[y + 1][0]) + (f < d[y + 1][1]);
+ if (test > 1)
+ b[0] = bg.r;
+
+ for (x = 1; x < w - 1; x++) {
+ f = d[y][x] + 0.5;
+ test = (f < d[y - 1][x - 1]) + (f < d[y - 1][x]) + (f < d[y - 1][x + 1])
+ + (f < d[y][x - 1]) + (f < d[y][x + 1])
+ + (f < d[y + 1][x - 1]) + (f < d[y + 1][x]) + (f < d[y + 1][x + 1]);
+ if (test > 1)
+ b[x] = bg.r;
+ }
+
+ f = d[y][w - 1] + 0.5;
+ test = (f < d[y - 1][w - 1]) + (f < d[y - 1][w - 2]) + (f < d[y][w - 2])
+ + (f < d[y + 1][w - 1]) + (f < d[y + 1][w - 2]);
+ if (test > 1)
+ b[w - 1] = bg.r;
+
+ b += w;
+ }
+
+ for (x = 1; x < w - 1; x++) {
+ f = d[h - 1][x] + 0.5;
+ test = (f < d[h - 1][x - 1]) + (f < d[h - 1][x + 1])
+ + (f < d[h - 2][x - 1]) + (f < d[h - 2][x]) + (f < d[h - 2][x + 1]);
+ if (test > 1)
+ b[x] = bg.r;
+ }
+
+ f = d[h - 1][0] + 0.5;
+ test = (f < d[h - 2][0]) + (f < d[h - 2][1]) + (f < d[h - 1][1]);
+ if (test > 1)
+ b[0] = bg.r;
+
+ f = d[h - 1][w - 1] + 0.5;
+ test = (f < d[h - 2][w - 1]) + (f < d[h - 2][w - 2]) + (f < d[h - 1][w - 2]);
+ if (test > 1)
+ b[w - 1] = bg.r;
+}
+#endif
+
+/* Binarize a grayscale or color image. */
+
+void binarize(at_bitmap * bitmap)
+{
+ unsigned i, npixels, spp;
+ unsigned char *b;
+
+ assert(bitmap != NULL);
+ assert(AT_BITMAP_BITS(bitmap) != NULL);
+
+ b = AT_BITMAP_BITS(bitmap);
+ spp = AT_BITMAP_PLANES(bitmap);
+ npixels = AT_BITMAP_WIDTH(bitmap) * AT_BITMAP_HEIGHT(bitmap);
+
+ if (spp == 1) {
+ for (i = 0; i < npixels; i++)
+ b[i] = (b[i] > GRAY_THRESHOLD ? WHITE : BLACK);
+ } else if (spp == 3) {
+ unsigned char *rgb = b;
+ for (i = 0; i < npixels; i++, rgb += 3) {
+ b[i] = (LUMINANCE(rgb[0], rgb[1], rgb[2]) > GRAY_THRESHOLD ? WHITE : BLACK);
+ }
+ XREALLOC(AT_BITMAP_BITS(bitmap), npixels);
+ AT_BITMAP_PLANES(bitmap) = 1;
+ } else {
+ WARNING("binarize: %u-plane images are not supported", spp);
+ }
+}
+
+#if 0
+/* Thin a binary image, replacing the original image with the thinned one. */
+
+at_bitmap ip_thin(bitmap_type input_b)
+{
+ unsigned y, x, i;
+ gboolean k, again;
+ struct etyp t;
+ unsigned w = AT_BITMAP_WIDTH(input_b);
+ unsigned h = AT_BITMAP_HEIGHT(input_b);
+ size_t num_bytes = w * h;
+ bitmap_type b = input_b;
+
+ if (AT_BITMAP_PLANES(input_b) != 1) {
+ FATAL("thin: single-plane image required; " "%u-plane images cannot be thinned", AT_BITMAP_PLANES(input_b));
+ return b;
+ }
+
+ /* Process and return a copy of the input image. */
+ XMALLOC(b.bitmap, num_bytes);
+ memcpy(b.bitmap, input_b.bitmap, num_bytes);
+
+ /* Set background pixels to zero, foreground pixels to one. */
+ for (i = 0; i < num_bytes; i++)
+ b.bitmap[i] = (b.bitmap[i] == BLACK ? 1 : 0);
+
+ again = TRUE;
+ while (again) {
+ again = FALSE;
+
+ for (y = 1; y < h - 1; y++) {
+ for (x = 1; x < w - 1; x++) {
+ /* During processing, pixels are used to store edge
+ type codes, so we can't just test for WHITE or BLACK. */
+ if (*AT_BITMAP_PIXEL(b, y, x) == 0)
+ continue;
+
+ k = (!get_edge(b, y, x, &t)
+ || (get_edge(b, y, x + 1, &t) && *AT_BITMAP_PIXEL(b, y - 1, x)
+ && *AT_BITMAP_PIXEL(b, y + 1, x))
+ || (get_edge(b, y + 1, x, &t) && *AT_BITMAP_PIXEL(b, y, x - 1)
+ && *AT_BITMAP_PIXEL(b, y, x + 1))
+ || (get_edge(b, y, x + 1, &t) && get_edge(b, y + 1, x + 1, &t)
+ && get_edge(b, y + 1, x, &t)));
+ if (k)
+ continue;
+
+ get_edge(b, y, x, &t);
+ if (t.t01)
+ *AT_BITMAP_PIXEL(b, y, x) |= 4;
+ *AT_BITMAP_PIXEL(b, y, x) |= 2;
+ again = TRUE;
+ }
+ }
+
+ for (y = 0; y < h; y++)
+ for (x = 0; x < w; x++)
+ if (*AT_BITMAP_PIXEL(b, y, x) & 02)
+ *AT_BITMAP_PIXEL(b, y, x) = 0;
+
+ for (y = 1; y < h - 1; y++) {
+ for (x = 1; x < w - 1; x++) {
+ if (*AT_BITMAP_PIXEL(b, y, x) == 0)
+ continue;
+
+ k = (!get_edge(b, y, x, &t)
+ || ((*AT_BITMAP_PIXEL(b, y, x) & 04) == 0)
+ || (get_edge(b, y + 1, x, &t) && (*AT_BITMAP_PIXEL(b, y, x - 1))
+ && *AT_BITMAP_PIXEL(b, y, x + 1))
+ || (get_edge(b, y, x + 1, &t) && *AT_BITMAP_PIXEL(b, y - 1, x)
+ && *AT_BITMAP_PIXEL(b, y + 1, x))
+ || (get_edge(b, y + 1, x, &t) && get_edge(b, y, x + 1, &t)
+ && get_edge(b, y + 1, x + 1, &t)));
+ if (k)
+ continue;
+
+ *AT_BITMAP_PIXEL(b, y, x) |= 02;
+ again = TRUE;
+ }
+ }
+
+ for (y = 0; y < h; y++) {
+ for (x = 0; x < w; x++) {
+ if (*AT_BITMAP_PIXEL(b, y, x) & 02)
+ *AT_BITMAP_PIXEL(b, y, x) = 0;
+ else if (*AT_BITMAP_PIXEL(b, y, x) > 0)
+ *AT_BITMAP_PIXEL(b, y, x) = 1;
+ }
+ }
+ }
+
+ /* Staircase removal; northward bias. */
+ for (y = 1; y < h - 1; y++) {
+ for (x = 1; x < w - 1; x++) {
+ if (*AT_BITMAP_PIXEL(b, y, x) == 0)
+ continue;
+
+ k = !(*AT_BITMAP_PIXEL(b, y - 1, x)
+ && ((*AT_BITMAP_PIXEL(b, y, x + 1) && !*AT_BITMAP_PIXEL(b, y - 1, x + 1)
+ && !*AT_BITMAP_PIXEL(b, y + 1, x - 1)
+ && (!*AT_BITMAP_PIXEL(b, y, x - 1) || !*AT_BITMAP_PIXEL(b, y + 1, x)))
+ || (*AT_BITMAP_PIXEL(b, y, x - 1) && !*AT_BITMAP_PIXEL(b, y - 1, x - 1)
+ && !*AT_BITMAP_PIXEL(b, y + 1, x + 1) && (!*AT_BITMAP_PIXEL(b, y, x + 1) || !*AT_BITMAP_PIXEL(b, y + 1, x)))));
+ if (k)
+ continue;
+
+ *AT_BITMAP_PIXEL(b, y, x) |= 02;
+ }
+ }
+ for (y = 0; y < h; y++) {
+ for (x = 0; x < w; x++) {
+ if (*AT_BITMAP_PIXEL(b, y, x) & 02)
+ *AT_BITMAP_PIXEL(b, y, x) = 0;
+ else if (*AT_BITMAP_PIXEL(b, y, x) > 0)
+ *AT_BITMAP_PIXEL(b, y, x) = 1;
+ }
+ }
+
+ /* Southward bias */
+ for (y = 1; y < h - 1; y++) {
+ for (x = 1; x < w - 1; x++) {
+ if (*AT_BITMAP_PIXEL(b, y, x) == 0)
+ continue;
+
+ k = !(*AT_BITMAP_PIXEL(b, y + 1, x)
+ && ((*AT_BITMAP_PIXEL(b, y, x + 1) && !*AT_BITMAP_PIXEL(b, y + 1, x + 1)
+ && !*AT_BITMAP_PIXEL(b, y - 1, x - 1) && (!*AT_BITMAP_PIXEL(b, y, x - 1)
+ || !*AT_BITMAP_PIXEL(b, y - 1, x))) || (*AT_BITMAP_PIXEL(b, y, x - 1)
+ && !*AT_BITMAP_PIXEL(b, y + 1, x - 1) && !*AT_BITMAP_PIXEL(b, y - 1, x + 1)
+ && (!*AT_BITMAP_PIXEL(b, y, x + 1) || !*AT_BITMAP_PIXEL(b, y - 1, x)))));
+ if (k)
+ continue;
+
+ *AT_BITMAP_PIXEL(b, y, x) |= 02;
+ }
+ }
+ for (y = 0; y < h; y++) {
+ for (x = 0; x < w; x++) {
+ if (*AT_BITMAP_PIXEL(b, y, x) & 02)
+ *AT_BITMAP_PIXEL(b, y, x) = 0;
+ else if (*AT_BITMAP_PIXEL(b, y, x) > 0)
+ *AT_BITMAP_PIXEL(b, y, x) = 1;
+ }
+ }
+
+ /* Set background pixels to WHITE, foreground pixels to BLACK. */
+ for (i = 0; i < num_bytes; i++)
+ b.bitmap[i] = (b.bitmap[i] == 0 ? WHITE : BLACK);
+ return b;
+}
+
+gboolean get_edge(bitmap_type b, int y, int x, struct etyp * t)
+{
+ t->t00 = 0;
+ t->t01 = 0;
+ t->t01s = 0;
+ t->t11 = 0;
+ check(*AT_BITMAP_PIXEL(b, y - 1, x - 1), *AT_BITMAP_PIXEL(b, y - 1, x), *AT_BITMAP_PIXEL(b, y - 1, x + 1), t);
+ check(*AT_BITMAP_PIXEL(b, y - 1, x + 1), *AT_BITMAP_PIXEL(b, y, x + 1), *AT_BITMAP_PIXEL(b, y + 1, x + 1), t);
+ check(*AT_BITMAP_PIXEL(b, y + 1, x + 1), *AT_BITMAP_PIXEL(b, y + 1, x), *AT_BITMAP_PIXEL(b, y + 1, x - 1), t);
+ check(*AT_BITMAP_PIXEL(b, y + 1, x - 1), *AT_BITMAP_PIXEL(b, y, x - 1), *AT_BITMAP_PIXEL(b, y - 1, x - 1), t);
+ return *AT_BITMAP_PIXEL(b, y, x) && t->t00 && t->t11 && !t->t01s;
+}
+
+void check(int v1, int v2, int v3, struct etyp *t)
+{
+ if (!v2 && (!v1 || !v3))
+ t->t00 = 1;
+ if (v2 && (v1 || v3))
+ t->t11 = 1;
+ if ((!v1 && v2) || (!v2 && v3)) {
+ t->t01s = t->t01;
+ t->t01 = 1;
+ }
+}
+#endif
generated by cgit v1.2.3 (git 2.39.1) at 2024-10-30 18:40:59 +0000