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;
* <p>Encapsulates logic that can detect a Data Matrix Code in an image, even if the Data Matrix Code
* is rotated or skewed, or partially obscured.</p>
*
- * @author srowen@google.com (Sean Owen)
+ * @author Sean Owen
*/
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);
}
/**
* <p>Detects a Data Matrix Code in an image.</p>
*
- * @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
}
}
+ if (maybeTopLeft == null || bottomLeft == null || maybeBottomRight == null) {
+ 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];
// 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 new ReaderException("Center of image not within barcode");
- }
- // 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 new ReaderException("Couldn't find an end to barcode");
+ 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())));
}
/**
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;
- }
- }
- }
-
- // 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;
- }
- }
- }
-
- 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());
}
/**
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;
}
projects / zxing.git / blobdiff