diff options
author | giraffedata <giraffedata@9d0c8265-081b-0410-96cb-a4ca84ce46f8> | 2007-05-22 03:12:47 +0000 |
---|---|---|
committer | giraffedata <giraffedata@9d0c8265-081b-0410-96cb-a4ca84ce46f8> | 2007-05-22 03:12:47 +0000 |
commit | 009d9aaa47db122f8161cd37c227e8d9159f1b1a (patch) | |
tree | 0689afec3d4256a4656d5fa9dd58635ac6eee0e9 | |
parent | 560b89d81de1360e0369b69ea34249f8bb8841c6 (diff) | |
download | netpbm-mirror-009d9aaa47db122f8161cd37c227e8d9159f1b1a.tar.gz netpbm-mirror-009d9aaa47db122f8161cd37c227e8d9159f1b1a.tar.xz netpbm-mirror-009d9aaa47db122f8161cd37c227e8d9159f1b1a.zip |
Release 10.38.03
git-svn-id: http://svn.code.sf.net/p/netpbm/code/advanced@306 9d0c8265-081b-0410-96cb-a4ca84ce46f8
-rw-r--r-- | Makefile.version | 2 | ||||
-rw-r--r-- | doc/HISTORY | 7 | ||||
-rw-r--r-- | editor/pamthreshold.c | 182 | ||||
-rw-r--r-- | lib/pam.h | 7 |
4 files changed, 127 insertions, 71 deletions
diff --git a/Makefile.version b/Makefile.version index 4f7fc74a..750487b0 100644 --- a/Makefile.version +++ b/Makefile.version @@ -1,4 +1,4 @@ NETPBM_MAJOR_RELEASE = 10 NETPBM_MINOR_RELEASE = 38 -NETPBM_POINT_RELEASE = 02 +NETPBM_POINT_RELEASE = 03 diff --git a/doc/HISTORY b/doc/HISTORY index 11ee9324..c88c066e 100644 --- a/doc/HISTORY +++ b/doc/HISTORY @@ -4,6 +4,13 @@ Netpbm. CHANGE HISTORY -------------- +07.05.22 BJH Release 10.38.03 + + pamthreshold: fix totally bogus threshold selection with + simple thresholding. + + PAM_STRUCT_SIZE: cast pointer to ulong instead of uint. + 07.05.09 BJH Release 10.38.02 Configure: fix bug detecting presence of libvga with diff --git a/editor/pamthreshold.c b/editor/pamthreshold.c index 4caaed9b..016dde64 100644 --- a/editor/pamthreshold.c +++ b/editor/pamthreshold.c @@ -300,6 +300,119 @@ analyzeDistribution(struct pam * const inpamP, static void +computeWhiteBlackMeans(const unsigned int * const histogram, + sample const maxval, + float const threshold, + float * const meanBlackP, + float * const meanWhiteP) { +/*---------------------------------------------------------------------------- + Assuming that histogram[] and 'maxval' describe the pixels of an image, + find the mean value of the pixels that are below 'threshold' and + that are above 'threshold'. +-----------------------------------------------------------------------------*/ + unsigned int nWhite, nBlack; + /* Number of would-be-black, would-be-white pixels */ + uint64_t sumBlack, sumWhite; + /* Sum of all the would-be-black, would-be-white pixels */ + sample gray; + + assert(threshold * maxval <= maxval); + + for (gray = 0, nBlack = 0, sumBlack = 0; + gray < threshold * maxval; + ++gray) { + nBlack += histogram[gray]; + sumBlack += gray * histogram[gray]; + } + for (nWhite = 0, sumWhite = 0; gray <= maxval; ++gray) { + nWhite += histogram[gray]; + sumWhite += gray * histogram[gray]; + } + + *meanBlackP = (float)sumBlack / nBlack / maxval; + *meanWhiteP = (float)sumWhite / nWhite / maxval; +} + + + +static void +computeGlobalThreshold(struct pam * const inpamP, + const unsigned int * const histogram, + struct range const globalRange, + float * const thresholdP) { +/*---------------------------------------------------------------------------- + Compute the proper threshold to use for the image described by + *inpamP, whose file is positioned to the raster. + + For our convenience: + + 'histogram' describes the frequency of occurence of the various sample + values in the image. + + 'globalRange' describes the range (minimum, maximum) of sample values + in the image. + + Return the threshold (scaled to [0, 1]) as *thresholdP. +-----------------------------------------------------------------------------*/ + /* Found this algo in the wikipedia article "Thresholding (image + processing)." It is said to be a special one-dimensional case + of the "k-means clustering algorithm." + + The article claims it's proven to converge, by the way. + We have an interation limit just as a safety net. + + This code originally implemented a rather different algorithm, + while nonetheless carrying the comment that it implemented the + Wikipedia article. I changed it to match Wikipedia in May 2007 + (at that time there was also a fatal bug in the code, so it + didn't implement any intentional algorithm). + + In May 2007, the Wikipedia article described an enhancement of + the algorithm that uses a weighted average. But that enhancement + actually reduces the entire thing to: set the threshold to the + mean pixel value. It must be some kind of mistake. We use the + unenhanced version of the algorithm. + */ + + float threshold; /* threshold is iteratively determined */ + float oldthreshold; /* stop if oldthreshold==threshold */ + unsigned int iter; /* count of done iterations */ + + assert(betweenZeroAndOne(globalRange.min)); + assert(betweenZeroAndOne(globalRange.max)); + + /* Use middle value (halfway between min and max) as initial threshold */ + threshold = (globalRange.min + globalRange.max) / 2.0; + + oldthreshold = -1.0; /* initial value */ + iter = 0; /* initial value */ + + /* adjust threshold to image */ + while (fabs(oldthreshold - threshold) > 2.0/inpamP->maxval && + iter < MAX_ITERATIONS) { + float meanBlack, meanWhite; + + ++iter; + + computeWhiteBlackMeans(histogram, inpamP->maxval, threshold, + &meanBlack, &meanWhite); + + assert(betweenZeroAndOne(meanBlack)); + assert(betweenZeroAndOne(meanWhite)); + + oldthreshold = threshold; + + threshold = (meanBlack + meanWhite) / 2; + } + + assert(betweenZeroAndOne(threshold)); + + *thresholdP = threshold; +} + + + +static void getLocalThreshold(tuplen ** const inrows, unsigned int const windowWidth, unsigned int const x, @@ -388,75 +501,6 @@ thresholdLocalRow(struct pam * const inpamP, static void -computeGlobalThreshold(struct pam * const inpamP, - const unsigned int * const histogram, - struct range const globalRange, - float * const thresholdP) { -/*---------------------------------------------------------------------------- - Compute the proper threshold to use for the image described by - *inpamP, whose file is positioned to the raster. - - For our convenience: - - 'histogram' describes the frequency of occurence of the various sample - values in the image. - - 'globalRange' describes the range (minimum, maximum) of sample values - in the image. - - Return the threshold (scaled to [0, 1]) as *thresholdP. - - Leave the file positioned to the raster. ------------------------------------------------------------------------------*/ - /* Found this algo in the wikipedia article "Thresholding (image - processing)" - */ - - float threshold; /* threshold is iteratively determined */ - float oldthreshold; /* stop if oldthreshold==threshold */ - unsigned int iter; /* count of done iterations */ - - /* Use middle value (halfway between min and max) as initial threshold */ - threshold = (globalRange.min + globalRange.max) / 2.0; - - oldthreshold = -1.0; /* initial value */ - iter = 0; /* initial value */ - - /* adjust threshold to image */ - while (fabs(oldthreshold - threshold) > 0.01 && iter < MAX_ITERATIONS) { - unsigned long white, black; /* number of white, black pixels */ - unsigned int row; - - ++iter; - - /* count black and white pixels */ - - for (row = 0, white = 0, black = 0; row < inpamP->height; ++row) { - unsigned int col; - - for(col = 0; col < threshold * inpamP->maxval; ++col) - black += histogram[col]; - for(; col <= inpamP->maxval; ++col) - white += histogram[col]; - } - - oldthreshold = threshold; - - /* Use the weighted average of black and white pixels to calculate new - threshold - */ - threshold = - (black * (globalRange.min + threshold) / 2.0 + - white * (threshold + globalRange.max) / 2.0) / - (black + white); - } - - *thresholdP = threshold; -} - - - -static void thresholdLocal(struct pam * const inpamP, struct pam * const outpamP, struct cmdlineInfo const cmdline) { diff --git a/lib/pam.h b/lib/pam.h index e66b831d..8f9f5d12 100644 --- a/lib/pam.h +++ b/lib/pam.h @@ -118,8 +118,13 @@ struct pam { member named x. This is useful in conjunction with the 'len' value to determine which fields are present in the structure. */ + +/* Some compilers are really vigilant and recognize it as an error + to cast a 64 bit address to a 32 bit type. Hence the roundabout + casting in PAM_MEMBER_OFFSET. +*/ #define PAM_MEMBER_OFFSET(mbrname) \ - ((unsigned int)(char*)&((struct pam *)0)->mbrname) + ((size_t)(unsigned long)(char*)&((struct pam *)0)->mbrname) #define PAM_MEMBER_SIZE(mbrname) \ sizeof(((struct pam *)0)->mbrname) #define PAM_STRUCT_SIZE(mbrname) \ |