link_treerings.c Source File

00001 #include        "sadie.h"
00002 #include        "proto.h"
00003 
00004 
00005 /* #define LINK_TREERINGS_DEBUG */
00006 
00007 
00008 /* variables necessary for drawing lines with bresh algorithm */
00009 extern int **x_array_buffer;     /* The data where info is stored      */
00010 extern int point;                /* Counter for points used            */
00011 extern int count_point;          /* Flag decide to count or fill array */
00012 
00013 typedef struct {                        /* Ring fragment data structure */
00014     int     valid;                      /* Indicates if this contains valid data */
00015     int     topx;                       /* Coordinate of top of fragment */
00016     int     topy;
00017     int     bottomx;                    /* Coordinate of bottom of fragment */
00018     int     bottomy;
00019     int     avgpos;                     /* Average position of fragment */
00020     int     numpix;                     /* Number of pixels in fragment */
00021     int     ringlbl;                    /* Label of ring fragment is assigned to */
00022     int     linked;                     /* Indicates if this fragment has been linked */
00023     int     deleted;                    /* Indicates if this fragment has been deleted */
00024 } FRAGMENT;
00025 
00026 
00027 typedef struct {                        /* Information for reconstructing a ring */
00028     int     top;                        /* Indicates if the ring touches the top of the roi */
00029     int     bottom;                     /* Indicates if the ring touches the bottom of the roi */
00030     int     last;                       /* Indicates the most recent fragment used to reconstruct ring */
00031 } RECONSTRUCT;
00032 
00033 
00034 /*-General Information--------------------------------------------------------*/
00035 /*                                                                            */
00036 /*  Description:  This procedure links tree ring fragments.  It assumes that  */
00037 /*  most of the tree ring edges in the image are fully connected.  It         */
00038 /*  searches between each pair of fully connected tree ring boundaries to     */
00039 /*  decide which fragments belong to a fragmented tree ring edge and which    */
00040 /*  are noise features to be discarded.  This algorithm assumes that the      */
00041 /*  relative width of a tree ring remains fairly constant within a region     */
00042 /*  of interest.                                                              */
00043 /*                                                                            */
00044 /*----------------------------------------------------------------------------*/
00045 /*-Interface Information------------------------------------------------------*/
00046 void LINK_TREERINGS (
00047 IMAGE  *in,         /*  I   Pointer to the input edge map image.              */
00048 int   discardedges, /*  I   Variable indicating whether to discard fragments  */
00049                     /*         at edges of input edge map that cannot be      */
00050                     /*         connected using this method.                   */
00051 IMAGE  **fillgaps,  /*  O   Address of a pointer to the image representing    */
00052                     /*         ring fragment connections                      */
00053 IMAGE  **out        /*  O   Address of a pointer to the output edge map image */
00054 /*----------------------------------------------------------------------------*/
00055 ) { register short i, j, k, l;
00056     char   msg[SLEN];
00057     int *completerings; /* mapping of complete ring number to label */
00058     int **ringxpos;     /* x-position pixel locations for each ring  (ringxpos[ring#][image line#] */
00059     int *fragcount;
00060     int *fraghist;
00061     int *fraglbl;
00062     int *fraglbl_track;
00063     int fraghistmax;
00064     int fragcountmax;
00065     int numfrags;
00066     int lochist[100][2];
00067     int locarray[50];
00068     int location;
00069     int count=0;
00070     IMAGE *lblimg;
00071     int curlbl;
00072     int rightbound, leftbound;
00073     int draw;
00074     int startx, starty, endx, endy;
00075     FRAGMENT *fraglist=NULL;
00076     RECONSTRUCT *fixringlist=NULL;
00077 
00078     /* if (TIMES) TIMING(T_LINK_TREERINGS2); */
00079     if (NAMES) {
00080         MESSAGE('I',"");
00081         MESSAGE('I',"LINK_TREERINGS");
00082         MESSAGE('I',"");
00083         sprintf(msg," Input image:                      %s",in->text);
00084         MESSAGE('I',msg);
00085         MESSAGE('I'," ...............");
00086     }
00087 
00088     /* check input */
00089     if (!CHECKIMG(in)) {
00090         MESSAGE('E'," Can't identify image.");
00091         goto the_end;
00092     } else if (in->nbnd > 1) {
00093         MESSAGE('E'," Only using first band of input image.");
00094     }
00095     
00096 
00097 
00098     /* Label the image */
00099     CMPLBL8(in,&lblimg);
00100     if (!CHECKIMG(lblimg)) {
00101         MESSAGE('E'," Problem labeling image.");
00102         goto the_end;
00103     }
00104     
00105     /* Find out how many objects are in the image */
00106     RANGE(lblimg);
00107     
00108     /* create output image of appropriate size */
00109     if (!CHECKIMG(*out)) GETMEM(1,lblimg->nlin,lblimg->npix,out);
00110     if (!*out) goto the_end;
00111     /* create output image of appropriate size */
00112     if (!CHECKIMG(*fillgaps)) GETMEM(1,lblimg->nlin,lblimg->npix,fillgaps);
00113     if (!*fillgaps) goto the_end;
00114     
00115     /* Copy the input to the output and initialize gaps image */
00116     for (j=0; j<in->nlin; j++) {
00117         for (k=0; k<in->npix; k++) {
00118             (*out)->data[0][j][k] = in->data[0][j][k];
00119             (*fillgaps)->data[0][j][k] = (PIXEL)0.0;
00120         }
00121     }
00122 
00123 
00124     /* Allocate memory to find complete rings */
00125     if (!(completerings=(int *)malloc((int)rnd(lblimg->npix)*sizeof(int)))) { 
00126         MESSAGE('E'," Could not allocate memory for complete rings list.");
00127         goto the_end;
00128     }
00129     /* Allocate memory to associate connected component labels with fragment labels */
00130     if (!(fraglbl_track=(int *)malloc((int)rnd(lblimg->gmax)*sizeof(int)))) { 
00131         MESSAGE('E'," Could not allocate memory for labeling fragments.");
00132         goto the_end;
00133     }
00134     /* Allocate memory to track fragment labels between two complete rings */
00135     if (!(fraglbl=(int *)malloc((int)rnd(lblimg->gmax)*sizeof(int)))) { 
00136         MESSAGE('E'," Could not allocate memory for labeling fragments.");
00137         goto the_end;
00138     }
00139     /* Allocate memory to count fragments between complete rings */
00140     if (!(fragcount=(int *)malloc((int)rnd(lblimg->nlin)*sizeof(int)))) { 
00141         MESSAGE('E'," Could not allocate memory for complete rings list.");
00142         goto the_end;
00143     }
00144     /* Allocate memory to create a histogram of fragment counts between complete rings */
00145     if (!(fraghist=(int *)malloc((int)rnd(lblimg->npix)*sizeof(int)))) { 
00146         MESSAGE('E'," Could not allocate memory for complete rings list.");
00147         goto the_end;
00148     }
00149     
00150     
00151     
00152     /* Search for complete rings */
00153     for (i=0; i<lblimg->npix; i++) {
00154         if (lblimg->data[0][0][i] > (PIXEL)0.0) {
00155             for (j=0; j<lblimg->npix; j++) {
00156                 if (lblimg->data[0][lblimg->nlin-1][j] == lblimg->data[0][0][i]) {
00157                     completerings[count++] = (int)rnd(lblimg->data[0][0][i]);
00158                     break;
00159                 }
00160             }
00161         }
00162     }
00163     
00164     /* Allocate memory to store complete ring positions */
00165     if (!(ringxpos=(int **)malloc(count*sizeof(int  * )))) { 
00166         MESSAGE('E'," Could not allocate memory for complete ring positions.");
00167         goto the_end;
00168     }
00169     for  (i = 0; i < count; i++){
00170         ringxpos[i] = (int  *) calloc(lblimg->nlin, sizeof(int));
00171         if (ringxpos[i] == (int) NULL){
00172             MESSAGE('E'," Could not allocate memory for complete ring positions.");
00173             goto the_end;
00174         }
00175     }
00176     
00177     /* Determine complete ring positions */
00178     for (i=0; i<count; i++) {        
00179         for (j=0; j<lblimg->nlin; j++) {
00180             for (k=0; k<lblimg->npix; k++) {
00181                 if ((int)rnd(lblimg->data[0][j][k]) == completerings[i]) {
00182                     ringxpos[i][j] = k;
00183                     break;
00184                 }
00185             }
00186         }    
00187     }
00188     
00189 
00190 #ifdef LINK_TREERINGS_DEBUG
00191     printf("\n%d complete rings were found!\n",count);
00192 #endif
00193     
00194     if (count < 2) {
00195         MESSAGE('E'," At least two complete rings are necessary to link inter-rings.");
00196         goto the_end;
00197     }
00198     
00199     
00200     
00201     
00202     if (discardedges) {
00203 
00204         curlbl = (int)rnd(lblimg->data[0][0][ringxpos[0][0]]);
00205         for (j=0; j<lblimg->nlin; j++) {
00206             for (k=0; k<ringxpos[0][j]; k++) {
00207                 if (lblimg->data[0][j][k] > (PIXEL)0.0) {
00208                     if (curlbl != (int)rnd(lblimg->data[0][j][k])) {
00209                         (*out)->data[0][j][k] = (PIXEL)0.0;
00210                     }
00211                 }
00212             }
00213         }
00214 
00215         curlbl = (int)rnd(lblimg->data[0][0][ringxpos[count-2][0]]);
00216         for (j=0; j<lblimg->nlin; j++) {
00217             for (k=ringxpos[count-2][j]+1; k<(*out)->npix; k++) {
00218                 if (lblimg->data[0][j][k] > (PIXEL)0.0) {
00219                     if (curlbl != (int)rnd(lblimg->data[0][j][k])) {
00220                         (*out)->data[0][j][k] = (PIXEL)0.0;
00221                     }
00222                 }
00223             }
00224         }
00225     
00226     }
00227     
00228     
00229     
00230     for (i=0; i<count-1; i++) {
00231     
00232 #ifdef LINK_TREERINGS_DEBUG
00233         printf("\n\nCompleting rings between rings %d and %d\n",completerings[i],completerings[i+1]);
00234 #endif
00235         
00236         /* Initialize the fragment counter */
00237         for (k=0; k<lblimg->npix; k++) {
00238             fraghist[k] = 0;
00239         }
00240         for (j=0; j<lblimg->nlin; j++) {
00241             fragcount[j] = 0;
00242         }
00243         
00244         /* Initialize the location histogram */
00245         for (j=0; j<100; j++) {
00246             lochist[j][0] = j;
00247             lochist[j][1] = 0;
00248         }
00249         
00250         /* Initialize fragment labels */
00251         for (j=0; j<(int)lblimg->gmax; j++) {
00252             fraglbl_track[j] = -1;
00253             fraglbl[j] = 0;
00254         }
00255         numfrags = 0;
00256         
00257         /* Count the number of fragments in each row */
00258         fraghistmax = 0;
00259         fragcountmax = 0;
00260         for (j=0; j<lblimg->nlin; j++) {
00261             for (k=ringxpos[i][j]+1; k<ringxpos[i+1][j]; k++) {
00262                 if ((lblimg->data[0][j][k] > (PIXEL)0.0)&&
00263                        (lblimg->data[0][j][k] != lblimg->data[0][j][ringxpos[i][j]])&&
00264                         (lblimg->data[0][j][k] != lblimg->data[0][j][ringxpos[i+1][j]])) {
00265                     fragcount[j] += 1;
00266                     
00267                     location = (int)rnd(((double)(k-ringxpos[i][j])/(double)(ringxpos[i+1][j]-ringxpos[i][j]))*100.0);
00268                     if (location < 100) {
00269                         lochist[location][1] += 1;
00270                     } else {
00271                         lochist[99][1] += 1;
00272                     }
00273                     
00274                     if (fraglbl_track[(int)lblimg->data[0][j][k] - 1] == -1) {
00275                         fraglbl_track[(int)lblimg->data[0][j][k] - 1] = numfrags;
00276                         fraglbl[numfrags++] = (int)lblimg->data[0][j][k];
00277                     }
00278                 }
00279             }
00280             
00281             fraghist[fragcount[j]] += 1;
00282             
00283             if (fraghist[fragcount[j]] >= fraghistmax) {
00284                 fraghistmax = fraghist[fragcount[j]];
00285                 fragcountmax = fragcount[j];
00286             }
00287         }
00288         
00289 #ifdef LINK_TREERINGS_DEBUG
00290         printf("    It looks like there are %d rings here\n",fragcountmax);
00291         printf("    They are made up of %d fragments:\n",numfrags);
00292         printf("       ");
00293         for (j=0; j<numfrags; j++) {
00294             printf(" %d ",fraglbl[j]);
00295         }
00296         printf("\n");
00297 #endif
00298         
00299 
00300         if (fragcountmax > 0) {
00301         
00302             /* Suppress non-local maxima */
00303             for (j=1; j<99; j++) {
00304                 if (lochist[j][1] <= lochist[j-1][1]) {
00305                     lochist[j][1] = 0;
00306                 } else if (lochist[j][1] <= lochist[j+1][1]) {
00307                     lochist[j][1] = 0;
00308                 }
00309             }
00310         
00311             /* Determine the locations of the rings.                                 */
00312             /*   (find the n most common fragment locations, where n = fragcountmax) */
00313             quicksort((int *)lochist,0,99);
00314             
00315             /* Sort the locations */
00316             for (j=0; j<fragcountmax; j++) {
00317                 locarray[j] = lochist[j][0];
00318             }
00319             if (fragcountmax > 1) {
00320                 quicksort2(locarray,0,fragcountmax-1);
00321             }
00322 #ifdef LINK_TREERINGS_DEBUG
00323             printf("    They are located at:  ");
00324             for (j=0; j<fragcountmax; j++) {
00325                 printf("%d%%  ",locarray[j]);
00326             }
00327             printf("\n");
00328 #endif
00329 
00330             
00331             
00332 
00333 
00334             /* Compute info about ring fragments */
00335 
00336             /* allocate a fragment list */
00337             if (!(fraglist=(FRAGMENT *)malloc(numfrags*sizeof(FRAGMENT)))) { 
00338                 MESSAGE('E'," Could not allocate memory for fragment list.");
00339                 goto the_end;
00340             }
00341 
00342             for (j=0; j<numfrags; j++) {
00343                 fraglist[j].valid=0;
00344             }
00345 
00346             for (j=0; j<lblimg->nlin; j++) {
00347                 for (k=ringxpos[i][j]+1; k<ringxpos[i+1][j]; k++) {
00348                     if ((lblimg->data[0][j][k] > (PIXEL)0.0)&&
00349                            (lblimg->data[0][j][k] != lblimg->data[0][j][ringxpos[i][j]])&&
00350                             (lblimg->data[0][j][k] != lblimg->data[0][j][ringxpos[i+1][j]])) {
00351                         curlbl = fraglbl_track[(int)rnd(lblimg->data[0][j][k])-1];
00352                         location = (int)rnd(((double)(k-ringxpos[i][j])/(double)(ringxpos[i+1][j]-ringxpos[i][j]))*100.0);
00353                         //if (location < 100) {
00354                         //    lochist[location][1] += 1;
00355                         //} else {
00356                         //    lochist[99][1] += 1;
00357                         //}
00358                         
00359                         
00360                         if (!fraglist[curlbl].valid) {
00361 
00362                             fraglist[curlbl].valid = 1;
00363                             fraglist[curlbl].topx = fraglist[curlbl].bottomx = k;
00364                             fraglist[curlbl].topy = fraglist[curlbl].bottomy = j;
00365                             fraglist[curlbl].avgpos = location;
00366                             fraglist[curlbl].numpix = 1;
00367                             fraglist[curlbl].ringlbl = fraglist[curlbl].linked = fraglist[curlbl].deleted = 0;
00368 
00369                         } else {
00370 
00371                             fraglist[curlbl].bottomx = k;
00372                             fraglist[curlbl].bottomy = j;
00373                             fraglist[curlbl].avgpos += location;
00374                             fraglist[curlbl].numpix += 1;
00375 
00376                         }
00377                     }
00378                 }
00379 
00380             }
00381 
00382             for (j=0; j<numfrags; j++) {
00383                 fraglist[j].avgpos = (int)rnd((double)fraglist[j].avgpos/(double)fraglist[j].numpix);
00384 
00385                 for (k=0; k<fragcountmax; k++) {
00386                     if (k>0) {
00387                         leftbound = locarray[k]-(int)rnd(min((double)5.0,(double)(locarray[k]-locarray[k-1])/4.0));
00388                     } else {
00389                         leftbound = locarray[k]-(int)rnd(min((double)5.0,(double)(locarray[k])/4.0));
00390                     }
00391                     if (k<fragcountmax-1) {
00392                         rightbound = locarray[k]+(int)rnd(min((double)5.0,(double)(locarray[k+1]-locarray[k])/4.0));
00393                     } else {
00394                         rightbound = locarray[k]+(int)rnd(min((double)5.0,(double)(100-locarray[k])/4.0));
00395                     }
00396                     
00397                     if ((fraglist[j].avgpos >= leftbound)&&(fraglist[j].avgpos <= rightbound)) {
00398                         fraglist[j].ringlbl = k+1;
00399                     }
00400 #ifdef LINK_TREERINGS_DEBUG
00401                     //printf("The bounds for the ring at %d%% are: %d%% - %d%%\n\n",locarray[k],leftbound,rightbound);
00402 #endif
00403                 }
00404             }
00405 
00406 #ifdef LINK_TREERINGS_DEBUG
00407             for (k=0; k<fragcountmax; k++) {
00408                 printf("The fragments for the ring at %d%% are:\n", locarray[k]);
00409                 printf("      ");
00410                 
00411                 for (j=0; j<numfrags; j++) {
00412                     if (fraglist[j].ringlbl == k+1) {
00413                         printf(" %d ",fraglbl[j]);
00414                     }
00415                 }
00416                 printf("\n");
00417             }
00418 #endif
00419             
00420             /* Delete the noise fragments from the output */
00421             for (curlbl=0; curlbl<numfrags; curlbl++) {
00422                 if (fraglist[curlbl].ringlbl == 0) {
00423                     for (j=0; j<lblimg->nlin; j++) {
00424                         for (k=ringxpos[i][j]+1; k<ringxpos[i+1][j]; k++) {
00425                             if (lblimg->data[0][j][k] == fraglbl[curlbl]) {
00426                                 (*out)->data[0][j][k] = (PIXEL)0.0;
00427                             }
00428                         }
00429                     }
00430                 }
00431             }
00432 
00433 
00434 
00435             /* Allocate memory to track information while connecting ring fragments */
00436             if (!(fixringlist=(RECONSTRUCT *)malloc(fragcountmax*sizeof(FRAGMENT)))) { 
00437                 MESSAGE('E'," Could not allocate memory for fragment list.");
00438                 goto the_end;
00439             }
00440             
00441             /* Initialize fixringlist */
00442             for (j=0; j<fragcountmax; j++) {
00443                 fixringlist[j].top = fixringlist[j].bottom = fixringlist[j].last = 0;
00444             }
00445             
00446             for (j=0; j<lblimg->nlin; j++) {
00447                 for (k=ringxpos[i][j]+1; k<ringxpos[i+1][j]; k++) {
00448  
00449                     draw = 0;
00450  
00451                     if ((lblimg->data[0][j][k] > (PIXEL)0.0)&&
00452                            (lblimg->data[0][j][k] != lblimg->data[0][j][ringxpos[i][j]])&&
00453                             (lblimg->data[0][j][k] != lblimg->data[0][j][ringxpos[i+1][j]])) {
00454                         curlbl = fraglbl_track[(int)rnd(lblimg->data[0][j][k])-1];
00455                         
00456                         if (fraglist[curlbl].ringlbl > 0) {
00457                             if (fixringlist[fraglist[curlbl].ringlbl - 1].top == 0) {
00458                                 if (j>0) {
00459                                     draw = 1;
00460                                     startx = endx = k;
00461                                     starty = 0;
00462                                     endy = j;
00463 #ifdef LINK_TREERINGS_DEBUG
00464                                     //printf("Connecting %d to top\n",fraglbl[curlbl]);
00465 #endif
00466                                 }
00467                                 fixringlist[fraglist[curlbl].ringlbl - 1].last = curlbl;
00468                                 fixringlist[fraglist[curlbl].ringlbl - 1].top = 1;
00469                                 fraglist[curlbl].linked = 1;
00470                             } else if ((fraglist[curlbl].linked == 0)&&(fraglist[curlbl].deleted == 0)) {
00471 
00472                                 if (fixringlist[fraglist[curlbl].ringlbl - 1].last != curlbl) {
00473                                         
00474                                     if ( fraglist[curlbl].bottomy > fraglist[fixringlist[fraglist[curlbl].ringlbl - 1].last].bottomy ) {
00475                                         draw = 1;
00476                                         startx = fraglist[fixringlist[fraglist[curlbl].ringlbl - 1].last].bottomx;
00477                                         starty = fraglist[fixringlist[fraglist[curlbl].ringlbl - 1].last].bottomy;
00478                                         endx = fraglist[curlbl].topx;
00479                                         endy = fraglist[curlbl].topy;
00480 #ifdef LINK_TREERINGS_DEBUG
00481                                         //printf("Connecting %d to %d\n",fraglbl[curlbl],fraglbl[fixringlist[fraglist[curlbl].ringlbl - 1].last]);
00482 #endif
00483 
00484                                         fraglist[curlbl].linked = 1;
00485                                         fixringlist[fraglist[curlbl].ringlbl - 1].last = curlbl;
00486                                     } else {
00487                                         fraglist[curlbl].deleted = 1;
00488                                     }
00489                                 }
00490 
00491                                 if (j == lblimg->nlin-1) {
00492                                     fixringlist[fraglist[curlbl].ringlbl - 1].bottom = 1;
00493                                 }
00494 
00495                             }
00496                         }
00497                     }
00498                         
00499 
00500                     if (draw) {
00501 
00502                         /* Count number of points in line */
00503                         count_point = TRUE;
00504                         point = 0;
00505                         brshnm(startx,starty,endx, endy);
00506 
00507                         /* Allocate memory */
00508                         x_array_buffer = (int **) malloc(point*sizeof(int  * ));
00509                         if (x_array_buffer == (int **) NULL){
00510                             printf("No memory for x_array_buffer\n");
00511                         } else{
00512 
00513                             for  (l = 0; l < point; l++){
00514                                 x_array_buffer[l] = (int  *) calloc(2, sizeof(int));
00515                                 if (x_array_buffer[l] == (int) NULL){
00516                                     printf ("No memory for element %d\n",x_array_buffer[l]);
00517                                 }
00518                             }
00519 
00520                             /* Fill array */ 
00521                             count_point = FALSE;
00522                             point = 0;
00523                             brshnm(startx,starty,endx, endy);
00524 
00525 #ifdef LINK_TREERINGS_DEBUG
00526                             //printf("startx=%d, starty=%d, endx=%d, endy=%d\n",startx,starty,endx,endy);
00527                             //printf("     x=%d,      y=%d,    x=%d,    y=%d\n",x_array_buffer[0][0],x_array_buffer[0][1],x_array_buffer[point-1][0],x_array_buffer[point-1][1]);
00528 #endif
00529 
00530                                 for (l=0; l < point; l++) {
00531                                      (*fillgaps)->data[0][x_array_buffer[l][1]][x_array_buffer[l][0]] = (PIXEL)1.0;
00532                                 }
00533 
00534                             if(x_array_buffer) {
00535                                 /* Free Bresh Array */
00536                                 for (l=0; l < point; l++){
00537                                     if(x_array_buffer[l]) {
00538                                         free(x_array_buffer[l]);
00539                                         x_array_buffer[l] = NULL;
00540                                     }
00541                                 }
00542 
00543                                 free(x_array_buffer);
00544                                 x_array_buffer = NULL;
00545                             }
00546 
00547                         }
00548                     }
00549                 }
00550             }
00551 
00552             /* Ensure rings are complete to bottom of roi */
00553             for (j=0; j<fragcountmax; j++) {
00554                 if (fixringlist[j].bottom == 0) {
00555                     startx = endx = fraglist[fixringlist[j].last].bottomx;
00556                     starty = fraglist[fixringlist[j].last].bottomy;
00557                     endy = lblimg->nlin-1;
00558                     
00559 #ifdef LINK_TREERINGS_DEBUG
00560                     //printf("Connecting %d to bottom\n",fraglbl[fixringlist[j].last]);
00561 #endif
00562                     
00563                     /* Count number of points in line */
00564                     count_point = TRUE;
00565                     point = 0;
00566                     brshnm(startx,starty,endx, endy);
00567 
00568                     /* Allocate memory */
00569                     x_array_buffer = (int **) malloc(point*sizeof(int  * ));
00570                     if (x_array_buffer == (int **) NULL){
00571                         printf("No memory for x_array_buffer\n");
00572                     } else{
00573 
00574                         for  (l = 0; l < point; l++){
00575                             x_array_buffer[l] = (int  *) calloc(2, sizeof(int));
00576                             if (x_array_buffer[l] == (int) NULL){
00577                                 printf ("No memory for element %d\n",x_array_buffer[l]);
00578                             }
00579                         }
00580 
00581                         /* Fill array */ 
00582                         count_point = FALSE;
00583                         point = 0;
00584                         brshnm(startx,starty,endx, endy);
00585 
00586                             for (l=0; l < point; l++) {
00587                                  (*fillgaps)->data[0][x_array_buffer[l][1]][x_array_buffer[l][0]] = (PIXEL)1.0;
00588                             }
00589 
00590                         if(x_array_buffer) {
00591                             /* Free Bresh Array */
00592                             for (l=0; l < point; l++){
00593                                 if(x_array_buffer[l]) {
00594                                     free(x_array_buffer[l]);
00595                                     x_array_buffer[l] = NULL;
00596                                 }
00597                             }
00598 
00599                             free(x_array_buffer);
00600                             x_array_buffer = NULL;
00601                         }
00602                     }
00603 
00604                 }
00605             }
00606             
00607             /* Remove the deleted noise fragments from the output */
00608             for (curlbl=0; curlbl<numfrags; curlbl++) {
00609                 
00610                 if (fraglist[curlbl].deleted == 1) {
00611                     for (j=0; j<lblimg->nlin; j++) {
00612                         for (k=ringxpos[i][j]+1; k<ringxpos[i+1][j]; k++) {
00613                             if (lblimg->data[0][j][k] == fraglbl[curlbl]) {
00614                                 (*out)->data[0][j][k] = (PIXEL)0.0;
00615                             }
00616                         }
00617                     }
00618                 }
00619                 
00620             }
00621             
00622 
00623 
00624             if(fraglist) free(fraglist);
00625             fraglist=NULL;
00626             if(fixringlist) free(fixringlist);
00627             fixringlist=NULL;
00628 
00629 
00630         } else {
00631 
00632             /* Delete the noise fragments from the output */
00633             for (curlbl=0; curlbl<numfrags; curlbl++) {
00634                 for (j=0; j<lblimg->nlin; j++) {
00635                     for (k=ringxpos[i][j]+1; k<ringxpos[i+1][j]; k++) {
00636                         if (lblimg->data[0][j][k] == fraglbl[curlbl]) {
00637                             (*out)->data[0][j][k] = (PIXEL)0.0;
00638                         }
00639                     }
00640                 }
00641             }
00642         
00643         }
00644 
00645 
00646         
00647         
00648     }
00649     
00650     
00651 
00652   
00653 
00654 
00655 
00656 
00657     the_end:
00658 
00659     /* if (TIMES)   TIMING(T_EXIT); */
00660     if (CHECKIMG(lblimg))  RELIMG(&lblimg);
00661     if (completerings) free(completerings);
00662     if (fraglbl_track) free(fraglbl_track);
00663     if (fraglbl) free(fraglbl);
00664     if (fragcount) free(fragcount);
00665     if (fraghist) free(fraghist);
00666     if (fraglist) free(fraglist);
00667     if(fixringlist) free(fixringlist);
00668     if(ringxpos) {
00669         for (i=0; i < count; i++){
00670             if(ringxpos[i]) {
00671                 free(ringxpos[i]);
00672                 ringxpos[i] = NULL;
00673             }
00674         }
00675 
00676         free(ringxpos);
00677         ringxpos = NULL;
00678     }
00679 }
00680 
00681 
00682 /* With payload, high to low */
00683 void quicksort(array,left,right)
00684     int *array, left, right;
00685 {
00686     int i,j,pivot,temp[2];
00687     
00688     if (right > left) {
00689         pivot = array[(left*2)+1];
00690         i = left + 1;
00691         j = right;
00692         
00693         do {
00694             while (array[(i*2)+1] >= pivot && i<right) i++;
00695             while (array[(j*2)+1] <= pivot && j>left) j--;
00696             if (i<j) {
00697                 temp[0] = array[(i*2)+0];
00698                 temp[1] = array[(i*2)+1];
00699                 
00700                 array[(i*2)+0] = array[(j*2)+0];
00701                 array[(i*2)+1] = array[(j*2)+1];
00702                 
00703                 array[(j*2)+0] = temp[0];
00704                 array[(j*2)+1] = temp[1];
00705             }
00706         } while (i < j);
00707 
00708         temp[0] = array[(left*2)+0];
00709         temp[1] = array[(left*2)+1];
00710 
00711         array[(left*2)+0] = array[(j*2)+0];
00712         array[(left*2)+1] = array[(j*2)+1];
00713 
00714         array[(j*2)+0] = temp[0];
00715         array[(j*2)+1] = temp[1];
00716     }
00717     
00718     if (j > left + 1) quicksort(array,left,j-1);
00719     if (j < right - 1) quicksort(array,j+1,right);
00720 
00721     return;
00722 }
00723 
00724 
00725 /* No payload, low to high */
00726 void quicksort2(array,left,right)
00727     int *array, left, right;
00728 {
00729     int i,j,pivot,temp;
00730     
00731     if (right > left) {
00732         pivot = array[left];
00733         i = left + 1;
00734         j = right;
00735         
00736         do {
00737             while (array[i] <= pivot && i<right) i++;
00738             while (array[j] >= pivot && j>left) j--;
00739             if (i<j) {
00740                 temp = array[i];
00741                 array[i] = array[j];
00742                 array[j] = temp;
00743             }
00744         } while (i < j);
00745 
00746         temp = array[left];
00747         array[left] = array[j];
00748         array[j] = temp;
00749     }
00750     
00751     if (j > left + 1) quicksort2(array,left,j-1);
00752     if (j < right - 1) quicksort2(array,j+1,right);
00753 
00754     return;
00755 }
00756