histogram.c Source File

00001 #include "trees.h"
00002 #include "histogram.h"
00003 
00004 
00005 
00006 /*-General Information--------------------------------------------------------*/
00007 /*                                                                            */
00008 /*  Description:   Function to initialize a histogram data structure.         */
00009 /*                                                                            */
00010 /*----------------------------------------------------------------------------*/
00011 /*-Interface Information------------------------------------------------------*/
00012 void HIST_INIT (
00013 HISTOGRAM  *hist   /* Pointer to the histogram data structure.                */
00014 /*----------------------------------------------------------------------------*/
00015 ) {
00016     register int i;
00017     
00018     hist->bin = 0;
00019     hist->cbin = 0;
00020     hist->edge = 0;
00021     hist->numpixels = 0;
00022     hist->r = (double)0.0;
00023     hist->per = 0;
00024     for(i = 0; i < HIST_RESOL; i++)
00025         hist->dir[i] = hist->mag[i] = 0;
00026 }
00027 
00028 
00029 
00030 /*-General Information--------------------------------------------------------*/
00031 /*                                                                            */
00032 /*  Description:   Function to compute the magnitude histogram.               */
00033 /*                                                                            */
00034 /*----------------------------------------------------------------------------*/
00035 /*-Interface Information------------------------------------------------------*/
00036 void HIST_MAG (
00037 IMAGE_BYTE  *iMag,        /*  I   Pointer to the gradient magnitude mosaic.   */
00038 MOSAIC_INDEX  *index,     /*  I   Pointer to the mosaic index.                */
00039 HISTOGRAM  *globalhist,   /*  I/O Pointer to the global histogram structure.  */
00040 HISTOGRAM  **localhist,   /*  I/O Address of a pointer to the local histogram.*/
00041 int nrows,                /*  I   Number of rows of blocks.                   */
00042 int ncols                 /*  I   Number of cols of blocks.                   */
00043 /*----------------------------------------------------------------------------*/
00044 ) {
00045     register int i, j, k;
00046     int row, col;
00047 
00048     int progmeter;
00049     double progress;
00050     double localpercent;
00051     double localprogress;
00052     int total, increment;
00053     int cancel=0;
00054 
00055     progmeter = ProgMeter_Create("Magnitude Histograms");
00056     progress = 0.0;
00057 
00058     if (progmeter) {
00059         localpercent = 0.75;
00060         localprogress = 0.0;
00061         total = index->hend - index->hstart;
00062         increment = rint((double)total/5.0) + 1;
00063     }
00064 
00065     /* Local */
00066     for(k = index->hstart; k <= index->hend; k++) {
00067 
00068         if (progmeter) {
00069             if (((k-index->hstart)%increment) == 0) {
00070                 localprogress = ((double)(k-index->hstart)/(double)total)*100.0;
00071                 cancel = ProgMeter_Update(progmeter,(localprogress*localpercent)+progress);
00072             }
00073         }
00074 
00075         for(j = index->vstart[k]; j <= index->vend[k]; j++) {
00076             row = (index->vstart[k]-index->roi->top[0])/HIST_BLOCK_DIM;
00077             col = (k-index->hstart)/HIST_BLOCK_DIM;
00078             localhist[row][col].mag[iMag->data[0][j-index->voffset[k]][k]]++;
00079             localhist[row][col].numpixels++; 
00080         }
00081     }
00082     
00083     if (progmeter) {
00084         progress = 75.0;
00085         cancel = ProgMeter_Update(progmeter,progress);
00086     }
00087     
00088     if (progmeter) {
00089         localpercent = 0.25;
00090         localprogress = 0.0;
00091         total = nrows;
00092         increment = rint((double)total/5.0) + 1;
00093     }
00094 
00095     /* Global */
00096     for(i = 0; i < nrows; i++) {
00097         if (progmeter) {
00098             if ((i%increment) == 0) {
00099                 localprogress = ((double)i/(double)total)*100.0;
00100                 cancel = ProgMeter_Update(progmeter,(localprogress*localpercent)+progress);
00101             }
00102         }
00103 
00104         for(j = 0; j < ncols; j++) {
00105             for(k = 0; k < HIST_RESOL; k++) {
00106                 globalhist->mag[k] += localhist[i][j].mag[k];
00107                 globalhist->numpixels += localhist[i][j].numpixels;
00108             }
00109         }
00110     }
00111 
00112 
00113     if (progmeter) {
00114         progress = 100.0;
00115         cancel = ProgMeter_Update(progmeter,progress);
00116     }
00117 
00118     if (progmeter) {
00119         ProgMeter_Destroy(progmeter);
00120     }
00121 }
00122 
00123 
00124 
00125 /*-General Information--------------------------------------------------------*/
00126 /*                                                                            */
00127 /*  Description:   Function to compute the rth percentile.                    */
00128 /*                                                                            */
00129 /*----------------------------------------------------------------------------*/
00130 /*-Interface Information------------------------------------------------------*/
00131 void HIST_RTH_PERCENTILE (
00132 HISTOGRAM  *globalhist,   /*  I/O Pointer to the global histogram structure.  */
00133 HISTOGRAM  **localhist,   /*  I/O Address of a pointer to the local histogram.*/
00134 double r,                 /*  I   the percentile to compute.                  */
00135 int nrows,                /*  I   Number of rows of blocks.                   */
00136 int ncols                 /*  I   Number of cols of blocks.                   */
00137 /*----------------------------------------------------------------------------*/
00138 ) {
00139     register int i, j, k;
00140     int sum;
00141 
00142     int progmeter;
00143     double progress;
00144     double localpercent;
00145     double localprogress;
00146     int total, increment;
00147     int cancel=0;
00148 
00149     progmeter = ProgMeter_Create("Computing Rth Percentile");
00150     progress = 0.0;
00151 
00152     if (progmeter) {
00153         localpercent = 1.0;
00154         localprogress = 0.0;
00155         total = nrows;
00156         increment = rint((double)total/5.0) + 1;
00157     }
00158     
00159     globalhist->r = r;
00160     
00161     /* Local */
00162     for(i = 0; i < nrows; i++) {
00163 
00164         if (progmeter) {
00165             if ((i%increment) == 0) {
00166                 localprogress = ((double)i/(double)total)*100.0;
00167                 cancel = ProgMeter_Update(progmeter,(localprogress*localpercent)+progress);
00168             }
00169         }
00170 
00171         for(j = 0; j < ncols; j++) {
00172             localhist[i][j].r = r;
00173             for(k = HIST_RESOL-1, sum = 0; k >= 0; k--) {
00174                 sum += localhist[i][j].mag[k];
00175                 if (sum >= localhist[i][j].numpixels*r) {
00176                     localhist[i][j].per = k;
00177                     break;
00178                 }
00179             }
00180         }
00181     }
00182 
00183     
00184     /* Global */
00185     for(k = HIST_RESOL-1, sum = 0; k >= 0; k--) {
00186         sum += globalhist->mag[k];
00187         if (sum >= globalhist->numpixels*r) {
00188             globalhist->per = k;
00189             break;
00190         }
00191     }
00192 
00193     if (progmeter) {
00194         progress = 100.0;
00195         cancel = ProgMeter_Update(progmeter,progress);
00196     }
00197 
00198     if (progmeter) {
00199         ProgMeter_Destroy(progmeter);
00200     }
00201 
00202 }
00203 
00204 
00205 
00206 /*-General Information--------------------------------------------------------*/
00207 /*                                                                            */
00208 /*  Description:   Function to compute the direction histogram.               */
00209 /*                                                                            */
00210 /*----------------------------------------------------------------------------*/
00211 /*-Interface Information------------------------------------------------------*/
00212 void HIST_DIR (
00213 IMAGE_BYTE  *iMag,        /*  I   Pointer to the gradient magnitude mosaic.   */
00214 IMAGE_BYTE  *iDir,        /*  I   Pointer to the gradient direction mosaic.   */
00215 MOSAIC_INDEX  *index,     /*  I   Pointer to the mosaic index.                */
00216 HISTOGRAM  *globalhist,   /*  I/O Pointer to the global histogram structure.  */
00217 HISTOGRAM  **localhist,   /*  I/O Address of a pointer to the local histogram.*/
00218 int nrows,                /*  I   Number of rows of blocks.                   */
00219 int ncols                 /*  I   Number of cols of blocks.                   */
00220 /*----------------------------------------------------------------------------*/
00221 ) {
00222     register int j, k;
00223     int row, col;
00224 
00225     int progmeter;
00226     double progress;
00227     double localpercent;
00228     double localprogress;
00229     int total, increment;
00230     int cancel=0;
00231 
00232     progmeter = ProgMeter_Create("Direction Histograms");
00233     progress = 0.0;
00234 
00235     if (progmeter) {
00236         localpercent = 1.0;
00237         localprogress = 0.0;
00238         total = index->hend - index->hstart;
00239         increment = rint((double)total/5.0) + 1;
00240     }
00241     
00242     for(k = index->hstart; k <= index->hend; k++) {
00243 
00244         if (progmeter) {
00245             if (((k-index->hstart)%increment) == 0) {
00246                 localprogress = ((double)(k-index->hstart)/(double)total)*100.0;
00247                 cancel = ProgMeter_Update(progmeter,(localprogress*localpercent)+progress);
00248             }
00249         }
00250 
00251         for(j = index->vstart[k]; j <= index->vend[k]; j++) {
00252 
00253             row = (index->vstart[k]-index->roi->top[0])/HIST_BLOCK_DIM;
00254             col = (k-index->hstart)/HIST_BLOCK_DIM;
00255 
00256             /* Local histogram */
00257             if (iMag->data[0][j-index->voffset[k]][k] >= localhist[row][col].per)
00258                 localhist[row][col].dir[iDir->data[0][j-index->voffset[k]][k]] += iMag->data[0][j-index->voffset[k]][k];
00259 
00260             /* Global histogram */
00261             if (iMag->data[0][j-index->voffset[k]][k] >= globalhist->per)
00262                 globalhist->dir[iDir->data[0][j-index->voffset[k]][k]] += iMag->data[0][j-index->voffset[k]][k];
00263     
00264         }
00265     }
00266 
00267     if (progmeter) {
00268         progress = 100.0;
00269         cancel = ProgMeter_Update(progmeter,progress);
00270     }
00271 
00272     if (progmeter) {
00273         ProgMeter_Destroy(progmeter);
00274     }
00275 }
00276 
00277 
00278 
00279 /*-General Information--------------------------------------------------------*/
00280 /*                                                                            */
00281 /*  Description:   Function to compute the orientation from the histogram.    */
00282 /*                                                                            */
00283 /*----------------------------------------------------------------------------*/
00284 /*-Interface Information------------------------------------------------------*/
00285 void HIST_ORIENTATION (
00286 HISTOGRAM  *globalhist,   /*  I/O Pointer to the global histogram structure.  */
00287 HISTOGRAM  **localhist,   /*  I/O Address of a pointer to the local histogram.*/
00288 int nrows,                /*  I   Number of rows of blocks.                   */
00289 int ncols                 /*  I   Number of cols of blocks.                   */
00290 /*----------------------------------------------------------------------------*/
00291 ) {
00292     register int i, j, k;
00293     int max, bin;
00294     
00295     int progmeter;
00296     double progress;
00297     double localpercent;
00298     double localprogress;
00299     int total, increment;
00300     int cancel=0;
00301 
00302     progmeter = ProgMeter_Create("Computing Ring Orientation");
00303     progress = 0.0;
00304 
00305     if (progmeter) {
00306         localpercent = 1.0;
00307         localprogress = 0.0;
00308         total = nrows;
00309         increment = rint((double)total/5.0) + 1;
00310     }
00311     
00312     /* Local */
00313     for(i = 0; i < nrows; i++) {
00314 
00315         if (progmeter) {
00316             if ((i%increment) == 0) {
00317                 localprogress = ((double)i/(double)total)*100.0;
00318                 cancel = ProgMeter_Update(progmeter,(localprogress*localpercent)+progress);
00319             }
00320         }
00321 
00322         for(j = 0; j < ncols; j++) {
00323             for(k = 0, max = 0; k < HIST_RESOL; k++) {
00324                 if (localhist[i][j].dir[k] > max) {
00325                     max = localhist[i][j].dir[k];
00326                     bin = k;
00327                 }
00328             }
00329             localhist[i][j].bin = bin;
00330             localhist[i][j].cbin = bin;
00331         }
00332     }
00333 
00334     /* Global */
00335     for(k = 0, max = 0; k < HIST_RESOL; k++) {
00336         if (globalhist->dir[k] > max) {
00337             max = globalhist->dir[k];
00338             bin = k;
00339         }
00340     }
00341     globalhist->bin = bin;
00342     globalhist->cbin = bin;
00343 
00344     if (progmeter) {
00345         progress = 100.0;
00346         cancel = ProgMeter_Update(progmeter,progress);
00347     }
00348 
00349     if (progmeter) {
00350         ProgMeter_Destroy(progmeter);
00351     }
00352     
00353 }
00354 
00355 
00356 
00357 /*-General Information--------------------------------------------------------*/
00358 /*                                                                            */
00359 /*  Description:   Function to determine orientation of the block that        */
00360 /*                 lies in the LOCAL_DEVN of global orientation.              */
00361 /*                                                                            */
00362 /*----------------------------------------------------------------------------*/
00363 /*-Interface Information------------------------------------------------------*/
00364 int HIST_DIR_OF_EDGE_NEIGHBOUR (
00365 HISTOGRAM  *globalhist,   /*  I   Pointer to the global histogram structure.  */
00366 HISTOGRAM  **localhist,   /*  I   Address of a pointer to the local histogram.*/
00367 int nrows,                /*  I   Number of rows of blocks.                   */
00368 int ncols,                /*  I   Number of cols of blocks.                   */
00369 int i,                    /*  I   Row co-ordinate of block.                   */
00370 int j                     /*  I   Column co-ordinate of block.                */
00371 /*----------------------------------------------------------------------------*/
00372 ) {
00373     int k, l;
00374     
00375     for(k = i-1; k < i+2; k ++) {
00376         if (k < 0 || k >= nrows)
00377             continue;
00378         for(l = j-1; l < j+2; l ++) {
00379             if (l < 0 || l >= ncols)
00380                 continue;
00381             
00382             if ( abs(localhist[k][l].bin - globalhist->bin) < LOCAL_DEVN )
00383                 return(localhist[k][l].bin);
00384         }
00385     }
00386 
00387     return(-1);
00388 }
00389 
00390 
00391 
00392 /*-General Information--------------------------------------------------------*/
00393 /*                                                                            */
00394 /*  Description:   Function to compute the orientation from the histogram.    */
00395 /*                                                                            */
00396 /*----------------------------------------------------------------------------*/
00397 /*-Interface Information------------------------------------------------------*/
00398 void HIST_RESOLVE (
00399 HISTOGRAM  *globalhist,   /*  I   Pointer to the global histogram structure.  */
00400 HISTOGRAM  **localhist,   /*  I/O Address of a pointer to the local histogram.*/
00401 int nrows,                /*  I   Number of rows of blocks.                   */
00402 int ncols                 /*  I   Number of cols of blocks.                   */
00403 /*----------------------------------------------------------------------------*/
00404 ) { 
00405     register int i, j;
00406     int bin;
00407     
00408     int progmeter;
00409     double progress;
00410     double localpercent;
00411     double localprogress;
00412     int total, increment;
00413     int cancel=0;
00414 
00415     progmeter = ProgMeter_Create("Resolving Ring Orientation");
00416     progress = 0.0;
00417 
00418     if (progmeter) {
00419         localpercent = 1.0;
00420         localprogress = 0.0;
00421         total = nrows;
00422         increment = rint((double)total/5.0) + 1;
00423     }
00424 
00425     for(i = 0; i < nrows; i++) {
00426 
00427         if (progmeter) {
00428             if ((i%increment) == 0) {
00429                 localprogress = ((double)i/(double)total)*100.0;
00430                 cancel = ProgMeter_Update(progmeter,(localprogress*localpercent)+progress);
00431             }
00432         }
00433 
00434         for(j = 0; j < ncols; j++) {
00435             /* Check if the local gradient orientation lies outside the LOCAL_DEVN
00436                neighbourhood of global orientation */
00437             if ( abs(localhist[i][j].bin-globalhist->bin) > LOCAL_DEVN ) {
00438                 
00439                 /* Check to see if the local orientation of any of the neighbours
00440                    lies within a LOCAL_DEVN neighbourhood of global orientation */
00441                 bin = HIST_DIR_OF_EDGE_NEIGHBOUR(globalhist, localhist, nrows, ncols, i, j);
00442 
00443                 /* If the block does not have an edge neighbour
00444                    return value is -1 */
00445                 if (bin == -1) {
00446                     localhist[i][j].bin = globalhist->bin;
00447                 } else {
00448                     localhist[i][j].bin = bin;
00449                 }
00450                 
00451             }
00452         }
00453    }
00454 
00455     if (progmeter) {
00456         progress = 100.0;
00457         cancel = ProgMeter_Update(progmeter,progress);
00458     }
00459 
00460     if (progmeter) {
00461         ProgMeter_Destroy(progmeter);
00462     }
00463     
00464 }
00465 
00466 
00467 
00468 /*-General Information--------------------------------------------------------*/
00469 /*                                                                            */
00470 /*  Description:   Function to determine the number of ring neighbours.       */
00471 /*                                                                            */
00472 /*----------------------------------------------------------------------------*/
00473 /*-Interface Information------------------------------------------------------*/
00474 int HIST_NUM_RING_NEIGH(
00475 IMAGE_BYTE  *iDir,        /*  I   Pointer to the gradient direction mosaic.   */
00476 MOSAIC_INDEX  *index,     /*  I   Pointer to the mosaic index.                */
00477 int m,                    /*  I   Row co-ordinate of pixel.                   */
00478 int n,                    /*  I   Column co-ordinate of pixel.                */
00479 int bin                   /*  I   Orientation of local block.                 */
00480 /*----------------------------------------------------------------------------*/
00481 ) {
00482     int j, k;
00483     int diff, count = 0;
00484 
00485     for(j = m - 1; j < m + 2; j++) {
00486         for(k = n - 1; k < n + 2; k++) {
00487             if (k < index->hstart || k > index->hend)
00488                 continue;
00489             if (j < index->vstart[k] || j > index->vend[k])
00490                 continue;
00491             diff = abs(iDir->data[0][j-index->voffset[k]][k] - bin);
00492             if (diff < DIR_TOL || (255-diff) < DIR_TOL)
00493                 count++;
00494         }
00495     }
00496     
00497     return(count);
00498 }
00499 
00500 
00501 
00502 /*-General Information--------------------------------------------------------*/
00503 /*                                                                            */
00504 /*  Description:   Function to suppress the non-edge pixels.                  */
00505 /*                                                                            */
00506 /*----------------------------------------------------------------------------*/
00507 /*-Interface Information------------------------------------------------------*/
00508 void HIST_SUPPRESS (
00509 IMAGE_BYTE  *iMag,        /*  I/O Pointer to the gradient magnitude mosaic.   */
00510 IMAGE_BYTE  *iDir,        /*  I   Pointer to the gradient direction mosaic.   */
00511 MOSAIC_INDEX  *index,     /*  I   Pointer to the mosaic index.                */
00512 HISTOGRAM  **localhist    /*  I   Address of a pointer to the local histogram.*/
00513 /*----------------------------------------------------------------------------*/
00514 ) {
00515     register int j, k;
00516     int bin, diff, row, col;
00517 
00518     int progmeter;
00519     double progress;
00520     double localpercent;
00521     double localprogress;
00522     int total, increment;
00523     int cancel=0;
00524 
00525     progmeter = ProgMeter_Create("Suppress Non-edge pixels");
00526     progress = 0.0;
00527 
00528     if (progmeter) {
00529         localpercent = 1.0;
00530         localprogress = 0.0;
00531         total = index->hend - index->hstart;
00532         increment = rint((double)total/5.0) + 1;
00533     }
00534 
00535     for(k = index->hstart; k <= index->hend; k++) {
00536 
00537         if (progmeter) {
00538             if (((k-index->hstart)%increment) == 0) {
00539                 localprogress = ((double)(k-index->hstart)/(double)total)*100.0;
00540                 cancel = ProgMeter_Update(progmeter,(localprogress*localpercent)+progress);
00541             }
00542         }
00543 
00544         for(j = index->vstart[k]; j <= index->vend[k]; j++) {
00545             row = (index->vstart[k]-index->roi->top[0])/HIST_BLOCK_DIM;
00546             col = (k-index->hstart)/HIST_BLOCK_DIM;
00547             bin = localhist[row][col].bin;
00548             diff = abs(iDir->data[0][j-index->voffset[k]][k] - bin);
00549 
00550             if (diff > DIR_TOL && (255-diff) > DIR_TOL) {
00551                 if (HIST_NUM_RING_NEIGH(iDir, index, j, k, bin) < 2)
00552                     iMag->data[0][j-index->voffset[k]][k] = 0;
00553             }
00554         }
00555     }
00556 
00557     if (progmeter) {
00558         progress = 100.0;
00559         cancel = ProgMeter_Update(progmeter,progress);
00560     }
00561 
00562     if (progmeter) {
00563         ProgMeter_Destroy(progmeter);
00564     }
00565 
00566 }
00567 
00568 /*-General Information--------------------------------------------------------*/
00569 /*                                                                            */
00570 /*  Description:   Function to determine the neighbour with highest gradient. */
00571 /*                                                                            */
00572 /*----------------------------------------------------------------------------*/
00573 /*-Interface Information------------------------------------------------------*/
00574 int HIST_FIND_MAX_NEIGH (
00575 IMAGE_BYTE  *iMag,        /*  I   Pointer to the gradient magnitude mosaic.   */
00576 IMAGE_BYTE  *byteimg,     /*  I   Pointer to the mosaic image.                */
00577 MOSAIC_INDEX  *index,     /*  I   Pointer to the mosaic index.                */
00578 int startx,               /*  I   Row coordinate of pixel.                    */
00579 int starty,               /*  I   Column coordinate of pixel.                 */
00580 int *newx,                /*  I   Row coordinate of neighbour.                */
00581 int *newy                 /*  I   Row coordinate of neighbour.                */
00582 /*----------------------------------------------------------------------------*/
00583 ) {
00584     int i, j, maxx, maxy, max;
00585     
00586     if (startx + 1 == index->vend[starty])
00587         return(0);
00588 
00589     max = 0;
00590     for(j = starty - 1; j < starty + 2; j++) {
00591         
00592         if (j < index->hstart || j > index->hend)
00593             continue;
00594         
00595         for(i = startx + 1; i < startx + 2; i++) {
00596 
00597             if (i < index->vstart[j] || i > index->vend[j])
00598                 continue;
00599             
00600             if (iMag->data[0][i - index->voffset[j]][j] > max) {
00601                 max = iMag->data[0][i - index->voffset[j]][j];
00602                 maxx = i;
00603                 maxy = j;
00604             }
00605         }
00606     }
00607 
00608     if (max) {
00609         *newx = maxx;
00610         *newy = maxy;
00611         return(1);
00612     }
00613     else
00614         return(0);
00615 
00616 }
00617 
00618 
00619 /*-General Information--------------------------------------------------------*/
00620 /*                                                                            */
00621 /*  Description:   Function to determine the number of neighbours.            */
00622 /*                                                                            */
00623 /*----------------------------------------------------------------------------*/
00624 /*-Interface Information------------------------------------------------------*/
00625 int HIST_NUM_NEIGH(
00626 IMAGE_BYTE  *iMag,        /*  I   Pointer to the gradient magnitude mosaic.   */
00627 MOSAIC_INDEX  *index,     /*  I   Pointer to the mosaic index.                */
00628 int m,                    /*  I   Row coordinate of pixel.                    */
00629 int n                    /*  I   Column coordinate of pixel.                 */
00630 /*----------------------------------------------------------------------------*/
00631 ) {
00632     int i, j, count = 0;
00633 
00634     for(j = n - 1; j < n + 2; j++) {
00635         if (j < index->hstart || j > index->hend)
00636             continue;
00637         for(i = m - 1; i < m + 2; i++) {
00638             if (i < index->vstart[j] || i > index->vend[j])
00639                 continue;
00640             if (iMag->data[0][i-index->voffset[j]][j] != 0)
00641                 count++;
00642         }
00643     }
00644 
00645     return(count);
00646 }