diff options
Diffstat (limited to 'libraries/zxing/src/com/google/zxing/qrcode/detector')
6 files changed, 1430 insertions, 0 deletions
diff --git a/libraries/zxing/src/com/google/zxing/qrcode/detector/AlignmentPattern.java b/libraries/zxing/src/com/google/zxing/qrcode/detector/AlignmentPattern.java new file mode 100644 index 000000000..6fc1a2c88 --- /dev/null +++ b/libraries/zxing/src/com/google/zxing/qrcode/detector/AlignmentPattern.java @@ -0,0 +1,48 @@ +/* + * 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 com.google.zxing.ResultPoint; + +/** + * <p>Encapsulates an alignment pattern, which are the smaller square patterns found in + * all but the simplest QR Codes.</p> + * + * @author Sean Owen + */ +public final class AlignmentPattern extends ResultPoint { + + private final float estimatedModuleSize; + + AlignmentPattern(float posX, float posY, float estimatedModuleSize) { + super(posX, posY); + this.estimatedModuleSize = estimatedModuleSize; + } + + /** + * <p>Determines if this alignment pattern "about equals" an alignment pattern at the stated + * position and size -- meaning, it is at nearly the same center with nearly the same size.</p> + */ + boolean aboutEquals(float moduleSize, float i, float j) { + if (Math.abs(i - getY()) <= moduleSize && Math.abs(j - getX()) <= moduleSize) { + float moduleSizeDiff = Math.abs(moduleSize - estimatedModuleSize); + return moduleSizeDiff <= 1.0f || moduleSizeDiff / estimatedModuleSize <= 1.0f; + } + return false; + } + +}
\ No newline at end of file diff --git a/libraries/zxing/src/com/google/zxing/qrcode/detector/AlignmentPatternFinder.java b/libraries/zxing/src/com/google/zxing/qrcode/detector/AlignmentPatternFinder.java new file mode 100644 index 000000000..3aadf284f --- /dev/null +++ b/libraries/zxing/src/com/google/zxing/qrcode/detector/AlignmentPatternFinder.java @@ -0,0 +1,279 @@ +/*
+ * 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 com.google.zxing.NotFoundException;
+import com.google.zxing.ResultPoint;
+import com.google.zxing.ResultPointCallback;
+import com.google.zxing.common.BitMatrix;
+
+import java.util.Vector;
+
+/**
+ * <p>This class attempts to find alignment patterns in a QR Code. Alignment patterns look like finder
+ * patterns but are smaller and appear at regular intervals throughout the image.</p>
+ *
+ * <p>At the moment this only looks for the bottom-right alignment pattern.</p>
+ *
+ * <p>This is mostly a simplified copy of {@link FinderPatternFinder}. It is copied,
+ * pasted and stripped down here for maximum performance but does unfortunately duplicate
+ * some code.</p>
+ *
+ * <p>This class is thread-safe but not reentrant. Each thread must allocate its own object.
+ *
+ * @author Sean Owen
+ */
+final class AlignmentPatternFinder {
+
+ private final BitMatrix image;
+ private final Vector possibleCenters;
+ private final int startX;
+ private final int startY;
+ private final int width;
+ private final int height;
+ private final float moduleSize;
+ private final int[] crossCheckStateCount;
+ private final ResultPointCallback resultPointCallback;
+
+ /**
+ * <p>Creates a finder that will look in a portion of the whole image.</p>
+ *
+ * @param image image to search
+ * @param startX left column from which to start searching
+ * @param startY top row from which to start searching
+ * @param width width of region to search
+ * @param height height of region to search
+ * @param moduleSize estimated module size so far
+ */
+ AlignmentPatternFinder(BitMatrix image,
+ int startX,
+ int startY,
+ int width,
+ int height,
+ float moduleSize,
+ ResultPointCallback resultPointCallback) {
+ this.image = image;
+ this.possibleCenters = new Vector(5);
+ this.startX = startX;
+ this.startY = startY;
+ this.width = width;
+ this.height = height;
+ this.moduleSize = moduleSize;
+ this.crossCheckStateCount = new int[3];
+ this.resultPointCallback = resultPointCallback;
+ }
+
+ /**
+ * <p>This method attempts to find the bottom-right alignment pattern in the image. It is a bit messy since
+ * it's pretty performance-critical and so is written to be fast foremost.</p>
+ *
+ * @return {@link AlignmentPattern} if found
+ * @throws NotFoundException if not found
+ */
+ AlignmentPattern find() throws NotFoundException {
+ int startX = this.startX;
+ int height = this.height;
+ int maxJ = startX + width;
+ int middleI = startY + (height >> 1);
+ // We are looking for black/white/black modules in 1:1:1 ratio;
+ // this tracks the number of black/white/black modules seen so far
+ int[] stateCount = new int[3];
+ for (int iGen = 0; iGen < height; iGen++) {
+ // Search from middle outwards
+ int i = middleI + ((iGen & 0x01) == 0 ? (iGen + 1) >> 1 : -((iGen + 1) >> 1));
+ stateCount[0] = 0;
+ stateCount[1] = 0;
+ stateCount[2] = 0;
+ int j = startX;
+ // Burn off leading white pixels before anything else; if we start in the middle of
+ // a white run, it doesn't make sense to count its length, since we don't know if the
+ // white run continued to the left of the start point
+ while (j < maxJ && !image.get(j, i)) {
+ j++;
+ }
+ int currentState = 0;
+ while (j < maxJ) {
+ if (image.get(j, i)) {
+ // Black pixel
+ if (currentState == 1) { // Counting black pixels
+ stateCount[currentState]++;
+ } else { // Counting white pixels
+ if (currentState == 2) { // A winner?
+ if (foundPatternCross(stateCount)) { // Yes
+ AlignmentPattern confirmed = handlePossibleCenter(stateCount, i, j);
+ if (confirmed != null) {
+ return confirmed;
+ }
+ }
+ stateCount[0] = stateCount[2];
+ stateCount[1] = 1;
+ stateCount[2] = 0;
+ currentState = 1;
+ } else {
+ stateCount[++currentState]++;
+ }
+ }
+ } else { // White pixel
+ if (currentState == 1) { // Counting black pixels
+ currentState++;
+ }
+ stateCount[currentState]++;
+ }
+ j++;
+ }
+ if (foundPatternCross(stateCount)) {
+ AlignmentPattern confirmed = handlePossibleCenter(stateCount, i, maxJ);
+ if (confirmed != null) {
+ return confirmed;
+ }
+ }
+
+ }
+
+ // Hmm, nothing we saw was observed and confirmed twice. If we had
+ // any guess at all, return it.
+ if (!possibleCenters.isEmpty()) {
+ return (AlignmentPattern) possibleCenters.elementAt(0);
+ }
+
+ throw NotFoundException.getNotFoundInstance();
+ }
+
+ /**
+ * Given a count of black/white/black pixels just seen and an end position,
+ * figures the location of the center of this black/white/black run.
+ */
+ private static float centerFromEnd(int[] stateCount, int end) {
+ return (float) (end - stateCount[2]) - stateCount[1] / 2.0f;
+ }
+
+ /**
+ * @param stateCount count of black/white/black pixels just read
+ * @return true iff the proportions of the counts is close enough to the 1/1/1 ratios
+ * used by alignment patterns to be considered a match
+ */
+ private boolean foundPatternCross(int[] stateCount) {
+ float moduleSize = this.moduleSize;
+ float maxVariance = moduleSize / 2.0f;
+ for (int i = 0; i < 3; i++) {
+ if (Math.abs(moduleSize - stateCount[i]) >= maxVariance) {
+ return false;
+ }
+ }
+ return true;
+ }
+
+ /**
+ * <p>After a horizontal scan finds a potential alignment pattern, this method
+ * "cross-checks" by scanning down vertically through the center of the possible
+ * alignment pattern to see if the same proportion is detected.</p>
+ *
+ * @param startI row where an alignment pattern was detected
+ * @param centerJ center of the section that appears to cross an alignment pattern
+ * @param maxCount maximum reasonable number of modules that should be
+ * observed in any reading state, based on the results of the horizontal scan
+ * @return vertical center of alignment pattern, or {@link Float#NaN} if not found
+ */
+ private float crossCheckVertical(int startI, int centerJ, int maxCount,
+ int originalStateCountTotal) {
+ BitMatrix image = this.image;
+
+ int maxI = image.getHeight();
+ int[] stateCount = crossCheckStateCount;
+ stateCount[0] = 0;
+ stateCount[1] = 0;
+ stateCount[2] = 0;
+
+ // Start counting up from center
+ int i = startI;
+ while (i >= 0 && image.get(centerJ, i) && stateCount[1] <= maxCount) {
+ stateCount[1]++;
+ i--;
+ }
+ // If already too many modules in this state or ran off the edge:
+ if (i < 0 || stateCount[1] > maxCount) {
+ return Float.NaN;
+ }
+ while (i >= 0 && !image.get(centerJ, i) && stateCount[0] <= maxCount) {
+ stateCount[0]++;
+ i--;
+ }
+ if (stateCount[0] > maxCount) {
+ return Float.NaN;
+ }
+
+ // Now also count down from center
+ i = startI + 1;
+ while (i < maxI && image.get(centerJ, i) && stateCount[1] <= maxCount) {
+ stateCount[1]++;
+ i++;
+ }
+ if (i == maxI || stateCount[1] > maxCount) {
+ return Float.NaN;
+ }
+ while (i < maxI && !image.get(centerJ, i) && stateCount[2] <= maxCount) {
+ stateCount[2]++;
+ i++;
+ }
+ if (stateCount[2] > maxCount) {
+ return Float.NaN;
+ }
+
+ int stateCountTotal = stateCount[0] + stateCount[1] + stateCount[2];
+ if (5 * Math.abs(stateCountTotal - originalStateCountTotal) >= 2 * originalStateCountTotal) {
+ return Float.NaN;
+ }
+
+ return foundPatternCross(stateCount) ? centerFromEnd(stateCount, i) : Float.NaN;
+ }
+
+ /**
+ * <p>This is called when a horizontal scan finds a possible alignment pattern. It will
+ * cross check with a vertical scan, and if successful, will see if this pattern had been
+ * found on a previous horizontal scan. If so, we consider it confirmed and conclude we have
+ * found the alignment pattern.</p>
+ *
+ * @param stateCount reading state module counts from horizontal scan
+ * @param i row where alignment pattern may be found
+ * @param j end of possible alignment pattern in row
+ * @return {@link AlignmentPattern} if we have found the same pattern twice, or null if not
+ */
+ private AlignmentPattern handlePossibleCenter(int[] stateCount, int i, int j) {
+ int stateCountTotal = stateCount[0] + stateCount[1] + stateCount[2];
+ float centerJ = centerFromEnd(stateCount, j);
+ float centerI = crossCheckVertical(i, (int) centerJ, 2 * stateCount[1], stateCountTotal);
+ if (!Float.isNaN(centerI)) {
+ float estimatedModuleSize = (float) (stateCount[0] + stateCount[1] + stateCount[2]) / 3.0f;
+ int max = possibleCenters.size();
+ for (int index = 0; index < max; index++) {
+ AlignmentPattern center = (AlignmentPattern) possibleCenters.elementAt(index);
+ // Look for about the same center and module size:
+ if (center.aboutEquals(estimatedModuleSize, centerI, centerJ)) {
+ return new AlignmentPattern(centerJ, centerI, estimatedModuleSize);
+ }
+ }
+ // Hadn't found this before; save it
+ ResultPoint point = new AlignmentPattern(centerJ, centerI, estimatedModuleSize);
+ possibleCenters.addElement(point);
+ if (resultPointCallback != null) {
+ resultPointCallback.foundPossibleResultPoint(point);
+ }
+ }
+ return null;
+ }
+
+}
diff --git a/libraries/zxing/src/com/google/zxing/qrcode/detector/Detector.java b/libraries/zxing/src/com/google/zxing/qrcode/detector/Detector.java new file mode 100644 index 000000000..724d39d59 --- /dev/null +++ b/libraries/zxing/src/com/google/zxing/qrcode/detector/Detector.java @@ -0,0 +1,406 @@ +/* + * 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 com.google.zxing.DecodeHintType; +import com.google.zxing.FormatException; +import com.google.zxing.NotFoundException; +import com.google.zxing.ResultPoint; +import com.google.zxing.ResultPointCallback; +import com.google.zxing.common.BitMatrix; +import com.google.zxing.common.DetectorResult; +import com.google.zxing.common.GridSampler; +import com.google.zxing.common.PerspectiveTransform; +import com.google.zxing.qrcode.decoder.Version; + +import java.util.Hashtable; + +/** + * <p>Encapsulates logic that can detect a QR Code in an image, even if the QR Code + * is rotated or skewed, or partially obscured.</p> + * + * @author Sean Owen + */ +public class Detector { + + private final BitMatrix image; + private ResultPointCallback resultPointCallback; + + public Detector(BitMatrix image) { + this.image = image; + } + + protected BitMatrix getImage() { + return image; + } + + protected ResultPointCallback getResultPointCallback() { + return resultPointCallback; + } + + /** + * <p>Detects a QR Code in an image, simply.</p> + * + * @return {@link DetectorResult} encapsulating results of detecting a QR Code + * @throws NotFoundException if no QR Code can be found + */ + public DetectorResult detect() throws NotFoundException, FormatException { + return detect(null); + } + + /** + * <p>Detects a QR Code in an image, simply.</p> + * + * @param hints optional hints to detector + * @return {@link NotFoundException} encapsulating results of detecting a QR Code + * @throws NotFoundException if QR Code cannot be found + * @throws FormatException if a QR Code cannot be decoded + */ + public DetectorResult detect(Hashtable hints) throws NotFoundException, FormatException { + + resultPointCallback = hints == null ? null : + (ResultPointCallback) hints.get(DecodeHintType.NEED_RESULT_POINT_CALLBACK); + + FinderPatternFinder finder = new FinderPatternFinder(image, resultPointCallback); + FinderPatternInfo info = finder.find(hints); + + return processFinderPatternInfo(info); + } + + protected DetectorResult processFinderPatternInfo(FinderPatternInfo info) + throws NotFoundException, FormatException { + + FinderPattern topLeft = info.getTopLeft(); + FinderPattern topRight = info.getTopRight(); + FinderPattern bottomLeft = info.getBottomLeft(); + + float moduleSize = calculateModuleSize(topLeft, topRight, bottomLeft); + if (moduleSize < 1.0f) { + throw NotFoundException.getNotFoundInstance(); + } + int dimension = computeDimension(topLeft, topRight, bottomLeft, moduleSize); + Version provisionalVersion = Version.getProvisionalVersionForDimension(dimension); + int modulesBetweenFPCenters = provisionalVersion.getDimensionForVersion() - 7; + + AlignmentPattern alignmentPattern = null; + // Anything above version 1 has an alignment pattern + if (provisionalVersion.getAlignmentPatternCenters().length > 0) { + + // Guess where a "bottom right" finder pattern would have been + float bottomRightX = topRight.getX() - topLeft.getX() + bottomLeft.getX(); + float bottomRightY = topRight.getY() - topLeft.getY() + bottomLeft.getY(); + + // Estimate that alignment pattern is closer by 3 modules + // from "bottom right" to known top left location + float correctionToTopLeft = 1.0f - 3.0f / (float) modulesBetweenFPCenters; + int estAlignmentX = (int) (topLeft.getX() + correctionToTopLeft * (bottomRightX - topLeft.getX())); + int estAlignmentY = (int) (topLeft.getY() + correctionToTopLeft * (bottomRightY - topLeft.getY())); + + // Kind of arbitrary -- expand search radius before giving up + for (int i = 4; i <= 16; i <<= 1) { + try { + alignmentPattern = findAlignmentInRegion(moduleSize, + estAlignmentX, + estAlignmentY, + (float) i); + break; + } catch (NotFoundException re) { + // try next round + } + } + // If we didn't find alignment pattern... well try anyway without it + } + + PerspectiveTransform transform = + createTransform(topLeft, topRight, bottomLeft, alignmentPattern, dimension); + + BitMatrix bits = sampleGrid(image, transform, dimension); + + ResultPoint[] points; + if (alignmentPattern == null) { + points = new ResultPoint[]{bottomLeft, topLeft, topRight}; + } else { + points = new ResultPoint[]{bottomLeft, topLeft, topRight, alignmentPattern}; + } + return new DetectorResult(bits, points); + } + + public static PerspectiveTransform createTransform(ResultPoint topLeft, + ResultPoint topRight, + ResultPoint bottomLeft, + ResultPoint alignmentPattern, + int dimension) { + float dimMinusThree = (float) dimension - 3.5f; + float bottomRightX; + float bottomRightY; + float sourceBottomRightX; + float sourceBottomRightY; + if (alignmentPattern != null) { + bottomRightX = alignmentPattern.getX(); + bottomRightY = alignmentPattern.getY(); + sourceBottomRightX = sourceBottomRightY = dimMinusThree - 3.0f; + } else { + // Don't have an alignment pattern, just make up the bottom-right point + bottomRightX = (topRight.getX() - topLeft.getX()) + bottomLeft.getX(); + bottomRightY = (topRight.getY() - topLeft.getY()) + bottomLeft.getY(); + sourceBottomRightX = sourceBottomRightY = dimMinusThree; + } + + return PerspectiveTransform.quadrilateralToQuadrilateral( + 3.5f, + 3.5f, + dimMinusThree, + 3.5f, + sourceBottomRightX, + sourceBottomRightY, + 3.5f, + dimMinusThree, + topLeft.getX(), + topLeft.getY(), + topRight.getX(), + topRight.getY(), + bottomRightX, + bottomRightY, + bottomLeft.getX(), + bottomLeft.getY()); + } + + private static BitMatrix sampleGrid(BitMatrix image, + PerspectiveTransform transform, + int dimension) throws NotFoundException { + + GridSampler sampler = GridSampler.getInstance(); + return sampler.sampleGrid(image, dimension, dimension, transform); + } + + /** + * <p>Computes the dimension (number of modules on a size) of the QR Code based on the position + * of the finder patterns and estimated module size.</p> + */ + protected static int computeDimension(ResultPoint topLeft, + ResultPoint topRight, + ResultPoint bottomLeft, + float moduleSize) throws NotFoundException { + int tltrCentersDimension = round(ResultPoint.distance(topLeft, topRight) / moduleSize); + int tlblCentersDimension = round(ResultPoint.distance(topLeft, bottomLeft) / moduleSize); + int dimension = ((tltrCentersDimension + tlblCentersDimension) >> 1) + 7; + switch (dimension & 0x03) { // mod 4 + case 0: + dimension++; + break; + // 1? do nothing + case 2: + dimension--; + break; + case 3: + throw NotFoundException.getNotFoundInstance(); + } + return dimension; + } + + /** + * <p>Computes an average estimated module size based on estimated derived from the positions + * of the three finder patterns.</p> + */ + protected float calculateModuleSize(ResultPoint topLeft, + ResultPoint topRight, + ResultPoint bottomLeft) { + // Take the average + return (calculateModuleSizeOneWay(topLeft, topRight) + + calculateModuleSizeOneWay(topLeft, bottomLeft)) / 2.0f; + } + + /** + * <p>Estimates module size based on two finder patterns -- it uses + * {@link #sizeOfBlackWhiteBlackRunBothWays(int, int, int, int)} to figure the + * width of each, measuring along the axis between their centers.</p> + */ + private float calculateModuleSizeOneWay(ResultPoint pattern, ResultPoint otherPattern) { + float moduleSizeEst1 = sizeOfBlackWhiteBlackRunBothWays((int) pattern.getX(), + (int) pattern.getY(), + (int) otherPattern.getX(), + (int) otherPattern.getY()); + float moduleSizeEst2 = sizeOfBlackWhiteBlackRunBothWays((int) otherPattern.getX(), + (int) otherPattern.getY(), + (int) pattern.getX(), + (int) pattern.getY()); + if (Float.isNaN(moduleSizeEst1)) { + return moduleSizeEst2 / 7.0f; + } + if (Float.isNaN(moduleSizeEst2)) { + return moduleSizeEst1 / 7.0f; + } + // Average them, and divide by 7 since we've counted the width of 3 black modules, + // and 1 white and 1 black module on either side. Ergo, divide sum by 14. + return (moduleSizeEst1 + moduleSizeEst2) / 14.0f; + } + + /** + * See {@link #sizeOfBlackWhiteBlackRun(int, int, int, int)}; computes the total width of + * a finder pattern by looking for a black-white-black run from the center in the direction + * of another point (another finder pattern center), and in the opposite direction too.</p> + */ + private float sizeOfBlackWhiteBlackRunBothWays(int fromX, int fromY, int toX, int toY) { + + float result = sizeOfBlackWhiteBlackRun(fromX, fromY, toX, toY); + + // Now count other way -- don't run off image though of course + float scale = 1.0f; + int otherToX = fromX - (toX - fromX); + if (otherToX < 0) { + scale = (float) fromX / (float) (fromX - otherToX); + otherToX = 0; + } else if (otherToX > image.getWidth()) { + scale = (float) (image.getWidth() - fromX) / (float) (otherToX - fromX); + otherToX = image.getWidth(); + } + int otherToY = (int) (fromY - (toY - fromY) * scale); + + scale = 1.0f; + if (otherToY < 0) { + scale = (float) fromY / (float) (fromY - otherToY); + otherToY = 0; + } else if (otherToY > image.getHeight()) { + scale = (float) (image.getHeight() - fromY) / (float) (otherToY - fromY); + otherToY = image.getHeight(); + } + otherToX = (int) (fromX + (otherToX - fromX) * scale); + + result += sizeOfBlackWhiteBlackRun(fromX, fromY, otherToX, otherToY); + return result; + } + + /** + * <p>This method traces a line from a point in the image, in the direction towards another point. + * It begins in a black region, and keeps going until it finds white, then black, then white again. + * It reports the distance from the start to this point.</p> + * + * <p>This is used when figuring out how wide a finder pattern is, when the finder pattern + * may be skewed or rotated.</p> + */ + private float sizeOfBlackWhiteBlackRun(int fromX, int fromY, int toX, int toY) { + // Mild variant of Bresenham's algorithm; + // see http://en.wikipedia.org/wiki/Bresenham's_line_algorithm + boolean steep = Math.abs(toY - fromY) > Math.abs(toX - fromX); + if (steep) { + int temp = fromX; + fromX = fromY; + fromY = temp; + temp = toX; + toX = toY; + toY = temp; + } + + int dx = Math.abs(toX - fromX); + int dy = Math.abs(toY - fromY); + int error = -dx >> 1; + int xstep = fromX < toX ? 1 : -1; + int ystep = fromY < toY ? 1 : -1; + + // In black pixels, looking for white, first or second time. + int state = 0; + for (int x = fromX, y = fromY; x != toX; x += xstep) { + int realX = steep ? y : x; + int realY = steep ? x : y; + + // In white pixels, looking for black. + // FIXME(dswitkin): This method seems to assume square images, which can cause these calls to + // BitMatrix.get() to throw ArrayIndexOutOfBoundsException. + if (state == 1) { + if (image.get(realX, realY)) { + state++; + } + } else { + if (!image.get(realX, realY)) { + state++; + } + } + + // Found black, white, black, and stumbled back onto white, so we're done. + if (state == 3) { + int diffX = x - fromX; + int diffY = y - fromY; + if (xstep < 0) { + diffX++; + } + return (float) Math.sqrt((double) (diffX * diffX + diffY * diffY)); + } + error += dy; + if (error > 0) { + if (y == toY) { + break; + } + y += ystep; + error -= dx; + } + } + int diffX = toX - fromX; + int diffY = toY - fromY; + return (float) Math.sqrt((double) (diffX * diffX + diffY * diffY)); + } + + /** + * <p>Attempts to locate an alignment pattern in a limited region of the image, which is + * guessed to contain it. This method uses {@link AlignmentPattern}.</p> + * + * @param overallEstModuleSize estimated module size so far + * @param estAlignmentX x coordinate of center of area probably containing alignment pattern + * @param estAlignmentY y coordinate of above + * @param allowanceFactor number of pixels in all directions to search from the center + * @return {@link AlignmentPattern} if found, or null otherwise + * @throws NotFoundException if an unexpected error occurs during detection + */ + protected AlignmentPattern findAlignmentInRegion(float overallEstModuleSize, + int estAlignmentX, + int estAlignmentY, + float allowanceFactor) + throws NotFoundException { + // Look for an alignment pattern (3 modules in size) around where it + // should be + int allowance = (int) (allowanceFactor * overallEstModuleSize); + int alignmentAreaLeftX = Math.max(0, estAlignmentX - allowance); + int alignmentAreaRightX = Math.min(image.getWidth() - 1, estAlignmentX + allowance); + if (alignmentAreaRightX - alignmentAreaLeftX < overallEstModuleSize * 3) { + throw NotFoundException.getNotFoundInstance(); + } + + int alignmentAreaTopY = Math.max(0, estAlignmentY - allowance); + int alignmentAreaBottomY = Math.min(image.getHeight() - 1, estAlignmentY + allowance); + if (alignmentAreaBottomY - alignmentAreaTopY < overallEstModuleSize * 3) { + throw NotFoundException.getNotFoundInstance(); + } + + AlignmentPatternFinder alignmentFinder = + new AlignmentPatternFinder( + image, + alignmentAreaLeftX, + alignmentAreaTopY, + alignmentAreaRightX - alignmentAreaLeftX, + alignmentAreaBottomY - alignmentAreaTopY, + overallEstModuleSize, + resultPointCallback); + return alignmentFinder.find(); + } + + /** + * Ends up being a bit faster than Math.round(). This merely rounds its argument to the nearest int, + * where x.5 rounds up. + */ + private static int round(float d) { + return (int) (d + 0.5f); + } +} diff --git a/libraries/zxing/src/com/google/zxing/qrcode/detector/FinderPattern.java b/libraries/zxing/src/com/google/zxing/qrcode/detector/FinderPattern.java new file mode 100644 index 000000000..7a9914d76 --- /dev/null +++ b/libraries/zxing/src/com/google/zxing/qrcode/detector/FinderPattern.java @@ -0,0 +1,63 @@ +/* + * 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 com.google.zxing.ResultPoint; + +/** + * <p>Encapsulates a finder pattern, which are the three square patterns found in + * the corners of QR Codes. It also encapsulates a count of similar finder patterns, + * as a convenience to the finder's bookkeeping.</p> + * + * @author Sean Owen + */ +public final class FinderPattern extends ResultPoint { + + private final float estimatedModuleSize; + private int count; + + FinderPattern(float posX, float posY, float estimatedModuleSize) { + super(posX, posY); + this.estimatedModuleSize = estimatedModuleSize; + this.count = 1; + } + + public float getEstimatedModuleSize() { + return estimatedModuleSize; + } + + int getCount() { + return count; + } + + void incrementCount() { + this.count++; + } + + /** + * <p>Determines if this finder pattern "about equals" a finder pattern at the stated + * position and size -- meaning, it is at nearly the same center with nearly the same size.</p> + */ + boolean aboutEquals(float moduleSize, float i, float j) { + if (Math.abs(i - getY()) <= moduleSize && Math.abs(j - getX()) <= moduleSize) { + float moduleSizeDiff = Math.abs(moduleSize - estimatedModuleSize); + return moduleSizeDiff <= 1.0f || moduleSizeDiff / estimatedModuleSize <= 1.0f; + } + return false; + } + +} diff --git a/libraries/zxing/src/com/google/zxing/qrcode/detector/FinderPatternFinder.java b/libraries/zxing/src/com/google/zxing/qrcode/detector/FinderPatternFinder.java new file mode 100644 index 000000000..01b3bde2a --- /dev/null +++ b/libraries/zxing/src/com/google/zxing/qrcode/detector/FinderPatternFinder.java @@ -0,0 +1,585 @@ +/*
+ * 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 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;
+import com.google.zxing.common.Collections;
+import com.google.zxing.common.Comparator;
+
+import java.util.Hashtable;
+import java.util.Vector;
+
+/**
+ * <p>This class attempts to find finder patterns in a QR Code. Finder patterns are the square
+ * markers at three corners of a QR Code.</p>
+ *
+ * <p>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 Vector possibleCenters;
+ private boolean hasSkipped;
+ private final int[] crossCheckStateCount;
+ private final ResultPointCallback resultPointCallback;
+
+ /**
+ * <p>Creates a finder that will search the image for three finder patterns.</p>
+ *
+ * @param image image to search
+ */
+ public FinderPatternFinder(BitMatrix image) {
+ this(image, null);
+ }
+
+ public FinderPatternFinder(BitMatrix image, ResultPointCallback resultPointCallback) {
+ this.image = image;
+ this.possibleCenters = new Vector();
+ this.crossCheckStateCount = new int[5];
+ this.resultPointCallback = resultPointCallback;
+ }
+
+ protected BitMatrix getImage() {
+ return image;
+ }
+
+ protected Vector getPossibleCenters() {
+ return possibleCenters;
+ }
+
+ FinderPatternInfo find(Hashtable hints) throws NotFoundException {
+ boolean tryHarder = hints != null && hints.containsKey(DecodeHintType.TRY_HARDER);
+ int maxI = image.getHeight();
+ int maxJ = image.getWidth();
+ // We are looking for black/white/black/white/black modules in
+ // 1:1:3:1:1 ratio; this tracks the number of such modules seen so far
+
+ // Let's assume that the maximum version QR Code we support takes up 1/4 the height of the
+ // image, and then account for the center being 3 modules in size. This gives the smallest
+ // number of pixels the center could be, so skip this often. When trying harder, look for all
+ // QR versions regardless of how dense they are.
+ int iSkip = (3 * maxI) / (4 * MAX_MODULES);
+ if (iSkip < MIN_SKIP || tryHarder) {
+ iSkip = MIN_SKIP;
+ }
+
+ boolean done = false;
+ int[] stateCount = new int[5];
+ for (int i = iSkip - 1; i < maxI && !done; i += iSkip) {
+ // Get a row of black/white values
+ stateCount[0] = 0;
+ stateCount[1] = 0;
+ stateCount[2] = 0;
+ stateCount[3] = 0;
+ stateCount[4] = 0;
+ int currentState = 0;
+ for (int j = 0; j < maxJ; j++) {
+ if (image.get(j, i)) {
+ // Black pixel
+ if ((currentState & 1) == 1) { // Counting white pixels
+ currentState++;
+ }
+ stateCount[currentState]++;
+ } else { // White pixel
+ if ((currentState & 1) == 0) { // Counting black pixels
+ if (currentState == 4) { // A winner?
+ if (foundPatternCross(stateCount)) { // Yes
+ boolean confirmed = handlePossibleCenter(stateCount, i, j);
+ if (confirmed) {
+ // Start examining every other line. Checking each line turned out to be too
+ // expensive and didn't improve performance.
+ iSkip = 2;
+ if (hasSkipped) {
+ done = haveMultiplyConfirmedCenters();
+ } else {
+ int rowSkip = findRowSkip();
+ if (rowSkip > stateCount[2]) {
+ // Skip rows between row of lower confirmed center
+ // and top of presumed third confirmed center
+ // but back up a bit to get a full chance of detecting
+ // it, entire width of center of finder pattern
+
+ // Skip by rowSkip, but back off by stateCount[2] (size of last center
+ // of pattern we saw) to be conservative, and also back off by iSkip which
+ // is about to be re-added
+ i += rowSkip - stateCount[2] - iSkip;
+ j = maxJ - 1;
+ }
+ }
+ } else {
+ stateCount[0] = stateCount[2];
+ stateCount[1] = stateCount[3];
+ stateCount[2] = stateCount[4];
+ stateCount[3] = 1;
+ stateCount[4] = 0;
+ currentState = 3;
+ continue;
+ }
+ // Clear state to start looking again
+ currentState = 0;
+ stateCount[0] = 0;
+ stateCount[1] = 0;
+ stateCount[2] = 0;
+ stateCount[3] = 0;
+ stateCount[4] = 0;
+ } else { // No, shift counts back by two
+ stateCount[0] = stateCount[2];
+ stateCount[1] = stateCount[3];
+ stateCount[2] = stateCount[4];
+ stateCount[3] = 1;
+ stateCount[4] = 0;
+ currentState = 3;
+ }
+ } else {
+ stateCount[++currentState]++;
+ }
+ } else { // Counting white pixels
+ stateCount[currentState]++;
+ }
+ }
+ }
+ if (foundPatternCross(stateCount)) {
+ boolean confirmed = handlePossibleCenter(stateCount, i, maxJ);
+ if (confirmed) {
+ iSkip = stateCount[0];
+ if (hasSkipped) {
+ // Found a third one
+ done = haveMultiplyConfirmedCenters();
+ }
+ }
+ }
+ }
+
+ FinderPattern[] patternInfo = selectBestPatterns();
+ ResultPoint.orderBestPatterns(patternInfo);
+
+ return new FinderPatternInfo(patternInfo);
+ }
+
+ /**
+ * Given a count of black/white/black/white/black pixels just seen and an end position,
+ * figures the location of the center of this run.
+ */
+ private static float centerFromEnd(int[] stateCount, int end) {
+ return (float) (end - stateCount[4] - stateCount[3]) - stateCount[2] / 2.0f;
+ }
+
+ /**
+ * @param stateCount count of black/white/black/white/black pixels just read
+ * @return true iff the proportions of the counts is close enough to the 1/1/3/1/1 ratios
+ * used by finder patterns to be considered a match
+ */
+ protected static boolean foundPatternCross(int[] stateCount) {
+ int totalModuleSize = 0;
+ for (int i = 0; i < 5; i++) {
+ int count = stateCount[i];
+ if (count == 0) {
+ return false;
+ }
+ totalModuleSize += count;
+ }
+ if (totalModuleSize < 7) {
+ return false;
+ }
+ int moduleSize = (totalModuleSize << INTEGER_MATH_SHIFT) / 7;
+ int maxVariance = moduleSize / 2;
+ // Allow less than 50% variance from 1-1-3-1-1 proportions
+ return Math.abs(moduleSize - (stateCount[0] << INTEGER_MATH_SHIFT)) < maxVariance &&
+ Math.abs(moduleSize - (stateCount[1] << INTEGER_MATH_SHIFT)) < maxVariance &&
+ Math.abs(3 * moduleSize - (stateCount[2] << INTEGER_MATH_SHIFT)) < 3 * maxVariance &&
+ Math.abs(moduleSize - (stateCount[3] << INTEGER_MATH_SHIFT)) < maxVariance &&
+ Math.abs(moduleSize - (stateCount[4] << INTEGER_MATH_SHIFT)) < maxVariance;
+ }
+
+ private int[] getCrossCheckStateCount() {
+ crossCheckStateCount[0] = 0;
+ crossCheckStateCount[1] = 0;
+ crossCheckStateCount[2] = 0;
+ crossCheckStateCount[3] = 0;
+ crossCheckStateCount[4] = 0;
+ return crossCheckStateCount;
+ }
+
+ /**
+ * <p>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.</p>
+ *
+ * @param startI row where a finder pattern was detected
+ * @param centerJ center of the section that appears to cross a finder pattern
+ * @param maxCount maximum reasonable number of modules that should be
+ * observed in any reading state, based on the results of the horizontal scan
+ * @return vertical center of finder pattern, or {@link Float#NaN} if not found
+ */
+ private float crossCheckVertical(int startI, int centerJ, int maxCount,
+ int originalStateCountTotal) {
+ BitMatrix image = this.image;
+
+ int maxI = image.getHeight();
+ int[] stateCount = getCrossCheckStateCount();
+
+ // Start counting up from center
+ int i = startI;
+ while (i >= 0 && image.get(centerJ, i)) {
+ stateCount[2]++;
+ i--;
+ }
+ if (i < 0) {
+ return Float.NaN;
+ }
+ while (i >= 0 && !image.get(centerJ, i) && stateCount[1] <= maxCount) {
+ stateCount[1]++;
+ i--;
+ }
+ // If already too many modules in this state or ran off the edge:
+ if (i < 0 || stateCount[1] > maxCount) {
+ return Float.NaN;
+ }
+ while (i >= 0 && image.get(centerJ, i) && stateCount[0] <= maxCount) {
+ stateCount[0]++;
+ i--;
+ }
+ if (stateCount[0] > maxCount) {
+ return Float.NaN;
+ }
+
+ // Now also count down from center
+ i = startI + 1;
+ while (i < maxI && image.get(centerJ, i)) {
+ stateCount[2]++;
+ i++;
+ }
+ if (i == maxI) {
+ return Float.NaN;
+ }
+ while (i < maxI && !image.get(centerJ, i) && stateCount[3] < maxCount) {
+ stateCount[3]++;
+ i++;
+ }
+ if (i == maxI || stateCount[3] >= maxCount) {
+ return Float.NaN;
+ }
+ while (i < maxI && image.get(centerJ, i) && stateCount[4] < maxCount) {
+ stateCount[4]++;
+ i++;
+ }
+ if (stateCount[4] >= maxCount) {
+ return Float.NaN;
+ }
+
+ // If we found a finder-pattern-like section, but its size is more than 40% different than
+ // the original, assume it's a false positive
+ int stateCountTotal = stateCount[0] + stateCount[1] + stateCount[2] + stateCount[3] +
+ stateCount[4];
+ if (5 * Math.abs(stateCountTotal - originalStateCountTotal) >= 2 * originalStateCountTotal) {
+ return Float.NaN;
+ }
+
+ return foundPatternCross(stateCount) ? centerFromEnd(stateCount, i) : Float.NaN;
+ }
+
+ /**
+ * <p>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.</p>
+ */
+ private float crossCheckHorizontal(int startJ, int centerI, int maxCount,
+ int originalStateCountTotal) {
+ BitMatrix image = this.image;
+
+ int maxJ = image.getWidth();
+ int[] stateCount = getCrossCheckStateCount();
+
+ int j = startJ;
+ while (j >= 0 && image.get(j, centerI)) {
+ stateCount[2]++;
+ j--;
+ }
+ if (j < 0) {
+ return Float.NaN;
+ }
+ while (j >= 0 && !image.get(j, centerI) && stateCount[1] <= maxCount) {
+ stateCount[1]++;
+ j--;
+ }
+ if (j < 0 || stateCount[1] > maxCount) {
+ return Float.NaN;
+ }
+ while (j >= 0 && image.get(j, centerI) && stateCount[0] <= maxCount) {
+ stateCount[0]++;
+ j--;
+ }
+ if (stateCount[0] > maxCount) {
+ return Float.NaN;
+ }
+
+ j = startJ + 1;
+ while (j < maxJ && image.get(j, centerI)) {
+ stateCount[2]++;
+ j++;
+ }
+ if (j == maxJ) {
+ return Float.NaN;
+ }
+ while (j < maxJ && !image.get(j, centerI) && stateCount[3] < maxCount) {
+ stateCount[3]++;
+ j++;
+ }
+ if (j == maxJ || stateCount[3] >= maxCount) {
+ return Float.NaN;
+ }
+ while (j < maxJ && image.get(j, centerI) && stateCount[4] < maxCount) {
+ stateCount[4]++;
+ j++;
+ }
+ if (stateCount[4] >= maxCount) {
+ return Float.NaN;
+ }
+
+ // If we found a finder-pattern-like section, but its size is significantly different than
+ // the original, assume it's a false positive
+ int stateCountTotal = stateCount[0] + stateCount[1] + stateCount[2] + stateCount[3] +
+ stateCount[4];
+ if (5 * Math.abs(stateCountTotal - originalStateCountTotal) >= originalStateCountTotal) {
+ return Float.NaN;
+ }
+
+ return foundPatternCross(stateCount) ? centerFromEnd(stateCount, j) : Float.NaN;
+ }
+
+ /**
+ * <p>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.</p>
+ *
+ * <p>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 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 = (float) stateCountTotal / 7.0f;
+ boolean found = false;
+ int max = possibleCenters.size();
+ for (int index = 0; index < max; index++) {
+ FinderPattern center = (FinderPattern) possibleCenters.elementAt(index);
+ // Look for about the same center and module size:
+ if (center.aboutEquals(estimatedModuleSize, centerI, centerJ)) {
+ center.incrementCount();
+ found = true;
+ break;
+ }
+ }
+ if (!found) {
+ ResultPoint point = new FinderPattern(centerJ, centerI, estimatedModuleSize);
+ possibleCenters.addElement(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;
+ }
+ FinderPattern firstConfirmedCenter = null;
+ for (int i = 0; i < max; i++) {
+ FinderPattern center = (FinderPattern) possibleCenters.elementAt(i);
+ 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 (int i = 0; i < max; i++) {
+ FinderPattern pattern = (FinderPattern) possibleCenters.elementAt(i);
+ 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 / (float) max;
+ float totalDeviation = 0.0f;
+ for (int i = 0; i < max; i++) {
+ FinderPattern pattern = (FinderPattern) possibleCenters.elementAt(i);
+ 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 (int i = 0; i < startSize; i++) {
+ float size = ((FinderPattern) possibleCenters.elementAt(i)).getEstimatedModuleSize();
+ totalModuleSize += size;
+ square += size * size;
+ }
+ float average = totalModuleSize / (float) startSize;
+ float stdDev = (float) Math.sqrt(square / startSize - average * average);
+
+ Collections.insertionSort(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 = (FinderPattern) possibleCenters.elementAt(i);
+ if (Math.abs(pattern.getEstimatedModuleSize() - average) > limit) {
+ possibleCenters.removeElementAt(i);
+ i--;
+ }
+ }
+ }
+
+ if (possibleCenters.size() > 3) {
+ // Throw away all but those first size candidate points we found.
+
+ float totalModuleSize = 0.0f;
+ for (int i = 0; i < possibleCenters.size(); i++) {
+ totalModuleSize += ((FinderPattern) possibleCenters.elementAt(i)).getEstimatedModuleSize();
+ }
+
+ float average = totalModuleSize / (float) possibleCenters.size();
+
+ Collections.insertionSort(possibleCenters, new CenterComparator(average));
+
+ possibleCenters.setSize(3);
+ }
+
+ return new FinderPattern[]{
+ (FinderPattern) possibleCenters.elementAt(0),
+ (FinderPattern) possibleCenters.elementAt(1),
+ (FinderPattern) possibleCenters.elementAt(2)
+ };
+ }
+
+ /**
+ * <p>Orders by furthest from average</p>
+ */
+ private static class FurthestFromAverageComparator implements Comparator {
+ private final float average;
+ private FurthestFromAverageComparator(float f) {
+ average = f;
+ }
+ public int compare(Object center1, Object center2) {
+ float dA = Math.abs(((FinderPattern) center2).getEstimatedModuleSize() - average);
+ float dB = Math.abs(((FinderPattern) center1).getEstimatedModuleSize() - average);
+ return dA < dB ? -1 : dA == dB ? 0 : 1;
+ }
+ }
+
+ /**
+ * <p>Orders by {@link FinderPattern#getCount()}, descending.</p>
+ */
+ private static class CenterComparator implements Comparator {
+ private final float average;
+ private CenterComparator(float f) {
+ average = f;
+ }
+ public int compare(Object center1, Object center2) {
+ if (((FinderPattern) center2).getCount() == ((FinderPattern) center1).getCount()) {
+ float dA = Math.abs(((FinderPattern) center2).getEstimatedModuleSize() - average);
+ float dB = Math.abs(((FinderPattern) center1).getEstimatedModuleSize() - average);
+ return dA < dB ? 1 : dA == dB ? 0 : -1;
+ } else {
+ return ((FinderPattern) center2).getCount() - ((FinderPattern) center1).getCount();
+ }
+ }
+ }
+
+}
diff --git a/libraries/zxing/src/com/google/zxing/qrcode/detector/FinderPatternInfo.java b/libraries/zxing/src/com/google/zxing/qrcode/detector/FinderPatternInfo.java new file mode 100644 index 000000000..3c3401085 --- /dev/null +++ b/libraries/zxing/src/com/google/zxing/qrcode/detector/FinderPatternInfo.java @@ -0,0 +1,49 @@ +/* + * 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; + +/** + * <p>Encapsulates information about finder patterns in an image, including the location of + * the three finder patterns, and their estimated module size.</p> + * + * @author Sean Owen + */ +public final class FinderPatternInfo { + + private final FinderPattern bottomLeft; + private final FinderPattern topLeft; + private final FinderPattern topRight; + + public FinderPatternInfo(FinderPattern[] patternCenters) { + this.bottomLeft = patternCenters[0]; + this.topLeft = patternCenters[1]; + this.topRight = patternCenters[2]; + } + + public FinderPattern getBottomLeft() { + return bottomLeft; + } + + public FinderPattern getTopLeft() { + return topLeft; + } + + public FinderPattern getTopRight() { + return topRight; + } + +} |