From db18533772d29f6c2833396af70c5a93c0dc05ea Mon Sep 17 00:00:00 2001 From: srowen Date: Fri, 3 Sep 2010 07:50:47 +0000 Subject: [PATCH] David Olivier's Data Matrix improvements git-svn-id: http://zxing.googlecode.com/svn/trunk@1573 59b500cc-1b3d-0410-9834-0bbf25fbcc57 --- AUTHORS | 1 + .../detector/WhiteRectangleDetector.java | 317 ++++++++++++++++++ .../zxing/datamatrix/detector/Detector.java | 144 +++++--- .../DataMatrixBlackBox1TestCase.java | 4 +- .../DataMatrixBlackBox2TestCase.java | 8 +- 5 files changed, 430 insertions(+), 44 deletions(-) create mode 100644 core/src/com/google/zxing/common/detector/WhiteRectangleDetector.java diff --git a/AUTHORS b/AUTHORS index a4d473f2..e3657985 100644 --- a/AUTHORS +++ b/AUTHORS @@ -15,6 +15,7 @@ Daniel Switkin (Google) Dave MacLachlan (Google) David Phillip Oster (Google) David Albert (Bug Labs) +David Olivier Diego Pierotto Eduardo Castillejo (University of Deusto) Eric Kobrin (Velocitude) diff --git a/core/src/com/google/zxing/common/detector/WhiteRectangleDetector.java b/core/src/com/google/zxing/common/detector/WhiteRectangleDetector.java new file mode 100644 index 00000000..66a32195 --- /dev/null +++ b/core/src/com/google/zxing/common/detector/WhiteRectangleDetector.java @@ -0,0 +1,317 @@ +/* + * Copyright 2010 ZXing authors + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +package com.google.zxing.common.detector; + +import com.google.zxing.NotFoundException; +import com.google.zxing.ResultPoint; +import com.google.zxing.common.BitMatrix; + +/** + *

+ * Detects a candidate barcode-like rectangular region within an image. It + * starts around the center of the image, increases the size of the candidate + * region until it finds a white rectangular region. By keeping track of the + * last black points it encountered, it determines the corners of the barcode. + *

+ * + * @author David Olivier + */ +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; + private final int width; + + public WhiteRectangleDetector(BitMatrix image) { + this.image = image; + height = image.getHeight(); + width = image.getWidth(); + } + + /** + *

+ * Detects a candidate barcode-like rectangular region within an image. It + * starts around the center of the image, increases the size of the candidate + * region until it finds a white rectangular region. + *

+ * + * @return {@link ResultPoint}[] describing the corners of the rectangular + * region. The first and last points are opposed on the diagonal, as + * are the second and third. The first point will be the topmost + * point and the last, the bottommost. The second point will be + * leftmost and the third, the rightmost + * @throws NotFoundException if no Data Matrix Code can be found + */ + public ResultPoint[] detect() throws NotFoundException { + + int left = (width - INIT_SIZE) / 2; + int right = (width + INIT_SIZE) / 2; + int up = (height - INIT_SIZE) / 2; + int down = (height + INIT_SIZE) / 2; + boolean sizeExceeded = false; + boolean aBlackPointFoundOnBorder = true; + boolean atLeastOneBlackPointFoundOnBorder = false; + + while (aBlackPointFoundOnBorder) { + + aBlackPointFoundOnBorder = false; + + // ..... + // . | + // ..... + boolean rightBorderNotWhite = true; + while (rightBorderNotWhite && right < width) { + rightBorderNotWhite = containsBlackPoint(up, down, right, false); + if (rightBorderNotWhite) { + right++; + aBlackPointFoundOnBorder = true; + } + } + + // ..... + // . . + // .___. + boolean bottomBorderNotWhite = true; + while (bottomBorderNotWhite && down < height) { + bottomBorderNotWhite = containsBlackPoint(left, right, down, true); + if (bottomBorderNotWhite) { + down++; + aBlackPointFoundOnBorder = true; + } + } + + // ..... + // | . + // ..... + boolean leftBorderNotWhite = true; + while (leftBorderNotWhite && left >= 0) { + leftBorderNotWhite = containsBlackPoint(up, down, left, false); + if (leftBorderNotWhite) { + left--; + aBlackPointFoundOnBorder = true; + } + } + + // .___. + // . . + // ..... + boolean topBorderNotWhite = true; + while (topBorderNotWhite && up >= 0) { + topBorderNotWhite = containsBlackPoint(left, right, up, true); + if (topBorderNotWhite) { + up--; + aBlackPointFoundOnBorder = true; + } + } + + if (right >= width || down >= height || up < 0 || left < 0) { + sizeExceeded = true; + break; + } + + if (aBlackPointFoundOnBorder) { + atLeastOneBlackPointFoundOnBorder = true; + } + + } + + 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; + } + + return centerEdges(y, z, x, t); + + } else { + throw NotFoundException.getNotFoundInstance(); + } + } + + /** + * recenters the points of a constant distance towards the center + * + * @param y bottom most point + * @param z left most point + * @param x right most point + * @param t top most point + * @return {@link ResultPoint}[] describing the corners of the rectangular + * region. The first and last points are opposed on the diagonal, as + * are the second and third. The first point will be the topmost + * point and the last, the bottommost. The second point will be + * leftmost and the third, the rightmost + */ + private ResultPoint[] centerEdges(ResultPoint y, ResultPoint z, + ResultPoint x, ResultPoint t) { + + // + // t t + // z x + // x OR z + // y y + // + + float yi = y.getX(), yj = y.getY(), zi = z.getX(), zj = z.getY(), xi = x + .getX(), xj = x.getY(), ti = t.getX(), tj = t.getY(); + + final int corr = 1; + if (yi < width / 2) { + return new ResultPoint[]{new ResultPoint(ti - corr, tj + corr), + new ResultPoint(zi + corr, zj + corr), + new ResultPoint(xi - corr, xj - corr), + new ResultPoint(yi + corr, yj - corr)}; + } else { + return new ResultPoint[]{new ResultPoint(ti + corr, tj + corr), + new ResultPoint(zi + corr, zj - corr), + new ResultPoint(xi - corr, xj + corr), + new ResultPoint(yi - corr, yj - corr)}; + } + } + + // 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 + * + * @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 true if a black point has been found, else false. + */ + private boolean containsBlackPoint(int a, int b, int fixed, boolean horizontal) { + + if (horizontal) { + for (int x = a; x < b; x++) { + if (image.get(x, fixed)) { + return true; + } + } + } else { + for (int y = a; y < b; y++) { + if (image.get(fixed, y)) { + return true; + } + } + } + + return false; + } + +} \ No newline at end of file diff --git a/core/src/com/google/zxing/datamatrix/detector/Detector.java b/core/src/com/google/zxing/datamatrix/detector/Detector.java index 5915865a..512a35f0 100644 --- a/core/src/com/google/zxing/datamatrix/detector/Detector.java +++ b/core/src/com/google/zxing/datamatrix/detector/Detector.java @@ -23,7 +23,7 @@ import com.google.zxing.common.Collections; import com.google.zxing.common.Comparator; import com.google.zxing.common.DetectorResult; import com.google.zxing.common.GridSampler; -import com.google.zxing.common.detector.MonochromeRectangleDetector; +import com.google.zxing.common.detector.WhiteRectangleDetector; import java.util.Enumeration; import java.util.Hashtable; @@ -37,7 +37,7 @@ import java.util.Vector; */ public final class Detector { - //private static final int MAX_MODULES = 32; + 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 @@ -46,17 +46,17 @@ public final class Detector { // No, can't use valueOf() private final BitMatrix image; - private final MonochromeRectangleDetector rectangleDetector; + private final WhiteRectangleDetector rectangleDetector; public Detector(BitMatrix image) { this.image = image; - rectangleDetector = new MonochromeRectangleDetector(image); + rectangleDetector = new WhiteRectangleDetector(image); } /** *

Detects a Data Matrix Code in an image.

* - * @return {@link DetectorResult} encapsulating results of detecting a QR Code + * @return {@link DetectorResult} encapsulating results of detecting a Data Matrix Code * @throws NotFoundException if no Data Matrix Code can be found */ public DetectorResult detect() throws NotFoundException { @@ -82,6 +82,12 @@ 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(); @@ -142,10 +148,8 @@ 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. The number of transitions could be higher than it should be - // due to noise. So we try both and take the min. - - int dimension = Math.min(transitionsBetween(topLeft, topRight).getTransitions(), + // or bottom right should work here. + int dimension = Math.max(transitionsBetween(topLeft, topRight).getTransitions(), transitionsBetween(bottomRight, topRight).getTransitions()); if ((dimension & 0x01) == 1) { // it can't be odd, so, round... up? @@ -153,8 +157,79 @@ public final class Detector { } dimension += 2; - BitMatrix bits = sampleGrid(image, topLeft, bottomLeft, bottomRight, dimension); - return new DetectorResult(bits, new ResultPoint[] {pointA, pointB, pointC, pointD}); + //correct top right point to match the white module + 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(), + transitionsBetween(bottomRight, correctedTopRight).getTransitions()); + dimension2++; + if ((dimension2 & 0x01) == 1) { + dimension2++; + } + + BitMatrix bits = sampleGrid(image, topLeft, bottomLeft, bottomRight, correctedTopRight, dimension2); + + return new DetectorResult(bits, new ResultPoint[]{topLeft, bottomLeft, bottomRight, correctedTopRight}); + } + + /** + * Calculates the position of the white top right module using the output of the rectangle detector + */ + private ResultPoint correctTopRight(ResultPoint bottomLeft, + ResultPoint bottomRight, + 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); + } + + // L2 distance + private static int distance(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()))); } /** @@ -169,36 +244,29 @@ public final class Detector { ResultPoint topLeft, ResultPoint bottomLeft, ResultPoint bottomRight, + ResultPoint topRight, int dimension) throws NotFoundException { - // We make up the top right point for now, based on the others. - // TODO: we actually found a fourth corner above and figured out which of two modules - // it was the corner of. We could use that here and adjust for perspective distortion. - float topRightX = (bottomRight.getX() - bottomLeft.getX()) + topLeft.getX(); - float topRightY = (bottomRight.getY() - bottomLeft.getY()) + topLeft.getY(); - - // Note that unlike in the QR Code sampler, we didn't find the center of modules, but the - // very corners. So there is no 0.5f here; 0.0f is right. GridSampler sampler = GridSampler.getInstance(); - return sampler.sampleGrid( - image, - dimension, - 0.0f, - 0.0f, - dimension, - 0.0f, - dimension, - dimension, - 0.0f, - dimension, - topLeft.getX(), - topLeft.getY(), - topRightX, - topRightY, - bottomRight.getX(), - bottomRight.getY(), - bottomLeft.getX(), - bottomLeft.getY()); + + return sampler.sampleGrid(image, + dimension, + 0.5f, + 0.5f, + dimension - 0.5f, + 0.5f, + dimension - 0.5f, + dimension - 0.5f, + 0.5f, + dimension - 0.5f, + topLeft.getX(), + topLeft.getY(), + topRight.getX(), + topRight.getY(), + bottomRight.getX(), + bottomRight.getY(), + bottomLeft.getX(), + bottomLeft.getY()); } /** diff --git a/core/test/src/com/google/zxing/datamatrix/DataMatrixBlackBox1TestCase.java b/core/test/src/com/google/zxing/datamatrix/DataMatrixBlackBox1TestCase.java index a4cc8810..14cc3cbc 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(7, 7, 90.0f); + addTest(4, 4, 90.0f); addTest(6, 6, 180.0f); - addTest(4, 4, 270.0f); + addTest(6, 6, 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 b33a7963..817ada71 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(4, 4, 0.0f); - addTest(1, 1, 90.0f); - addTest(3, 3, 180.0f); - addTest(1, 1, 270.0f); + addTest(5, 5, 0.0f); + addTest(6, 6, 90.0f); + addTest(7, 7, 180.0f); + addTest(7, 7, 270.0f); } } -- 2.20.1