2 * Copyright 2009 ZXing authors
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
8 * http://www.apache.org/licenses/LICENSE-2.0
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
17 package com.google.zxing.pdf417.detector;
19 import com.google.zxing.BinaryBitmap;
20 import com.google.zxing.ReaderException;
21 import com.google.zxing.ResultPoint;
22 import com.google.zxing.common.BitMatrix;
23 import com.google.zxing.common.DetectorResult;
24 import com.google.zxing.common.GridSampler;
26 import java.util.Hashtable;
29 * <p>Encapsulates logic that can detect a PDF417 Code in an image, even if the
30 * PDF417 Code is rotated or skewed, or partially obscured.</p>
32 * @author SITA Lab (kevin.osullivan@sita.aero)
33 * @author dswitkin@google.com (Daniel Switkin)
35 public final class Detector {
37 private static final int MAX_AVG_VARIANCE = (int) ((1 << 8) * 0.42f);
38 private static final int MAX_INDIVIDUAL_VARIANCE = (int) ((1 << 8) * 0.8f);
39 private static final int SKEW_THRESHOLD = 2;
41 // B S B S B S B S Bar/Space pattern
42 // 11111111 0 1 0 1 0 1 000
43 private static final int[] START_PATTERN = {8, 1, 1, 1, 1, 1, 1, 3};
45 // 11111111 0 1 0 1 0 1 000
46 private static final int[] START_PATTERN_REVERSE = {3, 1, 1, 1, 1, 1, 1, 8};
48 // 1111111 0 1 000 1 0 1 00 1
49 private static final int[] STOP_PATTERN = {7, 1, 1, 3, 1, 1, 1, 2, 1};
51 // B S B S B S B S B Bar/Space pattern
52 // 1111111 0 1 000 1 0 1 00 1
53 private static final int[] STOP_PATTERN_REVERSE = {1, 2, 1, 1, 1, 3, 1, 1, 7};
55 private final BinaryBitmap image;
57 public Detector(BinaryBitmap image) {
62 * <p>Detects a PDF417 Code in an image, simply.</p>
64 * @return {@link DetectorResult} encapsulating results of detecting a PDF417 Code
65 * @throws ReaderException if no QR Code can be found
67 public DetectorResult detect() throws ReaderException {
72 * <p>Detects a PDF417 Code in an image. Only checks 0 and 180 degree rotations.</p>
74 * @param hints optional hints to detector
75 * @return {@link DetectorResult} encapsulating results of detecting a PDF417 Code
76 * @throws ReaderException if no PDF417 Code can be found
78 public DetectorResult detect(Hashtable hints) throws ReaderException {
79 // Fetch the 1 bit matrix once up front.
80 BitMatrix matrix = image.getBlackMatrix();
82 // Try to find the vertices assuming the image is upright.
83 ResultPoint[] vertices = findVertices(matrix);
84 if (vertices == null) {
85 // Maybe the image is rotated 180 degrees?
86 vertices = findVertices180(matrix);
87 if (vertices != null) {
88 correctCodeWordVertices(vertices, true);
91 correctCodeWordVertices(vertices, false);
94 if (vertices != null) {
95 float moduleWidth = computeModuleWidth(vertices);
96 if (moduleWidth < 1.0f) {
97 throw ReaderException.getInstance();
100 int dimension = computeDimension(vertices[4], vertices[6],
101 vertices[5], vertices[7], moduleWidth);
103 // Deskew and sample image.
104 BitMatrix bits = sampleGrid(matrix, vertices[4], vertices[5],
105 vertices[6], vertices[7], dimension);
106 return new DetectorResult(bits, new ResultPoint[]{vertices[4],
107 vertices[5], vertices[6], vertices[7]});
109 throw ReaderException.getInstance();
114 * Locate the vertices and the codewords area of a black blob using the Start
115 * and Stop patterns as locators. Assumes that the barcode begins in the left half
116 * of the image, and ends in the right half.
117 * TODO: Fix this assumption, allowing the barcode to be anywhere in the image.
118 * TODO: Scanning every row is very expensive. We should only do this for TRY_HARDER.
120 * @param matrix the scanned barcode image.
121 * @return an array containing the vertices:
122 * vertices[0] x, y top left barcode
123 * vertices[1] x, y bottom left barcode
124 * vertices[2] x, y top right barcode
125 * vertices[3] x, y bottom right barcode
126 * vertices[4] x, y top left codeword area
127 * vertices[5] x, y bottom left codeword area
128 * vertices[6] x, y top right codeword area
129 * vertices[7] x, y bottom right codeword area
131 private static ResultPoint[] findVertices(BitMatrix matrix) {
132 int height = matrix.getHeight();
133 int width = matrix.getWidth();
134 int halfWidth = width >> 1;
136 ResultPoint[] result = new ResultPoint[8];
137 boolean found = false;
140 for (int i = 0; i < height; i++) {
141 int[] loc = findGuardPattern(matrix, 0, i, halfWidth, false, START_PATTERN);
143 result[0] = new ResultPoint(loc[0], i);
144 result[4] = new ResultPoint(loc[1], i);
150 if (found) { // Found the Top Left vertex
152 for (int i = height - 1; i > 0; i--) {
153 int[] loc = findGuardPattern(matrix, 0, i, halfWidth, false, START_PATTERN);
155 result[1] = new ResultPoint(loc[0], i);
156 result[5] = new ResultPoint(loc[1], i);
163 if (found) { // Found the Bottom Left vertex
165 for (int i = 0; i < height; i++) {
166 int[] loc = findGuardPattern(matrix, halfWidth, i, halfWidth, false, STOP_PATTERN);
168 result[2] = new ResultPoint(loc[1], i);
169 result[6] = new ResultPoint(loc[0], i);
176 if (found) { // Found the Top right vertex
178 for (int i = height - 1; i > 0; i--) {
179 int[] loc = findGuardPattern(matrix, halfWidth, i, halfWidth, false, STOP_PATTERN);
181 result[3] = new ResultPoint(loc[1], i);
182 result[7] = new ResultPoint(loc[0], i);
188 return found ? result : null;
192 * Locate the vertices and the codewords area of a black blob using the Start
193 * and Stop patterns as locators. This assumes that the image is rotated 180
194 * degrees and if it locates the start and stop patterns at it will re-map
195 * the vertices for a 0 degree rotation.
196 * TODO: Change assumption about barcode location.
197 * TODO: Scanning every row is very expensive. We should only do this for TRY_HARDER.
199 * @param matrix the scanned barcode image.
200 * @return an array containing the vertices:
201 * vertices[0] x, y top left barcode
202 * vertices[1] x, y bottom left barcode
203 * vertices[2] x, y top right barcode
204 * vertices[3] x, y bottom right barcode
205 * vertices[4] x, y top left codeword area
206 * vertices[5] x, y bottom left codeword area
207 * vertices[6] x, y top right codeword area
208 * vertices[7] x, y bottom right codeword area
210 private static ResultPoint[] findVertices180(BitMatrix matrix) {
211 int height = matrix.getHeight();
212 int width = matrix.getWidth();
213 int halfWidth = width >> 1;
215 ResultPoint[] result = new ResultPoint[8];
216 boolean found = false;
219 for (int i = height - 1; i > 0; i--) {
220 int[] loc = findGuardPattern(matrix, halfWidth, i, halfWidth, true, START_PATTERN_REVERSE);
222 result[0] = new ResultPoint(loc[1], i);
223 result[4] = new ResultPoint(loc[0], i);
229 if (found) { // Found the Top Left vertex
231 for (int i = 0; i < height; i++) {
232 int[] loc = findGuardPattern(matrix, halfWidth, i, halfWidth, true, START_PATTERN_REVERSE);
234 result[1] = new ResultPoint(loc[1], i);
235 result[5] = new ResultPoint(loc[0], i);
242 if (found) { // Found the Bottom Left vertex
244 for (int i = height - 1; i > 0; i--) {
245 int[] loc = findGuardPattern(matrix, 0, i, halfWidth, false, STOP_PATTERN_REVERSE);
247 result[2] = new ResultPoint(loc[0], i);
248 result[6] = new ResultPoint(loc[1], i);
255 if (found) { // Found the Top Right vertex
257 for (int i = 0; i < height; i++) {
258 int[] loc = findGuardPattern(matrix, 0, i, halfWidth, false, STOP_PATTERN_REVERSE);
260 result[3] = new ResultPoint(loc[0], i);
261 result[7] = new ResultPoint(loc[1], i);
267 return found ? result : null;
271 * Because we scan horizontally to detect the start and stop patterns, the vertical component of
272 * the codeword coordinates will be slightly wrong if there is any skew or rotation in the image.
273 * This method moves those points back onto the edges of the theoretically perfect bounding
274 * quadrilateral if needed.
276 * @param vertices The eight vertices located by findVertices().
278 private static void correctCodeWordVertices(ResultPoint[] vertices, boolean upsideDown) {
279 float skew = vertices[4].getY() - vertices[6].getY();
283 if (skew > SKEW_THRESHOLD) {
285 float length = vertices[4].getX() - vertices[0].getX();
286 float deltax = vertices[6].getX() - vertices[0].getX();
287 float deltay = vertices[6].getY() - vertices[0].getY();
288 float correction = length * deltay / deltax;
289 vertices[4] = new ResultPoint(vertices[4].getX(), vertices[4].getY() + correction);
290 } else if (-skew > SKEW_THRESHOLD) {
292 float length = vertices[2].getX() - vertices[6].getX();
293 float deltax = vertices[2].getX() - vertices[4].getX();
294 float deltay = vertices[2].getY() - vertices[4].getY();
295 float correction = length * deltay / deltax;
296 vertices[6] = new ResultPoint(vertices[6].getX(), vertices[6].getY() - correction);
299 skew = vertices[7].getY() - vertices[5].getY();
303 if (skew > SKEW_THRESHOLD) {
305 float length = vertices[5].getX() - vertices[1].getX();
306 float deltax = vertices[7].getX() - vertices[1].getX();
307 float deltay = vertices[7].getY() - vertices[1].getY();
308 float correction = length * deltay / deltax;
309 vertices[5] = new ResultPoint(vertices[5].getX(), vertices[5].getY() + correction);
310 } else if (-skew > SKEW_THRESHOLD) {
312 float length = vertices[3].getX() - vertices[7].getX();
313 float deltax = vertices[3].getX() - vertices[5].getX();
314 float deltay = vertices[3].getY() - vertices[5].getY();
315 float correction = length * deltay / deltax;
316 vertices[7] = new ResultPoint(vertices[7].getX(), vertices[7].getY() - correction);
321 * <p>Estimates module size (pixels in a module) based on the Start and End
322 * finder patterns.</p>
324 * @param vertices an array of vertices:
325 * vertices[0] x, y top left barcode
326 * vertices[1] x, y bottom left barcode
327 * vertices[2] x, y top right barcode
328 * vertices[3] x, y bottom right barcode
329 * vertices[4] x, y top left codeword area
330 * vertices[5] x, y bottom left codeword area
331 * vertices[6] x, y top right codeword area
332 * vertices[7] x, y bottom right codeword area
333 * @return the module size.
335 private static float computeModuleWidth(ResultPoint[] vertices) {
336 float pixels1 = ResultPoint.distance(vertices[0], vertices[4]);
337 float pixels2 = ResultPoint.distance(vertices[1], vertices[5]);
338 float moduleWidth1 = (pixels1 + pixels2) / (17 * 2.0f);
339 float pixels3 = ResultPoint.distance(vertices[6], vertices[2]);
340 float pixels4 = ResultPoint.distance(vertices[7], vertices[3]);
341 float moduleWidth2 = (pixels3 + pixels4) / (18 * 2.0f);
342 return (moduleWidth1 + moduleWidth2) / 2.0f;
346 * Computes the dimension (number of modules in a row) of the PDF417 Code
347 * based on vertices of the codeword area and estimated module size.
349 * @param topLeft of codeword area
350 * @param topRight of codeword area
351 * @param bottomLeft of codeword area
352 * @param bottomRight of codeword are
353 * @param moduleWidth estimated module size
354 * @return the number of modules in a row.
356 private static int computeDimension(ResultPoint topLeft, ResultPoint topRight,
357 ResultPoint bottomLeft, ResultPoint bottomRight, float moduleWidth) {
358 int topRowDimension = round(ResultPoint.distance(topLeft, topRight) / moduleWidth);
359 int bottomRowDimension = round(ResultPoint.distance(bottomLeft, bottomRight) / moduleWidth);
360 return ((((topRowDimension + bottomRowDimension) >> 1) + 8) / 17) * 17;
362 * int topRowDimension = round(ResultPoint.distance(topLeft,
363 * topRight)); //moduleWidth); int bottomRowDimension =
364 * round(ResultPoint.distance(bottomLeft, bottomRight)); //
365 * moduleWidth); int dimension = ((topRowDimension + bottomRowDimension)
366 * >> 1); // Round up to nearest 17 modules i.e. there are 17 modules per
367 * codeword //int dimension = ((((topRowDimension + bottomRowDimension) >>
368 * 1) + 8) / 17) * 17; return dimension;
372 private static BitMatrix sampleGrid(BitMatrix matrix, ResultPoint topLeft,
373 ResultPoint bottomLeft, ResultPoint topRight, ResultPoint bottomRight, int dimension)
374 throws ReaderException {
376 // Note that unlike the QR Code sampler, we didn't find the center of modules, but the
377 // very corners. So there is no 0.5f here; 0.0f is right.
378 GridSampler sampler = GridSampler.getInstance();
380 return sampler.sampleGrid(matrix, dimension, 0.0f, // p1ToX
388 topLeft.getX(), // p1FromX
389 topLeft.getY(), // p1FromY
390 topRight.getX(), // p2FromX
391 topRight.getY(), // p2FromY
392 bottomRight.getX(), // p3FromX
393 bottomRight.getY(), // p3FromY
394 bottomLeft.getX(), // p4FromX
395 bottomLeft.getY()); // p4FromY
399 * Ends up being a bit faster than Math.round(). This merely rounds its
400 * argument to the nearest int, where x.5 rounds up.
402 private static int round(float d) {
403 return (int) (d + 0.5f);
407 * @param matrix row of black/white values to search
408 * @param column x position to start search
409 * @param row y position to start search
410 * @param width the number of pixels to search on this row
411 * @param pattern pattern of counts of number of black and white pixels that are
412 * being searched for as a pattern
413 * @return start/end horizontal offset of guard pattern, as an array of two ints.
415 private static int[] findGuardPattern(BitMatrix matrix, int column, int row, int width,
416 boolean whiteFirst, int[] pattern) {
417 int patternLength = pattern.length;
418 // TODO: Find a way to cache this array, as this method is called hundreds of times
419 // per image, and we want to allocate as seldom as possible.
420 int[] counters = new int[patternLength];
421 boolean isWhite = whiteFirst;
423 int counterPosition = 0;
424 int patternStart = column;
425 for (int x = column; x < column + width; x++) {
426 boolean pixel = matrix.get(x, row);
427 if (pixel ^ isWhite) {
428 counters[counterPosition]++;
430 if (counterPosition == patternLength - 1) {
431 if (patternMatchVariance(counters, pattern, MAX_INDIVIDUAL_VARIANCE) < MAX_AVG_VARIANCE) {
432 return new int[]{patternStart, x};
434 patternStart += counters[0] + counters[1];
435 for (int y = 2; y < patternLength; y++) {
436 counters[y - 2] = counters[y];
438 counters[patternLength - 2] = 0;
439 counters[patternLength - 1] = 0;
444 counters[counterPosition] = 1;
452 * Determines how closely a set of observed counts of runs of black/white
453 * values matches a given target pattern. This is reported as the ratio of
454 * the total variance from the expected pattern proportions across all
455 * pattern elements, to the length of the pattern.
457 * @param counters observed counters
458 * @param pattern expected pattern
459 * @param maxIndividualVariance The most any counter can differ before we give up
460 * @return ratio of total variance between counters and pattern compared to
461 * total pattern size, where the ratio has been multiplied by 256.
462 * So, 0 means no variance (perfect match); 256 means the total
463 * variance between counters and patterns equals the pattern length,
464 * higher values mean even more variance
466 private static int patternMatchVariance(int[] counters, int[] pattern, int maxIndividualVariance) {
467 int numCounters = counters.length;
469 int patternLength = 0;
470 for (int i = 0; i < numCounters; i++) {
471 total += counters[i];
472 patternLength += pattern[i];
474 if (total < patternLength) {
475 // If we don't even have one pixel per unit of bar width, assume this
476 // is too small to reliably match, so fail:
477 return Integer.MAX_VALUE;
479 // We're going to fake floating-point math in integers. We just need to use more bits.
480 // Scale up patternLength so that intermediate values below like scaledCounter will have
481 // more "significant digits".
482 int unitBarWidth = (total << 8) / patternLength;
483 maxIndividualVariance = (maxIndividualVariance * unitBarWidth) >> 8;
485 int totalVariance = 0;
486 for (int x = 0; x < numCounters; x++) {
487 int counter = counters[x] << 8;
488 int scaledPattern = pattern[x] * unitBarWidth;
489 int variance = counter > scaledPattern ? counter - scaledPattern : scaledPattern - counter;
490 if (variance > maxIndividualVariance) {
491 return Integer.MAX_VALUE;
493 totalVariance += variance;
495 return totalVariance / total;