/* * Copyright 2007 ZXing authors * * Licensed under the Apache License, Version 2.0 (the "License"); * you may not use this file except in compliance with the License. * You may obtain a copy of the License at * * http://www.apache.org/licenses/LICENSE-2.0 * * Unless required by applicable law or agreed to in writing, software * distributed under the License is distributed on an "AS IS" BASIS, * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. * See the License for the specific language governing permissions and * limitations under the License. */ package com.google.zxing.qrcode.detector; import java.io.Serializable; import java.util.ArrayList; import java.util.Collections; import java.util.Comparator; import java.util.List; import java.util.Map; import com.google.zxing.DecodeHintType; import com.google.zxing.NotFoundException; import com.google.zxing.ResultPoint; import com.google.zxing.ResultPointCallback; import com.google.zxing.common.BitMatrix; /** *
This class attempts to find finder patterns in a QR Code. Finder patterns are the square * markers at three corners of a QR Code.
* *This class is thread-safe but not reentrant. Each thread must allocate its own object.
*
* @author Sean Owen
*/
public class FinderPatternFinder {
private static final int CENTER_QUORUM = 2;
protected static final int MIN_SKIP = 3; // 1 pixel/module times 3 modules/center
protected static final int MAX_MODULES = 57; // support up to version 10 for mobile clients
private static final int INTEGER_MATH_SHIFT = 8;
private final BitMatrix image;
private final List Creates a finder that will search the image for three finder patterns. After a horizontal scan finds a potential finder pattern, this method
* "cross-checks" by scanning down vertically through the center of the possible
* finder pattern to see if the same proportion is detected. Like {@link #crossCheckVertical(int, int, int, int)}, and in fact is basically identical,
* except it reads horizontally instead of vertically. This is used to cross-cross
* check a vertical cross check and locate the real center of the alignment pattern. This is called when a horizontal scan finds a possible alignment pattern. It will
* cross check with a vertical scan, and if successful, will, ah, cross-cross-check
* with another horizontal scan. This is needed primarily to locate the real horizontal
* center of the pattern in cases of extreme skew. If that succeeds the finder pattern location is added to a list that tracks
* the number of times each location has been nearly-matched as a finder pattern.
* Each additional find is more evidence that the location is in fact a finder
* pattern center
*
* @param stateCount reading state module counts from horizontal scan
* @param i row where finder pattern may be found
* @param j end of possible finder pattern in row
* @return true if a finder pattern candidate was found this time
*/
protected final boolean handlePossibleCenter(int[] stateCount, int i, int j) {
int stateCountTotal = stateCount[0] + stateCount[1] + stateCount[2] + stateCount[3] +
stateCount[4];
float centerJ = centerFromEnd(stateCount, j);
float centerI = crossCheckVertical(i, (int) centerJ, stateCount[2], stateCountTotal);
if (!Float.isNaN(centerI)) {
// Re-cross check
centerJ = crossCheckHorizontal((int) centerJ, (int) centerI, stateCount[2], stateCountTotal);
if (!Float.isNaN(centerJ)) {
float estimatedModuleSize = stateCountTotal / 7.0f;
boolean found = false;
for (int index = 0; index < possibleCenters.size(); index++) {
FinderPattern center = possibleCenters.get(index);
// Look for about the same center and module size:
if (center.aboutEquals(estimatedModuleSize, centerI, centerJ)) {
possibleCenters.set(index, center.combineEstimate(centerI, centerJ, estimatedModuleSize));
found = true;
break;
}
}
if (!found) {
FinderPattern point = new FinderPattern(centerJ, centerI, estimatedModuleSize);
possibleCenters.add(point);
if (resultPointCallback != null) {
resultPointCallback.foundPossibleResultPoint(point);
}
}
return true;
}
}
return false;
}
/**
* @return number of rows we could safely skip during scanning, based on the first
* two finder patterns that have been located. In some cases their position will
* allow us to infer that the third pattern must lie below a certain point farther
* down in the image.
*/
private int findRowSkip() {
int max = possibleCenters.size();
if (max <= 1) {
return 0;
}
ResultPoint firstConfirmedCenter = null;
for (FinderPattern center : possibleCenters) {
if (center.getCount() >= CENTER_QUORUM) {
if (firstConfirmedCenter == null) {
firstConfirmedCenter = center;
} else {
// We have two confirmed centers
// How far down can we skip before resuming looking for the next
// pattern? In the worst case, only the difference between the
// difference in the x / y coordinates of the two centers.
// This is the case where you find top left last.
hasSkipped = true;
return (int) (Math.abs(firstConfirmedCenter.getX() - center.getX()) -
Math.abs(firstConfirmedCenter.getY() - center.getY())) / 2;
}
}
}
return 0;
}
/**
* @return true iff we have found at least 3 finder patterns that have been detected
* at least {@link #CENTER_QUORUM} times each, and, the estimated module size of the
* candidates is "pretty similar"
*/
private boolean haveMultiplyConfirmedCenters() {
int confirmedCount = 0;
float totalModuleSize = 0.0f;
int max = possibleCenters.size();
for (FinderPattern pattern : possibleCenters) {
if (pattern.getCount() >= CENTER_QUORUM) {
confirmedCount++;
totalModuleSize += pattern.getEstimatedModuleSize();
}
}
if (confirmedCount < 3) {
return false;
}
// OK, we have at least 3 confirmed centers, but, it's possible that one is a "false positive"
// and that we need to keep looking. We detect this by asking if the estimated module sizes
// vary too much. We arbitrarily say that when the total deviation from average exceeds
// 5% of the total module size estimates, it's too much.
float average = totalModuleSize / max;
float totalDeviation = 0.0f;
for (FinderPattern pattern : possibleCenters) {
totalDeviation += Math.abs(pattern.getEstimatedModuleSize() - average);
}
return totalDeviation <= 0.05f * totalModuleSize;
}
/**
* @return the 3 best {@link FinderPattern}s from our list of candidates. The "best" are
* those that have been detected at least {@link #CENTER_QUORUM} times, and whose module
* size differs from the average among those patterns the least
* @throws NotFoundException if 3 such finder patterns do not exist
*/
private FinderPattern[] selectBestPatterns() throws NotFoundException {
int startSize = possibleCenters.size();
if (startSize < 3) {
// Couldn't find enough finder patterns
throw NotFoundException.getNotFoundInstance();
}
// Filter outlier possibilities whose module size is too different
if (startSize > 3) {
// But we can only afford to do so if we have at least 4 possibilities to choose from
float totalModuleSize = 0.0f;
float square = 0.0f;
for (FinderPattern center : possibleCenters) {
float size = center.getEstimatedModuleSize();
totalModuleSize += size;
square += size * size;
}
float average = totalModuleSize / startSize;
float stdDev = (float) Math.sqrt(square / startSize - average * average);
Collections.sort(possibleCenters, new FurthestFromAverageComparator(average));
float limit = Math.max(0.2f * average, stdDev);
for (int i = 0; i < possibleCenters.size() && possibleCenters.size() > 3; i++) {
FinderPattern pattern = possibleCenters.get(i);
if (Math.abs(pattern.getEstimatedModuleSize() - average) > limit) {
possibleCenters.remove(i);
i--;
}
}
}
if (possibleCenters.size() > 3) {
// Throw away all but those first size candidate points we found.
float totalModuleSize = 0.0f;
for (FinderPattern possibleCenter : possibleCenters) {
totalModuleSize += possibleCenter.getEstimatedModuleSize();
}
float average = totalModuleSize / possibleCenters.size();
Collections.sort(possibleCenters, new CenterComparator(average));
possibleCenters.subList(3, possibleCenters.size()).clear();
}
return new FinderPattern[]{
possibleCenters.get(0),
possibleCenters.get(1),
possibleCenters.get(2)
};
}
/**
* Orders by furthest from average Orders by {@link FinderPattern#getCount()}, descending.