2 * Copyright 2007 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.qrcode.detector;
19 import java.util.ArrayList;
20 import java.util.List;
22 import com.google.zxing.NotFoundException;
23 import com.google.zxing.ResultPointCallback;
24 import com.google.zxing.common.BitMatrix;
27 * <p>This class attempts to find alignment patterns in a QR Code. Alignment patterns look like finder
28 * patterns but are smaller and appear at regular intervals throughout the image.</p>
30 * <p>At the moment this only looks for the bottom-right alignment pattern.</p>
32 * <p>This is mostly a simplified copy of {@link FinderPatternFinder}. It is copied,
33 * pasted and stripped down here for maximum performance but does unfortunately duplicate
36 * <p>This class is thread-safe but not reentrant. Each thread must allocate its own object.</p>
40 final class AlignmentPatternFinder {
42 private final BitMatrix image;
43 private final List<AlignmentPattern> possibleCenters;
44 private final int startX;
45 private final int startY;
46 private final int width;
47 private final int height;
48 private final float moduleSize;
49 private final int[] crossCheckStateCount;
50 private final ResultPointCallback resultPointCallback;
53 * <p>Creates a finder that will look in a portion of the whole image.</p>
55 * @param image image to search
56 * @param startX left column from which to start searching
57 * @param startY top row from which to start searching
58 * @param width width of region to search
59 * @param height height of region to search
60 * @param moduleSize estimated module size so far
62 AlignmentPatternFinder(BitMatrix image,
68 ResultPointCallback resultPointCallback) {
70 this.possibleCenters = new ArrayList<AlignmentPattern>(5);
75 this.moduleSize = moduleSize;
76 this.crossCheckStateCount = new int[3];
77 this.resultPointCallback = resultPointCallback;
81 * <p>This method attempts to find the bottom-right alignment pattern in the image. It is a bit messy since
82 * it's pretty performance-critical and so is written to be fast foremost.</p>
84 * @return {@link AlignmentPattern} if found
85 * @throws NotFoundException if not found
87 AlignmentPattern find() throws NotFoundException {
88 int startX = this.startX;
89 int height = this.height;
90 int maxJ = startX + width;
91 int middleI = startY + (height >> 1);
92 // We are looking for black/white/black modules in 1:1:1 ratio;
93 // this tracks the number of black/white/black modules seen so far
94 int[] stateCount = new int[3];
95 for (int iGen = 0; iGen < height; iGen++) {
96 // Search from middle outwards
97 int i = middleI + ((iGen & 0x01) == 0 ? (iGen + 1) >> 1 : -((iGen + 1) >> 1));
102 // Burn off leading white pixels before anything else; if we start in the middle of
103 // a white run, it doesn't make sense to count its length, since we don't know if the
104 // white run continued to the left of the start point
105 while (j < maxJ && !image.get(j, i)) {
108 int currentState = 0;
110 if (image.get(j, i)) {
112 if (currentState == 1) { // Counting black pixels
113 stateCount[currentState]++;
114 } else { // Counting white pixels
115 if (currentState == 2) { // A winner?
116 if (foundPatternCross(stateCount)) { // Yes
117 AlignmentPattern confirmed = handlePossibleCenter(stateCount, i, j);
118 if (confirmed != null) {
122 stateCount[0] = stateCount[2];
127 stateCount[++currentState]++;
130 } else { // White pixel
131 if (currentState == 1) { // Counting black pixels
134 stateCount[currentState]++;
138 if (foundPatternCross(stateCount)) {
139 AlignmentPattern confirmed = handlePossibleCenter(stateCount, i, maxJ);
140 if (confirmed != null) {
147 // Hmm, nothing we saw was observed and confirmed twice. If we had
148 // any guess at all, return it.
149 if (!possibleCenters.isEmpty()) {
150 return possibleCenters.get(0);
153 throw NotFoundException.getNotFoundInstance();
157 * Given a count of black/white/black pixels just seen and an end position,
158 * figures the location of the center of this black/white/black run.
160 private static float centerFromEnd(int[] stateCount, int end) {
161 return end - stateCount[2] - stateCount[1] / 2.0f;
165 * @param stateCount count of black/white/black pixels just read
166 * @return true iff the proportions of the counts is close enough to the 1/1/1 ratios
167 * used by alignment patterns to be considered a match
169 private boolean foundPatternCross(int[] stateCount) {
170 float moduleSize = this.moduleSize;
171 float maxVariance = moduleSize / 2.0f;
172 for (int i = 0; i < 3; i++) {
173 if (Math.abs(moduleSize - stateCount[i]) >= maxVariance) {
181 * <p>After a horizontal scan finds a potential alignment pattern, this method
182 * "cross-checks" by scanning down vertically through the center of the possible
183 * alignment pattern to see if the same proportion is detected.</p>
185 * @param startI row where an alignment pattern was detected
186 * @param centerJ center of the section that appears to cross an alignment pattern
187 * @param maxCount maximum reasonable number of modules that should be
188 * observed in any reading state, based on the results of the horizontal scan
189 * @return vertical center of alignment pattern, or {@link Float#NaN} if not found
191 private float crossCheckVertical(int startI, int centerJ, int maxCount,
192 int originalStateCountTotal) {
193 BitMatrix image = this.image;
195 int maxI = image.getHeight();
196 int[] stateCount = crossCheckStateCount;
201 // Start counting up from center
203 while (i >= 0 && image.get(centerJ, i) && stateCount[1] <= maxCount) {
207 // If already too many modules in this state or ran off the edge:
208 if (i < 0 || stateCount[1] > maxCount) {
211 while (i >= 0 && !image.get(centerJ, i) && stateCount[0] <= maxCount) {
215 if (stateCount[0] > maxCount) {
219 // Now also count down from center
221 while (i < maxI && image.get(centerJ, i) && stateCount[1] <= maxCount) {
225 if (i == maxI || stateCount[1] > maxCount) {
228 while (i < maxI && !image.get(centerJ, i) && stateCount[2] <= maxCount) {
232 if (stateCount[2] > maxCount) {
236 int stateCountTotal = stateCount[0] + stateCount[1] + stateCount[2];
237 if (5 * Math.abs(stateCountTotal - originalStateCountTotal) >= 2 * originalStateCountTotal) {
241 return foundPatternCross(stateCount) ? centerFromEnd(stateCount, i) : Float.NaN;
245 * <p>This is called when a horizontal scan finds a possible alignment pattern. It will
246 * cross check with a vertical scan, and if successful, will see if this pattern had been
247 * found on a previous horizontal scan. If so, we consider it confirmed and conclude we have
248 * found the alignment pattern.</p>
250 * @param stateCount reading state module counts from horizontal scan
251 * @param i row where alignment pattern may be found
252 * @param j end of possible alignment pattern in row
253 * @return {@link AlignmentPattern} if we have found the same pattern twice, or null if not
255 private AlignmentPattern handlePossibleCenter(int[] stateCount, int i, int j) {
256 int stateCountTotal = stateCount[0] + stateCount[1] + stateCount[2];
257 float centerJ = centerFromEnd(stateCount, j);
258 float centerI = crossCheckVertical(i, (int) centerJ, 2 * stateCount[1], stateCountTotal);
259 if (!Float.isNaN(centerI)) {
260 float estimatedModuleSize = (stateCount[0] + stateCount[1] + stateCount[2]) / 3.0f;
261 for (AlignmentPattern center : possibleCenters) {
262 // Look for about the same center and module size:
263 if (center.aboutEquals(estimatedModuleSize, centerI, centerJ)) {
264 return center.combineEstimate(centerI, centerJ, estimatedModuleSize);
267 // Hadn't found this before; save it
268 AlignmentPattern point = new AlignmentPattern(centerJ, centerI, estimatedModuleSize);
269 possibleCenters.add(point);
270 if (resultPointCallback != null) {
271 resultPointCallback.foundPossibleResultPoint(point);