core/src/com/google/zxing/multi/qrcode/detector/MultiFinderPatternFinder.java

   1 /*\r
   2  * Copyright 2009 ZXing authors\r
   3  *\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
   7  *\r
   8  *      http://www.apache.org/licenses/LICENSE-2.0\r
   9  *\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
  15  */\r
  16 \r
  17 package com.google.zxing.multi.qrcode.detector;\r
  18 \r
  19 import com.google.zxing.DecodeHintType;\r
  20 import com.google.zxing.MonochromeBitmapSource;\r
  21 import com.google.zxing.ReaderException;\r
  22 import com.google.zxing.ResultPoint;\r
  23 import com.google.zxing.common.BitArray;\r
  24 import com.google.zxing.common.Collections;\r
  25 import com.google.zxing.common.Comparator;\r
  26 import com.google.zxing.qrcode.detector.FinderPattern;\r
  27 import com.google.zxing.qrcode.detector.FinderPatternFinder;\r
  28 import com.google.zxing.qrcode.detector.FinderPatternInfo;\r
  29 \r
  30 import java.util.Hashtable;\r
  31 import java.util.Vector;\r
  32 \r
  33 /**\r
  34  * <p>This class attempts to find finder patterns in a QR Code. Finder patterns are the square\r
  35  * markers at three corners of a QR Code.</p>\r
  36  *\r
  37  * <p>This class is not thread-safe and should not be reused.</p>\r
  38  *\r
  39  * <p>In contrast to {@link FinderPatternFinder}, this class will return an array of all possible\r
  40  * QR code locations in the image.</p>\r
  41  *\r
  42  * <p>Use the TRY_HARDER hint to ask for a more thorough detection.</p>\r
  43  *\r
  44  * @author Sean Owen\r
  45  * @author Hannes Erven\r
  46  */\r
  47 final class MultiFinderPatternFinder extends FinderPatternFinder {\r
  48 \r
  49   private static final FinderPatternInfo[] EMPTY_RESULT_ARRAY = new FinderPatternInfo[0];\r
  50 \r
  51   // TODO MIN_MODULE_COUNT and MAX_MODULE_COUNT would be great\r
  52   // hints to ask the user for since it limits the number of regions to decode\r
  53   private static final float MAX_MODULE_COUNT_PER_EDGE = 180; // max. legal count of modules per QR code edge (177)\r
  54   private static final float MIN_MODULE_COUNT_PER_EDGE = 9; // min. legal count per modules per QR code edge (11)\r
  55 \r
  56   /**\r
  57    * More or less arbitrary cutoff point for determining if two finder patterns might belong\r
  58    * to the same code if they differ less than DIFF_MODSIZE_CUTOFF_PERCENT percent in their\r
  59    * estimated modules sizes.\r
  60    */\r
  61   private static final float DIFF_MODSIZE_CUTOFF_PERCENT = 0.05f;\r
  62 \r
  63   /**\r
  64    * More or less arbitrary cutoff point for determining if two finder patterns might belong\r
  65    * to the same code if they differ less than DIFF_MODSIZE_CUTOFF pixels/module in their\r
  66    * estimated modules sizes.\r
  67    */\r
  68   private static final float DIFF_MODSIZE_CUTOFF = 0.5f;\r
  69 \r
  70 \r
  71   /**\r
  72    * A comparator that orders FinderPatterns by their estimated module size.\r
  73    */\r
  74   private static class ModuleSizeComparator implements Comparator {\r
  75     public int compare(Object center1, Object center2) {\r
  76       float value = ((FinderPattern) center2).getEstimatedModuleSize() -\r
  77                     ((FinderPattern) center1).getEstimatedModuleSize();\r
  78       return value < 0.0 ? -1 : value > 0.0 ? 1 : 0;\r
  79     }\r
  80   }\r
  81 \r
  82   /**\r
  83    * <p>Creates a finder that will search the image for three finder patterns.</p>\r
  84    *\r
  85    * @param image image to search\r
  86    */\r
  87   MultiFinderPatternFinder(MonochromeBitmapSource image) {\r
  88     super(image);\r
  89   }\r
  90 \r
  91   /**\r
  92    * @return the 3 best {@link FinderPattern}s from our list of candidates. The "best" are\r
  93    *         those that have been detected at least {@link #CENTER_QUORUM} times, and whose module\r
  94    *         size differs from the average among those patterns the least\r
  95    * @throws ReaderException if 3 such finder patterns do not exist\r
  96    */\r
  97   private FinderPattern[][] selectBestPatterns() throws ReaderException {\r
  98     Vector possibleCenters = getPossibleCenters();\r
  99     int size = possibleCenters.size();\r
 100 \r
 101     if (size < 3) {\r
 102       // Couldn't find enough finder patterns\r
 103       throw ReaderException.getInstance();\r
 104     }\r
 105 \r
 106     /*\r
 107      * Begin HE modifications to safely detect multiple codes of equal size\r
 108      */\r
 109     if (size == 3) {\r
 110       return new FinderPattern[][]{\r
 111           new FinderPattern[]{\r
 112               (FinderPattern) possibleCenters.elementAt(0),\r
 113               (FinderPattern) possibleCenters.elementAt(1),\r
 114               (FinderPattern) possibleCenters.elementAt(2)\r
 115           }\r
 116       };\r
 117     }\r
 118 \r
 119     // Sort by estimated module size to speed up the upcoming checks\r
 120     Collections.insertionSort(possibleCenters, new ModuleSizeComparator());\r
 121 \r
 122     /*\r
 123      * Now lets start: build a list of tuples of three finder locations that\r
 124      *  - feature similar module sizes\r
 125      *  - are placed in a distance so the estimated module count is within the QR specification\r
 126      *  - have similar distance between upper left/right and left top/bottom finder patterns\r
 127      *  - form a triangle with 90° angle (checked by comparing top right/bottom left distance with pythagoras)\r
 128      *\r
 129      * Note: we allow each point to be used for more than one code region: this might seem counterintuitive at first,\r
 130      * but the performance penalty is not that big. At this point, we cannot make a good quality decision whether\r
 131      * the three finders actually represent a QR code, or are just by chance layouted so it looks like there might\r
 132      * be a QR code there.\r
 133      * So, if the layout seems right, lets have the decoder try to decode.     \r
 134      */\r
 135 \r
 136     Vector results = new Vector(); // holder for the results\r
 137 \r
 138     for (int i1 = 0; i1 < (size - 2); i1++) {\r
 139       FinderPattern p1 = (FinderPattern) possibleCenters.elementAt(i1);\r
 140       if (p1 == null) {\r
 141         continue;\r
 142       }\r
 143 \r
 144       for (int i2 = i1 + 1; i2 < (size - 1); i2++) {\r
 145         FinderPattern p2 = (FinderPattern) possibleCenters.elementAt(i2);\r
 146         if (p2 == null) {\r
 147           continue;\r
 148         }\r
 149 \r
 150         // Compare the expected module sizes; if they are really off, skip\r
 151         float vModSize12 = (p1.getEstimatedModuleSize() - p2.getEstimatedModuleSize()) /\r
 152             (Math.min(p1.getEstimatedModuleSize(), p2.getEstimatedModuleSize()));\r
 153         float vModSize12A = Math.abs(p1.getEstimatedModuleSize() - p2.getEstimatedModuleSize());\r
 154         if (vModSize12A > DIFF_MODSIZE_CUTOFF && vModSize12 >= DIFF_MODSIZE_CUTOFF_PERCENT) {\r
 155           // break, since elements are ordered by the module size deviation there cannot be\r
 156           // any more interesting elements for the given p1.\r
 157           break;\r
 158         }\r
 159 \r
 160         for (int i3 = i2 + 1; i3 < size; i3++) {\r
 161           FinderPattern p3 = (FinderPattern) possibleCenters.elementAt(i3);\r
 162           if (p3 == null) {\r
 163             continue;\r
 164           }\r
 165 \r
 166           // Compare the expected module sizes; if they are really off, skip\r
 167           float vModSize23 = (p2.getEstimatedModuleSize() - p3.getEstimatedModuleSize()) /\r
 168               (Math.min(p2.getEstimatedModuleSize(), p3.getEstimatedModuleSize()));\r
 169           float vModSize23A = Math.abs(p2.getEstimatedModuleSize() - p3.getEstimatedModuleSize());\r
 170           if (vModSize23A > DIFF_MODSIZE_CUTOFF && vModSize23 >= DIFF_MODSIZE_CUTOFF_PERCENT) {\r
 171             // break, since elements are ordered by the module size deviation there cannot be\r
 172             // any more interesting elements for the given p1.\r
 173             break;\r
 174           }\r
 175 \r
 176           FinderPattern[] test = {p1, p2, p3};\r
 177           ResultPoint.orderBestPatterns(test);\r
 178 \r
 179           // Calculate the distances: a = topleft-bottomleft, b=topleft-topright, c = diagonal\r
 180           FinderPatternInfo info = new FinderPatternInfo(test);\r
 181           float dA = ResultPoint.distance(info.getTopLeft(), info.getBottomLeft());\r
 182           float dC = ResultPoint.distance(info.getTopRight(), info.getBottomLeft());\r
 183           float dB = ResultPoint.distance(info.getTopLeft(), info.getTopRight());\r
 184 \r
 185           // Check the sizes\r
 186           float estimatedModuleCount = ((dA + dB) / p1.getEstimatedModuleSize()) / 2;\r
 187           if (estimatedModuleCount > MAX_MODULE_COUNT_PER_EDGE || estimatedModuleCount < MIN_MODULE_COUNT_PER_EDGE) {\r
 188             continue;\r
 189           }\r
 190 \r
 191           // Calculate the difference of the edge lengths in percent\r
 192           float vABBC = Math.abs(((dA - dB) / Math.min(dA, dB)));\r
 193           if (vABBC >= 0.1f) {\r
 194             continue;\r
 195           }\r
 196 \r
 197           // Calculate the diagonal length by assuming a 90° angle at topleft\r
 198           float dCpy = (float) Math.sqrt(dA * dA + dB * dB);\r
 199           // Compare to the real distance in %\r
 200           float vPyC = Math.abs(((dC - dCpy) / Math.min(dC, dCpy)));\r
 201 \r
 202           if (vPyC >= 0.1f) {\r
 203             continue;\r
 204           }\r
 205 \r
 206           // All tests passed!\r
 207           results.addElement(test);\r
 208         } // end iterate p3\r
 209       } // end iterate p2\r
 210     } // end iterate p1\r
 211 \r
 212     if (!results.isEmpty()) {\r
 213       FinderPattern[][] resultArray = new FinderPattern[results.size()][];\r
 214       for (int i = 0; i < results.size(); i++) {\r
 215         resultArray[i] = (FinderPattern[]) results.elementAt(i);\r
 216       }\r
 217       return resultArray;\r
 218     }\r
 219 \r
 220     // Nothing found!\r
 221     throw ReaderException.getInstance();\r
 222   }\r
 223 \r
 224   public FinderPatternInfo[] findMulti(Hashtable hints) throws ReaderException {\r
 225     boolean tryHarder = hints != null && hints.containsKey(DecodeHintType.TRY_HARDER);\r
 226     MonochromeBitmapSource image = getImage();\r
 227     int maxI = image.getHeight();\r
 228     int maxJ = image.getWidth();\r
 229     // We are looking for black/white/black/white/black modules in\r
 230     // 1:1:3:1:1 ratio; this tracks the number of such modules seen so far\r
 231 \r
 232     // Let's assume that the maximum version QR Code we support takes up 1/4 the height of the\r
 233     // image, and then account for the center being 3 modules in size. This gives the smallest\r
 234     // number of pixels the center could be, so skip this often. When trying harder, look for all\r
 235     // QR versions regardless of how dense they are.\r
 236     int iSkip = (int) (maxI / (MAX_MODULES * 4.0f) * 3);\r
 237     if (iSkip < MIN_SKIP || tryHarder) {\r
 238       iSkip = MIN_SKIP;\r
 239     }\r
 240 \r
 241     int[] stateCount = new int[5];\r
 242     for (int i = iSkip - 1; i < maxI; i += iSkip) {\r
 243       BitArray blackRow = new BitArray(maxJ);\r
 244 \r
 245       // Get a row of black/white values\r
 246       blackRow = image.getBlackRow(i, blackRow, 0, maxJ);\r
 247       stateCount[0] = 0;\r
 248       stateCount[1] = 0;\r
 249       stateCount[2] = 0;\r
 250       stateCount[3] = 0;\r
 251       stateCount[4] = 0;\r
 252       int currentState = 0;\r
 253       for (int j = 0; j < maxJ; j++) {\r
 254         if (blackRow.get(j)) {\r
 255           // Black pixel\r
 256           if ((currentState & 1) == 1) { // Counting white pixels\r
 257             currentState++;\r
 258           }\r
 259           stateCount[currentState]++;\r
 260         } else { // White pixel\r
 261           if ((currentState & 1) == 0) { // Counting black pixels\r
 262             if (currentState == 4) { // A winner?\r
 263               if (foundPatternCross(stateCount)) { // Yes\r
 264                 boolean confirmed = handlePossibleCenter(stateCount, i, j);\r
 265                 if (!confirmed) {\r
 266                   do { // Advance to next black pixel\r
 267                     j++;\r
 268                   } while (j < maxJ && !blackRow.get(j));\r
 269                   j--; // back up to that last white pixel\r
 270                 }\r
 271                 // Clear state to start looking again\r
 272                 currentState = 0;\r
 273                 stateCount[0] = 0;\r
 274                 stateCount[1] = 0;\r
 275                 stateCount[2] = 0;\r
 276                 stateCount[3] = 0;\r
 277                 stateCount[4] = 0;\r
 278               } else { // No, shift counts back by two\r
 279                 stateCount[0] = stateCount[2];\r
 280                 stateCount[1] = stateCount[3];\r
 281                 stateCount[2] = stateCount[4];\r
 282                 stateCount[3] = 1;\r
 283                 stateCount[4] = 0;\r
 284                 currentState = 3;\r
 285               }\r
 286             } else {\r
 287               stateCount[++currentState]++;\r
 288             }\r
 289           } else { // Counting white pixels\r
 290             stateCount[currentState]++;\r
 291           }\r
 292         }\r
 293       } // for j=...\r
 294 \r
 295       if (foundPatternCross(stateCount)) {\r
 296         handlePossibleCenter(stateCount, i, maxJ);\r
 297       } // end if foundPatternCross\r
 298     } // for i=iSkip-1 ...\r
 299     FinderPattern[][] patternInfo = selectBestPatterns();\r
 300     Vector result = new Vector();\r
 301     for (int i = 0; i < patternInfo.length; i++) {\r
 302       FinderPattern[] pattern = patternInfo[i];\r
 303       ResultPoint.orderBestPatterns(pattern);\r
 304       result.addElement(new FinderPatternInfo(pattern));\r
 305     }\r
 306 \r
 307     if (result.isEmpty()) {\r
 308       return EMPTY_RESULT_ARRAY;\r
 309     } else {\r
 310       FinderPatternInfo[] resultArray = new FinderPatternInfo[result.size()];\r
 311       for (int i = 0; i < result.size(); i++) {\r
 312         resultArray[i] = (FinderPatternInfo) result.elementAt(i);\r
 313       }\r
 314       return resultArray;\r
 315     }\r
 316   }\r
 317 \r
 318 }\r