Edge Detection Using Kirsch Algorithms

Image processing is the study of representation and manipulation of pictorial information. In Image Processing, an edge is the boundary between an object and its background. Therefore, if the edges of image’s objects can be identified with precision, all the objects can be located and their properties such as area, perimeter and shape can be calculated. Edge detection is an essential tool for image processing. Edge detection is the process of locating the edge pixels. Then an edge enhancement will increase the contrast between the edges and the background in such a way that edges become more visible.

In the edge function, the Sobel method uses the derivative approximation to find edges. Therefore, it returns edges at those points where the gradient of the considered image is maximum. The Kirsch Edge module detects edges using eight compass filters. All eight filters are applied to the image with the maximum being retained for the final image. The eight filters are a rotation of a basic compass convolution filter (RoboRealm, 2006).

The proposal is organized as follows. First, describe the research problems statement, Research Objective, Hypothesis, Delimitations, Assumptions, Terms, significant of the ‘Research Problem’, ‘Literature Review’ session. Lastly the ‘Research Methodology’ and Conclusion sections respectively.

Research Problem

Problem Statements

As a human being, we could not notice the petite lines of an image. We could only recognize an enormous range of objects from just line images such cartoons. Besides, in Malaysian, it is acknowledge that there is no system to identify the edges of the local cars. They prefer to choose the human faces, geometric shapes or the environment image as their image research.

So, by using edge detection techniques, the result of detected edges image could show us the lines or edges from the obvious lines to the tiniest lines of that certain image (Brendan McCane, 2001).

For example, Prewit Edge Detector for detection of edges in digital images corrupted with different kinds of noise (Raman Maini, 2005). In the edge function, the Sobel method uses the derivative approximation to find edges where it returns edges at those points where the gradient of the considered image is maximum. The Kirsch Edge module detects edges using eight compass filters. All eight filters are applied to the image with the maximum being retained for the final image. The eight filters are a rotation of a basic compass convolution filter (RoboRealm, 2006).

Research Objectives

The objectives of this study are:

1) To identify edge detection of image processing system on Malaysian cars.

2) To be able to draw a bitmap result where edges are either in gray scaled or colored

for enhancement of edges in an image.

3) To compare the edge detection methods to one another by using the Prewit Edge

Detector, Sobel Edge Detector and Kirsch Edge Detector.

2.3 Hypothesis

Believe that by implementing different edge detecting algorithms, verified images will be more exact and precise in terms of image accuracy and clarity.

2.4 Delimitations

The edge detections will only be analyzing between Sobel, Prewit and Kirsch algoritms.

The image processing edge detection does not contain any hierarchical structure but only groups of local cars images.

2.5 Assumptions

The participants are familiar the basic knowledge of edge detection to ensure they realize what is happening during the experimental session.

They are not trained to identify the difference between the 3 algorithms given to them

All participants are at least two year experience in image processing activities to make sure that they could determine what the purpose of this research is.

Terms

Noise = amount of distortion of a pixel value against the frequency of images

Thresholding = separates the pixels in ways that tend to preserve the boundaries

Filter = Process by which we can enhance or otherwise modify images.

2.6 Research Significance

The image of Malaysian cars will be captured as the input. The each of the image’s edges will be detected either by using the Prewit Edge Detector, Sobel Edge Detector or Kirsch Edge Detector. If the user chooses to see the output of Prewit Edge Detector, the result of detected edges will be appear on the panel and same goes to if they choose the Sobel Edge Detector or the Kirsch Edge Detector. They could choose all of the three edge detectors for more precise observation. The result also will be compare with the human views to get the similarity of edge detecting against it.

Literature Review

Introduction to Image Processing Edge Detection

In Image Processing, an edge is the boundary between an object and its background. They represent the frontier for single objects. Therefore, if the edges of image’s objects can be identified with precision, all the objects can be located and their properties such as area, perimeter and shape can be calculated. Edge detection is an essential tool for image processing. Edge detection is the process of locating the edge pixels. Then an edge enhancement will increase the contrast between the edges and the background in such a way that edges become more visible. In addition, edge tracing is the process of following the edges, usually collecting the edge pixels into a list.

In the edge function, the Sobel method uses the derivative approximation to find edges. Therefore, it returns edges at those points where the gradient of the considered image is maximum. The horizontal and vertical gradient matrices whose dimensions are 3-3 for the Sobel method has been generally used in the edge detection operations. In this work, a function is developed to find edges using the matrices whose dimensions are 5-5 in matlab (Shigeru A, 2000).

Since edge detection is in the forefront of image processing for object detection, it is crucial to have a good understanding of edge detection algorithms. Prewit Edge Detector for detection of edges in digital images corrupted with different kinds of noise. Different kinds of noise are studied in order to evaluate the performance of the Prewitt Edge Detector (Raman Maini, 2005). The Kirsch Edge module detects edges using eight compass filters. All eight filters are applied to the image with the maximum being retained for the final image. The eight filters are a rotation of a basic compass convolution filter (RoboRealm, 2006).

3.2 Comparisons of Edge Detection Techniques

a) Sobel

Sobel edge detector using convolutions with row and column edge gradient masks (Percy S, 2001).

Applies a 3-3 convolution filter row-wise in order to determine the gradient of the surrounding pixels.

Pixel is a member of an edge if the intensity of it is greater than that of the members of its surrounding pixels.

The Sobel edge detection filter uses the two 3-3 templates to calculate the gradient value.

1

2

1

-1

0

1

-1

-2

1

1

1

1

0

0

1

1

-1

-1

Figure 1: Sobel Algorithm X Y

Original image

Sobel Edge Detection

Original image

Figure 1.1: Sobel Edge Detection Output

b) Prewit

Prewit Edge Detector for detection of edges in digital images corrupted with different kinds of noise. Different kinds of noise are studied in order to evaluate the performance of the Prewit Edge Detector (Raman Maini, 2005).

This is similar to the Sobel detector

Operates under the same principle except that it uses a different (simpler) convolution kernel.

-1

0

1

-1

0

1

-1

0

1The Prewitt edge detection filter uses the two 3-3 templates to calculate the gradient value.

-1

-1

-1

0

0

0

1

1

1

Figure 2: Prewit Algorithm X Y

Original image

Prewitt Edge Detection

Original image

Figure 2.1: Prewit Edge Detection Output

c) Kirsch

The Kirsch Edge module detects edges using eight compass filters. All eight filters are applied to the image with the maximum being retained for the final image. The eight filters are a rotation of a basic compass convolution filter (Mike Heath, 2001).The filters are of the form:

5

5

5

-3

-3

-3

-3

-3

-3

5

-3

-3

5

-3

-3

5

-3

-3

Figure 3: Kirsch Algorithm X Y

Original image

Kirsch Edge Detection

Original image

Figure 3.1: Kirsch Edge Detection Output

3.3 Thresholding

The idea of thresholding is to apply a boundary-finding method (such as edge detection), sample of the histogram that are only near where the boundary probability is high.

The benefit of thresholding is to separates the pixels in ways that tend to preserve the boundaries. Besides that, other scattered distributions within the object or the background are irrelevant. But, the problems if the characteristics change along the boundary, it still no guarantee you won’t have extraneous pixels or holes (IgorPro, 2006).

The advantages of thresholding can be declared that it is simple to implement, fast especially if repeating on similar images and it is good for some kinds of images such as documents, controlled set-ups.

The disadvantages of thresholding can be assume that it is usually not very good segmentation, there are no guarantees of object coherency such as they may have holes, extraneous pixels, and so on and there are connected component labeling can then be used to label separate foreground regions.

METHODOLOGY

This chapter provides methodology that used to develop text search engine prototype. Methodology is a study of methods, a set of procedures and selecting data. All of workflow involved in the implementation of this project is explained from the beginning to the end.

Project Formulation Framework

Figure 4: Overview of Project Formulation Framework

Project Framework Summary

Phase

Objectives

Deliverables

Planning

1) To identify and understand potential problems.

2) Ensure goals, scope, budget, schedule, methods and tools are in place.

1) Define the problem statement, objectives, scope and contribution of study.

2) Collecting images of Malaysian cars.

Analysis

1) Analyzing the system requirement.

2) Analyze the edge detection algorithms used for the system (Sobel, Prewit and Kirsch).

1) Prototype requirement and requirement model.

2) Identify the comparison of the algorithms chosen.

Design

1) Design the prototype interface and the coding (classes and object).

2) Design function and algorithms.

1) System and Detailed design.

2)GUI interface

Implementation

1) Translate design into code

New application

Testing

1)Pre-test and pro-test the application

Test the application

Data Collection

The data collection is the most critical process in this project. As mentioned earlier, this study will only focus on Malaysian cars. Before developed the application tool, all information must be collected first. This stages involved data collection about sample of Malaysian car images and project requirements which are hardware and software requirements.

The sample images of the car will be captured by using digital camera. The main hardware system in order to capture an image is the camera to grab the image of the cars. The images are in a bitmapped or digital image format. Besides that, this study also gathered information from internet. It was the greatest finding for this project. From internet, more information can be explored in detail such as about bitmapped image model, journals and articles about previous researches which related to this project the Malaysian cars itself and many more.

4.4 Prototype Development

Throughout the development of the application, there were involving some steps. After all the information gathered, the development processes take place. Firstly, as an input the image of the Malaysian cars must be captured. A digital camera was used to acquire the images. There were 10 images of different category of Malaysian cars as samples for this project. In capturing the images, hardware system also involved. The camera will use to grab the image and the computer system will do the image processing and data analysis for the images. The images were scanned to convert them into digital form.

Experiment and Procedure

In the experimental task, the participants will be given the Malaysian car images. They will run the application by choosing different car images and test all the images to the different edge detection algorithm provided to them. The output which is the result of comparison between those 3 algorithms (Sobel, Prewitt and Kirsch) will be recorded. The user, based on his/her experience will determine the sharp, sharper and sharpest result of edge detected images from system. Here, they might recognize which edge detector is more accurate in image clarity capturing. The summary of the experiment is as follows;

Pretest

Participants choose Malaysian cars images and tryout them using the algorithms provided.

Posttest /Treatment

Participants evaluate the result which edge detection algorithm is the sharp, sharper or sharpest.

Observation

My experiment used one-group pretest and posttest design.7. The group participated in both pre-experiment evaluation and post-experiment evaluation sequentially. The design is represented as follows:

Group

Time ƒ 

Group 1

Observation 1

(using Sobel Algorithm with and without thresholding)

Observation 2

(using Prewit Algorithm with and without thresholding)

Observation 3

(using Kirsch Algoritm with and without thresholding)

Figure 5: Experimental design 7

Experimental Design Number 7: pretest and posttest design.

Data Analyses

After collecting all the data from their query results from the participants, we use the following standard criteria for evaluating retrieval for effectiveness of search are used . The keyword-based search and the ontology-based search have been evaluated using the following formula:

Comparison of Edge Detectors Image Sharpness Based on Thresholding Value

Bil

Type of Malaysian Cars

Sobel

Prewit

Kirsch

1

Perodua Kelisa

Sharpest

Sharper

Sharp

2

Perodua Kenari

Sharpest

Sharper

Sharp

3

Perodua Kembara

Sharpest

Sharper

Sharp

4

Proton Wira

Sharpest

Sharper

Sharp

5

Proton Waja

Sharpest

Sharp

Sharper

6

Proton Satria Neo

Sharpest

Sharper

Sharp

7

Perodua Kancil

Sharpest

Sharper

Sharp

8

Proton Saga Aeroback

Sharpest

Sharp

Sharper

9

Proton Satria

Sharper

Sharpest

Sharp

10

Perodua Myvi

Sharpest

Sharper

Sharp

Table 1: Approximate image sharpness of the algorithms based on 10 of Malaysian car images

Sharp Result (Percentage)

Edge Detectors

Sobel

Prewit

Kirsch

0/10*100 = 0%

2/10*100 = 20%

8/10*100 = 80%

Table 2: Percentage for the Malaysian Cars Sharpness for sharp category

Sharper Result (Percentage)

Edge Detectors

Sobel

Prewit

Kirsch

1/10*100 = 10%

7/10*100 = 70%

2/10*100 = 20%

Table 3: Percentage for the Malaysian Cars Sharpness for sharper category

Sharpest Result (Percentage)

Edge Detectors

Sobel

Prewit

Kirsch

9/10*100 = 90%

1/10*100 = 10%

0/10*100 =0%

Table 4: Percentage for the Malaysian Cars Sharpness for sharpest category

Figure 6: Histogram for the comparison result for precision

According to the Figure 6, based on Table 2, Table 3 and Table 4, the sharp, sharper and sharpest result is based from the thresholding value of 60.

In making this research, some important lesson or experience has been learned. After the project successfully developed and tested, the result from the testing is analyzed. The results are between human viewing and prototype viewing. By analysis and compare the results the accuracy of the project is determined. It also use as a measurement to the third objective of the project. If the project result is accurate, the third objective is successfully achieved.

5.3 Recommendation

There are also some future expansions that can be done in order to improve this prototype.

This prototype developed for computer platform only.

This prototype can be developed in the PDA or handheld hand phone.

Recommendation for future is the samples of Malaysian cars should be various because from that the result can be more accurate.

5.4 Conclusion

There are many ways to perform edge detection. Various edge detection algorithms have been developed in the process of finding the perfect edge detector. Some of the edge detection operators that are discussed in this thesis are Prewitt, Sobel, and Kirsch operators. In this case, there are three criteria for optimal edge detections. First good detection where the optimal detector must minimize the probability of false positives, as well as that of false negatives. Second, good localization where the edges detected must be as close as possible to the true edges and finally, single response constraint where the detector must return one point only for each true edge point; that is, minimize the number of local maxima around the true edge (Trucco, 2006).