Wednesday, August 31, 2016

On Detecting Signal Spikes with 1D HWT Wavelets: Part 1




Problem
  
Suppose that we have a 1D signal where we need to detect spikes, i.e., significant changes in signal values. Of course, what makes a given change significant is domain- or problem-dependent. 1D HWT can be used to detect spikes. In this post, I will write down a few thoughts on how one can define spikes conceptually. In the next post, I will detail a JAVA implementation of detecting spikes with 1D HWT. 





Sample Images & Signals

Let us take a look at a concrete image where spikes enable us to detect useful features. Fig. 1 gives an image of a road with two lanes. The original image has been grayscaled and blurred with Gaussian blur using a 7x7 window for denoising. We can take a 1D horizontal sub-signal from this image (or several such sub-signals) and use 1D HWT of that subsignal to detect spikes.

Figure 1. Sample road image
Fig. 2 gives a graphical representation of a subsignal. Specifically, the horizontal white line is a row from which a signal of 128 samples is taken at row 87 on the left of the image, i.e., from columns 0 to 127. The two vertical lines represent the beginning and the end of a spike detected over the left lane. Fig. 3 depicts another signal of 128 samples taken at the same row on the right side of the image and a spike detected over the right lane.


Figure 2. Signal of 128 samples from row 87

Figure 3. Signal of 128 samples from row 87






1D HWT Analysis of Signals for Spike Detection

Fig. 4 is an graph of grayscale values in the signal depicted as the horizontal line in Fig. 2

Figure 4. Graph of grayscale values of 128 sample signals in Fig. 2

If we apply 1 scale of 1D Ordered HWT to this signal, we get the graph shown in Fig. 5. The first 64 values represent a downsampled signal whereas the remaining 64 values are the corresponding Haar wavelet coefficients.


Figure 5. 1 scale of 1D HWT of the signal in Fig. 4


Figures 6 and 7 gives graphs of the two parts of Fig. 5, i.e., the downsampled signal and the corresponding wavelets.

Figure 6. Downsampled signal after 1 scale of 1D HWT of the signal in Fig. 4

Figure 8. Haar wavelets after 1 scale of 1D HWT of the signal in Fig. 4






Definition of Spikes

1D HWT wavelets can be used to detect spikes. Spikes can be broken into two broad categories: up-down spikes and down-up spikes. An up-down spike consists of three structural segments: an upward segment (signal samples increasing), a flat segment (signal samples remain more or less on the same level, i..e, neither increase or decrease), and a downward segment (signal samples decreasing). Similarly, a down-up spike also consists of three structural segments: a downward segment (signal samples decreasing), a flat segment (signal samples neither increasing nor decreasing), and an upward segment (signal samples increasing). In up-down and down-up spikes the flat segments are optional. A specific segment can be detected by analyzing values of 1D HWT wavelets similar to those given in Fig. 8. After a spike is detected, the exact coordinates of the segments can be used to locate a spike to the original signal, e.g., a 2D grayscale image. Detected spikes can subsequently be used to identify various objects in the original signal, i.e., road lanes.