From 637425045ec4c4ff505688200fce830c07db46e8 Mon Sep 17 00:00:00 2001 From: srowen Date: Wed, 7 Nov 2007 06:42:22 +0000 Subject: [PATCH] More javadoc git-svn-id: http://zxing.googlecode.com/svn/trunk@14 59b500cc-1b3d-0410-9834-0bbf25fbcc57 --- .../qrcode/detector/AlignmentPattern.java | 7 + .../detector/AlignmentPatternFinder.java | 88 +++++++++--- .../zxing/qrcode/detector/Detector.java | 85 ++++++++---- .../zxing/qrcode/detector/FinderPattern.java | 8 ++ .../qrcode/detector/FinderPatternFinder.java | 127 ++++++++++++++---- .../qrcode/detector/FinderPatternInfo.java | 3 + 6 files changed, 249 insertions(+), 69 deletions(-) diff --git a/core/src/com/google/zxing/qrcode/detector/AlignmentPattern.java b/core/src/com/google/zxing/qrcode/detector/AlignmentPattern.java index da0c6332..e9ba31dc 100644 --- a/core/src/com/google/zxing/qrcode/detector/AlignmentPattern.java +++ b/core/src/com/google/zxing/qrcode/detector/AlignmentPattern.java @@ -19,6 +19,9 @@ package com.google.zxing.qrcode.detector; import com.google.zxing.ResultPoint; /** + *

Encapsulates an alignment pattern, which are the smaller square patterns found in + * all but the simplest QR Codes.

+ * * @author srowen@google.com (Sean Owen) */ public final class AlignmentPattern implements ResultPoint { @@ -45,6 +48,10 @@ public final class AlignmentPattern implements ResultPoint { return estimatedModuleSize; } + /** + *

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.

+ */ boolean aboutEquals(float moduleSize, float i, float j) { return Math.abs(i - posY) <= moduleSize && diff --git a/core/src/com/google/zxing/qrcode/detector/AlignmentPatternFinder.java b/core/src/com/google/zxing/qrcode/detector/AlignmentPatternFinder.java index 1e74bd9f..b4e35502 100644 --- a/core/src/com/google/zxing/qrcode/detector/AlignmentPatternFinder.java +++ b/core/src/com/google/zxing/qrcode/detector/AlignmentPatternFinder.java @@ -23,8 +23,15 @@ import com.google.zxing.common.BitArray; import java.util.Vector; /** + *

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.

* * @author srowen@google.com (Sean Owen) @@ -39,6 +46,16 @@ final class AlignmentPatternFinder { private final int height; private final float moduleSize; + /** + *

Creates a finder that will look in a portion of the whole image.

+ * + * @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(MonochromeBitmapSource image, int startX, int startY, @@ -54,17 +71,25 @@ final class AlignmentPatternFinder { this.moduleSize = moduleSize; } + /** + *

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.

+ * + * @return {@link AlignmentPattern} if found + * @throws ReaderException if not found + */ AlignmentPattern find() throws ReaderException { int startX = this.startX; int height = this.height; int maxJ = startX + width; int middleI = startY + (height >> 1); BitArray luminanceRow = new BitArray(width); - int[] stateCount = new int[3]; // looking for 1 1 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)); + int i = middleI + ((iGen & 0x01) == 0 ? ((iGen + 1) >> 1) : -((iGen + 1) >> 1)); image.getBlackRow(i, luminanceRow, startX, width); stateCount[0] = 0; stateCount[1] = 0; @@ -85,8 +110,7 @@ final class AlignmentPatternFinder { } else { // Counting white pixels if (currentState == 2) { // A winner? if (foundPatternCross(stateCount)) { // Yes - AlignmentPattern confirmed = - handlePossibleCenter(stateCount, i, j); + AlignmentPattern confirmed = handlePossibleCenter(stateCount, i, j); if (confirmed != null) { return confirmed; } @@ -125,10 +149,19 @@ final class AlignmentPatternFinder { throw new ReaderException("Could not find alignment pattern"); } + /** + * 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; for (int i = 0; i < 3; i++) { @@ -139,16 +172,30 @@ final class AlignmentPatternFinder { return true; } + /** + *

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.

+ * + * @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) { MonochromeBitmapSource image = this.image; int maxI = image.getHeight(); int[] stateCount = new int[3]; + + // Start counting up from center int i = startI; while (i >= 0 && image.isBlack(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; } @@ -160,17 +207,16 @@ final class AlignmentPatternFinder { return Float.NaN; } + // Now also count down from center i = startI + 1; - while (i < maxI && image.isBlack(centerJ, i) && - stateCount[1] <= maxCount) { + while (i < maxI && image.isBlack(centerJ, i) && stateCount[1] <= maxCount) { stateCount[1]++; i++; } if (i == maxI || stateCount[1] > maxCount) { return Float.NaN; } - while (i < maxI && !image.isBlack(centerJ, i) && - stateCount[2] <= maxCount) { + while (i < maxI && !image.isBlack(centerJ, i) && stateCount[2] <= maxCount) { stateCount[2]++; i++; } @@ -178,21 +224,25 @@ final class AlignmentPatternFinder { return Float.NaN; } - return - foundPatternCross(stateCount) ? - centerFromEnd(stateCount, i) : - Float.NaN; + return foundPatternCross(stateCount) ? centerFromEnd(stateCount, i) : Float.NaN; } - private AlignmentPattern handlePossibleCenter(int[] stateCount, - int i, - int j) { + /** + *

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.

+ * + * @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) { float centerJ = centerFromEnd(stateCount, j); float centerI = crossCheckVertical(i, (int) centerJ, 2 * stateCount[1]); if (!Float.isNaN(centerI)) { - float estimatedModuleSize = (float) (stateCount[0] + - stateCount[1] + - stateCount[2]) / 3.0f; + 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); diff --git a/core/src/com/google/zxing/qrcode/detector/Detector.java b/core/src/com/google/zxing/qrcode/detector/Detector.java index d10fbcb1..9847c931 100644 --- a/core/src/com/google/zxing/qrcode/detector/Detector.java +++ b/core/src/com/google/zxing/qrcode/detector/Detector.java @@ -23,6 +23,9 @@ import com.google.zxing.common.BitMatrix; import com.google.zxing.qrcode.decoder.Version; /** + *

Encapsulates logic that can detect a QR Code in an image, even if the QR Code + * is rotated or skewed, or partially obscured.

+ * * @author srowen@google.com (Sean Owen) */ public final class Detector { @@ -33,6 +36,12 @@ public final class Detector { this.image = image; } + /** + *

Detects a QR Code in an image, simply.

+ * + * @return {@link DetectorResult} encapsulating results of detecting a QR Code + * @throws ReaderException if no QR Code can be found + */ public DetectorResult detect() throws ReaderException { MonochromeBitmapSource image = this.image; @@ -71,7 +80,7 @@ public final class Detector { estAlignmentY, (float) i); break; - } catch (ReaderException de) { + } catch (ReaderException re) { // try next round } } @@ -82,12 +91,7 @@ public final class Detector { } GridSampler sampler = GridSampler.getInstance(); - BitMatrix bits = sampler.sampleGrid(image, - topLeft, - topRight, - bottomLeft, - alignmentPattern, - dimension); + BitMatrix bits = sampler.sampleGrid(image, topLeft, topRight, bottomLeft, alignmentPattern, dimension); /* try { @@ -104,8 +108,7 @@ public final class Detector { } } } - ImageIO.write(outImage, "PNG", - new File("/home/srowen/out.png")); + ImageIO.write(outImage, "PNG", new File("/tmp/out.png")); } catch (IOException ioe) { ioe.printStackTrace(); } @@ -120,21 +123,22 @@ public final class Detector { return new DetectorResult(bits, points); } + /** + *

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.

+ */ private static int computeDimension(ResultPoint topLeft, ResultPoint topRight, ResultPoint bottomLeft, - float moduleSize) - throws ReaderException { - int tltrCentersDimension = - round(FinderPatternFinder.distance(topLeft, topRight) / moduleSize); - int tlblCentersDimension = - round(FinderPatternFinder.distance(topLeft, bottomLeft) / moduleSize); + float moduleSize) throws ReaderException { + int tltrCentersDimension = round(FinderPatternFinder.distance(topLeft, topRight) / moduleSize); + int tlblCentersDimension = round(FinderPatternFinder.distance(topLeft, bottomLeft) / moduleSize); int dimension = ((tltrCentersDimension + tlblCentersDimension) >> 1) + 7; switch (dimension & 0x03) { // mod 4 case 0: dimension++; break; - // 1? do nothing + // 1? do nothing case 2: dimension--; break; @@ -144,16 +148,22 @@ public final class Detector { return dimension; } - private float calculateModuleSize(ResultPoint topLeft, - ResultPoint topRight, - ResultPoint bottomLeft) { + /** + *

Computes an average estimated module size based on estimated derived from the positions + * of the three finder patterns.

+ */ + private float calculateModuleSize(ResultPoint topLeft, ResultPoint topRight, ResultPoint bottomLeft) { // Take the average return (calculateModuleSizeOneWay(topLeft, topRight) + calculateModuleSizeOneWay(topLeft, bottomLeft)) / 2.0f; } - private float calculateModuleSizeOneWay(ResultPoint pattern, - ResultPoint otherPattern) { + /** + *

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.

+ */ + private float calculateModuleSizeOneWay(ResultPoint pattern, ResultPoint otherPattern) { float moduleSizeEst1 = sizeOfBlackWhiteBlackRunBothWays((int) pattern.getX(), (int) pattern.getY(), (int) otherPattern.getX(), @@ -173,12 +183,25 @@ public final class Detector { 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.

+ */ private float sizeOfBlackWhiteBlackRunBothWays(int fromX, int fromY, int toX, int toY) { float result = sizeOfBlackWhiteBlackRun(fromX, fromY, toX, toY); result += sizeOfBlackWhiteBlackRun(fromX, fromY, fromX - (toX - fromX), fromY - (toY - fromY)); return result - 1.0f; // -1 because we counted the middle pixel twice } + /** + *

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