2 * Copyright 2009 ZXing authors
\r
4 * Licensed under the Apache License, Version 2.0 (the "License");
\r
5 * you may not use this file except in compliance with the License.
\r
6 * You may obtain a copy of the License at
\r
8 * http://www.apache.org/licenses/LICENSE-2.0
\r
10 * Unless required by applicable law or agreed to in writing, software
\r
11 * distributed under the License is distributed on an "AS IS" BASIS,
\r
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
\r
13 * See the License for the specific language governing permissions and
\r
14 * limitations under the License.
\r
17 using BinaryBitmap = com.google.zxing.BinaryBitmap;
\r
18 using ReaderException = com.google.zxing.ReaderException;
\r
19 using ResultPoint = com.google.zxing.ResultPoint;
\r
20 using BitMatrix = com.google.zxing.common.BitMatrix;
\r
21 using DetectorResult = com.google.zxing.common.DetectorResult;
\r
22 using GridSampler = com.google.zxing.common.GridSampler;
\r
23 namespace com.google.zxing.pdf417.detector
\r
26 /// <summary> <p>Encapsulates logic that can detect a PDF417 Code in an image, even if the
\r
27 /// PDF417 Code is rotated or skewed, or partially obscured.</p>
\r
30 /// <author> SITA Lab (kevin.osullivan@sita.aero)
\r
32 /// <author> dswitkin@google.com (Daniel Switkin)
\r
34 /// <author>www.Redivivus.in (suraj.supekar@redivivus.in) - Ported from ZXING Java Source
\r
36 public sealed class Detector
\r
39 //UPGRADE_WARNING: Data types in Visual C# might be different. Verify the accuracy of narrowing conversions. "ms-help://MS.VSCC.v80/dv_commoner/local/redirect.htm?index='!DefaultContextWindowIndex'&keyword='jlca1042'"
\r
40 private static int MAX_AVG_VARIANCE = (int) SupportClass.Identity(((1 << 8) * 0.42f));
\r
41 //UPGRADE_WARNING: Data types in Visual C# might be different. Verify the accuracy of narrowing conversions. "ms-help://MS.VSCC.v80/dv_commoner/local/redirect.htm?index='!DefaultContextWindowIndex'&keyword='jlca1042'"
\r
42 private static int MAX_INDIVIDUAL_VARIANCE = (int) SupportClass.Identity(((1 << 8) * 0.8f));
\r
43 private const int SKEW_THRESHOLD = 2;
\r
45 // B S B S B S B S Bar/Space pattern
\r
46 // 11111111 0 1 0 1 0 1 000
\r
47 //UPGRADE_NOTE: Final was removed from the declaration of 'START_PATTERN'. "ms-help://MS.VSCC.v80/dv_commoner/local/redirect.htm?index='!DefaultContextWindowIndex'&keyword='jlca1003'"
\r
48 private static readonly int[] START_PATTERN = new int[]{8, 1, 1, 1, 1, 1, 1, 3};
\r
50 // 11111111 0 1 0 1 0 1 000
\r
51 //UPGRADE_NOTE: Final was removed from the declaration of 'START_PATTERN_REVERSE'. "ms-help://MS.VSCC.v80/dv_commoner/local/redirect.htm?index='!DefaultContextWindowIndex'&keyword='jlca1003'"
\r
52 private static readonly int[] START_PATTERN_REVERSE = new int[]{3, 1, 1, 1, 1, 1, 1, 8};
\r
54 // 1111111 0 1 000 1 0 1 00 1
\r
55 //UPGRADE_NOTE: Final was removed from the declaration of 'STOP_PATTERN'. "ms-help://MS.VSCC.v80/dv_commoner/local/redirect.htm?index='!DefaultContextWindowIndex'&keyword='jlca1003'"
\r
56 private static readonly int[] STOP_PATTERN = new int[]{7, 1, 1, 3, 1, 1, 1, 2, 1};
\r
58 // B S B S B S B S B Bar/Space pattern
\r
59 // 1111111 0 1 000 1 0 1 00 1
\r
60 //UPGRADE_NOTE: Final was removed from the declaration of 'STOP_PATTERN_REVERSE'. "ms-help://MS.VSCC.v80/dv_commoner/local/redirect.htm?index='!DefaultContextWindowIndex'&keyword='jlca1003'"
\r
61 private static readonly int[] STOP_PATTERN_REVERSE = new int[]{1, 2, 1, 1, 1, 3, 1, 1, 7};
\r
63 //UPGRADE_NOTE: Final was removed from the declaration of 'image '. "ms-help://MS.VSCC.v80/dv_commoner/local/redirect.htm?index='!DefaultContextWindowIndex'&keyword='jlca1003'"
\r
64 private BinaryBitmap image;
\r
66 public Detector(BinaryBitmap image)
\r
71 /// <summary> <p>Detects a PDF417 Code in an image, simply.</p>
\r
74 /// <returns> {@link DetectorResult} encapsulating results of detecting a PDF417 Code
\r
76 /// <throws> ReaderException if no QR Code can be found </throws>
\r
77 public DetectorResult detect()
\r
79 return detect(null);
\r
82 /// <summary> <p>Detects a PDF417 Code in an image. Only checks 0 and 180 degree rotations.</p>
\r
85 /// <param name="hints">optional hints to detector
\r
87 /// <returns> {@link DetectorResult} encapsulating results of detecting a PDF417 Code
\r
89 /// <throws> ReaderException if no PDF417 Code can be found </throws>
\r
90 public DetectorResult detect(System.Collections.Hashtable hints)
\r
92 // Fetch the 1 bit matrix once up front.
\r
93 BitMatrix matrix = image.BlackMatrix;
\r
95 // Try to find the vertices assuming the image is upright.
\r
96 ResultPoint[] vertices = findVertices(matrix);
\r
97 if (vertices == null)
\r
99 // Maybe the image is rotated 180 degrees?
\r
100 vertices = findVertices180(matrix);
\r
101 if (vertices != null)
\r
103 correctCodeWordVertices(vertices, true);
\r
108 correctCodeWordVertices(vertices, false);
\r
111 if (vertices != null)
\r
113 float moduleWidth = computeModuleWidth(vertices);
\r
114 if (moduleWidth < 1.0f)
\r
116 throw ReaderException.Instance;
\r
119 int dimension = computeDimension(vertices[4], vertices[6], vertices[5], vertices[7], moduleWidth);
\r
122 throw ReaderException.Instance;
\r
125 // Deskew and sample image.
\r
126 BitMatrix bits = sampleGrid(matrix, vertices[4], vertices[5], vertices[6], vertices[7], dimension);
\r
127 return new DetectorResult(bits, new ResultPoint[]{vertices[4], vertices[5], vertices[6], vertices[7]});
\r
131 throw ReaderException.Instance;
\r
135 /// <summary> Locate the vertices and the codewords area of a black blob using the Start
\r
136 /// and Stop patterns as locators. Assumes that the barcode begins in the left half
\r
137 /// of the image, and ends in the right half.
\r
138 /// TODO: Fix this assumption, allowing the barcode to be anywhere in the image.
\r
139 /// TODO: Scanning every row is very expensive. We should only do this for TRY_HARDER.
\r
142 /// <param name="matrix">the scanned barcode image.
\r
144 /// <returns> an array containing the vertices:
\r
145 /// vertices[0] x, y top left barcode
\r
146 /// vertices[1] x, y bottom left barcode
\r
147 /// vertices[2] x, y top right barcode
\r
148 /// vertices[3] x, y bottom right barcode
\r
149 /// vertices[4] x, y top left codeword area
\r
150 /// vertices[5] x, y bottom left codeword area
\r
151 /// vertices[6] x, y top right codeword area
\r
152 /// vertices[7] x, y bottom right codeword area
\r
154 private static ResultPoint[] findVertices(BitMatrix matrix)
\r
156 int height = matrix.Height;
\r
157 int width = matrix.Width;
\r
158 int halfWidth = width >> 1;
\r
160 ResultPoint[] result = new ResultPoint[8];
\r
161 bool found = false;
\r
164 for (int i = 0; i < height; i++)
\r
166 int[] loc = findGuardPattern(matrix, 0, i, halfWidth, false, START_PATTERN);
\r
169 result[0] = new ResultPoint(loc[0], i);
\r
170 result[4] = new ResultPoint(loc[1], i);
\r
178 // Found the Top Left vertex
\r
180 for (int i = height - 1; i > 0; i--)
\r
182 int[] loc = findGuardPattern(matrix, 0, i, halfWidth, false, START_PATTERN);
\r
185 result[1] = new ResultPoint(loc[0], i);
\r
186 result[5] = new ResultPoint(loc[1], i);
\r
195 // Found the Bottom Left vertex
\r
197 for (int i = 0; i < height; i++)
\r
199 int[] loc = findGuardPattern(matrix, halfWidth, i, halfWidth, false, STOP_PATTERN);
\r
202 result[2] = new ResultPoint(loc[1], i);
\r
203 result[6] = new ResultPoint(loc[0], i);
\r
212 // Found the Top right vertex
\r
214 for (int i = height - 1; i > 0; i--)
\r
216 int[] loc = findGuardPattern(matrix, halfWidth, i, halfWidth, false, STOP_PATTERN);
\r
219 result[3] = new ResultPoint(loc[1], i);
\r
220 result[7] = new ResultPoint(loc[0], i);
\r
226 return found?result:null;
\r
229 /// <summary> Locate the vertices and the codewords area of a black blob using the Start
\r
230 /// and Stop patterns as locators. This assumes that the image is rotated 180
\r
231 /// degrees and if it locates the start and stop patterns at it will re-map
\r
232 /// the vertices for a 0 degree rotation.
\r
233 /// TODO: Change assumption about barcode location.
\r
234 /// TODO: Scanning every row is very expensive. We should only do this for TRY_HARDER.
\r
237 /// <param name="matrix">the scanned barcode image.
\r
239 /// <returns> an array containing the vertices:
\r
240 /// vertices[0] x, y top left barcode
\r
241 /// vertices[1] x, y bottom left barcode
\r
242 /// vertices[2] x, y top right barcode
\r
243 /// vertices[3] x, y bottom right barcode
\r
244 /// vertices[4] x, y top left codeword area
\r
245 /// vertices[5] x, y bottom left codeword area
\r
246 /// vertices[6] x, y top right codeword area
\r
247 /// vertices[7] x, y bottom right codeword area
\r
249 private static ResultPoint[] findVertices180(BitMatrix matrix)
\r
251 int height = matrix.Height;
\r
252 int width = matrix.Width;
\r
253 int halfWidth = width >> 1;
\r
255 ResultPoint[] result = new ResultPoint[8];
\r
256 bool found = false;
\r
259 for (int i = height - 1; i > 0; i--)
\r
261 int[] loc = findGuardPattern(matrix, halfWidth, i, halfWidth, true, START_PATTERN_REVERSE);
\r
264 result[0] = new ResultPoint(loc[1], i);
\r
265 result[4] = new ResultPoint(loc[0], i);
\r
273 // Found the Top Left vertex
\r
275 for (int i = 0; i < height; i++)
\r
277 int[] loc = findGuardPattern(matrix, halfWidth, i, halfWidth, true, START_PATTERN_REVERSE);
\r
280 result[1] = new ResultPoint(loc[1], i);
\r
281 result[5] = new ResultPoint(loc[0], i);
\r
290 // Found the Bottom Left vertex
\r
292 for (int i = height - 1; i > 0; i--)
\r
294 int[] loc = findGuardPattern(matrix, 0, i, halfWidth, false, STOP_PATTERN_REVERSE);
\r
297 result[2] = new ResultPoint(loc[0], i);
\r
298 result[6] = new ResultPoint(loc[1], i);
\r
307 // Found the Top Right vertex
\r
309 for (int i = 0; i < height; i++)
\r
311 int[] loc = findGuardPattern(matrix, 0, i, halfWidth, false, STOP_PATTERN_REVERSE);
\r
314 result[3] = new ResultPoint(loc[0], i);
\r
315 result[7] = new ResultPoint(loc[1], i);
\r
321 return found?result:null;
\r
324 /// <summary> Because we scan horizontally to detect the start and stop patterns, the vertical component of
\r
325 /// the codeword coordinates will be slightly wrong if there is any skew or rotation in the image.
\r
326 /// This method moves those points back onto the edges of the theoretically perfect bounding
\r
327 /// quadrilateral if needed.
\r
330 /// <param name="vertices">The eight vertices located by findVertices().
\r
332 private static void correctCodeWordVertices(ResultPoint[] vertices, bool upsideDown)
\r
334 float skew = vertices[4].Y - vertices[6].Y;
\r
339 if (skew > SKEW_THRESHOLD)
\r
342 float length = vertices[4].X - vertices[0].X;
\r
343 float deltax = vertices[6].X - vertices[0].X;
\r
344 float deltay = vertices[6].Y - vertices[0].Y;
\r
345 float correction = length * deltay / deltax;
\r
346 vertices[4] = new ResultPoint(vertices[4].X, vertices[4].Y + correction);
\r
348 else if (- skew > SKEW_THRESHOLD)
\r
351 float length = vertices[2].X - vertices[6].X;
\r
352 float deltax = vertices[2].X - vertices[4].X;
\r
353 float deltay = vertices[2].Y - vertices[4].Y;
\r
354 float correction = length * deltay / deltax;
\r
355 vertices[6] = new ResultPoint(vertices[6].X, vertices[6].Y - correction);
\r
358 skew = vertices[7].Y - vertices[5].Y;
\r
363 if (skew > SKEW_THRESHOLD)
\r
366 float length = vertices[5].X - vertices[1].X;
\r
367 float deltax = vertices[7].X - vertices[1].X;
\r
368 float deltay = vertices[7].Y - vertices[1].Y;
\r
369 float correction = length * deltay / deltax;
\r
370 vertices[5] = new ResultPoint(vertices[5].X, vertices[5].Y + correction);
\r
372 else if (- skew > SKEW_THRESHOLD)
\r
375 float length = vertices[3].X - vertices[7].X;
\r
376 float deltax = vertices[3].X - vertices[5].X;
\r
377 float deltay = vertices[3].Y - vertices[5].Y;
\r
378 float correction = length * deltay / deltax;
\r
379 vertices[7] = new ResultPoint(vertices[7].X, vertices[7].Y - correction);
\r
383 /// <summary> <p>Estimates module size (pixels in a module) based on the Start and End
\r
384 /// finder patterns.</p>
\r
387 /// <param name="vertices">an array of vertices:
\r
388 /// vertices[0] x, y top left barcode
\r
389 /// vertices[1] x, y bottom left barcode
\r
390 /// vertices[2] x, y top right barcode
\r
391 /// vertices[3] x, y bottom right barcode
\r
392 /// vertices[4] x, y top left codeword area
\r
393 /// vertices[5] x, y bottom left codeword area
\r
394 /// vertices[6] x, y top right codeword area
\r
395 /// vertices[7] x, y bottom right codeword area
\r
397 /// <returns> the module size.
\r
399 private static float computeModuleWidth(ResultPoint[] vertices)
\r
401 float pixels1 = ResultPoint.distance(vertices[0], vertices[4]);
\r
402 float pixels2 = ResultPoint.distance(vertices[1], vertices[5]);
\r
403 float moduleWidth1 = (pixels1 + pixels2) / (17 * 2.0f);
\r
404 float pixels3 = ResultPoint.distance(vertices[6], vertices[2]);
\r
405 float pixels4 = ResultPoint.distance(vertices[7], vertices[3]);
\r
406 float moduleWidth2 = (pixels3 + pixels4) / (18 * 2.0f);
\r
407 return (moduleWidth1 + moduleWidth2) / 2.0f;
\r
410 /// <summary> Computes the dimension (number of modules in a row) of the PDF417 Code
\r
411 /// based on vertices of the codeword area and estimated module size.
\r
414 /// <param name="topLeft"> of codeword area
\r
416 /// <param name="topRight"> of codeword area
\r
418 /// <param name="bottomLeft"> of codeword area
\r
420 /// <param name="bottomRight">of codeword are
\r
422 /// <param name="moduleWidth">estimated module size
\r
424 /// <returns> the number of modules in a row.
\r
426 private static int computeDimension(ResultPoint topLeft, ResultPoint topRight, ResultPoint bottomLeft, ResultPoint bottomRight, float moduleWidth)
\r
428 int topRowDimension = round(ResultPoint.distance(topLeft, topRight) / moduleWidth);
\r
429 int bottomRowDimension = round(ResultPoint.distance(bottomLeft, bottomRight) / moduleWidth);
\r
430 return ((((topRowDimension + bottomRowDimension) >> 1) + 8) / 17) * 17;
\r
432 * int topRowDimension = round(ResultPoint.distance(topLeft,
\r
433 * topRight)); //moduleWidth); int bottomRowDimension =
\r
434 * round(ResultPoint.distance(bottomLeft, bottomRight)); //
\r
435 * moduleWidth); int dimension = ((topRowDimension + bottomRowDimension)
\r
436 * >> 1); // Round up to nearest 17 modules i.e. there are 17 modules per
\r
437 * codeword //int dimension = ((((topRowDimension + bottomRowDimension) >>
\r
438 * 1) + 8) / 17) * 17; return dimension;
\r
442 private static BitMatrix sampleGrid(BitMatrix matrix, ResultPoint topLeft, ResultPoint bottomLeft, ResultPoint topRight, ResultPoint bottomRight, int dimension)
\r
445 // Note that unlike the QR Code sampler, we didn't find the center of modules, but the
\r
446 // very corners. So there is no 0.5f here; 0.0f is right.
\r
447 GridSampler sampler = GridSampler.Instance;
\r
449 return sampler.sampleGrid(matrix, dimension, 0.0f, 0.0f, dimension, 0.0f, dimension, dimension, 0.0f, dimension, topLeft.X, topLeft.Y, topRight.X, topRight.Y, bottomRight.X, bottomRight.Y, bottomLeft.X, bottomLeft.Y); // p4FromY
\r
452 /// <summary> Ends up being a bit faster than Math.round(). This merely rounds its
\r
453 /// argument to the nearest int, where x.5 rounds up.
\r
455 private static int round(float d)
\r
457 //UPGRADE_WARNING: Data types in Visual C# might be different. Verify the accuracy of narrowing conversions. "ms-help://MS.VSCC.v80/dv_commoner/local/redirect.htm?index='!DefaultContextWindowIndex'&keyword='jlca1042'"
\r
458 return (int) (d + 0.5f);
\r
461 /// <param name="matrix">row of black/white values to search
\r
463 /// <param name="column">x position to start search
\r
465 /// <param name="row">y position to start search
\r
467 /// <param name="width">the number of pixels to search on this row
\r
469 /// <param name="pattern">pattern of counts of number of black and white pixels that are
\r
470 /// being searched for as a pattern
\r
472 /// <returns> start/end horizontal offset of guard pattern, as an array of two ints.
\r
474 private static int[] findGuardPattern(BitMatrix matrix, int column, int row, int width, bool whiteFirst, int[] pattern)
\r
476 int patternLength = pattern.Length;
\r
477 // TODO: Find a way to cache this array, as this method is called hundreds of times
\r
478 // per image, and we want to allocate as seldom as possible.
\r
479 int[] counters = new int[patternLength];
\r
480 bool isWhite = whiteFirst;
\r
482 int counterPosition = 0;
\r
483 int patternStart = column;
\r
484 for (int x = column; x < column + width; x++)
\r
486 bool pixel = matrix.get_Renamed(x, row);
\r
487 if (pixel ^ isWhite)
\r
489 counters[counterPosition]++;
\r
493 if (counterPosition == patternLength - 1)
\r
495 if (patternMatchVariance(counters, pattern, MAX_INDIVIDUAL_VARIANCE) < MAX_AVG_VARIANCE)
\r
497 return new int[]{patternStart, x};
\r
499 patternStart += counters[0] + counters[1];
\r
500 for (int y = 2; y < patternLength; y++)
\r
502 counters[y - 2] = counters[y];
\r
504 counters[patternLength - 2] = 0;
\r
505 counters[patternLength - 1] = 0;
\r
512 counters[counterPosition] = 1;
\r
513 isWhite = !isWhite;
\r
519 /// <summary> Determines how closely a set of observed counts of runs of black/white
\r
520 /// values matches a given target pattern. This is reported as the ratio of
\r
521 /// the total variance from the expected pattern proportions across all
\r
522 /// pattern elements, to the length of the pattern.
\r
525 /// <param name="counters">observed counters
\r
527 /// <param name="pattern">expected pattern
\r
529 /// <param name="maxIndividualVariance">The most any counter can differ before we give up
\r
531 /// <returns> ratio of total variance between counters and pattern compared to
\r
532 /// total pattern size, where the ratio has been multiplied by 256.
\r
533 /// So, 0 means no variance (perfect match); 256 means the total
\r
534 /// variance between counters and patterns equals the pattern length,
\r
535 /// higher values mean even more variance
\r
537 private static int patternMatchVariance(int[] counters, int[] pattern, int maxIndividualVariance)
\r
539 int numCounters = counters.Length;
\r
541 int patternLength = 0;
\r
542 for (int i = 0; i < numCounters; i++)
\r
544 total += counters[i];
\r
545 patternLength += pattern[i];
\r
547 if (total < patternLength)
\r
549 // If we don't even have one pixel per unit of bar width, assume this
\r
550 // is too small to reliably match, so fail:
\r
551 return System.Int32.MaxValue;
\r
553 // We're going to fake floating-point math in integers. We just need to use more bits.
\r
554 // Scale up patternLength so that intermediate values below like scaledCounter will have
\r
555 // more "significant digits".
\r
556 int unitBarWidth = (total << 8) / patternLength;
\r
557 maxIndividualVariance = (maxIndividualVariance * unitBarWidth) >> 8;
\r
559 int totalVariance = 0;
\r
560 for (int x = 0; x < numCounters; x++)
\r
562 int counter = counters[x] << 8;
\r
563 int scaledPattern = pattern[x] * unitBarWidth;
\r
564 int variance = counter > scaledPattern?counter - scaledPattern:scaledPattern - counter;
\r
565 if (variance > maxIndividualVariance)
\r
567 return System.Int32.MaxValue;
\r
569 totalVariance += variance;
\r
571 return totalVariance / total;
\r