home *** CD-ROM | disk | FTP | other *** search
/ Practical Algorithms for Image Analysis / Practical Algorithms for Image Analysis.iso / CH_5.4 / FITCRIT / FITCRIT.C next >
Encoding:
C/C++ Source or Header  |  1999-09-11  |  12.6 KB  |  394 lines
  1. /*
  2.  * fitcrit.c
  3.  *
  4.  * Practical Algorithms for Image Analysis
  5.  *
  6.  * Copyright (c) 1997, 1998, 1999 MLMSoftwareGroup, LLC
  7.  */
  8.  
  9. /* FITCRIT:     program fits lines between high curvature points (critical
  10.  *            points)
  11.  *       usage: fitcrit infile outimg [-l FIT_LENGTH] [-r CORNER_ARC] [-c] [-L]
  12.  */
  13.  
  14. #define NOCURVES 0              /* fit 2 lines to circ curves, not curves */
  15.  
  16. #include <stdio.h>
  17. #include <stdlib.h>
  18. #include <string.h>
  19. #include <images.h>
  20. #include "tiffimage.h"
  21. #include "pcc2.h"               /* for PCC programs */
  22. extern void print_sos_lic ();
  23.  
  24. unsigned char *fcCode;          /* code storage */
  25. long nByteCode;                 /* no. bytes in code storage */
  26. long maxCorner;                 /* maximum arc length of corner curvature */
  27.     /* needed for zzWidth calc in FEATDETERM */
  28. struct featNode *featHead = NULL,  /* linked list of features head/tail */
  29.  *featTail;
  30. long nFeats;                    /* number of ww features */
  31.  
  32. int linkcorner (int, struct point);
  33.  
  34. long xytoline (struct point *, long *, long *, long *);
  35. long wwtofeats (struct wwfeats *, long *, long *, long *);
  36. long usage (short);
  37. long input (int, char **, long *, long *, short *);
  38.  
  39. main (argc, argv)
  40.      int argc;
  41.      char *argv[];
  42. {
  43.   Image *imgO;                  /* pointer to output image structure */
  44.   unsigned char **image;        /* output image array */
  45.   long width, height;           /* image size */
  46.   struct point imgSize;         /* image size */
  47.   short coordFlag;              /* flag = 1, print fit coord.s; or 0 */
  48.   short curveFlag;              /* =0 for curve fit by 2 lines; =1 for curve */
  49.   struct point *data;           /* data curve */
  50.   long nData;                   /* no. coords in data curve */
  51.   long nSegments;               /* number of segments found */
  52.   long nStructs;                /* number of line structures found */
  53.   long drawline8 ();            /* joins points in 8-connected lines */
  54.   long wwtheta ();              /* finds critical points from theta plot */
  55.   long nThetaFeats;             /* no. of features found from plot */
  56.   struct edge edge;             /* lower/upper indices of segment in data */
  57.   long minLength;               /* minimum feature length */
  58.   struct wwPar wwPar;           /* wing-walk parameters */
  59.   long nWWFeats;                /* number of line critical features */
  60.   struct wwfeats *feats;        /* array of output ww features */
  61.   long nLines, nCurves;         /* number of lines and curves fit */
  62.   struct point midArc;          /* middle arc point of curve */
  63.   long x, y;
  64.   long i;
  65.  
  66. /* user input */
  67.   if (input (argc, argv, &minLength, &maxCorner, &coordFlag) < 0)
  68.     return (-1);
  69.   curveFlag = NOCURVES;
  70.  
  71. /* open input PCC file */
  72.   if (pccread (argv[1], &fcCode, &nByteCode, &width, &height) == -1)
  73.     exit (0);
  74.   if (!coordFlag)
  75.     printf ("image size: %dx%d, PCC length = %d\n", width, height, nByteCode);
  76.   imgSize.x = width;
  77.   imgSize.y = height;
  78.  
  79. /* allocate space for data coordinate array */
  80.   if ((data = (struct point *)
  81.        calloc (nByteCode * MAXPERCODE, sizeof (long))) == NULL) {
  82.     printf ("FITPOLYG: not enough memory -- sorry");
  83.     return (-1);
  84.   }
  85.  
  86. /* construct tables of feature chain decodes */
  87.   pccdecodes ();
  88.  
  89. /* perform feature chain decoding */
  90.   pcc2xy (data, &nData);
  91.  
  92.   data[nData++].x = -STOPCODE;
  93.   if ((data = (struct point *)
  94.        realloc (data, nData * sizeof (struct point))) == NULL) {
  95.     printf ("FITPOLYG: not enough memory -- sorry");
  96.     return (-2);
  97.   }
  98.  
  99. /* find x,y coordinates for each line */
  100.   if (xytoline (data, &nData, &nSegments, &nStructs) < 0)
  101.     return (-1);
  102.  
  103. /* determine geometric features in line data */
  104.   wwPar.m = (maxCorner % 2) ? maxCorner : maxCorner + 1;
  105.   wwPar.l = (minLength % 2) ? minLength : minLength - 1;
  106.   if (wwPar.m > wwPar.l - 2) {
  107.     wwPar.m = wwPar.l - 2;
  108.   }
  109.   wwPar.w = (wwPar.l - wwPar.m) / 2;
  110.  
  111.   for (i = 0; i < nData; i++) {
  112.     if (data[i].x != -1) {
  113.       edge.iLow = i;
  114.       linkcorner (WWSTRT, data[edge.iLow]);
  115.       while (data[++i].x >= 0);
  116.       --i;
  117.       edge.iHigh = i;
  118.       nThetaFeats = wwtheta (data, edge, wwPar, curveFlag);
  119.       if (nThetaFeats < 0)
  120.         return (-1);
  121.       linkcorner (WWEND, data[edge.iHigh]);
  122.     }
  123.   }
  124.  
  125. /* write corner features to ww features */
  126.   nWWFeats = nData;
  127.   if ((feats = (struct wwfeats *) calloc (nWWFeats, sizeof (*feats)))
  128.       == NULL) {
  129.     printf ("FITFEAT: nuts, not enough memory for <feats> array");
  130.     return (-3);
  131.   }
  132.  
  133.   wwtofeats (feats, &nWWFeats, &nLines, &nCurves);
  134.  
  135. /* print line features */
  136.   if (!coordFlag)
  137.     printf ("Number of lines = %d, curves = %d\n", nLines, nCurves);
  138.  
  139.   if (coordFlag)
  140.     for (i = 0; i < nWWFeats; i++) {
  141.       if (feats[i].radius == 0.0)
  142.         printf ("%d (LINE): (%3d,%3d) to (%3d,%3d)\n", i, feats[i].strt.x,
  143.                 feats[i].strt.y, feats[i].end.x, feats[i].end.y);
  144.       else {
  145.         printf ("%d (CURVE): (%3d,%3d) to (%3d,%3d), ", i, feats[i].strt.x,
  146.                 feats[i].strt.y, feats[i].end.x, feats[i].end.y);
  147.  
  148.         printf ("radius = %5.2f, center = (%5.2f,%5.2f)\n",
  149.                 feats[i].radius, feats[i].center.x, feats[i].center.y);
  150.       }
  151.     }
  152.  
  153. /* allocate output image */
  154.   imgO = ImageAlloc (height, width, 8);
  155.   image = ImageGetPtr (imgO);
  156.  
  157. /* initialize image */
  158.   for (y = 0; y < height; y++)
  159.     for (x = 0; x < width; x++)
  160.       image[y][x] = 255;
  161.  
  162. /* draw fits into output image */
  163.   for (i = 0; i < nWWFeats; i++) {
  164.     if (feats[i].radius == 0.0) {  /* straight line */
  165.       if (feats[i].strt.x < 0)
  166.         feats[i].strt.x = 0;
  167.       if (feats[i].strt.x >= width)
  168.         feats[i].strt.x = width - 1;
  169.       if (feats[i].strt.y < 0)
  170.         feats[i].strt.y = 0;
  171.       if (feats[i].strt.y >= height)
  172.         feats[i].strt.y = height - 1;
  173.  
  174.       if (feats[i].end.x < 0)
  175.         feats[i].end.x = 0;
  176.       if (feats[i].end.x >= width)
  177.         feats[i].end.x = width - 1;
  178.       if (feats[i].end.y < 0)
  179.         feats[i].end.y = 0;
  180.       if (feats[i].end.y >= height)
  181.         feats[i].end.y = height - 1;
  182.  
  183.       drawline8 (image, imgSize, feats[i].strt, feats[i].end, 0);
  184.     }
  185.     else {                      /* curve -- approx by 2 lines */
  186.       if (feats[i].strt.x < 0)
  187.         feats[i].strt.x = 0;
  188.       if (feats[i].strt.x >= width)
  189.         feats[i].strt.x = width - 1;
  190.       if (feats[i].strt.y < 0)
  191.         feats[i].strt.y = 0;
  192.       if (feats[i].strt.y >= height)
  193.         feats[i].strt.y = height - 1;
  194.  
  195.       midArc.x = (long) (feats[i].center.x + 0.5);
  196.       midArc.y = (long) (feats[i].center.y + 0.5);
  197.       if (feats[i].center.x < 0.0)
  198.         midArc.x = 0;
  199.       if (feats[i].center.x >= width)
  200.         midArc.x = width - 1;
  201.       if (feats[i].center.y < 0)
  202.         midArc.y = 0;
  203.       if (feats[i].center.y >= height)
  204.         midArc.y = height - 1;
  205.  
  206.       if (feats[i].end.x < 0)
  207.         feats[i].end.x = 0;
  208.       if (feats[i].end.x >= width)
  209.         feats[i].end.x = width - 1;
  210.       if (feats[i].end.y < 0)
  211.         feats[i].end.y = 0;
  212.       if (feats[i].end.y >= height)
  213.         feats[i].end.y = height - 1;
  214.  
  215.       drawline8 (image, imgSize, feats[i].strt, midArc, 0);
  216.       drawline8 (image, imgSize, midArc, feats[i].end, 0);
  217.     }
  218.  
  219.  
  220.   }
  221.  
  222. /* write image output file */
  223.   ImageOut (argv[2], imgO);
  224.  
  225.   return (0);
  226. }
  227.  
  228.  
  229. /* WWTOFEATS:   function produces list of line features from linked list
  230.  *            of critical points
  231.  *                  usage: wwtofeats (feats, &nWWFeats, &nLines, &nCurves)
  232.  */
  233.  
  234. long
  235. wwtofeats (feats, nWWFeats, nLines, nCurves)
  236.      struct wwfeats *feats;     /* array of output ww features */
  237.      long *nWWFeats;            /* number of line critical features */
  238.      long *nLines, *nCurves;    /* number of lines and curves fit */
  239. {
  240.   struct featK *featK;          /* corner and curve parameters */
  241.   struct featC *featC;
  242.   struct point lineStrt;        /* start of ww line feature */
  243.   long i;
  244.  
  245. /* go through linked list of critical points and copy features to list */
  246.   featTail = featHead;
  247.   *nWWFeats = 0;
  248.   *nLines = *nCurves = 0;
  249.   for (i = 0; i < 10000; i++) {
  250.     switch (featTail->type) {
  251.     case WWSTRT:               /* start line */
  252.       featK = (struct featK *) featTail->info;
  253.       lineStrt = featK->coord;
  254.       break;
  255.     case WWCORNER:             /* corner */
  256.       featK = (struct featK *) featTail->info;
  257.       feats[*nWWFeats].strt = lineStrt;
  258.       feats[*nWWFeats].end = featK->coord;
  259.       (*nWWFeats)++;
  260.       (*nLines)++;
  261.       lineStrt = featK->coord;
  262.       break;
  263.     case WWCURVE:              /* curve feature */
  264.       featC = (struct featC *) featTail->info;
  265.       feats[*nWWFeats].strt = lineStrt;  /* first store line */
  266.       feats[*nWWFeats].end = featC->trans1;
  267.       (*nWWFeats)++;
  268.       (*nLines)++;
  269.       if (featC->dirn == 1) {   /* then store curve */
  270.         feats[*nWWFeats].strt = featC->trans1;  /* correct order */
  271.         feats[*nWWFeats].end = featC->trans2;
  272.       }
  273.       else {                    /* reverse direction curve */
  274.         feats[*nWWFeats].strt = featC->trans2;
  275.         feats[*nWWFeats].end = featC->trans1;
  276.       }
  277.       feats[*nWWFeats].center = featC->center;
  278.       feats[*nWWFeats].radius = featC->radiusC;
  279.       lineStrt = featC->trans2;
  280.       (*nWWFeats)++;
  281.       (*nCurves)++;
  282.       break;
  283.     case WWEND:                /* end line */
  284.       featK = (struct featK *) featTail->info;
  285.       feats[*nWWFeats].strt = lineStrt;
  286.       feats[*nWWFeats].end = featK->coord;
  287.       (*nWWFeats)++;
  288.       (*nLines)++;
  289.       break;
  290.     }
  291.     featTail = featTail->next;
  292.     if (featTail == NULL)
  293.       break;
  294.   }
  295.   return (0);
  296. }
  297.  
  298.  
  299. /* USAGE:       function gives instructions on usage of program
  300.  *                    usage: usage (flag)
  301.  *              When flag is 1, the long message is given, 0 gives short.
  302.  */
  303.  
  304. long
  305. usage (flag)
  306.      short flag;                /* flag =1 for long message; =0 for short message */
  307. {
  308.  
  309. /* print short usage message or long */
  310.   printf ("USAGE: fitcrit infile outimg [-l FIT_LENGTH] [-r CORNER_ARC] [-c] [-L]\n");
  311.   if (flag == 0)
  312.     return (-1);
  313.  
  314.   printf ("\nfitcrit fits straight lines between critical points\n");
  315.   printf ("(curvature maxima) in the segments of pixel chains;\n");
  316.   printf ("corners are located at the location of intersection of their\n");
  317.   printf ("two boundary lines; curves are located by two straight lines\n");
  318.   printf ("drawn from curve onsets (transition points) to the middle\n");
  319.   printf ("point in the arc of the curve.\n\n");
  320.   printf ("ARGUMENTS:\n");
  321.   printf ("    infile: input filename (PCC)\n");
  322.   printf ("    outimg: input image filename (TIF)\n\n");
  323.   printf ("OPTIONS:\n");
  324.   printf ("  -l FIT_LENGTH: is the arc-length of the fit along the data\n");
  325.   printf ("                 segments; the longer is this length, the greater is\n");
  326.   printf ("                 smoothing, but the less ability to fit small features;\n");
  327.   printf ("                 this is usually chosen as the minimum arc-length between\n");
  328.   printf ("                 critical points on the data.\n");
  329.   printf ("                 (default = %d [connected pixels]. minimum is %d.)\n",
  330.           L_DFLT, L_MIN);
  331.   printf ("  -r CORNER_ARC: maximum arc-length of a corner; since a \n");
  332.   printf ("                 corner feature will usually be rounded, there is a maximum\n");
  333.   printf ("                 arc-length before over which that feature is considered\n");
  334.   printf ("                 a curve and not a corner. (default = %d [connected pixels].\n", M_MAX);
  335.   printf ("             -c: when set, prints out the (x,y) coordinates of the\n");
  336.   printf ("                 straight-line fits between critical points.\n");
  337.   printf ("             -L: print Software License for this module\n");
  338.  
  339.   return (-1);
  340. }
  341.  
  342.  
  343. /* INPUT:       function reads input parameters
  344.  *                  usage: input (argc, argv, &minLength, &coordFlag)
  345.  */
  346.  
  347. #define USAGE_EXIT(VALUE) {usage (VALUE); return (-1);}
  348.  
  349. long
  350. input (argc, argv, minLength, maxCorner, coordFlag)
  351.      int argc;
  352.      char *argv[];
  353.      long *minLength;           /* minimum length of feature */
  354.      long *maxCorner;           /* maximum arc length of corner curvature */
  355.      short *coordFlag;          /* flag = 1, print coordinates of fit; or 0 */
  356. {
  357.   long n;
  358.  
  359.   if (argc == 1)
  360.     USAGE_EXIT (1);
  361.   if (argc == 2)
  362.     USAGE_EXIT (0);
  363.  
  364.   *minLength = L_DFLT;
  365.   *maxCorner = M_MAX;
  366.   *coordFlag = 0;
  367.  
  368.   for (n = 3; n < argc; n++) {
  369.     if (strcmp (argv[n], "-l") == 0) {
  370.       if (++n == argc)
  371.         USAGE_EXIT (0);
  372.       *minLength = (long) atol (argv[n]);
  373.     }
  374.     else if (strcmp (argv[n], "-r") == 0) {
  375.       if (++n == argc)
  376.         usage (0);
  377.       *maxCorner = (long) atol (argv[n]);
  378.     }
  379.     else if (strcmp (argv[n], "-c") == 0)
  380.       *coordFlag = 1;
  381.     else if (strcmp (argv[n], "-L") == 0) {
  382.       print_sos_lic ();
  383.       exit (0);
  384.     }
  385.     else
  386.       USAGE_EXIT (0);
  387.   }
  388.  
  389.   if (*minLength < L_MIN)
  390.     *minLength = L_MIN;
  391.  
  392.   return (0);
  393. }
  394.