Algorithm to determine image contrast

How to determine image contrast ? More specifically - How to determine that image contrast is low and it needs automatic contrast adjustment through histogram equalization method ?

Algorithm is this:
1. Calculate cumulative histogram of image.
2. Make linear regression of cumulative histogram in the form freq(x) = A*x + B.
3. Calculate RMSE of real_cumulative_frequency(x)-freq(x).
4. If that RMSE is close to zero - image is already equalized and should be in good contrast. (That means for equalized images cumulative histograms must be linear)

Because picture is worth a thousand words - this is how cumulative histograms looks for image with different levels of contrast:

So as you see - image with most aggressive contrast has cumulative histogram which is almost a perfect line.

Now fun part - C code which opens image in PGM format with ASCII encoding and detects if image needs contrast adjustment or not :

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>

#define MAX_COLS 1000
#define MAX_ROWS 1000

typedef struct {
 int Width;
 int Height;
 int max_value;
 int data[MAX_ROWS][MAX_COLS];
} PGMdata;

void readPgmFile(char* fileName, PGMdata * pgmOut) {
 FILE * pFile;
 char line[1000];
 char* res;
 int lineNum = 0;

 if ((pFile = fopen(fileName , "r")) == NULL)
  printf("Error opening file %s \n", fileName);
 else {
  while ((res = fgets(line, 100, pFile)) != NULL) {
  lineNum++;
  // max value of pixel
  if (lineNum==4)
   sscanf(line,"%i",&pgmOut->max_value);
  // width and height of image
  if (lineNum==3) {
   sscanf(line,"%i %i",&pgmOut->Width, &pgmOut->Height);
  }
  // load real pixels
  if (lineNum > 4) {
   int ix = lineNum - 5;
   int row = ix/pgmOut->Width;
   int col = ix - row*pgmOut->Width;
   sscanf(line,"%i", &pgmOut->data[row][col]);
  }
  }
  fclose(pFile);
    }
}

void CumulativeHistogram(PGMdata* image, double* hist) {
 int i,j;
 double dp = 1.0/((double) image->Width*image->Height);

 // initializing histogram bins to zero
 for (i=0; i<256; i++) {
  hist[i] = 0.0;
 }

 // calculating histogram
 for (i=0; i<image->Width; i++) {
  for (j=0; j<image->Height; j++) {
   hist[image->data[j][i]] += dp;
  }
 }

 // making histogram cumulative
 for (i=0; i<255; i++) {
  hist[i+1] += hist[i];
 }
}

void CreateXmatrix(double mat[256][2]) {
 int i;
 for (i=0; i<256; i++) {
   mat[i][0] = 1;
   mat[i][1] = i;
 }
}

void TransposeMatrix(double mat[256][2], double tmat[2][256]) {
 int i,j;
 for (i=0; i<2; i++) {
  for (j=0; j<256; j++) {
   tmat[i][j] = mat[j][i];
  }
 }
}

double MultiplyMatrixes(double A[2][256], double B[256][2], int row, int col) {
 int i;
 double sum = 0.0;

 for (i=0; i<256; i++) {
  sum += A[row][i]*B[i][col];
 }

 return sum;
}

double MultiplyMatrixAndVector(double A[2][256], double Y[256], int row) {
 int i;
 double sum = 0.0;

 for (i=0; i<256; i++) {
  sum += A[row][i]*Y[i];
 }

 return sum;
}

double HistogramPredicted(double c0, double c1, double level) {
 return c0 + c1*level;
}

double RootMeanSquare(double* hist, double c0, double c1) {
 double rms = 0.0;
 int i;

 for (i=0; i<256; i++) {
  rms += pow(hist[i]-HistogramPredicted(c0,c1,i),2.0);
 }
 rms /= 256.0;

 return sqrt(rms);
}

void LinearLeastSquares(double* hist, double* c0, double* c1) {
 double X[256][2];
 double tX[2][256];
 double a1,a2,a3,a4;
 double b1, b2;

 // create matrix X composed of x'es
 CreateXmatrix(X);

 // transpose X matrix
 TransposeMatrix(X,tX);

 // calculate tX*X matrix which is
 // [a1 a2]
 // [a3 a4]

 a1 = MultiplyMatrixes(tX,X,0,0);
 a2 = MultiplyMatrixes(tX,X,0,1);
 a3 = MultiplyMatrixes(tX,X,1,0);
 a4 = MultiplyMatrixes(tX,X,1,1);

 // calculate tX*Y  (Y=HISTOGRAM) which is
 // [b1]
 // [b2]

 b1 = MultiplyMatrixAndVector(tX,hist,0);
 b2 = MultiplyMatrixAndVector(tX,hist,1);

 // solve matrix equation by using elimination of variables method
 // [a1 a2]   [c0]   [b1]
 //         *      =
 // [a3 a4]   [c1]   [b2]

 *c1 = (a1*b2-a3*b1)/(a1*a4-a2*a3);
 *c0 = (b1-a2*(*c1))/a1;

}

int main () {
 double hist[256];
 static PGMdata image = {0};
 double c0=0.0, c1=0.0;
 double rms;
 char pgm_file[20] = {0};

 while (1) {
   // get PGM file name
   printf("PGM filename: ");
   scanf("%s", pgm_file);

   // read grayscale image from PGM format
   memset(&image, 0, sizeof(image));
   readPgmFile(pgm_file, &image);
   if (image.Width == 0)
     continue;

   // create cumulative histogram
   CumulativeHistogram(&image, hist);

   // least mean squares method, to find c0,c1 coefficents in equation:
   // c0 + c1*gray_level = Frequency
   LinearLeastSquares(hist,&c0,&c1);

   // calculate RMS of Frequency[bin]-predicted_Frequency(bin)
   rms = RootMeanSquare(hist,c0,c1);

   // Low RMS shows that histogram frequencies are distributed in linear fashion
   // between bins. This means that histogram equalization was performed on image
   // and/or that global image contrast is good.
   if (rms <= 0.01)
    printf("\n==> %s contrast is OK (rms=%f)\n\n", pgm_file ,rms);
   else
    printf("\n==> %s contrast is BAD (rms=%f)\n\n", pgm_file ,rms);
 }

 return 0;
}

If you want to test this algorithm on ASCII PGM image - you better covert image to PGM format with GIMP 2.6.11, because it was only tested in this way.
So by running this C code on below image (after converting it to PGM)

we get algorithm output
"image contrast is BAD ... " :-)

Three doors problem

There is very interesting problem which solution seems unintuitive, but indeed is correct. Also problem is called Monty Hall paradox. Problem definition is this:
-------------------------------------------------------------
Suppose you're on a game show and you're given the choice of three doors. Behind one door is a car; behind the others, goats [that is, booby prizes]. The car and the goats were placed randomly behind the doors before the show. The rules of the game show are as follows: After you have chosen a door, the door remains closed for the time being. The game show host, Monty Hall, who knows what is behind the doors, now has to open one of the two remaining doors, and the door he opens must have a goat behind it. If both remaining doors have goats behind them, he chooses one randomly. After Monty Hall opens a door with a goat, he will ask you to decide whether you want to stay with your first choice or to switch to the last remaining door. Imagine that you chose Door 1 and the host opens Door 3, which has a goat. He then asks you "Do you want to switch to Door Number 2?" Is it to your advantage to change your choice?
-------------------------------------------------------------
Now what is probability that switching to last remaining door will reveal a car ?
This probability is 2/3. I will not explain it here, because it is very well explained in wikipedia site. It is more interesting to note that problem solution gets somewhat different when one must taken into account host bias. That is - what if host will have freedom to offer (or not) switching door ? If we define probability of host offering door switch when one looses (chooses door with goat) as Pol, and probability of host offering door switch when one wins (chooses door with car) as Pow. Then we can relate these two probabilities as
Pow=1-Pol and define host bias, which is bias=Pol-Pow.
So now we have required information and we can conduct experiment/simulation which will reveal host bias impact on probability that door switching wins.

Experiment algorithm is as follows -
1. Take some bias from the range [-1;1]
2. Calculate Pow,Pol according this bias.
3. Simulate 500 000 games with this bias.
3a. According to these probabilities Pow,Pol - offer (or not) door change to player.
3b. If switch was offered and switching win the car - increase won games.
4. Calculate win probability when switching doors, with current host bias.
5. Repeat everything from 1. until bias range is covered.

Code which did these measurements is this (this time coded in plain good C):

---

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

struct Game {
 int PrizeDoor;
 int ChosenDoor;
 int RevealDoor;
 int OtherDoor;
};

// Reveal one empty door and calculate what door left for changing
void OpenDoor(struct Game *gm) {
 for (int i=0; i!=3; ++i) {
  if (i!=gm->ChosenDoor && i!=gm->PrizeDoor ) {
   gm->RevealDoor = i;
   gm->OtherDoor = 3 - (gm->ChosenDoor + gm->RevealDoor);
   break;
  }
 }
}

// Calculate probability that changing door wins a prize.
// This probability is dependent on host bias towards the fair play.
// Bias +1 - host only offers to change door when one looses.
// Bias  0 - host offers to change door when one looses or wins.
// Bias -1 - host only offers to change door when one wins.
float ProbabilityChangeWins(float bias, int games) {
 float Pol, Pow, Prob, ProbChangeWins ;
 int TotalWins = 0, gamesWithOffers = 0;
 struct Game gm;

 Pol = (bias+1.0)/2.0;
 Pow = 1.0-Pol;
 srand(time(NULL));

 // Main game test loop. The doors are numbered as 0,1,2.
 for (int i=0; i!=games; ++i) {
  gm.PrizeDoor  = rand()%3;
  gm.ChosenDoor = rand()%3;
  Prob = (gm.PrizeDoor == gm.ChosenDoor) ? Pow : Pol; 
  // host offers to change doors based on his bias.
  if (((float)rand()/RAND_MAX) < Prob) {
   gamesWithOffers++;
   OpenDoor(&gm);
   TotalWins += (gm.OtherDoor == gm.PrizeDoor);
  }
 }
 ProbChangeWins = ((float)TotalWins)/gamesWithOffers;

 return ProbChangeWins;
}

int main(void)
{
 for (float i = -1.0; i < 1.05; i+=0.05)
  printf("Bias = %1.2f | ProbabilityOfChangeWins = %1.2f\n",
      i,ProbabilityChangeWins(i,500000));
 
 return 0;
}

---

Results of this experiment is graph plotted as switch win probability dependence on host bias:

Results is interesting and can be seen that host bias can shift "standard" problem solution very much.

Conclusions
1. Host can affect game outcome in such a way that switching doors always looses game or always wins game - in the case of marginal host bias values -1/+1.
2. If host is neutral (bias=0) then problem solution becomes the same as in "standard" way - swithing doors wins with the 2/3 probability.
3. Even if host is slightly shifted toward negative bias, that is bias > -0.3, switching doors is still beneficial.
4. What is more interesting that host bias can be established from the probability of win when switching doors. This means that from people who participated in that game and switched doors we can deduce host bias and tell if the game was fair or in what "amount" it was fair.

Have fun with probabilities and three door problem !