Make Pambackground find mid-row background

git-svn-id: http://svn.code.sf.net/p/netpbm/code/trunk@192 9d0c8265-081b-0410-96cb-a4ca84ce46f8

1 files changed, 282 insertions, 80 deletions

diff --git a/editor/pambackground.c b/editor/pambackground.c
index 92e1fce2..8911adf0 100644
--- a/editor/pambackground.c
+++ b/editor/pambackground.c
@@ -111,17 +111,14 @@ selectBackground(struct pam * const pamP,
 
     tuple bg;  /* Reference to one of ul, ur, ll, lr */
 
-    if (pnm_tupleequal(pamP, ul, ur)) {
-        if (pnm_tupleequal(pamP, ll, ul))
-            bg = ul;
-        else if (pnm_tupleequal(pamP, lr, ul))
-            bg = ul;
-    } else if (pnm_tupleequal(pamP, ll, lr)) {
-        if (pnm_tupleequal(pamP, ul, ll))
-            bg = ll;
-        else if (pnm_tupleequal(pamP, ur, ll))
-            bg = ll;
-    } else {
+    if (pnm_tupleequal(pamP, ul, ur) &&
+        (pnm_tupleequal(pamP, ul, ll) ||
+         pnm_tupleequal(pamP, ul, lr)))
+        bg = ul;
+    else if (pnm_tupleequal(pamP, ll, lr) &&
+             pnm_tupleequal(pamP, lr, ul))
+        bg = ll;
+    else {
         /* No 3 corners are same color; look for 2 corners */
         if (pnm_tupleequal(pamP, ul, ur))  /* top edge */
             bg = ul;
@@ -144,9 +141,9 @@ selectBackground(struct pam * const pamP,
 
 
 static void
-computeBackground(struct pam * const pamP,
-                  bool         const verbose,
-                  tuple *      const bgColorP) {
+determineBackgroundColor(struct pam * const pamP,
+                         bool         const verbose,
+                         tuple *      const bgColorP) {
 /*----------------------------------------------------------------------------
    Determine what color is the background color of the image in the
    file represented by *pamP.
@@ -195,49 +192,276 @@ computeBackground(struct pam * const pamP,
 }
 
 
+static unsigned char const PT_UNKNOWN = 0;
+static unsigned char const PT_BG      = 1;
+static unsigned char const PT_FG      = 2;
+
+
+static unsigned char **
+newPi(unsigned int const width,
+      unsigned int const height) {
+
+    unsigned char ** pi;
+    unsigned int row;
+
+    MALLOCARRAY(pi, height);
+    if (pi == NULL)
+        pm_error("Out of memory allocating %u row pointers", height);
+    for (row = 0; row < height; ++row) {
+        MALLOCARRAY(pi[row], width);
+        if (pi[row] == NULL)
+            pm_error("Out of memory allocating row %u", row);
+    }
+    return pi;
+}
+
+
 
 static void
-computeOutputRow(struct pam * const inpamP,
-                 tuple *      const inputTuplerow,
-                 tuple        const backgroundColor,
-                 struct pam * const outpamP,
-                 tuple *      const outputTuplerow,
-                 tuple        const foreground,
-                 tuple        const background) {
+destroyPi(const unsigned char *const * const pi,
+          unsigned int                 const height) {
 
+    unsigned int row;
+
+    for (row = 0; row < height; ++row)
+        free((void*)pi[row]);
+
+    free((void*)pi);
+}
+
+
+
+static void
+initPi(unsigned char **   const pi,
+       const struct pam * const pamP,
+       tuple              const backgroundColor) {
+/*----------------------------------------------------------------------------
+  Set the initial info about every pixel in pi[][].
+
+  Read through the image in the file described by *inpamP and set each
+  pixel which is not of background color, and therefore obviously
+  foreground, to type PT_FG.  Set every other pixel to PT_UNKNOWN.
+-----------------------------------------------------------------------------*/
+    tuple * tuplerow;
+    unsigned int row;
+
+    tuplerow  = pnm_allocpamrow(pamP);
+
+    for (row = 0; row < pamP->height; ++row) {
+        unsigned int col;
+
+        pnm_readpamrow(pamP, tuplerow);
+
+        for (col = 0; col < pamP->width; ++col) {
+            pi[row][col] =
+                pnm_tupleequal(pamP, tuplerow[col], backgroundColor) ?
+                PT_UNKNOWN : PT_FG;
+        }
+    }
+    pnm_freepamrow(tuplerow);
+}
+
+
+
+static void
+setEdges(unsigned char ** const pi,
+         unsigned int     const width,
+         unsigned int     const height) {
+/*----------------------------------------------------------------------------
+  Do the four edges.
+
+  Anything of background color in an edge is background.  Pixel type
+  PT_UNKNOWN implies background color, so we change all PT_UNKNOWN pixels
+  to PT_BG.
+-----------------------------------------------------------------------------*/
+    unsigned int row, col;
+
+    for (col = 0; col < width; ++col) {
+        if (pi[0][col] == PT_UNKNOWN)
+            pi[0][col] = PT_BG;
+
+        if (pi[height-1][col] == PT_UNKNOWN)
+            pi[height-1][col] = PT_BG;
+    }
+    for (row = 0; row < height; ++row) {
+        if (pi[row][0] == PT_UNKNOWN)
+            pi[row][0] = PT_BG;
+
+        if (pi[row][width-1] == PT_UNKNOWN)
+            pi[row][width-1] = PT_BG;
+    }
+}
+
+
+
+static void
+expandBackgroundHoriz(unsigned char ** const pi,
+                      unsigned int     const width,
+                      unsigned int     const height,
+                      bool *           const expandedP) {
+/*----------------------------------------------------------------------------
+   In every row, expand the background rightward from any known background
+   pixel through all consecutive unknown pixels.
+
+   Then do the same thing leftward.
+
+   Iff we managed to expand the background at all, return *expandedP == TRUE.
+-----------------------------------------------------------------------------*/
+    unsigned int row;
+    bool expanded;
+
+    for (row = 1, expanded = FALSE; row < height-1; ++row) {
+        int col;
+
+        for (col = 1; col < width - 1; ++col) {
+            if (pi[row][col] == PT_UNKNOWN && pi[row][col-1] == PT_BG) {
+                expanded = TRUE;
+                /* Set the whole consecutive row of unknown to background */
+                for (; pi[row][col] == PT_UNKNOWN && col < width - 1; ++col)
+                    pi[row][col] = PT_BG;
+            }
+        }
+
+        for (col = width-2; col > 0; --col) {
+            if (pi[row][col] == PT_UNKNOWN && pi[row][col+1] == PT_BG) {
+                expanded = TRUE;
+                /* Set the whole consecutive row of unknown to background */
+                for (; pi[row][col] == PT_UNKNOWN && col > 0; --col)
+                    pi[row][col] = PT_BG;
+            }
+        }
+    }
+    *expandedP = expanded;
+}
+
+
+
+static void
+expandBackgroundVert(unsigned char ** const pi,
+                     unsigned int     const width,
+                     unsigned int     const height,
+                     bool *           const expandedP) {
+/*----------------------------------------------------------------------------
+   In every column, expand the background downward from any known background
+   pixel through all consecutive unknown pixels.
+
+   Then do the same thing upward.
+
+   Iff we managed to expand the background at all, return *expandedP == TRUE.
+-----------------------------------------------------------------------------*/
     unsigned int col;
-    unsigned int firstForegroundCol;
-        // Column number of first column, going from the left, that is
-        // not the background color.
-    unsigned int endForegroundCol;
-        // Column number of the last column, going from the right,
-        // that is the background color.
-
-    col = 0;
-    while (col < inpamP->width &&
-           pnm_tupleequal(inpamP, inputTuplerow[col], backgroundColor))
-        ++col;
-
-    firstForegroundCol = col;
-
-    col = inpamP->width;
-    while (col > firstForegroundCol && 
-           pnm_tupleequal(inpamP, inputTuplerow[col-1], backgroundColor))
-        --col;
-
-    endForegroundCol = col;
-
-    // If the row is all background, 'firstForegroundCol' and
-    // 'endForegroundCol' are both one past the right edge.
-            
-    for (col = 0; col < firstForegroundCol; ++col)
-        outputTuplerow[col] = background;
-
-    for (col = firstForegroundCol; col < endForegroundCol; ++col)
-        outputTuplerow[col] = foreground;
-
-    for (col = endForegroundCol; col < outpamP->width; ++col)
-        outputTuplerow[col] = background;
+    bool expanded;
+
+    for (col = 1, expanded = FALSE; col < height-1; ++col) {
+        int row;
+
+        for (row = 1; row < height - 1; ++row) {
+            if (pi[row][col] == PT_UNKNOWN && pi[row-1][col] == PT_BG) {
+                expanded = TRUE;
+                /* Set the whole consecutive col of unknown to background */
+                for (; pi[row][col] == PT_UNKNOWN && row < height - 1; ++row)
+                    pi[row][col] = PT_BG;
+            }
+        }
+
+        for (row = height-2; row > 0; --row) {
+            if (pi[row][col] == PT_UNKNOWN && pi[row+1][col] == PT_BG) {
+                expanded = TRUE;
+                /* Set the whole consecutive col of unknown to background */
+                for (; pi[row][col] == PT_UNKNOWN && row > 0; --row)
+                    pi[row][col] = PT_BG;
+            }
+        }
+    }
+    *expandedP = expanded;
+}
+
+
+
+static void
+findBackgroundPixels(struct pam *                   const inpamP,
+                     tuple                          const backgroundColor,
+                     bool                           const verbose,
+                     const unsigned char * const ** const piP) {
+/*----------------------------------------------------------------------------
+   Figure out which pixels of the image are background.  Read the
+   image from the input file described by *inpamP (positioned now to
+   the start of the raster) and generate the matrix *piP telling which
+   pixels are background and which are foreground, given that the
+   background color is 'backgroundColor'.
+
+   Note that it isn't as simple as finding which pixels are of color
+   'backgroundColor'.  They have to be part of a contiguous region that
+   touches one of the 4 edges of the image.
+
+   In the matrix we return, there is one element for each pixel in the
+   image, and it has value PT_BG or PT_FG.
+-----------------------------------------------------------------------------*/
+    unsigned char ** pi;
+    bool backgroundComplete;
+    unsigned int passes;
+
+    pi = newPi(inpamP->width, inpamP->height);
+
+    initPi(pi, inpamP, backgroundColor);
+
+    setEdges(pi, inpamP->width, inpamP->height);
+
+    backgroundComplete = FALSE;
+    passes = 0;
+    
+    while (!backgroundComplete) {
+        bool expandedHoriz, expandedVert;
+
+        expandBackgroundHoriz(pi, inpamP->width, inpamP->height,
+                              &expandedHoriz);
+    
+        expandBackgroundVert(pi, inpamP->width, inpamP->height,
+                             &expandedVert);
+
+        backgroundComplete = !expandedHoriz && !expandedVert;
+
+        ++passes;
+    }
+
+    if (verbose)
+        pm_message("Background found in %u passes", passes);
+
+    *piP = (const unsigned char * const *)pi;
+}
+
+                     
+
+static void
+writeOutput(const struct pam *            const inpamP,
+            const unsigned char * const * const pi) {
+
+    tuple black, white;
+    tuple * outputTuplerow;
+        /* This is not a normal tuplerow; it is just pointers to either
+           'black' or 'white'
+        */
+    unsigned int row;
+    struct pam outpam;
+
+    initOutpam(inpamP, &outpam);
+
+    allocateOutputPointerRow(outpam.width, &outputTuplerow);
+    pnm_createBlackTuple(&outpam, &black);
+    createWhiteTuple(&outpam, &white);
+
+    pnm_writepaminit(&outpam);
+
+    for (row = 0; row < outpam.height; ++row) {
+        unsigned int col;
+        for (col = 0; col < outpam.width; ++col)
+            outputTuplerow[col] = pi[row][col] == PT_BG ? white : black;
+
+        pnm_writepamrow(&outpam, outputTuplerow);
+    }
+    pnm_freepamtuple(white);
+    pnm_freepamtuple(black);
+    free(outputTuplerow);
 }
 
 
@@ -247,15 +471,10 @@ main(int argc, char *argv[]) {
 
     struct cmdlineInfo cmdline;
     struct pam inpam;
-    struct pam outpam;
     FILE * ifP;
-    tuple * inputTuplerow;
-    tuple * outputTuplerow;
-        // Not a regular tuple row -- just pointer array
-    unsigned int row;
     pm_filepos rasterpos;
-    tuple black, white;
     tuple backgroundColor;
+    const unsigned char * const * pi;
     
     pnm_init(&argc, argv);
 
@@ -267,36 +486,19 @@ main(int argc, char *argv[]) {
 
     pm_tell2(ifP, &rasterpos, sizeof(rasterpos));
 
-    computeBackground(&inpam, cmdline.verbose, &backgroundColor);
-
-    initOutpam(&inpam, &outpam);
-
-    inputTuplerow  = pnm_allocpamrow(&inpam);
-
-    allocateOutputPointerRow(outpam.width, &outputTuplerow);
-    pnm_createBlackTuple(&outpam, &black);
-    createWhiteTuple(&outpam, &white);
-
-    pnm_writepaminit(&outpam);
+    determineBackgroundColor(&inpam, cmdline.verbose, &backgroundColor);
 
     pm_seek2(ifP, &rasterpos, sizeof(rasterpos));
 
-    for (row = 0; row < outpam.height; ++row) {
-        pnm_readpamrow(&inpam, inputTuplerow);
+    findBackgroundPixels(&inpam, backgroundColor, cmdline.verbose, &pi);
 
-        computeOutputRow(&inpam, inputTuplerow, backgroundColor,
-                         &outpam, outputTuplerow, black, white);
+    writeOutput(&inpam, pi);
 
-        pnm_writepamrow(&outpam, outputTuplerow);
-    }
+    destroyPi(pi, inpam.height);
 
     pm_close(ifP);
 
-    pnm_freepamrow(inputTuplerow);
-    free(outputTuplerow);
     pnm_freepamtuple(backgroundColor);
-    pnm_freepamtuple(white);
-    pnm_freepamtuple(black);
     
     return 0;
 }