Posts Tagged ‘backprojection’

13. Color image segmentation

September 23, 2010 2 comments

Image segmentation is the process where a region of interest (ROI) is extracted from the image for further processing. Noting that segmentation is more often not feasible for grayscale images, one of the features this process utilizes is the ROI’s unique true color. This method has been widely used for practical applications such as remote sensing, microscopy and object recognitions.

Parametric vs. Non-Parametric Probability Distribution Estimation

Color-based segmentation can be performed by finding the probability wherein a pixel falls within a distribution of interest.  Parametric segmentation finds the Gaussian probability distribution function (PDF) in the R and G values of the ROI in order then to segment the whole image.  Non-parametric segmentation, on the other hand, finds the 2D histogram of the ROI and uses it to segment the image using histogram backprojection.

Parametric Segmentation

For instance, we have an image of a 3D object with a single color and crop a monochromatic region of interest in the picture (Figure 1).

Figure 1. A 3D object with a single color. A. a red mug, B. region of interest (ROI)

We transform the RGB color of the image into normalized chromaticity coordinates (NCC), such that:

It is important to note that r + g + b = 1, and b is dependent on r and g since b = 1 – r – g.  We implement this process in Scilab as follows:

R = ROI(:, :, 1);
G = ROI(:, :, 2);
B = ROI(:, :, 3);
I = R + G + B;

I (find(I==0)) = 1000000;

r = R ./ I;
g = G ./ I;

The probability p(r) tells how much a pixel with chromaticity r belongs to the ROI:

We find these necessary factors from our r and g values:

mu_r = mean(r);
mu_g = mean(g);
sigma_r = stdev(r);
sigma_g = stdev(g);

Using these values we apply segmentation to the entire image by calculating the probabilities for r and g.

im = imread('3D_object.png');

R = im(:, :, 1);
G = im(:, :, 2);
B = im(:, :, 3);

I = R + G + B;
I (find(I==0)) = 1000000;

r = R ./ I;
g = G ./ I;

Pr = (1/(sigma_r*sqrt(2*%pi)))*exp(-((r - mu_r).^2)/(2*(sigma_r^2)));
Pg = (1/(sigma_g*sqrt(2*%pi)))*exp(-((g - mu_g).^2)/(2*(sigma_g^2)));

The joint probability is taken as the product of p(r) and p(g).

joint_probability = Pr.*Pg;
imshow(joint_probability, []);

Figure 2 shows the extracted portions from the image via segmentation.

Figure 2. Extracted region of interest (ROI) after applying parametric segmentation.

Non-parametric segmentation

Here we will use the 2D histogram of the r and g values of the image to do the segmentation.  After normalizing all pixels, we tag their membership by calculating finding the histogram of the r and g values in a matrix.

BINS = 32;
rint = round(r*(BINS-1) + 1);
gint = round(g*(BINS-1) + 1);

colors = gint(:) + (rint(:)-1)*BINS;
hist = zeros(BINS, BINS);
for row = 1:BINS
   for col = 1:(BINS-row+1)
      hist(row, col) = length(find(colors==( ((col + (row-1)*BINS)))));

The resulting matrix when rotated such that the origin is at the lower left corner, produces the 2D histogram for the ROI membership, which can be interpreted from the normalized chromaticity space or NCS (Figure 3).

Figure 3. A. 2D histogram for pixel membership; B. the Normalized Chromaticity Space (NCS)

Using this histogram, we can now apply segmentation to the image by means of backprojection. After finding the r and g values:

arsize = size(r);
rows = arsize(1);
cols = arsize(2);

backproj = zeros(rows, cols);

for i=1:rows
   for j=1:cols
      r_val = r(i, j);
      g_val = g(i, j);
      r_new = round(r_val*(BINS-1) + 1);
      g_new = round(g_val*(BINS-1) + 1);
      backproj(i, j) = hist(r_new, g_new);
      // replace pixel with the value

imshow(backproj, []);

Figure 4 shows the segmented image resulting from the non-parametric method.

Figure 4. Extracted region of interest (ROI) after applying non-parametric segmentation.

Comparing the segmented images obtained from the two algorithms, it can be observed that the non-parametric method has extracted a larger part of the region of interest (ROI).  The parametric method, on the other hand, has segmented sections that can be said to be sharper and smoother with respect to the objects surface (Gaussian approximation).  These two techniques, though different in their results, display good use for different scenes under different conditions.  Knowing the pros and cons of each, we would be able to wisely choose the right method for every need for segmentation.

For this section, I would rate myself 10 for being able to produce the outputs from both segmentation methods.

Credits: Dennis D., Tin C., and Marou R.

[1] Soriano, 2010. Color image segmentation. Applied Physics 186.
[2] The Scilab Reference Manual. 2010.


5. Image Enhancement by Histogram Manipulation

July 6, 2010 4 comments

An image histogram is a representation of the frequency distribution of values in an image.  It plots the number of pixels there are containing particular tonal values.  Photographers oftentimes use histogram manipulation in order to restore the proper contrast of the images or simply depict a particular mood on the scenery.

If Px(i) is the image histogram for pixel value i, the cumulative distribution function (or CDF) for all pixel values is expressed as

Images are easily modified and best manipulated using cumulative frequencies.  Backprojection is referred to as the method of manipulating an image’s CDF to conform a desired distribution.  This is performed by tracing back the frequency of a particular pixel tone towards the desired CDF and then replace it with its new corresponding value.

Figure 1. Image histogram manipulation by means of backprojection.

For instance we have the image below as an example of a poor-contrast image, with its image histogram and CDF shown on the attached plots.

Figure 2. An example of a dark photograph (in grayscale). Courtesy of M. Beslac.

Using Scilab and the SIVP toolbox, we can improve the image by implementing histogram manipulation through the backprojection algorithm.  First, we use the built-in function imhist() to obtain the image histogram from the grayscale image.  We used plot2d3() to allow us to plot our data in vertical bars.

I = imread('fakefree.jpg');
J = rgb2gray(I);

[counts, cells] = imhist(J);      // defaults to 256 bins
scf(0); plot2d3(cells, counts, rect=[0,0, 256, max(counts)]);
 // rect=[xmin, ymin, xmax, ymax]

We then utilize the function cumsum(), which returns an array corresponding to the cumulative distribution. Note that in our implementation we perform a normalization for the CDF.

cumulative_sum = cumsum(counts);
cumsum_max = max(cumulative_sum);
cdf = cumulative_sum/cumsum_max;  // normalized cumsum

scf(1); plot2d(cells, cdf, rect=[0, 0, 256, max(cdf)]);

For better coding practices, we create a self-defined function to solve for the x-values of the traced frequencies on our CDF plot. If for instance we desire to imitate a linear function obeying the equation y = (1/255)*x, we design our function to do an inverse of this relation. (This code snippet of the function may be placed at the beginning of the code or in a separate file.)

function inv_linearCDF = invLinearCDF(y)
  y = y*255;                          // denormalization
  inv_linearCDF = round(y);           // linear_cdf = (1/255)*x

Note that we performed denormalization on the CDF in order to work with actual values, and used the function round() for discrete approximations.  Next, we create a second image matrix – a copy of the original – where we will later apply the changes due to our manipulation. Iterating towards each pixel value, we retrace the individual frequencies and replace them with new pixel values on the second image.

K = J;      // a copy of the original image

for i = 1:256
  new_x = invLinearCDF(cdf(i));
  K (find(J==i-1)) = new_x;    // i-1 referring to pixel values (range:0-255)

Below is the new image now approximately conforming to the linear distribution.

Figure 3. Histogram manipulated image via backprojection towards a linear CDF.

We can perform the same method with non-linear distributions such as the parabolic function, implemented similar to the one below.

function inv_parabolicCDF = invParabolicCDF(y)
  y = y*255^2;                         // denormalization
  inv_parabolicCDF = round(sqrt(y));   // parabolic_cdf(x) = x^2

We may also apply this with a logarithmic function:

function inv_logarithmicCDF = invLogarithmicCDF(y)
  y = y*log(255);                      // denormalization
  inv_logarithmicCDF = round(exp(y));  // logarithmic_cdf(x) = log(x)

The following are the image results of the previous two non-linear functions, including their manipulated histograms and cumulative frequencies. We can observe how the images are similar to an overexposed and underexposed image.

Figure 4. Image backprojected towards (1) a parabolic CDF; (2) a logarithmic CDF.

Photographers usually use image processing softwares to easily perform histogram manipulation on photographs. GIMP or the GNU Image Manipulation Program (a FOSS graphics editor), offers this capability via graphical interface.  To navigate to this function, go to Colors > Curves.  Make sure the image is initial set to grayscale by choosing Image > Mode > Grayscale.  Here is a snapshot of an actual curve manipulation on GIMP.

Figure 5. Desktop snapshot of GIMP running the curve manipulation feature.

Now, being able to adjust images via histogram manipulation, we can achieve improved images with better brightness and color contrast.

For this segment, I would rate myself 11 for understanding the important ideas and, in addition, for exploring a software that applies the image enhancement method.

[1] Esporlas, C., 2009. Histogram backprojection. Applied Physics 186.
[2] Photoxels, 2010. Digital photography tutorial: Histogram.
[3] Soriano, M., 2010. Image enhancement by histogram manipulation. Applied Physics 186.
[4] Wikipedia, 2010. Histogram equalization.
[5] Wikipedia, 2010. Image histogram.