Abstract
This paper extends the scaleinvariant edge detector to the onedimensional 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 contrastinvariant operator is proposed to suppress noise. The intersample localization and interpolation greatly improve the accuracy. The proposed slope detector is also suitable for realworld signals. In additional to abovementioned, a threshold formula is developed for the first derivative slope detector, and the upperbound of the filterable noise level is also explored.
Keywords:
Slope; Gaussian; Threshold; Error function; Subsample; Localization; Interpolation; Noise suppression; The first derivative operatorIntroduction
This paper concerns the slope detection of onedimensional discrete signals (Oppenheim and Willsky 1983). The onedimensional slope detection shares some common problems (e.g. noise suppression, threshold selection) with the twodimensional 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 onedimensional 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 scaleinvariant edge detector (Zhang and Liu 2013).
Although twodimensional edge detection is a wellestablished subject, however, it seems that the slope of onedimensional 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 contrastinvariant 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 scaleinvariant edge detector can address the issue by automatically choosing the adequate scale for each edge feature. This research extends the technique to the onedimensional slope detection. Because of the apparent distinction between the one dimensional and the two dimensional signals, the scaleinvariant edge detector is adjusted for the slope with additional functions of intersample localization and interpolation. The proposed method is suitable for several broad classifications of signals: noisy and noiseless, periodic and nonperiodic, densely and sparsely sampled.
One dimensional slope detection
Signal representation
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 x_{0}, 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 x_{0}, 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 closedform, further investigation can be carried out.
Scale and spatial detector
The Lx operator is used in this paper to denote the scalenormalized derivative of L with respect to x (Equation 7). The scalenormalization is necessary for a scaleinvariant 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 scalenormalized 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.
Parameter estimation
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 presmoothing operation with a small scale is required. The presmoothing scale is removed from the detected scale, results in the width.
Intersample localization and interpolation
Directly applying the method of continuous functions will produce noticeable errors for discrete signals. Subpixel localization can be applied to threedimensional 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 intersample 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 intersample 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.
Implementation
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 intersample 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, presmoothing operation is not performed for the parameter estimation experiment.
Table 1. Implementation configuration
Noise suppression
It is wellknown 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 scaleinvariant detectors (instead of L_{x}). Therefore the following paragraphs deduce the threshold of L_{x} for a presmoothing scale.
The threshold of the first derivative operator
The first derivative of the smoothed ideal slope at the location of x_{0} can be obtained using Equation 21, where the σ is the presmoothing scale.
If the minimum and maximum values are denoted by subscript m and M, then the low and high threshold of the L_{x} detector are represented by T_{m} and T_{M} (Equation 22). The T_{M} and the first component of T_{m} filter slopes whose contrast is within the range of c_{m} and c_{M}, and the width within w_{m} and w_{M}. A noise can be filtered out by the second component of T_{m}, if the standard deviation (std^{n}) and mean (mean^{n}) 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 w_{m}^{n} (a small value, e.g. 0.5). If the second component of T_{m} is smaller than the first component, then all slopes within the range are detectable. If the second component of T_{m} is between the first one and T_{M}, 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 T_{m} should be no more than T_{M} (equation 23). An upper bound of the filterable noise is achieved with an infinite large presmoothing 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 L_{x} detector uses the thresholds (T_{m} and T_{M}) to filter out noise. The errors of L_{x} 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 L_{x }detector for the noisy ideal slopes, without considering noise threshold
Table 4. RMSD of positional errors of the L_{x }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 subsection 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, presmoothing scale and T_{m}are 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 (mean^{n}) and random standard deviations (std^{n}), Table 6 lists the percentages of Lxs/Lx at three intervals under two conditions. The first condition is four presmoothing 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 presmoothing scale, leading to a lower contrast threshold. The noise is completely removed by presmoothing scale 1 and contrast threshold of 6 times standard deviation. The experiment shows that the noise can be suppressed by the following procedures: presmoothing 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
Experimental
Quantitative experiments
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 x_{0}.
The positional error (e_{x}) 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 q_{0}:
The root mean squared deviation (RMSD) of the error is given by
where e^{n} is the nth actual error and ϵ^{n} is assumed to be zero.
The step slopes are presmoothed 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 intersample 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, presmoothing scale 0
The following experiments use the RMSD of the positional error to evaluate the performances. Except ramp slope, L_{x} produces similar errors for several slope functions (Table 8). The L_{x} of ramp is a constant; therefore a local extremum can not be found at the slope center. It can be verified that if L_{x} is implemented by a central difference, then a presmoothing is required for step slopes.
Table 8. RMSD of positional errors of the L_{x }detector for the ideal slopes
The proposed method achieves lower error because of the intersample localization (Table 9). A presmoothing 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 zeromean Gaussian noise. For the experiment of Table 10, the presmoothing 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 (T_{m}) 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 L_{x} (Table 3) will be more sensitive to noise than the proposed method (Table 11). Even for low level noise, L_{x} needs large presmoothing 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 presmoothing scale. For a large presmoothing 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 L_{x}(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 L_{x }detector for the sparsely sampled ideal slopes
Some qualitative examples
A few slopes of periodic signals are displayed in Figure 7, where the signaltonoise 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.
Conclusion
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 scalenormalization. Using an error function as a test slope, the parameters are solved for precisely in closed form. A precise intersample localization and interpolation procedure is proposed to improve the accuracy. The method can extract slopes from synthesized or realworld signals while detecting less noise than its counterpart methods. Based on mathematical functions, the threshold selection of the first derivative is also discussed.
Competing interests
The authors declare that they have no competing interests.
Authors’ contributions
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.
Acknowledgements
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).
References

Bansal B, Sain J, Bansal V, Kaur G (2012) Comparison of various edge detection techniques. Journal Of Information And Operations Management 3(1):103106

Brown M, Lowe DG (2002) Invariant features from interest point groups. In British Machine Vision Conference, Cardiff, Wales. pp 656665

Canny J (1986) A computational approach to edge detection. IEEE Trans Pattern Anal Mach Intell 8(6):679698 PubMed Abstract

Cooley J, Tukey J (1965) An algorithm for the machine calculation of complex Fourier series. Mathematics of computation 19(90):297301 Publisher Full Text

Lowe D (2004) Distinctive image features from scaleinvariant keypoints. Int J Comput Vis 60(2):91110

Marr D, Hildreth E (1980) Theory of edge detection. proc: of the royal society of London. Series B, Biological Sciences 207(1167):187217 Publisher Full Text

Oppenheim A, Willsky A (1983) Signals and systems. PrenticeHall Englewood Cliffs, NJ.

Pinho A, Almeida L (2012) A review on edge detection based on filtering and differentiation. Electrónica e Telecomunicações 2(1):113126 PubMed Abstract  PubMed Central Full Text

http://www.mathworks.com/matlabcentral/fileexchange/18458historicalstockdata downloader webcite

Witkin A (1983) Scalespace filtering. 8th Int. Joint Conf: Artificial Intelligence 2:10191022

Zhang X, C Liu C (2013) An ideal image edge detection scheme. Multidim Syst Sign Process.
doi: 10.1007/s1104501302249