2 * Copyright 2007 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.qrcode.detector;
\r
19 import com.google.zxing.MonochromeBitmapSource;
\r
20 import com.google.zxing.ReaderException;
\r
21 import com.google.zxing.common.BitArray;
\r
23 import java.util.Vector;
\r
26 * <p>This class attempts to find alignment patterns in a QR Code. Alignment patterns look like finder
\r
27 * patterns but are smaller and appear at regular intervals throughout the image.</p>
\r
29 * <p>At the moment this only looks for the bottom-right alignment pattern.</p>
\r
31 * <p>This is mostly a simplified copy of {@link FinderPatternFinder}. It is copied,
\r
32 * pasted and stripped down here for maximum performance but does unfortunately duplicate
\r
35 * <p>This class is thread-safe but not reentrant. Each thread must allocate its own object.
\r
39 final class AlignmentPatternFinder {
\r
41 private final MonochromeBitmapSource image;
\r
42 private final Vector possibleCenters;
\r
43 private final int startX;
\r
44 private final int startY;
\r
45 private final int width;
\r
46 private final int height;
\r
47 private final float moduleSize;
\r
48 private final int[] crossCheckStateCount;
\r
51 * <p>Creates a finder that will look in a portion of the whole image.</p>
\r
53 * @param image image to search
\r
54 * @param startX left column from which to start searching
\r
55 * @param startY top row from which to start searching
\r
56 * @param width width of region to search
\r
57 * @param height height of region to search
\r
58 * @param moduleSize estimated module size so far
\r
60 AlignmentPatternFinder(MonochromeBitmapSource image,
\r
67 this.possibleCenters = new Vector(5);
\r
68 this.startX = startX;
\r
69 this.startY = startY;
\r
71 this.height = height;
\r
72 this.moduleSize = moduleSize;
\r
73 this.crossCheckStateCount = new int[3];
\r
77 * <p>This method attempts to find the bottom-right alignment pattern in the image. It is a bit messy since
\r
78 * it's pretty performance-critical and so is written to be fast foremost.</p>
\r
80 * @return {@link AlignmentPattern} if found
\r
81 * @throws ReaderException if not found
\r
83 AlignmentPattern find() throws ReaderException {
\r
84 int startX = this.startX;
\r
85 int height = this.height;
\r
86 int maxJ = startX + width;
\r
87 int middleI = startY + (height >> 1);
\r
88 BitArray luminanceRow = new BitArray(width);
\r
89 // We are looking for black/white/black modules in 1:1:1 ratio;
\r
90 // this tracks the number of black/white/black modules seen so far
\r
91 int[] stateCount = new int[3];
\r
92 for (int iGen = 0; iGen < height; iGen++) {
\r
93 // Search from middle outwards
\r
94 int i = middleI + ((iGen & 0x01) == 0 ? ((iGen + 1) >> 1) : -((iGen + 1) >> 1));
\r
95 image.getBlackRow(i, luminanceRow, startX, width);
\r
100 // Burn off leading white pixels before anything else; if we start in the middle of
\r
101 // a white run, it doesn't make sense to count its length, since we don't know if the
\r
102 // white run continued to the left of the start point
\r
103 while (j < maxJ && !luminanceRow.get(j - startX)) {
\r
106 int currentState = 0;
\r
108 if (luminanceRow.get(j - startX)) {
\r
110 if (currentState == 1) { // Counting black pixels
\r
111 stateCount[currentState]++;
\r
112 } else { // Counting white pixels
\r
113 if (currentState == 2) { // A winner?
\r
114 if (foundPatternCross(stateCount)) { // Yes
\r
115 AlignmentPattern confirmed = handlePossibleCenter(stateCount, i, j);
\r
116 if (confirmed != null) {
\r
120 stateCount[0] = stateCount[2];
\r
125 stateCount[++currentState]++;
\r
128 } else { // White pixel
\r
129 if (currentState == 1) { // Counting black pixels
\r
132 stateCount[currentState]++;
\r
136 if (foundPatternCross(stateCount)) {
\r
137 AlignmentPattern confirmed = handlePossibleCenter(stateCount, i, maxJ);
\r
138 if (confirmed != null) {
\r
145 // Hmm, nothing we saw was observed and confirmed twice. If we had
\r
146 // any guess at all, return it.
\r
147 if (!possibleCenters.isEmpty()) {
\r
148 return (AlignmentPattern) possibleCenters.elementAt(0);
\r
151 throw ReaderException.getInstance();
\r
155 * Given a count of black/white/black pixels just seen and an end position,
\r
156 * figures the location of the center of this black/white/black run.
\r
158 private static float centerFromEnd(int[] stateCount, int end) {
\r
159 return (float) (end - stateCount[2]) - stateCount[1] / 2.0f;
\r
163 * @param stateCount count of black/white/black pixels just read
\r
164 * @return true iff the proportions of the counts is close enough to the 1/1/1 ratios
\r
165 * used by alignment patterns to be considered a match
\r
167 private boolean foundPatternCross(int[] stateCount) {
\r
168 float moduleSize = this.moduleSize;
\r
169 float maxVariance = moduleSize / 2.0f;
\r
170 for (int i = 0; i < 3; i++) {
\r
171 if (Math.abs(moduleSize - stateCount[i]) >= maxVariance) {
\r
179 * <p>After a horizontal scan finds a potential alignment pattern, this method
\r
180 * "cross-checks" by scanning down vertically through the center of the possible
\r
181 * alignment pattern to see if the same proportion is detected.</p>
\r
183 * @param startI row where an alignment pattern was detected
\r
184 * @param centerJ center of the section that appears to cross an alignment pattern
\r
185 * @param maxCount maximum reasonable number of modules that should be
\r
186 * observed in any reading state, based on the results of the horizontal scan
\r
187 * @return vertical center of alignment pattern, or {@link Float#NaN} if not found
\r
189 private float crossCheckVertical(int startI, int centerJ, int maxCount, int originalStateCountTotal) {
\r
190 MonochromeBitmapSource image = this.image;
\r
192 int maxI = image.getHeight();
\r
193 int[] stateCount = crossCheckStateCount;
\r
198 // Start counting up from center
\r
200 while (i >= 0 && image.isBlack(centerJ, i) && stateCount[1] <= maxCount) {
\r
204 // If already too many modules in this state or ran off the edge:
\r
205 if (i < 0 || stateCount[1] > maxCount) {
\r
208 while (i >= 0 && !image.isBlack(centerJ, i) && stateCount[0] <= maxCount) {
\r
212 if (stateCount[0] > maxCount) {
\r
216 // Now also count down from center
\r
218 while (i < maxI && image.isBlack(centerJ, i) && stateCount[1] <= maxCount) {
\r
222 if (i == maxI || stateCount[1] > maxCount) {
\r
225 while (i < maxI && !image.isBlack(centerJ, i) && stateCount[2] <= maxCount) {
\r
229 if (stateCount[2] > maxCount) {
\r
233 int stateCountTotal = stateCount[0] + stateCount[1] + stateCount[2];
\r
234 if (5 * Math.abs(stateCountTotal - originalStateCountTotal) >= originalStateCountTotal) {
\r
238 return foundPatternCross(stateCount) ? centerFromEnd(stateCount, i) : Float.NaN;
\r
242 * <p>This is called when a horizontal scan finds a possible alignment pattern. It will
\r
243 * cross check with a vertical scan, and if successful, will see if this pattern had been
\r
244 * found on a previous horizontal scan. If so, we consider it confirmed and conclude we have
\r
245 * found the alignment pattern.</p>
\r
247 * @param stateCount reading state module counts from horizontal scan
\r
248 * @param i row where alignment pattern may be found
\r
249 * @param j end of possible alignment pattern in row
\r
250 * @return {@link AlignmentPattern} if we have found the same pattern twice, or null if not
\r
252 private AlignmentPattern handlePossibleCenter(int[] stateCount, int i, int j) {
\r
253 int stateCountTotal = stateCount[0] + stateCount[1] + stateCount[2];
\r
254 float centerJ = centerFromEnd(stateCount, j);
\r
255 float centerI = crossCheckVertical(i, (int) centerJ, 2 * stateCount[1], stateCountTotal);
\r
256 if (!Float.isNaN(centerI)) {
\r
257 float estimatedModuleSize = (float) (stateCount[0] + stateCount[1] + stateCount[2]) / 3.0f;
\r
258 int max = possibleCenters.size();
\r
259 for (int index = 0; index < max; index++) {
\r
260 AlignmentPattern center = (AlignmentPattern) possibleCenters.elementAt(index);
\r
261 // Look for about the same center and module size:
\r
262 if (center.aboutEquals(estimatedModuleSize, centerI, centerJ)) {
\r
263 return new AlignmentPattern(centerJ, centerI, estimatedModuleSize);
\r
266 // Hadn't found this before; save it
\r
267 possibleCenters.addElement(new AlignmentPattern(centerJ, centerI, estimatedModuleSize));
\r