[gegl/soc-2011-seamless-clone: 34/37] Handle many error cases in the outline finding for seamless cloning



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, &current)
-            && ! is_opaque_island (search_area, buffer, format, &current))
+        if (is_opaque (search_area, buffer, format, &current))
           {
-            found = TRUE;
-            break;
+            if (is_opaque_island (search_area, buffer, format, &current))
+              {
+                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, &current);
+          hit = sc_point_eq (&current, 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, &current)))
+            {
+              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]