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