Processing the image

There are countless existing image processing algorithms like image segmentation, face detection etc. for different application purposes. However, basically there are some very fundamental operations performed on the images in order to obtain those algorithms.

One of them is Sobel operator which has a significant importance in edge detection algorithms. Sobel operator works on a monochrome image. It finds the gradient values around each pixel, and generates an output image.

Explanation of the Sobel Operator concept, how it is applied in this design, and how to compute edges inside the image are discussed in this part.

5.5.1. Transformation to monochrome

The processor reads the image from the FIFO in RGB format. In order to apply edge detection algorithms to the image, the image needs to be transformed to monochrome format. Monochrome image is often represented with Y since it is the first component of YCbCr colour space. The transformation to the monochrome from RGB colour space is formally defined as:

Y =0.2125×R+0.7154×G+0.0721×B (28)

Equation 28 shows that the green component has the most contribution to the monochrome image because the human eye is much more sensitive to green than the other colours.

Since the aim of this work is to test image processing feasibility within the context of limited image processing, instead of following the formal transformation equation, software uses an approximation which saves computation power.

The approximation to the formal transformation applied in the software follows that:

Y = 1

4×R+ 5

8×G+ 1

8×B (29)

It should be noted that the coefficients of the colour components are very easy to obtain by using simple bitwise right shift operation and addition. Of course this method introduces some error but on the other hand it is a very easy and fast way compared to having multiplication with fractional numbers and summing them for all the pixels of the image.

5.5.2. Gradient calculation

Once the monochrome image is formed, Sobel operator can be applied on it. Definition, usage and explanation of Sobel operator has been described in section 2.4 before. Again, to reduce computational power, some modifications are applied to this original method and explained.

The Sobel operator has only +2, +1, 0, -1, and -2 coefficients in the matrix. Among those values, only +2 and -2 needs multiplication operation but since they can be obtained with bitwise left shift operation, just summation after left shifting solves the computation in the kernel.

Convolution in two dimension for image processing has been described in section 2.3.

Same two dimensional convolution operations are performed for computation of both the horizontal and the vertical gradients. Once the Gx and the Gy orthogonal gradients are obtained as a vector, the magnitude of the vectorial sum must be calculated to find total gradient value.

At this point a problem arises with the computation of big gradient values. The values of the pixels are represented by 256 levels ranging from 0x00 up to 0xFF values in hexadecimal notation. In order to compute the magnitude, the square of those two orthogonal gradient values must be calculated and added together, then the square root operator must be applied.

Assuming that both horizontal and vertical convolution kernels computed the values of 0xFF, taking the second power of 255 and adding same two numbers results in 130050.

This number can't be represented by char or short type of variable, thus a 32–bit integer must be assigned to store this value. Square root computation is not a very easy task for computers compared to addition, multiplication etc. Here the operation needs a lot of computation because square root operation must be performed for every pixel of the image. For that reason, iterative square root calculation technique called Babylonian Square Root is applied. This method has been explained in section 2.5 before.

In order to justify this approximation, giving an example from the image processing software would be appropriate. Let x and y gradients be 0xF4 and 0xA5 respectively.

Sum of second powers of these two numbers is 86761 and the square root of it is 295.552 precisely in decimal. Here it should be noted that another problem in Sobel operator application is that the gradient magnitude can exceed the value what an unsigned char variable can represent. That's why the calculated magnitude is later scaled down to three quarter. Iterations given below show how fast and accurate Babylonian Square Root technique is. Software always takes 180 as initial estimation because it is half of the maximum gradient magnitude.

x₅= 1

2

(

)

⁽

⁾

Here very accurate result is achieved after the 5th iteration but 4th iteration is also close to the result with an error of:

∣317−295∣

295 =7.5% (36)

For the algorithm which is applied in this software, this error rate is acceptable because the error rate is proportional to how big the number is, thus it doesn't seriously affect the ratio between the gradients of different points.

Now the gradient magnitude is calculated for a given pixel, it is placed in the corresponding locations of all pixels of the output image. Gradient values are coded on the output image in grayscale format.

5.5.3. Edge detection

Edge detection is done by filtering the resultant gradient image that is obtained after the application of Sobel algorithm.

Firstly a threshold value of the filter is chosen. The gradient values which are below this threshold will be coded as black, and the values that are greater than the threshold can either be coded as pure white or the gradient value itself. Gradient image is in fact the edge detected image with a zero threshold. Setting the threshold value to maximum level will of course result in a pure black image.

Applying the Sobel operation over the image twice results in an approximation of Laplace transform of the image, but in this work it is not performed.