Edge Chain and Line Segment Detection by Applying Helmholtz Principle on Gradient Magnitude Map


Xiaohu Lu, Jian Yao*, Li Li, Yahui Liu and Wei Zhang

School of Remote Sensing and Information Engineering, Wuhan University, Wuhan, Hubei, P.R.China

*EMail: jian.yao@whu.edu.cn

*Web: http://www.scholat.com/jianyao http://cvrs.whu.edu.cn


[] The C++ source codes are released.download (9/5/2016).


1. Abstract

In this paper, we develop the Helmholtz principle on the gradient magnitude map of an image in the view of probability theory, and apply it on the detection of edge chains and line segments. The traditional Helmholtz principle needs a good estimation of Nconf to calculate the "number of false alarms" (NFA) of an event, which is difficult in some applications. To overcome this shortage, we propose to use the "relative number of false alarms" (RNFA) instead of the traditional NFA to validate an event. Based on this observation, a simple and efficient edge chain detection algorithm is proposed, which detects edge chains via edge pixel growing first and then validates the edge chains according to their RNFAs. In this way, not only edge chains that are weak in contrast but meaningful in vision can be detected, but also the false alarms ratio is controlled in a low level. Extending this observation to the line segment detection, we propose a novel line segment detector which fits for straight line segments directly on the gradient magnitude map instead of the edge chains which often suffer from the influence of noise. To evaluate the proposed edge chain and line segment detectors in quantity, both an edge chain detection benchmark with 25 semi-automatically labeled images and a line segment detection benchmark with 30 images were built. The proposed edge chain and line segment detectors were tested in these two benchmarks. The experimental results on the benchmarks sufficiently demonstrate that the proposed edge chain and line segment detectors outperform the state-of-the-art methods.

2. Helmholtz Principle on Gradient Magnitude Map

For each integral gradient magnitude level $u \in [1,g_{\max}]$ where $g_{\max}$ is the maximum gradient magnitude level in the gradient magnitude map $\mathbf{G}$, the number of pixels whose gradient magnitude level is equal or greater than $u$ is denoted as $k(u)$, thus the probability of the considered quality that "a pixel on $\mathbf{I}$ whose gradient magnitude level is equal or greater than $u$" is defined as: \begin{equation}\label{Eq:Probability2} P(u) = k(u) / M, \end{equation} where $ M = w \times h$ is the size of $\mathbf{I}$.

$\textbf{Definition of NFA} - \textbf{Number of False Alarms}$. Given an event $\mathcal{E}$ (a detected structure) made up of $l$ pixels on an image, $N_{\textrm{conf}}$ is the theoretical number of $\mathcal{E}$ on the image, $u$ is the minimal gradient magnitude of these pixels, the NFA of $\mathcal{E}$ on the gradient magnitude map is defined as: \begin{equation}\label{Eq:NFAGradient} \text{NFA} = N_{\textrm{conf}} \times P(u)^l. \end{equation}

In some applications, it is difficult to give a good approximation of the $N_{\textrm{conf}}$, for example the value of $N_{\textrm{conf}}$ for edge chain is hard to be obtained. In this case, we propose to use the ``relative number of false alarms" (RNFA) to validate edge chains.

$\textbf{Definition of RNFA} - \textbf{Relative Number of False Alarms}$. Given an event $\mathcal{E}$ (a detected structure) whose binomial probability is $\mathcal{B}(n,k,p)$, and $\mathcal{E}_{r}$ is a minimal meaningful event (MME) whose binomial probability is $\mathcal{B}(n_r,k_r,p_r)$. The relative number of false alarms of $\mathcal{E}$ to $\mathcal{E}_{r}$ is defined as: \begin{equation}\label{Eq:RNFA} \text{RNFA} = \frac{N_{\textrm{conf}} \times \mathcal{B}(n,k,p)}{N_{\textrm{conf}} \times \mathcal{B}(n_r,k_r,p_r)} = \frac{\mathcal{B}(n,k,p)}{\mathcal{B}(n_r,k_r,p_r)}, \end{equation} where $N_{\textrm{conf}}$ is the number of different possible configurations one could have for the searched event, and we simply say that the event is meaningful than the minimal meaningful event (MME) if $\text{RNFA} < 1$.

3. Edge Chain Detection

3.1. Edge Chain Validation

We consider using the proposed RNFA to validate the meaningfulness of the edge chains.

$\textbf{Definition of MME}_{\textbf{edge}} - \textbf{Minimal Meaningful Edge Chain Event}$. A minimal meaningful edge chain event is defined as the edge chain with a size of $L_{mm}$ and a minimal gradient magnitude equal to $g_{\min}$.

The $g_{\min}$ is a user defined parameter which is set as a constant, and $L_{mm}$ is the minimum length of a meaningful line segment, which can be very well solved according to the works of LSD and CannyLines as following: \begin{equation}\label{Eq:LMM} L_{mm} = -2.5\log(M) / \log(p), \end{equation} where $ M = w \times h$ is the size of $\mathbf{I}$ and $p=1/8$.

3.2. Edge Chain Detector

The proposed edge chain detector contains four steps:

  • First, given a gray image $\mathbf{I}$, a $3\times 3$ Gaussian filter with the standard deviation $\sigma = 1$ is applied to suppress noise and smooth out the image, then the gradient magnitude map $\mathbf{G}$ and gradient orientation map $\mathbf{O}$ of $\mathbf{I}$ are calculated by applying a certain gradient operator (a $3\times 3$ Sobel was applied in our work).
  • Then, the non-maximum suppression procedure is applied on $\mathbf{G}$, the gradient magnitudes of those suppressed pixels are set zero and the remaining ones are edge pixels, the set of which is denoted as $\mathbf{E}$.
  • Third, the set $\mathbf{E}$ is roughly sorted in descending order according to the gradient magnitudes. The foremost unprocessed edge pixel in $\mathbf{E}$ is selected as the initial seed pixel $\mathbf{p}_{seed}$. The 8-neighborhood of the $\mathbf{p}_{seed}$ is searched, if there exists a 8-neighbor who is an unprocessed edge pixel, we consider this pixel to be the next seed pixel, then we add it into the current edge chain and begin 8-neighbor searching from this newly added pixel. On each step, the gradient orientation deviation between $\mathbf{p}_{seed}$ and the newly added edge pixel is calculated. The seed growing of the current edge chain is conducted iteratively until all the pixels in this chain is processed or there exist two consecutive steps where the orientation deviations are both greater than $\theta$, which means that there is no more smooth edge chains exist in front, then we add the current edge chain into the edge chain set $\mathcal{C}$ and begin with another edge chain from the rest of $\mathbf{E}$.
  • Each edge chain detected in the step (3) is validated by the Helmholtz principle on edge chain proposed in Section 3.1 to get rid of the false alarms. The same strategy as that of EDPF is applied, that is: if the RNFA of an edge chain $\mathbf{C}$ is larger than 1, i.e., RNFA $>1$, the pixel $\mathbf{p}$ is the one with the minimum gradient magnitude in $\mathbf{C}$, then $\mathbf{C}$ is divided into two sub edge chains $\mathbf{C}_{1}$ and $\mathbf{C}_{2}$ at $\mathbf{p}$, then $\mathbf{C}_{1}$ and $\mathbf{C}_{2}$ are added into $\mathcal{C}$ and validated later.

4. Line Segment Detection

4.1. Line Segment Validation

We apply the NFA on the validation of line segments.

Assume that there is a line segment made up of $l$ pixels, the minimal gradient magnitude of these pixels is $u$, the NFA of this line segment is: \begin{equation}\label{Eq:NFALine} \text{NFA} = M^{2.5} \times P(u)^l, \end{equation} where $M = w \times h$ is the size of the image. If $\text{NFA} < 1$, we simply say that the event is meaningful.

It's worth noting that we can also apply the RNFA on the line segment validation if a minimal meaningful line segment event is given. In this work, we recommend to apply both NFA and RNFA to double check the line segments, in this way the performance of the validation procedure can be adjusted by setting a customized $g_{\min}$.

4.2. Line Segment Detector

The first two steps are the same as those of the edge chain detector proposed in Section 3.2 and the resting steps are described as follows:

  • First, the set $\mathbf{E}$ is roughly sorted in descending order according to the gradient magnitudes. The foremost unprocessed edge pixel in $\mathbf{E}$ is selected as the initial seed pixel $\mathbf{p}_{seed}$, and the tangent line $\mathbf{l}$ of $\mathbf{p}_{seed}$ (passing $\mathbf{p}_{seed}$ and orthogonal to the gradient orientation of $\mathbf{p}_{seed}$) is set as the initial line segment. Then the 8-neighborhood of $\mathbf{p}_{seed}$ is searched and any edge pixel in the 8-neighborhood whose orthogonal distance to $\mathbf{l}$ is less than $2.0$ is collected as the "support edge pixels". All the collected support edge pixels are as a set $\mathbf{E}_{line}$. The growing procedure of the current line segment is conducted iteratively until all the pixels in $\mathbf{E}_{line}$ are processed, and then we begin with another line segment from the rest of $\mathbf{E}$. To efficiently fit the line segment in the growing procedure, we adopt the following simple strategy. Whenever the number of newly added support edge pixels is greater than $1/5$ of the size of $\mathbf{E}_{line}$, the tangent line $\mathbf{l}$ is updated by applying the least square fitting on $\mathbf{E}_{line}$.
  • Each line segment detected in the above step is validated by the Helmholtz principle on line segment proposed in Section 4.1.

5. Experimental Results

5.1. Evaluation on Edge Chain Detector

5.1.1 Edge Chain Benchmark

To evaluate the performance of the proposed edge chain detector, we built an edge chain benchmark with ground truth edge chains labeled in a semi-automatic way. There are 25 labeled images in our benchmark, most of which were selected from the EDC dataset. Fig. 1 shows six representative images and the corresponding ground truth edge chains on the proposed benchmark.

Fig. 1. Six representative images and the corresponding ground truth edge chains on the proposed benchmark.

5.1.2 Choice of Best $g_{\min}$

As an edge chain detector, we consider to detect as many meaningful edge chains as possible. In this condition, we should find the value of $g_{\min}$ corresponding to the minimal meaningful edge chain event. To find out the best value of $g_{\min}$ for edge chain detection, we tested the proposed edge chain detector on our edge chain benchmark with $g_{\min}$= 40, 60, 80, 100, 120, 140, 160, 180, and 200, respectively. Fig.2(a) shows the edge chain detection results on our benchmark with different values of $g_{\min}$, we recommend to set $g_{\min}=120$ as a balance between the precision and recall for edge chain detection.

As an object boundary detector, we consider to detect as many boundary as possible. In this condition, the value of $g_{\min}$ should be greater than that of edge chain detection because the boundaries are usually with greater contrast. To find out a general value of $g_{\min}$ for boundary detection, we tested the proposed edge chain detector on the RUG dataset with $g_{\min}$= 100, 120, 140, 160, 180, 200, 220, 240, and 260, respectively. Fig.2(b) shows the edge chain detection results on the RUG with different values of $g_{\min}$, we recommend to set $g_{\min}=180$ as a balance between the precision and recall for boundary detection.

(a) (b)

Fig. 2. Different performances of our proposed edge chain detection algorithm with different values of $g_{\min}$.

5.1.3 Comparison with State-of-the-Art Methods

We compared it with other four state-of-the-art edge detection methods, including: EDPF, ED, SREdge and CannyPF on the proposed edge chain benchmark, the RUG dataset and the BSDS dataset. Table 1 shows the average accuracies of these algorithms on the proposed benchmark and the RUG dataset. We can see in this table that the proposed RNFA method achieves the highest values on both precision and $F$-score, which are much better than the EDPF on the second place. Fig.3 shows the precision recall curve of the five tested algorithms on the BSDS dataset, in which we set $g_{\min}=180$ for the proposed RNFA method. We can see that the performances of the RNFA and EDPF are close to each other with the same $F$-score equals 0.57, which are better than that of the SREdge (0.53), ED (0.52) and CannyPF (0.52). Fig.4, 5, 6 show the edge chain detection result of the five tested methods on our benchmark, the RUG dataset and the BSDS dataset, respectively.

Table 1. Comparison of CannyPF, ED, SREdge, EDPF and RNFA on the proposed edge chain benchmark and the RUG dataset.

Algorithm CannyPF ED SREdge EDPF RNFA
Measure R P F R P F R P F R P F R P F
Our Benchmark 0.88 0.49 0.59 0.83 0.55 0.62 0.79 0.61 0.65 0.81 0.65 0.71 0.82 0.75 0.77
RUG Dataset 0.82 0.16 0.26 0.83 0.19 0.29 0.81 0.23 0.35 0.72 0.26 0.37 0.60 0.44 0.49

Fig. 3. PR curve of the five tested algorithms on the BSDS dataset.

Fig. 4. The proposed edge chain benchmark, click on each image to see the detection result of RNFA, EDPF, SREdge, ED and CannyPF in detail.

Fig. 5. The RUG dataset, click on each image to see the detection result of RNFA, EDPF, SREdge, ED and CannyPF in detail.

Fig. 6. The edge chain detection result of the proposed RNFA method on 16 images in the BSDS dataset.

5.2. Evaluation on Line Segment Detector

5.2.1 Line Segment Benchmark

To evaluate the performance of the proposed line segment detector, we built a benchmark with ground truth line segments labeled in the same way as the edge chain benchmark in Section 5.1.1. There are 30 labeled images in our benchmark, all of them were selected from the YorkUrbanDB dataset. These images cover a range of indoor and outdoor scenes.

5.2.2 Comparison with State-of-the-Art Methods

To sufficiently evaluate the performance of the proposed NFA+RNFA line segment detector, we compared it with other three state-of-the-art line segment detectors, including: CannyLines, LSD and EDLines. We also tested the line segment detection result based on the edge chains detected by the proposed RNFA based edge chain detector. The least square method to fit for line segments on each edge chains, also the same gradient orientation line validation procedure as LSD and EDLines is applied to get rid of false alarms. We denote this line segment detector as RNFAEdge. Fig.7 shows the line segment detection results of NFA+RNFA, RNFAEdge, CannyLines, LSD and EDLines on our benchmark. Table 2. is the comparison of EDLines, LSD, CannyLines, RNFAEdge and NFA+RNFA on our line segment benchmark.

Table 2. Comparison of EDLines, LSD, CannyLines, RNFAEdge and NFA+RNFA on our line segment benchmark.

Algorithm EDLines LSD CannyLines RNFAEdge NFA+RNFA
Measure R P F R P F R P F R P F R P F
Average 0.638 0.724 0.675 0.729 0.796 0.757 0.792 0.819 0.802 0.827 0.865 0.843 0.862 0.841 0.851

Fig. 7. The proposed line segment benchmark, click on each image to see the detection result of NFA+RNFA, RNFAEdge, CannyLines, LSD and EDLines in detail.

Dataset and Codes

Citation

  • Xiaohu Lu, Jian Yao*, Li Li, Yahui Liu, and Wei Zhang. Edge Chain and Line Segment Detection by Applying Helmholtz Principle on Gradient Magnitude Map, Submitted to IEEE Transactions on Image Processing, May 2016.