Updates to C++ port

[Christoph Schulz]

Hi all,

TL;DR: CMake, PDF417, tons of changes

over the past 2 months we have worked on ZXing's C++ port. The set of changes is rather large spread:
- MSVS support (we're testing on Windows+Linux+Mac OS)
- added CMake files: CMake can generate Visual Studio / Qt Creator / XCode / Eclipse / Make / Ninja files. The reasoning behind this is having a real IDE :)
  - acceptance to use CMake?
  - drop SCons? (totally super seeded by CMake)
  - drop XCode project files? (maybe some adjustments for iOS to CMakeLists.txt must be made)
- replaced ImageMagick with stb_image (2 lightweight files). The reasoning behind this is: ImageMagick is a real pain to build on Windows and OS X.
  - acceptance to adding this to libzxing (not zxing.exe)? (note: this allows some visual debugging for bit matrices)
  - stb_image cannot do image manipulation (rotate90 + crop are a no brainer)
  - stb_image cannot load every *.png / *.jpg / ... but most of them
  - licsense seems ok
  - another option would be to use a combination of LodePNG and jpgd
- added PDF417 support
  - merged many (but not all) PDF417 changes by Hartmut Neubauer (hfn)
  - hfn: Delta2Binarizer neat binarizer that scans lines using a modified Bresenham (not present in java port)
  - Delta2Binarizer added some modifications to prevent it from punching holes into PDF417 guard patterns
  - hfn: Detector changes to guard pattern search (not present in java port)
  - Detector replaced QR-Code style grid sampling with a "knowlege driven" approach that guesses codewords using squared error minimization (this is computational more intensive than "hashing bits", but results are a lot better since every codeword gets valid)
  - rest roughly equals initial port by hfn
  - we're currently fixing some remaining issues with the decoder and the detector (some issues remain at VERY low resolutions)
- rewritten zxing.exe
  - new name zxing-image.exe
  - dropped --show-filename --dump-raw etc. in favor of --test-mode ("...failed: <valid result>" messages were confusing)
  - dropped --show-format in favor of --more (displays result points in addition to format)
  - added support for reading *.bin files
  - overall simpler code
- some minor changes here and there + some more likely to come
- back-port(s) to Java are on our list - no worries :)
- see https://github.com/schulzch/zxing/tree/pdf417

The question is how to deal with those changes. Create one issue with a big fat patch or split it into multiple patches (that'll be a real pain)? Everyone happy with those changes or is there anything to change/enhance left? :)

Regards,
Christoph

[Sean Owen]

I think there are three types of changes in here:

1. C++ make / build system changes. I'd defer to Steven about what to incorporate. I'm sure it's all a good idea; some bits may be at odds with building for stuff like the iPhone, I don't know. I can provide commit access if that's the easiest way to add it.

2. Simple PDF417 changes. That should be easy to back-port to Java and I can help there.

3. Complex PDF417 changes. Let's talk about this last. I remember trying to incorporate a patch on this point and finding it was a bit too hard for some reason. 

[Steven Parkes]

  - acceptance to use CMake?

I'm okay with putting this in as long as someone maintains it. If it gets out of date and becomes a support issue, I think it'd be yanked. That seem reasonable?

  - drop SCons? (totally super seeded by CMake)

I wouldn't think so unless it's causing a problem I don't know of? CMake is a beast. I have no problem enabling it but I don't want to require it. Heck, we don't even require people install scons, we have the "lite" copy installed so they just need python.

  - drop XCode project files? (maybe some adjustments for iOS to CMakeLists.txt must be made)

I don't think so. That would make CMake a hard dependence and I can imagine all sorts of issues when Apple decides to make changes to the project file format.

- replaced ImageMagick with stb_image (2 lightweight files). The reasoning behind this is: ImageMagick is a real pain to build on Windows and OS X.

Given that there are limitations, I wouldn't think so. But I don't have any problem providing multiple options.

  - acceptance to adding this to libzxing (not zxing.exe)? (note: this allows some visual debugging for bit matrices)

I wouldn't think so … just as in the java case, I don't think the core library should have any image-specifc code. It makes no sense to include any of this stuff on iOS and having different compositions of the library on different platforms seems unclean. Fine to have a library/app that includes aux stuff, though.

- rewritten zxing.exe

Haven't looked at these in detail. Not sure if these are objectively better (one man's confusing is another man's clear). Not sure if these remove functionality, which might be an issue. I can't remember if the exec is used in testing ...

I have a big commit pending which modernizes most of the 1D decoders and has a bunch of other cleanup. I'll try to get it in this weekend.

[Christoph Schulz]

Ok, sounds fair so far:

- complex PDF417 changes: Sure. Do you prefer a top-down summary or bottom-up annotated diffs? The backport to Java is a separate patch anyway.

- CMake maintainership: I'm ok with this, since they usually dont break things.

- stb_image: I can replace it with jpgd+LodePNG and move it to zxing-image, so that it won't clutter libzxing (note: visual debugging gets sort of lost this way :/). In terms of functionality these two libs are a complete replacement for ImageMagick in terms of current functionality. I think its really worth dropping ImageMagick, because its more or less a show-stopper (talking about beasts) on non-linux platforms.

- rewritten zxing.exe: I'll make sure so that no use-case gets lost (bash-pipeline processing, playing around, blackbox testing). The non-refactoring change is: you have to enable "--test-mode" to get *.txt/*.bin compared against *.png/*.jpg. I think its reasonable because "--dump-raw" already got implicitly enabled when argc == 2 ("zxing <image>" output differed heavliy from "zxing --try-harder <image>" - very confusing to 4 out of 4 people).

Regards,
Christoph

[Steven Parkes]

- complex PDF417 changes: Sure. Do you prefer a top-down summary or bottom-up annotated diffs? The backport to Java is a separate patch anyway.

I'd really rather both ports were committed at the same time. In particular, I'd like Sean's buy-off on the Java changes before committing the parallel changes to the C++ project. There's a huge benefit in terms of getting the most value out of contributor time if the Java and C++ have exactly the same behavior.

 

- stb_image: I can replace it with jpgd+LodePNG and move it to zxing-image, so that it won't clutter libzxing (note: visual debugging gets sort of lost this way :/).

LodePNG is BSD licensed, which is good. Looks like there's a successor to jpgd and it's also labeled a "public domain". That's actually not a license and lawyers sometimes don't like it. But I don't think it's a show-stopper for us. But I think it's good that we keep the core library is separate so in some weak sense, we're not distributing other people's code.

Not sure about removing IM vs. making it an optional backend. I need to check some downstream stuff I have. I can do that this weekend. I don't think it's an issue but I want to double check.

- rewritten zxing.exe: I'll make sure so that no use-case gets lost (bash-pipeline processing, playing around, blackbox testing)

Great. That was my only concern, particularly using it for tests. I also found the invokation to be a bit weird.

[Sean Owen]

For Java, bottom-up diff from HEAD is ideal. Obviously matching the style is best but that's easy for me to touch-up before commit. The harder thing would be integrating significant structural changes, and I don't imagine this needs structural changes.

We can tackle in parts if that's easier. I can commit the Java parts, and if Steven's OK, could even give you commit access to then commit the parallel C++ change. That offloads this part onto us then.

[hfneubauer]

Hi Christoph,
thanks lots for your work. It seams interesting :-)
Regards, Hartmut (hfneubauer)

[Christoph Schulz]

Am Freitag, 8. Februar 2013 12:20:56 UTC+1 schrieb Sean Owen:

For Java, bottom-up diff from HEAD is ideal. Obviously matching the style is best but that's easy for me to touch-up before commit. The harder thing would be integrating significant structural changes, and I don't imagine this needs structural changes.

Ok. I'm going to split off non-pdf417 c++ specific stuff into a filter branch next week, that can be applied to HEAD in near future. Backporting pdf417 from c++ to java (diffrent branch = one patch series) can happen in early march from our side.

[hfneubauer-home]

Hi Christoph,

yesterday I found a litte, but effective improvement of "my" (hfn's) C++ port of the PDF417 detector. It happens that sometimes an image seems accurate, but it cannot be decoded because of perspective distorsion. However, I only hat to take into account that - as you know - each PDF417 codeword has 4 bars and 4 spaces. So, if the number of bars and spaces of one row equals 8 times the number of expected codewords, the new code takes 8 bars/spaces for each codeword. Are you still interested in this improvement although many changes have been done in "your" version of Detector? I can add it on monday and tell you the diff. Regards, hfn

Am Freitag, 8. Februar 2013 19:54:23 UTC+1 schrieb Christoph Schulz:

Am Freitag, 8. Februar 2013 12:20:56 UTC+1 schrieb Sean Owen:

(...)

[Christoph Schulz]

Hi,

took me longer than expected due to some urgent tasks. Here is the first patch containing all non-pdf417 specific changes ready to merge into SVN (patch file is attached). Rest (pdf417 java+cpp) will follow.

Am Freitag, 22. Februar 2013 22:12:23 UTC+1 schrieb hfneubauer-home:

yesterday I found a litte, but effective improvement of "my" (hfn's) C++ port of the PDF417 detector. It happens that sometimes an image seems accurate, but it cannot be decoded because of perspective distorsion. However, I only hat to take into account that - as you know - each PDF417 codeword has 4 bars and 4 spaces. So, if the number of bars and spaces of one row equals 8 times the number of expected codewords, the new code takes 8 bars/spaces for each codeword. Are you still interested in this improvement although many changes have been done in "your" version of Detector? I can add it on monday and tell you the diff. Regards, hfn

Interessting tweak, but I'm not sure if that can be applied to "our" version (term feels wrong). We're detecting codewords from each binarized scanline (see line 843+) and then diffing lines on codeword level (see line 950+). The effect should be the same, but in addition one "line of codewords" can be recovered from many scanlines using cluster validation and hamming distances - though we're currently only doing half of that ;-)

In addition a small tweak got in this week you might be interested in: Look at more than a single pixel to extend the area determined by findGuardPattern() up- and downwards

Regards,
Christoph

[hfneubauer-home]

Hi all,
thank you for the idea about extending the findGuardPattern area up- and downwards by more than one pixel; perhaps, I'll adopt it.
Currently I am investigating in the following issues:
- let the argument of the Delta2Binarizer constructor be variable (currently 24 - see the Detector::detect method) - in cases of very dark, but more or less clear images, this is helpful;
- other time improve the Delta2Binarizer::createLinesMatrix: the idea: if you want to divide the lines of a rectangle into equal parts, if the opposite sides are not parallel, don't divide the length of the sides, but rather the logarithms of their distances to their intersection; and this not only in vertical, but also in horizontal direction.
Greetings, HFNeubauer

[Christoph Schulz]

I've build some additional blackbox tests (mainly damaged PDF417 barcodes with EC level 4 or level 8). They're all passing ClearImage and nearly all of them pass "our" implementation. I've build them as we can't publish real world data due to privaciy issues. Hope you like them ;-)

[Sean Owen]

(Shall I put these in the main Java project? more benchmarks wouldn't hurt.)

[Steven Parkes]

+1

On Mar 12, 2013, at 10:49 AM, Sean Owen <sro...@gmail.com> wrote:

> (Shall I put these in the main Java project? more benchmarks wouldn't hurt.)
>

> --
>
> ---
> You received this message because you are subscribed to the Google Groups "zxing" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to zxing+un...@googlegroups.com.
> For more options, visit https://groups.google.com/groups/opt_out.
>
>

[hfneubauer]

Hi Christoph,
I have an improvement of Delta2Binarizer::createLinesMatrix. It now uses the PerspectiveTransform class of ZXing (no more exp and log), until now for the y axis. Are you interested?
Regards, hfneubauer

[Christoph Schulz]

Yes, I'm interested. We've replaced Delta2Binarizer with GridSampler today, as an experiment. Oversampling the barcode works quite well and seems to be more in line with ZXing's processing pipeline. Havn't had a chance to profile it though. Changes should be visible on github this week.

Regards,
Christoph

[hfneubauer]

Hi, this is the new version of Delta2Binarizer::createLinesMatrix:

/**
* Create a lines matrix from the points <xTopLeft,yTopLeft>,<xTopRight,yTopRight>,
* <xBottomLeft,yBottomLeft>,<xBottomRight,yBottomRight> with nLines lines.
**/
/**
* todo: append argument "int nColumns" in order to handle perspective transformation
* in horizontal direction; in vertical direction it's yet done
**/
Ref<BitMatrix> Delta2Binarizer::createLinesMatrix(
                                                  int xTopLeft,
                                                  int yTopLeft,
                                                  int xTopRight,
                                                  int yTopRight,
                                                  int xBottomLeft,
                                                  int yBottomLeft,
                                                  int xBottomRight,
                                                  int yBottomRight,
                                                  int nLines)
{
  if(Matrix_)
    return Matrix_;
 
  LuminanceSource& source = *getLuminanceSource();
  nWidth_ = Maximum(abs(xTopRight-xTopLeft),abs(xBottomRight-xBottomLeft))+1;
  nHeight_ = nLines;
 
  InitArrays(nWidth_);
 
  Ref<BitMatrix> newMatrix (new BitMatrix(nWidth_ * UNIT, nHeight_));
 
  ArrayRef<unsigned char> row_ref (nWidth_);
  unsigned char* row = &row_ref[0];
  int nDoubleHeight = nHeight_ * 2;
 
  int rownum;
  int xStart,yStart,xStop,yStop;

  Ref<ResultPoint>rTopLeft(new ResultPoint(xTopLeft,yTopLeft)),
    rTopRight(new ResultPoint(xTopRight,yTopRight)),
    rBottomLeft(new ResultPoint(xBottomLeft,yBottomLeft)),
    rBottomRight(new ResultPoint(xBottomRight,yBottomRight));

  /* 2013-03-13 hfn: use perspective transformation, at first only with xdimension = 1(2 col.) */
  Ref<PerspectiveTransform> trfm = createTransform(
    rTopLeft,rTopRight,rBottomLeft,rBottomRight,
    /*nColumns*/1,nLines);
  std::vector<float> leftColumn(nLines << 1, (const float)0.0f);
  std::vector<float> rightColumn(nLines << 1, (const float)0.0f);
  for(int i=0;i<nLines;i++) {
    int ii = i << 1;
    leftColumn[ii] = 0;
    leftColumn[ii + 1] = ((float)i + 0.5);
    rightColumn[ii] = 1.0;
    rightColumn[ii + 1] = ((float)i + 0.5);
  }

  trfm->transformPoints(leftColumn);
  trfm->transformPoints(rightColumn);

  for(rownum=0;rownum<nHeight_;rownum++) {
    int rownum2 = rownum << 1;
    xStart=(int)round(leftColumn[rownum2]);
    yStart=(int)round(leftColumn[rownum2 + 1]);
    xStop=(int)round(rightColumn[rownum2]);
    yStop=(int)round(rightColumn[rownum2 + 1]);
#if (defined _WIN32 && defined DEBUG)
    WCHAR sz[256];
    swprintf(sz,_T("rownum = %d,start=%d,%d,stop=%d,%d\n"),rownum,xStart,yStart,xStop,yStop);
    OutputDebugString(sz);
#endif
   
    /* get the line from start to end point: */
    if(source.getStraightLine(row,nWidth_,xStart,yStart,xStop,yStop) > 0)
      HandleRow(rownum,row,newMatrix);
  }

  Matrix_ = newMatrix;
  return newMatrix;
}

The createTransform method can be defined similar as in other classes, or perhaps as static in the PerspectiveTransform class itself:

Ref<PerspectiveTransform> Delta2Binarizer::createTransform(
  Ref<ResultPoint> topLeft,
  Ref<ResultPoint> topRight,
  Ref<ResultPoint> bottomLeft,
  Ref<ResultPoint> bottomRight,
  int dimensionX, int dimensionY)
{
  Ref<PerspectiveTransform> transform(
    PerspectiveTransform::quadrilateralToQuadrilateral(
    0.0f, // p1ToX
    0.0f, // p1ToY
    dimensionX, // p2ToX
    0.0f, // p2ToY
    dimensionX, // p3ToX
    dimensionY, // p3ToY
    0.0f, // p4ToX
    dimensionY, // p4ToY
    topLeft->getX(), // p1FromX
    topLeft->getY(), // p1FromY
    topRight->getX(), // p2FromX
    topRight->getY(), // p2FromY
    bottomRight->getX(), // p3FromX
    bottomRight->getY(), // p3FromY
    bottomLeft->getX(), // p4FromX
    bottomLeft->getY())); // p4FromY
  return transform;
}

Regards.

[Christoph Schulz]

1. C++ make / build system changes. I'd defer to Steven about what to incorporate. I'm sure it's all a good idea; some bits may be at odds with building for stuff like the iPhone, I don't know. I can provide commit access if that's the easiest way to add it.

Done (see earlier patch along with some minor changes not in the patch).
 

2. Simple PDF417 changes. That should be easy to back-port to Java and I can help there.

3. Complex PDF417 changes. Let's talk about this last. I remember trying to incorporate a patch on this point and finding it was a bit too hard for some reason. 

Done. PDF1/2 JUnit tests pass... Java before:
pdf417 INFO: Decoded 16 images out of 32 (50%, 16 required)
pdf417-2 INFO: Decoded 72 images out of 92 (78%, 72 required)
and Java after:
pdf417 INFO: Decoded 20 images out of 32 (62%, 16 required)
pdf417-2 INFO: Decoded 90 images out of 92 (97%, 72 required)
C++ test results:
pdf417 summary:
 8 images tested total,
 5 passed hybrid, 5 passed global, 4 pass both,
 1 passed only hybrid, 1 passed only global, 2 pass neither.
pdf417-2 summary:
 23 images tested total,
 23 passed hybrid, 23 passed global, 23 pass both,
 0 passed only hybrid, 0 passed only global, 0 pass neither.

Commits concerning Java:
https://github.com/schulzch/zxing/commit/40f10dd6258a49cb66e2d14400faab39184a5543
https://github.com/schulzch/zxing/commit/350b3a54d34557f17a837fe42c97d87b3e288f43

I think it's best to get the Java PDF417 patch right first. Afterwards the C++ version can be refactored/adjusted and merged.
Feel free to comment/merge/whatever :)

Regards,
Christoph

[Sean Owen]

OK, so the Java patches are ready to review/commit? and should I start with the first one only?

[Christoph Schulz]

Am Donnerstag, 21. März 2013 15:54:49 UTC+1 schrieb Sean Owen:

OK, so the Java patches are ready to review/commit? and should I start with the first one only?

I've merged the patches and dropped white space noise for you: cleaned patch :)

Regards,
Christoph

[Sean Owen]

Yes this looks like a strong improvement. Many more test images pass; there are a few new failures I'll look into. I'm going to tweak a few things about the code conventions and commit.

[Sean Owen]

(The failures were due to bad tests actually. This is a significant improvement across the board especially for large barcodes.)