[gegl/soc-2011-seamless-clone: 34/37] Handle many error cases in the outline finding for seamless cloning
- From: Barak Itkin <barakitkin src gnome org>
- To: commits-list gnome org
- Cc:
- Subject: [gegl/soc-2011-seamless-clone: 34/37] Handle many error cases in the outline finding for seamless cloning
- Date: Sat, 11 Aug 2012 13:19:24 +0000 (UTC)
commit 4f3932e3a61bac29658091169f421775a70b55b7
Author: Barak Itkin <lightningismyname gmail com>
Date: Fri Jul 20 21:20:46 2012 +0300
Handle many error cases in the outline finding for seamless cloning
operations/common/seamless-clone/find-outline.c | 217 +++++++++++++++++---
operations/common/seamless-clone/find-outline.h | 12 +-
.../common/seamless-clone/seamless-clone-common.c | 45 +++-
.../common/seamless-clone/seamless-clone-common.h | 8 +
operations/common/seamless-clone/seamless-clone.c | 6 +-
5 files changed, 240 insertions(+), 48 deletions(-)
---
diff --git a/operations/common/seamless-clone/find-outline.c b/operations/common/seamless-clone/find-outline.c
index 892e43d..69efad0 100644
--- a/operations/common/seamless-clone/find-outline.c
+++ b/operations/common/seamless-clone/find-outline.c
@@ -18,18 +18,29 @@
*/
/* This file is part 1 of 3 in the seamless clone operation. The logic
- * in this file allows to find the outline of a given image. A pixel is
- * considered an outline pixel, if it's alpha is larger than 0.5 and one
- * of it's neighbors has alpha lower than that.
+ * in this file allows to find the outline of a given image.
*
- * Currently, the logic in this file allows for finding one outline with
- * no holes, and it currently assumse that only one "island" of high
- * alpha exists
+ * Terminology:
+ *
+ * Opaque - A pixel with alpha of at least 0.5
+ * Island - An opaque pixel with 8 non-opaque neighbors
+ * Edge - An opaque pixel with at least 1 (out of 8) non-opaque
+ * neighbors
+ * Area - A continuos region (using 8 neighbor connectivity) of
+ * pixels with the same opacity state
+ * Outline - A non-repeating sequence of edge pixels where each pixel
+ * is a neighbor of the previous, and the first pixel is a
+ * neighbor of the last pixel
+ *
+ * Currently, the logic in this file implements an algorithm for
+ * finding one outline. If more than one outline exists (may happen due
+ * to non-opaque areas inside opaque areas ("holes") or due to the
+ * existance of more than one opaque area in the image)
+ * NOTE: Island pixels are ignored in the outline finding algorithm
*/
#include <gegl.h>
-
#include "seamless-clone.h"
#include <poly2tri-c/p2t/poly2tri.h>
#include <poly2tri-c/refine/refine.h>
@@ -68,25 +79,6 @@ sc_point_eq (const ScPoint *pt1,
return pt1->x == pt2->x && pt1->y == pt2->y;
}
-static gint
-sc_point_cmp (const ScPoint *pt1,
- const ScPoint *pt2)
-{
- if (pt1->y < pt2->y)
- return -1;
- else if (pt1->y > pt2->y)
- return +1;
- else
- {
- if (pt1->x < pt2->x)
- return -1;
- else if (pt1->x > pt2->x)
- return +1;
- else
- return 0;
- }
-}
-
static inline gboolean
in_range (gint val,
gint min,
@@ -120,7 +112,7 @@ is_opaque (const GeglRectangle *search_area,
return col[3] >= 0.5f;
}
-/* This function assumes the pixel is white! */
+/* This function assumes the pixel is opaque! */
static inline gboolean
is_opaque_island (const GeglRectangle *search_area,
GeglBuffer *buffer,
@@ -137,6 +129,42 @@ is_opaque_island (const GeglRectangle *search_area,
return TRUE;
}
+/* This function checks whether a pixel is opaque, is not an island and
+ * also is an edge pixel */
+static inline gboolean
+is_valid_edge (const GeglRectangle *search_area,
+ GeglBuffer *buffer,
+ const Babl *format,
+ const ScPoint *pt)
+{
+ gint i;
+ ScPoint temp;
+
+ if (! is_opaque (search_area, buffer, format, pt))
+ return FALSE;
+
+ for (i = 0; i < 8; ++i)
+ if (is_opaque (search_area, buffer, format, sc_point_move (pt, i, &temp)))
+ return FALSE;
+
+ return TRUE;
+}
+
+/**
+ * This function takes an opaque edge pixel which MUST NOT BE AN ISLAND
+ * and returns the next edge pixel, going clock-wise around the outline
+ * of the area.
+ *
+ * Finding the next edge pixel is based on the following concept:
+ * - If we are going clock-wise around the outline, then the circular
+ * sector whose center is the current pixel and it's two radii (in
+ * clock-wise order) are the line to the previous outline pixel and
+ * the line to the next outline pixel must contain only non-opaque
+ * pixels!
+ * - So, use this property to go clockwise inside this circular sector
+ * untill you find an opaque pixel. That pixel must then be the next
+ * edge pixel (when going in clock-wise direction)!
+ */
static inline ScDirection
walk_cw (const GeglRectangle *search_area,
GeglBuffer *buffer,
@@ -159,9 +187,17 @@ walk_cw (const GeglRectangle *search_area,
return dir_to_next;
}
+/**
+ * This function scans the image from the top left corner (X,Y = 0),
+ * going right (increasing X) and then down (increasing Y) until it
+ * encounters the first opaque edge pixel which is not an island. It
+ * the finds and returns the outline in which this edge pixel takes
+ * a part.
+ */
ScOutline*
sc_outline_find (const GeglRectangle *search_area,
- GeglBuffer *buffer)
+ GeglBuffer *buffer,
+ gboolean *ignored_islands)
{
const Babl *format = babl_format("RGBA float");
ScOutline *result = g_ptr_array_new ();
@@ -176,11 +212,18 @@ sc_outline_find (const GeglRectangle *search_area,
for (current.y = search_area->y; current.y < row_max; ++current.y)
{
for (current.x = search_area->x; current.x < col_max; ++current.x)
- if (is_opaque (search_area, buffer, format, ¤t)
- && ! is_opaque_island (search_area, buffer, format, ¤t))
+ if (is_opaque (search_area, buffer, format, ¤t))
{
- found = TRUE;
- break;
+ if (is_opaque_island (search_area, buffer, format, ¤t))
+ {
+ if (ignored_islands)
+ *ignored_islands = TRUE;
+ }
+ else
+ {
+ found = TRUE;
+ break;
+ }
}
if (found)
@@ -208,6 +251,116 @@ sc_outline_find (const GeglRectangle *search_area,
return result;
}
+/**
+ * A function to sort points first by increasing Y values and then by
+ * increasing X values
+ */
+static gint
+sc_point_cmp (const ScPoint **pt1,
+ const ScPoint **pt2)
+{
+ if ((*pt1)->y < (*pt2)->y)
+ return -1;
+ else if ((*pt1)->y > (*pt2)->y)
+ return +1;
+ else
+ {
+ if ((*pt1)->x < (*pt2)->x)
+ return -1;
+ else if ((*pt1)->x > (*pt2)->x)
+ return +1;
+ else
+ return 0;
+ }
+}
+
+/**
+ * This function checks whether a given outline is the only outline
+ * inside the image. The logic of the function works like this:
+ *
+ * - Iterate over each row of pixels in the search area
+ * - Use the even-odd technique to decide whether you are outside or
+ * inside the area defined by the outline
+ * - If we found a non-opaque pixel inside the area or an opaque pixel
+ * outside the area, then there is more than one outline
+ *
+ * To efficiently test whether the current pixel is a part of the
+ * outline, we will sort the outline pixels by increasing Y values and
+ * then by increasing X values.
+ * Since our scan of the image is by rows (increasing X) and going from
+ * top to bottom, this will exactly match the sorting of the array,
+ * allowing to check whether a pixel is in the outline in constant
+ * time!
+ */
+gboolean
+sc_outline_check_if_single (const GeglRectangle *search_area,
+ GeglBuffer *buffer,
+ ScOutline *existing)
+{
+ const Babl *format = babl_format("RGBA float");
+ GPtrArray *sorted_points = g_ptr_array_sized_new (existing->len);
+ gboolean not_single = FALSE;
+
+ ScPoint current, *sorted_p;
+ guint s_index;
+
+ gint row_max = search_area->x + search_area->width;
+ gint col_max = search_area->y + search_area->height;
+
+ for (s_index = 0; s_index < existing->len; ++s_index)
+ g_ptr_array_add (sorted_points, g_ptr_array_index (existing, s_index));
+ g_ptr_array_sort (sorted_points, (GCompareFunc) sc_point_cmp);
+
+ s_index = 0;
+ sorted_p = (ScPoint*) g_ptr_array_index (sorted_points, s_index);
+
+ for (current.y = search_area->y; current.y < row_max; ++current.y)
+ {
+ gboolean inside = FALSE;
+
+ for (current.x = search_area->x; current.x < col_max; ++current.x)
+ {
+ gboolean hit, opaque;
+
+ opaque = is_opaque (search_area, buffer, format, ¤t);
+ hit = sc_point_eq (¤t, sorted_p);
+
+ if (hit && ! inside)
+ {
+ inside = TRUE;
+ sorted_p = (ScPoint*) g_ptr_array_index (sorted_points, ++s_index);
+ /* Prevent "leaving" the area in the next if statement */
+ hit = FALSE;
+ }
+
+ if (inside != opaque
+ && ! (opaque && is_opaque_island (search_area, buffer, format, ¤t)))
+ {
+ not_single = FALSE;
+ break;
+ }
+
+ if (hit && inside)
+ {
+ inside = FALSE;
+ sorted_p = (ScPoint*) g_ptr_array_index (sorted_points, ++s_index);
+ }
+ }
+
+ if (not_single)
+ break;
+ }
+
+ g_ptr_array_free (sorted_points, TRUE);
+ return ! not_single;
+}
+
+guint
+sc_outline_length (ScOutline *self)
+{
+ return ((GPtrArray*) self)->len;
+}
+
void
sc_outline_free (ScOutline *self)
{
diff --git a/operations/common/seamless-clone/find-outline.h b/operations/common/seamless-clone/find-outline.h
index 01e1fc1..cc56379 100644
--- a/operations/common/seamless-clone/find-outline.h
+++ b/operations/common/seamless-clone/find-outline.h
@@ -106,8 +106,16 @@ typedef struct {
*/
typedef GPtrArray ScOutline;
-ScOutline* sc_outline_find (const GeglRectangle *rect, GeglBuffer *pixels);
+ScOutline* sc_outline_find (const GeglRectangle *rect,
+ GeglBuffer *pixels,
+ gboolean *ignored_islands);
-void sc_outline_free (ScOutline *self);
+gboolean sc_outline_check_if_single (const GeglRectangle *search_area,
+ GeglBuffer *buffer,
+ ScOutline *existing);
+
+guint sc_outline_length (ScOutline *self);
+
+void sc_outline_free (ScOutline *self);
#endif
diff --git a/operations/common/seamless-clone/seamless-clone-common.c b/operations/common/seamless-clone/seamless-clone-common.c
index 555923e..548d285 100644
--- a/operations/common/seamless-clone/seamless-clone-common.c
+++ b/operations/common/seamless-clone/seamless-clone-common.c
@@ -146,6 +146,11 @@ sc_render_seamless (GeglBuffer *bg,
g_warning ("No preprocessing result given. Stop.");
return FALSE;
}
+ if (cache->error != SC_ERROR_NONE)
+ {
+ g_warning ("The preprocessing result contains an error. Stop.");
+ return FALSE;
+ }
if (gegl_rectangle_is_empty (&cache->mesh_bounds))
{
return TRUE;
@@ -248,26 +253,42 @@ sc_render_seamless (GeglBuffer *bg,
}
ScCache*
-sc_generate_cache (GeglBuffer *fg,
- const GeglRectangle *extents,
- int max_refine_steps)
+sc_generate_cache (GeglBuffer *fg,
+ const GeglRectangle *extents,
+ int max_refine_steps)
{
- ScOutline *outline;
ScCache *result = g_new0 (ScCache, 1);
-
- /* Find an outline around the area of the paste */
- outline = sc_outline_find (extents, fg);
+ gint outline_length = 0;
+ gboolean ignored_islands;
+
+ result->error = SC_ERROR_NONE;
+ result->mesh = NULL;
+ result->sampling = NULL;
+ result->uvt = NULL;
+
+ /* Find an outline around the area of the paste. We will also
+ * need it later to compute the sampling list for each point
+ */
+ result->outline = sc_outline_find (extents, fg, &ignored_islands);
+ outline_length = sc_outline_length (result->outline);
+
+ if (outline_length == 0)
+ result->error = ignored_islands ? SC_ERROR_SMALL_PASTE : SC_ERROR_NO_PASTE;
+ else if (outline_length < 3)
+ result->error = SC_ERROR_SMALL_PASTE;
+ else if (! sc_outline_check_if_single (extents, fg, result->outline))
+ result->error = SC_ERROR_HOLED_OR_SPLIT_PASTE;
+
+ if (result->error != SC_ERROR_NONE)
+ return result;
/* Create a fine mesh from the polygon defined by that outline */
- result->mesh = sc_make_fine_mesh (outline, &result->mesh_bounds,
+ result->mesh = sc_make_fine_mesh (result->outline, &result->mesh_bounds,
max_refine_steps);
/* Now compute the list of points to sample in order to define the
* color of each triangulation vertex */
- result->sampling = sc_mesh_sampling_compute (outline, result->mesh);
-
- /* We need the outline since the sampling relies on it's points */
- result->outline = outline;
+ result->sampling = sc_mesh_sampling_compute (result->outline, result->mesh);
/* For each pixel inside the paste area, cache which triangle contains
* it, and the triangle interpolation parameters for that point */
diff --git a/operations/common/seamless-clone/seamless-clone-common.h b/operations/common/seamless-clone/seamless-clone-common.h
index fcd653d..1dcaa20 100644
--- a/operations/common/seamless-clone/seamless-clone-common.h
+++ b/operations/common/seamless-clone/seamless-clone-common.h
@@ -27,6 +27,13 @@
#include "find-outline.h"
#include "make-mesh.h"
+typedef enum {
+ SC_ERROR_NONE = 0,
+ SC_ERROR_NO_PASTE,
+ SC_ERROR_SMALL_PASTE,
+ SC_ERROR_HOLED_OR_SPLIT_PASTE,
+} ScError;
+
typedef struct {
GeglRectangle bg_rect;
GeglBuffer *fg_buf;
@@ -38,6 +45,7 @@ typedef struct {
} ScColorComputeInfo;
typedef struct {
+ ScError error;
GeglRectangle mesh_bounds;
P2trMesh *mesh;
ScMeshSampling *sampling;
diff --git a/operations/common/seamless-clone/seamless-clone.c b/operations/common/seamless-clone/seamless-clone.c
index acdc1ed..33f5f2d 100644
--- a/operations/common/seamless-clone/seamless-clone.c
+++ b/operations/common/seamless-clone/seamless-clone.c
@@ -133,8 +133,10 @@ process (GeglOperation *operation,
}
g_mutex_unlock (props->mutex);
- return_val = sc_render_seamless (input, aux, o->xoff, o->yoff, output, result, props->preprocess);
-
+ if (props->preprocess->error == SC_ERROR_NONE)
+ return sc_render_seamless (input, aux, o->xoff, o->yoff, output, result, props->preprocess);
+ else
+ return FALSE;
return return_val;
}
[
Date Prev][
Date Next] [
Thread Prev][
Thread Next]
[
Thread Index]
[
Date Index]
[
Author Index]
