C# How to: Weighted Difference of Gaussians

Article Purpose

It is the purpose of this article to illustrate the concept of  . This article extends the conventional implementation of algorithms through the application of equally sized   only differing by a weight factor.

Frog: Kernel 5×5, Weight1 0.1, Weight2 2.1

Frog: Kernel 5x5, Weight1 0.1, Weight2 2.1

Sample Source Code

This article is accompanied by a sample source code Visual Studio project which is available for download here.

Using the Sample Application

This article relies on a sample application included as part of the accompanying sample source code. The sample application serves as a practical implementation of the concepts explored throughout this article.

The sample application user interface enables the user to configure and control the implementation of a filter. The configuration options exposed through the sample application’s user interface can be detailed as follows:

  • Load/Save Images – When executing the sample application users are able to load source/input from the local system through clicking the Load Image button. If desired, the sample application enables users to save resulting to the local file system through clicking the Save Image button.
  • Kernel Size – This option relates to the size of the that is to be implemented when performing through . Smaller are faster to compute and generally result in detected in the source/input to be expressed through thinner gradient edges. Larger can be computationally expensive to compute as sizes increase. In addition, the edges detected in source/input will generally be expressed as thicker gradient edges in resulting .
  • Weight Values – The sample application calculates   and in doing so implements a weight factor. A Weight Factor determines the blur intensity observed in result after having applied . Higher weight factors result in a more intense level of being applied. As expected, lower weight factors values result in  a less intense level of being applied. If the value of the first weight factor exceeds the value of the second weight factor resulting will be generated with a Black background and edges being indicated in White. In a similar fashion, when the second weight factor value exceeds that of the first weight factor resulting will be generated with a White background and edges being indicated in Black. The greater the difference between the first and second weight factor values result in a greater degree of removal. When weight factor values only differ slightly, resulting may be prone to .

The following image is screenshot of the Weighted Difference of Gaussians sample application in action:

Weighted Difference Of Gaussians Sample Application

Frog: Kernel 5×5, Weight1 1.8, Weight2 0.1

Frog: Kernel 5x5, Weight1 1.8, Weight2 0.1

Gaussian Blur

The algorithm can be described as one of the most popular and widely implemented methods of . From we gain the following excerpt:

A Gaussian blur (also known as Gaussian smoothing) is the result of blurring an image by a Gaussian function. It is a widely used effect in graphics software, typically to reduce image noise and reduce detail. The visual effect of this blurring technique is a smooth blur resembling that of viewing the image through a translucent screen, distinctly different from the bokeh effect produced by an out-of-focus lens or the shadow of an object under usual illumination. Gaussian smoothing is also used as a pre-processing stage in computer vision algorithms in order to enhance image structures at different scales.

Mathematically, applying a Gaussian blur to an image is the same as convolving the image with a Gaussian function. This is also known as a two-dimensional Weierstrass transform.

Take Note: The algorithm has the attribute of smoothing detail/definition whilst also having an edge preservation attribute. When applying a to an a level of detail/definition will be blurred/smoothed away, done in a fashion that would exclude/preserve edges.

Frog: Kernel 5×5, Weight1 2.7, Weight2 0.1

Frog: Kernel 5x5, Weight1 2.7, Weight2 0.1

Difference of Gaussians Edge Detection

refers to a specific method of . , common abbreviated as DoG, functions through the implementation of .

A clear and concise description can be found on the Wikipedia Article Page:

In imaging science, difference of Gaussians is a feature enhancement algorithm that involves the subtraction of one blurred version of an original image from another, less blurred version of the original. In the simple case of grayscale images, the blurred images are obtained by convolving the original grayscale images with Gaussian kernels having differing standard deviations. Blurring an image using a Gaussian kernel suppresses only high-frequency spatial information. Subtracting one image from the other preserves spatial information that lies between the range of frequencies that are preserved in the two blurred images. Thus, the difference of Gaussians is a band-pass filter that discards all but a handful of spatial frequencies that are present in the original grayscale image.

In a conventional sense involves applying to created as copies of the original source/input . There must be a difference in the size of the implemented when applying . A typical example would be applying a 3×3 on one copy whilst applying a 5×5 on another copy. The final step requires creating a result populated by subtracting the two blurred copies. The results obtained from subtraction represents the edges forming part of the source/input .

This article extends beyond the conventional method of implementing . The implementation illustrated in this article retains the core concept of subtracting values which have been blurred to different intensities. The implementation method explored here differs from the conventional method in the sense that the implemented do not differ in size. Both are in fact required to have the same size dimensions.

The implemented are equal in terms of their size dimensions, although values are different. Expressed from another angle: equally sized of which one represents a more intense level of than the other. A resulting intensity can be determined by the weight factor implemented when calculating the values.

Frog: Kernel 5×5, Weight1 3.7, Weight2 0.2

Frog: Kernel 5x5, Weight1 3.7, Weight2 0.2

The advantages of implementing equally sized can be described as follows:

Single Convolution implementation:  involves executing several nested code loops. Application performance can be severely negatively impacted when executing large nested loops. The conventional method of implementing generally involves having to implement two instances of , once per copy. The method implemented in this article executes the code loops related to only once. Considering the are equal in size, both can be iterated within the same set of loops.

Eliminating Image subtraction: In conventional implementations expressing differing intensity levels of have to be subtracted. The implementation method described in this article eliminates the need to perform subtraction. When applying using both simultaneously the two results obtained, one  from each , can be subtracted and assigned to the result . In addition, through calculating both results at the same time further reduces the need to create two temporary source copies.

Frog: Kernel 5×5, Weight1 2.4, Weight2 0.3

Frog: Kernel 5x5, Weight1 2.4, Weight2 0.3

Difference of Gaussians Edge Detection Required Steps

When implementing a several steps are required, those steps are detailed as follows:

  1. Calculate Kernels – Before implementing two have to be calculated. The calculated are required to be of equal size and differ in intensity. The sample application allows the user to configure intensity through updating the weight values, expressed as Weight 1 and Weight 2.
  2. Convert Source Image to Grayscale – Applying on   outperforms on RGB . When converting an RGB pixel to a pixel, colour components are combined to form a single gray level intensity. In other words a   consists of a third of the number of pixels when compared to the RGB from which the had been rendered. In the case of an ARGB the derived will be expressed in 25% of the number of pixels forming part of the source ARGB . When applying the number of processor cycles increases when the pixel count increases.
  3. Perform Convolution Implementing Thresholds – Using the newly created perform for both calculated in the first step. The result value equates to subtracting the two results obtained from .  If the result value exceeds the difference between the first and second weight value, the resulting pixel should be set to White, if not, set the result pixel to Black.

Frog: Kernel 5×5, Weight1 2.1, Weight2 0.5

Frog: Kernel 5x5, Weight1 2.1, Weight2 0.5

Calculating Gaussian Convolution Kernels

The sample application implements calculations. The implemented in are calculated at runtime, as opposed to being hard coded. Being able to dynamically construct has the advantage of providing a greater degree of control in runtime regarding application.

Several steps are involved in calculating . The first required step being to determine the Size and Weight. The size and weight factor of a comprises the two configurable values implemented when calculating . In the case of this article and the sample application those values will be configured by the user through the sample application’s user interface.

The formula implemented in calculating can be expressed as follows:

Gaussian Formula

The formula contains a number of symbols, which define how the filter will be implemented. The symbols forming part of the formula are described in the following list:

  • G(x y) – A value calculated using the Kernel formula. This value forms part of a , representing a single element.
  • π – Pi, one of the better known members of the Greek alphabet. The mathematical constant defined as 22 / 7.
  • σ – The lower case version of the Greek alphabet letter Sigma. This symbol simply represents a threshold or factor value, as specified by the user.
  • e – The formula references a lower case e symbol. The symbol represents . The value of has been defined as a mathematical constant equating to 2.71828182846.
  • x, y – The variables referenced as x and y relate to pixel coordinates within an . y Representing the vertical offset or row and x represents the horizontal offset or column.

Note: The formula’s implementation expects x and y to equal zero values when representing the coordinates of the pixel located in the middle of the .

Frog: Kernel 7×7, Weight1 0.1, Weight2 2.0

Frog: Kernel 7x7, Weight1 0.1, Weight2 2.0

Implementing Gaussian Kernel Calculations

The sample application defines the GaussianCalculator.Calculate method. This method accepts two parameters, kernel size and kernel weight. The following code snippet details the implementation:

public static double[,] Calculate(int lenght, double weight) 
{
    double[,] Kernel = new double [lenght, lenght]; 
    double sumTotal = 0; 

int kernelRadius = lenght / 2; double distance = 0;
double calculatedEuler = 1.0 / (2.0 * Math.PI * Math.Pow(weight, 2));
for (int filterY = -kernelRadius; filterY <= kernelRadius; filterY++) { for (int filterX = -kernelRadius; filterX <= kernelRadius; filterX++) { distance = ((filterX * filterX) + (filterY * filterY)) / (2 * (weight * weight));
Kernel[filterY + kernelRadius, filterX + kernelRadius] = calculatedEuler * Math.Exp(-distance);
sumTotal += Kernel[filterY + kernelRadius, filterX + kernelRadius]; } }
for (int y = 0; y < lenght; y++) { for (int x = 0; x < lenght; x++) { Kernel[y, x] = Kernel[y, x] * (1.0 / sumTotal); } }
return Kernel; }

Frog: Kernel 3×3, Weight1 0.1, Weight2 1.8

Frog: Kernel 3x3, Weight1 0.1, Weight2 1.8

Implementing Difference of Gaussians Edge Detection

The sample source code defines the DifferenceOfGaussianFilter method. This method has been defined as an targeting the class. The following code snippet provides the implementation:

public static Bitmap DifferenceOfGaussianFilter(this Bitmap sourceBitmap,  
                                                int matrixSize, double weight1, 
                                                double weight2) 
{
    double[,] kernel1 =  
    GaussianCalculator.Calculate(matrixSize,  
    (weight1 > weight2 ? weight1 : weight2)); 

double[,] kernel2 = GaussianCalculator.Calculate(matrixSize, (weight1 > weight2 ? weight2 : weight1));
BitmapData sourceData = sourceBitmap.LockBits(new Rectangle (0, 0, sourceBitmap.Width, sourceBitmap.Height), ImageLockMode.ReadOnly, PixelFormat.Format32bppArgb);
byte[] pixelBuffer = new byte [sourceData.Stride * sourceData.Height]; byte[] resultBuffer = new byte [sourceData.Stride * sourceData.Height]; byte[] grayscaleBuffer = new byte [sourceData.Width * sourceData.Height];
Marshal.Copy(sourceData.Scan0, pixelBuffer, 0, pixelBuffer.Length); sourceBitmap.UnlockBits(sourceData);
double rgb = 0;
for (int source = 0, dst = 0; source < pixelBuffer.Length && dst < grayscaleBuffer.Length; source += 4, dst++) { rgb = pixelBuffer * 0.11f; rgb += pixelBuffer * 0.59f; rgb += pixelBuffer * 0.3f;
grayscaleBuffer[dst] = (byte)rgb; }
double color1 = 0.0; double color2 = 0.0;
int filterOffset = (matrixSize - 1) / 2; int calcOffset = 0;
for (int source = 0, dst = 0; source < grayscaleBuffer.Length && dst + 4 < resultBuffer.Length; source++, dst += 4) { color1 = 0; color2 = 0;
for (int filterY = -filterOffset; filterY <= filterOffset; filterY++) { for (int filterX = -filterOffset; filterX <= filterOffset; filterX++) { calcOffset = source + (filterX) + (filterY * sourceBitmap.Width);
calcOffset = (calcOffset < 0 ? 0 : (calcOffset >= grayscaleBuffer.Length ? grayscaleBuffer.Length - 1 : calcOffset));
color1 += (grayscaleBuffer[calcOffset]) * kernel1[filterY + filterOffset, filterX + filterOffset];
color2 += (grayscaleBuffer[calcOffset]) * kernel2[filterY + filterOffset, filterX + filterOffset]; } }
color1 = color1 - color2; color1 = (color1 >= weight1 - weight2 ? 255 : 0);
resultBuffer[dst] = (byte)color1; resultBuffer[dst + 1] = (byte)color1; resultBuffer[dst + 2] = (byte)color1; resultBuffer[dst + 3] = 255; }
Bitmap resultBitmap = new Bitmap(sourceBitmap.Width, sourceBitmap.Height);
BitmapData resultData = resultBitmap.LockBits(new Rectangle (0, 0, resultBitmap.Width, resultBitmap.Height), ImageLockMode.WriteOnly, PixelFormat.Format32bppArgb);
Marshal.Copy(resultBuffer, 0, resultData.Scan0, resultBuffer.Length); resultBitmap.UnlockBits(resultData);
return resultBitmap; }

Frog: Kernel 3×3, Weight1 2.1, Weight2 0.7

Frog: Kernel 3x3, Weight1 2.1, Weight2 0.7

Sample Images

This article features a number of sample images. All featured images have been licensed allowing for reproduction. The following image files feature as sample images:

Panamanian Golden Frog

Panamanian Golden Frog

Dendropsophus Microcephalus

Dendropsophus Microcephalus

Tyler’s Tree Frog

Tyler's Tree Frog

Mimic Poison Frog

Mimic Poison Frog

Phyllobates Terribilis

Phyllobates Terribilis

Related Articles and Feedback

Feedback and questions are always encouraged. If you know of an alternative implementation or have ideas on a more efficient implementation please share in the comments section.

I’ve published a number of articles related to imaging and images of which you can find URL links here:

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s




about.me :: Dewald Esterhuizen

Dewald Esterhuizen

Blog Stats

  • 168,825 hits

Gravatar :: Dewald Esterhuizen

SoftwareByDefault QR Code

SoftwareByDefault QR Code

I review for the O'Reilly Blogger Review Program

Enter your email address to follow and receive notifications of new posts by email.

Join 152 other followers

Archives

Twitter feed

RSS SoftwareByDefault on MSDN

  • An error has occurred; the feed is probably down. Try again later.

del.icio.us Links

http://softwarebydefault.com
http://softwarebydefault.com
http://softwarebydefault.com
http://softwarebydefault.com
http://softwarebydefault.com

Follow

Get every new post delivered to your Inbox.

Join 152 other followers

%d bloggers like this: