home *** CD-ROM | disk | FTP | other *** search
/ InfoMagic Source Code 1993 July / THE_SOURCE_CODE_CD_ROM.iso / gnu / fontutils-0.6 / imageto / extract.c < prev    next >
Encoding:
C/C++ Source or Header  |  1992-10-02  |  7.5 KB  |  240 lines
  1. /* extract.c: operations on bitmaps.  These could be put in
  2.    lib/bitmap.c, but since they are not particularly common
  3.    operations, we may as well define them separately for now.
  4.  
  5. Copyright (C) 1992 Free Software Foundation, Inc.
  6.  
  7. This program is free software; you can redistribute it and/or modify
  8. it under the terms of the GNU General Public License as published by
  9. the Free Software Foundation; either version 2, or (at your option)
  10. any later version.
  11.  
  12. This program is distributed in the hope that it will be useful,
  13. but WITHOUT ANY WARRANTY; without even the implied warranty of
  14. MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15. GNU General Public License for more details.
  16.  
  17. You should have received a copy of the GNU General Public License
  18. along with this program; if not, write to the Free Software
  19. Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.  */
  20.  
  21. #include "config.h"
  22.  
  23. #include "bitmap.h"
  24. #include "bounding-box.h"
  25. #include "report.h"
  26.  
  27. #include "bitmap2.h"
  28. #include "extract.h"
  29. #include "main.h"
  30. #include "input-img.h"
  31. #include "input-pbm.h"
  32.  
  33. static bitmap_type *get_image_row (boolean, unsigned);
  34. static unsigned *image_row_transitions (bitmap_type);
  35.  
  36.  
  37.  
  38.  
  39. /* Combine the images in the bitmaps B1 and B2, returning the result in
  40.    B1.  The relative position of the bitmaps is given by the bounding
  41.    boxes BB1 and BB2.  We update the bounding box, also.  */
  42.  
  43. void
  44. combine_images (bitmap_type *b1, bitmap_type b2,
  45.                 bounding_box_type *bb1, bounding_box_type bb2)
  46. {
  47.   int this_row, this_col;
  48.   bitmap_type whole_bitmap;
  49.   bounding_box_type whole_bb;
  50.   
  51.   /* If either of the bitmaps are nonexistent, we have nothing
  52.      significant to do.  */
  53.   if (BITMAP_BITS (b2) == NULL)
  54.     return;
  55.   if (BITMAP_BITS (*b1) == NULL)
  56.     {
  57.       *b1 = b2;
  58.       return;
  59.     }
  60.  
  61.   MIN_ROW (whole_bb) = MIN (MIN_ROW (*bb1), MIN_ROW (bb2));
  62.   MAX_ROW (whole_bb) = MAX (MAX_ROW (*bb1), MAX_ROW (bb2));
  63.   MIN_COL (whole_bb) = MIN (MIN_COL (*bb1), MIN_COL (bb2));
  64.   MAX_COL (whole_bb) = MAX (MAX_COL (*bb1), MAX_COL (bb2));
  65.  
  66.   whole_bitmap = new_bitmap (bb_to_dimensions (whole_bb));
  67.   
  68.   /* First, copy the first image in.  */
  69.   for (this_row = MIN_ROW (*bb1); this_row <= MAX_ROW (*bb1); this_row++)
  70.     {
  71.       one_byte *target_row
  72.         = BITMAP_BITS (whole_bitmap)
  73.           + (this_row - MIN_ROW (whole_bb)) * BITMAP_WIDTH (whole_bitmap)
  74.           + MIN_COL (*bb1) - MIN_COL (whole_bb);
  75.       one_byte *source_row
  76.         = BITMAP_BITS (*b1)
  77.           + (this_row - MIN_ROW (*bb1)) * BITMAP_WIDTH (*b1);
  78.         
  79.       memcpy (target_row, source_row, BITMAP_WIDTH (*b1));
  80.     }
  81.  
  82.   /* Put the second image in.  */
  83.   for (this_row = MIN_ROW (bb2); this_row <= MAX_ROW (bb2); this_row++)
  84.     for (this_col = MIN_COL (bb2); this_col < MAX_COL (bb2); this_col++)
  85.       {
  86.         if (BITMAP_PIXEL (b2, this_row - MIN_ROW (bb2),
  87.                           this_col - MIN_COL (bb2)) == BLACK)
  88.           BITMAP_PIXEL (whole_bitmap, this_row - MIN_ROW (whole_bb),
  89.                         this_col - MIN_COL (whole_bb))
  90.             = BLACK;
  91.       }
  92.  
  93.   free_bitmap (b1);
  94.   *b1 = whole_bitmap;
  95.   *bb1 = whole_bb;
  96. }
  97.  
  98. /* Get the next image row of width WIDTH, ignoring leading white rows.
  99.    Return the columns at which there are black-to-white or white-black
  100.    transitions in TRANSITIONS.  */
  101.  
  102. bitmap_type *
  103. some_black_to_all_white_row (unsigned width, unsigned **transitions)
  104. {
  105.   bitmap_type *new = get_image_row (false, width);
  106.   if (new == NULL)
  107.     return NULL;
  108.  
  109.   *transitions = image_row_transitions (*new);
  110.   return new;
  111. }
  112.  
  113.  
  114. /* Get the next image row, including leading blank rows, concatenating
  115.    it below B with one blank row between.  Otherwise like
  116.    `some_black_to_all_white_row'.  */
  117.  
  118. bitmap_type *
  119. append_next_image_row (bitmap_type b, unsigned width, unsigned **transitions)
  120. {
  121.   bitmap_type *new = XTALLOC1 (bitmap_type);
  122.   bitmap_type *next = get_image_row (true, width);
  123.  
  124.   if (next == NULL)
  125.     return NULL;
  126.   
  127.   *new = bitmap_vconcat (b, *next);
  128.   *transitions = image_row_transitions (*new);
  129.   return new;
  130. }
  131.  
  132. /* Because scanlines take a relatively long time to read, we will want
  133.    some kind of status report.  */
  134.  
  135. #define REPORT_SCANLINE() if (++scanline_count % 100 == 0) REPORT (".")
  136.  
  137. /* Read scanlines of width WIDTH from the image file until we get one
  138.    that has at least one black pixel in it (i.e., found part of a
  139.    character).  Then read scanlines until we get one that is entirely
  140.    white.  If KEEP_LEADING_WHITE_ROWS, then include the white rows we
  141.    found at the beginning in the returned bitmap; otherwise, it's just
  142.    the rows from the first-black to the one before the all-white.  */
  143.  
  144. static bitmap_type *
  145. get_image_row (boolean keep_leading_white_rows, unsigned width)
  146. {
  147.   static unsigned scanline_count = 0;
  148.   bitmap_type *bitmap;
  149.   boolean found_white_row;
  150.   one_byte *image;
  151.   unsigned rows_used, rows_allocated;
  152.   boolean found_black_row = false;
  153.   one_byte *scanline = xmalloc (width);
  154.   unsigned white_row_count = 0;
  155.   
  156.   while ((*image_get_scanline) (scanline))
  157.     {
  158.       REPORT_SCANLINE ();
  159.       
  160.       found_black_row = memchr (scanline, BLACK, width) != NULL;
  161.       if (found_black_row)
  162.         break;
  163.       
  164.       white_row_count++;
  165.     }
  166.   
  167.   /* If reached end of the image before finding a black row, return NULL.  */
  168.   if (!found_black_row)
  169.     return NULL;
  170.   
  171.   /* Initialize the image to either the scanline with some black that we
  172.      just found, or to a bitmap with as many all-white rows as we've
  173.      seen, depending on `keep_leading_white_rows'.  */
  174.   rows_used = 1;
  175.   if (keep_leading_white_rows && white_row_count > 0)
  176.     { /* We clear the last row unnecessarily, since the next we do is
  177.          memcpy into it -- but that's better than realloc-ing.  */
  178.       image = xcalloc (white_row_count + 1, width);
  179.       rows_used += white_row_count;
  180.       memcpy (image + white_row_count * width, scanline, width);
  181.       free (scanline);
  182.     }
  183.   else
  184.     image = scanline;
  185.  
  186.   /* Found the row with a black pixel; now look for the all-white row.
  187.      When we start off here, we've allocated exactly as much space as
  188.      we've used so far.  */
  189.   rows_allocated = rows_used;
  190.   found_white_row = false;
  191.   while (!found_white_row)
  192.     { /* Since we only need one more row at a time, we don't need a
  193.          `while' loop here.  */
  194.       if (rows_used + 1 > rows_allocated)
  195.         { /* Perhaps doubling is the wrong thing to do here, as it may
  196.              waste quite a bit of memory.  But it's simple.  */
  197.           rows_allocated += 100 /* ;<<= 1*/;
  198.           image = xrealloc (image, rows_allocated * width);
  199.     }
  200.  
  201.       scanline = image + rows_used * width;
  202.       if (!(*image_get_scanline) (scanline))
  203.         break;
  204.       REPORT_SCANLINE ();
  205.       rows_used++;
  206.       found_white_row = memchr (scanline, BLACK, width) == NULL;
  207.     }
  208.  
  209.   bitmap = XTALLOC1 (bitmap_type);
  210.   BITMAP_WIDTH (*bitmap) = width;
  211.   BITMAP_HEIGHT (*bitmap) = rows_used;
  212.   BITMAP_BITS (*bitmap) = image;
  213.  
  214.   return bitmap;
  215. }
  216.  
  217.  
  218. /* Return a vector of the column numbers at which B changes from black
  219.    to white or white to black, terminated with an element which is B's
  220.    width + 1.  */
  221.  
  222. static unsigned *
  223. image_row_transitions (bitmap_type b)
  224. {
  225.   unsigned *transitions;
  226.   unsigned row, col;
  227.   unsigned width = BITMAP_WIDTH (b);
  228.   one_byte *or_of_all = xcalloc (width, 1);
  229.  
  230.   for (row = 0; row < BITMAP_HEIGHT (b); row++)
  231.     for (col = 0; col < width; col++)
  232.       or_of_all[col] |= BITMAP_PIXEL (b, row, col);
  233.         
  234.   /* We use `or_of_all' to find transitions: its ith column is 1
  235.      if any row in the image had a black pixel at the ith column.  */
  236.   transitions = bitmap_find_transitions (or_of_all, width);
  237.   
  238.   return transitions;
  239. }
  240.