Activity 4 - Image Enhancement by Histogram Manipulation

Histogram manipulation is an image processing method that is used to enhance the contrast and improve the quality of an image. [1]

In this activity, a poor contrast image found in the web is to be enhanced by manipulating a property. Initially, the image has poor contrast, and the details are not well resolved.

Original image [2]

Left: Histogram of original image. Right: Cumulative distribution function of original image. We can see that in the histogram, the grayscale values of the pixels vary only over a small range, that is why the image is mostly gray and has poor contrast. The CDF is non-linear with a high gradient in the middle, which means the values of the histogram are mostly in the middle.

To enhance this image, we will tinker with its histogram, or its Probability Density Function (PDF). The Cumulative Distribution Function (CDF) will be projected to a desired CDF to get the desired grayscale values for a pixel. This technique is called histogram backprojection. In this technique, the desired CDF serves as a lookup table for manipulation of the histogram. [3]

Histogram Backprojection
To do this, pixel per pixel, we get the grayscale value of the original image. The value of the CDF for this grayscale value is checked in the desired CDF, and the corresponding desired grayscale value for that CDF value replaces the original grayscale value in the image.

Step by step, this is how histogram backprojection is implemented:

1. For each pixel, get the grayscale value and obtain its CDF value.
2. Get the desired grayscale value for this CDF value from the desired CDF. This can be done when you know the inverse function of your desired CDF. Initially, the desired CDF is linear.
   
3. Replace the grayscale value of the current pixel by the calculated desired grayscale value.

*Note: If the inverse is not an integer, it can be rounded off to the nearest integer.

The result:

Before and after Histogram Backprojection. The contrast is better, and the details are now clear. The outline of the door of the car in the foreground is clearer, as well as the details of the car in the middle and the details on the wall.

Histogram and Cumulative Distribution Function of processed image. Now, the histogram is well-spread. The values are not concentrated in the middle, and the range of possible grayscale values include the extreme values.The backprojection was correctly implemented because the desired linear CDF was achieved.

Nonlinear Cumulative Distribution Function
Next, a non-linear CDF is now desired. The same procedure as above was done for the desired non-linear CDF. For this example, the desired CDF was y = x^2.

Parabolic desired CDF. The values are higher in the white region than in the black region, which should result in a whiter image.

This equation is quickly increasing for the higher grayscale values, so we expect this to be whiter than the original image as well as the image processed with a linear desired CDF.

Before and after Histogram Backprojection for parabolic desired CDF. The resulting image is whiter than the original image, as well as the previous resulting image. This is because a parabolic CDF means the desired histogram is more concentrated on the white region, resulting in a white image.


Histogram and Cumulative Distribution Function of processed image. Again, the histogram is now spread over the possible grayscale values, and have more values in the right side of the plot (whiter region). The CDF matched the desired CDF.

Taking the histogram of the resulting image shows that indeed, there are more pixels with high grayscale values (values in the whiter region). The CDF matches that of the desired parabolic CDF, which means the procedure was done correctly.

I give myself 10 points for this activity. The images were enhanced using backprojection, and the resulting images had more contrast than the original one. The program can be used to manipulate images using any desired Cumulative Distribution Function.

I thank Miguel Sison and Jaya Combinido for useful discussions.

The code:
Img = round(gray_imread("C:\Documents and Settings\Yayay\My Documents\AP186\Activity 4\cargray.jpg")*256);

scf(1);
imshow(Img,[]);

[x,y] = size(Img);
img = matrix(Img, 1 ,x*y);

// histogram and CDF of image
xvals = linspace(0,255,256);
f = tabul(img);
f(:,1)=f(:,1)+1; //removes zero as an index in next calculations
hist = zeros(1,256);
for i=1:length(f(:,1)), hist(f(i,1)) = f(i,2), end;
CDF = cumsum(hist);
scf(2);
plot(xvals, hist);
scf(3);
plot(xvals,CDF);

// equation for inverse of ideal function
function invCDF = invIdeal(px)
invCDF = px^(0.5);
endfunction

// histogram backprojection
for i=1:(x*y),
px = round(invIdeal(CDF(img(i))));
img(i) = px;
end;
img = round(img*255/max(img)); //resizing x-axis to 0-255

scf(4);
newimg = matrix(img, x,y);
imshow(newimg,[]);

// histogram and CDF of new image
fnew = tabul(img);
histnew = zeros(1,256);
fnew(:,1)=fnew(:,1)+1;
for j=1:length(fnew(:,1)),
histnew(fnew(j,1)) = fnew(j,2);
end;
CDFnew = cumsum(histnew);
scf(5);
plot(xvals, histnew);
scf(6);
plot(xvals, CDFnew);

[1] A4 - Image Enhancement by Histogram Manipulation 2009.pdf (by Dr. Maricor Soriano)
[2] http://www.generation5.org/content/2004/histogramEqualization.asp
[3] http://en.wikipedia.org/wiki/Histogram_equalization

Activity 2 - Area Estimation of Images with Defined Edges

Using Paint, a simple shape was created (in this case, a 30x30 square). The background is black (0), and the object is white (1).
The area of this shape is to be estimated by implementing Green's Theorem in Scilab. The contour of the object is traced by the command follow in SIP toolbox.

Once the contour is known, the area can now be calculated using Green's Theorem. The discrete form of Green's theorem is given by [1]
where x and y are the coordinates of the contour, and Nb is the number of pixels of the contour.

Outright implementation of the above formula resulted in an error in the calculated area. It was observed that the follow command gets the inner contour for the upper right side of the image, and the outer contour for the lower left side of the image. The inner contour is closer to the center by a pixel, so a correction factor is necessary. Since it affects only half of the contour of the area, half of the perimeter of the contour is added to the calculated area.

The calculated area of the program was 841 pixels. This may seem wrong, because since the image created in Paint is 30x30, the area should be 900 pixels. However, it was observed that the pixel coordinates shown in the lower right area in Paint are off by a pixel (for example, if it shows that the pixel coordinates are (10,10), the true pixel coordinates are (9,9)). This means that the image made is actually 29x29, and the area is exactly 841 pixels.

Next, the method was tested using other shapes. Shown below are four other images with which the method was tested, and their corresponding percent errors in area estimation.

(a) (b) (c) (d)
Figure 1. Other shapes, not to scale. (a) Square: 39x39 pixels, 0% error. (b) Circle: radius = 75 pixels, 0.648% error. (c) Flower: middle square = 97x97 pixels, 0.745% error. (d) Puzzle piece: middle square = 193x193 pixels, 0.098% error.

With the correction factor, the method is 100% accurate for square and rectangular shapes. For other shapes, there are errors but only very minimal, usually less than 1%.

For this activity, I give myself 10 points. I was able to use Green's theorem to estimate the areas of objects with defined edges with less than 1% error.

Credits: Miguel Sison, Martin Tensuan.

[1] A2- Area estimation of images with defined edges.pdf (from Dr. Maricor Soriano)

Activity 3 - Image types and basic image enhancement

Activity 3

Below are samples of different image types.

Figure 1. Truecolor image. Bit depth: 24
(http://biggestmenu.com/rdr/CA/Venice/Jin-Patisserie-1591326/Macarons-23302)

Figure 2. Indexed image. Bit depth: 8
(http://en.wikipedia.org/wiki/Palette_(computing))

Figure 3. Grayscale image. Bit depth: 8
(http://www.pixelperfectdigital.com/free_stock_photos/showphoto.php/photo/7536)

Figure 4. Binary image. Bit depth: 2
(http://www.news.cornell.edu/releases/Nov99/Arecibo.message.ws.html)

Activity 1 - Digital Scanning Report

The objective of this activity was to create a digital plot from the scanned image of a plot by getting the pixel coordinates of the data points on the image and getting the corresponding physical values with the use of ratio and proportion. This method can be used when for example, only the image is available and the actual physical values are needed.

A hand-drawn plot was photocopied from The Journal of Experimental Zoology, Number 1, Volume 20 pp 431 (1916).

Figure 1. Scanned image of the plot.

Procedure
The scanned image was opened in GIMP 2, where the graph was cropped so that the unnecessary parts were removed. Using the Measure tool, 2 points on the x-axis were selected to measure the angle of rotation of the image. (The image was scanned so it might be tilted, and making sure the x-axis was horizontal would make replicating the graph easier.) The tilt was then corrected by rotating the image.

After the image pre-processing, the pixel coordinates of the origin and the data points as well as the points on the trendline were obtained. GIMP 2 displays this information of the lower left of the window. It is important to note the pixel coordinates of the origin for proper conversion of pixel counts to the actual physical values of the graph.

The pixel coordinates of the graph was corrected by subtracting the pixel coordinates of the origin to all of the pixel coordinates of the data points.

To convert the pixel coordinates to physical values, a conversion table was needed. The conversion table for the x-axis was made by dividing the physical length of the x-axis (in this case, 160 grams) by the number of pixels that span the whole x-axis (in this case, 1126 pixels). This means every pixel in the x-axis is equivalent to 0.14 grams. Doing the same thing for the y-axis, it was found that every pixel in the y-axis is equivalent to 0.42 cc/min.

By using the conversion table, the pixel coordinates is now converted to actual physical values. We now have the digital plot.

Figure 2. Digital plot of the scanned image.

To check if the plot is right, we superimpose the digital plot with the scanned image. This can be done in OpenOffice in a few steps:

1. Crop the scanned plot in GIMP, using the plot boundaries as the crop boundaries and save the image as .bmp.
   
2. In OpenOffice Draw, select Format>Area and select the Bitmap tab. Click Import and import your scanned plot.
3. In your plot in OpenOffice Calc, right-click on the chart and select Object Properties. Select the Area tab and in the drop-down menu, select Bitmap.
4. You should be able to find the imported scanned plot and use this as the background of your digital plot. Uncheck the Tile and check Autofit.

Figure 3. Digital plot (colored red) with scanned plot as background. Notice the original unfilled circles encircling the points on the digital plot.

I give myself 10 points for this activity. The digital plot and the scanned plot are well matched with only very small deviations from the scanned data points, due to difficulty in accurately pointing the cursor and in selecting the boundary for cropping (in the image, the boundaries are more than one pixel in width). I was also able to use the original scanned image as the background for the plot.

:)

A1 - Digital Scanning

Introduction
In this activity, we use ratio and proportion to find the numerical values of a digitally scanned hand-drawn plot. For now you will need the following software, Paint for finding the pixel locations of points on the graph, and Excel or OpenOffice Spreadsheet to tabluate the values of the graph.

Activity
1. Find and old journal in the CS Library and look for a hand-drawn graph from its pages. Make sure there is only one plot on the graph. Photocopy the graph.
2. Digitally scan the graph in grayscale. Except for this setting, choose your own resolution. Save the file in any standard image format such as jpg.
3. Open the image in Paint and move the mouse on the tick marks of both X and Y axis of the graph. Note down the physical values of the tick marks and through ratio and proportion, find how many pixels along the X and Y is equivalent to the physical values on each axis. Note also the image pixel location of the graph's origin.
4. Move your mouse about points on the graph. In Paint, you see these numbers at the bottom right of the application window. Tabulate in Excel or Spreadsheet their pixel locations.
5. Find an equation to relate pixel location to physical variable and use this to interpolate points on the graph.
6. Reconstruct the graph in Excel or Spreadsheet.
7. Compare the scanned graph with the reconstructed graph and rate yourself in a scale of 1 to 10 on how you accurately you were able to reconstruct the graph. (Note to Spreadsheet users, do you know that you can overlay an image on the background of your Spreadsheet graph? Bonus points to those who can find how this is done.)