thin-image.c

这是关于细化算法的一个源码

/* 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 "message.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 */ 
		    LOG3("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)
		{ 
		    LOG1 ("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:
	{
	  LOG1 ("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);
		      } 
            } 
           }
          } 
          LOG2 ("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;
                  } 
              } 
          } 
          LOG2("thin1: pass %d, %d pixels deleted\n", pc, count); 
      } 
      free (qb); 
}