import java.util.Hashtable;
/**
- * <p>
- * Encapsulates logic that can detect a PDF417 Code in an image, even if the
- * PDF417 Code is rotated or skewed, or partially obscured.
- * </p>
+ * <p>Encapsulates logic that can detect a PDF417 Code in an image, even if the
+ * PDF417 Code is rotated or skewed, or partially obscured.</p>
*
* @author SITA Lab (kevin.osullivan@sita.aero)
+ * @author dswitkin@google.com (Daniel Switkin)
*/
public final class Detector {
- public static final int MAX_AVG_VARIANCE = (int) ((1 << 8) * 0.42f);
- public static final int MAX_INDIVIDUAL_VARIANCE = (int) ((1 << 8) * 0.8f);
+ private static final int MAX_AVG_VARIANCE = (int) ((1 << 8) * 0.42f);
+ private static final int MAX_INDIVIDUAL_VARIANCE = (int) ((1 << 8) * 0.8f);
+ private static final int SKEW_THRESHOLD = 2;
// B S B S B S B S Bar/Space pattern
// 11111111 0 1 0 1 0 1 000
}
/**
- * <p>
- * Detects a PDF417 Code in an image, simply.
- * </p>
+ * <p>Detects a PDF417 Code in an image, simply.</p>
*
- * @return {@link DetectorResult} encapsulating results of detecting a PDF417
- * Code
+ * @return {@link DetectorResult} encapsulating results of detecting a PDF417 Code
* @throws ReaderException if no QR Code can be found
*/
public DetectorResult detect() throws ReaderException {
}
/**
- * <p>
- * Detects a PDF417 Code in an image, simply.
- * </p>
+ * <p>Detects a PDF417 Code in an image. Only checks 0 and 180 degree rotations.</p>
*
* @param hints optional hints to detector
- * @return {@link DetectorResult} encapsulating results of detecting a PDF417
- * Code
+ * @return {@link DetectorResult} encapsulating results of detecting a PDF417 Code
* @throws ReaderException if no PDF417 Code can be found
*/
public DetectorResult detect(Hashtable hints) throws ReaderException {
// Fetch the 1 bit matrix once up front.
BitMatrix matrix = image.getBlackMatrix();
-
+
+ // Try to find the vertices assuming the image is upright.
ResultPoint[] vertices = findVertices(matrix);
- if (vertices == null) { // Couldn't find the vertices
+ if (vertices == null) {
// Maybe the image is rotated 180 degrees?
vertices = findVertices180(matrix);
- /*
- * // Don't need this because the PDF417 code won't fit into // the
- * camera view finder when it is rotated. if (vertices == null) { //
- * Couldn't find the vertices // Maybe the image is rotated 90 degrees?
- * vertices = findVertices90(image); if (vertices == null) { //
- * Couldn't find the vertices // Maybe the image is rotated 270
- * degrees? vertices = findVertices270(image); } }
- */
+ if (vertices != null) {
+ correctCodeWordVertices(vertices, true);
+ }
+ } else {
+ correctCodeWordVertices(vertices, false);
}
+
if (vertices != null) {
float moduleWidth = computeModuleWidth(vertices);
if (moduleWidth < 1.0f) {
int dimension = computeDimension(vertices[4], vertices[6],
vertices[5], vertices[7], moduleWidth);
- // Deskew and sample image
+ // Deskew and sample image.
BitMatrix bits = sampleGrid(matrix, vertices[4], vertices[5],
vertices[6], vertices[7], dimension);
- //bits.setModuleWidth(moduleWidth);
return new DetectorResult(bits, new ResultPoint[]{vertices[4],
vertices[5], vertices[6], vertices[7]});
} else {
* TODO: Scanning every row is very expensive. We should only do this for TRY_HARDER.
*
* @param matrix the scanned barcode image.
- * @return the an array containing the vertices. vertices[0] x, y top left
- * barcode vertices[1] x, y bottom left barcode vertices[2] x, y top
- * right barcode vertices[3] x, y bottom right barcode vertices[4] x,
- * y top left codeword area vertices[5] x, y bottom left codeword
- * area vertices[6] x, y top right codeword area vertices[7] x, y
- * bottom right codeword area
+ * @return an array containing the vertices:
+ * vertices[0] x, y top left barcode
+ * vertices[1] x, y bottom left barcode
+ * vertices[2] x, y top right barcode
+ * vertices[3] x, y bottom right barcode
+ * vertices[4] x, y top left codeword area
+ * vertices[5] x, y bottom left codeword area
+ * vertices[6] x, y top right codeword area
+ * vertices[7] x, y bottom right codeword area
*/
- private static ResultPoint[] findVertices(BitMatrix matrix) throws ReaderException {
+ private static ResultPoint[] findVertices(BitMatrix matrix) {
int height = matrix.getHeight();
int width = matrix.getWidth();
int halfWidth = width >> 1;
ResultPoint[] result = new ResultPoint[8];
boolean found = false;
- int[] loc = null;
// Top Left
for (int i = 0; i < height; i++) {
- loc = findGuardPattern(matrix, 0, i, halfWidth, START_PATTERN);
+ int[] loc = findGuardPattern(matrix, 0, i, halfWidth, false, START_PATTERN);
if (loc != null) {
result[0] = new ResultPoint(loc[0], i);
result[4] = new ResultPoint(loc[1], i);
if (found) { // Found the Top Left vertex
found = false;
for (int i = height - 1; i > 0; i--) {
- loc = findGuardPattern(matrix, 0, i, halfWidth, START_PATTERN);
+ int[] loc = findGuardPattern(matrix, 0, i, halfWidth, false, START_PATTERN);
if (loc != null) {
result[1] = new ResultPoint(loc[0], i);
result[5] = new ResultPoint(loc[1], i);
if (found) { // Found the Bottom Left vertex
found = false;
for (int i = 0; i < height; i++) {
- loc = findGuardPattern(matrix, halfWidth, i, halfWidth, STOP_PATTERN);
+ int[] loc = findGuardPattern(matrix, halfWidth, i, halfWidth, false, STOP_PATTERN);
if (loc != null) {
result[2] = new ResultPoint(loc[1], i);
result[6] = new ResultPoint(loc[0], i);
if (found) { // Found the Top right vertex
found = false;
for (int i = height - 1; i > 0; i--) {
- loc = findGuardPattern(matrix, halfWidth, i, halfWidth, STOP_PATTERN);
+ int[] loc = findGuardPattern(matrix, halfWidth, i, halfWidth, false, STOP_PATTERN);
if (loc != null) {
result[3] = new ResultPoint(loc[1], i);
result[7] = new ResultPoint(loc[0], i);
* TODO: Scanning every row is very expensive. We should only do this for TRY_HARDER.
*
* @param matrix the scanned barcode image.
- * @return the an array containing the vertices. vertices[0] x, y top left
- * barcode vertices[1] x, y bottom left barcode vertices[2] x, y top
- * right barcode vertices[3] x, y bottom right barcode vertices[4] x,
- * y top left codeword area vertices[5] x, y bottom left codeword
- * area vertices[6] x, y top right codeword area vertices[7] x, y
- * bottom right codeword area
+ * @return an array containing the vertices:
+ * vertices[0] x, y top left barcode
+ * vertices[1] x, y bottom left barcode
+ * vertices[2] x, y top right barcode
+ * vertices[3] x, y bottom right barcode
+ * vertices[4] x, y top left codeword area
+ * vertices[5] x, y bottom left codeword area
+ * vertices[6] x, y top right codeword area
+ * vertices[7] x, y bottom right codeword area
*/
- private static ResultPoint[] findVertices180(BitMatrix matrix) throws ReaderException {
+ private static ResultPoint[] findVertices180(BitMatrix matrix) {
int height = matrix.getHeight();
int width = matrix.getWidth();
int halfWidth = width >> 1;
ResultPoint[] result = new ResultPoint[8];
boolean found = false;
- int[] loc = null;
// Top Left
for (int i = height - 1; i > 0; i--) {
- loc = findGuardPattern(matrix, halfWidth, i, halfWidth, START_PATTERN_REVERSE);
+ int[] loc = findGuardPattern(matrix, halfWidth, i, halfWidth, true, START_PATTERN_REVERSE);
if (loc != null) {
result[0] = new ResultPoint(loc[1], i);
result[4] = new ResultPoint(loc[0], i);
if (found) { // Found the Top Left vertex
found = false;
for (int i = 0; i < height; i++) {
- loc = findGuardPattern(matrix, halfWidth, i, halfWidth, START_PATTERN_REVERSE);
+ int[] loc = findGuardPattern(matrix, halfWidth, i, halfWidth, true, START_PATTERN_REVERSE);
if (loc != null) {
result[1] = new ResultPoint(loc[1], i);
result[5] = new ResultPoint(loc[0], i);
if (found) { // Found the Bottom Left vertex
found = false;
for (int i = height - 1; i > 0; i--) {
- loc = findGuardPattern(matrix, 0, i, halfWidth, STOP_PATTERN_REVERSE);
+ int[] loc = findGuardPattern(matrix, 0, i, halfWidth, false, STOP_PATTERN_REVERSE);
if (loc != null) {
result[2] = new ResultPoint(loc[0], i);
result[6] = new ResultPoint(loc[1], i);
if (found) { // Found the Top Right vertex
found = false;
for (int i = 0; i < height; i++) {
- loc = findGuardPattern(matrix, 0, i, halfWidth, STOP_PATTERN_REVERSE);
+ int[] loc = findGuardPattern(matrix, 0, i, halfWidth, false, STOP_PATTERN_REVERSE);
if (loc != null) {
result[3] = new ResultPoint(loc[0], i);
result[7] = new ResultPoint(loc[1], i);
}
/**
- * <p>
- * Estimates module size (pixels in a module) based on the Start and End
+ * Because we scan horizontally to detect the start and stop patterns, the vertical component of
+ * the codeword coordinates will be slightly wrong if there is any skew or rotation in the image.
+ * This method moves those points back onto the edges of the theoretically perfect bounding
+ * quadrilateral if needed.
+ *
+ * @param vertices The eight vertices located by findVertices().
+ */
+ private static void correctCodeWordVertices(ResultPoint[] vertices, boolean upsideDown) {
+ float skew = vertices[4].getY() - vertices[6].getY();
+ if (upsideDown) {
+ skew = -skew;
+ }
+ if (skew > SKEW_THRESHOLD) {
+ // Fix v4
+ float length = vertices[4].getX() - vertices[0].getX();
+ float deltax = vertices[6].getX() - vertices[0].getX();
+ float deltay = vertices[6].getY() - vertices[0].getY();
+ float correction = length * deltay / deltax;
+ vertices[4] = new ResultPoint(vertices[4].getX(), vertices[4].getY() + correction);
+ } else if (-skew > SKEW_THRESHOLD) {
+ // Fix v6
+ float length = vertices[2].getX() - vertices[6].getX();
+ float deltax = vertices[2].getX() - vertices[4].getX();
+ float deltay = vertices[2].getY() - vertices[4].getY();
+ float correction = length * deltay / deltax;
+ vertices[6] = new ResultPoint(vertices[6].getX(), vertices[6].getY() - correction);
+ }
+
+ skew = vertices[7].getY() - vertices[5].getY();
+ if (upsideDown) {
+ skew = -skew;
+ }
+ if (skew > SKEW_THRESHOLD) {
+ // Fix v5
+ float length = vertices[5].getX() - vertices[1].getX();
+ float deltax = vertices[7].getX() - vertices[1].getX();
+ float deltay = vertices[7].getY() - vertices[1].getY();
+ float correction = length * deltay / deltax;
+ vertices[5] = new ResultPoint(vertices[5].getX(), vertices[5].getY() + correction);
+ } else if (-skew > SKEW_THRESHOLD) {
+ // Fix v7
+ float length = vertices[3].getX() - vertices[7].getX();
+ float deltax = vertices[3].getX() - vertices[5].getX();
+ float deltay = vertices[3].getY() - vertices[5].getY();
+ float correction = length * deltay / deltax;
+ vertices[7] = new ResultPoint(vertices[7].getX(), vertices[7].getY() - correction);
+ }
+ }
+
+ /**
+ * <p>Estimates module size (pixels in a module) based on the Start and End
* finder patterns.</p>
*
- * @param vertices [] vertices[0] x, y top left barcode vertices[1] x, y bottom
- * left barcode vertices[2] x, y top right barcode vertices[3] x, y
- * bottom right barcode vertices[4] x, y top left Codeword area
- * vertices[5] x, y bottom left Codeword area vertices[6] x, y top
- * right Codeword area vertices[7] x, y bottom right Codeword area
+ * @param vertices an array of vertices:
+ * vertices[0] x, y top left barcode
+ * vertices[1] x, y bottom left barcode
+ * vertices[2] x, y top right barcode
+ * vertices[3] x, y bottom right barcode
+ * vertices[4] x, y top left codeword area
+ * vertices[5] x, y bottom left codeword area
+ * vertices[6] x, y top right codeword area
+ * vertices[7] x, y bottom right codeword area
* @return the module size.
*/
private static float computeModuleWidth(ResultPoint[] vertices) {
*/
private static int computeDimension(ResultPoint topLeft, ResultPoint topRight,
ResultPoint bottomLeft, ResultPoint bottomRight, float moduleWidth) {
- int topRowDimension = round(ResultPoint
- .distance(topLeft, topRight)
- / moduleWidth);
- int bottomRowDimension = round(ResultPoint.distance(bottomLeft,
- bottomRight)
- / moduleWidth);
+ int topRowDimension = round(ResultPoint.distance(topLeft, topRight) / moduleWidth);
+ int bottomRowDimension = round(ResultPoint.distance(bottomLeft, bottomRight) / moduleWidth);
return ((((topRowDimension + bottomRowDimension) >> 1) + 8) / 17) * 17;
/*
* int topRowDimension = round(ResultPoint.distance(topLeft,
ResultPoint bottomLeft, ResultPoint topRight, ResultPoint bottomRight, int dimension)
throws ReaderException {
- // Note that unlike in the QR Code sampler, we didn't find the center of
- // modules, but the
+ // Note that unlike the QR Code sampler, we didn't find the center of modules, but the
// very corners. So there is no 0.5f here; 0.0f is right.
GridSampler sampler = GridSampler.getInstance();
bottomRight.getY(), // p3FromY
bottomLeft.getX(), // p4FromX
bottomLeft.getY()); // p4FromY
-
}
/**
* @param column x position to start search
* @param row y position to start search
* @param width the number of pixels to search on this row
- * @param pattern pattern of counts of number of black and white pixels that are
- * being searched for as a pattern
+ * @param pattern pattern of counts of number of black and white pixels that are
+ * being searched for as a pattern
* @return start/end horizontal offset of guard pattern, as an array of two ints.
*/
- static int[] findGuardPattern(BitMatrix matrix, int column, int row, int width, int[] pattern) {
+ private static int[] findGuardPattern(BitMatrix matrix, int column, int row, int width,
+ boolean whiteFirst, int[] pattern) {
int patternLength = pattern.length;
+ // TODO: Find a way to cache this array, as this method is called hundreds of times
+ // per image, and we want to allocate as seldom as possible.
int[] counters = new int[patternLength];
- boolean isWhite = false;
+ boolean isWhite = whiteFirst;
int counterPosition = 0;
int patternStart = column;
* the total variance from the expected pattern proportions across all
* pattern elements, to the length of the pattern.
*
- * @param counters observed counters
- * @param pattern expected pattern
+ * @param counters observed counters
+ * @param pattern expected pattern
* @param maxIndividualVariance The most any counter can differ before we give up
* @return ratio of total variance between counters and pattern compared to
* total pattern size, where the ratio has been multiplied by 256.
* variance between counters and patterns equals the pattern length,
* higher values mean even more variance
*/
- public static int patternMatchVariance(int[] counters, int[] pattern,
- int maxIndividualVariance) {
+ private static int patternMatchVariance(int[] counters, int[] pattern, int maxIndividualVariance) {
int numCounters = counters.length;
int total = 0;
int patternLength = 0;
}
if (total < patternLength) {
// If we don't even have one pixel per unit of bar width, assume this
- // is too small
- // to reliably match, so fail:
+ // is too small to reliably match, so fail:
return Integer.MAX_VALUE;
}
- // We're going to fake floating-point math in integers. We just need to
- // use more bits.
- // Scale up patternLength so that intermediate values below like
- // scaledCounter will have
- // more "significant digits"
+ // We're going to fake floating-point math in integers. We just need to use more bits.
+ // Scale up patternLength so that intermediate values below like scaledCounter will have
+ // more "significant digits".
int unitBarWidth = (total << 8) / patternLength;
maxIndividualVariance = (maxIndividualVariance * unitBarWidth) >> 8;
for (int x = 0; x < numCounters; x++) {
int counter = counters[x] << 8;
int scaledPattern = pattern[x] * unitBarWidth;
- int variance = counter > scaledPattern ? counter - scaledPattern
- : scaledPattern - counter;
+ int variance = counter > scaledPattern ? counter - scaledPattern : scaledPattern - counter;
if (variance > maxIndividualVariance) {
return Integer.MAX_VALUE;
}