# An Improved NMS-Based Adaptive Edge Detection Method and Its FPGA Implementation

Authors: Enzeng Dong; Yao  Zhao; Xiao Yu; Junchao Zhu; Chao Chen
Journal: Journal of Sensors
 (2016)

---

## Abstract

For improving the processing speed and accuracy of edge detection, an adaptive edge detection method based on improved NMS (nonmaximum suppression) was proposed in this paper. In the method, the gradient image was computed by four directional Sobel operators. Then, the gradient image was processed by using NMS method. By defining a power map function, the elements values of gradient image histogram were mapped into a wider value range. By calculating the maximal between-class variance according to the mapped histogram, the corresponding threshold was obtained as adaptive threshold value in edge detection. Finally, to be convenient for engineering application, the proposed method was realized in FPGA (Field Programmable Gate Array). The experiment results demonstrated that the proposed method was effective in edge detection and suitable for real-time application.


---

## Body

## 1. Introduction

Due to the broad application fields, such as in industry, spaceflight, medicine, and military [1–3], the study on edge detection became a hot issue in image processing. At present, the researches on edge detection are mainly focused on mathematical morphology methods [4, 5] and gradient methods [6, 7]. The morphology based edge detection methods can effectively detect edges; however, complex iterative operations in these methods are the main obstacle for real-time applications.On the other hand, the gradient based edge detection methods are more suitable for engineering implementation due to relatively simple calculation. Many improved edge detection algorithms based on gradient calculation such as Roberts operator [8], Sobel operator [9], Canny operator [10], and Laplacian operator [11] were proposed successively. For example, based on the Canny operator, Yu et al. [12] designed an edge directional interpolation method to process the MRI (magnetic resonance image) of fetal spinal column. Wang et al. [13] improved the Sobel edge detection algorithm by using NMS algorithm. Wiehle and Lehner [14] proposed an edge detection algorithm for high definition satellite images based on Sobel operator.Owing to the advantages in high calculation speed and parallel processing, the FPGA became a useful hardware realization tool for real-time images processing [15–18]. Li et al. [19] designed a data block accelerator to optimize the Sobel operator in FPGA, and this method could be applied in real-time edge detection.In previous works, the accuracy and speed of edge detection methods were improved from different aspects. Nevertheless, edge detection threshold has not been given much concern. In this paper, an adaptive edge detection algorithm based on the NMS was proposed. In this method, the gradient image was processed by utilizing NMS method. Then, the elements values of gradient image histogram were mapped into a wider value range by a certain power map, which can help calculate the threshold accurately.According to the maximal between-class variance, the threshold was calculated and inverse mapped to original gradient map. The inverse mapped threshold was considered as adaptive threshold value in edge detection. Finally, for application in engineering fields, the proposed method was realized in FPGA. The experiment results showed that the proposed method has higher processing speed and detection accuracy.


## 2. The Adaptive Edge Detection Algorithm

The flow chart of edge detection algorithm was shown in Figure1. Gradient image was computed from original image data by Sobel operator. Then, NMS method was employed to process gradient image. Because gradient values in processed gradient image clustered in low value range, histogram mapping was performed to obtain a more spread distribution. After histogram mapping, the threshold T~ in mapped histogram was calculated by using OTSU method. By inverse mapping, adaptive threshold T was achieved. Double thresholds computed from threshold T were applied to determine potential edges.Figure 1
Flow chart of edge detection algorithm.


### 2.1. Gradient Calculation and NMS Processing

The original image was divided into 5× 5 subregion. The 3 × 3 Sobel operator of vertical, horizontal, and two diagonals (0°, 45°, 90°, and 135°) was employed to calculate the gradient, as shown in Tables 1(a), 1(b), 1(c), and 1(d).Table 1
3 × 3 Sobel operator.
(a)
0° template
−1
0
1
−2
0
2
−1
0
1
(b)
45° template
0
1
2
−1
0
1
−2
−1
0
(c)
90° template
−1
−2
−1
0
0
0
1
2
1
(d)
135° template
−2
−1
0
−1
0
1
0
1
2
(e)
The original grey value
Z
1
Z
2
Z
3
Z
4
Z
5
Z
6
Z
7
Z
8
Z
9The gradient of a 3× 3 image region (Table 1(e)) can be computed by multiplying the element value with the corresponding value in four directional Sobel operators. Then, four gradient values with direction were calculated as in the following equation:(1)g0=Z3+2Z6+Z9-Z1+2Z4+Z7,g45=Z2+2Z3+Z6-Z4+2Z7+Z8,g90=Z7+2Z8+Z9-Z1+2Z2+Z3,g135=Z8+2Z9+Z6-Z4+2Z1+Z2,where g0, g45, g90, and g135 are the gradient amplitude with 0°, 45°, 90°, and 135°, respectively. The maximal value and its direction were selected as gradient amplitude as shown in (2) and gradient direction, respectively, in the following process:(2)Gi=max⁡g0,g45,g90,g135.For 5× 5 subregion, nine gradient amplitudes and the directions according to each gradient amplitude can be computed, as shown in Table 2.Table 2
3 × 3 gradient amplitude template.
G
1
G
2
G
3
G
4
G
5
G
6
G
7
G
8
G
9The nonmaximum suppression method set the gradient valuesG5 of central point to 0 if the gradient amplitude G5 of central point is not local maximal, which indicates the location with the sharpest change of intensity value. According to the direction, the final gradient of the central point can be calculated by (3) as follows:(3)G5f=G5,G4<G5,G6<G5,gd=0°,G5,G3<G5,G7<G5,gd=45°,G5,G2<G5,G8<G5,gd=90°,G5,G1<G5,G9<G5,gd=135°,0,others,where gd is the direction of central point and G5f is the gradient amplitude of the central point after NMS processing.By traversing the whole image, the NMS processed gradient image was achieved. The larger value of gradient amplitude means more possibility of edge. To improve the accuracy of edge detection, threshold of gradient amplitude should be calculated to determine whether one point is edge point or not.


### 2.2. The Adaptive Strategy of Threshold Calculation

After NMS processing, gradient amplitude mainly concentrated in the smaller values ranges. The accuracy of edge detection is very sensitive to threshold. Thus, the calculation of threshold is a key step in the proposed method. In this subsection, calculation of adaptive threshold consists of three parts: histogram mapping, calculation of threshold according to maximal between-class variance, and inverse mapping of threshold as shown in Figure2.Figure 2
Flow chart of adaptive threshold calculation.In the step of histogram mapping, the gradient amplitudes were mapped into more widely values ranges. Histogram mapping function was defined as follows:(4)j=round16·i,where i is the value in original histogram and j is the value in mapped histogram. Function round rounds decimal to the nearest integer.In OTSU method [13], the optimum threshold separating the two classes was calculated by maximizing the between-class variance. Assuming that the NMS processed image contains two classes of point (edge point or not), the between-class variance can be computed by the following equation: (5)σB2=N1Nu1-u2+N-N1Nu2-u2,where σB2  is the between-class variance, N is the total number of pixels of NMS processed gradient image, u is the average gradient amplitude, N1 is the number of edge points, and u1 and u2 are the average values of edge points and background points, respectively, in the mapped gradient image.Equation (5) can be simplified into (6)(6)σB2=N1N-N1u1-u2.Furthermore,(7)N1=∑i=1tni,where ni is the number of points whose gradient value is i.The average gradient valueu can be calculated as (8)(8)u=∑i=1255i·ni∑i=1255ni.u
1 and u2 can be calculated as follows: (9)u1=∑i=1ti·ni∑i=1tni=utN1,u2=∑i=t+1Li·ni∑i=t+1Lni=u·N-utN-N1,where u(t) is equal to ∑i=1ti·ni.By traversingt from 1 to 254, the value t corresponding to the maximum between-class variance σB2 is the threshold T~. Finally, the adaptive threshold T in NMS processed image can be obtained by using inverse mapping as follows: (10)T=T~162.


### 2.3. The Processing of Double Threshold

The double thresholds were designed to determine the true or false edge points in NMS processed image. The threshold valueT was defined as the mean value between the high threshold and the low threshold. Then, the high threshold and the low threshold can be calculated as the following equations:(11)Th=T0.7≈1.43T,Tl=0.4·T0.7≈0.57T,where Th is the high threshold and Tl is the low threshold.In edge detection process, if the gradient value is greater thanTh, it was edge point. If the gradient value is smaller than Tl, it was not considered as edge point. In addition, if the gradient value is between high threshold and low threshold, at least one gradient value of neighborhood points (Table 2) is greater than the high threshold; this point was edge point; otherwise, it was not the edge point.


## 2.1. Gradient Calculation and NMS Processing

The original image was divided into 5× 5 subregion. The 3 × 3 Sobel operator of vertical, horizontal, and two diagonals (0°, 45°, 90°, and 135°) was employed to calculate the gradient, as shown in Tables 1(a), 1(b), 1(c), and 1(d).Table 1
3 × 3 Sobel operator.
(a)
0° template
−1
0
1
−2
0
2
−1
0
1
(b)
45° template
0
1
2
−1
0
1
−2
−1
0
(c)
90° template
−1
−2
−1
0
0
0
1
2
1
(d)
135° template
−2
−1
0
−1
0
1
0
1
2
(e)
The original grey value
Z
1
Z
2
Z
3
Z
4
Z
5
Z
6
Z
7
Z
8
Z
9The gradient of a 3× 3 image region (Table 1(e)) can be computed by multiplying the element value with the corresponding value in four directional Sobel operators. Then, four gradient values with direction were calculated as in the following equation:(1)g0=Z3+2Z6+Z9-Z1+2Z4+Z7,g45=Z2+2Z3+Z6-Z4+2Z7+Z8,g90=Z7+2Z8+Z9-Z1+2Z2+Z3,g135=Z8+2Z9+Z6-Z4+2Z1+Z2,where g0, g45, g90, and g135 are the gradient amplitude with 0°, 45°, 90°, and 135°, respectively. The maximal value and its direction were selected as gradient amplitude as shown in (2) and gradient direction, respectively, in the following process:(2)Gi=max⁡g0,g45,g90,g135.For 5× 5 subregion, nine gradient amplitudes and the directions according to each gradient amplitude can be computed, as shown in Table 2.Table 2
3 × 3 gradient amplitude template.
G
1
G
2
G
3
G
4
G
5
G
6
G
7
G
8
G
9The nonmaximum suppression method set the gradient valuesG5 of central point to 0 if the gradient amplitude G5 of central point is not local maximal, which indicates the location with the sharpest change of intensity value. According to the direction, the final gradient of the central point can be calculated by (3) as follows:(3)G5f=G5,G4<G5,G6<G5,gd=0°,G5,G3<G5,G7<G5,gd=45°,G5,G2<G5,G8<G5,gd=90°,G5,G1<G5,G9<G5,gd=135°,0,others,where gd is the direction of central point and G5f is the gradient amplitude of the central point after NMS processing.By traversing the whole image, the NMS processed gradient image was achieved. The larger value of gradient amplitude means more possibility of edge. To improve the accuracy of edge detection, threshold of gradient amplitude should be calculated to determine whether one point is edge point or not.


## 2.2. The Adaptive Strategy of Threshold Calculation

After NMS processing, gradient amplitude mainly concentrated in the smaller values ranges. The accuracy of edge detection is very sensitive to threshold. Thus, the calculation of threshold is a key step in the proposed method. In this subsection, calculation of adaptive threshold consists of three parts: histogram mapping, calculation of threshold according to maximal between-class variance, and inverse mapping of threshold as shown in Figure2.Figure 2
Flow chart of adaptive threshold calculation.In the step of histogram mapping, the gradient amplitudes were mapped into more widely values ranges. Histogram mapping function was defined as follows:(4)j=round16·i,where i is the value in original histogram and j is the value in mapped histogram. Function round rounds decimal to the nearest integer.In OTSU method [13], the optimum threshold separating the two classes was calculated by maximizing the between-class variance. Assuming that the NMS processed image contains two classes of point (edge point or not), the between-class variance can be computed by the following equation: (5)σB2=N1Nu1-u2+N-N1Nu2-u2,where σB2  is the between-class variance, N is the total number of pixels of NMS processed gradient image, u is the average gradient amplitude, N1 is the number of edge points, and u1 and u2 are the average values of edge points and background points, respectively, in the mapped gradient image.Equation (5) can be simplified into (6)(6)σB2=N1N-N1u1-u2.Furthermore,(7)N1=∑i=1tni,where ni is the number of points whose gradient value is i.The average gradient valueu can be calculated as (8)(8)u=∑i=1255i·ni∑i=1255ni.u
1 and u2 can be calculated as follows: (9)u1=∑i=1ti·ni∑i=1tni=utN1,u2=∑i=t+1Li·ni∑i=t+1Lni=u·N-utN-N1,where u(t) is equal to ∑i=1ti·ni.By traversingt from 1 to 254, the value t corresponding to the maximum between-class variance σB2 is the threshold T~. Finally, the adaptive threshold T in NMS processed image can be obtained by using inverse mapping as follows: (10)T=T~162.


## 2.3. The Processing of Double Threshold

The double thresholds were designed to determine the true or false edge points in NMS processed image. The threshold valueT was defined as the mean value between the high threshold and the low threshold. Then, the high threshold and the low threshold can be calculated as the following equations:(11)Th=T0.7≈1.43T,Tl=0.4·T0.7≈0.57T,where Th is the high threshold and Tl is the low threshold.In edge detection process, if the gradient value is greater thanTh, it was edge point. If the gradient value is smaller than Tl, it was not considered as edge point. In addition, if the gradient value is between high threshold and low threshold, at least one gradient value of neighborhood points (Table 2) is greater than the high threshold; this point was edge point; otherwise, it was not the edge point.


## 3. FPGA Implementation

The FPGA implementation scheme was mainly divided into three modules: image storage module, VGA display module, and algorithm executive module. The whole structure diagram was shown in Figure3.Figure 3
Block diagram of the system.


### 3.1. Image Storage Module

Image storage module consists of two on-chip ROMs. One was used to store address of pixels, and the other one was used to store the grayscale of the corresponding pixel. This design can reduce image storage space as shown in Figure4.Figure 4
Memory module.


### 3.2. VGA Display Module

VGA display module was designed to realize two main functions. Firstly, it can generate clock signal, blanking signal, line sync signal, and field sync signal for the display [20]. Secondly, it can produce the correct address signal for reading the image data stored in ROM. The module circuit was shown in Figure 5.Figure 5
VGA display module.


### 3.3. Algorithm Executive Module

Six submodules were designed to realize the edge detection algorithm, including gradient amplitude calculation submodule, gradient direction calculation submodule, NMS processing submodule, histogram mapping submodule, maximal between-class variance calculation submodule, and double threshold processing submodule.Gradient amplitude calculation submodule and gradient direction calculation submodule were used to calculate the eight neighborhood gradient amplitudes and gradient direction of center point, respectively. NMS processing module was designed to process gradient image. These three submodules were shown in Figure6.Figure 6
Gradient calculation related modules.
(a)
Gradient amplitude
(b)
Gradient direction
(c)
NMS processingHistogram mapping submodule was used to map the histogram of the gradient image. Maximal between-class variance calculation submodule was designed to find the threshold corresponding to maximal between-class variance. Double threshold processing submodule was used to inverse map the threshold and calculate double threshold. Threshold calculation related three submodules and connection were shown in Figure7.Figure 7
Adaptive threshold calculation related modules.


## 3.1. Image Storage Module

Image storage module consists of two on-chip ROMs. One was used to store address of pixels, and the other one was used to store the grayscale of the corresponding pixel. This design can reduce image storage space as shown in Figure4.Figure 4
Memory module.


## 3.2. VGA Display Module

VGA display module was designed to realize two main functions. Firstly, it can generate clock signal, blanking signal, line sync signal, and field sync signal for the display [20]. Secondly, it can produce the correct address signal for reading the image data stored in ROM. The module circuit was shown in Figure 5.Figure 5
VGA display module.


## 3.3. Algorithm Executive Module

Six submodules were designed to realize the edge detection algorithm, including gradient amplitude calculation submodule, gradient direction calculation submodule, NMS processing submodule, histogram mapping submodule, maximal between-class variance calculation submodule, and double threshold processing submodule.Gradient amplitude calculation submodule and gradient direction calculation submodule were used to calculate the eight neighborhood gradient amplitudes and gradient direction of center point, respectively. NMS processing module was designed to process gradient image. These three submodules were shown in Figure6.Figure 6
Gradient calculation related modules.
(a)
Gradient amplitude
(b)
Gradient direction
(c)
NMS processingHistogram mapping submodule was used to map the histogram of the gradient image. Maximal between-class variance calculation submodule was designed to find the threshold corresponding to maximal between-class variance. Double threshold processing submodule was used to inverse map the threshold and calculate double threshold. Threshold calculation related three submodules and connection were shown in Figure7.Figure 7
Adaptive threshold calculation related modules.


## 4. The Experiment Results and Analysis

In this section, the experimental results were analyzed in three aspects: resource usage rate, running duration, and accuracy of edge detection.


### 4.1. Resource Usage Rate

The DE2-115 education development board (Altera Corporation) with EP4CE115F29C7N chip was used in this experiment. The size of image was 640 × 480 pixels. The system resource usage was shown in Table3. Note that the resource usage of the whole system is less than the sum of the two subsystems, because of the repetition usage of the logical elements in subsystems. The logical elements used were 11% of the whole elements in running time, which suggested that the resource usage rate of proposed method is relatively low.Table 3
Resource usage of edge detection system.
Logical elements
Registers
Multiplier
Gradient calculation
3800
2032
0
Adaptive threshold calculation
9263
3999
7
The whole system
12461
5654
7


### 4.2. Running Duration of Each Process

In previous works, adaptive edge detection algorithm [21] and a simple Canny algorithm [22] were realized by FPGA. Comparison of running duration with those works was shown in Table 4. Although the working frequency of proposed method was relatively lower, the running duration of each process was shorter, which demonstrated the higher speed of proposed algorithm.Table 4
System running duration.
Algorithm
Platform
Image size
Uptime
Adaptive threshold algorithm in [21]
Cyclone II, working frequency: 50 MHz
512 × 512 × 8 bits
0.0313 s
Simple Canny algorithm in [22]
Virtex-5, working frequency: 100 MHz
512 × 512 × 8 bits
0.0287 s
The proposed algorithm based on FPGA
Cyclone IV, working frequency: 50 MHz
640 × 480 × 8 bits
0.0245 s


### 4.3. Accuracy of Edge Detection

Image Lena (Figure8(a)) and image Flower (Figure 9(a)) were used in edge detection experiments. The detection results of the two images were shown in Figures 8(b), 8(c), and 8(d) and Figures 9(b), 9(c), and 9(d), respectively. Compared with the other two methods, the detected edge by proposed method is thinner than the other methods.Figure 8
The edge detection results with image Lena, (a) original image, (b) method in [23], (c) Prewitt method, and (d) proposed method.
(a)
(b)
(c)
(d)Figure 9
The edge detection results with image Flower, (a) original image, (b) method in [23], (c) Prewitt method, and (d) proposed method.
(a)
(b)
(c)
(d)The positive rates of edge detection were calculated to evaluate the effect of the proposed method, as shown in Table5. Compared with Roberts operator, Prewitt operator, Sobel operator, LoG operator, and Canny operator, true positive rate by proposed method is the highest and false positive rate is relatively lower. These results suggested that the proposed method can detect the edge more accurately.Table 5
Comparison of the positive rate.
True positive rate (%)
False positive rate (%)
Roberts operator
31.26
1.02
Prewitt operator
34.08
0.58
Sobel operator
32.73
0.53
LoG operator
26.83
2.39
Canny operator
45.17
5.2
Proposed method
48.16
1.19


## 4.1. Resource Usage Rate

The DE2-115 education development board (Altera Corporation) with EP4CE115F29C7N chip was used in this experiment. The size of image was 640 × 480 pixels. The system resource usage was shown in Table3. Note that the resource usage of the whole system is less than the sum of the two subsystems, because of the repetition usage of the logical elements in subsystems. The logical elements used were 11% of the whole elements in running time, which suggested that the resource usage rate of proposed method is relatively low.Table 3
Resource usage of edge detection system.
Logical elements
Registers
Multiplier
Gradient calculation
3800
2032
0
Adaptive threshold calculation
9263
3999
7
The whole system
12461
5654
7


## 4.2. Running Duration of Each Process

In previous works, adaptive edge detection algorithm [21] and a simple Canny algorithm [22] were realized by FPGA. Comparison of running duration with those works was shown in Table 4. Although the working frequency of proposed method was relatively lower, the running duration of each process was shorter, which demonstrated the higher speed of proposed algorithm.Table 4
System running duration.
Algorithm
Platform
Image size
Uptime
Adaptive threshold algorithm in [21]
Cyclone II, working frequency: 50 MHz
512 × 512 × 8 bits
0.0313 s
Simple Canny algorithm in [22]
Virtex-5, working frequency: 100 MHz
512 × 512 × 8 bits
0.0287 s
The proposed algorithm based on FPGA
Cyclone IV, working frequency: 50 MHz
640 × 480 × 8 bits
0.0245 s


## 4.3. Accuracy of Edge Detection

Image Lena (Figure8(a)) and image Flower (Figure 9(a)) were used in edge detection experiments. The detection results of the two images were shown in Figures 8(b), 8(c), and 8(d) and Figures 9(b), 9(c), and 9(d), respectively. Compared with the other two methods, the detected edge by proposed method is thinner than the other methods.Figure 8
The edge detection results with image Lena, (a) original image, (b) method in [23], (c) Prewitt method, and (d) proposed method.
(a)
(b)
(c)
(d)Figure 9
The edge detection results with image Flower, (a) original image, (b) method in [23], (c) Prewitt method, and (d) proposed method.
(a)
(b)
(c)
(d)The positive rates of edge detection were calculated to evaluate the effect of the proposed method, as shown in Table5. Compared with Roberts operator, Prewitt operator, Sobel operator, LoG operator, and Canny operator, true positive rate by proposed method is the highest and false positive rate is relatively lower. These results suggested that the proposed method can detect the edge more accurately.Table 5
Comparison of the positive rate.
True positive rate (%)
False positive rate (%)
Roberts operator
31.26
1.02
Prewitt operator
34.08
0.58
Sobel operator
32.73
0.53
LoG operator
26.83
2.39
Canny operator
45.17
5.2
Proposed method
48.16
1.19


## 5. Conclusion

An improved adaptive edge detection algorithm based on the NMS method was proposed in this paper. In the proposed method, a power map function was defined to map the NMS processed gradient image. Then, adaptive threshold corresponding to maximal between-class variance was calculated based on the mapped histogram. Additionally, the proposed method was realized in FPGA. Experimental results showed that this method has higher processing speed and better accuracy, which was suitable for application in real-time image processing.



---

*Source: 1470312-2015-12-22.xml*