2 * Copyright 2009 ZXing authors
\r
4 * Licensed under the Apache License, Version 2.0 (the "License");
\r
5 * you may not use this file except in compliance with the License.
\r
6 * You may obtain a copy of the License at
\r
8 * http://www.apache.org/licenses/LICENSE-2.0
\r
10 * Unless required by applicable law or agreed to in writing, software
\r
11 * distributed under the License is distributed on an "AS IS" BASIS,
\r
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
\r
13 * See the License for the specific language governing permissions and
\r
14 * limitations under the License.
\r
17 package com.google.zxing.multi.qrcode.detector;
\r
19 import com.google.zxing.DecodeHintType;
\r
20 import com.google.zxing.MonochromeBitmapSource;
\r
21 import com.google.zxing.ReaderException;
\r
22 import com.google.zxing.ResultPoint;
\r
23 import com.google.zxing.common.BitArray;
\r
24 import com.google.zxing.common.Collections;
\r
25 import com.google.zxing.common.Comparator;
\r
26 import com.google.zxing.qrcode.detector.FinderPattern;
\r
27 import com.google.zxing.qrcode.detector.FinderPatternFinder;
\r
28 import com.google.zxing.qrcode.detector.FinderPatternInfo;
\r
30 import java.util.Hashtable;
\r
31 import java.util.Vector;
\r
34 * <p>This class attempts to find finder patterns in a QR Code. Finder patterns are the square
\r
35 * markers at three corners of a QR Code.</p>
\r
37 * <p>This class is not thread-safe and should not be reused.</p>
\r
38 * TODO(dswitkin): Is this comment still true? I don't see any global variables for example.
\r
40 * <p>In contrast to {@link FinderPatternFinder}, this class will return an array of all possible
\r
41 * QR code locations in the image.</p>
\r
43 * <p>Use the TRY_HARDER hint to ask for a more thorough detection.</p>
\r
46 * @author Hannes Erven
\r
48 final class MultiFinderPatternFinder extends FinderPatternFinder {
\r
50 private static final FinderPatternInfo[] EMPTY_RESULT_ARRAY = new FinderPatternInfo[0];
\r
52 // TODO MIN_MODULE_COUNT and MAX_MODULE_COUNT would be great
\r
53 // hints to ask the user for since it limits the number of regions to decode
\r
54 private static final float MAX_MODULE_COUNT_PER_EDGE = 180; // max. legal count of modules per QR code edge (177)
\r
55 private static final float MIN_MODULE_COUNT_PER_EDGE = 9; // min. legal count per modules per QR code edge (11)
\r
58 * More or less arbitrary cutoff point for determining if two finder patterns might belong
\r
59 * to the same code if they differ less than DIFF_MODSIZE_CUTOFF_PERCENT percent in their
\r
60 * estimated modules sizes.
\r
62 private static final float DIFF_MODSIZE_CUTOFF_PERCENT = 0.05f;
\r
65 * More or less arbitrary cutoff point for determining if two finder patterns might belong
\r
66 * to the same code if they differ less than DIFF_MODSIZE_CUTOFF pixels/module in their
\r
67 * estimated modules sizes.
\r
69 private static final float DIFF_MODSIZE_CUTOFF = 0.5f;
\r
73 * A comparator that orders FinderPatterns by their estimated module size.
\r
75 private static class ModuleSizeComparator implements Comparator {
\r
76 public int compare(Object center1, Object center2) {
\r
77 float value = ((FinderPattern) center2).getEstimatedModuleSize() -
\r
78 ((FinderPattern) center1).getEstimatedModuleSize();
\r
79 return value < 0.0 ? -1 : value > 0.0 ? 1 : 0;
\r
84 * <p>Creates a finder that will search the image for three finder patterns.</p>
\r
86 * @param image image to search
\r
88 MultiFinderPatternFinder(MonochromeBitmapSource image) {
\r
93 * @return the 3 best {@link FinderPattern}s from our list of candidates. The "best" are
\r
94 * those that have been detected at least {@link #CENTER_QUORUM} times, and whose module
\r
95 * size differs from the average among those patterns the least
\r
96 * @throws ReaderException if 3 such finder patterns do not exist
\r
98 private FinderPattern[][] selectBestPatterns() throws ReaderException {
\r
99 Vector possibleCenters = getPossibleCenters();
\r
100 int size = possibleCenters.size();
\r
103 // Couldn't find enough finder patterns
\r
104 throw ReaderException.getInstance();
\r
108 * Begin HE modifications to safely detect multiple codes of equal size
\r
111 return new FinderPattern[][]{
\r
112 new FinderPattern[]{
\r
113 (FinderPattern) possibleCenters.elementAt(0),
\r
114 (FinderPattern) possibleCenters.elementAt(1),
\r
115 (FinderPattern) possibleCenters.elementAt(2)
\r
120 // Sort by estimated module size to speed up the upcoming checks
\r
121 Collections.insertionSort(possibleCenters, new ModuleSizeComparator());
\r
124 * Now lets start: build a list of tuples of three finder locations that
\r
125 * - feature similar module sizes
\r
126 * - are placed in a distance so the estimated module count is within the QR specification
\r
127 * - have similar distance between upper left/right and left top/bottom finder patterns
\r
128 * - form a triangle with 90° angle (checked by comparing top right/bottom left distance with pythagoras)
\r
130 * Note: we allow each point to be used for more than one code region: this might seem counterintuitive at first,
\r
131 * but the performance penalty is not that big. At this point, we cannot make a good quality decision whether
\r
132 * the three finders actually represent a QR code, or are just by chance layouted so it looks like there might
\r
133 * be a QR code there.
\r
134 * So, if the layout seems right, lets have the decoder try to decode.
\r
137 Vector results = new Vector(); // holder for the results
\r
139 for (int i1 = 0; i1 < (size - 2); i1++) {
\r
140 FinderPattern p1 = (FinderPattern) possibleCenters.elementAt(i1);
\r
145 for (int i2 = i1 + 1; i2 < (size - 1); i2++) {
\r
146 FinderPattern p2 = (FinderPattern) possibleCenters.elementAt(i2);
\r
151 // Compare the expected module sizes; if they are really off, skip
\r
152 float vModSize12 = (p1.getEstimatedModuleSize() - p2.getEstimatedModuleSize()) /
\r
153 (Math.min(p1.getEstimatedModuleSize(), p2.getEstimatedModuleSize()));
\r
154 float vModSize12A = Math.abs(p1.getEstimatedModuleSize() - p2.getEstimatedModuleSize());
\r
155 if (vModSize12A > DIFF_MODSIZE_CUTOFF && vModSize12 >= DIFF_MODSIZE_CUTOFF_PERCENT) {
\r
156 // break, since elements are ordered by the module size deviation there cannot be
\r
157 // any more interesting elements for the given p1.
\r
161 for (int i3 = i2 + 1; i3 < size; i3++) {
\r
162 FinderPattern p3 = (FinderPattern) possibleCenters.elementAt(i3);
\r
167 // Compare the expected module sizes; if they are really off, skip
\r
168 float vModSize23 = (p2.getEstimatedModuleSize() - p3.getEstimatedModuleSize()) /
\r
169 (Math.min(p2.getEstimatedModuleSize(), p3.getEstimatedModuleSize()));
\r
170 float vModSize23A = Math.abs(p2.getEstimatedModuleSize() - p3.getEstimatedModuleSize());
\r
171 if (vModSize23A > DIFF_MODSIZE_CUTOFF && vModSize23 >= DIFF_MODSIZE_CUTOFF_PERCENT) {
\r
172 // break, since elements are ordered by the module size deviation there cannot be
\r
173 // any more interesting elements for the given p1.
\r
177 FinderPattern[] test = {p1, p2, p3};
\r
178 ResultPoint.orderBestPatterns(test);
\r
180 // Calculate the distances: a = topleft-bottomleft, b=topleft-topright, c = diagonal
\r
181 FinderPatternInfo info = new FinderPatternInfo(test);
\r
182 float dA = ResultPoint.distance(info.getTopLeft(), info.getBottomLeft());
\r
183 float dC = ResultPoint.distance(info.getTopRight(), info.getBottomLeft());
\r
184 float dB = ResultPoint.distance(info.getTopLeft(), info.getTopRight());
\r
187 float estimatedModuleCount = ((dA + dB) / p1.getEstimatedModuleSize()) / 2;
\r
188 if (estimatedModuleCount > MAX_MODULE_COUNT_PER_EDGE || estimatedModuleCount < MIN_MODULE_COUNT_PER_EDGE) {
\r
192 // Calculate the difference of the edge lengths in percent
\r
193 float vABBC = Math.abs(((dA - dB) / Math.min(dA, dB)));
\r
194 if (vABBC >= 0.1f) {
\r
198 // Calculate the diagonal length by assuming a 90° angle at topleft
\r
199 float dCpy = (float) Math.sqrt(dA * dA + dB * dB);
\r
200 // Compare to the real distance in %
\r
201 float vPyC = Math.abs(((dC - dCpy) / Math.min(dC, dCpy)));
\r
203 if (vPyC >= 0.1f) {
\r
207 // All tests passed!
\r
208 results.addElement(test);
\r
209 } // end iterate p3
\r
210 } // end iterate p2
\r
211 } // end iterate p1
\r
213 if (!results.isEmpty()) {
\r
214 FinderPattern[][] resultArray = new FinderPattern[results.size()][];
\r
215 for (int i = 0; i < results.size(); i++) {
\r
216 resultArray[i] = (FinderPattern[]) results.elementAt(i);
\r
218 return resultArray;
\r
222 throw ReaderException.getInstance();
\r
225 public FinderPatternInfo[] findMulti(Hashtable hints) throws ReaderException {
\r
226 boolean tryHarder = hints != null && hints.containsKey(DecodeHintType.TRY_HARDER);
\r
227 MonochromeBitmapSource image = getImage();
\r
228 int maxI = image.getHeight();
\r
229 int maxJ = image.getWidth();
\r
230 // We are looking for black/white/black/white/black modules in
\r
231 // 1:1:3:1:1 ratio; this tracks the number of such modules seen so far
\r
233 // Let's assume that the maximum version QR Code we support takes up 1/4 the height of the
\r
234 // image, and then account for the center being 3 modules in size. This gives the smallest
\r
235 // number of pixels the center could be, so skip this often. When trying harder, look for all
\r
236 // QR versions regardless of how dense they are.
\r
237 int iSkip = (int) (maxI / (MAX_MODULES * 4.0f) * 3);
\r
238 if (iSkip < MIN_SKIP || tryHarder) {
\r
242 int[] stateCount = new int[5];
\r
243 for (int i = iSkip - 1; i < maxI; i += iSkip) {
\r
244 BitArray blackRow = new BitArray(maxJ);
\r
246 // Get a row of black/white values
\r
247 blackRow = image.getBlackRow(i, blackRow, 0, maxJ);
\r
253 int currentState = 0;
\r
254 for (int j = 0; j < maxJ; j++) {
\r
255 if (blackRow.get(j)) {
\r
257 if ((currentState & 1) == 1) { // Counting white pixels
\r
260 stateCount[currentState]++;
\r
261 } else { // White pixel
\r
262 if ((currentState & 1) == 0) { // Counting black pixels
\r
263 if (currentState == 4) { // A winner?
\r
264 if (foundPatternCross(stateCount)) { // Yes
\r
265 boolean confirmed = handlePossibleCenter(stateCount, i, j);
\r
267 do { // Advance to next black pixel
\r
269 } while (j < maxJ && !blackRow.get(j));
\r
270 j--; // back up to that last white pixel
\r
272 // Clear state to start looking again
\r
279 } else { // No, shift counts back by two
\r
280 stateCount[0] = stateCount[2];
\r
281 stateCount[1] = stateCount[3];
\r
282 stateCount[2] = stateCount[4];
\r
288 stateCount[++currentState]++;
\r
290 } else { // Counting white pixels
\r
291 stateCount[currentState]++;
\r
296 if (foundPatternCross(stateCount)) {
\r
297 handlePossibleCenter(stateCount, i, maxJ);
\r
298 } // end if foundPatternCross
\r
299 } // for i=iSkip-1 ...
\r
300 FinderPattern[][] patternInfo = selectBestPatterns();
\r
301 Vector result = new Vector();
\r
302 for (int i = 0; i < patternInfo.length; i++) {
\r
303 FinderPattern[] pattern = patternInfo[i];
\r
304 ResultPoint.orderBestPatterns(pattern);
\r
305 result.addElement(new FinderPatternInfo(pattern));
\r
308 if (result.isEmpty()) {
\r
309 return EMPTY_RESULT_ARRAY;
\r
311 FinderPatternInfo[] resultArray = new FinderPatternInfo[result.size()];
\r
312 for (int i = 0; i < result.size(); i++) {
\r
313 resultArray[i] = (FinderPatternInfo) result.elementAt(i);
\r
315 return resultArray;
\r