Edge and Corner detection

Edge detection and Corner detection are two of the most basic feature detection algorithms, and are very useful ones too. Having information about the edges in an image can be of great help in applications, where you want to find boundaries of different objects in an image, or you need to find corners in an image when you want to analyze how an object rotates or moves in a given sequence of images (or videos). In this section, we will take a look at the techniques and implementations of various Edge and Corner detection algorithms, such as Difference of Gaussian, Canny Edge detector, Sobel Operator, and Harris Corners.

The Difference of Gaussian technique

Let's start with the easiest and the most rudimentary technique. Before we understand how Difference of Gaussian (DoG) works, let's take a look at what exactly edges are. To put it simply, edges are points in an image where the pixel intensity changes appreciably. We will exploit this property of edges and by applying Gaussian blur on the image, we will compute the edge points (Edges).

Here is a three-step explanation of the algorithm:

1. Convert the given image to a grayscale image.
2. On the grayscale image, perform Gaussian blur using two different blurring radiuses (you should have two Gaussian blurred images after this step).
3. Subtract (arithmetic subtraction) the two images generated in the previous step to get the resultant image with only edge points (Edges) in it.

Why does this technique work? How can subtracting two Gaussian blurred images give us edge points? A Gaussian filter is used to smooth out an image and the extent of smoothening depends on the blurring radius. Consider an image of a chess board. When you apply a Gaussian filter to the chess board image, you will observe that there is almost no change near the center of the white and black squares, whereas the common side of the black and white squares (which is an edge point) gets smudged, implying loss of edge information. Gaussian blur makes the edge less prominent.

According to our technique, we have two Gaussian blurred images with different blurring radius. When you subtract these two images, you will lose all the points where no smoothening or smudging happened, that is, the center of the black and white squares in the case of a chess board image. However, pixel values near the edges would have changed because smudging pixel values and subtracting such points will give us a non-zero value, indicating an edge point. Hence, you get edge points after subtracting two Gaussian blurred images.

Since we are only performing Gaussian blurs on images, it is one of the fastest ways of calculating edges. Having said that, it is also true that this technique does not return very promising results. This technique might work very well for some images and can completely fail in some scenarios. However, it doesn't hurt to know one extra algorithm!

Let's modify our Features App that we created in the last section and apply DoG to it. In the applications menu, we add a new menu option, Difference of Gaussian, to the menu resource XML file using these lines:

<item android:id="@+id/DoG" android:title="@string/DoG"
        android:orderInCategory="100" android:showAsAction="never" />

Make a new function public void DifferenceOfGaussian(), which will compute edges in any given image, as follows:

public void DifferenceOfGaussian()
    {
        Mat grayMat = new Mat();
        Mat blur1 = new Mat();
        Mat blur2 = new Mat();

        //Converting the image to grayscale
        Imgproc.cvtColor(originalMat,grayMat,Imgproc.COLOR_BGR2GRAY);

        //Bluring the images using two different blurring radius
        Imgproc.GaussianBlur(grayMat,blur1,new Size(15,15),5);
        Imgproc.GaussianBlur(grayMat,blur2,new Size(21,21),5);

        //Subtracting the two blurred images
        Mat DoG = new Mat();
        Core.absdiff(blur1, blur2,DoG);

        //Inverse Binary Thresholding
        Core.multiply(DoG,new Scalar(100), DoG);
        Imgproc.threshold(DoG,DoG,50,255,Imgproc.THRESH_BINARY_INV);

        //Converting Mat back to Bitmap
        Utils.matToBitmap(DoG, currentBitmap);
        loadImageToImageView();
    }

In the preceding piece of code, we first convert the image to a grayscale image. Then, we apply the Gaussian filter to the image twice, with two different blurring radiuses, using the Imgproc.GaussianBlur() function. The first and second parameters in this function are input and output images, respectively. The third parameter specifies the size of the kernel to be used while applying the filter, and the last parameter specifies the value of sigma used in the Gaussian function. Then we determine the absolute difference of the images using Core.absdiff(). Once this is done, we post-process our image to make it comprehensible by applying the Inverse Binary Threshold operation to set the edge point values to white (255). Finally, we convert the bitmap to Mat and display it on the screen using loadImageToView().

Here is the resulting image after applying DoG on Lenna:

Difference of Gaussian is not often used because it has been superseded by other more sophisticated techniques that we are going to discuss later in this chapter.

The Canny Edge detector

Canny Edge detection is a widely used algorithm in computer vision and is often considered as an optimal technique for edge detection. The algorithm uses more sophisticated techniques than Difference of Gaussian, such as intensity gradient in multiple directions, and thresholding with hysteresis.

The algorithm is broadly pided into four stages:

1. Smoothing the image: This is the first step of the algorithm, where we reduce the amount of noise present in the image by performing a Gaussian blur with an appropriate blurring radius.
2. Calculating the gradient of the image: Here we calculate the intensity gradient of the image and classify the gradients as vertical, horizontal, or diagonal. The output of this step is used to calculate actual edges in the next stage.
3. Non-maximal supression: Using the direction of gradient calculated in the previous step, we check whether or not a pixel is the local maxima in the positive and negative direction of the gradient if not then, we suppress the pixel (which means that a pixel is not a part of any edge). This is an edge thinning technique. Select edge points with the sharpest change.
4. Edge selection through hysteresis thresholding: This is the final step of the algorithm. Here we check whether an edge is strong enough to be included in the final output, essentially removing all the less prominent edges.

Tip

Refer to http://en.wikipedia.org/wiki/Canny_edge_detector for a more detailed explanation.

The following is an implementation of the algorithm using OpenCV for Android.

For Difference of Gaussian, first add the Canny Edges option to the application menu by adding a new item in the menu resource XML file, as follows:

<item android:id="@+id/CannyEdges" android:title="@string/CannyEdges"
        android:orderInCategory="100" android:showAsAction="never" />

Create a new function, public void Canny(), and add the following lines of code to it:

//Canny Edge Detection
    public void Canny()
    {
        Mat grayMat = new Mat();
        Mat cannyEdges = new Mat();
        //Converting the image to grayscale
            Imgproc.cvtColor(originalMat,grayMat,Imgproc.COLOR_BGR2GRAY);

        Imgproc.Canny(grayMat, cannyEdges,10, 100);

        //Converting Mat back to Bitmap
        Utils.matToBitmap(cannyEdges, currentBitmap);
        loadImageToImageView();
    }

In the preceding code, we first convert our image to a grayscale image, and then simply call the Imgproc.Canny() function implemented in the OpenCV API for Android. The important thing to notice here are the last two parameters in Imgproc.Canny(). They are for low and high thresholds respectively. In Canny Edge detection algorithm, we classify each point in the image into one of three classes, suppressed points, weak edge points, and strong edge points. All the points that have the intensity gradient value less than the low threshold values are classified as suppressed points, points with the intensity gradient value between low and high threshold values are classified as weak edge points, and points with the intensity gradient value above the high threshold values are classified as strong edge points.

According to the algorithm, we ignore all the suppressed points. They will not be a part of any edge in the image. Strong edge points definitely form a part of an edge. For weak edge points, we check whether they are connected to any strong edge points in the image by checking the eight pixels around that weak point. If there are any strong edge points in those eight pixels, we count that weak point as a part of the edge. That's Canny Edge detection!

The Sobel operator

Another technique for computing edges in an image is using the Sobel operator (or Sobel filter). As in Canny Edge detection, we calculate the intensity gradient of the pixel, but in a different way. Here we calculate the approximate intensity gradient by convoluting the image with two 3x3 kernels for horizontal and vertical directions each:

Convolution matrices used in Sobel filter

Using the horizontal and vertical gradient values, we calculate the absolute gradient at each pixel using this formula:

For an approximate gradient, the following formula is usually used:

The steps involved in computing edges using a Sobel operator are as follows:

1. Convert the image to a grayscale image.
2. Calculate the absolute value of the intensity gradient in the horizontal direction.
3. Calculate the absolute value of the intensity gradient in the vertical direction.
4. Compute the resultant gradient using the preceding formula. The resultant gradient values are essentially the edges.

Let's now add a Sobel filter to our Features App. Start by adding a Sobel filter menu option in the menu's XML file:

<item android:id="@+id/SobelFilter" android:title="@string/SobelFilter"
        android:orderInCategory="100" android:showAsAction="never" />

The following is a Sobel filter using OpenCV for Android:

//Sobel Operator
    void Sobel()
    {
        Mat grayMat = new Mat();
        Mat sobel = new Mat(); //Mat to store the result

        //Mat to store gradient and absolute gradient respectively
        Mat grad_x = new Mat();
        Mat abs_grad_x = new Mat();

        Mat grad_y = new Mat();
        Mat abs_grad_y = new Mat();

        //Converting the image to grayscale
        Imgproc.cvtColor(originalMat,grayMat,Imgproc.COLOR_BGR2GRAY);

        //Calculating gradient in horizontal direction
        Imgproc.Sobel(grayMat, grad_x,CvType.CV_16S, 1,0,3,1,0);

        //Calculating gradient in vertical direction
        Imgproc.Sobel(grayMat, grad_y,CvType.CV_16S, 0,1,3,1,0);

        //Calculating absolute value of gradients in both the direction
        Core.convertScaleAbs(grad_x, abs_grad_x);
        Core.convertScaleAbs(grad_y, abs_grad_y);

        //Calculating the resultant gradient
        Core.addWeighted(abs_grad_x, 0.5, abs_grad_y, 0.5, 1, sobel);

        //Converting Mat back to Bitmap
        Utils.matToBitmap(sobel, currentBitmap);
        loadImageToImageView();
    }

In this code, we first convert the image to a grayscale image. After this, using the grayscale image, we calculate the intensity gradient in the horizontal and vertical directions using the Imgproc.Sobel() function, and store the output in grad_x and grad_y. As per the formula mentioned in the algorithm, we calculate the absolute value of the gradients and add them together to get the resultant gradient value (basically the edges). The following code snippet performs the described step:

//Calculating absolute value of gradients in both the direction
        Core.convertScaleAbs(grad_x, abs_grad_x);
        Core.convertScaleAbs(grad_y, abs_grad_y);

        //Calculating the resultant gradient
        Core.addWeighted(abs_grad_x, 0.5, abs_grad_y, 0.5, 1, sobel);

Finally, we convert the Mat into a bitmap and display it on the screen.

Tip

You may also be interested to take a look at the Prewitt operator (http://en.wikipedia.org/wiki/Prewitt_operator). It is similar to a Sobel operator, but uses a different matrix for convolution.

Harris Corner detection

In the literal sense of the term, corners are points of intersection of two edges or a point which has multiple prominent edge directions in its local neighborhood. Corners are often considered as points of interest in an image and are used in many applications, ranging from image correlation, video stabilization, 3D modelling, and the likes. Harris Corner detection is one of the most used techniques in corner detection; and in this section, we will take a look at how to implement it on an Android platform.

Harris corner detector uses a sliding window over the image to calculate the variation in intensity. Since corners will have large variations in the intensity values around them, we are looking for positions in the image where the sliding windows show large variations in intensity. We try to maximize the following term:

Here, I is the image, u is the shift in the sliding window in the horizontal direction, and v is the shift in the vertical direction.

The following is an implementation of Harris Corner using OpenCV:

void HarrisCorner() {
        Mat grayMat = new Mat();
        Mat corners = new Mat();

        //Converting the image to grayscale
        Imgproc.cvtColor(originalMat, grayMat, Imgproc.COLOR_BGR2GRAY);

        Mat tempDst = new Mat();
        //finding corners        Imgproc.cornerHarris(grayMat, tempDst, 2, 3, 0.04);

        //Normalizing harris corner's output
        Mat tempDstNorm = new Mat();
        Core.normalize(tempDst, tempDstNorm, 0, 255, Core.NORM_MINMAX);
        Core.convertScaleAbs(tempDstNorm, corners);

        //Drawing corners on a new image
        Random r = new Random();
        for (int i = 0; i < tempDstNorm.cols(); i++) {
            for (int j = 0; j < tempDstNorm.rows(); j++) {
                double[] value = tempDstNorm.get(j, i);
                if (value[0] > 150)
                    Core.circle(corners, new Point(i, j), 5, new Scalar(r.nextInt(255)), 2);
            }
        }

        //Converting Mat back to Bitmap
        Utils.matToBitmap(corners, currentBitmap);
        loadImageToImageView();
    }

In the preceding code, we start off by converting the image to a grayscale image and then use it as an input to the Imgproc.cornerHarris() function. The other inputs to the function are the block size, kernel size, and a parameter, k, that is used to solve one of the equations in the algorithm (for details on mathematics, refer to OpenCV's documentation on Harris Corner at http://docs.opencv.org/doc/tutorials/features2d/trackingmotion/harris_detector/harris_detector.html). The output of Harris Corner is a 16-bit scalar image, which is normalized to get the pixel values in the range 0 to 255. After this, we run a for loop and draw all the circles on the image with the centers being points whose intensity value is greater than a certain user set threshold.