From 18e3e8522fb403891dc211e6de9681dcf1030b66 Mon Sep 17 00:00:00 2001 From: "dav.olivier@gmail.com" Date: Fri, 3 Sep 2010 20:49:22 +0000 Subject: [PATCH] Improved datamatrix reader with new algorithm git-svn-id: http://zxing.googlecode.com/svn/trunk@1574 59b500cc-1b3d-0410-9834-0bbf25fbcc57 --- .../detector/WhiteRectangleDetector.java | 187 ++++++++---------- .../zxing/datamatrix/detector/Detector.java | 77 +++----- .../DataMatrixBlackBox1TestCase.java | 6 +- .../DataMatrixBlackBox2TestCase.java | 8 +- 4 files changed, 112 insertions(+), 166 deletions(-) diff --git a/core/src/com/google/zxing/common/detector/WhiteRectangleDetector.java b/core/src/com/google/zxing/common/detector/WhiteRectangleDetector.java index 66a32195..030d3a27 100644 --- a/core/src/com/google/zxing/common/detector/WhiteRectangleDetector.java +++ b/core/src/com/google/zxing/common/detector/WhiteRectangleDetector.java @@ -33,7 +33,6 @@ import com.google.zxing.common.BitMatrix; public final class WhiteRectangleDetector { private static final int INIT_SIZE = 40; - private static final int MIN_SIZE = 20; private final BitMatrix image; private final int height; @@ -134,34 +133,91 @@ public final class WhiteRectangleDetector { if (!sizeExceeded && atLeastOneBlackPointFoundOnBorder) { - // t t - //z x - // x OR z - // y y - - ResultPoint x = getBlackPoint(up, down, right - 1, false); - ResultPoint y = getBlackPoint(left, right, down - 1, true); - ResultPoint z = getBlackPoint(up, down, left + 1, false); - ResultPoint t = getBlackPoint(left, right, up + 1, true); - - // if the rectangle if perfectly horizontal (mostly in test cases) - // then we end up with: - // zt x - // - // y - - if (distance(z, t) < MIN_SIZE) { - ResultPoint u = getBlackPointInverted(up, down, right - 1, false); - t = x; - x = u; - } + ResultPoint x=null, y=null, z=null, t=null; + + final int max_size = right-left; + + for (int i = 1; i < max_size; i++){ + ResultPoint a = new ResultPoint(left, down-i); + ResultPoint b = new ResultPoint(left+i, down); + z = getBlackPointOnSegment(a, b); + if (z != null){ + break; + } + } + + if (z == null){ + throw NotFoundException.getNotFoundInstance(); + } - return centerEdges(y, z, x, t); + //go down right + for (int i = 1; i < max_size; i++){ + ResultPoint a = new ResultPoint(left, up+i); + ResultPoint b = new ResultPoint(left+i, up); + t = getBlackPointOnSegment(a, b); + if (t != null){ + break; + } + } + + if (t == null){ + throw NotFoundException.getNotFoundInstance(); + } + + //go down left + for (int i = 1; i < max_size; i++){ + ResultPoint a = new ResultPoint(right, up+i); + ResultPoint b = new ResultPoint(right-i, up); + x = getBlackPointOnSegment(a, b); + if (x != null){ + break; + } + } + + if (x == null){ + throw NotFoundException.getNotFoundInstance(); + } + + //go up left + for (int i = 1; i < max_size; i++){ + ResultPoint a = new ResultPoint(right, down-i); + ResultPoint b = new ResultPoint(right-i, down); + y = getBlackPointOnSegment(a, b); + if (y != null){ + break; + } + } + + if (y == null){ + throw NotFoundException.getNotFoundInstance(); + } + + return centerEdges(y, z, x, t); } else { - throw NotFoundException.getNotFoundInstance(); + throw NotFoundException.getNotFoundInstance(); } } + + + private ResultPoint getBlackPointOnSegment(ResultPoint a, ResultPoint b) { + int dist = distanceL2(a, b); + float xStep = (b.getX()-a.getX())/dist; + float yStep = (b.getY()-a.getY())/dist; + + for (int i = 0; i < dist; i++){ + if (image.get(Math.round(a.getX()+i*xStep), Math.round(a.getY()+i*yStep))){ + return new ResultPoint(Math.round(a.getX()+i*xStep), Math.round(a.getY()+i*yStep)); + } + } + return null; + } + + private static int distanceL2(ResultPoint a, ResultPoint b) { + return (int) Math.round(Math.sqrt((a.getX() - b.getX()) + * (a.getX() - b.getX()) + (a.getY() - b.getY()) + * (a.getY() - b.getY()))); + } /** * recenters the points of a constant distance towards the center @@ -203,89 +259,6 @@ public final class WhiteRectangleDetector { } } - // L1 distance (metropolitan distance) - private static float distance(ResultPoint a, ResultPoint b) { - return Math.abs(a.getX() - b.getX()) + Math.abs(a.getY() - b.getY()); - } - - /** - * Gets the coordinate of an extreme black point of a segment - * - * @param a min value of the scanned coordinate - * @param b max value of the scanned coordinate - * @param fixed value of fixed coordinate - * @param horizontal set to true if scan must be horizontal, false if vertical - * @return {@link ResultPoint} describing the black point. If scan is horizontal, - * the returned point is the first encountered if it is on the left of the image, - * else the last one. If scan is vertical, the returned point is the first encountered - * if it is on the top of the image, else the last one. - * {@link ResultPoint} is null if not black point has been found - */ - private ResultPoint getBlackPoint(int a, int b, int fixed, boolean horizontal) { - - ResultPoint last = null; - - if (horizontal) { - for (int x = a; x < b; x++) { - if (image.get(x, fixed)) { - if (x < width / 2) { - return new ResultPoint(x, fixed); - } else { - while (x < width && image.get(x, fixed)) { - x++; - } - x--; - last = new ResultPoint(x, fixed); - } - } - } - } else { - for (int y = a; y < b; y++) { - if (image.get(fixed, y)) { - if (y < height / 2) { - return new ResultPoint(fixed, y); - } else { - while (y < height && image.get(fixed, y)) { - y++; - } - y--; - last = new ResultPoint(fixed, y); - } - } - } - } - - return last; - } - - /** - * Same as getBlackPoint, but returned point is the last one found. - * - * @param a min value of the scanned coordinate - * @param b max value of the scanned coordinate - * @param fixed value of fixed coordinate - * @param horizontal set to true if scan must be horizontal, false if vertical - * @return {@link ResultPoint} describing the black point. - */ - private ResultPoint getBlackPointInverted(int a, int b, int fixed, boolean horizontal) { - - if (horizontal) { - for (int x = b + 1; x >= a; x--) { - if (image.get(x, fixed)) { - return new ResultPoint(x, fixed); - } - } - } else { - for (int y = b + 1; y >= a; y--) { - if (image.get(fixed, y)) { - return new ResultPoint(fixed, y); - } - } - } - - return null; - } - /** * Determines whether a segment contains a black point * diff --git a/core/src/com/google/zxing/datamatrix/detector/Detector.java b/core/src/com/google/zxing/datamatrix/detector/Detector.java index 512a35f0..206e5187 100644 --- a/core/src/com/google/zxing/datamatrix/detector/Detector.java +++ b/core/src/com/google/zxing/datamatrix/detector/Detector.java @@ -37,8 +37,6 @@ import java.util.Vector; */ public final class Detector { - private static final int MIN_GIVEUP_THRESHOLD = 3; - // Trick to avoid creating new Integer objects below -- a sort of crude copy of // the Integer.valueOf(int) optimization added in Java 5, not in J2ME private static final Integer[] INTEGERS = @@ -82,12 +80,6 @@ public final class Detector { ResultPointsAndTransitions lSideOne = (ResultPointsAndTransitions) transitions.elementAt(0); ResultPointsAndTransitions lSideTwo = (ResultPointsAndTransitions) transitions.elementAt(1); - //give up if there is no chance we'll decode something... - if (lSideOne.transitions > MIN_GIVEUP_THRESHOLD || - lSideTwo.transitions > MIN_GIVEUP_THRESHOLD) { - throw NotFoundException.getNotFoundInstance(); - } - // Figure out which point is their intersection by tallying up the number of times we see the // endpoints in the four endpoints. One will show up twice. Hashtable pointCount = new Hashtable(); @@ -149,7 +141,7 @@ public final class Detector { // The top right point is actually the corner of a module, which is one of the two black modules // adjacent to the white module at the top right. Tracing to that corner from either the top left // or bottom right should work here. - int dimension = Math.max(transitionsBetween(topLeft, topRight).getTransitions(), + int dimension = Math.min(transitionsBetween(topLeft, topRight).getTransitions(), transitionsBetween(bottomRight, topRight).getTransitions()); if ((dimension & 0x01) == 1) { // it can't be odd, so, round... up? @@ -161,7 +153,7 @@ public final class Detector { ResultPoint correctedTopRight = correctTopRight(bottomLeft, bottomRight, topLeft, topRight, dimension); //We redetermine the dimension using the corrected top right point - int dimension2 = Math.min(transitionsBetween(topLeft, correctedTopRight).getTransitions(), + int dimension2 = Math.max(transitionsBetween(topLeft, correctedTopRight).getTransitions(), transitionsBetween(bottomRight, correctedTopRight).getTransitions()); dimension2++; if ((dimension2 & 0x01) == 1) { @@ -181,48 +173,29 @@ public final class Detector { ResultPoint topLeft, ResultPoint topRight, int dimension) { - float corr = distance(bottomLeft, bottomRight) / (float) dimension; - float corrx = 0.0f; - float corry = 0.0f; - int norm = distance(topLeft, topRight); - float cos = (topRight.getX() - topLeft.getX()) / norm; - float sin = -(topRight.getY() - topLeft.getY()) / norm; - - if (cos > 0.0f && sin > 0.0f) { - if (cos > sin) { - corrx = corr * cos; - corry = -corr * sin; - } else { - corrx = -corr * sin; - corry = -corr * cos; - } - } else if (cos > 0.0f && sin < 0.0f) { - if (cos > -sin) { - corrx = -corr * sin; - corry = -corr * cos; - } else { - corrx = corr * cos; - corry = -corr * sin; - } - } else if (cos < 0.0f && sin < 0.0f) { - if (-cos > -sin) { - corrx = corr * cos; - corry = -corr * sin; - } else { - corrx = -corr * sin; - corry = -corr * cos; - } - } else if (cos < 0.0f && sin > 0.0f) { - if (-cos > sin) { - corrx = -corr * sin; - corry = -corr * cos; - } else { - corrx = corr * cos; - corry = -corr * sin; - } - } - - return new ResultPoint(topRight.getX() + corrx, topRight.getY() + corry); + + float corr = distance(bottomLeft, bottomRight) / (float)dimension; + int norm = distance(topLeft, topRight); + float cos = (topRight.getX() - topLeft.getX()) / norm; + float sin = (topRight.getY() - topLeft.getY()) / norm; + + ResultPoint c1 = new ResultPoint(topRight.getX()+corr*cos, topRight.getY()+corr*sin); + + corr = distance(bottomLeft, bottomRight) / (float)dimension; + norm = distance(bottomRight, topRight); + cos = (topRight.getX() - bottomRight.getX()) / norm; + sin = (topRight.getY() - bottomRight.getY()) / norm; + + ResultPoint c2 = new ResultPoint(topRight.getX()+corr*cos, topRight.getY()+corr*sin); + + int l1 = Math.abs(transitionsBetween(topLeft, c1).getTransitions() - transitionsBetween(bottomRight, c1).getTransitions()); + int l2 = Math.abs(transitionsBetween(topLeft, c2).getTransitions() - transitionsBetween(bottomRight, c2).getTransitions()); + + if (l1 <= l2){ + return c1; + } + + return c2; } // L2 distance diff --git a/core/test/src/com/google/zxing/datamatrix/DataMatrixBlackBox1TestCase.java b/core/test/src/com/google/zxing/datamatrix/DataMatrixBlackBox1TestCase.java index 14cc3cbc..5dc4c855 100644 --- a/core/test/src/com/google/zxing/datamatrix/DataMatrixBlackBox1TestCase.java +++ b/core/test/src/com/google/zxing/datamatrix/DataMatrixBlackBox1TestCase.java @@ -28,9 +28,9 @@ public final class DataMatrixBlackBox1TestCase extends AbstractBlackBoxTestCase // TODO use MultiFormatReader here once Data Matrix decoder is done super("test/data/blackbox/datamatrix-1", new DataMatrixReader(), BarcodeFormat.DATA_MATRIX); addTest(7, 7, 0.0f); - addTest(4, 4, 90.0f); - addTest(6, 6, 180.0f); - addTest(6, 6, 270.0f); + addTest(7, 7, 90.0f); + addTest(7, 7, 180.0f); + addTest(7, 7, 270.0f); } } \ No newline at end of file diff --git a/core/test/src/com/google/zxing/datamatrix/DataMatrixBlackBox2TestCase.java b/core/test/src/com/google/zxing/datamatrix/DataMatrixBlackBox2TestCase.java index 817ada71..a08f0bec 100644 --- a/core/test/src/com/google/zxing/datamatrix/DataMatrixBlackBox2TestCase.java +++ b/core/test/src/com/google/zxing/datamatrix/DataMatrixBlackBox2TestCase.java @@ -27,10 +27,10 @@ public final class DataMatrixBlackBox2TestCase extends AbstractBlackBoxTestCase public DataMatrixBlackBox2TestCase() { // TODO use MultiFormatReader here once Data Matrix decoder is done super("test/data/blackbox/datamatrix-2", new DataMatrixReader(), BarcodeFormat.DATA_MATRIX); - addTest(5, 5, 0.0f); - addTest(6, 6, 90.0f); - addTest(7, 7, 180.0f); - addTest(7, 7, 270.0f); + addTest(10, 10, 0.0f); + addTest(13, 13, 90.0f); + addTest(16, 16, 180.0f); + addTest(12, 12, 270.0f); } } -- 2.20.1