DataMatrix DMDetetor: traceGap() assertion may fail in noisy area

[neycyanshi]

If the image is noisy after binarization, traceGap() assertion may fail on this line.
https://github.com/nu-book/zxing-cpp/blob/b93fdeef39342a4af66c5c62a6b28d05379c9772/core/src/datamatrix/DMDetector.cpp#L554
Because there are actually two operations in the main while loop that moves EdgeTracer's current point p, and it may stay unmoved. Project back + centered() and traceStep() happens to move the point in exactly the opposite direction. https://github.com/nu-book/zxing-cpp/blob/b93fdeef39342a4af66c5c62a6b28d05379c9772/core/src/datamatrix/DMDetector.cpp#L576 and https://github.com/nu-book/zxing-cpp/blob/b93fdeef39342a4af66c5c62a6b28d05379c9772/core/src/datamatrix/DMDetector.cpp#L607

[axxel]

Could you provide a sample image that triggers this issue?

[neycyanshi]

I found one assertion failure in one image in my large dataset. However, I have modified the binarizer and use image pyramid. So the image may not trigger failure in the original code. I could provide the binarized BitMatrix image and the tracer state.

[axxel]

I need something to reproduce the error on my machine. You should be able to dump your BitMatrix as a b/w image so that I can use that with the code as.

Am I right to assume you are employing an image pyramid to improve the decoding of high resolution images?

[neycyanshi]

That's right, pyramid is to improve decoding of high-res image. I am trying to reproduce on your master branch, stb_image.h doesn't support HEIC format. Also, the image contains private info, so I have to remove them. But you can see these lines may have some problem.

[neycyanshi]

Fortunately I have reproduced it on the binarized image. Here is the image that cause assertion failure. Manually set try_harder = true in DMDetector.

[neycyanshi]

First set tryHarder = true in DMDetector.cpp Line 779, to enable multi-line scan to detect off-center symbols.

Entry arguments:
ZXing:BitMatrixCursorF = {
img = {
object_ = 0x0000000101291bf0
}
p = (x = 283.5, y = 92.5)
d = (x = -1, y = 0.02175528874599993)
…
}
maxStepSize = 15

Line 340:
CHECK(tlTracer.traceGaps(tlTracer.right(), lineT, maxStepSize));

in traceGaps()
do…while loop
line.points().back() equals to p at the 14th iteration

(lldb) p line
(ZXing::DataMatrix::RegressionLine) $5 = {
_points = size=14 {
[0] = (x = 283.5, y = 92.5)
[1] = (x = 282.5, y = 92.5)
[2] = (x = 281.5, y = 91.5)
[3] = (x = 280.5, y = 91.5)
[4] = (x = 279.5, y = 91.5)
[5] = (x = 279.5, y = 93.5)
[6] = (x = 278.5, y = 95.5)
[7] = (x = 277.5, y = 95.5)
[8] = (x = 274.5, y = 95.5)
[9] = (x = 276.5, y = 100.5)
[10] = (x = 275.5, y = 99.5)
[11] = (x = 275.5, y = 101.5)
[12] = (x = 274.5, y = 100.5)
[13] = (x = 273.5, y = 99.5)
}
_directionInward = (x = -0.021750142264310393, y = -0.99976343767487418)
a = -0.82308011556249749
b = -0.56792527973812335
c = -283.34570390971504
}

(lldb) p *this
(ZXing::DataMatrix::EdgeTracer) $4 = {
ZXing::BitMatrixCursorF = {
img = {
object_ = 0x0000000101291bf0
}
p = (x = 273.5, y = 99.5)
d = (x = -1, y = 0.39311942704135705)
}
history = {
object_ = 0x0000000101291e90
}
}

(lldb) p gaps
(int) $6 = 1

[neycyanshi]

#171

[axxel]

I can not reproduce the failed assertion with your sample image with current master (including the tryHarder = true change). Could you please double check that this actually shows the issue. Which parameters to you pass ZXingReader?

Your removal of the assertion will fix your immediate issue but the assertion is there to let me know if there still is a problem with endless loops in the code. I'd rather reproduce the problem first and maybe fix it at a more appropriate place. Thanks for the effort, though!

[axxel]

Question: what compiler flags related to optimization/floating point math are you using? It could be that we get different results because you are using some relaxed floating point math, like -ffast-math?

[neycyanshi]

Question: what compiler flags related to optimization/floating point math are you using? It could be that we get different results because you are using some relaxed floating point math, like -ffast-math?

No, I checked by default this flag if off.

[neycyanshi]

Have your tracer traced to p = (x = 273.5, y = 99.5)?

[neycyanshi]

I can not reproduce the failed assertion with your sample image with current master (including the tryHarder = true change). Could you please double check that this actually shows the issue. Which parameters to you pass ZXingReader?

Your removal of the assertion will fix your immediate issue but the assertion is there to let me know if there still is a problem with endless loops in the code. I'd rather reproduce the problem first and maybe fix it at a more appropriate place. Thanks for the effort, though!

The parameters are -format DataMatrix **.png.

[axxel]

My trace passes through p = (x = 273.5, y = 99.5) as well but the contents of line is different at that point in time. I still suspect the differences in behavior come from differences in what your and my compiler actually put out. I was not referring only to the specific -ffast-math flag. Could you please provide the full command line of your compilation of DMDetector.cpp? (see e.g. make VERBOSE=1).

[neycyanshi]

I use clang 11.0

[ 32%] Building CXX object core/CMakeFiles/ZXing.dir/src/datamatrix/DMDetector.cpp.o
cd /Users/nullptr/Downloads/zxing-cpp/Debug/core && /Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/bin/c++ -DZXing_EXPORTS -I/Users/nullptr/Downloads/zxing-cpp/core/src -g -isysroot /Applications/Xcode.app/Contents/Developer/Platforms/MacOSX.platform/Developer/SDKs/MacOSX11.0.sdk -mmacosx-version-min=11.0 -fPIC -Wall -Wextra -Wno-missing-braces -Werror=undef -std=c++17 -o CMakeFiles/ZXing.dir/src/datamatrix/DMDetector.cpp.o -c /Users/nullptr/Downloads/zxing-cpp/core/src/datamatrix/DMDetector.cpp

After make, run
example/ZXingReader -format DataMatrix /Users/nullptr/Downloads/Sample_TraceGap.png
Assertion failed: (line.points().empty() || p != line.points().back()), function traceGaps, file /Users/nullptr/Downloads/zxing-cpp/core/src/datamatrix/DMDetector.cpp, line 554.
fish: 'example/ZXingReader -format Dat…' terminated by signal SIGABRT (Abort)

[neycyanshi]

I noticed there is no -ffloat-store, is this flag causing the problem?

[axxel]

I noticed there is no -ffloat-store, is this flag causing the problem?

That seemed like a very good guess, but it turns out, my linux clang-11 setup is not using that compiler flag either. I'm running out of ideas. It seems the only difference left is macOS + clang12 vs linux + clang11. My gut feeling says it is unlikely that this really is the root cause.

Could you please double check that the input you are working with is exactly what you posted above?

[neycyanshi]

I noticed there is no -ffloat-store, is this flag causing the problem?

That seemed like a very good guess, but it turns out, my linux clang-11 setup is not using that compiler flag either. I'm running out of ideas. It seems the only difference left is macOS + clang12 vs linux + clang11. My gut feeling says it is unlikely that this really is the root cause.

Could you please double check that the input you are working with is exactly what you posted above?

I checked the input is exactly what I posted above. Have you set tryHarder = true in DMDetector.cpp on your linux + chang11 setup?

[axxel]

Good question but, yes, I did. At this point I give up. I assume you don't mind if the assert stays (debug build only)? The release build will contain your fix.

[neycyanshi]

Good question but, yes, I did. At this point I give up. I assume you don't mind if the assert stays (debug build only)? The release build will contain your fix.

Thanks, I don't mind the asserts. Btw, there is also another assert in TraceStep(), which may fail in rare cases. I will keep filling more DataMatrix test cases and try to trigger it. I will notify you once I found another case.