/* [<][>][^][v][top][bottom][index][help] */
DEFINITIONS
This source file includes following definitions.
- otsu
- thresholding
/*
This is a Optical-Character-Recognition program
Copyright (C) 2000-2007 Joerg Schulenburg
This program is free software; you can redistribute it and/or
modify it under the terms of the GNU General Public License
as published by the Free Software Foundation; either version 2
of the License, or (at your option) any later version.
This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU General Public License for more details.
You should have received a copy of the GNU General Public License
along with this program; if not, write to the Free Software
Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
see README for EMAIL-address
the following code was send by Ryan Dibble <dibbler@umich.edu>
The algorithm is very simple but works good hopefully.
Compare the grayscale histogram with a mass density diagram:
I think the algorithm is a kind of
divide a body into two parts in a way that the mass
centers have the largest distance from each other,
the function is weighted in a way that same masses have a advantage
- otsu algorithm is failing on diskrete multi color images
TODO:
RGB: do the same with all colors (CMYG?) seperately
test: hardest case = two colors
bbg: test done, using a two color gray file. Output:
# threshold: Value = 43 gmin=43 gmax=188
my changes:
- float -> double
- debug option added (vvv & 1..2)
- **image => *image, &image[i][1] => &image[i*cols+1]
- do only count pixels near contrast regions
this makes otsu much better for shadowed fonts or multi colored text
on white background
(m) Joerg Schulenburg (see README for email address)
ToDo:
- measure contrast
- detect low-contrast regions
*/
#include <stdio.h>
#include <string.h>
#define Abs(x) ((x<0)?-(x):x)
/*======================================================================*/
/* global thresholding routine */
/* takes a 2D unsigned char array pointer, number of rows, and */
/* number of cols in the array. returns the value of the threshold */
/*======================================================================*/
int
otsu (unsigned char *image, int rows, int cols,
int x0, int y0, int dx, int dy, int vvv) {
unsigned char *np; // pointer to position in the image we are working with
unsigned char op1, op2; // predecessor of pixel *np (start value)
int maxc=0; // maximum contrast (start value)
int thresholdValue=1; // value we will threshold at
int ihist[256]; // image histogram
int chist[256]; // contrast histogram
int i, j, k; // various counters
int is, i1, i2, ns, n1, n2, gmin, gmax;
double m1, m2, sum, csum, fmax, sb;
// zero out histogram ...
memset(ihist, 0, sizeof(ihist));
memset(chist, 0, sizeof(chist));
op1=op2=0;
gmin=255; gmax=0; k=dy/512+1;
// v0.43 first get max contrast, dont do it together with next step
// because it failes if we have pattern as background (on top)
for (i = 0; i < dy ; i+=k) {
np = &image[(y0+i)*cols+x0];
for (j = 0; j < dx ; j++) {
ihist[*np]++;
if(*np > gmax) gmax=*np;
if(*np < gmin) gmin=*np;
if (Abs(*np-op1)>maxc) maxc=Abs(*np-op1); /* new maximum contrast */
if (Abs(*np-op2)>maxc) maxc=Abs(*np-op2); /* new maximum contrast */
/* we hope that maxc will be find its maximum very fast */
op2=op1; /* shift old pixel to next older */
op1=*np; /* store old pixel for contrast check */
np++; /* next pixel */
}
}
// generate the histogram
// Aug06 images with large white or black homogeneous
// areas give bad results, so we only add pixels on contrast edges
for (i = 0; i < dy ; i+=k) {
np = &image[(y0+i)*cols+x0];
for (j = 0; j < dx ; j++) {
if (Abs(*np-op1)>maxc/4
|| Abs(*np-op2)>maxc/4)
chist[*np]++; // count only relevant pixels
op2=op1; /* shift old pixel to next older */
op1=*np; /* store old pixel for contrast check */
np++; /* next pixel */
}
}
// set up everything
sum = csum = 0.0;
ns = 0;
is = 0;
for (k = 0; k <= 255; k++) {
sum += (double) k * (double) chist[k]; /* x*f(x) cmass moment */
ns += chist[k]; /* f(x) cmass */
is += ihist[k]; /* f(x) imass */
// Debug: output to out_hist.dat?
// fprintf(stderr,"\chistogram %3d %6d (brightness weight)", k, ihist[k]);
}
if (!ns) {
// if n has no value we have problems...
fprintf (stderr, "NOT NORMAL, thresholdValue = 160\n");
return (160);
}
// ToDo: only care about extremas in a 3 pixel environment
// check if there are more than 2 mass centers (more colors)
// return object colors and color radius instead of threshold value
// also the reagion, where colored objects are found
// what if more than one background color? no otsu at all?
// whats background? box with lot of other boxes in it
// threshold each box (examples/invers.png,colors.png)
// get maximum white and minimum black pixel color (possible range)
// check range between them for low..high contrast ???
// typical scenes (which must be covered):
// - white page with text of different colors (gray values)
// - binear page: background (gray=1) + black text (gray=0)
// - text mixed with big (dark) images
// ToDo: recursive clustering for maximum multipol moments?
// idea: normalize ihist to max=1024 before otsu?
// do the otsu global thresholding method
if ((vvv&1)) // Debug
fprintf(stderr,"# threshold: value ihist chist mass_dipol_moment\n");
fmax = -1.0;
n1 = 0;
for (k = 0; k < 255; k++) {
n1 += chist[k]; // left mass (integration)
if (!n1) continue; // we need at least one foreground pixel
n2 = ns - n1; // right mass (num pixels - left mass)
if (n2 == 0) break; // we need at least one background pixel
csum += (double) k *chist[k]; // left mass moment
m1 = csum / n1; // left mass center (black chars)
m2 = (sum - csum) / n2; // right mass center (white background)
// max. dipol moment?
// orig: sb = (double) n1 *(double) n2 * (m1 - m2) * (m1 - m2);
sb = (double) n1 *(double) n2 * (m2 - m1); // seems to be better Aug06
/* bbg: note: can be optimized. */
if (sb > fmax) {
fmax = sb;
thresholdValue = k + 1;
// thresholdValue = (m1 + 3 * m2) / 4;
}
if ((vvv&1) && ihist[k]) // Debug
fprintf(stderr,"# threshold: %3d %6d %6d %8.2f\n",
k, ihist[k], chist[k],
sb/(dx*dy)); /* normalized dipol moment */
}
// ToDo: error = left/right point where sb is 90% of maximum?
// now we count all pixels for background detection
i1 = 0;
for (k = 0; k < thresholdValue; k++) {
i1 += ihist[k]; // left mass (integration)
}
i2 = is - i1; // right mass (num pixels - left mass)
// at this point we have our thresholding value
// black_char: value<cs, white_background: value>=cs
// can it happen? check for sureness
if (thresholdValue > gmax) {
fprintf(stderr,"# threshold: Value >gmax\n");
thresholdValue = gmax;
}
if (thresholdValue <= gmin) {
fprintf(stderr,"# threshold: Value<=gmin\n");
thresholdValue = gmin+1;
}
// debug code to display thresholding values
if ( vvv & 1 )
fprintf(stderr,"# threshold: Value = %d gmin=%d gmax=%d cmax=%d"
" i= %d %d\n",
thresholdValue, gmin, gmax, maxc, i1, i2);
if (i1>=4*i2) { // black>=4*white, obviously black is background
if ( vvv & 1 )
fprintf(stderr,"# threshold: invert the image\n");
// we do inversion here (no data lost)
for (i = 0; i < dy ; i++) {
np = &image[(y0+i)*cols+x0];
for (j = 0; j < dx ; j++) {
*np=255-*np;
np++; /* next pixel */
}
}
thresholdValue=255-thresholdValue+1;
}
return(thresholdValue);
/* range: 0 < thresholdValue <= 255, example: 1 on b/w images */
/* 0..threshold-1 is foreground */
/* threshold..255 is background */
/* ToDo: min=blackmasscenter/2,thresh,max=(whitemasscenter+255)/2 */
}
/*======================================================================*/
/* thresholding the image (set threshold to 128+32=160=0xA0) */
/* now we have a fixed thresholdValue good to recognize on gray image */
/* - so lower bits can used for other things (bad design?) */
/* ToDo: different foreground colors, gray on black/white background */
/*======================================================================*/
int
thresholding (unsigned char *image, int rows, int cols,
int x0, int y0, int dx, int dy, int thresholdValue) {
unsigned char *np; // pointer to position in the image we are working with
int i, j; // various counters
int gmin=255,gmax=0;
int nmin=255,nmax=0;
// calculate min/max (twice?)
for (i = y0 + 1; i < y0 + dy - 1; i++) {
np = &image[i*cols+x0+1];
for (j = x0 + 1; j < x0 + dx - 1; j++) {
if(*np > gmax) gmax=*np;
if(*np < gmin) gmin=*np;
np++; /* next pixel */
}
}
/* allowed_threshold=gmin+1..gmax v0.43 */
if (thresholdValue<=gmin || thresholdValue>gmax){
thresholdValue=(gmin+gmax+1)/2; /* range=0..1 -> threshold=1 */
fprintf(stderr,"# thresholdValue out of range %d..%d, reset to %d\n",
gmin, gmax, thresholdValue);
}
/* b/w: min=0,tresh=1,max=1 v0.43 */
// actually performs the thresholding of the image...
// later: grayvalues should also be used, only rescaling threshold=160=0xA0
for (i = y0; i < y0+dy; i++) {
np = &image[i*cols+x0];
for (j = x0; j < x0+dx; j++) {
*np = (unsigned char) (*np >= thresholdValue ?
(255-(gmax - *np)* 80/(gmax - thresholdValue + 1)) :
( 0+(*np - gmin)*150/(thresholdValue - gmin )) );
if(*np > nmax) nmax=*np;
if(*np < nmin) nmin=*np;
np++;
}
}
// fprintf(stderr,"# thresholding: nmin=%d nmax=%d\n", nmin, nmax);
return(128+32); // return the new normalized threshold value
/* 0..159 is foreground */
/* 160..255 is background */
}