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) + * @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; } - /** - *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 { + protected BitMatrix getImage() { + return image; + } + + protected ResultPointCallback getResultPointCallback() { + return resultPointCallback; + } + + /** + *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); - MonochromeBitmapSource image = this.image; + 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; @@ -80,70 +118,96 @@ public final class Detector { estAlignmentY, (float) i); break; - } catch (ReaderException re) { + } 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("/tmp/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); } + 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.
*/ - 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); + 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 + // 1? do nothing case 2: dimension--; break; case 3: - throw new ReaderException("Bad dimension: " + dimension); + throw NotFoundException.getNotFoundInstance(); } return dimension; } @@ -152,31 +216,33 @@ public final class Detector { *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) { + 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; } - /** - *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.
- */ + /** + *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. @@ -189,10 +255,34 @@ public final class Detector { * 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. @@ -226,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++; } } @@ -238,16 +328,23 @@ 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)); } /** @@ -257,22 +354,29 @@ public final class Detector { * @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 + * @param allowanceFactor number of pixels in all directions to search from the center * @return {@link AlignmentPattern} if found, or null otherwise - * @throws ReaderException if an unexpected error occurs during detection + * @throws NotFoundException if an unexpected error occurs during detection */ - private AlignmentPattern findAlignmentInRegion(float overallEstModuleSize, - int estAlignmentX, - int estAlignmentY, - float allowanceFactor) - throws ReaderException { + 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( @@ -281,7 +385,8 @@ public final class Detector { alignmentAreaTopY, alignmentAreaRightX - alignmentAreaLeftX, alignmentAreaBottomY - alignmentAreaTopY, - overallEstModuleSize); + overallEstModuleSize, + resultPointCallback); return alignmentFinder.find(); } @@ -292,5 +397,4 @@ public final class Detector { private static int round(float d) { return (int) (d + 0.5f); } - }