Encapsulates logic that can detect a QR Code in an image, even if the QR Code + * is rotated or skewed, or partially obscured.
+ * + * @author Sean Owen */ -public final class Detector { +public class Detector { - private final MonochromeBitmapSource image; + private final BitMatrix image; + private ResultPointCallback resultPointCallback; - public Detector(MonochromeBitmapSource image) { + public Detector(BitMatrix image) { this.image = image; } - public DetectorResult detect() throws ReaderException { + protected BitMatrix getImage() { + return image; + } + + protected ResultPointCallback getResultPointCallback() { + return resultPointCallback; + } - MonochromeBitmapSource image = this.image; + /** + *Detects a QR Code in an image, simply.
+ * + * @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); + } + + /** + *Detects a QR Code in an image, simply.
+ * + * @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); + } - FinderPatternFinder finder = new FinderPatternFinder(image); - FinderPatternInfo info = finder.find(); + 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; - // 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(); - 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; @@ -71,64 +118,85 @@ public final class Detector { estAlignmentY, (float) i); break; - } catch (ReaderException de) { + } catch (NotFoundException re) { // try next round } } - if (alignmentPattern == null) { - throw new ReaderException("Could not find alignment pattern"); - } - + // If we didn't find alignment pattern... well try anyway without it } - GridSampler sampler = GridSampler.getInstance(); - BitMatrix bits = sampler.sampleGrid(image, - topLeft, - topRight, - bottomLeft, - alignmentPattern, - dimension); - - /* - try { - BufferedImage outImage = - new BufferedImage(dimension, - dimension, - BufferedImage.TYPE_BYTE_BINARY); - for (int i = 0; i < dimension; i++) { - for (int j = 0; j < dimension; j++) { - if (bits.get(i, j)) { - outImage.setRGB(j, i, 0xFF000000); - } else { - outImage.setRGB(j, i, 0xFFFFFFFF); - } - } - } - ImageIO.write(outImage, "PNG", - new File("/home/srowen/out.png")); - } catch (IOException ioe) { - ioe.printStackTrace(); - } - */ + 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 }; + points = new ResultPoint[]{bottomLeft, topLeft, topRight}; } else { - points = new ResultPoint[] { bottomLeft, topLeft, topRight, alignmentPattern }; + points = new ResultPoint[]{bottomLeft, topLeft, topRight, alignmentPattern}; } return new DetectorResult(bits, points); } - 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); + public 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); + } + + /** + *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.
+ */ + 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: @@ -139,46 +207,91 @@ public final class Detector { dimension--; break; case 3: - throw new ReaderException("Bad dimension: " + dimension); + throw NotFoundException.getNotFoundInstance(); } 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.
+ */ + protected float calculateModuleSize(ResultPoint topLeft, + ResultPoint topRight, + ResultPoint bottomLeft) { // Take the average return (calculateModuleSizeOneWay(topLeft, topRight) + - calculateModuleSizeOneWay(topLeft, bottomLeft)) / 2.0f; + 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(), - (int) otherPattern.getY()); + (int) pattern.getY(), + (int) otherPattern.getX(), + (int) otherPattern.getY()); float moduleSizeEst2 = sizeOfBlackWhiteBlackRunBothWays((int) otherPattern.getX(), - (int) otherPattern.getY(), - (int) pattern.getX(), - (int) pattern.getY()); + (int) otherPattern.getY(), + (int) pattern.getX(), + (int) pattern.getY()); if (Float.isNaN(moduleSizeEst1)) { - return moduleSizeEst2; + return moduleSizeEst2 / 7.0f; } if (Float.isNaN(moduleSizeEst2)) { - return moduleSizeEst1; + 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. + */ 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 - } + 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; + } + + /** + *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 @@ -203,11 +316,11 @@ public final class Detector { int realX = steep ? y : x; int realY = steep ? x : y; if (state == 1) { // In white pixels, looking for black - if (image.isBlack(realX, realY)) { + if (image.get(realX, realY)) { state++; } } else { - if (!image.isBlack(realX, realY)) { + if (!image.get(realX, realY)) { state++; } } @@ -215,32 +328,55 @@ public final class Detector { if (state == 3) { // Found black, white, black, and stumbled back onto white; done 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; } } - // Hmm, couldn't find all of what we wanted -- don't know - return Float.NaN; + int diffX = toX - fromX; + int diffY = toY - fromY; + return (float) Math.sqrt((double) (diffX * diffX + diffY * diffY)); } - private AlignmentPattern findAlignmentInRegion(float overallEstModuleSize, - int estAlignmentX, - int estAlignmentY, - float allowanceFactor) - throws ReaderException { + /** + *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 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); + 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); + int alignmentAreaBottomY = Math.min(image.getHeight() - 1, estAlignmentY + allowance); + if (alignmentAreaBottomY - alignmentAreaTopY < overallEstModuleSize * 3) { + throw NotFoundException.getNotFoundInstance(); + } AlignmentPatternFinder alignmentFinder = new AlignmentPatternFinder( @@ -249,15 +385,16 @@ public final class Detector { alignmentAreaTopY, alignmentAreaRightX - alignmentAreaLeftX, alignmentAreaBottomY - alignmentAreaTopY, - overallEstModuleSize); + overallEstModuleSize, + resultPointCallback); return alignmentFinder.find(); } /** - * 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); } - }