summaryrefslogtreecommitdiffstats
path: root/src/3rdparty/autotrace/thin-image.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/3rdparty/autotrace/thin-image.c')
-rw-r--r--src/3rdparty/autotrace/thin-image.c353
1 files changed, 353 insertions, 0 deletions
diff --git a/src/3rdparty/autotrace/thin-image.c b/src/3rdparty/autotrace/thin-image.c
new file mode 100644
index 0000000..2e220ec
--- /dev/null
+++ b/src/3rdparty/autotrace/thin-image.c
@@ -0,0 +1,353 @@
+/* thin-image.c: thin binary image
+
+ Copyright (C) 2001, 2002 Martin Weber
+
+ This library is free software; you can redistribute it and/or
+ modify it under the terms of the GNU Lesser General Public License
+ as published by the Free Software Foundation; either version 2.1 of
+ the License, or (at your option) any later version.
+
+ This library is distributed in the hope that it will be useful, but
+ WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ Lesser General Public License for more details.
+
+ You should have received a copy of the GNU Lesser General Public
+ License along with this library; if not, write to the Free Software
+ Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307
+ USA. */
+
+#ifdef HAVE_CONFIG_H
+#include "config.h"
+#endif /* Def: HAVE_CONFIG_H */
+
+#include <stdlib.h>
+#include <stdio.h>
+#include "thin-image.h"
+#include "logreport.h"
+#include "types.h"
+#include "bitmap.h"
+#include "xstd.h"
+#include <string.h>
+
+#define PIXEL_SET(p, new) ((void)memcpy((p), (new), sizeof(Pixel)))
+#define PIXEL_EQUAL(p1, p2) \
+ ((p1)[0] == (p2)[0] && (p1)[1] == (p2)[1] && (p1)[2] == (p2)[2])
+
+typedef unsigned char Pixel[3]; /* RGB pixel data type */
+
+void thin3(at_bitmap * image, Pixel colour);
+void thin1(at_bitmap * image, unsigned char colour);
+
+/* -------------------------------- ThinImage - Thin binary image. --------------------------- *
+ *
+ * Description:
+ * Thins the supplied binary image using Rosenfeld's parallel
+ * thinning algorithm.
+ *
+ * On Entry:
+ * image = Image to thin.
+ *
+ * -------------------------------------------------------------------------------------------- */
+
+/* Direction masks: */
+/* N S W E */
+static unsigned int masks[] = { 0200, 0002, 0040, 0010 };
+
+/* True if pixel neighbor map indicates the pixel is 8-simple and */
+/* not an end point and thus can be deleted. The neighborhood */
+/* map is defined as an integer of bits abcdefghi with a non-zero */
+/* bit representing a non-zero pixel. The bit assignment for the */
+/* neighborhood is: */
+/* */
+/* a b c */
+/* d e f */
+/* g h i */
+
+static unsigned char todelete[512] = {
+ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
+ 0, 0, 0, 1, 0, 0, 1, 1, 0, 1, 1, 1, 0, 0, 1, 1,
+ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
+ 0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1,
+ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
+ 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 1, 1,
+ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
+ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 1, 1,
+ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
+ 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 1, 1,
+ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
+ 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
+ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
+ 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 1, 1,
+ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
+ 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
+ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
+ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
+ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
+ 1, 0, 1, 1, 1, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1,
+ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
+ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
+ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
+ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 1, 1,
+ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
+ 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 1, 1,
+ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
+ 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
+ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
+ 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 1, 1,
+ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
+ 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1
+};
+
+static at_color background = { 0xff, 0xff, 0xff };
+
+void thin_image(at_bitmap * image, const at_color * bg, at_exception_type * exp)
+{
+ /* This is nasty as we need to call thin once for each
+ * colour in the image the way I do this is to keep a second
+ * copy of the bitmap and to use this to keep
+ * track of which colours have not yet been processed,
+ * trades time for pathological case memory.....*/
+ long m, n, num_pixels;
+ at_bitmap bm;
+ unsigned int spp = AT_BITMAP_PLANES(image), width = AT_BITMAP_WIDTH(image), height = AT_BITMAP_HEIGHT(image);
+
+ if (bg)
+ background = *bg;
+
+ bm.height = image->height;
+ bm.width = image->width;
+ bm.np = image->np;
+ XMALLOC(bm.bitmap, height * width * spp);
+ memcpy(bm.bitmap, image->bitmap, height * width * spp);
+ /* that clones the image */
+
+ num_pixels = height * width;
+ switch (spp) {
+ case 3:
+ {
+ Pixel *ptr = (Pixel *) AT_BITMAP_BITS(&bm);
+ Pixel bg_color;
+ bg_color[0] = background.r;
+ bg_color[1] = background.g;
+ bg_color[2] = background.b;
+
+ for (n = num_pixels - 1; n >= 0L; --n) {
+ Pixel p;
+
+ PIXEL_SET(p, ptr[n]);
+ if (!PIXEL_EQUAL(p, bg_color)) {
+ /* we have a new colour in the image */
+ LOG("Thinning colour (%x, %x, %x)\n", p[0], p[1], p[2]);
+ for (m = n - 1; m >= 0L; --m) {
+ if (PIXEL_EQUAL(ptr[m], p))
+ PIXEL_SET(ptr[m], bg_color);
+ }
+ thin3(image, p);
+ }
+ }
+ break;
+ }
+
+ case 1:
+ {
+ unsigned char *ptr = AT_BITMAP_BITS(&bm);
+ unsigned char bg_color;
+
+ if (background.r == background.g && background.g == background.b)
+ bg_color = background.r;
+ else
+ bg_color = at_color_luminance(&background);
+
+ for (n = num_pixels - 1; n >= 0L; --n) {
+ unsigned char c = ptr[n];
+ if (c != bg_color) {
+ LOG("Thinning colour %x\n", c);
+ for (m = n - 1; m >= 0L; --m)
+ if (ptr[m] == c)
+ ptr[m] = bg_color;
+ thin1(image, c);
+ }
+ }
+ break;
+ }
+
+ default:
+ {
+ LOG("thin_image: %u-plane images are not supported", spp);
+ at_exception_fatal(exp, "thin_image: wrong plane images are passed");
+ goto cleanup;
+ }
+ }
+cleanup:
+ free(bm.bitmap);
+}
+
+void thin3(at_bitmap * image, Pixel colour)
+{
+ Pixel *ptr, *y_ptr, *y1_ptr;
+ Pixel bg_color;
+ unsigned int xsize, ysize; /* Image resolution */
+ unsigned int x, y; /* Pixel location */
+ unsigned int i; /* Pass index */
+ unsigned int pc = 0; /* Pass count */
+ unsigned int count = 1; /* Deleted pixel count */
+ unsigned int p, q; /* Neighborhood maps of adjacent */
+ /* cells */
+ unsigned char *qb; /* Neighborhood maps of previous */
+ /* scanline */
+ unsigned int m; /* Deletion direction mask */
+
+ bg_color[0] = background.r;
+ bg_color[1] = background.g;
+ bg_color[2] = background.b;
+
+ LOG(" Thinning image.....\n ");
+ xsize = AT_BITMAP_WIDTH(image);
+ ysize = AT_BITMAP_HEIGHT(image);
+ XMALLOC(qb, xsize * sizeof(unsigned char));
+ qb[xsize - 1] = 0; /* Used for lower-right pixel */
+ ptr = (Pixel *) AT_BITMAP_BITS(image);
+
+ while (count) { /* Scan image while deletions */
+ pc++;
+ count = 0;
+
+ for (i = 0; i < 4; i++) {
+
+ m = masks[i];
+
+ /* Build initial previous scan buffer. */
+ p = PIXEL_EQUAL(ptr[0], colour);
+ for (x = 0; x < xsize - 1; x++)
+ qb[x] = (unsigned char)(p = ((p << 1) & 0006) | (unsigned int)PIXEL_EQUAL(ptr[x + 1], colour));
+
+ /* Scan image for pixel deletion candidates. */
+ y_ptr = ptr;
+ y1_ptr = ptr + xsize;
+ for (y = 0; y < ysize - 1; y++, y_ptr += xsize, y1_ptr += xsize) {
+ q = qb[0];
+ p = ((q << 2) & 0330) | (unsigned int)PIXEL_EQUAL(y1_ptr[0], colour);
+
+ for (x = 0; x < xsize - 1; x++) {
+ q = qb[x];
+ p = ((p << 1) & 0666) | ((q << 3) & 0110) | (unsigned int)PIXEL_EQUAL(y1_ptr[x + 1], colour);
+ qb[x] = (unsigned char)p;
+ if ((i != 2 || x != 0) && ((p & m) == 0) && todelete[p]) {
+ count++; /* delete the pixel */
+ PIXEL_SET(y_ptr[x], bg_color);
+ }
+ }
+
+ /* Process right edge pixel. */
+ p = (p << 1) & 0666;
+ if (i != 3 && (p & m) == 0 && todelete[p]) {
+ count++;
+ PIXEL_SET(y_ptr[xsize - 1], bg_color);
+ }
+ }
+
+ if (i != 1) {
+ /* Process bottom scan line. */
+ q = qb[0];
+ p = ((q << 2) & 0330);
+
+ y_ptr = ptr + xsize * (ysize - 1);
+ for (x = 0; x < xsize; x++) {
+ q = qb[x];
+ p = ((p << 1) & 0666) | ((q << 3) & 0110);
+ if ((i != 2 || x != 0) && (p & m) == 0 && todelete[p]) {
+ count++;
+ PIXEL_SET(y_ptr[x], bg_color);
+ }
+ }
+ }
+ }
+ LOG("ThinImage: pass %d, %d pixels deleted\n", pc, count);
+ }
+ free(qb);
+}
+
+void thin1(at_bitmap * image, unsigned char colour)
+{
+ unsigned char *ptr, *y_ptr, *y1_ptr;
+ unsigned char bg_color;
+ unsigned int xsize, ysize; /* Image resolution */
+ unsigned int x, y; /* Pixel location */
+ unsigned int i; /* Pass index */
+ unsigned int pc = 0; /* Pass count */
+ unsigned int count = 1; /* Deleted pixel count */
+ unsigned int p, q; /* Neighborhood maps of adjacent */
+ /* cells */
+ unsigned char *qb; /* Neighborhood maps of previous */
+ /* scanline */
+ unsigned int m; /* Deletion direction mask */
+
+ if (background.r == background.g && background.g == background.b)
+ bg_color = background.r;
+ else
+ bg_color = at_color_luminance(&background);
+
+ LOG(" Thinning image.....\n ");
+ xsize = AT_BITMAP_WIDTH(image);
+ ysize = AT_BITMAP_HEIGHT(image);
+ XMALLOC(qb, xsize * sizeof(unsigned char));
+ qb[xsize - 1] = 0; /* Used for lower-right pixel */
+ ptr = AT_BITMAP_BITS(image);
+
+ while (count) { /* Scan image while deletions */
+ pc++;
+ count = 0;
+
+ for (i = 0; i < 4; i++) {
+
+ m = masks[i];
+
+ /* Build initial previous scan buffer. */
+ p = (ptr[0] == colour);
+ for (x = 0; x < xsize - 1; x++)
+ qb[x] = (unsigned char)(p = ((p << 1) & 0006) | (unsigned int)(ptr[x + 1] == colour));
+
+ /* Scan image for pixel deletion candidates. */
+ y_ptr = ptr;
+ y1_ptr = ptr + xsize;
+ for (y = 0; y < ysize - 1; y++, y_ptr += xsize, y1_ptr += xsize) {
+ q = qb[0];
+ p = ((q << 2) & 0330) | (y1_ptr[0] == colour);
+
+ for (x = 0; x < xsize - 1; x++) {
+ q = qb[x];
+ p = ((p << 1) & 0666) | ((q << 3) & 0110) | (unsigned int)(y1_ptr[x + 1] == colour);
+ qb[x] = (unsigned char)p;
+ if (((p & m) == 0) && todelete[p]) {
+ count++;
+ y_ptr[x] = bg_color; /* delete the pixel */
+ }
+ }
+
+ /* Process right edge pixel. */
+ p = (p << 1) & 0666;
+ if ((p & m) == 0 && todelete[p]) {
+ count++;
+ y_ptr[xsize - 1] = bg_color;
+ }
+ }
+
+ /* Process bottom scan line. */
+ q = qb[0];
+ p = ((q << 2) & 0330);
+
+ y_ptr = ptr + xsize * (ysize - 1);
+ for (x = 0; x < xsize; x++) {
+ q = qb[x];
+ p = ((p << 1) & 0666) | ((q << 3) & 0110);
+ if ((p & m) == 0 && todelete[p]) {
+ count++;
+ y_ptr[x] = bg_color;
+ }
+ }
+ }
+ LOG("thin1: pass %d, %d pixels deleted\n", pc, count);
+ }
+ free(qb);
+}
generated by cgit v1.2.3 (git 2.39.1) at 2024-06-18 03:24:19 +0000