/*
- * Copyright 2007 ZXing authors
+ * Copyright 2008 ZXing authors
*
* Licensed under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
import com.google.zxing.MonochromeBitmapSource;
import com.google.zxing.ReaderException;
+import com.google.zxing.ResultPoint;
+import com.google.zxing.BlackPointEstimationMethod;
+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 java.util.Enumeration;
+import java.util.Hashtable;
+import java.util.Vector;
/**
* <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 bbrown@google.com (Brian Brown)
+ * @author srowen@google.com (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) };
+
private final MonochromeBitmapSource image;
public Detector(MonochromeBitmapSource image) {
}
/**
- * <p>Detects a Data Matrix Code in an image, simply.</p>
+ * <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
*/
- public DetectorResult detect() {
- // TODO
- return new DetectorResult(null, null);
+ public DetectorResult detect() throws ReaderException {
+
+ if (!BlackPointEstimationMethod.TWO_D_SAMPLING.equals(image.getLastEstimationMethod())) {
+ image.estimateBlackPoint(BlackPointEstimationMethod.TWO_D_SAMPLING, 0);
+ }
+
+ int height = image.getHeight();
+ int width = image.getWidth();
+ int halfHeight = height >> 1;
+ int halfWidth = width >> 1;
+ int iSkip = Math.max(1, height / (MAX_MODULES << 2));
+ int jSkip = Math.max(1, width / (MAX_MODULES << 2));
+
+ int minI = 0;
+ int maxI = height;
+ int minJ = 0;
+ int maxJ = width;
+ ResultPoint pointA = findCornerFromCenter(halfHeight, -iSkip, minI, maxI, halfWidth, 0, minJ, maxJ, halfWidth >> 2);
+ minI = (int) pointA.getY() - 1;
+ ResultPoint pointB = findCornerFromCenter(halfHeight, 0, minI, maxI, halfWidth, -jSkip, minJ, maxJ, halfHeight >> 2);
+ minJ = (int) pointB.getX() - 1;
+ ResultPoint pointC = findCornerFromCenter(halfHeight, 0, minI, maxI, halfWidth, jSkip, minJ, maxJ, halfHeight >> 2);
+ maxJ = (int) pointC.getX() + 1;
+ ResultPoint pointD = findCornerFromCenter(halfHeight, iSkip, minI, maxI, halfWidth, 0, minJ, maxJ, halfWidth >> 2);
+ 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);
+
+ // Point A and D are across the diagonal from one another,
+ // as are B and C. Figure out which are the solid black lines
+ // by counting transitions
+ Vector transitions = new Vector(4);
+ transitions.addElement(transitionsBetween(pointA, pointB));
+ transitions.addElement(transitionsBetween(pointA, pointC));
+ transitions.addElement(transitionsBetween(pointB, pointD));
+ transitions.addElement(transitionsBetween(pointC, pointD));
+ Collections.insertionSort(transitions, new ResultPointsAndTransitionsComparator());
+
+ // Sort by number of transitions. First two will be the two solid sides; last two
+ // will be the two alternating black/white sides
+ ResultPointsAndTransitions lSideOne = (ResultPointsAndTransitions) transitions.elementAt(0);
+ ResultPointsAndTransitions lSideTwo = (ResultPointsAndTransitions) transitions.elementAt(1);
+
+ // 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();
+ increment(pointCount, lSideOne.getFrom());
+ increment(pointCount, lSideOne.getTo());
+ increment(pointCount, lSideTwo.getFrom());
+ increment(pointCount, lSideTwo.getTo());
+
+ ResultPoint maybeTopLeft = null;
+ ResultPoint bottomLeft = null;
+ ResultPoint maybeBottomRight = null;
+ Enumeration points = pointCount.keys();
+ while (points.hasMoreElements()) {
+ ResultPoint point = (ResultPoint) points.nextElement();
+ Integer value = (Integer) pointCount.get(point);
+ if (value.intValue() == 2) {
+ bottomLeft = point; // this is definitely the bottom left, then -- end of two L sides
+ } else {
+ // Otherwise it's either top left or bottom right -- just assign the two arbitrarily now
+ if (maybeTopLeft == null) {
+ maybeTopLeft = point;
+ } else {
+ maybeBottomRight = point;
+ }
+ }
+ }
+
+ // Bottom left is correct but top left and bottom right might be switched
+ ResultPoint[] corners = new ResultPoint[] { maybeTopLeft, bottomLeft, maybeBottomRight };
+ // Use the dot product trick to sort them out
+ GenericResultPoint.orderBestPatterns(corners);
+
+ // Now we know which is which:
+ ResultPoint bottomRight = corners[0];
+ bottomLeft = corners[1];
+ ResultPoint topLeft = corners[2];
+
+ // Which point didn't we find in relation to the "L" sides? that's the top right corner
+ ResultPoint topRight;
+ if (!pointCount.containsKey(pointA)) {
+ topRight = pointA;
+ } else if (!pointCount.containsKey(pointB)) {
+ topRight = pointB;
+ } else if (!pointCount.containsKey(pointC)) {
+ topRight = pointC;
+ } else {
+ topRight = pointD;
+ }
+
+ // Next determine the dimension by tracing along the top or right side and counting black/white
+ // transitions. Since we start inside a black module, we should see a number of transitions
+ // equal to 1 less than the code dimension. Well, actually 2 less, because we are going to
+ // end on a black module:
+
+ // 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();
+ }
+ dimension += 2;
+
+ BitMatrix bits = sampleGrid(image, topLeft, bottomLeft, bottomRight, dimension);
+ return new DetectorResult(bits, new ResultPoint[] {pointA, pointB, pointC, pointD});
+ }
+
+ /**
+ * 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
+ */
+ 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");
+ }
+
+ /**
+ * Increments the Integer associated with a key by one.
+ */
+ private static void increment(Hashtable table, ResultPoint key) {
+ Integer value = (Integer) table.get(key);
+ 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;
+
+ // Scan left/up first
+ int start = center;
+ while (start >= minDim) {
+ if (horizontal ? image.isBlack(start, fixedDimension) : image.isBlack(fixedDimension, start)) {
+ start--;
+ } else {
+ int whiteRunStart = start;
+ do {
+ start--;
+ } while (start >= minDim &&
+ !(horizontal ? image.isBlack(start, fixedDimension) : image.isBlack(fixedDimension, 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 (horizontal ? image.isBlack(end, fixedDimension) : image.isBlack(fixedDimension, end)) {
+ end++;
+ } else {
+ int whiteRunStart = end;
+ do {
+ end++;
+ } while (end < maxDim &&
+ !(horizontal ? image.isBlack(end, fixedDimension) : image.isBlack(fixedDimension, 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,
+ 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();
+
+ // 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());
+ }
+
+ /**
+ * Counts the number of black/white transitions between two points, using something like Bresenham's algorithm.
+ */
+ private ResultPointsAndTransitions transitionsBetween(ResultPoint from, ResultPoint to) {
+ // See QR Code Detector, sizeOfBlackWhiteBlackRun()
+ int fromX = (int) from.getX();
+ int fromY = (int) from.getY();
+ int toX = (int) to.getX();
+ int toY = (int) to.getY();
+ boolean steep = Math.abs(toY - fromY) > Math.abs(toX - fromX);
+ if (steep) {
+ int temp = fromX;
+ fromX = fromY;
+ fromY = temp;
+ temp = toX;
+ toX = toY;
+ toY = temp;
+ }
+
+ int dx = Math.abs(toX - fromX);
+ int dy = Math.abs(toY - fromY);
+ int error = -dx >> 1;
+ 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);
+ for (int x = fromX, y = fromY; x != toX; x += xstep) {
+ boolean isBlack = image.isBlack(steep ? y : x, steep ? x : y);
+ if (isBlack == !inBlack) {
+ transitions++;
+ inBlack = isBlack;
+ }
+ error += dy;
+ if (error > 0) {
+ y += ystep;
+ error -= dx;
+ }
+ }
+ return new ResultPointsAndTransitions(from, to, transitions);
+ }
+
+ /**
+ * Simply encapsulates two points and a number of transitions between them.
+ */
+ private static class ResultPointsAndTransitions {
+ private final ResultPoint from;
+ private final ResultPoint to;
+ private final int transitions;
+ private ResultPointsAndTransitions(ResultPoint from, ResultPoint to, int transitions) {
+ this.from = from;
+ this.to = to;
+ this.transitions = transitions;
+ }
+ public ResultPoint getFrom() {
+ return from;
+ }
+ public ResultPoint getTo() {
+ return to;
+ }
+ public int getTransitions() {
+ return transitions;
+ }
+ public String toString() {
+ return from + "/" + to + '/' + transitions;
+ }
+ }
+
+ /**
+ * Orders ResultPointsAndTransitions by number of transitions, ascending.
+ */
+ private static class ResultPointsAndTransitionsComparator implements Comparator {
+ public int compare(Object o1, Object o2) {
+ return ((ResultPointsAndTransitions) o1).getTransitions() - ((ResultPointsAndTransitions) o2).getTransitions();
+ }
+ }
}
projects / zxing.git / commitdiff