From: srowen Date: Wed, 18 Jun 2008 22:12:59 +0000 (+0000) Subject: Improved approach to 1D decoding -- better use of integer math by scaling pattern... X-Git-Url: http://git.rot13.org/?p=zxing.git;a=commitdiff_plain;h=37b2a3f1265f80f9549ca5a44efda26041682f91 Improved approach to 1D decoding -- better use of integer math by scaling pattern ratios up to expected number of pixels, rather than the other way. Modified constants accordingly. Also introduced notion of maxium variance that any one bar in a pattern can have and stiill be accepted. Finally, adjusted false-positives test failure limit downward due to recent improvements. git-svn-id: http://zxing.googlecode.com/svn/trunk@441 59b500cc-1b3d-0410-9834-0bbf25fbcc57 --- diff --git a/core/src/com/google/zxing/oned/AbstractOneDReader.java b/core/src/com/google/zxing/oned/AbstractOneDReader.java index d642547d..86f0a7b6 100644 --- a/core/src/com/google/zxing/oned/AbstractOneDReader.java +++ b/core/src/com/google/zxing/oned/AbstractOneDReader.java @@ -36,6 +36,7 @@ import java.util.Hashtable; public abstract class AbstractOneDReader implements OneDReader { private static final int INTEGER_MATH_SHIFT = 8; + public static final int PATTERN_MATCH_RESULT_SCALE_FACTOR = 256; public final Result decode(MonochromeBitmapSource image) throws ReaderException { return decode(image, null); @@ -183,12 +184,13 @@ public abstract class AbstractOneDReader implements OneDReader { * * @param counters observed counters * @param pattern expected pattern + * @param maxIndividualVariance * @return ratio of total variance between counters and pattern compared to total pattern size, * where the ratio has been multiplied by 256. So, 0 means no variance (perfect match); 256 means * the total variance between counters and patterns equals the pattern length, higher values mean * even more variance */ - static int patternMatchVariance(int[] counters, int[] pattern) { + static int patternMatchVariance(int[] counters, int[] pattern, int maxIndividualVariance) { int numCounters = counters.length; int total = 0; int patternLength = 0; @@ -204,16 +206,20 @@ public abstract class AbstractOneDReader implements OneDReader { // We're going to fake floating-point math in integers. We just need to use more bits. // Scale up patternLength so that intermediate values below like scaledCounter will have // more "significant digits" - patternLength <<= INTEGER_MATH_SHIFT; - int patternRatio = patternLength / total; + int unitBarWidth = (total << INTEGER_MATH_SHIFT) / patternLength; + maxIndividualVariance *= unitBarWidth; int totalVariance = 0; for (int x = 0; x < numCounters; x++) { - int scaledCounter = counters[x] * patternRatio; - int width = pattern[x] << INTEGER_MATH_SHIFT; - totalVariance += scaledCounter > width ? scaledCounter - width : width - scaledCounter; + int counter = counters[x] << INTEGER_MATH_SHIFT; + int scaledPattern = pattern[x] * unitBarWidth; + int variance = counter > scaledPattern ? counter - scaledPattern : scaledPattern - counter; + if (variance > maxIndividualVariance) { + return Integer.MAX_VALUE; + } + totalVariance += variance; } - return (totalVariance << 8) / patternLength; + return totalVariance / total; } // This declaration should not be necessary, since this class is diff --git a/core/src/com/google/zxing/oned/AbstractUPCEANReader.java b/core/src/com/google/zxing/oned/AbstractUPCEANReader.java index f4b1fa60..4aa11f46 100644 --- a/core/src/com/google/zxing/oned/AbstractUPCEANReader.java +++ b/core/src/com/google/zxing/oned/AbstractUPCEANReader.java @@ -35,7 +35,8 @@ import java.util.Hashtable; */ public abstract class AbstractUPCEANReader extends AbstractOneDReader implements UPCEANReader { - private static final int MAX_VARIANCE = 104; + private static final int MAX_AVG_VARIANCE = (int) (PATTERN_MATCH_RESULT_SCALE_FACTOR * 0.40625f); + private static final int MAX_INDIVIDUAL_VARIANCE = (int) (PATTERN_MATCH_RESULT_SCALE_FACTOR * 0.5f); /** * Start/end guard pattern. @@ -207,7 +208,7 @@ public abstract class AbstractUPCEANReader extends AbstractOneDReader implements counters[counterPosition]++; } else { if (counterPosition == patternLength - 1) { - if (patternMatchVariance(counters, pattern) < MAX_VARIANCE) { + if (patternMatchVariance(counters, pattern, MAX_INDIVIDUAL_VARIANCE) < MAX_AVG_VARIANCE) { return new int[]{patternStart, x}; } patternStart += counters[0] + counters[1]; @@ -242,12 +243,12 @@ public abstract class AbstractUPCEANReader extends AbstractOneDReader implements static int decodeDigit(BitArray row, int[] counters, int rowOffset, int[][] patterns) throws ReaderException { recordPattern(row, rowOffset, counters); - int bestVariance = MAX_VARIANCE; // worst variance we'll accept + int bestVariance = MAX_AVG_VARIANCE; // worst variance we'll accept int bestMatch = -1; int max = patterns.length; for (int i = 0; i < max; i++) { int[] pattern = patterns[i]; - int variance = patternMatchVariance(counters, pattern); + int variance = patternMatchVariance(counters, pattern, MAX_INDIVIDUAL_VARIANCE); if (variance < bestVariance) { bestVariance = variance; bestMatch = i; diff --git a/core/src/com/google/zxing/oned/Code128Reader.java b/core/src/com/google/zxing/oned/Code128Reader.java index 1fc430c3..8b027bbc 100644 --- a/core/src/com/google/zxing/oned/Code128Reader.java +++ b/core/src/com/google/zxing/oned/Code128Reader.java @@ -142,7 +142,8 @@ public final class Code128Reader extends AbstractOneDReader { {2, 3, 3, 1, 1, 1, 2} }; - private static final int MAX_VARIANCE = 56; + private static final int MAX_AVG_VARIANCE = (int) (PATTERN_MATCH_RESULT_SCALE_FACTOR * 0.1875f); + private static final int MAX_INDIVIDUAL_VARIANCE = (int) (PATTERN_MATCH_RESULT_SCALE_FACTOR * 0.25f); private static final int CODE_SHIFT = 98; @@ -183,10 +184,10 @@ public final class Code128Reader extends AbstractOneDReader { counters[counterPosition]++; } else { if (counterPosition == patternLength - 1) { - int bestVariance = MAX_VARIANCE; + int bestVariance = MAX_AVG_VARIANCE; int bestMatch = -1; for (int startCode = CODE_START_A; startCode <= CODE_START_C; startCode++) { - int variance = patternMatchVariance(counters, CODE_PATTERNS[startCode]); + int variance = patternMatchVariance(counters, CODE_PATTERNS[startCode], MAX_INDIVIDUAL_VARIANCE); if (variance < bestVariance) { bestVariance = variance; bestMatch = startCode; @@ -214,11 +215,11 @@ public final class Code128Reader extends AbstractOneDReader { private static int decodeCode(BitArray row, int[] counters, int rowOffset) throws ReaderException { recordPattern(row, rowOffset, counters); - int bestVariance = MAX_VARIANCE; // worst variance we'll accept + int bestVariance = MAX_AVG_VARIANCE; // worst variance we'll accept int bestMatch = -1; for (int d = 0; d < CODE_PATTERNS.length; d++) { int[] pattern = CODE_PATTERNS[d]; - int variance = patternMatchVariance(counters, pattern); + int variance = patternMatchVariance(counters, pattern, MAX_INDIVIDUAL_VARIANCE); if (variance < bestVariance) { bestVariance = variance; bestMatch = d; diff --git a/core/test/src/com/google/zxing/common/FalsePositivesBlackBoxTestCase.java b/core/test/src/com/google/zxing/common/FalsePositivesBlackBoxTestCase.java index d078c15f..9eef2119 100644 --- a/core/test/src/com/google/zxing/common/FalsePositivesBlackBoxTestCase.java +++ b/core/test/src/com/google/zxing/common/FalsePositivesBlackBoxTestCase.java @@ -35,7 +35,7 @@ import java.io.IOException; public final class FalsePositivesBlackBoxTestCase extends AbstractBlackBoxTestCase { // This number should be reduced as we get better at rejecting false positives. - private static final int FALSE_POSITIVES_ALLOWED = 44; + private static final int FALSE_POSITIVES_ALLOWED = 23; // Use the multiformat reader to evaluate all decoders in the system. public FalsePositivesBlackBoxTestCase() {