cmplbl8.c Source File

00001 #include        "sadie.h"
00002 #include        "proto.h"
00003 #include        "math.h"
00004 
00005 /*-General Information--------------------------------------------------------*/
00006 /*                                                                            */
00007 /*  Description:  This procedure performs 8-connected component               */
00008 /*  labeling for a binary image.  This routine implements                     */
00009 /*  Algorithm 2.2 in Machine Vision, by Jain, Kasturi, and Schunck.           */
00010 /*                                                                            */
00011 /*----------------------------------------------------------------------------*/
00012 /*-Interface Information------------------------------------------------------*/
00013 void CMPLBL8 (
00014 IMAGE  *in,     /*  I   Pointer to the input image.                           */
00015 IMAGE  **out    /*  O   Address of a pointer to the output image.             */
00016 /*----------------------------------------------------------------------------*/
00017 ) { register short t, l, ul, ur, p, i, j, k;
00018     char   msg[SLEN];
00019     long   total, *eqv=0, top, lft, uplft, upr, newLabel, label=1L;
00020     long  tempmin;
00021 
00022     int progmeter;
00023     double progress;
00024     double localpercent;
00025     double localprogress;
00026     int progcount, progtotal, progincr;
00027     int cancel=0;
00028 
00029     progmeter = ProgMeter_Create("Label Foreground Objects");
00030     progress = 0.0;
00031 
00032 
00033 
00034     if (TIMES) TIMING(T_LABEL);
00035     if (NAMES) {
00036         MESSAGE('I',"");
00037         MESSAGE('I',"CMPLBL8");
00038         MESSAGE('I',"");
00039         sprintf(msg," Input image:                      %s",in->text);
00040         MESSAGE('I',msg);
00041         MESSAGE('I'," ...............");
00042     }
00043 
00044     /* check input */
00045     if (!CHECKIMG(in)) {
00046         MESSAGE('E'," Can't identify image.");
00047         goto the_end;
00048     } else if (in->nbnd > 1) {
00049         MESSAGE('E'," Only using first band of input image.");
00050     }
00051 
00052     /* allocate space */
00053     total = (long)in->nlin*(long)in->npix;
00054     if (!(eqv=(long *)malloc(total*sizeof(long)))) {
00055        MESSAGE('E'," Memory request failed.");
00056        goto the_end;
00057     }
00058 
00059 
00060 
00061     /* create image of appropriate size */
00062     if (!CHECKIMG(*out)) GETMEM(1,in->nlin,in->npix,out);
00063     if (!*out) goto the_end;
00064 
00065 
00066 
00067 
00068     /* initialize eqv[0] */
00069     eqv[0L] = 0L;
00070 
00071     RANGE(in);
00072 
00073 
00074     if (progmeter) {
00075         localpercent = 0.7;
00076         localprogress = 0.0;
00077         progcount = 0;
00078         progtotal = in->npix * in->nlin;
00079         progincr = rint((double)progtotal/28.0);
00080     }
00081     for (j=0; j<in->nlin; j++) {
00082         for (k=0; k<in->npix; k++) {
00083             if (progmeter) {
00084                 progcount++;
00085                 if ((progcount%progincr) == 0) {
00086                     localprogress = ((double)progcount/(double)progtotal)*100.0;
00087                     cancel = ProgMeter_Update(progmeter,(localprogress*localpercent)+progress);
00088                     if (cancel != 0) goto the_end;
00089                 }
00090             }
00091 
00092             /* look at adjacent segments */
00093             if (t = j) {
00094                 for (top=eqv[(long)(*out)->data[0][j-1][k]]; top!=eqv[top]; top=eqv[top]);
00095                 eqv[(long)(*out)->data[0][j-1][k]] = top;
00096             }
00097             if (l = k) {
00098                 for (lft=eqv[(long)(*out)->data[0][j][k-1]]; lft!=eqv[lft]; lft=eqv[lft]);
00099                 eqv[(long)(*out)->data[0][j][k-1]] = lft;
00100             }
00101             if (ul = (l && t)) {
00102                 for (uplft=eqv[(long)(*out)->data[0][j-1][k-1]]; uplft!=eqv[uplft]; uplft=eqv[uplft]);
00103                 eqv[(long)(*out)->data[0][j-1][k-1]] = uplft;
00104             }
00105             if (ur = (t && k<in->npix-1)) {
00106                 for (upr=eqv[(long)(*out)->data[0][j-1][k+1]]; upr!=eqv[upr]; upr=eqv[upr]);
00107                 eqv[(long)(*out)->data[0][j-1][k+1]] = upr;
00108             }
00109             
00110             
00111             /* check pixel values */
00112             p = (in->data[0][j][k] > in->gmin);
00113             if (t) {
00114                 t = (in->data[0][j-1][k] > in->gmin);
00115             }
00116             if (l) {
00117                 l = (in->data[0][j][k-1] > in->gmin);
00118             }
00119             if (ul) {
00120                 ul = (in->data[0][j-1][k-1] > in->gmin);
00121             }
00122             if (ur) {
00123                 ur = (in->data[0][j-1][k+1] > in->gmin);
00124             }
00125 
00126 
00127             if (p) {
00128                 /* assign pixel label */
00129                 
00130                 
00131                 /* Case (a) */
00132                 if (l && !t && !ul && !ur) {
00133                     (*out)->data[0][j][k] = (*out)->data[0][j][k-1];
00134                 } else if (!l && t && !ul && !ur) {
00135                     (*out)->data[0][j][k] = (*out)->data[0][j-1][k];
00136                 } else if (!l && !t && ul && !ur) {
00137                     (*out)->data[0][j][k] = (*out)->data[0][j-1][k-1];
00138                 } else if (!l && !t && !ul && ur) {
00139                     (*out)->data[0][j][k] = (*out)->data[0][j-1][k+1];
00140 
00141                 } else if (l || t || ul || ur) {
00142                 
00143                     /* find the minimum label */
00144                     if (ul) {
00145                         tempmin = uplft;
00146                         if (t && (top < tempmin)) {
00147                             tempmin = top;
00148                         }
00149                         if (ur && (upr < tempmin)) {
00150                             tempmin = upr;
00151                         }
00152                         if (l && (lft < tempmin)) {
00153                             tempmin = lft;
00154                         }
00155                     } else if (t) {
00156                         tempmin = top;
00157                         if (ur && (upr < tempmin)) {
00158                             tempmin = upr;
00159                         }
00160                         if (l && (lft < tempmin)) {
00161                             tempmin = lft;
00162                         }
00163                     } else if (ur) {
00164                         tempmin = upr;
00165                         if (l && (lft < tempmin)) {
00166                             tempmin = lft;
00167                         }
00168                     } else {
00169                         tempmin = lft;
00170                     }
00171 
00172                         
00173                     (*out)->data[0][j][k] = (PIXEL) tempmin;
00174 
00175                     /* merge adjacent segments */
00176                     if (ul && uplft > tempmin) {
00177                         eqv[uplft] = tempmin;
00178                     }
00179                     if (t && top > tempmin) {
00180                         eqv[top] = tempmin;
00181                     }
00182                     if (ur && upr > tempmin) {
00183                         eqv[upr] = tempmin;
00184                     }
00185                     if (l && lft > tempmin) {
00186                         eqv[lft] = tempmin;
00187                     }
00188     
00189                 
00190                 
00191                 } else {
00192 
00193                     /* assign a new label */
00194                     eqv[label] = label;
00195                     (*out)->data[0][j][k] = (PIXEL)label++;
00196                     
00197                 }
00198                 
00199                                 
00200             } else {
00201             
00202                 (*out)->data[0][j][k] = 0.0;
00203             
00204             }
00205 
00206         }
00207     }
00208     if (progmeter) {
00209         progress += localpercent * 100.0;
00210     }
00211 
00212 
00213 
00214     /* assign consecutive labels */
00215     if (progmeter) {
00216         localpercent = 0.05;
00217         localprogress = 0.0;
00218         progcount = 0;
00219         progtotal = label;
00220         progincr = rint((double)progtotal/3.0);
00221     }
00222     for (top=0L; top<label; top++) {
00223         if (progmeter) {
00224             progcount++;
00225             if ((progcount%progincr) == 0) {
00226                 localprogress = ((double)progcount/(double)progtotal)*100.0;
00227                 cancel = ProgMeter_Update(progmeter,(localprogress*localpercent)+progress);
00228                 if (cancel != 0) goto the_end;
00229             }
00230         }
00231 
00232         if (eqv[top] != top) {
00233             for (newLabel=eqv[top]; newLabel!=eqv[newLabel]; newLabel=eqv[newLabel]);
00234             eqv[top] = newLabel;
00235         }
00236     }
00237     if (progmeter) {
00238         progress += localpercent * 100.0;
00239     }
00240 
00241 
00242     if (progmeter) {
00243         localpercent = 0.05;
00244         localprogress = 0.0;
00245         progcount = 0;
00246         progtotal = label;
00247         progincr = rint((double)progtotal/3.0);
00248     }
00249     for (newLabel=top=0L; top<label; top++) {
00250         if (progmeter) {
00251             progcount++;
00252             if ((progcount%progincr) == 0) {
00253                 localprogress = ((double)progcount/(double)progtotal)*100.0;
00254                 cancel = ProgMeter_Update(progmeter,(localprogress*localpercent)+progress);
00255                 if (cancel != 0) goto the_end;
00256             }
00257         }
00258 
00259         eqv[top] = (eqv[top] == top ? newLabel++ : eqv[eqv[top]]);
00260     }
00261     if (progmeter) {
00262         progress += localpercent * 100.0;
00263     }
00264 
00265 
00266 
00267     if (progmeter) {
00268         localpercent = 0.2;
00269         localprogress = 0.0;
00270         progcount = 0;
00271         progtotal = in->npix * in->nlin;
00272         progincr = rint((double)progtotal/8.0);
00273     }
00274     for (j=0; j<in->nlin; j++) {
00275         for (k=0; k<in->npix; k++) {
00276             if (progmeter) {
00277                 progcount++;
00278                 if ((progcount%progincr) == 0) {
00279                     localprogress = ((double)progcount/(double)progtotal)*100.0;
00280                     cancel = ProgMeter_Update(progmeter,(localprogress*localpercent)+progress);
00281                     if (cancel != 0) goto the_end;
00282                 }
00283             }
00284 
00285             (*out)->data[0][j][k] = (PIXEL)eqv[(long)(*out)->data[0][j][k]];
00286         }
00287     }
00288     if (progmeter) {
00289         progress += localpercent * 100.0;
00290     }
00291 
00292 
00293     
00294     (*out)->gmin = (PIXEL)0L;
00295     (*out)->gmax = (PIXEL)(newLabel-1L);
00296     MESSAGE('I',"");
00297     sprintf(msg," Number of foreground objects = %ld",newLabel-1);
00298     MESSAGE('I',msg);
00299 
00300     the_end:
00301     if (eqv)     free(eqv);
00302     if (TIMES)   TIMING(T_EXIT);
00303 
00304 
00305     if (progmeter) {
00306         ProgMeter_Destroy(progmeter);
00307     }
00308 
00309     if (cancel != 0) {
00310         if (*out) RELMEM(*out);
00311         *out = NULL;
00312     }
00313 }