summaryrefslogtreecommitdiffstats
path: root/src/3rdparty/autotrace/despeckle.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/3rdparty/autotrace/despeckle.c')
-rw-r--r--src/3rdparty/autotrace/despeckle.c710
1 files changed, 710 insertions, 0 deletions
diff --git a/src/3rdparty/autotrace/despeckle.c b/src/3rdparty/autotrace/despeckle.c
new file mode 100644
index 0000000..3ab66ac
--- /dev/null
+++ b/src/3rdparty/autotrace/despeckle.c
@@ -0,0 +1,710 @@
+/* despeckle.c: Bitmap despeckler
+
+ Copyright (C) 2001 David A. Bartold / 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 <assert.h>
+#include <math.h>
+#include <stdio.h>
+#include <time.h>
+#include "xstd.h"
+#include "logreport.h"
+#include "types.h"
+#include "bitmap.h"
+#include "despeckle.h"
+
+/* Calculate Error - compute the error between two colors
+ *
+ * Input parameters:
+ * Two 24 bit RGB colors
+ *
+ * Returns:
+ * The squared error between the two colors
+ */
+
+static int calc_error(unsigned char *color1, unsigned char *color2)
+{
+ int the_error;
+ int temp;
+
+ temp = color1[0] - color2[0];
+ the_error = temp * temp;
+ temp = color1[1] - color2[1];
+ the_error += temp * temp;
+ temp = color1[2] - color2[2];
+ the_error += temp * temp;
+
+ return the_error;
+}
+
+/* Calculate Error - compute the error between two colors
+ *
+ * Input parameters:
+ * Two 8 bit gray scale colors
+ *
+ * Returns:
+ * The squared error between the two colors
+ */
+
+static int calc_error_8(unsigned char *color1, unsigned char *color2)
+{
+ int the_error;
+
+ the_error = abs(color1[0] - color2[0]);
+
+ return the_error;
+}
+
+/* Find Size - Find the number of adjacent pixels of the same color
+ *
+ * Input Parameters:
+ * An 24 bit image, the current location inside the image, and the palette
+ * index of the color we are looking for
+ *
+ * Modified Parameters:
+ * A mask array used to prevent backtracking over already counted pixels
+ *
+ * Returns:
+ * Number of adjacent pixels found having the same color
+ */
+
+static int find_size( /* in */ unsigned char *index,
+ /* in */ int x,
+ /* in */ int y,
+ /* in */ int width,
+ /* in */ int height,
+ /* in */ unsigned char *bitmap,
+ /* in/out */ unsigned char *mask)
+{
+ int count;
+ int x1, x2;
+
+ if (y < 0 || y >= height || mask[y * width + x] == 1 || bitmap[3 * (y * width + x)] != index[0] || bitmap[3 * (y * width + x) + 1] != index[1] || bitmap[3 * (y * width + x) + 2] != index[2])
+ return 0;
+
+ for (x1 = x; x1 >= 0 && bitmap[3 * (y * width + x1)] == index[0] && bitmap[3 * (y * width + x1) + 1] == index[1] && bitmap[3 * (y * width + x1) + 2] == index[2] && mask[y * width + x] != 1; x1--) ;
+ x1++;
+
+ for (x2 = x; x2 < width && bitmap[3 * (y * width + x2)] == index[0] && bitmap[3 * (y * width + x2) + 1] == index[1] && bitmap[3 * (y * width + x2) + 2] == index[2] && mask[y * width + x] != 1; x2++) ;
+ x2--;
+
+ count = x2 - x1 + 1;
+ for (x = x1; x <= x2; x++)
+ mask[y * width + x] = 1;
+
+ for (x = x1; x <= x2; x++) {
+ count += find_size(index, x, y - 1, width, height, bitmap, mask);
+ count += find_size(index, x, y + 1, width, height, bitmap, mask);
+ }
+
+ return count;
+}
+
+/* Find Size - Find the number of adjacent pixels of the same color
+ *
+ * Input Parameters:
+ * An 8 bit image, the current location inside the image, and the palette
+ * index of the color we are looking for
+ *
+ * Modified Parameters:
+ * A mask array used to prevent backtracking over already counted pixels
+ *
+ * Returns:
+ * Number of adjacent pixels found having the same color
+ */
+
+static int find_size_8( /* in */ unsigned char *index,
+ /* in */ int x,
+ /* in */ int y,
+ /* in */ int width,
+ /* in */ int height,
+ /* in */ unsigned char *bitmap,
+ /* in/out */ unsigned char *mask)
+{
+ int count;
+ int x1, x2;
+
+ if (y < 0 || y >= height || mask[y * width + x] == 1 || bitmap[(y * width + x)] != index[0])
+ return 0;
+
+ for (x1 = x; x1 >= 0 && bitmap[(y * width + x1)] == index[0] && mask[y * width + x] != 1; x1--) ;
+ x1++;
+
+ for (x2 = x; x2 < width && bitmap[(y * width + x2)] == index[0] && mask[y * width + x] != 1; x2++) ;
+ x2--;
+
+ count = x2 - x1 + 1;
+ for (x = x1; x <= x2; x++)
+ mask[y * width + x] = 1;
+
+ for (x = x1; x <= x2; x++) {
+ count += find_size_8(index, x, y - 1, width, height, bitmap, mask);
+ count += find_size_8(index, x, y + 1, width, height, bitmap, mask);
+ }
+
+ return count;
+}
+
+/* Find Most Similar Neighbor - Given a position in an 24 bit bitmap and a color
+ * index, traverse over a blob of adjacent pixels having the same value.
+ * Return the color index of the neighbor pixel that has the most similar
+ * color.
+ *
+ * Input parameters:
+ * 24 bit bitmap, the current location inside the image,
+ * and the color index of the blob
+ *
+ * Modified parameters:
+ * Mask used to prevent backtracking
+ *
+ * Output parameters:
+ * Closest index != index and the error between the two colors squared
+ */
+
+static void find_most_similar_neighbor( /* in */ unsigned char *index,
+ /* in/out */ unsigned char **closest_index,
+ /* in/out */ int *error_amt,
+ /* in */ int x,
+ /* in */ int y,
+ /* in */ int width,
+ /* in */ int height,
+ /* in */ unsigned char *bitmap,
+ /* in/out */ unsigned char *mask)
+{
+ int x1, x2;
+ int temp_error;
+ unsigned char *value, *temp;
+
+ if (y < 0 || y >= height || mask[y * width + x] == 2)
+ return;
+
+ temp = &bitmap[3 * (y * width + x)];
+
+ assert(closest_index != NULL);
+
+ if (temp[0] != index[0] || temp[1] != index[1] || temp[2] != index[2]) {
+ value = temp;
+
+ temp_error = calc_error(index, value);
+
+ if (*closest_index == NULL || temp_error < *error_amt)
+ *closest_index = value, *error_amt = temp_error;
+
+ return;
+ }
+
+ for (x1 = x; x1 >= 0 && bitmap[3 * (y * width + x1)] == index[0] && bitmap[3 * (y * width + x1) + 1] == index[1] && bitmap[3 * (y * width + x1) + 2] == index[2]; x1--) ;
+ x1++;
+
+ for (x2 = x; x2 < width && bitmap[3 * (y * width + x2)] == index[0] && bitmap[3 * (y * width + x2) + 1] == index[1] && bitmap[3 * (y * width + x2) + 2] == index[2]; x2++) ;
+ x2--;
+
+ if (x1 > 0) {
+ value = &bitmap[3 * (y * width + x1 - 1)];
+
+ temp_error = calc_error(index, value);
+
+ if (*closest_index == NULL || temp_error < *error_amt)
+ *closest_index = value, *error_amt = temp_error;
+ }
+
+ if (x2 < width - 1) {
+ value = &bitmap[3 * (y * width + x2 + 1)];
+
+ temp_error = calc_error(index, value);
+
+ if (*closest_index == NULL || temp_error < *error_amt)
+ *closest_index = value, *error_amt = temp_error;
+ }
+
+ for (x = x1; x <= x2; x++)
+ mask[y * width + x] = 2;
+
+ for (x = x1; x <= x2; x++) {
+ find_most_similar_neighbor(index, closest_index, error_amt, x, y - 1, width, height, bitmap, mask);
+ find_most_similar_neighbor(index, closest_index, error_amt, x, y + 1, width, height, bitmap, mask);
+ }
+}
+
+/* Find Most Similar Neighbor - Given a position in an 8 bit bitmap and a color
+ * index, traverse over a blob of adjacent pixels having the same value.
+ * Return the color index of the neighbor pixel that has the most similar
+ * color.
+ *
+ * Input parameters:
+ * 8 bit bitmap, the current location inside the image,
+ * and the color index of the blob
+ *
+ * Modified parameters:
+ * Mask used to prevent backtracking
+ *
+ * Output parameters:
+ * Closest index != index and the error between the two colors squared
+ */
+
+static void find_most_similar_neighbor_8( /* in */ unsigned char *index,
+ /* in/out */ unsigned char **closest_index,
+ /* in/out */ int *error_amt,
+ /* in */ int x,
+ /* in */ int y,
+ /* in */ int width,
+ /* in */ int height,
+ /* in */ unsigned char *bitmap,
+ /* in/out */ unsigned char *mask)
+{
+ int x1, x2;
+ int temp_error;
+ unsigned char *value, *temp;
+
+ if (y < 0 || y >= height || mask[y * width + x] == 2)
+ return;
+
+ temp = &bitmap[(y * width + x)];
+
+ assert(closest_index != NULL);
+
+ if (temp[0] != index[0]) {
+ value = temp;
+
+ temp_error = calc_error_8(index, value);
+
+ if (*closest_index == NULL || temp_error < *error_amt)
+ *closest_index = value, *error_amt = temp_error;
+
+ return;
+ }
+
+ for (x1 = x; x1 >= 0 && bitmap[(y * width + x1)] == index[0]; x1--) ;
+ x1++;
+
+ for (x2 = x; x2 < width && bitmap[(y * width + x2)] == index[0]; x2++) ;
+ x2--;
+
+ if (x1 > 0) {
+ value = &bitmap[(y * width + x1 - 1)];
+
+ temp_error = calc_error_8(index, value);
+
+ if (*closest_index == NULL || temp_error < *error_amt)
+ *closest_index = value, *error_amt = temp_error;
+ }
+
+ if (x2 < width - 1) {
+ value = &bitmap[(y * width + x2 + 1)];
+
+ temp_error = calc_error_8(index, value);
+
+ if (*closest_index == NULL || temp_error < *error_amt)
+ *closest_index = value, *error_amt = temp_error;
+ }
+
+ for (x = x1; x <= x2; x++)
+ mask[y * width + x] = 2;
+
+ for (x = x1; x <= x2; x++) {
+ find_most_similar_neighbor_8(index, closest_index, error_amt, x, y - 1, width, height, bitmap, mask);
+ find_most_similar_neighbor_8(index, closest_index, error_amt, x, y + 1, width, height, bitmap, mask);
+ }
+}
+
+/* Fill - change the color of a blob
+ *
+ * Input parameters:
+ * The new color
+ *
+ * Modified parameters:
+ * 24 bit pixbuf and its mask (used to prevent backtracking)
+ */
+
+static void fill( /* in */ unsigned char *to_index,
+ /* in */ int x,
+ /* in */ int y,
+ /* in */ int width,
+ /* in */ int height,
+ /* in/out */ unsigned char *bitmap,
+ /* in/out */ unsigned char *mask)
+{
+ int x1, x2;
+
+ if (y < 0 || y >= height || mask[y * width + x] != 2)
+ return;
+
+ for (x1 = x; x1 >= 0 && mask[y * width + x1] == 2; x1--) ;
+ x1++;
+ for (x2 = x; x2 < width && mask[y * width + x2] == 2; x2++) ;
+ x2--;
+
+ assert(x1 >= 0 && x2 < width);
+
+ for (x = x1; x <= x2; x++) {
+ bitmap[3 * (y * width + x)] = to_index[0];
+ bitmap[3 * (y * width + x) + 1] = to_index[1];
+ bitmap[3 * (y * width + x) + 2] = to_index[2];
+ mask[y * width + x] = 3;
+ }
+
+ for (x = x1; x <= x2; x++) {
+ fill(to_index, x, y - 1, width, height, bitmap, mask);
+ fill(to_index, x, y + 1, width, height, bitmap, mask);
+ }
+}
+
+/* Fill - change the color of a blob
+ *
+ * Input parameters:
+ * The new color
+ *
+ * Modified parameters:
+ * 8 bit pixbuf and its mask (used to prevent backtracking)
+ */
+
+static void fill_8( /* in */ unsigned char *to_index,
+ /* in */ int x,
+ /* in */ int y,
+ /* in */ int width,
+ /* in */ int height,
+ /* in/out */ unsigned char *bitmap,
+ /* in/out */ unsigned char *mask)
+{
+ int x1, x2;
+
+ if (y < 0 || y >= height || mask[y * width + x] != 2)
+ return;
+
+ for (x1 = x; x1 >= 0 && mask[y * width + x1] == 2; x1--) ;
+ x1++;
+ for (x2 = x; x2 < width && mask[y * width + x2] == 2; x2++) ;
+ x2--;
+
+ assert(x1 >= 0 && x2 < width);
+
+ for (x = x1; x <= x2; x++) {
+ bitmap[(y * width + x)] = to_index[0];
+ mask[y * width + x] = 3;
+ }
+
+ for (x = x1; x <= x2; x++) {
+ fill_8(to_index, x, y - 1, width, height, bitmap, mask);
+ fill_8(to_index, x, y + 1, width, height, bitmap, mask);
+ }
+}
+
+/* Ignore - blob is big enough, mask it off
+ *
+ * Modified parameters:
+ * its mask (used to prevent backtracking)
+ */
+
+static void ignore( /* in */ int x,
+ /* in */ int y,
+ /* in */ int width,
+ /* in */ int height,
+ /* in/out */ unsigned char *mask)
+{
+ int x1, x2;
+
+ if (y < 0 || y >= height || mask[y * width + x] != 1)
+ return;
+
+ for (x1 = x; x1 >= 0 && mask[y * width + x1] == 1; x1--) ;
+ x1++;
+ for (x2 = x; x2 < width && mask[y * width + x2] == 1; x2++) ;
+ x2--;
+
+ assert(x1 >= 0 && x2 < width);
+
+ for (x = x1; x <= x2; x++)
+ mask[y * width + x] = 3;
+
+ for (x = x1; x <= x2; x++) {
+ ignore(x, y - 1, width, height, mask);
+ ignore(x, y + 1, width, height, mask);
+ }
+}
+
+/* Recolor - conditionally change a feature's color to the closest color of all
+ * neighboring pixels
+ *
+ * Input parameters:
+ * The color palette, current blob size, and adaptive tightness
+ *
+ * Adaptive Tightness: (integer 1 to 256)
+ * 1 = really tight
+ * 256 = turn off the feature
+ *
+ * Modified parameters:
+ * 24 bit pixbuf and its mask (used to prevent backtracking)
+ *
+ * Returns:
+ * TRUE - feature was recolored, thus coalesced
+ * FALSE - feature wasn't recolored
+ */
+
+static gboolean recolor( /* in */ double adaptive_tightness,
+ /* in */ int x,
+ /* in */ int y,
+ /* in */ int width,
+ /* in */ int height,
+ /* in/out */ unsigned char *bitmap,
+ /* in/out */ unsigned char *mask)
+{
+ unsigned char *index, *to_index;
+ int error_amt, max_error;
+
+ index = &bitmap[3 * (y * width + x)];
+ to_index = NULL;
+ error_amt = 0;
+ max_error = (int)(3.0 * adaptive_tightness * adaptive_tightness);
+
+ find_most_similar_neighbor(index, &to_index, &error_amt, x, y, width, height, bitmap, mask);
+
+ /* This condition only fails if the bitmap is all the same color */
+ if (to_index != NULL) {
+ /*
+ * If the difference between the two colors is too great,
+ * don't coalesce the feature with its neighbor(s). This prevents a
+ * color from turning into its complement.
+ */
+
+ if (calc_error(index, to_index) > max_error)
+ fill(index, x, y, width, height, bitmap, mask);
+ else {
+ fill(to_index, x, y, width, height, bitmap, mask);
+
+ return TRUE;
+ }
+ }
+
+ return FALSE;
+}
+
+/* Recolor - conditionally change a feature's color to the closest color of all
+ * neighboring pixels
+ *
+ * Input parameters:
+ * The color palette, current blob size, and adaptive tightness
+ *
+ * Adaptive Tightness: (integer 1 to 256)
+ * 1 = really tight
+ * 256 = turn off the feature
+ *
+ * Modified parameters:
+ * 8 bit pixbuf and its mask (used to prevent backtracking)
+ *
+ * Returns:
+ * TRUE - feature was recolored, thus coalesced
+ * FALSE - feature wasn't recolored
+ */
+
+static gboolean recolor_8( /* in */ double adaptive_tightness,
+ /* in */ int x,
+ /* in */ int y,
+ /* in */ int width,
+ /* in */ int height,
+ /* in/out */ unsigned char *bitmap,
+ /* in/out */ unsigned char *mask)
+{
+ unsigned char *index, *to_index;
+ int error_amt;
+
+ index = &bitmap[(y * width + x)];
+ to_index = NULL;
+ error_amt = 0;
+
+ find_most_similar_neighbor_8(index, &to_index, &error_amt, x, y, width, height, bitmap, mask);
+
+ /* This condition only fails if the bitmap is all the same color */
+ if (to_index != NULL) {
+ /*
+ * If the difference between the two colors is too great,
+ * don't coalesce the feature with its neighbor(s). This prevents a
+ * color from turning into its complement.
+ */
+
+ if (calc_error_8(index, to_index) > adaptive_tightness)
+ fill_8(index, x, y, width, height, bitmap, mask);
+ else {
+ fill_8(to_index, x, y, width, height, bitmap, mask);
+
+ return TRUE;
+ }
+ }
+
+ return FALSE;
+}
+
+/* Despeckle Iteration - Despeckle all regions smaller than cur_size pixels
+ *
+ * Input Parameters:
+ * Current blob size, maximum blob size
+ * for all iterations (used to selectively recolor blobs), adaptive
+ * tightness and noise removal
+ *
+ * Modified Parameters:
+ * The 24 bit pixbuf is despeckled
+ */
+
+static void despeckle_iteration( /* in */ int level,
+ /* in */ double adaptive_tightness,
+ /* in */ double noise_max,
+ /* in */ int width,
+ /* in */ int height,
+ /* in/out */ unsigned char *bitmap)
+{
+ unsigned char *mask;
+ int x, y;
+ int current_size;
+ int tightness;
+
+ /* Size doubles each iteration level, so current_size = 2^level */
+ current_size = 1 << level;
+ tightness = (int)(noise_max / (1.0 + adaptive_tightness * level));
+
+ mask = (unsigned char *)calloc(width * height, sizeof(unsigned char));
+ for (y = 0; y < height; y++) {
+ for (x = 0; x < width; x++) {
+ if (mask[y * width + x] == 0) {
+ int size;
+
+ size = find_size(&bitmap[3 * (y * width + x)], x, y, width, height, bitmap, mask);
+
+ assert(size > 0);
+
+ if (size < current_size) {
+ if (recolor(tightness, x, y, width, height, bitmap, mask))
+ x--;
+ } else
+ ignore(x, y, width, height, mask);
+ }
+ }
+ }
+
+ free(mask);
+}
+
+/* Despeckle Iteration - Despeckle all regions smaller than cur_size pixels
+ *
+ * Input Parameters:
+ * Current blob size, maximum blob size
+ * for all iterations (used to selectively recolor blobs), adaptive
+ * tightness and noise removal
+ *
+ * Modified Parameters:
+ * The 8 bit pixbuf is despeckled
+ */
+
+static void despeckle_iteration_8( /* in */ int level,
+ /* in */ double adaptive_tightness,
+ /* in */ double noise_max,
+ /* in */ int width,
+ /* in */ int height,
+ /* in/out */ unsigned char *bitmap)
+{
+ unsigned char *mask;
+ int x, y;
+ int current_size;
+ int tightness;
+
+ /* Size doubles each iteration level, so current_size = 2^level */
+ current_size = 1 << level;
+ tightness = (int)(noise_max / (1.0 + adaptive_tightness * level));
+
+ mask = (unsigned char *)calloc(width * height, sizeof(unsigned char));
+ for (y = 0; y < height; y++) {
+ for (x = 0; x < width; x++) {
+ if (mask[y * width + x] == 0) {
+ int size;
+
+ size = find_size_8(&bitmap[(y * width + x)], x, y, width, height, bitmap, mask);
+
+ assert(size > 0);
+
+ if (size < current_size) {
+ if (recolor_8(tightness, x, y, width, height, bitmap, mask))
+ x--;
+ } else
+ ignore(x, y, width, height, mask);
+ }
+ }
+ }
+
+ free(mask);
+}
+
+/* Despeckle - Despeckle a 8 or 24 bit image
+ *
+ * Input Parameters:
+ * Adaptive feature coalescing value, the despeckling level and noise removal
+ *
+ * Despeckling level (level): Integer from 0 to ~20
+ * 0 = perform no despeckling
+ * An increase of the despeckling level by one doubles the size of features.
+ * The Maximum value must be smaller then the logarithm base two of the number
+ * of pixels.
+ *
+ * Feature coalescing (tightness): Real from 0.0 to ~8.0
+ * 0 = Turn it off (whites may turn black and vice versa, etc)
+ * 3 = Good middle value
+ * 8 = Really tight
+ *
+ * Noise removal (noise_removal): Real from 1.0 to 0.0
+ * 1 = Maximum noise removal
+ * You should always use the highest value, only if certain parts of the image
+ * disappear you should lower it.
+ *
+ * Modified Parameters:
+ * The bitmap is despeckled.
+ */
+
+void despeckle( /* in/out */ at_bitmap * bitmap,
+ /* in */ int level,
+ /* in */ gfloat tightness,
+ /* in */ gfloat noise_removal,
+ /* exception handling */ at_exception_type * excep)
+{
+ int i, planes, max_level;
+ short width, height;
+ unsigned char *bits;
+ double noise_max, adaptive_tightness;
+
+ planes = AT_BITMAP_PLANES(bitmap);
+ noise_max = noise_removal * 255.0;
+ width = AT_BITMAP_WIDTH(bitmap);
+ height = AT_BITMAP_HEIGHT(bitmap);
+ bits = AT_BITMAP_BITS(bitmap);
+ max_level = (int)(log(width * height) / log(2.0) - 0.5);
+ if (level > max_level)
+ level = max_level;
+ adaptive_tightness = (noise_removal * (1.0 + tightness * level) - 1.0) / level;
+
+ if (planes == 3) {
+ for (i = 0; i < level; i++)
+ despeckle_iteration(i, adaptive_tightness, noise_max, width, height, bits);
+ } else if (planes == 1) {
+ for (i = 0; i < level; i++)
+ despeckle_iteration_8(i, adaptive_tightness, noise_max, width, height, bits);
+ } else {
+ LOG("despeckle: %u-plane images are not supported", planes);
+ at_exception_fatal(excep, "despeckle: wrong plane images are passed");
+ return;
+ }
+
+}
generated by cgit v1.2.3 (git 2.39.1) at 2024-06-15 12:07:52 +0000