package com.google.zxing.pdf417.detector;
-import com.google.zxing.BlackPointEstimationMethod;
-import com.google.zxing.MonochromeBitmapSource;
+import com.google.zxing.BinaryBitmap;
import com.google.zxing.ReaderException;
import com.google.zxing.ResultPoint;
-import com.google.zxing.common.BitArray;
import com.google.zxing.common.BitMatrix;
import com.google.zxing.common.DetectorResult;
import com.google.zxing.common.GridSampler;
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
- private static final int[] START_PATTERN = {8, 1, 1, 1, 1, 1, 1, 3}; // 11111111
- // 0 1
- // 0 1
- // 0 1
- // 000
+ // 11111111 0 1 0 1 0 1 000
+ private static final int[] START_PATTERN = {8, 1, 1, 1, 1, 1, 1, 3};
+
+ // 11111111 0 1 0 1 0 1 000
+ private static final int[] START_PATTERN_REVERSE = {3, 1, 1, 1, 1, 1, 1, 8};
+
+ // 1111111 0 1 000 1 0 1 00 1
+ private static final int[] STOP_PATTERN = {7, 1, 1, 3, 1, 1, 1, 2, 1};
// B S B S B S B S B Bar/Space pattern
- private static final int[] STOP_PATTERN_REVERSE = {1, 2, 1, 1, 1, 3, 1, 1,
- 7}; // 1111111 0 1 000 1 0 1 00 1
+ // 1111111 0 1 000 1 0 1 00 1
+ private static final int[] STOP_PATTERN_REVERSE = {1, 2, 1, 1, 1, 3, 1, 1, 7};
- private final MonochromeBitmapSource image;
+ private final BinaryBitmap image;
- public Detector(MonochromeBitmapSource image) {
+ public Detector(BinaryBitmap image) {
this.image = image;
}
/**
- * <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 {
- if (!BlackPointEstimationMethod.TWO_D_SAMPLING.equals(image
- .getLastEstimationMethod())) {
- image.estimateBlackPoint(BlackPointEstimationMethod.TWO_D_SAMPLING, 0);
- }
+ // Fetch the 1 bit matrix once up front.
+ BitMatrix matrix = image.getBlackMatrix();
- ResultPoint[] vertices = findVertices(image);
- if (vertices == null) { // Couldn't find the vertices
+ // Try to find the vertices assuming the image is upright.
+ ResultPoint[] vertices = findVertices(matrix);
+ if (vertices == null) {
// Maybe the image is rotated 180 degrees?
- vertices = findVertices180(image);
- /*
- * // 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); } }
- */
+ vertices = findVertices180(matrix);
+ 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
- BitMatrix bits = sampleGrid(image, vertices[4], vertices[5],
+ // 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 {
/**
* Locate the vertices and the codewords area of a black blob using the Start
- * and Stop patterns as locators.
+ * and Stop patterns as locators. Assumes that the barcode begins in the left half
+ * of the image, and ends in the right half.
+ * TODO: Fix this assumption, allowing the barcode to be anywhere in the image.
+ * TODO: Scanning every row is very expensive. We should only do this for TRY_HARDER.
*
- * @param image 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
+ * @param matrix the scanned barcode image.
+ * @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(MonochromeBitmapSource image) {
- int height = image.getHeight();
- int width = image.getWidth();
+ private static ResultPoint[] findVertices(BitMatrix matrix) {
+ int height = matrix.getHeight();
+ int width = matrix.getWidth();
+ int halfWidth = width >> 1;
ResultPoint[] result = new ResultPoint[8];
- BitArray row = null;
boolean found = false;
- int[] loc = null;
// Top Left
for (int i = 0; i < height; i++) {
- row = image.getBlackRow(i, null, 0, width / 4);
- loc = findGuardPattern(row, 0, 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--) {
- row = image.getBlackRow(i, null, 0, width / 4);
- loc = findGuardPattern(row, 0, 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++) {
- row = image.getBlackRow(i, null, (width * 3) / 4, width / 4);
- row.reverse();
- loc = findGuardPattern(row, 0, STOP_PATTERN_REVERSE);
+ int[] loc = findGuardPattern(matrix, halfWidth, i, halfWidth, false, STOP_PATTERN);
if (loc != null) {
- result[2] = new ResultPoint(width - loc[0], i);
- result[6] = new ResultPoint(width - loc[1], i);
+ result[2] = new ResultPoint(loc[1], i);
+ result[6] = new ResultPoint(loc[0], i);
found = true;
break;
}
if (found) { // Found the Top right vertex
found = false;
for (int i = height - 1; i > 0; i--) {
- row = image.getBlackRow(i, null, (width * 3) / 4, width / 4);
- row.reverse();
- loc = findGuardPattern(row, 0, STOP_PATTERN_REVERSE);
+ int[] loc = findGuardPattern(matrix, halfWidth, i, halfWidth, false, STOP_PATTERN);
if (loc != null) {
- result[3] = new ResultPoint(width - loc[0], i);
- result[7] = new ResultPoint(width - loc[1], i);
+ result[3] = new ResultPoint(loc[1], i);
+ result[7] = new ResultPoint(loc[0], i);
found = true;
break;
}
* and Stop patterns as locators. This assumes that the image is rotated 180
* degrees and if it locates the start and stop patterns at it will re-map
* the vertices for a 0 degree rotation.
+ * TODO: Change assumption about barcode location.
+ * TODO: Scanning every row is very expensive. We should only do this for TRY_HARDER.
*
- * @param image 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
+ * @param matrix the scanned barcode image.
+ * @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(MonochromeBitmapSource image) {
- int height = image.getHeight();
- int width = image.getWidth();
+ private static ResultPoint[] findVertices180(BitMatrix matrix) {
+ int height = matrix.getHeight();
+ int width = matrix.getWidth();
+ int halfWidth = width >> 1;
ResultPoint[] result = new ResultPoint[8];
- BitArray row = null;
boolean found = false;
- int[] loc = null;
// Top Left
for (int i = height - 1; i > 0; i--) {
- row = image.getBlackRow(i, null, 0, width / 4);
- row.reverse();
- loc = findGuardPattern(row, 0, START_PATTERN);
+ int[] loc = findGuardPattern(matrix, halfWidth, i, halfWidth, true, START_PATTERN_REVERSE);
if (loc != null) {
- result[0] = new ResultPoint(width - loc[0], i);
- result[4] = new ResultPoint(width - loc[1], i);
+ result[0] = new ResultPoint(loc[1], i);
+ result[4] = new ResultPoint(loc[0], i);
found = true;
break;
}
if (found) { // Found the Top Left vertex
found = false;
for (int i = 0; i < height; i++) {
- row = image.getBlackRow(i, null, 0, width / 4);
- row.reverse();
- loc = findGuardPattern(row, 0, START_PATTERN);
+ int[] loc = findGuardPattern(matrix, halfWidth, i, halfWidth, true, START_PATTERN_REVERSE);
if (loc != null) {
- result[1] = new ResultPoint(width - loc[0], i);
- result[5] = new ResultPoint(width - loc[1], i);
+ result[1] = new ResultPoint(loc[1], i);
+ result[5] = new ResultPoint(loc[0], i);
found = true;
break;
}
if (found) { // Found the Bottom Left vertex
found = false;
for (int i = height - 1; i > 0; i--) {
- row = image.getBlackRow(i, null, (width * 3) / 4, width / 4);
- loc = findGuardPattern(row, 0, 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++) {
- row = image.getBlackRow(i, null, (width * 3) / 4, width / 4);
- loc = findGuardPattern(row, 0, 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);
}
}
}
- if (found) {
- return result;
- } else {
- return null;
+ return found ? result : null;
+ }
+
+ /**
+ * 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
+ * <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) {
* @param moduleWidth estimated module size
* @return the number of modules in a row.
*/
- 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);
+ 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);
return ((((topRowDimension + bottomRowDimension) >> 1) + 8) / 17) * 17;
/*
* int topRowDimension = round(ResultPoint.distance(topLeft,
*/
}
- private static BitMatrix sampleGrid(MonochromeBitmapSource image,
- ResultPoint topLeft, ResultPoint bottomLeft, ResultPoint topRight,
- ResultPoint bottomRight, int dimension) throws ReaderException {
+ private static BitMatrix sampleGrid(BitMatrix matrix, ResultPoint 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();
- return sampler.sampleGrid(image, dimension, 0.0f, // p1ToX
+
+ return sampler.sampleGrid(matrix, dimension, 0.0f, // p1ToX
0.0f, // p1ToY
dimension, // p2ToX
0.0f, // p2ToY
bottomRight.getY(), // p3FromY
bottomLeft.getX(), // p4FromX
bottomLeft.getY()); // p4FromY
-
}
/**
}
/**
- * @param row row of black/white values to search
- * @param rowOffset position to start search
- * @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.
+ * @param matrix row of black/white values to search
+ * @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
+ * @return start/end horizontal offset of guard pattern, as an array of two ints.
*/
- static int[] findGuardPattern(BitArray row, int rowOffset, 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];
- int width = row.getSize();
- boolean isWhite = false;
+ boolean isWhite = whiteFirst;
int counterPosition = 0;
- int patternStart = rowOffset;
- for (int x = rowOffset; x < width; x++) {
- boolean pixel = row.get(x);
+ int patternStart = column;
+ for (int x = column; x < column + width; x++) {
+ boolean pixel = matrix.get(x, row);
if (pixel ^ isWhite) {
counters[counterPosition]++;
} else {
if (counterPosition == patternLength - 1) {
- if (patternMatchVariance(counters, pattern,
- MAX_INDIVIDUAL_VARIANCE) < MAX_AVG_VARIANCE) {
+ if (patternMatchVariance(counters, pattern, MAX_INDIVIDUAL_VARIANCE) < MAX_AVG_VARIANCE) {
return new int[]{patternStart, x};
}
patternStart += counters[0] + counters[1];
* 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;
}
projects / zxing.git / blobdiff