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.ReaderException;
20 import com.google.zxing.ResultPoint;
21 import com.google.zxing.common.BitMatrix;
22 import com.google.zxing.common.Collections;
23 import com.google.zxing.common.Comparator;
24 import com.google.zxing.common.DetectorResult;
25 import com.google.zxing.common.GridSampler;
26 import com.google.zxing.common.detector.MonochromeRectangleDetector;
28 import java.util.Enumeration;
29 import java.util.Hashtable;
30 import java.util.Vector;
33 * <p>Encapsulates logic that can detect a Data Matrix Code in an image, even if the Data Matrix Code
34 * is rotated or skewed, or partially obscured.</p>
38 public final class Detector {
40 //private static final int MAX_MODULES = 32;
42 // Trick to avoid creating new Integer objects below -- a sort of crude copy of
43 // the Integer.valueOf(int) optimization added in Java 5, not in J2ME
44 private static final Integer[] INTEGERS =
45 { new Integer(0), new Integer(1), new Integer(2), new Integer(3), new Integer(4) };
46 // No, can't use valueOf()
48 private final BitMatrix image;
49 private final MonochromeRectangleDetector rectangleDetector;
51 public Detector(BitMatrix image) {
53 rectangleDetector = new MonochromeRectangleDetector(image);
57 * <p>Detects a Data Matrix Code in an image.</p>
59 * @return {@link DetectorResult} encapsulating results of detecting a QR Code
60 * @throws ReaderException if no Data Matrix Code can be found
62 public DetectorResult detect() throws ReaderException {
64 ResultPoint[] cornerPoints = rectangleDetector.detect();
65 ResultPoint pointA = cornerPoints[0];
66 ResultPoint pointB = cornerPoints[1];
67 ResultPoint pointC = cornerPoints[2];
68 ResultPoint pointD = cornerPoints[3];
70 // Point A and D are across the diagonal from one another,
71 // as are B and C. Figure out which are the solid black lines
72 // by counting transitions
73 Vector transitions = new Vector(4);
74 transitions.addElement(transitionsBetween(pointA, pointB));
75 transitions.addElement(transitionsBetween(pointA, pointC));
76 transitions.addElement(transitionsBetween(pointB, pointD));
77 transitions.addElement(transitionsBetween(pointC, pointD));
78 Collections.insertionSort(transitions, new ResultPointsAndTransitionsComparator());
80 // Sort by number of transitions. First two will be the two solid sides; last two
81 // will be the two alternating black/white sides
82 ResultPointsAndTransitions lSideOne = (ResultPointsAndTransitions) transitions.elementAt(0);
83 ResultPointsAndTransitions lSideTwo = (ResultPointsAndTransitions) transitions.elementAt(1);
85 // Figure out which point is their intersection by tallying up the number of times we see the
86 // endpoints in the four endpoints. One will show up twice.
87 Hashtable pointCount = new Hashtable();
88 increment(pointCount, lSideOne.getFrom());
89 increment(pointCount, lSideOne.getTo());
90 increment(pointCount, lSideTwo.getFrom());
91 increment(pointCount, lSideTwo.getTo());
93 ResultPoint maybeTopLeft = null;
94 ResultPoint bottomLeft = null;
95 ResultPoint maybeBottomRight = null;
96 Enumeration points = pointCount.keys();
97 while (points.hasMoreElements()) {
98 ResultPoint point = (ResultPoint) points.nextElement();
99 Integer value = (Integer) pointCount.get(point);
100 if (value.intValue() == 2) {
101 bottomLeft = point; // this is definitely the bottom left, then -- end of two L sides
103 // Otherwise it's either top left or bottom right -- just assign the two arbitrarily now
104 if (maybeTopLeft == null) {
105 maybeTopLeft = point;
107 maybeBottomRight = point;
112 if (maybeTopLeft == null || bottomLeft == null || maybeBottomRight == null) {
113 throw ReaderException.getInstance();
116 // Bottom left is correct but top left and bottom right might be switched
117 ResultPoint[] corners = { maybeTopLeft, bottomLeft, maybeBottomRight };
118 // Use the dot product trick to sort them out
119 ResultPoint.orderBestPatterns(corners);
121 // Now we know which is which:
122 ResultPoint bottomRight = corners[0];
123 bottomLeft = corners[1];
124 ResultPoint topLeft = corners[2];
126 // Which point didn't we find in relation to the "L" sides? that's the top right corner
127 ResultPoint topRight;
128 if (!pointCount.containsKey(pointA)) {
130 } else if (!pointCount.containsKey(pointB)) {
132 } else if (!pointCount.containsKey(pointC)) {
138 // Next determine the dimension by tracing along the top or right side and counting black/white
139 // transitions. Since we start inside a black module, we should see a number of transitions
140 // equal to 1 less than the code dimension. Well, actually 2 less, because we are going to
141 // end on a black module:
143 // The top right point is actually the corner of a module, which is one of the two black modules
144 // adjacent to the white module at the top right. Tracing to that corner from either the top left
145 // or bottom right should work here. The number of transitions could be higher than it should be
146 // due to noise. So we try both and take the min.
148 int dimension = Math.min(transitionsBetween(topLeft, topRight).getTransitions(),
149 transitionsBetween(bottomRight, topRight).getTransitions());
150 if ((dimension & 0x01) == 1) {
151 // it can't be odd, so, round... up?
156 BitMatrix bits = sampleGrid(image, topLeft, bottomLeft, bottomRight, dimension);
157 return new DetectorResult(bits, new ResultPoint[] {pointA, pointB, pointC, pointD});
161 * Increments the Integer associated with a key by one.
163 private static void increment(Hashtable table, ResultPoint key) {
164 Integer value = (Integer) table.get(key);
165 table.put(key, value == null ? INTEGERS[1] : INTEGERS[value.intValue() + 1]);
168 private static BitMatrix sampleGrid(BitMatrix image,
170 ResultPoint bottomLeft,
171 ResultPoint bottomRight,
172 int dimension) throws ReaderException {
174 // We make up the top right point for now, based on the others.
175 // TODO: we actually found a fourth corner above and figured out which of two modules
176 // it was the corner of. We could use that here and adjust for perspective distortion.
177 float topRightX = (bottomRight.getX() - bottomLeft.getX()) + topLeft.getX();
178 float topRightY = (bottomRight.getY() - bottomLeft.getY()) + topLeft.getY();
180 // Note that unlike in the QR Code sampler, we didn't find the center of modules, but the
181 // very corners. So there is no 0.5f here; 0.0f is right.
182 GridSampler sampler = GridSampler.getInstance();
183 return sampler.sampleGrid(
205 * Counts the number of black/white transitions between two points, using something like Bresenham's algorithm.
207 private ResultPointsAndTransitions transitionsBetween(ResultPoint from, ResultPoint to) {
208 // See QR Code Detector, sizeOfBlackWhiteBlackRun()
209 int fromX = (int) from.getX();
210 int fromY = (int) from.getY();
211 int toX = (int) to.getX();
212 int toY = (int) to.getY();
213 boolean steep = Math.abs(toY - fromY) > Math.abs(toX - fromX);
223 int dx = Math.abs(toX - fromX);
224 int dy = Math.abs(toY - fromY);
225 int error = -dx >> 1;
226 int ystep = fromY < toY ? 1 : -1;
227 int xstep = fromX < toX ? 1 : -1;
229 boolean inBlack = image.get(steep ? fromY : fromX, steep ? fromX : fromY);
230 for (int x = fromX, y = fromY; x != toX; x += xstep) {
231 boolean isBlack = image.get(steep ? y : x, steep ? x : y);
232 if (isBlack != inBlack) {
245 return new ResultPointsAndTransitions(from, to, transitions);
249 * Simply encapsulates two points and a number of transitions between them.
251 private static class ResultPointsAndTransitions {
252 private final ResultPoint from;
253 private final ResultPoint to;
254 private final int transitions;
255 private ResultPointsAndTransitions(ResultPoint from, ResultPoint to, int transitions) {
258 this.transitions = transitions;
260 public ResultPoint getFrom() {
263 public ResultPoint getTo() {
266 public int getTransitions() {
269 public String toString() {
270 return from + "/" + to + '/' + transitions;
275 * Orders ResultPointsAndTransitions by number of transitions, ascending.
277 private static class ResultPointsAndTransitionsComparator implements Comparator {
278 public int compare(Object o1, Object o2) {
279 return ((ResultPointsAndTransitions) o1).getTransitions() - ((ResultPointsAndTransitions) o2).getTransitions();