Signal Denoising Using Otsu's Algorithm on Peak Strengths
The following barcode denoising technique was developed by Stephen Shellhammer, David Goren, and Theo Pavlidis of Symbol Technologies (IEEE Robotics & Automation Magazine, March 1999). This method works off the first derivative signal, which should be a series of spikes alternating in sign. First, a "selective sampling" stage picks out the location of the the maxima / minima of the signal. This is appropriate since we are trying to loacte edges (jumps). Second, a histogram of the peak strengths is prepared (in absolute value). Finally, a threshold is established by Otsu's Algorithm, which chooses a dividing point that minimizes the sum of the variances of the two groups. That is, Otsu's Algorithm looks for a "gap" in the histogram.

This thresholding method is shown below on an actual barcode derivative signal (sig2a5cm_8). The first plot shows the original derivative signal. The second plot is a stem plot of the signal after selective sampling. Note the size of the signal has been reduced by a factor of 6. The third plot is the histogram of the peak strengths. The red vertical line is the threshold found by Otsu's Algorithm at 0.84357. The red lines on the fourth plot show the thresholds at +/- 0.84357. As can be seen in the last plot, the method failed to produce alternating spikes throughout. The pictures were produced by the program otsu.m with the calls "load sig2a5cm_8.txt" and "[s,u] = otsu (sig2a5cm_8')". Shellhammer et. al describe in the paper how to incorporate the Gaussian mentioned in the previous section.

Back to Main Page Next: The TV Norm