The results of descent.m on test barcodes generated by make_noisy.m are promising. In order for the algorithm to have any hope of finding the correct barcode, the signal cannot be too noisy. In particular, the value of the Gaussian width w needs to be small enough for the bars to be distinct. Ideally, the Gaussian should have width smaller than the width of the narrowest bar.

A barcode signal of just two humps was convolved with a Gaussian of width w =0.1. A small amount of noise was added using make_noisy.m. This signal h was fed as input and is shown below in green. The program descent.m was run for 1,000 iterations on this signal. The convolution b*g, shown in blue in the top plot, matches the noisy h as well as a smooth curve can. The final result b is shown in the bottom plot in blue. It matches the original clean barcode, in red, fairly well. The program found w =0.08426. Running the program for more iterations should refine the signal b.

The same two hump barcode signal was then convolved with a Gaussian of width w =0.25 and noise was added. Again, the program was run for 1,000 iterations. In the top plot, h is shown in green and b*g is shown in blue. In the bottom plot, the original two hump barcode is plotted in red and the output signal b is shown in blue. Note this signal was too noisy for the program to realize that there were two small humps instead of one large hump, even though the curves in the top plot match reasonably well. The program found w =-0.087714, which is too far from the correct value of 0.25.

To test the steepest descent method on a realistic signal, we generated the UPC barcode '0123456789' using upc2signal.m. We convolved this clean step signal with a Gaussian of width w =0.02 and added random perturbations using make_noisy.m. The program descent.m was run for 1,000 iterations, which is probably not enough time for a complicated signal such as this. The top plot shows the noisy input signal h in green and the convolution b*g in blue. The bottom plot shows the output b in blue and the original clean barcode signal in red. If we were to threshold the blue signal b at 0.5, it would match the original red signal fairly well. However, at least two humps would be omitted, such as the hump on the far left. The program found w =-0.0180192, which is close to the correct value 0.02 in absolute value. Unfortunately, running the program for 10,000 iterations did not seem to pick up the missed humps.

There are a few refinements that need to be made to this steepest descent approach. First, the value of the constant k and its dependence on the vector length N needs to be determined. The minimization over the Gaussian amplitude a should be incorporated. This should be a reasonably simple addition to the code, but we omitted it for simplicity so we could concentrate on the more important values of b and w. Perhaps giving separate step sizes to the variables b, a and w would improve the optimization.

Back to Main Page