PDF417 updates, java

[Guenther Grau]

Hi all,

I started to work on PDF417 improvements a while a go, but was interrupted by other urgent work. Last weekend I finally found the time to at least create a version that can decode all zxing PDF417 test images. Work is far from complete and it's not ready to be committed into the zxing repository yet, but if someone needs support for Compact PDF417 and/or Macro PDF417, it might be a good starting point.

I've cloned the official ZXing git repo on github and made my changes available in https://github.com/graug/zxing.

Best regards,

  Guenther

[Sean Owen]

That's great, let me know when it's close enough to commit. I can manage fitting it exactly back into the main branch from a rough patch.

[Christoph Schulz]

Am Montag, 8. April 2013 11:10:27 UTC+2 schrieb Guenther Grau:

I started to work on PDF417 improvements a while a go, but was interrupted by other urgent work. Last weekend I finally found the time to at least create a version that can decode all zxing PDF417 test images. Work is far from complete and it's not ready to be committed into the zxing repository yet, but if someone needs support for Compact PDF417 and/or Macro PDF417, it might be a good starting point.

Have you compared your changes to this PDF417 patch and/or tested these pdf417-3 files? Just curious.

It's back port from our C++ changes (not merged into trunk, yet. See my pdf417 branch). We didn't do much to the decoder (just simplifications). The biggest improvement was achieved by "guessing" codewords using squared error reduction during detection (LinesSampler.java). As a result the decoder gets a pretty perfect barcode, even if the barcode was printed with a needle printer on low ink (I really should submit a test case for that). It's even beating ClearImage in several cases, though it can't deal with barcodes that are cut in half (ec level 8). That's because the detector can't compensate for missing guard patterns or "shifted" barcode rectangles.

Your approach looks quite similar, without looking at details ("ScanningDecoder" roughly equals "LinesSampler"?). I'm interested in this because our approach is quite heavy performance wise, but it's capable of guessing information that can't be restored by normal error correction.

Regards,
Christoph

[Guenther Grau]

Hi Christoph,

On Monday, April 8, 2013 8:33:06 PM UTC+2, Christoph Schulz wrote:

Am Montag, 8. April 2013 11:10:27 UTC+2 schrieb Guenther Grau:

I started to work on PDF417 improvements a while a go, but was interrupted by other urgent work. Last weekend I finally found the time to at least create a version that can decode all zxing PDF417 test images. Work is far from complete and it's not ready to be committed into the zxing repository yet, but if someone needs support for Compact PDF417 and/or Macro PDF417, it might be a good starting point.

Have you compared your changes to this PDF417 patch and/or tested these pdf417-3 files? Just curious.

No, I haven't compared it to the mentioned PDF417 patch. I last looked at the official ZXing java code about one and a half month ago, so I haven't even seen what the latest code looks like (there have been a few pdf417 related commits around end of March). I plan to look at the current code and will also look at your patch to compare ideas and implementations. :-)

I tested my changes against all pdf417 test files. I manages to detect all of them correctly if my binarizer is used. When using the default HybridBinarizer, a few test cases in pdf417-2 fail. I will have a look at these later.
My binarizer is extremely simple and currently only works for greyscale or black and white images. It uses a single black point for the whole image. If no valid barcode can be decoded for a blackpoint, the code simply changes to a blackpoint nearby and tries the detection again. It takes a bit longer, if no barcode can be found, but usually it's very fast. I'll do performance measurements once I'm happy with the detection rate. Btw., it doesn't need to create a black and white copy of the image bitmap. It simply compares the original image pixel with the blackpoint, so the performance is faster for the detection case and slower when doing several blackpoint adjustment iterations.
I might create a separate discussion about the binarizer later, as it requires a few changes in the zxing common code.
 

It's back port from our C++ changes (not merged into trunk, yet. See my pdf417 branch). We didn't do much to the decoder (just simplifications). The biggest improvement was achieved by "guessing" codewords using squared error reduction during detection (LinesSampler.java). As a result the decoder gets a pretty perfect barcode, even if the barcode was printed with a needle printer on low ink (I really should submit a test case for that). It's even beating ClearImage in several cases, though it can't deal with barcodes that are cut in half (ec level 8). That's because the detector can't compensate for missing guard patterns or "shifted" barcode rectangles.

 

My changes initially also focused on "guessing" codewords. I analyzed a lot of barcode images came up with a quite complicated algorithm, which is implemented in PDF417CodewordDecoder.java and AdjustmentResult.java. In addition to this "manual" adjustment of bits, I also implemented a version, which tries more accurate sampling based on floating point width of the black and white bars. (AdjustmentResultFloat.java) This was a big improvement. The final (so far :-) change was to return a second codeword which has the two bits flipped, that are closest to a sampling coordinate between two bars. With this change, all tests can be decoded correctly.

Currently I'm looking into detection problems where black bars are wider than white bars. I have to deal with black and white scans, where the scanner has the "wrong" blackpoint :-(

If I remember correctly, the current code transforms the image to a normalized rectangle, create row sum averages and tries to decode these. I found that the transformation caused a lot of misdetected pixels, so I tried a version which works by scanning the original image line by line. This works fine for all test barcodes. It will fail, however, if the barcode is rotated too much. This is a low priority problem for me, as the barcodes I'm dealing with are at most very slightly rotated.

My code currently does not sum up several rows to get a more reliable value. Instead it counts the number of detected values for a single codeword and uses the one with the highest count that matches the row number. This doesn't work well if the image has a lot of sporadic pixel errors. I already have some ideas on how fix that, but ill look into this later.

When scanning line by line, I found it very important to get the correct start and end position of a codeword right and to know what row the codeword is in (for skewed, rotated and especially damaged images). Initially, I tried calculating the start and end positions while decoding, but this didn't work well. My current solution is twofold. First I remember the start and end positions for all detected codewords, second, I scan column by column. This made detection of codeword start and endpoints very reliable.

To know which row a codeword belongs to is important in case of damaged images or other decoding problems. Initially, I tried to set this information during decoding but found it not reliable enough. Now I simply remember the detected codeword value for each row and do the codeword line numbering when I have the complete "picture" ;-) This implementation is not yet complete, but works reasonably well.

I had a few barcodes where decoding a few values contradicted other decoded information and wasn't sure how to tell which is the correct information. I fixed that by first reading the left row indicator column completely. It contains the important meta data several times which makes it the most reliable source. Using information from that column also allows me to deal with Compact PDF417 and damaged normal PDF417 missing columns on the right. I haven't implemented dealing with a missing left row indicator column yet, but it would be fairly easy to do.
 

Your approach looks quite similar, without looking at details ("ScanningDecoder" roughly equals "LinesSampler"?). I'm interested in this because our approach is quite heavy performance wise, but it's capable of guessing information that can't be restored by normal error correction.

I haven't done any performance measurements or optimizations yet. Curious about your code now and will look at it :-)

 Best regards,

  Guenther

[Christoph Schulz]

Am Montag, 8. April 2013 22:16:06 UTC+2 schrieb Guenther Grau:

Have you compared your changes to this PDF417 patch and/or tested these pdf417-3 files? Just curious.

No, I haven't compared it to the mentioned PDF417 patch. I last looked at the official ZXing java code about one and a half month ago, so I haven't even seen what the latest code looks like (there have been a few pdf417 related commits around end of March). I plan to look at the current code and will also look at your patch to compare ideas and implementations. :-)

We've tested today with ZXing's test suite and 16 of our "nasty real life" barcodes. I have to say: I'm impressed by your solution's performance. It misses 1 out of our 16 barcodes (very crippled lines, very hart to define "bar dots"). Can't share it for privacy reasons (medical records) :(

When using the default HybridBinarizer, a few test cases in pdf417-2 fail. I will have a look at these later.

Random guess: the HybridBinarizer "punches" holes into large pixel segments... its quite hacky and there already was a topic about this in late 2012/early 2013 (Hartmut Neubauer was involved in that discussion).

Currently I'm looking into detection problems where black bars are wider than white bars. I have to deal with black and white scans, where the scanner has the "wrong" blackpoint :-(

At some point we stopped thinking of bar widths as percentage or seats in a vote. Instead we started thinking about it as "distance to a valid to codeword". Maybe it helps, if you can't get raw data from your scanner to compute white balance yourself.

Thanks for your explanation.
We fixed bad pixels resulting form transformation by oversampling the barcode along with a majority vote on codewords across multiple lines. Oversampling is required to prevent bad codewords from getting too many seats in the vote.

Regards,
Christoph

[Guenther Grau]

Hi Christoph,

On Tuesday, April 9, 2013 4:35:39 PM UTC+2, Christoph Schulz wrote:

Am Montag, 8. April 2013 22:16:06 UTC+2 schrieb Guenther Grau:

Have you compared your changes to this PDF417 patch and/or tested these pdf417-3 files? Just curious.

No, I haven't compared it to the mentioned PDF417 patch. I last looked at the official ZXing java code about one and a half month ago, so I haven't even seen what the latest code looks like (there have been a few pdf417 related commits around end of March). I plan to look at the current code and will also look at your patch to compare ideas and implementations. :-)

We've tested today with ZXing's test suite and 16 of our "nasty real life" barcodes. I have to say: I'm impressed by your solution's performance. It misses 1 out of our 16 barcodes (very crippled lines, very hart to define "bar dots"). Can't share it for privacy reasons (medical records) :(

Is your code able to decode all of the nasty real life barcodes?
It think there is still quite a bit of room for improvement on the detection of "bad" barcodes. At least, I've quite a few ideas on how to improve it. If I only had the time and someone to pay me for it :-) Glad to hear that you are happy with the performance. As I said before, so far I haven't done any performance analysis or tuning. It think it can be made even faster in a few areas. The most obvious being, that I need a better blackpoint detection instead of hardcoding it to some random value. Sean will be happy to read this, because he was worried about bad performance when I proposed my initial changes (which I withdrew shortly thereafter, as they had consequences on other parts of zxing). What target environment are you running the detection on? PCs, servers, mobile or embedded devices?

I don't need the whole barcode, but it would be _really_ nice if you could cut out a small portion of the undetected image, so I can get a grasp of the nature of the barcode. Is the barcode straight and square or heavily distorted, rotated, skewed and/or damaged? Does it find the start and stop patterns properly? Once I have a little more information and a sample, I could add some log information to the code for you to run, which would give me some ideas about why it's not detected, without revealing information to me.

When using the default HybridBinarizer, a few test cases in pdf417-2 fail. I will have a look at these later.

Random guess: the HybridBinarizer "punches" holes into large pixel segments... its quite hacky and there already was a topic about this in late 2012/early 2013 (Hartmut Neubauer was involved in that discussion).

Haven't really looked into that at all. I have no idea what the HybridBinarizer is doing and why. I just wanted to focus on the detection of the raw image first.
 

Currently I'm looking into detection problems where black bars are wider than white bars. I have to deal with black and white scans, where the scanner has the "wrong" blackpoint :-(

At some point we stopped thinking of bar widths as percentage or seats in a vote. Instead we started thinking about it as "distance to a valid to codeword". Maybe it helps, if you can't get raw data from your scanner to compute white balance yourself.

I started to read your code (LineSampler), but I haven't had time to go through it completely. (BTW., what are those resize[1,4]() methods at the end of the class doing? They look weird at first glance :-))

 

Thanks for your explanation.
We fixed bad pixels resulting form transformation by oversampling the barcode along with a majority vote on codewords across multiple lines. Oversampling is required to prevent bad codewords from getting too many seats in the vote.

I had a go at oversampling as well, but it didn't really achieve the results I wanted, despite throwing a lot of computing and memory resources at it. It certainly does improve things, but only to a certain extend. It think the transformation introduces rounding errors which results in loss of information, which just cannot be compensated anymore. You lose even more information when the transformation changes the width of the modules.
Another problem with the transformation is that it is quite indeterministic from a development and error analysis point of view. You never know what a barcode will look like after the transformation. Therefore it's really hard to adjust the code to overcome a certain detection problem. That was another reason why I chose to implement detection on the raw image. If I need to do transformation, I can still do it when detecting on the image.

Best regards,

  Guenther

[Guenther Grau]

Hi Christoph,

with regard to the failing test image: Maybe you can use a paint tool to color the middle of the barcode black, leaving only the start and end pattern, the left and right row indicator columns and the last four code words in the last barcode row. These portions of the barcode contain only PDF417 meta data and no actual content.

Best regards,

  Guenther

P.S.: After reading your second post again, I think I misread you remark about the performance in this one. I think you were referring to the detection rate rather then performance, right?

[Christoph Schulz]

Is your code able to decode all of the nasty real life barcodes?

We havn't found a any PDF417 that doesn't get decoded properly when corner vertices are detected correctly (unless the physician done some inking/stamping/bood/etc. to the barcode).
 

What target environment are you running the detection on? PCs, servers, mobile or embedded devices?

We're using desktop clients (scanner with a document feeder + low cost pc, no ZXing here) and a server setup with distributed workers (see node-dv, this contains ZXing). It's has to be this way, because the sheer number of scans is several thousand per day in very few hours.

I don't need the whole barcode, but it would be _really_ nice if you could cut out a small portion of the undetected image, so I can get a grasp of the nature of the barcode.

See attachment. I've cropped the barcode. One of my collegues looked today into this and told me that the problem might be about brightness. Both codes are EC Level 4, so they _should_ have no problem with imprinted dates.

I started to read your code (LineSampler), but I haven't had time to go through it completely. (BTW., what are those resize[1,4]() methods at the end of the class doing? They look weird at first glance :-))

It's ported from C++ within 2 days, feel free to refactor, if it's not Java-ish enough :). As allocation of memory is heavy std::vector<>::resize() is a neat trick to prevent the vector from reallocating (note: it does reallocate in steps, not on every push_back()). At the very end resize is used to crop the vector.

Regards,
Christoph

[Guenther Grau]

Hi Christoph,

On Wednesday, April 10, 2013 3:51:31 PM UTC+2, Christoph Schulz wrote:

Is your code able to decode all of the nasty real life barcodes?

We havn't found a any PDF417 that doesn't get decoded properly when corner vertices are detected correctly (unless the physician done some inking/stamping/bood/etc. to the barcode).

So the problem with pdf417-3/10.png is not being decoded by your code is incorrect detection of the corner vertices?
 

What target environment are you running the detection on? PCs, servers, mobile or embedded devices?

We're using desktop clients (scanner with a document feeder + low cost pc, no ZXing here) and a server setup with distributed workers (see node-dv, this contains ZXing). It's has to be this way, because the sheer number of scans is several thousand per day in very few hours.

Sounds like an interesting project. I looked at your code a little more. Doing the squared error reduction for all 2787 potential codewords against each detected codeword seems to be the compute intensive part, right? You could cut this by 3 if you knew what line you are on, but it's tough to know in advance what line you are on, when decoding damaged barcodes :-(
 

I don't need the whole barcode, but it would be _really_ nice if you could cut out a small portion of the undetected image, so I can get a grasp of the nature of the barcode.

See attachment. I've cropped the barcode. One of my collegues looked today into this and told me that the problem might be about brightness. Both codes are EC Level 4, so they _should_ have no problem with imprinted dates.

Great, thanx for sharing! They do look a bit more challenging and would make for really good test cases :-) Hard to guess by the naked eye what codes where actually meant. Will see what I can do about these :-)
 

I started to read your code (LineSampler), but I haven't had time to go through it completely. (BTW., what are those resize[1,4]() methods at the end of the class doing? They look weird at first glance :-))

It's ported from C++ within 2 days, feel free to refactor, if it's not Java-ish enough :). As allocation of memory is heavy std::vector<>::resize() is a neat trick to prevent the vector from reallocating (note: it does reallocate in steps, not on every push_back()). At the very end resize is used to crop the vector.

I still haven't read your code completely, so I don't know why you need to resize various lists, but the methods don't do what I think they are suppose to do. E.g., if the size of the list is 57 and you call it with the new size 50, after the call, the list will have the size 53 and not 50.

  private static void resize3(List<List<Integer>> list, int size) {
    // Delete some
    for (int i = size; i < list.size(); i++) {
      list.remove(i);
    }
    // Append some.
    for (int i = list.size(); i < size; i++) {
      list.add(new ArrayList<Integer>());
    }
  }
 
I guess it's just a minor detail. I was just wondering about it.

Best regards,

  Guenther

[Christoph Schulz]

Am Mittwoch, 10. April 2013 17:31:59 UTC+2 schrieb Guenther Grau:

Hi Christoph,

On Wednesday, April 10, 2013 3:51:31 PM UTC+2, Christoph Schulz wrote:

Is your code able to decode all of the nasty real life barcodes?

We havn't found a any PDF417 that doesn't get decoded properly when corner vertices are detected correctly (unless the physician done some inking/stamping/bood/etc. to the barcode).

So the problem with pdf417-3/10.png is not being decoded by your code is incorrect detection of the corner vertices?

Most likely, yes. Its readable after all by ClearImage.

Sounds like an interesting project. I looked at your code a little more. Doing the squared error reduction for all 2787 potential codewords against each detected codeword seems to be the compute intensive part, right? You could cut this by 3 if you knew what line you are on, but it's tough to know in advance what line you are on, when decoding damaged barcodes :-(

If I remember correctly the hamming distance is too small for unambigous inference Reducing the amount of searching would greatly enhance performance (e.g. don't search from start, search in one of three lists, ...). About being though to know while reading: voting isn't done on the fly. It's done after all potential codewords are read. This could be a starting point :)

I still haven't read your code completely, so I don't know why you need to resize various lists, but the methods don't do what I think they are suppose to do. E.g., if the size of the list is 57 and you call it with the new size 50, after the call, the list will have the size 53 and not 50.

It's best not to think about this (really). I'd love to refactor this myself someday. Its more or less a bad habit to use multidimensional arrays like that instead of objects when designing algorithms and I'm glad that Martin Folwer doesn't read this :P

[Guenther Grau]

On Wednesday, April 10, 2013 6:11:04 PM UTC+2, Christoph Schulz wrote:

Am Mittwoch, 10. April 2013 17:31:59 UTC+2 schrieb Guenther Grau:

Hi Christoph,

On Wednesday, April 10, 2013 3:51:31 PM UTC+2, Christoph Schulz wrote:

Is your code able to decode all of the nasty real life barcodes?

We havn't found a any PDF417 that doesn't get decoded properly when corner vertices are detected correctly (unless the physician done some inking/stamping/bood/etc. to the barcode).

So the problem with pdf417-3/10.png is not being decoded by your code is incorrect detection of the corner vertices?

Most likely, yes. Its readable after all by ClearImage.

Sounds like an interesting project. I looked at your code a little more. Doing the squared error reduction for all 2787 potential codewords against each detected codeword seems to be the compute intensive part, right? You could cut this by 3 if you knew what line you are on, but it's tough to know in advance what line you are on, when decoding damaged barcodes :-(

If I remember correctly the hamming distance is too small for unambigous inference Reducing the amount of searching would greatly enhance performance (e.g. don't search from start, search in one of three lists, ...). About being though to know while reading: voting isn't done on the fly. It's done after all potential codewords are read. This could be a starting point :)

This is also one of my ideas. Once both row indicator columns are read, it should be possible to get a reasonably accurate idea about which line number each codeword is on.
 

I still haven't read your code completely, so I don't know why you need to resize various lists, but the methods don't do what I think they are suppose to do. E.g., if the size of the list is 57 and you call it with the new size 50, after the call, the list will have the size 53 and not 50.

It's best not to think about this (really). I'd love to refactor this myself someday. Its more or less a bad habit to use multidimensional arrays like that instead of objects when designing algorithms and I'm glad that Martin Folwer doesn't read this :P

:-) :-)

Best regards and have a nice evening,

  Guenther