/* * Copyright 2012 ZXing authors * * Licensed under the Apache License, Version 2.0 (the "License"); * you may not use this file except in compliance with the License. * You may obtain a copy of the License at * * http://www.apache.org/licenses/LICENSE-2.0 * * Unless required by applicable law or agreed to in writing, software * distributed under the License is distributed on an "AS IS" BASIS, * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. * See the License for the specific language governing permissions and * limitations under the License. */ #import "ZXBitArray.h" #import "ZXBitMatrix.h" #import "ZXBinaryBitmap.h" #import "ZXDecodeHints.h" #import "ZXErrors.h" #import "ZXGridSampler.h" #import "ZXMathUtils.h" #import "ZXPDF417Detector.h" #import "ZXPDF417DetectorResult.h" #import "ZXPerspectiveTransform.h" #import "ZXResultPoint.h" const int ZX_PDF417_INDEXES_START_PATTERN[] = {0, 4, 1, 5}; const int ZX_PDF417_INDEXES_STOP_PATTERN[] = {6, 2, 7, 3}; const float ZX_PDF417_MAX_AVG_VARIANCE = 0.42f; const float ZX_PDF417_MAX_INDIVIDUAL_VARIANCE = 0.8f; // B S B S B S B S Bar/Space pattern // 11111111 0 1 0 1 0 1 000 const int ZX_PDF417_DETECTOR_START_PATTERN[] = {8, 1, 1, 1, 1, 1, 1, 3}; // 1111111 0 1 000 1 0 1 00 1 const int ZX_PDF417_DETECTOR_STOP_PATTERN[] = {7, 1, 1, 3, 1, 1, 1, 2, 1}; const int ZX_PDF417_MAX_PIXEL_DRIFT = 3; const int ZX_PDF417_MAX_PATTERN_DRIFT = 5; // if we set the value too low, then we don't detect the correct height of the bar if the start patterns are damaged. // if we set the value too high, then we might detect the start pattern from a neighbor barcode. const int ZX_PDF417_SKIPPED_ROW_COUNT_MAX = 25; // A PDF471 barcode should have at least 3 rows, with each row being >= 3 times the module width. Therefore it should be at least // 9 pixels tall. To be conservative, we use about half the size to ensure we don't miss it. const int ZX_PDF417_ROW_STEP = 5; const int ZX_PDF417_BARCODE_MIN_HEIGHT = 10; @implementation ZXPDF417Detector + (ZXPDF417DetectorResult *)detect:(ZXBinaryBitmap *)image hints:(ZXDecodeHints *)hints multiple:(BOOL)multiple error:(NSError **)error { // TODO detection improvement, tryHarder could try several different luminance thresholds/blackpoints or even // different binarizers //boolean tryHarder = hints != null && hints.containsKey(DecodeHintType.TRY_HARDER); ZXBitMatrix *bitMatrix = [image blackMatrixWithError:error]; NSArray *barcodeCoordinates = [self detect:multiple bitMatrix:bitMatrix error:error]; if (!barcodeCoordinates) { return nil; } if ([barcodeCoordinates count] == 0) { bitMatrix = [bitMatrix copy]; [bitMatrix rotate180]; barcodeCoordinates = [self detect:multiple bitMatrix:bitMatrix error:error]; if (!barcodeCoordinates) { return nil; } } return [[ZXPDF417DetectorResult alloc] initWithBits:bitMatrix points:barcodeCoordinates]; } /** * Detects PDF417 codes in an image. Only checks 0 degree rotation * @param multiple if true, then the image is searched for multiple codes. If false, then at most one code will * be found and returned * @param bitMatrix bit matrix to detect barcodes in * @return List of ResultPoint arrays containing the coordinates of found barcodes */ + (NSArray *)detect:(BOOL)multiple bitMatrix:(ZXBitMatrix *)bitMatrix error:(NSError **)error { NSMutableArray *barcodeCoordinates = [NSMutableArray array]; int row = 0; int column = 0; BOOL foundBarcodeInRow = NO; while (row < bitMatrix.height) { NSArray *vertices = [self findVertices:bitMatrix startRow:row startColumn:column]; if (vertices[0] == [NSNull null] && vertices[3] == [NSNull null]) { if (!foundBarcodeInRow) { // we didn't find any barcode so that's the end of searching break; } // we didn't find a barcode starting at the given column and row. Try again from the first column and slightly // below the lowest barcode we found so far. foundBarcodeInRow = NO; column = 0; for (NSArray *barcodeCoordinate in barcodeCoordinates) { if (barcodeCoordinate[1] != [NSNull null]) { row = MAX(row, (int) [(ZXResultPoint *)barcodeCoordinate[1] y]); } if (barcodeCoordinate[3] != [NSNull null]) { row = MAX(row, (int) [(ZXResultPoint *)barcodeCoordinate[3] y]); } } row += ZX_PDF417_ROW_STEP; continue; } foundBarcodeInRow = YES; [barcodeCoordinates addObject:vertices]; if (!multiple) { break; } // if we didn't find a right row indicator column, then continue the search for the next barcode after the // start pattern of the barcode just found. if (vertices[2] != [NSNull null]) { column = (int) [(ZXResultPoint *)vertices[2] x]; row = (int) [(ZXResultPoint *)vertices[2] y]; } else { column = (int) [(ZXResultPoint *)vertices[4] x]; row = (int) [(ZXResultPoint *)vertices[4] y]; } } return barcodeCoordinates; } /** * Locate the vertices and the codewords area of a black blob using the Start * and Stop patterns as locators. * * @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 */ + (NSMutableArray *)findVertices:(ZXBitMatrix *)matrix startRow:(int)startRow startColumn:(int)startColumn { int height = matrix.height; int width = matrix.width; NSMutableArray *result = [NSMutableArray arrayWithCapacity:8]; for (int i = 0; i < 8; i++) { [result addObject:[NSNull null]]; } [self copyToResult:result tmpResult:[self findRowsWithPattern:matrix height:height width:width startRow:startRow startColumn:startColumn pattern:ZX_PDF417_DETECTOR_START_PATTERN patternLen:sizeof(ZX_PDF417_DETECTOR_START_PATTERN) / sizeof(int)] destinationIndexes:ZX_PDF417_INDEXES_START_PATTERN length:sizeof(ZX_PDF417_INDEXES_START_PATTERN) / sizeof(int)]; if (result[4] != [NSNull null]) { startColumn = (int) [(ZXResultPoint *)result[4] x]; startRow = (int) [(ZXResultPoint *)result[4] y]; } [self copyToResult:result tmpResult:[self findRowsWithPattern:matrix height:height width:width startRow:startRow startColumn:startColumn pattern:ZX_PDF417_DETECTOR_STOP_PATTERN patternLen:sizeof(ZX_PDF417_DETECTOR_STOP_PATTERN) / sizeof(int)] destinationIndexes:ZX_PDF417_INDEXES_STOP_PATTERN length:sizeof(ZX_PDF417_INDEXES_STOP_PATTERN) / sizeof(int)]; return result; } + (void)copyToResult:(NSMutableArray *)result tmpResult:(NSMutableArray *)tmpResult destinationIndexes:(const int[])destinationIndexes length:(int)length { for (int i = 0; i < length; i++) { result[destinationIndexes[i]] = tmpResult[i]; } } + (NSMutableArray *)findRowsWithPattern:(ZXBitMatrix *)matrix height:(int)height width:(int)width startRow:(int)startRow startColumn:(int)startColumn pattern:(const int[])pattern patternLen:(int)patternLen { NSMutableArray *result = [NSMutableArray array]; for (int i = 0; i < 4; i++) { [result addObject:[NSNull null]]; } BOOL found = NO; int counters[patternLen]; memset(counters, 0, patternLen * sizeof(int)); for (; startRow < height; startRow += ZX_PDF417_ROW_STEP) { NSRange loc = [self findGuardPattern:matrix column:startColumn row:startRow width:width whiteFirst:false pattern:pattern patternLen:patternLen counters:counters]; if (loc.location != NSNotFound) { while (startRow > 0) { NSRange previousRowLoc = [self findGuardPattern:matrix column:startColumn row:--startRow width:width whiteFirst:false pattern:pattern patternLen:patternLen counters:counters]; if (previousRowLoc.location != NSNotFound) { loc = previousRowLoc; } else { startRow++; break; } } result[0] = [[ZXResultPoint alloc] initWithX:loc.location y:startRow]; result[1] = [[ZXResultPoint alloc] initWithX:NSMaxRange(loc) y:startRow]; found = YES; break; } } int stopRow = startRow + 1; // Last row of the current symbol that contains pattern if (found) { int skippedRowCount = 0; NSRange previousRowLoc = NSMakeRange((NSUInteger) [(ZXResultPoint *)result[0] x], ((NSUInteger)[(ZXResultPoint *)result[1] x]) - ((NSUInteger)[(ZXResultPoint *)result[0] x])); for (; stopRow < height; stopRow++) { NSRange loc = [self findGuardPattern:matrix column:(int)previousRowLoc.location row:stopRow width:width whiteFirst:NO pattern:pattern patternLen:patternLen counters:counters]; // a found pattern is only considered to belong to the same barcode if the start and end positions // don't differ too much. Pattern drift should be not bigger than two for consecutive rows. With // a higher number of skipped rows drift could be larger. To keep it simple for now, we allow a slightly // larger drift and don't check for skipped rows. if (loc.location != NSNotFound && ABS((int)previousRowLoc.location - (int)loc.location) < ZX_PDF417_MAX_PATTERN_DRIFT && ABS((int)NSMaxRange(previousRowLoc) - (int)NSMaxRange(loc)) < ZX_PDF417_MAX_PATTERN_DRIFT) { previousRowLoc = loc; skippedRowCount = 0; } else { if (skippedRowCount > ZX_PDF417_SKIPPED_ROW_COUNT_MAX) { break; } else { skippedRowCount++; } } } stopRow -= skippedRowCount + 1; result[2] = [[ZXResultPoint alloc] initWithX:previousRowLoc.location y:stopRow]; result[3] = [[ZXResultPoint alloc] initWithX:NSMaxRange(previousRowLoc) y:stopRow]; } if (stopRow - startRow < ZX_PDF417_BARCODE_MIN_HEIGHT) { for (int i = 0; i < 4; i++) { result[i] = [NSNull null]; } } return result; } /** * @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 * @param counters array of counters, as long as pattern, to re-use * @return start/end horizontal offset of guard pattern, as an array of two ints. */ + (NSRange)findGuardPattern:(ZXBitMatrix *)matrix column:(int)column row:(int)row width:(int)width whiteFirst:(BOOL)whiteFirst pattern:(const int[])pattern patternLen:(int)patternLen counters:(int *)counters { int patternLength = patternLen; memset(counters, 0, patternLength * sizeof(int)); BOOL isWhite = whiteFirst; int patternStart = column; int pixelDrift = 0; // if there are black pixels left of the current pixel shift to the left, but only for ZX_PDF417_MAX_PIXEL_DRIFT pixels while ([matrix getX:patternStart y:row] && patternStart > 0 && pixelDrift++ < ZX_PDF417_MAX_PIXEL_DRIFT) { patternStart--; } int x = patternStart; int counterPosition = 0; for (;x < width; x++) { BOOL pixel = [matrix getX:x y:row]; if (pixel ^ isWhite) { counters[counterPosition] = counters[counterPosition] + 1; } else { if (counterPosition == patternLength - 1) { if ([self patternMatchVariance:counters countersSize:patternLength pattern:pattern maxIndividualVariance:ZX_PDF417_MAX_INDIVIDUAL_VARIANCE] < ZX_PDF417_MAX_AVG_VARIANCE) { return NSMakeRange(patternStart, x - patternStart); } patternStart += counters[0] + counters[1]; for (int y = 2; y < patternLength; y++) { counters[y - 2] = counters[y]; } counters[patternLength - 2] = 0; counters[patternLength - 1] = 0; counterPosition--; } else { counterPosition++; } counters[counterPosition] = 1; isWhite = !isWhite; } } if (counterPosition == patternLength - 1) { if ([self patternMatchVariance:counters countersSize:patternLen pattern:pattern maxIndividualVariance:ZX_PDF417_MAX_INDIVIDUAL_VARIANCE] < ZX_PDF417_MAX_AVG_VARIANCE) { return NSMakeRange(patternStart, x - patternStart - 1); } } return NSMakeRange(NSNotFound, 0); } /** * Determines how closely a set of observed counts of runs of black/white * values matches a given target pattern. This is reported as the ratio of * 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 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 */ + (float)patternMatchVariance:(int *)counters countersSize:(int)countersSize pattern:(const int[])pattern maxIndividualVariance:(float)maxIndividualVariance { int numCounters = countersSize; int total = 0; int patternLength = 0; for (int i = 0; i < numCounters; i++) { total += counters[i]; patternLength += pattern[i]; } if (total < patternLength || patternLength == 0) { return FLT_MAX; } float unitBarWidth = (float) total / patternLength; maxIndividualVariance *= unitBarWidth; float totalVariance = 0.0f; for (int x = 0; x < numCounters; x++) { int counter = counters[x]; float scaledPattern = pattern[x] * unitBarWidth; float variance = counter > scaledPattern ? counter - scaledPattern : scaledPattern - counter; if (variance > maxIndividualVariance) { return FLT_MAX; } totalVariance += variance; } return totalVariance / total; } @end