2 * Copyright 2008 ZXing authors
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
8 * http://www.apache.org/licenses/LICENSE-2.0
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
17 package com.google.zxing.datamatrix.detector;
19 import com.google.zxing.MonochromeBitmapSource;
20 import com.google.zxing.ReaderException;
21 import com.google.zxing.ResultPoint;
22 import com.google.zxing.common.BitMatrix;
23 import com.google.zxing.common.Collections;
24 import com.google.zxing.common.Comparator;
25 import com.google.zxing.common.DetectorResult;
26 import com.google.zxing.common.GenericResultPoint;
27 import com.google.zxing.common.GridSampler;
28 import com.google.zxing.common.detector.MonochromeRectangleDetector;
30 import java.util.Enumeration;
31 import java.util.Hashtable;
32 import java.util.Vector;
35 * <p>Encapsulates logic that can detect a Data Matrix Code in an image, even if the Data Matrix Code
36 * is rotated or skewed, or partially obscured.</p>
40 public final class Detector {
42 private static final int MAX_MODULES = 32;
44 // Trick to avoid creating new Integer objects below -- a sort of crude copy of
45 // the Integer.valueOf(int) optimization added in Java 5, not in J2ME
46 private static final Integer[] INTEGERS =
47 { new Integer(0), new Integer(1), new Integer(2), new Integer(3), new Integer(4) };
49 private final MonochromeBitmapSource image;
50 private final MonochromeRectangleDetector rectangleDetector;
52 public Detector(MonochromeBitmapSource image) {
54 rectangleDetector = new MonochromeRectangleDetector(image);
58 * <p>Detects a Data Matrix Code in an image.</p>
60 * @return {@link DetectorResult} encapsulating results of detecting a QR Code
61 * @throws ReaderException if no Data Matrix Code can be found
63 public DetectorResult detect() throws ReaderException {
65 ResultPoint[] cornerPoints = rectangleDetector.detect();
66 ResultPoint pointA = cornerPoints[0];
67 ResultPoint pointB = cornerPoints[1];
68 ResultPoint pointC = cornerPoints[2];
69 ResultPoint pointD = cornerPoints[3];
71 // Point A and D are across the diagonal from one another,
72 // as are B and C. Figure out which are the solid black lines
73 // by counting transitions
74 Vector transitions = new Vector(4);
75 transitions.addElement(transitionsBetween(pointA, pointB));
76 transitions.addElement(transitionsBetween(pointA, pointC));
77 transitions.addElement(transitionsBetween(pointB, pointD));
78 transitions.addElement(transitionsBetween(pointC, pointD));
79 Collections.insertionSort(transitions, new ResultPointsAndTransitionsComparator());
81 // Sort by number of transitions. First two will be the two solid sides; last two
82 // will be the two alternating black/white sides
83 ResultPointsAndTransitions lSideOne = (ResultPointsAndTransitions) transitions.elementAt(0);
84 ResultPointsAndTransitions lSideTwo = (ResultPointsAndTransitions) transitions.elementAt(1);
86 // Figure out which point is their intersection by tallying up the number of times we see the
87 // endpoints in the four endpoints. One will show up twice.
88 Hashtable pointCount = new Hashtable();
89 increment(pointCount, lSideOne.getFrom());
90 increment(pointCount, lSideOne.getTo());
91 increment(pointCount, lSideTwo.getFrom());
92 increment(pointCount, lSideTwo.getTo());
94 ResultPoint maybeTopLeft = null;
95 ResultPoint bottomLeft = null;
96 ResultPoint maybeBottomRight = null;
97 Enumeration points = pointCount.keys();
98 while (points.hasMoreElements()) {
99 ResultPoint point = (ResultPoint) points.nextElement();
100 Integer value = (Integer) pointCount.get(point);
101 if (value.intValue() == 2) {
102 bottomLeft = point; // this is definitely the bottom left, then -- end of two L sides
104 // Otherwise it's either top left or bottom right -- just assign the two arbitrarily now
105 if (maybeTopLeft == null) {
106 maybeTopLeft = point;
108 maybeBottomRight = point;
113 if (maybeTopLeft == null || bottomLeft == null || maybeBottomRight == null) {
114 throw ReaderException.getInstance();
117 // Bottom left is correct but top left and bottom right might be switched
118 ResultPoint[] corners = { maybeTopLeft, bottomLeft, maybeBottomRight };
119 // Use the dot product trick to sort them out
120 GenericResultPoint.orderBestPatterns(corners);
122 // Now we know which is which:
123 ResultPoint bottomRight = corners[0];
124 bottomLeft = corners[1];
125 ResultPoint topLeft = corners[2];
127 // Which point didn't we find in relation to the "L" sides? that's the top right corner
128 ResultPoint topRight;
129 if (!pointCount.containsKey(pointA)) {
131 } else if (!pointCount.containsKey(pointB)) {
133 } else if (!pointCount.containsKey(pointC)) {
139 // Next determine the dimension by tracing along the top or right side and counting black/white
140 // transitions. Since we start inside a black module, we should see a number of transitions
141 // equal to 1 less than the code dimension. Well, actually 2 less, because we are going to
142 // end on a black module:
144 // The top right point is actually the corner of a module, which is one of the two black modules
145 // adjacent to the white module at the top right. Tracing to that corner from either the top left
146 // or bottom right should work here, but, one will be more reliable since it's traced straight
147 // up or across, rather than at a slight angle. We use dot products to figure out which is
150 if (GenericResultPoint.crossProductZ(bottomLeft, bottomRight, topRight) <
151 GenericResultPoint.crossProductZ(topRight, topLeft, bottomLeft)) {
152 dimension = transitionsBetween(topLeft, topRight).getTransitions();
154 dimension = transitionsBetween(bottomRight, topRight).getTransitions();
158 BitMatrix bits = sampleGrid(image, topLeft, bottomLeft, bottomRight, dimension);
159 return new DetectorResult(bits, new ResultPoint[] {pointA, pointB, pointC, pointD});
163 * Increments the Integer associated with a key by one.
165 private static void increment(Hashtable table, ResultPoint key) {
166 Integer value = (Integer) table.get(key);
167 table.put(key, value == null ? INTEGERS[1] : INTEGERS[value.intValue() + 1]);
170 private static BitMatrix sampleGrid(MonochromeBitmapSource image,
172 ResultPoint bottomLeft,
173 ResultPoint bottomRight,
174 int dimension) throws ReaderException {
176 // We make up the top right point for now, based on the others.
177 // TODO: we actually found a fourth corner above and figured out which of two modules
178 // it was the corner of. We could use that here and adjust for perspective distortion.
179 float topRightX = (bottomRight.getX() - bottomLeft.getX()) + topLeft.getX();
180 float topRightY = (bottomRight.getY() - bottomLeft.getY()) + topLeft.getY();
182 // Note that unlike in the QR Code sampler, we didn't find the center of modules, but the
183 // very corners. So there is no 0.5f here; 0.0f is right.
184 GridSampler sampler = GridSampler.getInstance();
185 return sampler.sampleGrid(
207 * Counts the number of black/white transitions between two points, using something like Bresenham's algorithm.
209 private ResultPointsAndTransitions transitionsBetween(ResultPoint from, ResultPoint to) {
210 // See QR Code Detector, sizeOfBlackWhiteBlackRun()
211 int fromX = (int) from.getX();
212 int fromY = (int) from.getY();
213 int toX = (int) to.getX();
214 int toY = (int) to.getY();
215 boolean steep = Math.abs(toY - fromY) > Math.abs(toX - fromX);
225 int dx = Math.abs(toX - fromX);
226 int dy = Math.abs(toY - fromY);
227 int error = -dx >> 1;
228 int ystep = fromY < toY ? 1 : -1;
229 int xstep = fromX < toX ? 1 : -1;
231 boolean inBlack = image.isBlack(steep ? fromY : fromX, steep ? fromX : fromY);
232 for (int x = fromX, y = fromY; x != toX; x += xstep) {
233 boolean isBlack = image.isBlack(steep ? y : x, steep ? x : y);
234 if (isBlack != inBlack) {
244 return new ResultPointsAndTransitions(from, to, transitions);
248 * Simply encapsulates two points and a number of transitions between them.
250 private static class ResultPointsAndTransitions {
251 private final ResultPoint from;
252 private final ResultPoint to;
253 private final int transitions;
254 private ResultPointsAndTransitions(ResultPoint from, ResultPoint to, int transitions) {
257 this.transitions = transitions;
259 public ResultPoint getFrom() {
262 public ResultPoint getTo() {
265 public int getTransitions() {
268 public String toString() {
269 return from + "/" + to + '/' + transitions;
274 * Orders ResultPointsAndTransitions by number of transitions, ascending.
276 private static class ResultPointsAndTransitionsComparator implements Comparator {
277 public int compare(Object o1, Object o2) {
278 return ((ResultPointsAndTransitions) o1).getTransitions() - ((ResultPointsAndTransitions) o2).getTransitions();