--- /dev/null
+/*\r
+ * Copyright 2009 ZXing authors\r
+ *\r
+ * Licensed under the Apache License, Version 2.0 (the "License");\r
+ * you may not use this file except in compliance with the License.\r
+ * You may obtain a copy of the License at\r
+ *\r
+ * http://www.apache.org/licenses/LICENSE-2.0\r
+ *\r
+ * Unless required by applicable law or agreed to in writing, software\r
+ * distributed under the License is distributed on an "AS IS" BASIS,\r
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.\r
+ * See the License for the specific language governing permissions and\r
+ * limitations under the License.\r
+ */\r
+\r
+package com.google.zxing.multi.qrcode.detector;\r
+\r
+import com.google.zxing.DecodeHintType;\r
+import com.google.zxing.MonochromeBitmapSource;\r
+import com.google.zxing.ReaderException;\r
+import com.google.zxing.ResultPoint;\r
+import com.google.zxing.common.BitArray;\r
+import com.google.zxing.common.Collections;\r
+import com.google.zxing.common.Comparator;\r
+import com.google.zxing.qrcode.detector.FinderPattern;\r
+import com.google.zxing.qrcode.detector.FinderPatternFinder;\r
+import com.google.zxing.qrcode.detector.FinderPatternInfo;\r
+\r
+import java.util.Hashtable;\r
+import java.util.Vector;\r
+\r
+/**\r
+ * <p>This class attempts to find finder patterns in a QR Code. Finder patterns are the square\r
+ * markers at three corners of a QR Code.</p>\r
+ *\r
+ * <p>This class is not thread-safe and should not be reused.</p>\r
+ *\r
+ * <p>In contrast to {@link FinderPatternFinder}, this class will return an array of all possible\r
+ * QR code locations in the image.</p>\r
+ *\r
+ * <p>Use the TRY_HARDER hint to ask for a more thorough detection.</p>\r
+ *\r
+ * @author Sean Owen\r
+ * @author Hannes Erven\r
+ */\r
+final class MultiFinderPatternFinder extends FinderPatternFinder {\r
+\r
+ private static final FinderPatternInfo[] EMPTY_RESULT_ARRAY = new FinderPatternInfo[0];\r
+\r
+ // TODO MIN_MODULE_COUNT and MAX_MODULE_COUNT would be great\r
+ // hints to ask the user for since it limits the number of regions to decode\r
+ private static final float MAX_MODULE_COUNT_PER_EDGE = 180; // max. legal count of modules per QR code edge (177)\r
+ private static final float MIN_MODULE_COUNT_PER_EDGE = 9; // min. legal count per modules per QR code edge (11)\r
+\r
+ /**\r
+ * More or less arbitrary cutoff point for determining if two finder patterns might belong\r
+ * to the same code if they differ less than DIFF_MODSIZE_CUTOFF_PERCENT percent in their\r
+ * estimated modules sizes.\r
+ */\r
+ private static final float DIFF_MODSIZE_CUTOFF_PERCENT = 0.05f;\r
+\r
+ /**\r
+ * More or less arbitrary cutoff point for determining if two finder patterns might belong\r
+ * to the same code if they differ less than DIFF_MODSIZE_CUTOFF pixels/module in their\r
+ * estimated modules sizes.\r
+ */\r
+ private static final float DIFF_MODSIZE_CUTOFF = 0.5f;\r
+\r
+\r
+ /**\r
+ * A comparator that orders FinderPatterns by their estimated module size.\r
+ */\r
+ private static class ModuleSizeComparator implements Comparator {\r
+ public int compare(Object center1, Object center2) {\r
+ float value = ((FinderPattern) center2).getEstimatedModuleSize() -\r
+ ((FinderPattern) center1).getEstimatedModuleSize();\r
+ return value < 0.0 ? -1 : value > 0.0 ? 1 : 0;\r
+ }\r
+ }\r
+\r
+ /**\r
+ * <p>Creates a finder that will search the image for three finder patterns.</p>\r
+ *\r
+ * @param image image to search\r
+ */\r
+ MultiFinderPatternFinder(MonochromeBitmapSource image) {\r
+ super(image);\r
+ }\r
+\r
+ /**\r
+ * @return the 3 best {@link FinderPattern}s from our list of candidates. The "best" are\r
+ * those that have been detected at least {@link #CENTER_QUORUM} times, and whose module\r
+ * size differs from the average among those patterns the least\r
+ * @throws ReaderException if 3 such finder patterns do not exist\r
+ */\r
+ private FinderPattern[][] selectBestPatterns() throws ReaderException {\r
+ Vector possibleCenters = getPossibleCenters();\r
+ int size = possibleCenters.size();\r
+\r
+ if (size < 3) {\r
+ // Couldn't find enough finder patterns\r
+ throw ReaderException.getInstance();\r
+ }\r
+\r
+ /*\r
+ * Begin HE modifications to safely detect multiple codes of equal size\r
+ */\r
+ if (size == 3) {\r
+ return new FinderPattern[][]{\r
+ new FinderPattern[]{\r
+ (FinderPattern) possibleCenters.elementAt(0),\r
+ (FinderPattern) possibleCenters.elementAt(1),\r
+ (FinderPattern) possibleCenters.elementAt(2)\r
+ }\r
+ };\r
+ }\r
+\r
+ // Sort by estimated module size to speed up the upcoming checks\r
+ Collections.insertionSort(possibleCenters, new ModuleSizeComparator());\r
+\r
+ /*\r
+ * Now lets start: build a list of tuples of three finder locations that\r
+ * - feature similar module sizes\r
+ * - are placed in a distance so the estimated module count is within the QR specification\r
+ * - have similar distance between upper left/right and left top/bottom finder patterns\r
+ * - form a triangle with 90° angle (checked by comparing top right/bottom left distance with pythagoras)\r
+ *\r
+ * Note: we allow each point to be used for more than one code region: this might seem counterintuitive at first,\r
+ * but the performance penalty is not that big. At this point, we cannot make a good quality decision whether\r
+ * the three finders actually represent a QR code, or are just by chance layouted so it looks like there might\r
+ * be a QR code there.\r
+ * So, if the layout seems right, lets have the decoder try to decode. \r
+ */\r
+\r
+ Vector results = new Vector(); // holder for the results\r
+\r
+ for (int i1 = 0; i1 < (size - 2); i1++) {\r
+ FinderPattern p1 = (FinderPattern) possibleCenters.elementAt(i1);\r
+ if (p1 == null) {\r
+ continue;\r
+ }\r
+\r
+ for (int i2 = i1 + 1; i2 < (size - 1); i2++) {\r
+ FinderPattern p2 = (FinderPattern) possibleCenters.elementAt(i2);\r
+ if (p2 == null) {\r
+ continue;\r
+ }\r
+\r
+ // Compare the expected module sizes; if they are really off, skip\r
+ float vModSize12 = (p1.getEstimatedModuleSize() - p2.getEstimatedModuleSize()) /\r
+ (Math.min(p1.getEstimatedModuleSize(), p2.getEstimatedModuleSize()));\r
+ float vModSize12A = Math.abs(p1.getEstimatedModuleSize() - p2.getEstimatedModuleSize());\r
+ if (vModSize12A > DIFF_MODSIZE_CUTOFF && vModSize12 >= DIFF_MODSIZE_CUTOFF_PERCENT) {\r
+ // break, since elements are ordered by the module size deviation there cannot be\r
+ // any more interesting elements for the given p1.\r
+ break;\r
+ }\r
+\r
+ for (int i3 = i2 + 1; i3 < size; i3++) {\r
+ FinderPattern p3 = (FinderPattern) possibleCenters.elementAt(i3);\r
+ if (p3 == null) {\r
+ continue;\r
+ }\r
+\r
+ // Compare the expected module sizes; if they are really off, skip\r
+ float vModSize23 = (p2.getEstimatedModuleSize() - p3.getEstimatedModuleSize()) /\r
+ (Math.min(p2.getEstimatedModuleSize(), p3.getEstimatedModuleSize()));\r
+ float vModSize23A = Math.abs(p2.getEstimatedModuleSize() - p3.getEstimatedModuleSize());\r
+ if (vModSize23A > DIFF_MODSIZE_CUTOFF && vModSize23 >= DIFF_MODSIZE_CUTOFF_PERCENT) {\r
+ // break, since elements are ordered by the module size deviation there cannot be\r
+ // any more interesting elements for the given p1.\r
+ break;\r
+ }\r
+\r
+ FinderPattern[] test = {p1, p2, p3};\r
+ ResultPoint.orderBestPatterns(test);\r
+\r
+ // Calculate the distances: a = topleft-bottomleft, b=topleft-topright, c = diagonal\r
+ FinderPatternInfo info = new FinderPatternInfo(test);\r
+ float dA = ResultPoint.distance(info.getTopLeft(), info.getBottomLeft());\r
+ float dC = ResultPoint.distance(info.getTopRight(), info.getBottomLeft());\r
+ float dB = ResultPoint.distance(info.getTopLeft(), info.getTopRight());\r
+\r
+ // Check the sizes\r
+ float estimatedModuleCount = ((dA + dB) / p1.getEstimatedModuleSize()) / 2;\r
+ if (estimatedModuleCount > MAX_MODULE_COUNT_PER_EDGE || estimatedModuleCount < MIN_MODULE_COUNT_PER_EDGE) {\r
+ continue;\r
+ }\r
+\r
+ // Calculate the difference of the edge lengths in percent\r
+ float vABBC = Math.abs(((dA - dB) / Math.min(dA, dB)));\r
+ if (vABBC >= 0.1f) {\r
+ continue;\r
+ }\r
+\r
+ // Calculate the diagonal length by assuming a 90° angle at topleft\r
+ float dCpy = (float) Math.sqrt(dA * dA + dB * dB);\r
+ // Compare to the real distance in %\r
+ float vPyC = Math.abs(((dC - dCpy) / Math.min(dC, dCpy)));\r
+\r
+ if (vPyC >= 0.1f) {\r
+ continue;\r
+ }\r
+\r
+ // All tests passed!\r
+ results.addElement(test);\r
+ } // end iterate p3\r
+ } // end iterate p2\r
+ } // end iterate p1\r
+\r
+ if (!results.isEmpty()) {\r
+ FinderPattern[][] resultArray = new FinderPattern[results.size()][];\r
+ for (int i = 0; i < results.size(); i++) {\r
+ resultArray[i] = (FinderPattern[]) results.elementAt(i);\r
+ }\r
+ return resultArray;\r
+ }\r
+\r
+ // Nothing found!\r
+ throw ReaderException.getInstance();\r
+ }\r
+\r
+ public FinderPatternInfo[] findMulti(Hashtable hints) throws ReaderException {\r
+ boolean tryHarder = hints != null && hints.containsKey(DecodeHintType.TRY_HARDER);\r
+ MonochromeBitmapSource image = getImage();\r
+ int maxI = image.getHeight();\r
+ int maxJ = image.getWidth();\r
+ // We are looking for black/white/black/white/black modules in\r
+ // 1:1:3:1:1 ratio; this tracks the number of such modules seen so far\r
+\r
+ // Let's assume that the maximum version QR Code we support takes up 1/4 the height of the\r
+ // image, and then account for the center being 3 modules in size. This gives the smallest\r
+ // number of pixels the center could be, so skip this often. When trying harder, look for all\r
+ // QR versions regardless of how dense they are.\r
+ int iSkip = (int) (maxI / (MAX_MODULES * 4.0f) * 3);\r
+ if (iSkip < MIN_SKIP || tryHarder) {\r
+ iSkip = MIN_SKIP;\r
+ }\r
+\r
+ int[] stateCount = new int[5];\r
+ for (int i = iSkip - 1; i < maxI; i += iSkip) {\r
+ BitArray blackRow = new BitArray(maxJ);\r
+\r
+ // Get a row of black/white values\r
+ blackRow = image.getBlackRow(i, blackRow, 0, maxJ);\r
+ stateCount[0] = 0;\r
+ stateCount[1] = 0;\r
+ stateCount[2] = 0;\r
+ stateCount[3] = 0;\r
+ stateCount[4] = 0;\r
+ int currentState = 0;\r
+ for (int j = 0; j < maxJ; j++) {\r
+ if (blackRow.get(j)) {\r
+ // Black pixel\r
+ if ((currentState & 1) == 1) { // Counting white pixels\r
+ currentState++;\r
+ }\r
+ stateCount[currentState]++;\r
+ } else { // White pixel\r
+ if ((currentState & 1) == 0) { // Counting black pixels\r
+ if (currentState == 4) { // A winner?\r
+ if (foundPatternCross(stateCount)) { // Yes\r
+ boolean confirmed = handlePossibleCenter(stateCount, i, j);\r
+ if (!confirmed) {\r
+ do { // Advance to next black pixel\r
+ j++;\r
+ } while (j < maxJ && !blackRow.get(j));\r
+ j--; // back up to that last white pixel\r
+ }\r
+ // Clear state to start looking again\r
+ currentState = 0;\r
+ stateCount[0] = 0;\r
+ stateCount[1] = 0;\r
+ stateCount[2] = 0;\r
+ stateCount[3] = 0;\r
+ stateCount[4] = 0;\r
+ } else { // No, shift counts back by two\r
+ stateCount[0] = stateCount[2];\r
+ stateCount[1] = stateCount[3];\r
+ stateCount[2] = stateCount[4];\r
+ stateCount[3] = 1;\r
+ stateCount[4] = 0;\r
+ currentState = 3;\r
+ }\r
+ } else {\r
+ stateCount[++currentState]++;\r
+ }\r
+ } else { // Counting white pixels\r
+ stateCount[currentState]++;\r
+ }\r
+ }\r
+ } // for j=...\r
+\r
+ if (foundPatternCross(stateCount)) {\r
+ handlePossibleCenter(stateCount, i, maxJ);\r
+ } // end if foundPatternCross\r
+ } // for i=iSkip-1 ...\r
+ FinderPattern[][] patternInfo = selectBestPatterns();\r
+ Vector result = new Vector();\r
+ for (int i = 0; i < patternInfo.length; i++) {\r
+ FinderPattern[] pattern = patternInfo[i];\r
+ ResultPoint.orderBestPatterns(pattern);\r
+ result.addElement(new FinderPatternInfo(pattern));\r
+ }\r
+\r
+ if (result.isEmpty()) {\r
+ return EMPTY_RESULT_ARRAY;\r
+ } else {\r
+ FinderPatternInfo[] resultArray = new FinderPatternInfo[result.size()];\r
+ for (int i = 0; i < result.size(); i++) {\r
+ resultArray[i] = (FinderPatternInfo) result.elementAt(i);\r
+ }\r
+ return resultArray;\r
+ }\r
+ }\r
+\r
+}\r
projects / zxing.git / blobdiff