From d629e79f409f9d03ff788613360b045726b6ee4b Mon Sep 17 00:00:00 2001 From: srowen Date: Mon, 4 Aug 2008 18:37:42 +0000 Subject: [PATCH] Initial checkin of Data Matrix detector. Still needs work, and is not enabled by default. git-svn-id: http://zxing.googlecode.com/svn/trunk@545 59b500cc-1b3d-0410-9834-0bbf25fbcc57 --- .../zxing/datamatrix/DataMatrixReader.java | 15 +- .../zxing/datamatrix/detector/Detector.java | 385 +++++++++++++++++- 2 files changed, 388 insertions(+), 12 deletions(-) diff --git a/core/src/com/google/zxing/datamatrix/DataMatrixReader.java b/core/src/com/google/zxing/datamatrix/DataMatrixReader.java index 75a3bf48..fd597abf 100644 --- a/core/src/com/google/zxing/datamatrix/DataMatrixReader.java +++ b/core/src/com/google/zxing/datamatrix/DataMatrixReader.java @@ -17,6 +17,7 @@ package com.google.zxing.datamatrix; import com.google.zxing.BarcodeFormat; +import com.google.zxing.DecodeHintType; import com.google.zxing.MonochromeBitmapSource; import com.google.zxing.Reader; import com.google.zxing.ReaderException; @@ -24,7 +25,9 @@ import com.google.zxing.Result; import com.google.zxing.ResultPoint; import com.google.zxing.common.BitMatrix; import com.google.zxing.common.DecoderResult; +import com.google.zxing.common.DetectorResult; import com.google.zxing.datamatrix.decoder.Decoder; +import com.google.zxing.datamatrix.detector.Detector; import java.util.Hashtable; @@ -53,15 +56,15 @@ public final class DataMatrixReader implements Reader { throws ReaderException { DecoderResult decoderResult; ResultPoint[] points; - //if (hints != null && hints.containsKey(DecodeHintType.PURE_BARCODE)) { + if (hints != null && hints.containsKey(DecodeHintType.PURE_BARCODE)) { BitMatrix bits = extractPureBits(image); decoderResult = decoder.decode(bits); points = NO_POINTS; - //} else { - // DetectorResult result = new Detector(image).detect(); - // decoderResult = decoder.decode(result.getBits()); - // points = result.getPoints(); - //} + } else { + DetectorResult result = new Detector(image).detect(); + decoderResult = decoder.decode(result.getBits()); + points = result.getPoints(); + } return new Result(decoderResult.getText(), decoderResult.getRawBytes(), points, BarcodeFormat.DATAMATRIX); } diff --git a/core/src/com/google/zxing/datamatrix/detector/Detector.java b/core/src/com/google/zxing/datamatrix/detector/Detector.java index b1e40f4d..af53b915 100644 --- a/core/src/com/google/zxing/datamatrix/detector/Detector.java +++ b/core/src/com/google/zxing/datamatrix/detector/Detector.java @@ -1,5 +1,5 @@ /* - * 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. @@ -18,16 +18,34 @@ package com.google.zxing.datamatrix.detector; 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; /** *

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.

* - * @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) { @@ -35,15 +53,370 @@ public final class Detector { } /** - *

Detects a Data Matrix Code in an image, simply.

+ *

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 */ - 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(); + } + } } -- 2.20.1