home *** CD-ROM | disk | FTP | other *** search
/ Practical Algorithms for Image Analysis / Practical Algorithms for Image Analysis.iso / TARFILE.GZ / tarfile / ch_5.7 / xsgll / sall.c < prev    next >
Encoding:
C/C++ Source or Header  |  1999-09-11  |  7.6 KB  |  295 lines
  1. /* 
  2.  * sall.c
  3.  * 
  4.  * Practical Algorithms for Image Analysis
  5.  * 
  6.  * Copyright (c) 1997, 1998, 1999 MLMSoftwareGroup, LLC
  7.  */
  8.  
  9. /*
  10.  * SALL
  11.  *
  12.  * construct segm adj list;
  13.  * version employing memory saving segment structure; see also: lsall.c
  14.  *
  15.  * ms, 11/90;
  16.  */
  17. #include <stdio.h>
  18. #include <string.h>
  19. #include <math.h>
  20.  
  21. #include "lldef.h"
  22. #include "xsgll.h"
  23.  
  24.  
  25. #define    OFF        0
  26. #define    ORDER_DIJ    -1            /* construct dij-ordered lists */
  27. #define    ORDER_PJI    1             /* construct pji-ordered lists */
  28. #define    ORDER        ORDER_PJI
  29.  
  30. #define    MIN_SAL_SIZE    3
  31.  
  32. #undef    DEBUG
  33. #undef    SHOW_SEG
  34. #undef    SHOW_PARMS
  35.  
  36. /*
  37.  * compare list entries (segments):
  38.  *   key: inverse overlap parameter, pji
  39.  *
  40.  */
  41. int
  42. cmpSegmpji (oldSegm, newSegm)
  43.      struct Segmtype *oldSegm, *newSegm;
  44. {
  45.  
  46.   return (SIGN (oldSegm->pji - newSegm->pji));
  47. }
  48.  
  49.  
  50. /*
  51.  * scan list, comparing inverse overlap pji of newSegm <j> with that
  52.  * of those segments already in current segm adj list (SAL);
  53.  * a list is desired in which all segments following the reference
  54.  * segment (stored at the top) are entered in the order of decreasing pji;
  55.  * employs matching function, here cmpSegmpji
  56.  * (see also: llsearch() in llist.c )
  57.  */
  58. Boolean
  59. cmppji (newSegm, sall)
  60.      struct Segmtype *newSegm;
  61.      struct linklist *sall;
  62. {
  63.   Boolean MatchStatus = False;
  64.  
  65. /* scan bwd from tail until newpji > existpji */
  66.   lltail (sall);
  67.   do {
  68.     if (((*sall->match) (sall->clp->item, newSegm)) > 0)
  69.       MatchStatus = True;
  70.  
  71.   } while ((MatchStatus != True) && (llprevious (sall) == True));
  72.  
  73.  
  74.   return (MatchStatus);
  75. }
  76.  
  77.  
  78.  
  79. /* 
  80.  * display segment
  81.  */
  82. void
  83. show_segment (index, segm, rSegm)
  84.      int index;
  85.      struct Segm *segm;
  86.      struct Segmtype *rSegm;
  87. {
  88.  
  89.   printf ("\n...segment <%d>, as initialized:\n", index);
  90.  
  91.   printf ("     ptO.x = %d, ptO.y = %d\n",
  92.           segm->ptO.x, segm->ptO.y);
  93.   printf ("     ptF.x = %d, ptF.y = %d\n",
  94.           segm->ptF.x, segm->ptF.y);
  95.   printf ("    slope = %f\n", segm->slope);
  96.   printf ("    line_ind = %d\n", segm->line_ind);
  97.  
  98.   printf ("    dij = %f, pij = %f, pji = %f\n",
  99.           rSegm->dij, rSegm->pij, rSegm->pji);
  100.   printf ("    segm_ind = %d\n", rSegm->segm_ind);
  101.   printf ("    sgl_level = %d\n", rSegm->sgl_level);
  102.   printf ("    SalStatus = %d\n", rSegm->SalStat);
  103.  
  104. }
  105.  
  106.  
  107. /*
  108.  * initialize new segment entry (link) in list
  109.  * note:
  110.  *   the index of a segment read from the input data file is not necessarily
  111.  *   identical to the array index associated with this segment; the segment
  112.  *   index entered into the list is currently just the array index; this 
  113.  *   facilitates subsequent access of segment data (e.g. coordinates), but
  114.  *   can introduce an index offset between the two segment structures;
  115.  */
  116. struct Segmtype *
  117. init_node (list, index, Segm)
  118.      struct linklist *list;
  119.      int index;
  120.      struct Segmtype *Segm;
  121. {
  122.   struct Segmtype *Segmptr;
  123.  
  124.  
  125.   Segm->segm_ind = index;
  126.   Segm->dij = (float) 0.0;
  127.   Segm->pij = (float) 999.0;    /* self overlap */
  128.   Segm->pji = (float) 999.0;    /* self overlap */
  129.   Segm->sgl_level = 0;
  130.   Segm->SalStat = Active;
  131.  
  132.   return (Segmptr = Segm);
  133. }
  134.  
  135.  
  136.  
  137. /* 
  138.  * construct segment adjacency list
  139.  * to obtain an ordered list, the present version employs insertion sorting
  140.  */
  141. int
  142. construct_sall (sall, segm, n_segm, angl_thresh, ovlp_thresh, d_max)
  143.      struct linklist sall[];
  144.      struct Segm *segm;
  145.      int n_segm;
  146.      double angl_thresh;
  147.      double ovlp_thresh;
  148.      double d_max;
  149. {
  150.  
  151.   struct linklist *clist;       /* ptr to current list */
  152.   struct Segmtype refSegm, *rSegm = &refSegm;  /* lin. segm. list entry */
  153.   struct Segmtype curSegm, *cSegm = &curSegm;  /* lin. segm. list entry */
  154.   struct spoint ptO1, ptF1, ptO2, ptF2;  /*segm orig. and fin points */
  155.   int n_sall;
  156.  
  157.   double dij, dji, pij, pji;
  158.   float slpi, slpj, slp_thresh;
  159.   int i, j;
  160.   int order_sal = ORDER;        /* when set, order SAL with */
  161.   /* respect to dij or pji */
  162.  
  163.  
  164.   slp_thresh = (float) tan (angl_thresh * (PI / 180.0));
  165.  
  166.  
  167. /* 
  168.  * consider every pair ( i!=j ) of segments
  169.  */
  170.   printf ("\n...constructing segment adj lists:\n");
  171.   printf ("...processing segment:\n");
  172.   n_sall = 0;
  173.   for (i = 0; i < n_segm; i++) {
  174.     printf (" %3d ", i);
  175.     if ((i + 1) % 12 == 0)
  176.       printf ("\n");
  177.  
  178.     /* initialize new SAL<i> with the reference segment <i> */
  179.     clist = &sall[i];
  180.  
  181. /*              rSegm = init_node(clist, (inSegm+i)->segm_ind, &refSegm); */
  182.     rSegm = init_node (clist, i, &refSegm);
  183.     lltail (clist);
  184.     lladd ((char *) rSegm, clist);
  185.  
  186.  
  187.     ptO1.x = (segm + i)->ptO.x;
  188.     ptO1.y = (segm + i)->ptO.y;
  189.     ptF1.x = (segm + i)->ptF.x;
  190.     ptF1.y = (segm + i)->ptF.y;
  191.     slpi = (segm + i)->slope;
  192.  
  193. #ifdef SHOW_SEG
  194.     show_segment (i, segm + i, rSegm);
  195. #endif
  196.  
  197.     for (j = 0; j < n_segm; j++) {
  198.       if (j != i) {
  199.         slpj = (segm + j)->slope;
  200.         /*if (slpi * slpj == -1.0) {
  201.          * printf ("\n...segments m%d, m%d perpendicular:", i, j);
  202.          * printf (" pair skipped\n");
  203.          * }
  204.          * else */ if (fabs ((slpi - slpj) / (1.0 + slpi * slpj)) < slp_thresh) {
  205.  
  206.           ptO2.x = (segm + j)->ptO.x;
  207.           ptO2.y = (segm + j)->ptO.y;
  208.           ptF2.x = (segm + j)->ptF.x;
  209.           ptF2.y = (segm + j)->ptF.y;
  210.  
  211.           prlpar (ptO1, ptF1, ptO2, ptF2, &dij, &dji, &pij, &pji);
  212.  
  213. #ifdef SHOW_PARMS
  214.           printf ("\n...returned from prlpar():\n");
  215.           printf ("    overlap(%d,%d)=%.2lf\n", i, j, pij);
  216.           printf ("    overlap(%d,%d)=%.2lf\n", j, i, pji);
  217.           printf ("  perp.dist(%d,%d)=%.2lf\n", i, j, dij);
  218. #endif
  219.  
  220.           switch (SIGN (dij)) {
  221.           case -1:
  222.             if (fabs (dij) < d_max) {
  223.               if (pij > (double) ovlp_thresh) {
  224.  
  225.                 cSegm = init_node (clist, j, &curSegm);
  226.                 cSegm->segm_ind = j;
  227.                 cSegm->dij = (float) dij;
  228.                 cSegm->pij = (float) pij;
  229.                 cSegm->pji = (float) pji;
  230.  
  231.                 if (order_sal == ORDER_PJI) {
  232.                   llsetmatch (cmpSegmpji, clist);
  233.                   while (cmppji (cSegm, clist) != True);
  234.                   lladd ((char *) cSegm, clist);
  235.                 }
  236.                 else {
  237.                   llhead (clist);
  238.                   if (order_sal == ORDER_DIJ) {
  239.                     llsetmatch (cmpSegmdist, clist);
  240.                     while (cmpdij (cSegm, SIGN (dij), clist) != True);
  241.                   }
  242.                   lladdprev ((char *) cSegm, clist);
  243.                 }
  244.               }
  245.             }
  246.             break;
  247.           case 1:
  248.             if (dij < d_max) {
  249.               if (pij > (double) ovlp_thresh) {
  250.                 cSegm = init_node (clist, j, &curSegm);
  251.                 cSegm->segm_ind = j;
  252.                 cSegm->dij = (float) dij;
  253.                 cSegm->pij = (float) pij;
  254.                 cSegm->pji = (float) pji;
  255.  
  256.                 if (order_sal == ORDER_PJI) {
  257.                   llsetmatch (cmpSegmpji, clist);
  258.                   while (cmppji (cSegm, clist) != True);
  259.                   lladd ((char *) cSegm, clist);
  260.                 }
  261.                 else {
  262.                   lltail (clist);
  263.                   if (order_sal == ORDER_DIJ) {
  264.                     llsetmatch (cmpSegmdist, clist);
  265.                     while (cmpdij (cSegm, SIGN (dij), clist) != True);
  266.                   }
  267.                   lladd ((char *) cSegm, clist);
  268.                 }
  269.               }
  270.             }
  271.             break;
  272.           case 0:
  273. #ifdef DEBUG
  274.             printf ("\n...overlap p(%d,%d) = %.2lf ignored\n",
  275.                     i, j, pij);
  276. #endif
  277.             break;
  278.           default:
  279.             printf ("\n...unknown SIGN(dij)!\n");
  280.             break;
  281.           }
  282.         }
  283.       }
  284.     }
  285.  
  286.     if (clist->listlength >= MIN_SAL_SIZE)
  287.       n_sall++;
  288. #ifdef DEBUG
  289.     show_segm_list (clist, i);
  290. #endif
  291.   }
  292.  
  293.   return (n_sall);
  294. }
  295.