/*
|
* 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 "ZXBitMatrix.h"
|
#import "ZXDecodeHints.h"
|
#import "ZXErrors.h"
|
#import "ZXMultiFinderPatternFinder.h"
|
#import "ZXQRCodeFinderPattern.h"
|
#import "ZXQRCodeFinderPatternInfo.h"
|
|
// TODO MIN_MODULE_COUNT and MAX_MODULE_COUNT would be great hints to ask the user for
|
// since it limits the number of regions to decode
|
|
// max. legal count of modules per QR code edge (177)
|
float const ZX_MAX_MODULE_COUNT_PER_EDGE = 180;
|
// min. legal count per modules per QR code edge (11)
|
float const ZX_MIN_MODULE_COUNT_PER_EDGE = 9;
|
|
/**
|
* More or less arbitrary cutoff point for determining if two finder patterns might belong
|
* to the same code if they differ less than DIFF_MODSIZE_CUTOFF_PERCENT percent in their
|
* estimated modules sizes.
|
*/
|
float const ZX_DIFF_MODSIZE_CUTOFF_PERCENT = 0.05f;
|
|
/**
|
* More or less arbitrary cutoff point for determining if two finder patterns might belong
|
* to the same code if they differ less than DIFF_MODSIZE_CUTOFF pixels/module in their
|
* estimated modules sizes.
|
*/
|
float const ZX_DIFF_MODSIZE_CUTOFF = 0.5f;
|
|
@implementation ZXMultiFinderPatternFinder
|
|
/**
|
* Returns the 3 best {@link FinderPattern}s from our list of candidates. The "best" are
|
* those that have been detected at least {@link #CENTER_QUORUM} times, and whose module
|
* size differs from the average among those patterns the least
|
*/
|
- (NSArray *)selectBestPatternsWithError:(NSError **)error {
|
NSMutableArray *_possibleCenters = [NSMutableArray arrayWithArray:[self possibleCenters]];
|
NSUInteger size = [_possibleCenters count];
|
|
if (size < 3) {
|
if (error) *error = ZXNotFoundErrorInstance();
|
return nil;
|
}
|
|
/*
|
* Begin HE modifications to safely detect multiple codes of equal size
|
*/
|
if (size == 3) {
|
return @[[@[_possibleCenters[0], _possibleCenters[1], _possibleCenters[2]] mutableCopy]];
|
}
|
|
[_possibleCenters sortUsingFunction:moduleSizeCompare context:nil];
|
|
/*
|
* Now lets start: build a list of tuples of three finder locations that
|
* - feature similar module sizes
|
* - are placed in a distance so the estimated module count is within the QR specification
|
* - have similar distance between upper left/right and left top/bottom finder patterns
|
* - form a triangle with 90° angle (checked by comparing top right/bottom left distance
|
* with pythagoras)
|
*
|
* Note: we allow each point to be used for more than one code region: this might seem
|
* counterintuitive at first, but the performance penalty is not that big. At this point,
|
* we cannot make a good quality decision whether the three finders actually represent
|
* a QR code, or are just by chance layouted so it looks like there might be a QR code there.
|
* So, if the layout seems right, lets have the decoder try to decode.
|
*/
|
|
NSMutableArray *results = [NSMutableArray array];
|
|
for (int i1 = 0; i1 < (size - 2); i1++) {
|
ZXQRCodeFinderPattern *p1 = self.possibleCenters[i1];
|
if (p1 == nil) {
|
continue;
|
}
|
|
for (int i2 = i1 + 1; i2 < (size - 1); i2++) {
|
ZXQRCodeFinderPattern *p2 = self.possibleCenters[i2];
|
if (p2 == nil) {
|
continue;
|
}
|
|
float vModSize12 = ([p1 estimatedModuleSize] - [p2 estimatedModuleSize]) / MIN([p1 estimatedModuleSize], [p2 estimatedModuleSize]);
|
float vModSize12A = fabsf([p1 estimatedModuleSize] - [p2 estimatedModuleSize]);
|
if (vModSize12A > ZX_DIFF_MODSIZE_CUTOFF && vModSize12 >= ZX_DIFF_MODSIZE_CUTOFF_PERCENT) {
|
break;
|
}
|
|
for (int i3 = i2 + 1; i3 < size; i3++) {
|
ZXQRCodeFinderPattern *p3 = self.possibleCenters[i3];
|
if (p3 == nil) {
|
continue;
|
}
|
|
float vModSize23 = ([p2 estimatedModuleSize] - [p3 estimatedModuleSize]) / MIN([p2 estimatedModuleSize], [p3 estimatedModuleSize]);
|
float vModSize23A = fabsf([p2 estimatedModuleSize] - [p3 estimatedModuleSize]);
|
if (vModSize23A > ZX_DIFF_MODSIZE_CUTOFF && vModSize23 >= ZX_DIFF_MODSIZE_CUTOFF_PERCENT) {
|
break;
|
}
|
|
NSMutableArray *test = [NSMutableArray arrayWithObjects:p1, p2, p3, nil];
|
[ZXResultPoint orderBestPatterns:test];
|
|
ZXQRCodeFinderPatternInfo *info = [[ZXQRCodeFinderPatternInfo alloc] initWithPatternCenters:test];
|
float dA = [ZXResultPoint distance:[info topLeft] pattern2:[info bottomLeft]];
|
float dC = [ZXResultPoint distance:[info topRight] pattern2:[info bottomLeft]];
|
float dB = [ZXResultPoint distance:[info topLeft] pattern2:[info topRight]];
|
|
float estimatedModuleCount = (dA + dB) / ([p1 estimatedModuleSize] * 2.0f);
|
if (estimatedModuleCount > ZX_MAX_MODULE_COUNT_PER_EDGE || estimatedModuleCount < ZX_MIN_MODULE_COUNT_PER_EDGE) {
|
continue;
|
}
|
|
float vABBC = fabsf((dA - dB) / MIN(dA, dB));
|
if (vABBC >= 0.1f) {
|
continue;
|
}
|
|
float dCpy = (float)sqrt(dA * dA + dB * dB);
|
float vPyC = fabsf((dC - dCpy) / MIN(dC, dCpy));
|
|
if (vPyC >= 0.1f) {
|
continue;
|
}
|
|
[results addObject:test];
|
}
|
}
|
}
|
|
if ([results count] > 0) {
|
return results;
|
}
|
|
if (error) *error = ZXNotFoundErrorInstance();
|
return nil;
|
}
|
|
- (NSArray *)findMulti:(ZXDecodeHints *)hints error:(NSError **)error {
|
BOOL tryHarder = hints != nil && hints.tryHarder;
|
BOOL pureBarcode = hints != nil && hints.pureBarcode;
|
int maxI = self.image.height;
|
int maxJ = self.image.width;
|
// We are looking for black/white/black/white/black modules in
|
// 1:1:3:1:1 ratio; this tracks the number of such modules seen so far
|
|
// Let's assume that the maximum version QR Code we support takes up 1/4 the height of the
|
// image, and then account for the center being 3 modules in size. This gives the smallest
|
// number of pixels the center could be, so skip this often. When trying harder, look for all
|
// QR versions regardless of how dense they are.
|
int iSkip = (int)(maxI / (ZX_FINDER_PATTERN_MAX_MODULES * 4.0f) * 3);
|
if (iSkip < ZX_FINDER_PATTERN_MIN_SKIP || tryHarder) {
|
iSkip = ZX_FINDER_PATTERN_MIN_SKIP;
|
}
|
|
int stateCount[5];
|
for (int i = iSkip - 1; i < maxI; i += iSkip) {
|
stateCount[0] = 0;
|
stateCount[1] = 0;
|
stateCount[2] = 0;
|
stateCount[3] = 0;
|
stateCount[4] = 0;
|
int currentState = 0;
|
|
for (int j = 0; j < maxJ; j++) {
|
if ([self.image getX:j y:i]) {
|
if ((currentState & 1) == 1) {
|
currentState++;
|
}
|
stateCount[currentState]++;
|
} else {
|
if ((currentState & 1) == 0) {
|
if (currentState == 4) {
|
if ([ZXQRCodeFinderPatternFinder foundPatternCross:stateCount] && [self handlePossibleCenter:stateCount i:i j:j pureBarcode:pureBarcode]) {
|
currentState = 0;
|
stateCount[0] = 0;
|
stateCount[1] = 0;
|
stateCount[2] = 0;
|
stateCount[3] = 0;
|
stateCount[4] = 0;
|
} else {
|
stateCount[0] = stateCount[2];
|
stateCount[1] = stateCount[3];
|
stateCount[2] = stateCount[4];
|
stateCount[3] = 1;
|
stateCount[4] = 0;
|
currentState = 3;
|
}
|
} else {
|
stateCount[++currentState]++;
|
}
|
} else {
|
stateCount[currentState]++;
|
}
|
}
|
}
|
|
if ([ZXQRCodeFinderPatternFinder foundPatternCross:stateCount]) {
|
[self handlePossibleCenter:stateCount i:i j:maxJ pureBarcode:pureBarcode];
|
}
|
}
|
NSArray *patternInfo = [self selectBestPatternsWithError:error];
|
if (!patternInfo) {
|
return nil;
|
}
|
NSMutableArray *result = [NSMutableArray array];
|
for (NSMutableArray *pattern in patternInfo) {
|
[ZXResultPoint orderBestPatterns:pattern];
|
[result addObject:[[ZXQRCodeFinderPatternInfo alloc] initWithPatternCenters:pattern]];
|
}
|
|
return result;
|
}
|
|
/**
|
* A comparator that orders FinderPatterns by their estimated module size.
|
*/
|
NSInteger moduleSizeCompare(id center1, id center2, void *context) {
|
float value = [((ZXQRCodeFinderPattern *)center2) estimatedModuleSize] - [((ZXQRCodeFinderPattern *)center1) estimatedModuleSize];
|
return value < 0.0 ? -1 : value > 0.0 ? 1 : 0;
|
}
|
|
@end
|
