Edge Detection using Dynamic Programming
Abstract
Edge Detection is one of the essential methods in early vision of the Human Visual System(HVS) to extract important information from the projected image of the environment. This is due to the fact that, edges and boundaries characterize the object and are therefore useful in identifying objects in scenes. There are some common types of boundary detection schemes:
1. Contour following
2. Edge linking
3. Dynamic programming
4. Hough transform
5. Neural Networks
6. Fuzzy Logic
....
However, in this report, we are required to compare edge detection techniques using a dynamic programming and a conventional smoothing followed by gradient method technique. The second method here can be achieved by simply filtering the image with a low pass filter and then applying a gradient filter on it.
Introduction
Dynamic Programming(DP) is used to find the global optimum of multistage decision process when not all the variables of the model defined for the underlying process are interrelated simultaneously. The key concept of DP is based on the fact that the optimum path between two given points is also optimum for any two points lying on the path. Consequently, Dynamic programming is optimum in execution time as compared to other boundary detection algorithm but does not enhance the image.
Simulation Example
The image features used in extracting boundaries can be classified as:
1. Gradient (weighted by w1)
2. Intensity (weighted by w2)
3. Continuity (weighted by w3)
4. Texture
In our report, the last feature,i.e. texture, is not considered. The three features are weighted and summed together to define a cost function upon which out algorithm is based. The weighting factors is adjusted until obtaining the minimum square error e, and using these optimum training factors w1, w2, and w3, to weight the gradient, intensity, and continuity, until we find the satisfied e, r and CV value, which were set by our purposes.
In our project, we were required to detect the boundary line and make the standard deviation of the position error between the detected line and the ideal line smaller than 0.5 pixel. Actually, through carefully select, we found the best training factors to make the error equal to zero as shown in the figure below.
