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