13,197,117 members (61,419 online)
alternative version

#### Stats

101.4K views
107 bookmarked
Posted 19 Jul 2010

# Pixel Shader for Edge Detection and Cartoon Effect

, 19 Aug 2010
 Rate this:
Implementation of Sobel Edge Detection and Cartoon Effect using pixel shader.

## Introduction

This article explains the implementation of the Sobel Edge Detection method in a pixel shader using C++. And also the implementation of Cartoon effect of an image with edge information.

Input image (TajMahal.bmp)

Screenshot of edge detection output of TajMahal.bmp

Screenshot of Cartoon effect output of TajMahal.bmp

Another screenshot of Cartoon effect

## Background

Edge detection is simple image processing, which aims at identifying points in a digital image at which the image brightness changes sharply, or more formally, has discontinuities. Sobel Edge detection uses implementation of the Sobel operator as explained in http://en.wikipedia.org/wiki/Sobel_operator.

After implementing edge detection, I found a simple technique to make the cartoon effect image by combining the input image and its edge image.

## Using the code

Initially, we can look at the C++ implementation of the Sobel Edge detection method. Two kernels are applied to each pixel. One kernel finds the color change [gradient] in the X direction, and the other finds the color change [gradient] in the Y direction.

The below section describes how these matrices are applied to a sample image.

This is the sample image, and we can see how the X directional and Y directional gradient calculations work.

Sample image used to explain the X directional and Y directional gradient calculation

The code below finds out the changes in the X direction. Just find the weighted sum of the surrounding 3 * 3 pixels.

```// Initializing X direction gradient kernel.
GX[0][0] = -1; GX[0][1] = 0; GX[0][2] = 1;
GX[1][0] = -2; GX[1][1] = 0; GX[1][2] = 2;
GX[2][0] = -1; GX[2][1] = 0; GX[2][2] = 1;

// Looping to findout change in X diretion
for(I=-1; I<=1; I++)
{
for(J=-1; J<=1; J++)
{
sumX = sumX + (int)( (*(stOriginalImage_i.pData + nX + I +
(nY + J)*stOriginalImage_i.nCols)) * GX[I+1][J+1]);
}
}```

Here is the output image of the X directional gradient calculation:

The output of the X directional gradient calculation

The code below finds out the changes in the Y direction. Just find the weighted sum of the surrounding 3 * 3 pixels.

```// Initializing Y direction gradient kernel.
GY[0][0] =  1; GY[0][1] =  2; GY[0][2] =  1;
GY[1][0] =  0; GY[1][1] =  0; GY[1][2] =  0;
GY[2][0] = -1; GY[2][1] = -2; GY[2][2] = -1;
// Looping to findout change in Y diretion
for(I=-1; I<=1; I++)
{
for(J=-1; J<=1; J++)
{
sumY = sumY + (int)( (*(stOriginalImage_i.pData + nX + I +
(nY + J)*stOriginalImage_i.nCols)) * GY[I+1][J+1]);
}
}```

Here is the output image of the Y directional gradient calculation:

Output image of the Y directional gradient calculation

## Final image calculation

Finally, the X and Y directional gradient values are combined with the following equation:

and the code:

`SUM =  sqrt(double(sumX * sumX) + double(sumY * sumY));`

Here is the output:

Output image of the test bitmap

## Edge Detection of RGB Image

This logic is used to find out the gradient for a single component image. I used this algorithm for each component of the input image [R, G, B] separately and combined the output together.

```// Extract each component[R,G,B] to separate buffer to find gradient in
// each component.
BYTE* pbyTemp = pbyBMP_io;
for (int n= 0; n < nWidth * nHeight; n++)
{
originalImageR.pData[n] = *pbyTemp++; // Blue
originalImageG.pData[n] = *pbyTemp++; // Green
originalImageB.pData[n] = *pbyTemp++; // Red
}

// Find Gradient of each component separately.
FindEdge( originalImageR, OutputRed );
FindEdge( originalImageG, OutputGreen );
FindEdge( originalImageB, OutputBlue );

// Combine RGB gradient information to a output buffer.
pbyTemp = pbyBMP_io;
for (int n= 0; n < nWidth * nHeight; n++)
{
*pbyTemp++ = OutputRed.pData[n];
*pbyTemp++ = OutputGreen.pData[n];
*pbyTemp++ = OutputBlue.pData[n];
}```

Here is the entire code of the gradient calculation of a component:

```void EdgeDetectCPU::FindEdge( ImageInfo_t& stOriginalImage_i,
ImageInfo_t& stEdgeImage_o )
{
int        nX, nY,I, J;
long            sumX, sumY;
int            nColors, SUM;
int            GX[3][3];
int            GY[3][3];
// Allocate output buffer
stEdgeImage_o.pData =
new BYTE[stOriginalImage_i.nCols * stOriginalImage_i.nRows];

GX[0][0] = -1; GX[0][1] = 0; GX[0][2] = 1;
GX[1][0] = -2; GX[1][1] = 0; GX[1][2] = 2;
GX[2][0] = -1; GX[2][1] = 0; GX[2][2] = 1;

GY[0][0] =  1; GY[0][1] =  2; GY[0][2] =  1;
GY[1][0] =  0; GY[1][1] =  0; GY[1][2] =  0;
GY[2][0] = -1; GY[2][1] = -2; GY[2][2] = -1;

// Iterate each pixels in the image.
for(nY=0; nY<=(stOriginalImage_i.nRows-1); nY++)
{
for(nX=0; nX<=(stOriginalImage_i.nCols-1); nX++)
{
sumX = 0;
sumY = 0;

SUM = 0;
if( !(nX==0 || nX==stOriginalImage_i.nCols-1 ||
nY==0 || nY==stOriginalImage_i.nRows-1))
{
// Looping to findout change in X direction
for(I=-1; I<=1; I++)
{
for(J=-1; J<=1; J++)
{
sumX = sumX + (int)( (*(stOriginalImage_i.pData + nX + I +
(nY + J)*stOriginalImage_i.nCols)) * GX[I+1][J+1]);
}
}

// Looping to find out change in Y direction
for(I=-1; I<=1; I++)
{
for(J=-1; J<=1; J++)
{
sumY = sumY + (int)( (*(stOriginalImage_i.pData + nX + I +
(nY + J)*stOriginalImage_i.nCols)) * GY[I+1][J+1]);
}
}
SUM =  sqrt(double(sumX * sumX) + double(sumY * sumY));
}

if(SUM>255) SUM=255;
if(SUM<0) SUM=0;
*(stEdgeImage_o.pData + nX + nY * stOriginalImage_i.nCols) =
255 - (unsigned char)(SUM);
}
}
}```

## Cartoon Effect Implementation

The edge information of an image is now done. Cartoon effect can be simply created with this edge image and its input data. Just combine the edge image and its corresponding input image. The following figure illustrates the creation of a cartoon effect with the edge image.

Cartoon effect created by combining the edge image and input image

The following code explains the Cartoon effect implementation with the edge image. `EdgeDetectCPU::FindEdge` is modified to create a cartoon effect or edge image based on the `m_bCartoonEffect` flag.

```if(SUM>255) SUM=255;
if(SUM<0) SUM=0;
int nOut = 0;
// Checking Cartoon Effect flag to create final image.
if( m_bCartoonEffect )
{
// Make Cartoon effect by combining edge information and original image.
nOut = (SUM * 0.5) + (*(stOriginalImage_i.pData + nX +
nY * stOriginalImage_i.nCols) * 0.5);
}
else
{
// Creating displayable edge data.
nOut = 255 - (unsigned char)(SUM);
}
*(stEdgeImage_o.pData + nX + nY * stOriginalImage_i.nCols) = nOut;```

I hope this logic is very simple to port to a pixel shader, since the logic of the gradient calculation for a pixel is common function, and that can be applied to each pixel of the image. And the gradient calculation of a pixel does not depend on the output of the other pixel calculations (it is difficult to implement a pixel shader, if one pixel output depends on the output of the other pixel). Therefore, I removed the two `for` loops (that are used for the iteration of each pixel in the bitmap) in the pixel shader. The remaining task for creating the pixel shader is to convert some data types to the shader compatible data types. For example, the shader does not support two dimensional arrays, but it provides a matrix data type that can be used similar to a two dimensional array. Here is the X,Y gradient matrix declaration in the shader.

```// X directional search matrix.
mat3 GX = mat3( -1.0, 0.0, 1.0,
-2.0, 0.0, 2.0,
-1.0, 0.0, 1.0 );
// Y directional search matrix.
mat3 GY =  mat3( 1.0,  2.0,  1.0,
0.0,  0.0,  0.0,
-1.0, -2.0, -1.0 );```

The texture coordinates received in the pixel shader are used to find out the `nX`, `nY` values of the C++ `for` loop code.

```// Findout X , Y index of incoming pixel from its texture coordinate.
float fXIndex = gl_TexCoord[0].s * fWidth;
float fYIndex = gl_TexCoord[0].t * fHeight;```

And the entire pixel shader for edge detection and Cartoon effect is:

```// Image texture.
uniform sampler2D ImageTexture;

// Width of Image.
uniform float fWidth;
// Height of Image.
uniform float fHeight;
// Indicating cartoon effect is enabled or not.
uniform float fCartoonEffect;

void main()
{
// X directional search matrix.
mat3 GX = mat3( -1.0, 0.0, 1.0,
-2.0, 0.0, 2.0,
-1.0, 0.0, 1.0 );
// Y directional search matrix.
mat3 GY =  mat3( 1.0,  2.0,  1.0,
0.0,  0.0,  0.0,
-1.0, -2.0, -1.0 );

vec4  fSumX = vec4( 0.0,0.0,0.0,0.0 );
vec4  fSumY = vec4( 0.0,0.0,0.0,0.0 );
vec4 fTotalSum = vec4( 0.0,0.0,0.0,0.0 );

// Findout X , Y index of incoming pixel
// from its texture coordinate.
float fXIndex = gl_TexCoord[0].s * fWidth;
float fYIndex = gl_TexCoord[0].t * fHeight;

/* image boundaries Top, Bottom, Left, Right pixels*/
if( ! ( fYIndex < 1.0 || fYIndex > fHeight - 1.0 ||
fXIndex < 1.0 || fXIndex > fWidth - 1.0 ))
{
for(float I=-1.0; I<=1.0; I = I + 1.0)
{
for(float J=-1.0; J<=1.0; J = J + 1.0)
{
float fTempX = ( fXIndex + I + 0.5 ) / fWidth ;
float fTempY = ( fYIndex + J + 0.5 ) / fHeight ;
vec4 fTempSumX = texture2D( ImageTexture, vec2( fTempX, fTempY ));
fSumX = fSumX + ( fTempSumX * vec4( GX[int(I+1.0)][int(J+1.0)],
GX[int(I+1.0)][int(J+1.0)],
GX[int(I+1.0)][int(J+1.0)],
GX[int(I+1.0)][int(J+1.0)]));
}
}

{ // Y Directional Gradient calculation.
for(float I=-1.0; I<=1.0; I = I + 1.0)
{
for(float J=-1.0; J<=1.0; J = J + 1.0)
{
float fTempX = ( fXIndex + I + 0.5 ) / fWidth ;
float fTempY = ( fYIndex + J + 0.5 ) / fHeight ;
vec4 fTempSumY = texture2D( ImageTexture, vec2( fTempX, fTempY ));
fSumY = fSumY + ( fTempSumY * vec4( GY[int(I+1.0)][int(J+1.0)],
GY[int(I+1.0)][int(J+1.0)],
GY[int(I+1.0)][int(J+1.0)],
GY[int(I+1.0)][int(J+1.0)]));
}
}
// Combine X Directional and Y Directional Gradient.
vec4 fTem = fSumX * fSumX + fSumY * fSumY;
fTotalSum = sqrt( fTem );
}
}
// Checking status of cartoon effect.
if( 0.5 < fCartoonEffect )
{
// Creaing cartoon effect by combining
// edge informatioon and original image data.
fTotalSum = mix( fTotalSum, texture2D( ImageTexture,
vec2( gl_TexCoord[0].s, gl_TexCoord[0].t)), 0.5);
}
else
{
// Creating displayable edge data.
fTotalSum = vec4( 1.0,1.0,1.0,1.0) - fTotalSum;
}

gl_FragColor = ( fTotalSum );
}```

The Cartoon effect or edge image is the output of this shader. This program will be executed for each pixels of the image, and this program will calculate the edge information for each pixel. Then at the final stage, the `fCartoonEffect` flag is used to make the output color of the shader. `fCartoonEffect` is set from the application to the shader based on the state of the `CartoonEffect` check box.

```// Checking status of cartoon effect.
if( 0.5 < fCartoonEffect )
{
// Creaing cartoon effect by combining edge
// informatioon and original image data.
fTotalSum = mix( fTotalSum, texture2D( ImageTexture,
vec2( gl_TexCoord[0].s, gl_TexCoord[0].t)), 0.5);
}
else
{
// Creating displayable edge data.
fTotalSum = vec4( 1.0,1.0,1.0,1.0) - fTotalSum;
}```

I think more explanation on this pixel shader is not required because we have already discussed the X directional and Y directional gradient (change) calculations in the above C++ logic.

## Save Functionality

The Save button of the Edge Detection application can be used to save the output of the Edge Detection algorithm to a BMP file. The Save functionality simply reads the pixels from the screen using the `glReadPixels()` API.

Here is the code to read the pixel information from the screen:

```pbyData = new BYTE[stImageArea.bottom * stImageArea.right  * 3];
if( 0 == pbyData )
{
AfxMessageBox( L"Memory Allocation failed" );
return;
}
GL_BGR_EXT, GL_UNSIGNED_BYTE, pbyData );
SaveBmp.SaveBMP( csFileName, stImageArea.right, stImageArea.bottom, pbyData );```

The file name creation code for saving is a tricky one:

```CString csFileName;
// This one create different names in CPU mode and GPU mode.
csFileName.Format( L"EdgeDetection_%s_%d.bmp",
( RUN_IN_CPU == m_nRunIn ) ? L"CPU" : L"GPU",
( RUN_IN_CPU == m_nRunIn ) ? ++nCPUCount : ++nGPUCount );
CFileDialog SaveDlg( false, L"*.bmp", csFileName );```

An example of different names generated in CPU and GPU mode: EdgeDetection_GPU_1.bmp, EdgeDetection_CPU_1.bmp.

## Points of Interest

The 4 byte boundary padding of BMP data made some difficulty for edge detection calculation in CPU. The CPU edge detection is specially handled when the number of columns of the bitmap is not a multiple of 4. When edge detection is performed without considering the padding data [BMP file contains some unexpected value in the padding pixels], I get a strange output image, because the buffer provided to `EdgeDetectCPU` contains some unwanted data in the padded pixels. Therefore, I followed these steps to avoid the issue:

1. Removed unexpected pixels padded at the right end of the image to make the columns a multiple of 4.
2. Find out the edge image using `EdgeDetect.EdgeDetect( m_nImageWidth, m_nImageHeight, pbyImage )`.

The code below handles this special case:

```// Extract each component[R,G,B] to separate buffer to find gradient in
// each component.
BYTE* pbyTemp = pbyBMP_io;
for (int n= 0; n < nWidth * nHeight; n++)
{
originalImageR.pData[n] = *pbyTemp++; // Blue
originalImageG.pData[n] = *pbyTemp++; // Green
originalImageB.pData[n] = *pbyTemp++; // Red
}

// Find Gradient of each component separately.
FindEdge( originalImageR, OutputRed );
FindEdge( originalImageG, OutputGreen );
FindEdge( originalImageB, OutputBlue );

// Combine RGB gradient information to a output buffer.
pbyTemp = pbyBMP_io;
for (int n= 0; n < nWidth * nHeight; n++)
{
*pbyTemp++ = OutputRed.pData[n];
*pbyTemp++ = OutputGreen.pData[n];
*pbyTemp++ = OutputBlue.pData[n];
}```

`BMPLoader::LoadBMP` uses GDI+ to load an image file. It uses the `GDIPlus::Bitmap` class to read an image from a file. `m_pBitmap->LockBits()` provides the image data.

```// Code for reading Image file from file using GDI+
Gdiplus::Bitmap* m_pBitmap = new Gdiplus::Bitmap(pFileName_i, true);

BYTE* pbyData = 0;
int nWidth = m_pBitmap->GetWidth();
int nHeight = m_pBitmap->GetHeight();
Gdiplus::Rect rect(0,0,nWidth,nHeight);
Gdiplus::BitmapData pBMPData;
PixelFormat24bppRGB, &pBMPData );
pbyData_o = new BYTE[nWidth * nHeight * 3];
nWidth_o = nWidth;
nHeight_o = nHeight;
if( 0 == pBMPData.Scan0 )
{
return false;
}
BYTE* pSrc = (BYTE*)pBMPData.Scan0;
int nVert = nHeight - 1;
for( int nY = 0; nY < nHeight && nVert > 0; nY++ )
{
// Avoid top and bottom difference.
BYTE* pDest = pbyData_o + ( nWidth * nVert * 3 );
memcpy( pDest, pSrc, 3 * nWidth);
nVert--;
pSrc += ( nWidth * 3 );
}
m_pBitmap->UnlockBits( &pBMPData );```

## History

• 19 July 2010 - Initial version.
• 28 July 2010 - Added the `AppError` class to display an error message if the shader creation fails.
• 14 August 2010 - Added Cartoon effect functionality.

## Share

 India
No Biography provided

## You may also be interested in...

 First PrevNext
 question Member 1225753614-Jan-16 6:37 Member 12257536 14-Jan-16 6:37
 Re: question Santhosh G_15-Jan-16 8:35 Santhosh G_ 15-Jan-16 8:35
 My vote of 5 liam.lee25-Apr-13 16:37 liam.lee 25-Apr-13 16:37
 Re: My vote of 5 Santhosh G_26-Apr-13 4:15 Santhosh G_ 26-Apr-13 4:15
 OpenCL FredWah9-Nov-12 7:32 FredWah 9-Nov-12 7:32
 My vote of 5 nefu_boy23-May-12 15:00 nefu_boy 23-May-12 15:00
 Re: My vote of 5 ImABeginner24-Oct-12 17:49 ImABeginner 24-Oct-12 17:49
 How does Pixel Shader choose the Edge Points? Member 899307221-May-12 19:58 Member 8993072 21-May-12 19:58
 Re: How does Pixel Shader choose the Edge Points? Santhosh_G23-May-12 7:33 Santhosh_G 23-May-12 7:33
 Re: How does Pixel Shader choose the Edge Points? nefu_boy23-May-12 15:31 nefu_boy 23-May-12 15:31
 Your Machine not supports Opengls GL_ARB_fragment_shader Member 775469514-Mar-11 20:56 Member 7754695 14-Mar-11 20:56
 Re: Your Machine not supports Opengls GL_ARB_fragment_shader santhosh4gCode22-Mar-11 7:13 santhosh4gCode 22-Mar-11 7:13
 My vote of 4 Mick Leong3-Mar-11 18:58 Mick Leong 3-Mar-11 18:58
 Digital output Mick Leong1-Aug-10 21:13 Mick Leong 1-Aug-10 21:13
 Re: Digital output santhosh4gCode14-Aug-10 22:59 santhosh4gCode 14-Aug-10 22:59
 Re: Digital output Attila Kúr19-Aug-10 9:38 Attila Kúr 19-Aug-10 9:38
 Mick, one way to detect vector lines / circles / arcs in an edge-detected image is to use Hough transform. However, you also need to pre-process that edge-detected image by denoising it first, in order to achieve better results.
 Re: Digital output Mick Leong22-Aug-10 20:23 Mick Leong 22-Aug-10 20:23
 Re: Digital output Attila Kúr23-Aug-10 12:05 Attila Kúr 23-Aug-10 12:05
 Re: Digital output Mick Leong24-Aug-10 23:53 Mick Leong 24-Aug-10 23:53
 My vote of 5 Mick Leong1-Aug-10 21:08 Mick Leong 1-Aug-10 21:08
 You like chinese ? Aric Green28-Jul-10 15:55 Aric Green 28-Jul-10 15:55
 Re: You like chinese ? santhosh4gCode28-Jul-10 23:32 santhosh4gCode 28-Jul-10 23:32
 Re: You like chinese ? Member 899307221-May-12 19:05 Member 8993072 21-May-12 19:05
 File link is incorrect Avis p28-Jul-10 0:59 Avis p 28-Jul-10 0:59
 Re: File link is incorrect santhosh4gCode28-Jul-10 2:31 santhosh4gCode 28-Jul-10 2:31
 Last Visit: 31-Dec-99 18:00     Last Update: 20-Oct-17 11:46 Refresh 12 Next »