## Wednesday, August 31, 2016

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

Problem

In my previous post, I jotted down a few thoughts on how 1D HWT can be used to detect spikes in signals. 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. In this post, I will outline a few details on how spike detection can be implemented in JAVA.

Spike Class

Below is a JAVA class that implements a spike. It breaks down a spike into three segments (runs) and keeps track of where each run starts and ends both in the wavelet sequences as well as the original signal. I have omitted the getters and setters as well as a few constructors.

public final class OneDHWTSpike {

private double mUpWaveCoeffThresh;            // threshold used to detect upward segments
private double mDownWaveCoeffThresh;       // threshold used to detect downward segments
private int    mNumIters;                                  // number of iterations/scales of 1D HWT
private int    mWaveLengthOfUpRun;              // length of upward run
private int    mWaveLengthOfDownRun;         // length of downward run
private int    mWaveStartOfUpRun;                 // where the upward run starts in the wavelet array
private int    mWaveStartOfDownRun;            // where the downward run starts in the wavelet array
private int    mWaveStartOfFlatRun;               // where the flat run starts in the wavelet array
private int    mWaveLengthOfFlatRun;            // length of the flat run
private int    mSigRowOrCol;                           // the original signal's row/col
private int    mSigRowOrColStart;                  //  the original signal's row/col start
private int    mSigRowOrColEnd;                     // the original signal's row/col end
private int    mSigStartOfUpRun;                    // where the upward run starts in the original signal
private int    mSigLengthOfUpRun;                 // the length of the upward run in the original signal
private int    mSigStartOfDownRun;               // where the downward run starts in the original signal
private int    mSigLengthOfDownRun;            // length of the downward run in the original signal
private int    mSigStartOfFlatRun;                  // where the flat run starts in the original signal
private int    mSigLengthOfFlatRun;               // length of the flat run in the original signal

// rest of code
}

Spike Detection

Below is my JAVA implementation of two methods: the first one implements a possible way to detect up-down spikes; the second one implements detection of down-up spikes. The methods detect spikes in sub-signals taken from rows in images. Column detection is identical.

The first two arguments are the original sub-signal and its 1D ordered HWT. The third argument specifies the number of iterations of 1D ordered HWT. The fourth argument specifies the row of the image from which the sub-signal is taken, the fifth and sixth arguments (sig_col_start and sig_col_end) specify the start and end columns of the sub-signal in the specified row. The arguments 7 - 12 implement the thresholds used in detecting spikes.

The arguments uwc_thresh and dwc_thresh are the thresholds for the HWT wavelets. HWT wavelets below these thresholds do not start up or down runs that constitute spikes. The arguments up_run_len_thresh, down_run_thresh threshold the lengths of the up and down runs, respectively. The arguments up_deg_angle_thresh and down_deg_angle_thresh threshold the angles of the up and down spikes, respectively. The up-down spikes are detected by detecting an up run, then a possible flat run, and then a down run. The down-up spikes are detected by detecting a down run, a possible flat run, and then an up run.

public static ArrayList<OneDHWTSpike>
detectUpDownSpikesInHWTOfRowSigSegmentByWaveDeg(
double[] row_sig_segment, double[] hwt,
int num_iters,
int sig_row, int sig_col_start, int sig_col_end,
double uwc_thresh, double dwc_thresh,
int up_run_len_thresh, int down_run_len_thresh,
double up_deg_angle_thresh, double down_deg_angle_thresh)

{
ArrayList<OneDHWTSpike> spikes = new ArrayList<>();

final int hwt_size = (hwt.length / (int) (Math.pow(2, num_iters)));
final int n = 2 * hwt_size;
int i = hwt_size;

int up_run_start   = -1;
int down_run_start = -1;
int flat_run_start = -1;
while ( i < n ) {

int j = i;
up_run_start = j;
while ( j < n ) {
if ( hwt[j] >= 0 ) { break; }
if (Math.abs(hwt[j]) < uwc_thresh) { break; }
j++;
}

int up_run_len = j - up_run_start;
if (up_run_len < up_run_len_thresh) {
up_run_start = -1; down_run_start = -1; i++;
continue;
}

// detect a flat run
flat_run_start = j;
while ( j < n ) {
if (Math.abs(hwt[j]) >= uwc_thresh || Math.abs(hwt[j]) >= dwc_thresh) { break; }
j++;
}

int flat_run_len = j - flat_run_start;
if (flat_run_len > 0) {
System.out.println("flat_run_len > 0;");
} else {
flat_run_start = -1;
}

if (j + down_run_len_thresh - 1 >= n) {
up_run_start = -1;
down_run_start = -1;
break; // outer while loop
}

down_run_start = j;
while ( j < n ) {
if (hwt[j] <= 0) { break; }
if (hwt[j] < dwc_thresh) { break; }
j++;
}

int down_run_len = j - down_run_start;

if (down_run_len < down_run_len_thresh) {
up_run_start = -1;
down_run_start = -1;
i++;
continue;
}

OneDHWTSpike spike = null;

if (flat_run_len > 0) {
spike = new OneDHWTSpike(sig_row,
sig_col_start,
sig_col_end,
uwc_thresh, dwc_thresh, num_iters,
up_run_start - hwt_size, up_run_len,
flat_run_start - hwt_size, flat_run_len,
down_run_start - hwt_size, down_run_len);

} else {
spike = new OneDHWTSpike(sig_row,
sig_col_start,
sig_col_end,
uwc_thresh, dwc_thresh, num_iters,
up_run_start - hwt_size, up_run_len,
down_run_start - hwt_size, down_run_len);
}
i = j + 1;
}

return spikes;
}

public static ArrayList<OneDHWTSpike>
detectDownUpSpikesInHWTOfRowSigSegmentByWaveDeg(
double[] row_sig_segment, double[] hwt, int num_iters,
int sig_row, int sig_col_start, int sig_col_end,
double uwc_thresh, double dwc_thresh,
int up_run_len_thresh, int down_run_len_thresh,
double up_deg_angle_thresh, double down_deg_angle_thresh)

{
ArrayList<OneDHWTSpike> spikes = new ArrayList<>();

final int hwt_size = (hwt.length / (int) (Math.pow(2, num_iters)));
final int n = 2 * hwt_size;
int i = hwt_size;

int up_run_start   = -1; int down_run_start = -1; int flat_run_start = -1;
while (i < n) {
int j = i; down_run_start = j;
while ( j < n ) {
if (hwt[j] >= 0) { break; }
if (Math.abs(hwt[j]) < dwc_thresh) { break; }
j++;
}

int down_run_len = j - down_run_start;
if (down_run_len < down_run_len_thresh) {
down_run_start = -1;
up_run_start = -1;
i++;
continue;
}

// detect a flat run
flat_run_start = j;
while ( j < n ) {
if (Math.abs(hwt[j]) >= uwc_thresh || Math.abs(hwt[j]) >= dwc_thresh) { break; }
j++;
}
int flat_run_len = j - flat_run_start;
if (flat_run_len > 0) {
System.out.println("flat_run_len > 0;");
} else {
flat_run_start = -1;
}

if (j + up_run_len_thresh - 1 >= n) {
up_run_start = -1;
down_run_start = -1;
System.out.println("j + up_run_len_thresh >= n");
System.out.println("no more spikes");
break; // outer while loop
}

up_run_start = j;
while (j < n) {
if (hwt[j] <= 0) { break; }
if (hwt[j] < uwc_thresh) { break; }
j++;
}

int up_run_len = j - up_run_start;

if (up_run_len < up_run_len_thresh) {
up_run_start = -1;
down_run_start = -1;
i++;
continue;
}

OneDHWTSpike spike = null;

if (flat_run_len > 0) {
spike = new OneDHWTSpike(sig_row, sig_col_start, sig_col_end,
uwc_thresh, dwc_thresh, num_iters,
up_run_start - hwt_size, up_run_len,
flat_run_start - hwt_size, flat_run_len,
down_run_start - hwt_size, down_run_len);

} else {
spike = new OneDHWTSpike(sig_row, sig_col_start, sig_col_end,
uwc_thresh, dwc_thresh, num_iters,
up_run_start - hwt_size, up_run_len,
down_run_start - hwt_size, down_run_len);
}

// a spike filter can be added to detect the strength of spikes
i = j + 1;
}
return spikes;
}