DataBar: improve detection rate by incorporating edge-2-edge pattern …

…idea This brings the algorithm closer to the reference algorithm and to what the new DataBarLimited reader is doing. One less MAX_INDIVIDUAL_VARIANCE magic number, yay.
zxing-cpp · Oct 29, 2024 · 308f820 · 308f820
1 parent 939abf8
commit 308f820
Show file tree

Hide file tree

Showing 10 changed files with 100 additions and 80 deletions.
diff --git a/core/src/Pattern.h b/core/src/Pattern.h
@@ -278,14 +278,15 @@ PatternView FindLeftGuard(const PatternView& view, int minSize, const FixedPatte
 							  });
 }
 
-template <int LEN, int SUM>
-std::array<int, LEN - 2> NormalizedE2EPattern(const PatternView& view)
+template <int LEN>
+std::array<int, LEN - 2> NormalizedE2EPattern(const PatternView& view, int mods, bool reverse = false)
 {
-	double moduleSize = static_cast<double>(view.sum(LEN)) / SUM;
+	double moduleSize = static_cast<double>(view.sum(LEN)) / mods;
 	std::array<int, LEN - 2> e2e;
 
 	for (int i = 0; i < LEN - 2; i++) {
-		double v = (view[i] + view[i + 1]) / moduleSize;
+		int i_v = reverse ? LEN - 2 - i : i;
+		double v = (view[i_v] + view[i_v + 1]) / moduleSize;
 		e2e[i] = int(v + .5);
 	}
 

diff --git a/core/src/oned/ODCode128Reader.cpp b/core/src/oned/ODCode128Reader.cpp
@@ -158,7 +158,7 @@ class Raw2TxtDecoder
 constexpr auto START_PATTERN_PREFIX = FixedPattern<3, 4>{2, 1, 1};
 constexpr int CHAR_LEN = 6;
 constexpr float QUIET_ZONE = 5;	// quiet zone spec is 10 modules, real world examples ignore that, see #138
-constexpr int CHAR_SUM = 11;
+constexpr int CHAR_MODS = 11;
 
 //TODO: make this a constexpr variable initialization
 static auto E2E_PATTERNS = [] {
@@ -180,7 +180,7 @@ Barcode Code128Reader::decodePattern(int rowNumber, PatternView& next, std::uniq
 	int minCharCount = 4; // start + payload + checksum + stop
 	auto decodePattern = [](const PatternView& view, bool start = false) {
 		// This is basically the reference algorithm from the specification
-		int code = IndexOf(E2E_PATTERNS, ToInt(NormalizedE2EPattern<CHAR_LEN, CHAR_SUM>(view)));
+		int code = IndexOf(E2E_PATTERNS, ToInt(NormalizedE2EPattern<CHAR_LEN>(view, CHAR_MODS)));
 		if (code == -1 && !start) // if the reference algo fails, give the original upstream version a try (required to decode a few samples)
 			code = DecodeDigit(view, Code128::CODE_PATTERNS, MAX_AVG_VARIANCE, MAX_INDIVIDUAL_VARIANCE);
 		return code;

diff --git a/core/src/oned/ODDataBarCommon.cpp b/core/src/oned/ODDataBarCommon.cpp
@@ -74,6 +74,14 @@ using Array4F = std::array<float, 4>;
 bool ReadDataCharacterRaw(const PatternView& view, int numModules, bool reversed, Array4I& oddPattern,
 						  Array4I& evnPattern)
 {
+#if 1
+	auto pattern = NormalizedPatternFromE2E<8>(view, numModules, reversed);
+	OddEven<Array4I&> res = {oddPattern, evnPattern};
+
+	for (int i = 0; i < Size(pattern); ++i)
+		res[i % 2][i / 2] = pattern[i];
+
+#else
 	OddEven<Array4I&> res = {oddPattern, evnPattern};
 	OddEven<Array4F> rem;
 
@@ -86,6 +94,7 @@ bool ReadDataCharacterRaw(const PatternView& view, int numModules, bool reversed
 		res[i % 2][i / 2] = int(v + .5f);
 		rem[i % 2][i / 2] = v - res[i % 2][i / 2];
 	}
+#endif
 
 	// DataBarExpanded data character is 17 modules wide
 	// DataBar outer   data character is 16 modules wide

diff --git a/core/src/oned/ODDataBarCommon.h b/core/src/oned/ODDataBarCommon.h
@@ -114,14 +114,22 @@ struct PairHash
 constexpr int FULL_PAIR_SIZE = 8 + 5 + 8;
 constexpr int HALF_PAIR_SIZE = 8 + 5 + 2; // half has to be followed by a guard pattern
 
-template<typename T>
-int ParseFinderPattern(const PatternView& view, bool reversed, T l2rPattern, T r2lPattern)
+template<int N>
+int ParseFinderPattern(const PatternView& view, bool reversed, const std::array<std::array<int, 3>, N>& e2ePatterns)
 {
-	constexpr float MAX_AVG_VARIANCE        = 0.2f;
-	constexpr float MAX_INDIVIDUAL_VARIANCE = 0.45f;
-
-	int i = 1 + RowReader::DecodeDigit(view, reversed ? r2lPattern : l2rPattern, MAX_AVG_VARIANCE,
-									   MAX_INDIVIDUAL_VARIANCE, true);
+	const auto e2e = NormalizedE2EPattern<5>(view, 15, reversed);
+
+	int best_i, best_e = 3;
+	for (int i = 0; i < Size(e2ePatterns); ++i) {
+		int e = 0;
+		for (int j = 0; j < 3; ++j)
+			e += std::abs(e2ePatterns[i][j] - e2e[j]);
+		if (e < best_e) {
+			best_e = e;
+			best_i = i;
+		}
+	}
+	int i = best_e <= 1 ? 1 + best_i : 0;
 	return reversed ? -i : i;
 }
 
@@ -134,6 +142,49 @@ struct OddEven
 
 using Array4I = std::array<int, 4>;
 
+// elements() determines the element widths of an (n,k) character with
+// at least one even-numbered element that's just one module wide.
+// (Note: even-numbered elements - 2nd, 4th, 6th, etc., have odd indexes)
+// for DataBarLimited: LEN=14, mods=26/18
+template <int LEN>
+std::array<int, LEN> NormalizedPatternFromE2E(const PatternView& view, int mods, bool reversed = false)
+{
+	bool isExp = mods == 17; // elementsExp() with at least one odd-numbered element that's just one module wide
+	const auto e2e = NormalizedE2EPattern<LEN>(view, mods, reversed);
+	std::array<int, LEN> widths;
+
+	// derive element widths from normalized edge-to-similar-edge measurements
+	int barSum = widths[0] = isExp ? 8 : 1; // first assume 1st bar is 1 / 8
+	for (int i = 0; i < Size(e2e); i++) {
+		widths[i + 1] = e2e[i] - widths[i];
+		barSum += widths[i + 1];
+	}
+	widths.back() = mods - barSum; // last even element makes mods modules
+
+	// int minEven = widths[1];
+	// for (int i = 3; i < Size(widths); i += 2)
+	// 	minEven = std::min(minEven, widths[i]);
+	OddEven<int> min = {widths[0], widths[1]};
+	for (int i = 2; i < Size(widths); i++)
+		min[i] = std::min(min[i], widths[i]);
+
+	if (isExp && min[0] > 1) {
+		// minimum odd width is too big, readjust so minimum odd is 1
+		for (int i = 0; i < Size(widths); i += 2) {
+			widths[i] -= min[0] - 1;
+			widths[i + 1] += min[0] - 1;
+		}
+	} else if (!isExp && min[1] > 1) {
+		// minimum even width is too big, readjust so minimum even is 1
+		for (int i = 0; i < Size(widths); i += 2) {
+			widths[i] += min[1] - 1;
+			widths[i + 1] -= min[1] - 1;
+		}
+	}
+
+	return widths;
+}
+
 bool ReadDataCharacterRaw(const PatternView& view, int numModules, bool reversed, Array4I& oddPattern,
 						  Array4I& evnPattern);
 

diff --git a/core/src/oned/ODDataBarExpandedReader.cpp b/core/src/oned/ODDataBarExpandedReader.cpp
@@ -137,19 +137,16 @@ static const std::array<int, 7> VALID_HALF_PAIRS = {{-FINDER_A, FINDER_B, -FINDE
 
 static int ParseFinderPattern(const PatternView& view, Direction dir)
 {
-	static constexpr std::array<FixedPattern<5, 15>, 6> FINDER_PATTERNS = {{
-		{1, 8, 4, 1, 1}, // A
-		{3, 6, 4, 1, 1}, // B
-		{3, 4, 6, 1, 1}, // C
-		{3, 2, 8, 1, 1}, // D
-		{2, 6, 5, 1, 1}, // E
-		{2, 2, 9, 1, 1}, // F
+	static constexpr std::array<std::array<int, 3>, 6> e2ePatterns = {{
+		{9, 12, 5 }, // {1, 8, 4, 1, 1}, // A
+		{9, 10, 5 }, // {3, 6, 4, 1, 1}, // B
+		{7, 10, 7 }, // {3, 4, 6, 1, 1}, // C
+		{5, 10, 9 }, // {3, 2, 8, 1, 1}, // D
+		{8, 11, 6 }, // {2, 6, 5, 1, 1}, // E
+		{4, 11, 10}, // {2, 2, 9, 1, 1}, // F
 	}};
-	// TODO: c++20 constexpr inversion from FIND_PATTERN?
-	static constexpr std::array<FixedPattern<5, 15>, 6> REVERSED_FINDER_PATTERNS = {
-		{{1, 1, 4, 8, 1}, {1, 1, 4, 6, 3}, {1, 1, 6, 4, 3}, {1, 1, 8, 2, 3}, {1, 1, 5, 6, 2}, {1, 1, 9, 2, 2}}};
 
-	return ParseFinderPattern(view, dir == Direction::Left, FINDER_PATTERNS, REVERSED_FINDER_PATTERNS);
+	return ParseFinderPattern<6>(view, dir == Direction::Left, e2ePatterns);
 }
 
 static bool ChecksumIsValid(const Pairs& pairs)

diff --git a/core/src/oned/ODDataBarLimitedReader.cpp b/core/src/oned/ODDataBarLimitedReader.cpp
@@ -27,47 +27,14 @@ using namespace DataBar;
 constexpr int CHAR_LEN = 14;
 constexpr int SYMBOL_LEN = 1 + 3 * CHAR_LEN + 2;
 
-// elements() determines the element widths of an (n,k) character with
-// at least one even-numbered element that's just one module wide.
-// (Note: even-numbered elements - 2nd, 4th, 6th, etc., have odd indexes)
-// for DataBarLimited: SUM=26/18, LEN=14
-template <int LEN, int SUM>
-std::array<int, LEN> NormalizedPatternFromE2E(const PatternView& view)
-{
-	auto e2e = NormalizedE2EPattern<LEN, SUM>(view);
-	std::array<int, LEN> widths;
-
-	// derive element widths from normalized edge-to-similar-edge measurements
-	int barSum = widths[0] = 1; // first assume 1st bar is 1
-	for (int i = 0; i < Size(e2e); i++) {
-		widths[i + 1] = e2e[i] - widths[i];
-		barSum += widths[i + 1];
-	}
-	widths.back() = SUM - barSum; // last even element makes SUM modules
-
-	int minEven = widths[1];
-	for (int i = 3; i < Size(widths); i += 2)
-		minEven = std::min(minEven, widths[i]);
-
-	if (minEven > 1) {
-		// minimum even width is too big, readjust so minimum even is 1
-		for (int i = 0; i < Size(widths); i += 2) {
-			widths[i] += minEven - 1;
-			widths[i + 1] -= minEven - 1;
-		}
-	}
-
-	return widths;
-}
-
 static Character ReadDataCharacter(const PatternView& view)
 {
 	constexpr int G_SUM[] = {0, 183064, 820064, 1000776, 1491021, 1979845, 1996939};
 	constexpr int T_EVEN[] = {28, 728, 6454, 203, 2408, 1, 16632};
 	constexpr int ODD_SUM[] = {17, 13, 9, 15, 11, 19, 7};
 	constexpr int ODD_WIDEST[] = {6, 5, 3, 5, 4, 8, 1};
 
-	auto pattern = NormalizedPatternFromE2E<14, 26>(view);
+	auto pattern = NormalizedPatternFromE2E<14>(view, 26);
 
 	int checkSum = 0;
 	for (auto it = pattern.rbegin(); it != pattern.rend(); ++it)
@@ -170,13 +137,13 @@ Barcode DataBarLimitedReader::decodePattern(int rowNumber, PatternView& next, st
 		if ((!next.isAtFirstBar() && next[-1] < modSize) || (!next.isAtLastBar() && next[SYMBOL_LEN] < 5 * modSize))
 			continue;
 
-		auto checkCharPattern = ToInt(NormalizedPatternFromE2E<CHAR_LEN, 18>(checkView));
+		auto checkCharPattern = ToInt(NormalizedPatternFromE2E<CHAR_LEN>(checkView, 18));
 		int checkSum = IndexOf(CheckChars, checkCharPattern);
 		if (checkSum == -1)
 			continue;
 
 		printf("%f - ", modSize);
-		printv("%d ", NormalizedPatternFromE2E<CHAR_LEN, 18>(checkView));
+		printv("%d ", NormalizedPatternFromE2E<CHAR_LEN>(checkView, 18));
 
 		auto left = ReadDataCharacter(leftView);
 		auto right = ReadDataCharacter(rightView);

diff --git a/core/src/oned/ODDataBarReader.cpp b/core/src/oned/ODDataBarReader.cpp
@@ -86,25 +86,19 @@ static Character ReadDataCharacter(const PatternView& view, bool outsideChar, bo
 
 int ParseFinderPattern(const PatternView& view, bool reversed)
 {
-	static constexpr std::array<FixedPattern<5, 15>, 10> FINDER_PATTERNS = {{
-		{3, 8, 2, 1, 1},
-		{3, 5, 5, 1, 1},
-		{3, 3, 7, 1, 1},
-		{3, 1, 9, 1, 1},
-		{2, 7, 4, 1, 1},
-		{2, 5, 6, 1, 1},
-		{2, 3, 8, 1, 1},
-		{1, 5, 7, 1, 1},
-		{1, 3, 9, 1, 1},
+	static constexpr std::array<std::array<int, 3>, 9> e2ePatterns = {{
+		{11, 10, 3 }, // {3, 8, 2, 1, 1}
+		{8 , 10, 6 }, // {3, 5, 5, 1, 1}
+		{6 , 10, 8 }, // {3, 3, 7, 1, 1}
+		{4 , 10, 10}, // {3, 1, 9, 1, 1}
+		{9 , 11, 5 }, // {2, 7, 4, 1, 1}
+		{7 , 11, 7 }, // {2, 5, 6, 1, 1}
+		{5 , 11, 9 }, // {2, 3, 8, 1, 1}
+		{6 , 11, 8 }, // {1, 5, 7, 1, 1}
+		{4 , 12, 10}, // {1, 3, 9, 1, 1}
 	}};
 
-	// TODO: c++20 constexpr inversion from FIND_PATTERN?
-	static constexpr std::array<FixedPattern<5, 15>, 10> REVERSED_FINDER_PATTERNS = {{
-		{1, 1, 2, 8, 3}, {1, 1, 5, 5, 3}, {1, 1, 7, 3, 3}, {1, 1, 9, 1, 3}, {1, 1, 4, 7, 2},
-		{1, 1, 6, 5, 2}, {1, 1, 8, 3, 2}, {1, 1, 7, 5, 1}, {1, 1, 9, 3, 1},
-	}};
-
-	return ParseFinderPattern(view, reversed, FINDER_PATTERNS, REVERSED_FINDER_PATTERNS);
+	return ParseFinderPattern<9>(view, reversed, e2ePatterns);
 }
 
 static Pair ReadPair(const PatternView& view, bool rightPair)

diff --git a/test/blackbox/BlackboxTestRunner.cpp b/test/blackbox/BlackboxTestRunner.cpp
@@ -533,9 +533,9 @@ int runBlackBoxTests(const fs::path& testPathPrefix, const std::set<std::string>
 			{ 6, 6, 180 },
 		});
 
-		runTests("rss14-2", "DataBar", 13, {
-			{ 8, 10, 0   },
-			{ 9, 10, 180 },
+		runTests("rss14-2", "DataBar", 14, {
+			{ 10, 11, 0   },
+			{ 10, 11, 180 },
 		});
 
 		runTests("rssexpanded-1", "DataBarExpanded", 34, {

diff --git a/test/samples/rss14-2/0120358468019312.jpg b/test/samples/rss14-2/0120358468019312.jpg
diff --git a/test/samples/rss14-2/0120358468019312.txt b/test/samples/rss14-2/0120358468019312.txt
@@ -0,0 +1 @@
+20358468019312