From 637425045ec4c4ff505688200fce830c07db46e8 Mon Sep 17 00:00:00 2001
From: srowen Encapsulates an alignment pattern, which are the smaller square patterns found in
+ * all but the simplest QR Codes. 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. 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. At the moment this only looks for the bottom-right alignment pattern. 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. This class is not thread-safe. Creates a finder that will look in a portion of the whole image. 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. 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. 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. Encapsulates logic that can detect a QR Code in an image, even if the QR Code
+ * is rotated or skewed, or partially obscured. Detects a QR Code in an image, simply. 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. Computes an average estimated module size based on estimated derived from the positions
+ * of the three finder patterns. 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.
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.
+ * + *This is used when figuring out how wide a finder pattern is, when the finder pattern + * may be skewed or rotated.
+ */ 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 @@ -227,6 +250,17 @@ public final class Detector { return Float.NaN; } + /** + *Attempts to locate an alignment pattern in a limited region of the image, which is + * guessed to contain it. This method uses {@link AlignmentPattern}.
+ * + * @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 directons to search from the center + * @return {@link AlignmentPattern} if found, or null otherwise + * @throws ReaderException if an unexpected error occurs during detection + */ private AlignmentPattern findAlignmentInRegion(float overallEstModuleSize, int estAlignmentX, int estAlignmentY, @@ -236,11 +270,9 @@ public final class Detector { // should be int allowance = (int) (allowanceFactor * overallEstModuleSize); int alignmentAreaLeftX = Math.max(0, estAlignmentX - allowance); - int alignmentAreaRightX = Math.min(image.getWidth() - 1, - estAlignmentX + allowance); + int alignmentAreaRightX = Math.min(image.getWidth() - 1, estAlignmentX + allowance); int alignmentAreaTopY = Math.max(0, estAlignmentY - allowance); - int alignmentAreaBottomY = Math.min(image.getHeight() - 1, - estAlignmentY + allowance); + int alignmentAreaBottomY = Math.min(image.getHeight() - 1, estAlignmentY + allowance); AlignmentPatternFinder alignmentFinder = new AlignmentPatternFinder( @@ -254,7 +286,8 @@ public final class Detector { } /** - * Ends up being a bit faster than Math.round() + * 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/core/src/com/google/zxing/qrcode/detector/FinderPattern.java b/core/src/com/google/zxing/qrcode/detector/FinderPattern.java index 11e0337d..1d98fe92 100644 --- a/core/src/com/google/zxing/qrcode/detector/FinderPattern.java +++ b/core/src/com/google/zxing/qrcode/detector/FinderPattern.java @@ -19,6 +19,10 @@ package com.google.zxing.qrcode.detector; import com.google.zxing.ResultPoint; /** + *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 {@link FinderPatternFinder}'s bookkeeping.
+ * * @author srowen@google.com (Sean Owen) */ public final class FinderPattern implements ResultPoint { @@ -55,6 +59,10 @@ public final class FinderPattern implements ResultPoint { this.count++; } + /** + *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.
+ */ boolean aboutEquals(float moduleSize, float i, float j) { return Math.abs(i - posY) <= moduleSize && Math.abs(j - posX) <= moduleSize && diff --git a/core/src/com/google/zxing/qrcode/detector/FinderPatternFinder.java b/core/src/com/google/zxing/qrcode/detector/FinderPatternFinder.java index 47a6d62d..4ef3d58c 100755 --- a/core/src/com/google/zxing/qrcode/detector/FinderPatternFinder.java +++ b/core/src/com/google/zxing/qrcode/detector/FinderPatternFinder.java @@ -26,6 +26,9 @@ import com.google.zxing.common.Comparator; import java.util.Vector; /** + *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 not thread-safe and should not be reused.
* * @author srowen@google.com (Sean Owen) @@ -39,6 +42,11 @@ final class FinderPatternFinder { private final Vector possibleCenters; private boolean hasSkipped; + /** + *Creates a finder that will search the image for three finder patterns.
+ * + * @param image image to search + */ FinderPatternFinder(MonochromeBitmapSource image) { this.image = image; this.possibleCenters = new Vector(5); @@ -47,13 +55,16 @@ final class FinderPatternFinder { FinderPatternInfo find() throws ReaderException { int maxI = image.getHeight(); int maxJ = image.getWidth(); - int[] stateCount = new int[5]; // looking for 1 1 3 1 1 + // 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 + int[] stateCount = new int[5]; boolean done = false; // We can afford to examine every few lines until we've started finding // the patterns int iSkip = BIG_SKIP; for (int i = iSkip - 1; i < maxI && !done; i += iSkip) { - BitArray luminanceRow = image.getBlackRow(i, null, 0, maxJ); + // Get a row of black/white values + BitArray blackRow = image.getBlackRow(i, null, 0, maxJ); stateCount[0] = 0; stateCount[1] = 0; stateCount[2] = 0; @@ -61,7 +72,7 @@ final class FinderPatternFinder { stateCount[4] = 0; int currentState = 0; for (int j = 0; j < maxJ; j++) { - if (luminanceRow.get(j)) { + if (blackRow.get(j)) { // Black pixel if ((currentState & 1) == 1) { // Counting white pixels currentState++; @@ -71,8 +82,7 @@ final class FinderPatternFinder { if ((currentState & 1) == 0) { // Counting black pixels if (currentState == 4) { // A winner? if (foundPatternCross(stateCount)) { // Yes - boolean confirmed = - handlePossibleCenter(stateCount, i, j); + boolean confirmed = handlePossibleCenter(stateCount, i, j); if (confirmed) { iSkip = 1; // Go back to examining each line if (hasSkipped) { @@ -96,7 +106,7 @@ final class FinderPatternFinder { // Advance to next black pixel do { j++; - } while (j < maxJ && !luminanceRow.get(j)); + } while (j < maxJ && !blackRow.get(j)); j--; // back up to that last white pixel } // Clear state to start looking again @@ -141,14 +151,22 @@ final class FinderPatternFinder { totalModuleSize += patternInfo[i].getEstimatedModuleSize(); } - return new FinderPatternInfo(totalModuleSize / (float) patternInfo.length, - patternInfo); + return new FinderPatternInfo(totalModuleSize / (float) patternInfo.length, 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/13/1/1 ratios + * used by finder patterns to be considered a match + */ private static boolean foundPatternCross(int[] stateCount) { int totalModuleSize = 0; for (int i = 0; i < 5; i++) { @@ -162,20 +180,31 @@ final class FinderPatternFinder { } int moduleSize = totalModuleSize / 7; // Allow less than 50% deviance from 1-1-3-1-1 pattern - return - Math.abs(moduleSize - stateCount[0]) << 1 <= moduleSize && + return Math.abs(moduleSize - stateCount[0]) << 1 <= moduleSize && Math.abs(moduleSize - stateCount[1]) << 1 <= moduleSize && Math.abs(3 * moduleSize - stateCount[2]) << 1 <= 3 * moduleSize && Math.abs(moduleSize - stateCount[3]) << 1 <= moduleSize && Math.abs(moduleSize - stateCount[4]) << 1 <= moduleSize; } + /** + *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.
+ * + * @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) { MonochromeBitmapSource image = this.image; int maxI = image.getHeight(); int[] stateCount = new int[5]; + // Start counting up from center int i = startI; while (i >= 0 && image.isBlack(centerJ, i)) { stateCount[2]++; @@ -200,6 +229,7 @@ final class FinderPatternFinder { return Float.NaN; } + // Now also count down from center i = startI + 1; while (i < maxI && image.isBlack(centerJ, i)) { stateCount[2]++; @@ -226,6 +256,11 @@ final class FinderPatternFinder { return foundPatternCross(stateCount) ? centerFromEnd(stateCount, i) : Float.NaN; } + /** + *Like {@link #crossCheckVertical(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.
+ */ private float crossCheckHorizontal(int startJ, int centerI, int maxCount) { MonochromeBitmapSource image = this.image; @@ -244,7 +279,6 @@ final class FinderPatternFinder { stateCount[1]++; j--; } - // If already too many modules in this state or ran off the edge: if (j < 0 || stateCount[1] > maxCount) { return Float.NaN; } @@ -282,6 +316,22 @@ final class FinderPatternFinder { return foundPatternCross(stateCount) ? centerFromEnd(stateCount, j) : Float.NaN; } + /** + *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 + */ private boolean handlePossibleCenter(int[] stateCount, int i, int j) { @@ -291,11 +341,8 @@ final class FinderPatternFinder { // Re-cross check centerJ = crossCheckHorizontal((int) centerJ, (int) centerI, stateCount[2]); if (!Float.isNaN(centerJ)) { - float estimatedModuleSize = (float) (stateCount[0] + - stateCount[1] + - stateCount[2] + - stateCount[3] + - stateCount[4]) / 7.0f; + float estimatedModuleSize = + (float) (stateCount[0] + stateCount[1] + stateCount[2] + stateCount[3] + stateCount[4]) / 7.0f; boolean found = false; int max = possibleCenters.size(); for (int index = 0; index < max; index++) { @@ -308,8 +355,7 @@ final class FinderPatternFinder { } } if (!found) { - possibleCenters.addElement( - new FinderPattern(centerJ, centerI, estimatedModuleSize)); + possibleCenters.addElement(new FinderPattern(centerJ, centerI, estimatedModuleSize)); } return true; } @@ -317,6 +363,12 @@ final class FinderPatternFinder { 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) { @@ -343,6 +395,10 @@ final class FinderPatternFinder { return 0; } + /** + * @return true iff we have found at least 3 finder patterns that have been detected + * at least {@link #CENTER_QUORUM} times each + */ private boolean haveMulitplyConfirmedCenters() { int count = 0; int max = possibleCenters.size(); @@ -356,6 +412,12 @@ final class FinderPatternFinder { return false; } + /** + * @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 ReaderException if 3 such finder patterns do not exist + */ private FinderPattern[] selectBestPatterns() throws ReaderException { Collections.insertionSort(possibleCenters, new CenterComparator()); int size = 0; @@ -393,11 +455,9 @@ final class FinderPatternFinder { } averageModuleSize /= (float) size; - Collections.insertionSort( - possibleCenters, - new ClosestToAverageComparator(averageModuleSize)); + // We don't have java.util.Collections in J2ME + Collections.insertionSort(possibleCenters, new ClosestToAverageComparator(averageModuleSize)); - //return confirmedCenters.subList(0, 3).toArray(new FinderPattern[3]); FinderPattern[] result = new FinderPattern[3]; for (int i = 0; i < 3; i++) { result[i] = (FinderPattern) possibleCenters.elementAt(i); @@ -405,6 +465,15 @@ final class FinderPatternFinder { return result; } + /** + *
Having found three "best" finder patterns we need to decide which is the top-left, top-right, + * bottom-left. We assume that the one closest to the other two is the top-left one; this is not + * strictly true (imagine extreme perspective distortion) but for the moment is a serviceable assumption. + * Lastly we sort top-right from bottom-left by figuring out orientation from vector cross products.
+ * + * @param patterns three best {@link FinderPattern}s + * @return same {@link FinderPattern}s ordered bottom-left, top-left, top-right + */ private static FinderPattern[] orderBestPatterns(FinderPattern[] patterns) { // Find distances between pattern centers @@ -415,10 +484,11 @@ final class FinderPatternFinder { FinderPattern topLeft; FinderPattern topRight; FinderPattern bottomLeft; - // Assume one closest to other two is top left + // Assume one closest to other two is top left; + // topRight and bottomLeft will just be guesses below at first if (bcDistance >= abDistance && bcDistance >= acDistance) { topLeft = patterns[0]; - topRight = patterns[1]; // These two are guesses at the moment + topRight = patterns[1]; bottomLeft = patterns[2]; } else if (acDistance >= bcDistance && acDistance >= abDistance) { topLeft = patterns[1]; @@ -443,18 +513,27 @@ final class FinderPatternFinder { return new FinderPattern[]{bottomLeft, topLeft, topRight}; } + /** + * @return distance between two points + */ static float distance(ResultPoint pattern1, ResultPoint pattern2) { float xDiff = pattern1.getX() - pattern2.getX(); float yDiff = pattern1.getY() - pattern2.getY(); return (float) Math.sqrt((double) (xDiff * xDiff + yDiff * yDiff)); } + /** + *Orders by {@link FinderPattern#getCount()}, descending.
+ */ private static class CenterComparator implements Comparator { public int compare(Object center1, Object center2) { return ((FinderPattern) center2).getCount() - ((FinderPattern) center1).getCount(); } } + /** + *Orders by variance from average module size, ascending.
+ */ private static class ClosestToAverageComparator implements Comparator { private float averageModuleSize; diff --git a/core/src/com/google/zxing/qrcode/detector/FinderPatternInfo.java b/core/src/com/google/zxing/qrcode/detector/FinderPatternInfo.java index 8f5bc88a..10281cd9 100644 --- a/core/src/com/google/zxing/qrcode/detector/FinderPatternInfo.java +++ b/core/src/com/google/zxing/qrcode/detector/FinderPatternInfo.java @@ -17,6 +17,9 @@ package com.google.zxing.qrcode.detector; /** + *Encapsulates information about finder patterns in an image, including the location of + * the three finder patterns, and their estimated module size.
+ * * @author srowen@google.com (Sean Owen) */ final class FinderPatternInfo { -- 2.20.1