X-Git-Url: http://git.rot13.org/?p=zxing.git;a=blobdiff_plain;f=core%2Fsrc%2Fcom%2Fgoogle%2Fzxing%2Fdatamatrix%2Fdetector%2FDetector.java;h=206e5187c36ade495c10144926246d850dc8e3b0;hp=f120c36f7a7afa486958e3aa6db55295c0273934;hb=18e3e8522fb403891dc211e6de9681dcf1030b66;hpb=1170ad08b19f495ae38daf72a816ac60e5606aae diff --git a/core/src/com/google/zxing/datamatrix/detector/Detector.java b/core/src/com/google/zxing/datamatrix/detector/Detector.java index f120c36f..206e5187 100644 --- a/core/src/com/google/zxing/datamatrix/detector/Detector.java +++ b/core/src/com/google/zxing/datamatrix/detector/Detector.java @@ -16,17 +16,14 @@ package com.google.zxing.datamatrix.detector; -import com.google.zxing.MonochromeBitmapSource; -import com.google.zxing.ReaderException; +import com.google.zxing.NotFoundException; import com.google.zxing.ResultPoint; -import com.google.zxing.BlackPointEstimationMethod; -import com.google.zxing.common.BitArray; import com.google.zxing.common.BitMatrix; import com.google.zxing.common.Collections; import com.google.zxing.common.Comparator; import com.google.zxing.common.DetectorResult; -import com.google.zxing.common.GenericResultPoint; import com.google.zxing.common.GridSampler; +import com.google.zxing.common.detector.WhiteRectangleDetector; import java.util.Enumeration; import java.util.Hashtable; @@ -40,52 +37,33 @@ import java.util.Vector; */ public final class Detector { - private static final int MAX_MODULES = 32; - // 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 = { new Integer(0), new Integer(1), new Integer(2), new Integer(3), new Integer(4) }; + // No, can't use valueOf() - private final MonochromeBitmapSource image; + private final BitMatrix image; + private final WhiteRectangleDetector rectangleDetector; - public Detector(MonochromeBitmapSource image) { + public Detector(BitMatrix image) { this.image = image; + rectangleDetector = new WhiteRectangleDetector(image); } /** *

Detects a Data Matrix Code in an image.

* - * @return {@link DetectorResult} encapsulating results of detecting a QR Code - * @throws ReaderException if no Data Matrix Code can be found + * @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 ReaderException { - - if (!BlackPointEstimationMethod.TWO_D_SAMPLING.equals(image.getLastEstimationMethod())) { - image.estimateBlackPoint(BlackPointEstimationMethod.TWO_D_SAMPLING, 0); - } + public DetectorResult detect() throws NotFoundException { - int height = image.getHeight(); - int width = image.getWidth(); - int halfHeight = height >> 1; - int halfWidth = width >> 1; - int iSkip = Math.max(1, height / (MAX_MODULES << 3)); - int jSkip = Math.max(1, width / (MAX_MODULES << 3)); - - int minI = 0; - int maxI = height; - int minJ = 0; - int maxJ = width; - ResultPoint pointA = findCornerFromCenter(halfHeight, -iSkip, minI, maxI, halfWidth, 0, minJ, maxJ, halfWidth >> 1); - minI = (int) pointA.getY() - 1; - ResultPoint pointB = findCornerFromCenter(halfHeight, 0, minI, maxI, halfWidth, -jSkip, minJ, maxJ, halfHeight >> 1); - minJ = (int) pointB.getX() - 1; - ResultPoint pointC = findCornerFromCenter(halfHeight, 0, minI, maxI, halfWidth, jSkip, minJ, maxJ, halfHeight >> 1); - maxJ = (int) pointC.getX() + 1; - ResultPoint pointD = findCornerFromCenter(halfHeight, iSkip, minI, maxI, halfWidth, 0, minJ, maxJ, halfWidth >> 1); - maxI = (int) pointD.getY() + 1; - // Go try to find point A again with better information -- might have been off at first. - pointA = findCornerFromCenter(halfHeight, -iSkip, minI, maxI, halfWidth, 0, minJ, maxJ, halfWidth >> 2); + ResultPoint[] cornerPoints = rectangleDetector.detect(); + ResultPoint pointA = cornerPoints[0]; + ResultPoint pointB = cornerPoints[1]; + ResultPoint pointC = cornerPoints[2]; + ResultPoint pointD = cornerPoints[3]; // Point A and D are across the diagonal from one another, // as are B and C. Figure out which are the solid black lines @@ -130,13 +108,13 @@ public final class Detector { } if (maybeTopLeft == null || bottomLeft == null || maybeBottomRight == null) { - throw ReaderException.getInstance(); + throw NotFoundException.getNotFoundInstance(); } // Bottom left is correct but top left and bottom right might be switched - ResultPoint[] corners = new ResultPoint[] { maybeTopLeft, bottomLeft, maybeBottomRight }; + ResultPoint[] corners = { maybeTopLeft, bottomLeft, maybeBottomRight }; // Use the dot product trick to sort them out - GenericResultPoint.orderBestPatterns(corners); + ResultPoint.orderBestPatterns(corners); // Now we know which is which: ResultPoint bottomRight = corners[0]; @@ -162,85 +140,69 @@ 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, but, one will be more reliable since it's traced straight - // up or across, rather than at a slight angle. We use dot products to figure out which is - // better to use: - int dimension; - if (GenericResultPoint.crossProductZ(bottomLeft, bottomRight, topRight) < - GenericResultPoint.crossProductZ(topRight, topLeft, bottomLeft)) { - dimension = transitionsBetween(topLeft, topRight).getTransitions(); - } else { - dimension = transitionsBetween(bottomRight, topRight).getTransitions(); + // or bottom right should work here. + int dimension = Math.min(transitionsBetween(topLeft, topRight).getTransitions(), + transitionsBetween(bottomRight, topRight).getTransitions()); + if ((dimension & 0x01) == 1) { + // it can't be odd, so, round... up? + dimension++; } 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.max(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}); } /** - * Attempts to locate a corner of the barcode by scanning up, down, left or right from a center - * point which should be within the barcode. - * - * @param centerI center's i componennt (vertical) - * @param di change in i per step. If scanning up this is negative; down, positive; left or right, 0 - * @param minI minimum value of i to search through (meaningless when di == 0) - * @param maxI maximum value of i - * @param centerJ center's j component (horizontal) - * @param dj same as di but change in j per step instead - * @param minJ see minI - * @param maxJ see minJ - * @param maxWhiteRun maximum run of white pixels that can still be considered to be within - * the barcode - * @return a {@link ResultPoint} encapsulating the corner that was found - * @throws ReaderException if such a point cannot be found + * Calculates the position of the white top right module using the output of the rectangle detector */ - private ResultPoint findCornerFromCenter(int centerI, int di, int minI, int maxI, - int centerJ, int dj, int minJ, int maxJ, - int maxWhiteRun) throws ReaderException { - int[] lastRange = null; - for (int i = centerI, j = centerJ; - i < maxI && i >= minI && j < maxJ && j >= minJ; - i += di, j += dj) { - int[] range; - if (dj == 0) { - // horizontal slices, up and down - range = blackWhiteRange(i, maxWhiteRun, minJ, maxJ, true); - } else { - // vertical slices, left and right - range = blackWhiteRange(j, maxWhiteRun, minI, maxI, false); - } - if (range == null) { - if (lastRange == null) { - throw ReaderException.getInstance(); - } - // lastRange was found - if (dj == 0) { - int lastI = i - di; - if (lastRange[0] < centerJ) { - if (lastRange[1] > centerJ) { - // straddle, choose one or the other based on direction - return new GenericResultPoint(di > 0 ? lastRange[0] : lastRange[1], lastI); - } - return new GenericResultPoint(lastRange[0], lastI); - } else { - return new GenericResultPoint(lastRange[1], lastI); - } - } else { - int lastJ = j - dj; - if (lastRange[0] < centerI) { - if (lastRange[1] > centerI) { - return new GenericResultPoint(lastJ, dj < 0 ? lastRange[0] : lastRange[1]); - } - return new GenericResultPoint(lastJ, lastRange[0]); - } else { - return new GenericResultPoint(lastJ, lastRange[1]); - } - } - } - lastRange = range; - } - throw ReaderException.getInstance(); + private ResultPoint correctTopRight(ResultPoint bottomLeft, + ResultPoint bottomRight, + ResultPoint topLeft, + ResultPoint topRight, + int dimension) { + + 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 + 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()))); } /** @@ -251,104 +213,33 @@ public final class Detector { table.put(key, value == null ? INTEGERS[1] : INTEGERS[value.intValue() + 1]); } - /** - * Computes the start and end of a region of pixels, either horizontally or vertically, that could be - * part of a Data Matrix barcode. - * - * @param fixedDimension if scanning horizontally, this is the row (the fixed vertical location) where - * we are scanning. If scanning vertically it's the colummn, the fixed horizontal location - * @param maxWhiteRun largest run of white pixels that can still be considered part of the barcode region - * @param minDim minimum pixel location, horizontally or vertically, to consider - * @param maxDim maximum pixel location, horizontally or vertically, to consider - * @param horizontal if true, we're scanning left-right, instead of up-down - * @return int[] with start and end of found range, or null if no such range is found (e.g. only white was found) - */ - private int[] blackWhiteRange(int fixedDimension, int maxWhiteRun, int minDim, int maxDim, boolean horizontal) { - - int center = (minDim + maxDim) / 2; - - BitArray rowOrColumn = horizontal ? image.getBlackRow(fixedDimension, null, 0, image.getWidth()) - : image.getBlackColumn(fixedDimension, null, 0, image.getHeight()); - - // Scan left/up first - int start = center; - while (start >= minDim) { - if (rowOrColumn.get(start)) { - start--; - } else { - int whiteRunStart = start; - do { - start--; - } while (start >= minDim && !rowOrColumn.get(start)); - int whiteRunSize = whiteRunStart - start; - if (start < minDim || whiteRunSize > maxWhiteRun) { - start = whiteRunStart + 1; // back up - break; - } - } - } - start++; - - // Then try right/down - int end = center; - while (end < maxDim) { - if (rowOrColumn.get(end)) { - end++; - } else { - int whiteRunStart = end; - do { - end++; - } while (end < maxDim && !rowOrColumn.get(end)); - int whiteRunSize = end - whiteRunStart; - if (end >= maxDim || whiteRunSize > maxWhiteRun) { - end = whiteRunStart - 1; - break; - } - } - } - end--; - - if (end > start) { - return new int[] { start, end }; - } else { - return null; - } - } - - private static BitMatrix sampleGrid(MonochromeBitmapSource image, + private static BitMatrix sampleGrid(BitMatrix image, ResultPoint topLeft, ResultPoint bottomLeft, ResultPoint bottomRight, - int dimension) throws ReaderException { - - // 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(); + ResultPoint topRight, + int dimension) throws NotFoundException { - // 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()); } /** @@ -376,15 +267,18 @@ public final class Detector { int ystep = fromY < toY ? 1 : -1; int xstep = fromX < toX ? 1 : -1; int transitions = 0; - boolean inBlack = image.isBlack(steep ? fromY : fromX, steep ? fromX : fromY); + boolean inBlack = image.get(steep ? fromY : fromX, steep ? fromX : fromY); for (int x = fromX, y = fromY; x != toX; x += xstep) { - boolean isBlack = image.isBlack(steep ? y : x, steep ? x : y); - if (isBlack == !inBlack) { + boolean isBlack = image.get(steep ? y : x, steep ? x : y); + if (isBlack != inBlack) { transitions++; inBlack = isBlack; } error += dy; if (error > 0) { + if (y == toY) { + break; + } y += ystep; error -= dx; }