This paper extends the scale-invariant edge detector to the one-dimensional slope. It can accurately detect the slope and estimate its parameters. The method has been verified with several mathematical functions, sample sizes, and noise levels. A contrast-invariant operator is proposed to suppress noise. The inter-sample localization and interpolation greatly improve the accuracy. The proposed slope detector is also suitable for real-world signals. In additional to above-mentioned, a threshold formula is developed for the first derivative slope detector, and the upper-bound of the filterable noise level is also explored.
Keywords:Slope; Gaussian; Threshold; Error function; Sub-sample; Localization; Interpolation; Noise suppression; The first derivative operator
This paper concerns the slope detection of one-dimensional discrete signals (Oppenheim and Willsky 1983). The one-dimensional slope detection shares some common problems (e.g. noise suppression, threshold selection) with the two-dimensional case (Bansal et al. 2012, Pinho and Almeida 2012). This paper is dedicated to these problems.
The edge detection has attracted the attention of many researchers. To suppress signal noise, Witkin proposed a scale space by convolving the input signal with the Gaussian distribution function (Witkin 1983). Canny treated the first derivative of the Gaussian distribution function as one-dimensional edge detector (Canny 1986). Marr et al. studied edge detection using the zero crossing of the second derivative of the Gaussian (Marr 1980). Zhang et al. found a scale-invariant edge detector (Zhang and Liu 2013).
Although two-dimensional edge detection is a well-established subject, however, it seems that the slope of one-dimensional discrete signal is seldom studied. The first derivative operator is a seemingly easy solution. This paper will discuss its problems in detail, and give the remedies. Noise suppression is an important subject of slope detection. Inspired by a contrast-invariant differential operator (Zhang and Liu 2013), a method capable of effectively differentiating noise and slope is proposed. The selection of the smoothing scale is another major problem of many existing methods. The scale-invariant edge detector can address the issue by automatically choosing the adequate scale for each edge feature. This research extends the technique to the one-dimensional slope detection. Because of the apparent distinction between the one dimensional and the two dimensional signals, the scale-invariant edge detector is adjusted for the slope with additional functions of inter-sample localization and interpolation. The proposed method is suitable for several broad classifications of signals: noisy and noiseless, periodic and non-periodic, densely and sparsely sampled.
One dimensional slope detection
An ideal slope function is needed to investigate detectors quantitatively. The function is characterized by a position, contrast, offset, and width parameters (Figure 1). These parameters can be modeled by the x0, c, d, and w constant parameters of an error function (Equation 1).
Figure 1. An ideal slope and its parameters.
A step is just a special ideal slope with zero width (Equation 2), therefore all forthcoming discussions are equally applicable.
For a function f having the shape of a slope, two steps are involved to acquire a slope of width w, contrast c, position x0, and offset d, as shown in Equation 3. The min and max functions return minimum and maximum value of their inputs. The discussion is based on the ideal slope (Zhang and Liu 2013), and the result is verified by several slope functions.
Convolving the input slope function and the Gaussian distribution function results in the scale space (Equation 4) of the input signal where the σ represents the scale. It is easy to verify that the L function is also an error function.
The error function has nice properties. For example, with a variable substitute (Equation 6), both the error function and its scale space are solutions of the heat equation:
Because the scale space of the ideal slope and its differential operators are represented in closed-form, further investigation can be carried out.
Scale and spatial detector
The Lx operator is used in this paper to denote the scale-normalized derivative of L with respect to x (Equation 7). The scale-normalization is necessary for a scale-invariant detector (Zhang and Liu 2013). The derivative of Lx with respect to scale is shown in Equation 8.
To detect a slope on a specific scale, the operator should have a local extremum along the scale coordinate axis. In order to show that Lxs satisfies the requirement, Equation 9 (Zhang and Liu 2013) is used to substitute variables. The ξ and Q can be treated as scale-normalized x and w.
Figure 2 shows the variable substituted version of Lx and Lxs. The Lx operator has a local extremum along the ξ coordinate axis, and the Lxs operator has a local extremum along the Q coordinate axis.
Figure 2. The transformed Lx and Lxs.
The location of Q is solved by taking the derivative of Lxs with respect to Q and evaluating to zero (Equation 10).
The same thing can be illustrated by Figure 3. Using planes ξ=0 and Q=sqrt(2) to intersect Lx and Lxs results in curves. The diagram in the upper left quadrant of Figure 3 shows Lx lacking a local extremum along Q coordinate axis. On the other hand, Lxs has a local extremum along Q coordinate axis (upper right quadrant). From the diagrams in the lower left and lower right quadrants of Figure 3, it seems that both operators having a local extreme along ξ coordinate.
Figure 3. The spatial and scale perspective of Lx and Lxs.
To ensure the existence of a local extremum of Lxs along the ξ coordinate axis, the second derivative of Lxs with respect to ξ is computed, obtaining a zero (Equation 11).
The fact indicates that Lxs has not a local extremum along the ξ coordinate and therefore can not locate spatial position. To detect the position and scale of a slope, two operators are necessary.
The slope is detected when Lxs reaches a local extremum along the scale coordinate. As shown in Equation 12, the contrast of the slope can be solved for using Lxs and the offset can be solved for using L (value at the extremum location). To detect step slopes, a pre-smoothing operation with a small scale is required. The pre-smoothing scale is removed from the detected scale, results in the width.
Inter-sample localization and interpolation
Directly applying the method of continuous functions will produce noticeable errors for discrete signals. Sub-pixel localization can be applied to three-dimensional scale space functions (Brown and Lowe 2002, Lowe 2004). This paper adopts a slightly different approach, because the scale and position are detected by two different operators. Taking the derivative of the Taylor expansion of a function can determine the inter-sample location. The Lxs operator is used for scale localization (Equation 13) and Lx for spatial localization (Equation 14).
Bilinear interpolation using the refined location and scale is involved to compute the parameters. The inter-sample localization and interpolation procedure greatly improves the detection and estimation accuracy. Figure 4 illustrates located slopes between samples and the interpolated vertical position (d+c/2).
Figure 4. Sparsely sampled sine slopes detected by the proposed detector.
The scale space (L) and the Lx spaces are computed in the frequency domain (Cooley and Tukey 1965):
Where σs is the discrete smoothing scale given by Equation 20.
The Gaussian and the derivative of the Gaussian convolution kernels can be computed using the expression:
The Lxs is implemented using a central difference:
The scale and spatial derivatives of Lx and Lxs can be obtained using differences (Equation 18 and Equation 19), and these values are used for the inter-sample localization.
In Table 1 and Equation 20, the maximum scale ensures that the convolution kernel will not exceed the signal boundary. Only slopes with contrast greater than 0.05 are considered therefore low contrast slopes are ignored as a noise. Because narrow slopes (e.g. step) are difficult to detect; it is necessary to smooth the signal first using some small scale. However, for better accuracy, pre-smoothing operation is not performed for the parameter estimation experiment.
Table 1. Implementation configuration
It is well-known that the first derivative operator is extremely sensitive to noise; therefore a smoothing operation is often carried out to suppress noise. Although a large scale can filter the high level noise, signal details are also removed. The smoothing scale is often selected empirically, and a minimum scale is necessary to filter a certain noise level (mean and standard deviation). The minimum scale can only be determined by the scale-invariant detectors (instead of Lx). Therefore the following paragraphs deduce the threshold of Lx for a pre-smoothing scale.
The threshold of the first derivative operator
The first derivative of the smoothed ideal slope at the location of x0 can be obtained using Equation 21, where the σ is the pre-smoothing scale.
If the minimum and maximum values are denoted by subscript m and M, then the low and high threshold of the Lx detector are represented by Tm and TM (Equation 22). The TM and the first component of Tm filter slopes whose contrast is within the range of cm and cM, and the width within wm and wM. A noise can be filtered out by the second component of Tm, if the standard deviation (stdn) and mean (meann) of the noise are known. It is assumed that the highest contrast of a Gaussian noise is six times the standard deviation plus the mean, and its lowest width is wmn (a small value, e.g. 0.5). If the second component of Tm is smaller than the first component, then all slopes within the range are detectable. If the second component of Tm is between the first one and TM, then only slopes of partial range are detectable. Otherwise, no slope can be detected. Besides, six times standard deviation is guaranteed to filter out all noise points in principle, while three times standard deviation may preserve a few noise points.
In order to detect slope and filter out all noise, the second component of Tm should be no more than TM (equation 23). An upper bound of the filterable noise is achieved with an infinite large pre-smoothing scale. The noise with higher standard deviation can not be completely removed from the detectable slopes.
As defined by Table 2, the highest contrast of synthesized ideal slopes is 1, hence the highest contrast of filterable noise is also 1. Without loss of generality, the experiments are based on Gaussian noise series of zero mean and random standard deviation. The Lx detector uses the thresholds (Tm and TM) to filter out noise. The errors of Lx are effectively reduced, as shown in Table 3 and Table 4.
Table 2. Parameter ranges for ideal slopes
Table 3. RMSD of positional errors of the Lx detector for the noisy ideal slopes, without considering noise threshold
Table 4. RMSD of positional errors of the Lx detector for the noisy ideal slopes, considering noise threshold
A method to differentiate slope and noise
Two techniques are adopted by the proposed method to suppress noise. The first is setting contrast threshold (Equation 24), and the second is limiting an operator to some range. The contrast is estimated using equation 12; therefore this sub-section will concentrate on the second technique.
The ratio of the two operators of the ideal slope is a constant at the extremum location, as shown in Equation 25.
Table 5 lists the ratios’ range, mean and standard deviation of several slope functions. For each slope function, the experiment uses Table 2 to generate 1000 synthesized slopes. The ratios of different slope functions are similar, because the means are near 2/3, and the standard deviations are small.
Table 5. statistics of Lxs/Lx for various slope functions
The ratio behaves differently for noise. Figure 5 illustrates the ratios’ distribution for Gaussian noise. The ratios are mainly located at negative axis, and reach a peak near −1.5.
Figure 5. Lxs/Lx of Gaussian noise of zero mean and random standard deviations, pre-smoothing scale and Tmare 0.
The following content tries to explain the phenomenon. A noise (impulse) of contrast, offset, and width (c, d, and w) is modeled by:
As before, the scale space L is the Gaussian smoothed signal, and the Lxs and Lx operators can be obtained from Equation 7 and Equation 8. The ratio equals −2 when both Q and ξ are zero (Equation 27).
The division of Lxs and Lx is shown in Figure 6. Because the width of the noise impulse is near zero, the location (x) of the feature is also near zero. And because the smoothing scale is not zero, according to Equation 9, Q and ξ are also near zero. However, since both Q and ξ are actually small values, the ratio will be slightly larger than −2 (accord with −1.5 in Figure 5).
Figure 6. Lxs/Lx of noise impulse signal.
Experimenting on Gaussian noise series of zero mean (meann) and random standard deviations (stdn), Table 6 lists the percentages of Lxs/Lx at three intervals under two conditions. The first condition is four pre-smoothing scales, and the second is the contrast thresholds, which is 0, 1, 3, or 6 times standard deviation of the noise. The table indicates that, increasing the contrast threshold will reduce the percentage of Lxs/Lx at interval [0, 1). The characteristic contributes to noise suppression, because the noise and the slopes are indistinguishable in this interval. Noise is suppressed by large pre-smoothing scale, leading to a lower contrast threshold. The noise is completely removed by pre-smoothing scale 1 and contrast threshold of 6 times standard deviation. The experiment shows that the noise can be suppressed by the following procedures: pre-smoothing the signal with a small scale, setting appropriate contrast threshold, and limiting the Lxs/Lx.
Table 6. The percentages of Lxs/Lx of noise at three intervals under two conditions
The quantitative experiments involve 1000 randomly generated synthesized slopes with parameters listed in Table 2. Signal is sampled from −256 to 256 discretely and the slope is centered at x0.
The positional error (ex) was measured by the distances between the slope center and the detected location (Equation 28). The slope centers could be located between the samples. Except the width of the step slopes, the parameter estimation accuracies have been measured by the relative error where the true value of a quantity is q and the inferred value q0:
The root mean squared deviation (RMSD) of the error is given by
where en is the nth actual error and ϵn is assumed to be zero.
The step slopes are pre-smoothed with scale 1 and the width is measured by absolute errors. Except the erf and step slope, the widths are transformed by median values for different function. The estimated parameters of the ideal slopes are more precise than other slope functions (Table 7). Although the signals are sampled at discrete points, the inter-sample locations are precisely recovered. The offset is estimated using the scale space and the estimated contrast, therefore has a slightly lower accuracy.
Table 7. RMSD of positional errors of the proposed method, pre-smoothing scale 0
The following experiments use the RMSD of the positional error to evaluate the performances. Except ramp slope, Lx produces similar errors for several slope functions (Table 8). The Lx of ramp is a constant; therefore a local extremum can not be found at the slope center. It can be verified that if Lx is implemented by a central difference, then a pre-smoothing is required for step slopes.
Table 8. RMSD of positional errors of the Lx detector for the ideal slopes
The proposed method achieves lower error because of the inter-sample localization (Table 9). A pre-smoothing is also required for the step slopes, because zero width can not be detected in the scale space.
Table 9. RMSD of positional errors of the proposed detector for the ideal slopes
The following experiments adopt zero-mean Gaussian noise. For the experiment of Table 10, the pre-smoothing scale is 2, and the standard deviation of the noise is a random variable between 0.001 and 1. A lower error is achieved with either a high contrast threshold (Tm) or a constraint of Lxs/Lx.
Table 10. RMSD of positional error of the proposed method for noisy ideal slopes under two conditions
Assuming zero noise (omitting the second component of the lower threshold in Equation 22 and Equation 24), the Lx (Table 3) will be more sensitive to noise than the proposed method (Table 11). Even for low level noise, Lx needs large pre-smoothing scales to suppress noise. Both methods sacrifice for high level noise.
Table 11. RMSD of positional errors of the proposed detector for the noisy ideal slopes, without considering noise threshold
Incorporating noise information to the lower threshold, both methods produce significantly lower errors (Table 4 and Table 12). The proposed method achieves low errors for noisy slopes without large pre-smoothing scale. For a large pre-smoothing scale (e.g. 64), the two methods show similar performances.
Table 12. RMSD of positional errors of the proposed detector for the noisy ideal slopes, considering noise threshold
In additional to densely sampled signals, the method presented here can also detect slopes of sparsely sampled signals. For these slopes (sample size is 21), the proposed method (Table 13) outperforms Lx(Table 14). However the result of sparsely sampled slopes (Table 13) is not as good as that of densely sampled slopes (Table 9).
Table 13. RMSD of positional errors of the proposed detector for the sparsely sampled ideal slopes
Table 14. RMSD of positional errors of the Lx detector for the sparsely sampled ideal slopes
Some qualitative examples
A few slopes of periodic signals are displayed in Figure 7, where the signal-to-noise ratio of the noisy signals is 25dB.
Figure 7. Slopes of periodic signals.
Using a script (Renfree 2008), historical stock data can be retrieved from a financial website (Yahoo! Finance 2013). Figure 8 shows historical stock data of CitiBank from January, 2003 to December, 2008, with threshold 1. The proposed method successfully detects slopes of various widths, contrasts, offset,and locations.
Figure 8. Slopes detected for stock data by the proposed method.
Simple methods such as the first derivative or zero crossings of the second derivative are very sensitive to noise. To detect a slope, two operators are necessary, which should have a local extremum along either the scale or the spatial coordinate axis. The proposed detector involves the scale derivative of the spatial derivative operator, with scale-normalization. Using an error function as a test slope, the parameters are solved for precisely in closed form. A precise inter-sample localization and interpolation procedure is proposed to improve the accuracy. The method can extract slopes from synthesized or real-world signals while detecting less noise than its counterpart methods. Based on mathematical functions, the threshold selection of the first derivative is also discussed.
The authors declare that they have no competing interests.
Xiaochun Zhang proposed the problem, implemented the algorithm and drafted the manuscript. Chuancai Liu carried out the review and suggestion. All authors read and approved the final manuscript.
This work is partially supported by National Natural Science Foundation of China (Grant No. 60472061, 60632050, 90820004), National 863 Project (Grant No. 2006AA04Z238, 200 6AA01Z119), the project of Ministry of Industry and Information Technology of China (Grant No. E0310/1112/JC01).
Canny J (1986) A computational approach to edge detection. IEEE Trans Pattern Anal Mach Intell 8(6):679-698 PubMed Abstract
Cooley J, Tukey J (1965) An algorithm for the machine calculation of complex Fourier series. Mathematics of computation 19(90):297-301 Publisher Full Text
Marr D, Hildreth E (1980) Theory of edge detection. proc: of the royal society of London. Series B, Biological Sciences 207(1167):187-217 Publisher Full Text