Archive

Posts Tagged ‘morphology’

Ink caricature via edge detection and morphology

February 25, 2011 4 comments
Today,
I’m gonna teach you
how to turn …
 

← THIS

 

into THIS →

In this post, I’ll be showing an algorithm for generating an ink caricature out of a face photograph. Using a series of basic image processing techniques we will extract the features of the human face and then reconstruct them into a black-on-white sketch with details similar to brush (or pen) touches. This is useful for those who wish to avoid the work of manually producing such artworks. In addition, this set of methods can serve as initial groundwork for more intelligent and advanced algorithms in creating digital caricatures.

The overall algorithm can be summarized as follows:

Firstly, we choose a good threshold value to produce a satisfactory binary conversion of the raw image.  The parameter value should be sufficient to capture and preserve the important features of the face (i.e. eyes, brows, facial linings, teeth, etc.).

Applying edge detection using a spot filter would obtain the important linings of these facial aspects.

grayscaled image
binary equivalent
detected edges

Notice however that though we were able to capture the details of the face, due to the limitations of the photo (dark hair against dark background), we were not able to capture the details of the hair.  This is because the dark areas were not acquired/obtained by the chosen threshold value.  This can be resolved by applying value inversion, which changes the brightness of the pixels, but not the color.  We use the built-in method in Scilab, rgb2hsv(), to accomplish this and then revert it back its RGB representation.

img = rgb2hsv(im)
// img (:, :, 1) → HUE
// img (:, :, 2) → SATURATION
// img (:, :, 3) → VALUE

img_value = img (:,:,3);
img (:,:,3) = 1 – img_value;
im = hsv2rgb(img);

After applying the same methods performed above, the following pictures show the captured details of the photo.

grayscaled image
binary equivalent
detected edges

Next, we combine the edges detected for the face and the hair and obtain the overall edges for the face photo.

+
=

We remove the pits and holes by applying a simple morphology using a structuring element in a shape of a circle. Note that for a 5×5 matrix this would appear more like a diamond (like the one below), but it is the best shape to approximate the touch of a inkbrush or pen.

After morphology, we invert the processed image into its black-on-white equivalent and finally obtain our ink caricature.

structuring element
resulting image after morphology
inverted value (our ink caricature)

This set of methods also show to be effective for various facial expressions.

Raw images courtesy of DailyMail.

The limitations however are that (1) the methods sometimes need human supervision in choosing threshold values, so to make sure all the valuable features of the face are captured (aesthetic reasons, i.e. eyelashes, dimples, etc.).  (2) The effectiveness would depend on value contrasts, thus the need for value inversions. (3) The caricature detail would depend on the brush/pen size preferred and would greatly affect its accuracy.

———————————————————————————————–—————–————————————
References:
[1] Soriano, 2010. Binary operations. Applied Physics 186.
[2] Soriano, 2010. Fourier Transform model of image formation. Applied Physics 186.
[3] Wikipedia, 2010. Caricature.
[4] Portrait Workshop, 2010. Types of Caricatures.

Advertisements

10. Binary Operations

August 31, 2010 1 comment

Important applications, such as biomedical imaging, need the performance of accurate area detection and measurement, especially in disease examinations (e.g. malaria parasite detection, cancer cell detection). Oftentimes, noisy background obstructs the region of interest (ROI), which causes false interpretations from the image data.  Thresholding an image to binary is not able to make up for these errors due to the illegitimate features still present in the grayscaled specimen.

Methods in morphological image processing offer operators that are able to transform images and clean them from unwanted artifacts.  A good combination of the erosion and dilation techniques accomplish more sophisticated morphological operations that achieve image cleaning.  The morphological opening operator is an erosion followed by a dilation, using the same structuring element for both operations.  It reduces the size of areas that are of smaller size compared to the strel.  The closing operator, on the other hand, performs a reverse of this – it fills in small holes along areas similar to the strel.  A procedure doing opening followed by closing makes an intelligent workhorse for morphological noise removal.

For instance we have a specimen image similar to a microscope photo-capture of human cells (Figure 1).

Figure 1. An image of scattered punched paper digitized using a flatbed scanner. Suppose these circles are cells under the microscope. Courtesy of Soriano, M. [1].

We cut the big picture into sub-images of dimension 256 x 256 with slight overlap.  We perform binarization with a threshold that best captures the important parts of the image with minimal noise in the background.

Figure 2. Binarized sub-images of the cell image at optimal threshold.

For each of these images, we apply the opening and closing operations, using a structuring element shaped as a circle with a size larger than the background noise and about similar to the cells in the image.  This can then be implemented in Scilab as follows:

im = erode(im, se);    // opening, se being the cirular strel
im = dilate(im, se);
im = dilate(im, se);   // closing
im = erode(im, se);

The image, after this noise reduction method, and recombining the sub-images, produces a much excellent capture of the cells – our regions of interest (ROI) (Figure 3).

Figure 3. Cleaned image of the cell circles after undergoing morphological opening and closing operations.

In order to be able to calculate for the areas, we use the function bwlabel to distinguish connected areas in the image.

[L, n] = bwlabel(img);
area = [];
count = 1;

// scan regions for connected areas
for i = 1:n
   area(count) = length(find(L==i));
   count = count + 1;
end

Curiosity would raise a question on how to determine the area of the cells considering there are overlapping cells in the image. The best solution to this is to look into the histogram of the areas detected and find the range at which we are certain that overlaps are not involved.

scf(0); histplot(length(area), area);

This gives us a plot that tells us that most of the detected areas (which in our special case, are the unconnected ones) fall under the range 450-600 pixels (Figure 4A).  We can zoom into this range by creating a separate histogram for it (Figure 4B).

cells = find(area<600 & area>450);
scf(1); histplot(length(cells), area(cells));
Figure 4. Histogram of areas detected in the cleaned image. A. for all areas  B. for areas with no overlapping cells.

We can now calculate for the average area of the cells in this range, implemented by:

all_cells = area(cells);
average_area = sum(all_cells)/length(cells) //area
stdev_area = stdev(area(cells))             //error

Our calculations will result to an area A = 536.28 + 23.17.  To verify the integrity of this value, we attempt to measure the average area of the cells in a sub-image at which we are sure of no overlaps (Figure 5).

Figure 5. 10th sub-image of the cleaned binarized cells.

This gives us an area value A = 533.60 + 25.58, which is of no significant difference to our actual measurement.

Circles with cancer
Now that we know the area of the cells, we can now use these methods for cancer cell detection.  Suppose we have an image of cells now with the presence of enlarged blobs to portray abnormal cancer cells (Figure 6).

Figure 6. Another set of punched papers now with some “cells” bigger than the rest. Courtesy of Soriano, M. [1].

The technique here is to make an intelligent use of the morphological operations such that we can isolated the enlarged cells.  We instead use a structuring element with area greater than our previously measured area A.  We use a circular strel with radius R > sqrt[(μarea + σ) / π].  Oftentimes, R would need a larger value in order to eliminate clustered cells.  This will result to a binary image with the cancer cells isolated (Figure 7).

Figure 7. Isolated “cancer” cells from the set of punched papers.

Current intelligent systems already make more sophisticated applications of image isolation, wherein an image of a target property is captured separately based on a user-specified property identifier.  Nonetheless, it is the morphological operations that make up the fundamentals of these complex machines.

Credits to Dr. Soriano for the valuable tips and discussions.  I would rate myself 10 for doing an awesome job and enjoying the learning at the same time.

———————————————————————————————–—————–————————————
References:
[1] Soriano, 2010. Binary operations. Applied Physics 186.
[2] Mathworks, 2010. Morphology fundamentals: Dilation and erosion. Image processing toolbox.

Now that we know the area of the cells, we can now use this for cancer cell detection

9. Morphological Operations

August 8, 2010 2 comments

Morphological operations, such as erosion and dilation, transform images such that each output pixel is defined by the application of a rule on the input pixel and its neighbors.  The following table (adapted from Mathworks) summarizes the rules for these basic operations:

Operation Rule
Erosion The value of the output pixel is the minimum value of all the pixels in the input pixel’s neighborhood. In a binary image, if any of the pixels is set to 0, the output pixel is set to 0.
Dilation The value of the output pixel is the maximum value of all the pixels in the input pixel’s neighborhood. In a binary image, if any of the pixels is set to the value 1, the output pixel is set to 1.

The neighborhood of a certain pixel is defined by the structuring element used in the operation.  The function applies the rule to the input pixel and its neighbors based on the center point of the structuring element, and then assigns a value to the corresponding output pixel.  Figure 1 illustrates dilation with a 3-pixel horizontal line.

Figure 1. Morphological dilation operation with a horizontal line.  Courtesy of Mathworks.

Morphological erosion and dilation operations follow the Set Theory.  The erosion of A by structuring element B is expressed as:

This results to the reduction of the image by the shape of B.

On the other hand, the dilation of A by structuring element B is denoted by:

This results to the expansion or elongation of A in the shape of B.

———————————————————————————————–—————–————————————

In the succeeding sections, we will see the actual effect of these morphological operations on images with certain shapes when they are operated with particular strels (shortcut for structuring elements).  We have the following initial shapes:

  1. a 5×5 square
  2. a triangle (base = 4 boxes, height = 3 boxes)
  3. a 10×10 square hollow (2 boxes thick)
  4. a plus sign (one box thick, 5 boxes along each line)

The structuring elements with which we will apply the morphological rules with will be the following:

  1. 2×2 ones
  2. 2×1 ones
  3. 1×2 ones
  4. a cross (3 pixels long, one pixel thick)
  5. a diagonal line (2 pixels long, i.e. [0 1; 1, 0])

We apply the operations using Scilab’s erode() and dilate() functions, which are implemented through the following:

E = erode(Img, [SE, center])

where Img is the MxN binary image to be eroded, SE the arbitrary structuring element represented as a binary array, and center the origin of the structuring element.  Similar implementation is done with the dilate() function.

Note that the center of each structuring element should be assigned to a pixel of value 1 or “ON”.  The center for the cross strel will be pixel [2, 2].  For strels with even-numbered dimensions such as first three items listed, the center can be assigned to pixel [1, 1], while diagonal strel can have the pixel [2, 1] as center.

Erosion

The transformations resulting after erosion are shown in Figure 2, where the first row displays the initial shapes and the leftmost column displays the structuring elements.

Figure 2. Morphological erosion of basic shapes by certain structuring elements.

On binary images, erosion reduces the figures by the shape of the structuring element.  On grayscale images, the operation reduces the brightness of objects.  On certain practical applications, it is able to remove small irregularities from the image by subtracting objects that are of smaller radius compared to the structuring element.

Dilation

The results for morphological dilation is shown below (Figure 3).

Figure 3. Morphological dilation of basic shapes by certain structuring elements.

The dilation of binary images connects sections that are parted by spaces smaller compared to the structuring element.  On grayscale images, this function increases the brightness of objects.  Practical applications of this is usually to increase the size of objects and remove holes and broken areas.

Other operations such as skel and thin also impose different rules in processing images.

Using thin performs thinning of the image by means of border deletion using the Zhang-Suen technique.  The function gives an output similar to Figure 4, which was implemented simply by:

out = thin(img)
Figure 4. Morphological thinning of a stick figure.

The function skel, on the other hand, does a skeletonization of the image using the Medial Axis Transform.  Some optional parameters for processing include side [interior (default), exterior or both] and algorithm [fast euclidean (default) or exact euclidean].  It can be performed with the following script:

[skl,dt,lbl] = skel(img, 'interior', 'fast euclidean'])

Below are the figures resulting from varying the side parameter.

Figure 5. Morphological skeletonization of a stick figure using fast euclidean algorithm. Left to right: interior side, exterior side, both sides.

The fast and exact euclidean algorithm make little difference in their results.  It is only that the exact method runs relatively slower than the other.

These basic morphological operations are often used for further image processing and/or extracting information from the image.  An article following this post (soon) aims to make useful application of these methods.

I would rate myself 11 for this activity for completing the tasks and investigating for other morphological functions.

———————————————————————————————–—————–————————————
References:
[1] Soriano, 2010. Morphological operations. Applied Physics 186.
[2] Mathworks, 2010. Morphology fundamentals: Dilation and erosion. Image processing toolbox.
[3] IDL Astronomy User’s Library, 2007. Eroding and dilating image objects. NASA Goddard Space Flight Center.
[4] Wikipedia, 2010. Mathematical morphology.
[5] SIP, 2010. Scilab Image Processing Toolbox. Sourceforge Reference.

Categories: Image Processing Tags: ,