home *** CD-ROM | disk | FTP | other *** search
/ RISC DISC 3 / RISC_DISC_3.iso / resources / etexts / gems / gemsv / ch6_4 / vectorize.c < prev   
Encoding:
C/C++ Source or Header  |  1994-11-22  |  6.1 KB  |  207 lines
  1. #include <string.h>
  2. #include <stdlib.h>
  3. #include <limits.h>
  4. #include "chainCode.h"
  5. #include "pt2.h"
  6.  
  7. /* DEFINITION OF THE CONSTANTS */
  8.  
  9. #define CONTOUR 'c'
  10. #define VISITED 'v'
  11. #define BLACK '1'
  12. #define WHITE '0'
  13.  
  14. /* DEFINITION OF THE MACROS */
  15.  
  16. #define PIX(a,b) ((b) * f_size.x + (a))
  17. #define PIX2(a,b) ((b) * size->x + (a))
  18. #define MIN(x,y) ((x)<(y) ? (x) : (y))
  19. #define MAX(x,y) ((x)>(y) ? (x) : (y))
  20.  
  21.  
  22. /*************************************************************/
  23. /*                                                           */
  24. /* This is the main function. It receives as a parameter a   */
  25. /* bitmap image of size 'size' and outputs a chain code.     */ 
  26. /* The following constraints are placed on the bitmap:       */
  27. /* + Each pixel is encoded as a char.                        */
  28. /* + Only white (0) and black (1) pixels are taken into      */
  29. /*   account.                                                */
  30. /* + The shape to encode should have no holes and should be  */
  31. /*   in a single piece.                                      */
  32. /*                                                           */
  33. /*************************************************************/
  34.  
  35. chainCode* encode(pt2 *size, char *bitmap)
  36. {
  37. static pt2    contour_dir[8] = {{ 1, 0},
  38.                 { 0,-1},
  39.                 {-1, 0},
  40.                 { 0, 1},
  41.                 { 1,-1},
  42.                 {-1,-1},
  43.                 {-1, 1},
  44.                 { 1, 1}};
  45. chainCode *code1,
  46.           code4;
  47. char *fatmap,
  48.      direction_code[8] = {'0','2','4','6','1','3','5','7'};
  49. int i,j,u,v,
  50.     flag,
  51.     d, distance,
  52.     last_dir;
  53. pt2 pixel,
  54.     test_pixel,
  55.     start_pixel,
  56.     f_size,
  57.     bbox[2] = {{INT_MAX, INT_MAX},
  58.                {-INT_MAX, -INT_MAX}};
  59.  
  60. /* CREATE AN EMPTY CHAIN CODE TO RETURN THE RESULT */
  61. code1 = new chainCode();
  62.  
  63. /* RESCAN THE BITMAP AT A GREATER RESOLUTION (4x4 GREATER) */
  64. /* ADD TWO BLANK LINES TO THE LEFT, RIGHT, TOP AND BOTTOM  */
  65. /* OF THE FATMAP. THESE COULD BE NECESSARY TO AVOID THE    */
  66. /* CONTOUR TO BE DRAWN OUTSIDE OF THE BOUNDS OF THE MATRIX */
  67.  
  68. f_size.x = 2 + SCALE*size->x + 2;
  69. f_size.y = 2 + SCALE*size->y + 2;
  70. fatmap = malloc(f_size.x * f_size.y * sizeof(char));
  71. for (i=0; i<f_size.x * f_size.y; i++)
  72.     fatmap[i] = WHITE;
  73. for (j=0; j<size->y; j++)
  74.     for (i=0; i<size->x; i++)
  75.         if (bitmap[PIX2(i,j)] == BLACK)
  76.             for(v=0; v<SCALE; v++)
  77.                 for(u=0; u<SCALE; u++)
  78.                     fatmap[PIX(2+4*i+u, 2+4*j+v)] = BLACK;
  79.  
  80. /* GENERATE THE CONTOUR OF THE BITMAP USING 4 SUCCESSIVE */
  81. /* PASSES: FOR EACH DIRECTION, WE SCAN EACH LINE UNTIL   */
  82. /* WE REACH A BLACK PIXEL: THE PIXEL JUST BEFORE IT IS A */
  83. /* CONTOUR PIXEL                                         */
  84.  
  85. /* PASS 1: LEFTWARDS */
  86. for (j=0; j<f_size.y; j++)
  87.     for(i=1; i<f_size.x; i++)
  88.             if (fatmap[PIX(i,j)] == BLACK){
  89.                 if (flag == 0) {
  90.                         fatmap[PIX(i-1, j)] = CONTOUR;
  91.                         flag = 1;
  92.             }
  93.         }
  94.             else
  95.                     flag = 0;
  96.  
  97. /* PASS 2: RIGHTWARDS */
  98. for (j=0; j<f_size.y; j++)
  99.     for (i=f_size.x - 1; i>=0; i--)
  100.             if (fatmap[PIX(i,j)] == BLACK){
  101.                 if (flag == 0) {
  102.                         fatmap[PIX(i+1, j)] = CONTOUR;
  103.                         flag = 1;
  104.             }
  105.         }
  106.             else
  107.                     flag = 0;
  108.  
  109. /* PASS 3: DOWNWARDS */
  110. flag = 0;
  111. for (i=0; i<f_size.x; i++)
  112.     for (j=0; j<f_size.y; j++)
  113.             if (fatmap[PIX(i,j)] == BLACK){
  114.                 if (flag == 0) {
  115.                         fatmap[PIX(i, j-1)] = CONTOUR;
  116.                         flag = 1;
  117.             }
  118.         }
  119.             else
  120.                     flag = 0;
  121.  
  122. /* PASS 4: UPWARDS */
  123. flag = 0;
  124. for (i=0; i<f_size.x; i++)
  125.     for (j=f_size.y - 1; j>=0; j--)
  126.             if (fatmap[PIX(i,j)] == BLACK){
  127.                 if (flag == 0) {
  128.                         fatmap[PIX(i, j+1)] = CONTOUR;
  129.                         flag = 1;
  130.             }
  131.         }
  132.             else
  133.                     flag = 0;
  134.  
  135.  
  136. /* COMPUTE THE BOUNDING BOX OF THE CHARACTER (L,T,R,B) */
  137. for (j=0; j<f_size.y; j++)
  138.     for(i=1; i<f_size.x; i++)   
  139.         if (fatmap[PIX(i,j)]==CONTOUR){
  140.             bbox[0].x = MIN(i, bbox[0].x);
  141.             bbox[0].y = MIN(j, bbox[0].y);
  142.             bbox[1].x = MAX(i, bbox[1].x);
  143.             bbox[1].y = MAX(j, bbox[1].y);
  144.         }
  145.  
  146. /* DETERMINE THE CONTOUR PIXEL CLOSEST TO THE UPPER LEFT CORNER */
  147. /* OF THE BOUNDING BOX                                          */
  148.  
  149. distance = INT_MAX;
  150. for (j=0; j<f_size.y; j++)
  151.     for(i=1; i<f_size.x; i++)   
  152.         if (fatmap[PIX(i,j)]==CONTOUR){
  153.             d = (i-bbox[0].x) * (i-bbox[0].x) + (j-bbox[0].y) * (j-bbox[0].y);
  154.             if (d < distance) {
  155.                 distance = d;
  156.                 start_pixel.x = i;
  157.                 start_pixel.y = j;
  158.             }
  159.         }
  160.  
  161. /* BEGIN THE ENCODING PROCEDURE */
  162. pixel.x = start_pixel.x;
  163. pixel.y = start_pixel.y;
  164. fatmap[PIX(pixel.x, pixel.y)] = VISITED;
  165. last_dir = 4;
  166. while(0 < 1) {
  167.     /* AT FIRST, CHECK THE PIXEL IN THE LAST KNOWN DIRECTION */
  168.     addPt2(&pixel, &contour_dir[last_dir], &test_pixel);
  169.     if (fatmap[PIX(test_pixel.x, test_pixel.y)] == CONTOUR){
  170.         pixel.x = test_pixel.x;
  171.         pixel.y = test_pixel.y;
  172.         fatmap[PIX(pixel.x, pixel.y)] = VISITED;
  173.         code4.add(direction_code[last_dir]);
  174.         }
  175.     /* CHECK ALL THE POSSIBLE DIRECTIONS, CLOCKWISE */
  176.     for (i=0;i<8;i++) {
  177.         addPt2(&pixel, &contour_dir[i], &test_pixel);
  178.         if (fatmap[PIX(test_pixel.x, test_pixel.y)] == CONTOUR){
  179.             pixel.x = test_pixel.x;
  180.             pixel.y = test_pixel.y;
  181.             fatmap[PIX(pixel.x, pixel.y)] = VISITED;
  182.             code4.add(direction_code[i]);
  183.             last_dir = i;
  184.             break;
  185.             }
  186.         }
  187.     if (i == 8)
  188.         break;
  189. }
  190.  
  191. /* WRITE THE LAST MOVE TO THE OUTPUT VECTOR */
  192. for (i=0; i<8; i++) {
  193.     subPt2(&start_pixel, &pixel, &test_pixel);
  194.     if (test_pixel.x==contour_dir[i].x && test_pixel.y==contour_dir[i].y){
  195.         code4.add(direction_code[i]);
  196.         break;
  197.         }
  198.     }
  199.  
  200. /* POST-PROCESSING LOOP:                                  */
  201. /* GO BACK TO A LOWER RESOLUTION BY FILTERING THE 4x CODE */
  202.  
  203. code1 = code4.postProcess();
  204. return code1;
  205. }
  206.  
  207.