Creates a finder that will search the image for three finder patterns.
@@ -52,9 +54,14 @@ public class FinderPatternFinder { * @param image image to search */ public FinderPatternFinder(BitMatrix image) { + this(image, null); + } + + public FinderPatternFinder(BitMatrix image, ResultPointCallback resultPointCallback) { this.image = image; this.possibleCenters = new Vector(); this.crossCheckStateCount = new int[5]; + this.resultPointCallback = resultPointCallback; } protected BitMatrix getImage() { @@ -65,7 +72,7 @@ public class FinderPatternFinder { return possibleCenters; } - FinderPatternInfo find(Hashtable hints) throws ReaderException { + FinderPatternInfo find(Hashtable hints) throws NotFoundException { boolean tryHarder = hints != null && hints.containsKey(DecodeHintType.TRY_HARDER); int maxI = image.getHeight(); int maxJ = image.getWidth(); @@ -125,11 +132,13 @@ public class FinderPatternFinder { } } } else { - // Advance to next black pixel - do { - j++; - } while (j < maxJ && !image.get(j, i)); - j--; // back up to that last white pixel + stateCount[0] = stateCount[2]; + stateCount[1] = stateCount[3]; + stateCount[2] = stateCount[4]; + stateCount[3] = 1; + stateCount[4] = 0; + currentState = 3; + continue; } // Clear state to start looking again currentState = 0; @@ -283,11 +292,11 @@ public class FinderPatternFinder { return Float.NaN; } - // If we found a finder-pattern-like section, but its size is more than 20% different than + // If we found a finder-pattern-like section, but its size is more than 40% different than // the original, assume it's a false positive int stateCountTotal = stateCount[0] + stateCount[1] + stateCount[2] + stateCount[3] + stateCount[4]; - if (5 * Math.abs(stateCountTotal - originalStateCountTotal) >= originalStateCountTotal) { + if (5 * Math.abs(stateCountTotal - originalStateCountTotal) >= 2 * originalStateCountTotal) { return Float.NaN; } @@ -379,7 +388,7 @@ public class FinderPatternFinder { * @param j end of possible finder pattern in row * @return true if a finder pattern candidate was found this time */ - protected boolean handlePossibleCenter(int[] stateCount, int i, int j) throws ReaderException { + protected boolean handlePossibleCenter(int[] stateCount, int i, int j) { int stateCountTotal = stateCount[0] + stateCount[1] + stateCount[2] + stateCount[3] + stateCount[4]; float centerJ = centerFromEnd(stateCount, j); @@ -401,7 +410,11 @@ public class FinderPatternFinder { } } if (!found) { - possibleCenters.addElement(new FinderPattern(centerJ, centerI, estimatedModuleSize)); + ResultPoint point = new FinderPattern(centerJ, centerI, estimatedModuleSize); + possibleCenters.addElement(point); + if (resultPointCallback != null) { + resultPointCallback.foundPossibleResultPoint(point); + } } return true; } @@ -463,7 +476,7 @@ public class FinderPatternFinder { // OK, we have at least 3 confirmed centers, but, it's possible that one is a "false positive" // and that we need to keep looking. We detect this by asking if the estimated module sizes // vary too much. We arbitrarily say that when the total deviation from average exceeds - // 15% of the total module size estimates, it's too much. + // 5% of the total module size estimates, it's too much. float average = totalModuleSize / (float) max; float totalDeviation = 0.0f; for (int i = 0; i < max; i++) { @@ -477,36 +490,55 @@ public class FinderPatternFinder { * @return 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 - * @throws ReaderException if 3 such finder patterns do not exist + * @throws NotFoundException if 3 such finder patterns do not exist */ - private FinderPattern[] selectBestPatterns() throws ReaderException { - Collections.insertionSort(possibleCenters, new CenterComparator()); - int size = 0; - int max = possibleCenters.size(); - while (size < max) { - if (((FinderPattern) possibleCenters.elementAt(size)).getCount() < CENTER_QUORUM) { - break; - } - size++; - } + private FinderPattern[] selectBestPatterns() throws NotFoundException { - if (size < 3) { + int startSize = possibleCenters.size(); + if (startSize < 3) { // Couldn't find enough finder patterns - throw ReaderException.getInstance(); + throw NotFoundException.getNotFoundInstance(); + } + + // Filter outlier possibilities whose module size is too different + if (startSize > 3) { + // But we can only afford to do so if we have at least 4 possibilities to choose from + float totalModuleSize = 0.0f; + float square = 0.0f; + for (int i = 0; i < startSize; i++) { + float size = ((FinderPattern) possibleCenters.elementAt(i)).getEstimatedModuleSize(); + totalModuleSize += size; + square += size * size; + } + float average = totalModuleSize / (float) startSize; + float stdDev = (float) Math.sqrt(square / startSize - average * average); + + Collections.insertionSort(possibleCenters, new FurthestFromAverageComparator(average)); + + float limit = Math.max(0.2f * average, stdDev); + + for (int i = 0; i < possibleCenters.size() && possibleCenters.size() > 3; i++) { + FinderPattern pattern = (FinderPattern) possibleCenters.elementAt(i); + if (Math.abs(pattern.getEstimatedModuleSize() - average) > limit) { + possibleCenters.removeElementAt(i); + i--; + } + } } - if (size > 3) { + if (possibleCenters.size() > 3) { // Throw away all but those first size candidate points we found. - possibleCenters.setSize(size); - // We need to pick the best three. Find the most - // popular ones whose module size is nearest the average - float averageModuleSize = 0.0f; - for (int i = 0; i < size; i++) { - averageModuleSize += ((FinderPattern) possibleCenters.elementAt(i)).getEstimatedModuleSize(); + + float totalModuleSize = 0.0f; + for (int i = 0; i < possibleCenters.size(); i++) { + totalModuleSize += ((FinderPattern) possibleCenters.elementAt(i)).getEstimatedModuleSize(); } - averageModuleSize /= (float) size; - // We don't have java.util.Collections in J2ME - Collections.insertionSort(possibleCenters, new ClosestToAverageComparator(averageModuleSize)); + + float average = totalModuleSize / (float) possibleCenters.size(); + + Collections.insertionSort(possibleCenters, new CenterComparator(average)); + + possibleCenters.setSize(3); } return new FinderPattern[]{ @@ -517,29 +549,36 @@ public class FinderPatternFinder { } /** - *Orders by {@link FinderPattern#getCount()}, descending.
+ *Orders by furthest from average
*/ - private static class CenterComparator implements Comparator { + private static class FurthestFromAverageComparator implements Comparator { + private final float average; + private FurthestFromAverageComparator(float f) { + average = f; + } public int compare(Object center1, Object center2) { - return ((FinderPattern) center2).getCount() - ((FinderPattern) center1).getCount(); + float dA = Math.abs(((FinderPattern) center2).getEstimatedModuleSize() - average); + float dB = Math.abs(((FinderPattern) center1).getEstimatedModuleSize() - average); + return dA < dB ? -1 : (dA == dB ? 0 : 1); } } /** - *Orders by variance from average module size, ascending.
+ *Orders by {@link FinderPattern#getCount()}, descending.
*/ - private static class ClosestToAverageComparator implements Comparator { - private final float averageModuleSize; - - private ClosestToAverageComparator(float averageModuleSize) { - this.averageModuleSize = averageModuleSize; + private static class CenterComparator implements Comparator { + private final float average; + private CenterComparator(float f) { + average = f; } - public int compare(Object center1, Object center2) { - return Math.abs(((FinderPattern) center1).getEstimatedModuleSize() - averageModuleSize) < - Math.abs(((FinderPattern) center2).getEstimatedModuleSize() - averageModuleSize) ? - -1 : - 1; + if (((FinderPattern) center2).getCount() == ((FinderPattern) center1).getCount()) { + float dA = Math.abs(((FinderPattern) center2).getEstimatedModuleSize() - average); + float dB = Math.abs(((FinderPattern) center1).getEstimatedModuleSize() - average); + return dA < dB ? 1 : (dA == dB ? 0 : -1); + } else { + return ((FinderPattern) center2).getCount() - ((FinderPattern) center1).getCount(); + } } }