Quality software development
using mathematically-inspired methods

Provably superior software

QEDDecoderMetric Case Study

In the early development of QEDDecoderMetric, a functional decoder was required to fully exercise the capabilties of the test suite. After some investigation, the open-source package ZBar was chosen to act as the test decoder.

Visiting the above link, downloading version 0.10 of the source code, and integrating it into QEDDecoderMetric, the source compiled with no changes. Running a small database of a few dozen Code 39 images resulted in zero decodes. After QEDDecoderMetric generated hundreds of additional images, then a small handful decoded.

With the decoder now working, the full set of 19 sensitivity tests was run on the Code 39 sample barcode. The resulting full set of graphs can be seen here.

To interpret the graphs, a red dot indicates the presence of a misdecode - an incorrectly decoded result. A large green dot indicates a large percentage (greater than 95%) of barcodes with the given parameters decode. A medium sized green dot indicates a medium percentage (50% - 95%) of barcodes with the given parameters decode. A small green dot indicates a low percentage (10% - 50%) of barcodes with the given parameters decode. The absence of a green dot indicates that fewer than 10% of those barcodes decode.

The set of graphs contains a large amount of information. What is clear, is that for the majority of the graphs, decode strength is weak, as is evidenced by small dots or no dots in most locations.

Upon examining the graphs, three clearly show that there exist conditions under which the decoder is able to decode well: Blur vs SNR, SNR vs SNR Balance, and White vs MRD. Examination of these three graphs will yield some significant insights.

Please note that the red dots (indicating misdecodes) have been removed from the following graphs as they will only serve as a distraction at this point in time.

Blur vs SNR
The purpose of the above graph is to diplay the relationship that SNR and blur values have on the ability of a given image to be decoded.

The graph tells a valuable story. Given that all of the large dots are to the right of the rightmost red line, this means that the decoder is only able to decode images with SNR values of 26 dB and greater.

As most decoders are able to decode in the presence of SNR values of approximately 10 dB or greater (a level corresponding to the leftmost red line), we now conclude that ZBar is very sensitive to noise.

Furthermore, all of the other sensitivity tests that do not have SNR as one of its axes use an SNR value of 20 dB, which corresponds to the expected noise level of an average quality image. Given that the above graph demonstrates that a level of 20 dB is on ZBar's threshold of decodability, it is now of little surprise that most graphs demonstrate weak decoding.

SNR Balance
The purpose of the above graph is to demonstrate the decoder's sensitivity to conditions where the noise is primarily present in the black areas of the image (negative values of balance), or white areas of the image (positive values).

To interpret the graph, an SNR balance of zero indicates that noise is present in equal amounts in both the black and white areas of the image. A balance value of negative one represents the case where only black areas have noise, while the white areas are noiseless. A balance value of positive one represents the case where only white areas have noise, while the black areas are noiseless.

What is evident, is that the decoder is very sensitive to noise in the white areas of the image.

White versus MRD
The purpose of the above graph is to demonstrate the decoder's ability to decode images with various brightness and contrast levels with a fixed noise level of 20 dB.

The graphs shows a characteristic that is usually indicative of a weakness in a decoder. In this case, we have a region of large dots, corresponding to a high probability of decode. However, inside of this region, there exists an area of lower probability of decode, namely that area within the red outline.

Note that the White vs MRD graph shows that even at an SNR value of 20 dB, decoding is possible for darker images (lower white levels), lower contrast images (lower MRD), and saturated images (white levels in excess of 255).

The fact that saturated images decode well should be expected given the SNR balance will be negative in these cases (noise only present on black elements as white elements saturate at 255).

The common characteristic of darker images and lower contrast images is that the absolute magnitude of the noise is lower. This would tend to imply that once noise (in particular, noise on white) exceeds a fixed threshold, decoding is not possible.

Examining the source code, it was found that a fixed-value minimum edge size was used to indicate the presence of an edge. The code was modified to use a two pass algorithm where the minimum edge size is set to a fixed ratio of the maximum edge size, with a fixed minimum (equal to the original threshold).

The full set of graphs after having applied the candidate fix can be seen here. It is readily evident that the decode rate of the proposed modification is significantly better than the original code.

While it is clear that the decode performance has been greatly improved, there exist a number of remaining deficiencies.

There is a very large number of red dots on all of the graphs, indicating misdecoded results. In general, returning an incorrect result is viewed as considerably worse than returning no result. This is a very serious weakness of the code.

Roll angles other than vertical and horizontal
It is quite evident that ZBar is unable to decode barcodes unless the bars are precisely vertical or horizontal. In many environments, it is not possible to guarantee such orientation, making this a very serious flaw.

Blur limit
The code, as it stands, is not able to withstand more than 1.8 modules of blur. Experience has shown that binary codes are able to withstand 3.0 modules of blur, making the existing decoder much weaker than competing decoders.

PPM limit
The decoder appears to be unable to decode barcodes with fewer than 1.1 pixels per module present. It is known that lower values are reliably decodable.

SNR limit
The decoder appears to experience difficulties when decoding at SNR levels  under 13 dB. Experience has shown that levels of 0 dB may be reliably decoded.

If the margin present is less than 7 modules, the decoder does not decode. While this may be prudent in a laser-based application, in an image-based one, where full 2D information is available, a significantly smaller margin may be reliably used. This is important since not all barcodes are printed with the required margin.

While there exist other shortcomings, the preceding list is a good starting point for tuture improvements to the ZBar decoder.
Copyright 2013 QEDWare