core/src/com/google/zxing/qrcode/detector/FinderPatternFinder.java

   1 /*\r
   2  * Copyright 2007 Google Inc.\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.qrcode.detector;\r
  18 \r
  19 import com.google.zxing.MonochromeBitmapSource;\r
  20 import com.google.zxing.ReaderException;\r
  21 import com.google.zxing.ResultPoint;\r
  22 import com.google.zxing.common.BitArray;\r
  23 import com.google.zxing.common.Collections;\r
  24 import com.google.zxing.common.Comparator;\r
  25 \r
  26 import java.util.Vector;\r
  27 \r
  28 /**\r
  29  * <p>This class is not thread-safe and should not be reused.</p>\r
  30  *\r
  31  * @author srowen@google.com (Sean Owen)\r
  32  */\r
  33 final class FinderPatternFinder {\r
  34 \r
  35   private static final int CENTER_QUORUM = 2;\r
  36   private static final int BIG_SKIP = 3;\r
  37 \r
  38   private final MonochromeBitmapSource image;\r
  39   private final Vector possibleCenters;\r
  40   private boolean hasSkipped;\r
  41 \r
  42   FinderPatternFinder(MonochromeBitmapSource image) {\r
  43     this.image = image;\r
  44     this.possibleCenters = new Vector(5);\r
  45   }\r
  46 \r
  47   FinderPatternInfo find() throws ReaderException {\r
  48     int maxI = image.getHeight();\r
  49     int maxJ = image.getWidth();\r
  50     int[] stateCount = new int[5]; // looking for 1 1 3 1 1\r
  51     boolean done = false;\r
  52     // We can afford to examine every few lines until we've started finding\r
  53     // the patterns\r
  54     int iSkip = BIG_SKIP;\r
  55     for (int i = iSkip - 1; i < maxI && !done; i += iSkip) {\r
  56       BitArray luminanceRow = image.getBlackRow(i, null, 0, maxJ);\r
  57       stateCount[0] = 0;\r
  58       stateCount[1] = 0;\r
  59       stateCount[2] = 0;\r
  60       stateCount[3] = 0;\r
  61       stateCount[4] = 0;\r
  62       int currentState = 0;\r
  63       for (int j = 0; j < maxJ; j++) {\r
  64         if (luminanceRow.get(j)) {\r
  65           // Black pixel\r
  66           if ((currentState & 1) == 1) { // Counting white pixels\r
  67             currentState++;\r
  68           }\r
  69           stateCount[currentState]++;\r
  70         } else { // White pixel\r
  71           if ((currentState & 1) == 0) { // Counting black pixels\r
  72             if (currentState == 4) { // A winner?\r
  73               if (foundPatternCross(stateCount)) { // Yes\r
  74                 boolean confirmed =\r
  75                     handlePossibleCenter(stateCount, i, j);\r
  76                 if (confirmed) {\r
  77                   iSkip = 1; // Go back to examining each line\r
  78                   if (hasSkipped) {\r
  79                     done = haveMulitplyConfirmedCenters();\r
  80                   } else {\r
  81                     int rowSkip = findRowSkip();\r
  82                     if (rowSkip > stateCount[2]) {\r
  83                       // Skip rows between row of lower confirmed center\r
  84                       // and top of presumed third confirmed center\r
  85                       // but back up a bit to get a full chance of detecting\r
  86                       // it, entire width of center of finder pattern\r
  87 \r
  88                       // Skip by rowSkip, but back off by stateCount[2] (size of last center\r
  89                       // of pattern we saw) to be conservative, and also back off by iSkip which\r
  90                       // is about to be re-added\r
  91                       i += rowSkip - stateCount[2] - iSkip;\r
  92                       j = maxJ - 1;\r
  93                     }\r
  94                   }\r
  95                 } else {\r
  96                   // Advance to next black pixel\r
  97                   do {\r
  98                     j++;\r
  99                   } while (j < maxJ && !luminanceRow.get(j));\r
 100                   j--; // back up to that last white pixel\r
 101                 }\r
 102                 // Clear state to start looking again\r
 103                 currentState = 0;\r
 104                 stateCount[0] = 0;\r
 105                 stateCount[1] = 0;\r
 106                 stateCount[2] = 0;\r
 107                 stateCount[3] = 0;\r
 108                 stateCount[4] = 0;\r
 109               } else { // No, shift counts back by two\r
 110                 stateCount[0] = stateCount[2];\r
 111                 stateCount[1] = stateCount[3];\r
 112                 stateCount[2] = stateCount[4];\r
 113                 stateCount[3] = 1;\r
 114                 stateCount[4] = 0;\r
 115                 currentState = 3;\r
 116               }\r
 117             } else {\r
 118               stateCount[++currentState]++;\r
 119             }\r
 120           } else { // Counting white pixels\r
 121             stateCount[currentState]++;\r
 122           }\r
 123         }\r
 124       }\r
 125       if (foundPatternCross(stateCount)) {\r
 126         boolean confirmed = handlePossibleCenter(stateCount, i, maxJ);\r
 127         if (confirmed) {\r
 128           iSkip = stateCount[0];\r
 129           if (hasSkipped) {\r
 130             // Found a third one\r
 131             done = haveMulitplyConfirmedCenters();\r
 132           }\r
 133         }\r
 134       }\r
 135     }\r
 136 \r
 137     FinderPattern[] patternInfo = selectBestPatterns();\r
 138     patternInfo = orderBestPatterns(patternInfo);\r
 139     float totalModuleSize = 0.0f;\r
 140     for (int i = 0; i < patternInfo.length; i++) {\r
 141       totalModuleSize += patternInfo[i].getEstimatedModuleSize();\r
 142     }\r
 143 \r
 144     return new FinderPatternInfo(totalModuleSize / (float) patternInfo.length,\r
 145         patternInfo);\r
 146   }\r
 147 \r
 148   private static float centerFromEnd(int[] stateCount, int end) {\r
 149     return (float) (end - stateCount[4] - stateCount[3]) - stateCount[2] / 2.0f;\r
 150   }\r
 151 \r
 152   private static boolean foundPatternCross(int[] stateCount) {\r
 153     int totalModuleSize = 0;\r
 154     for (int i = 0; i < 5; i++) {\r
 155       if (stateCount[i] == 0) {\r
 156         return false;\r
 157       }\r
 158       totalModuleSize += stateCount[i];\r
 159     }\r
 160     if (totalModuleSize < 7) {\r
 161       return false;\r
 162     }\r
 163     int moduleSize = totalModuleSize / 7;\r
 164     // Allow less than 50% deviance from 1-1-3-1-1 pattern\r
 165     return\r
 166         Math.abs(moduleSize - stateCount[0]) << 1 <= moduleSize &&\r
 167             Math.abs(moduleSize - stateCount[1]) << 1 <= moduleSize &&\r
 168             Math.abs(3 * moduleSize - stateCount[2]) << 1 <= 3 * moduleSize &&\r
 169             Math.abs(moduleSize - stateCount[3]) << 1 <= moduleSize &&\r
 170             Math.abs(moduleSize - stateCount[4]) << 1 <= moduleSize;\r
 171   }\r
 172 \r
 173   private float crossCheckVertical(int startI, int centerJ, int maxCount) {\r
 174     MonochromeBitmapSource image = this.image;\r
 175 \r
 176     int maxI = image.getHeight();\r
 177     int[] stateCount = new int[5];\r
 178 \r
 179     int i = startI;\r
 180     while (i >= 0 && image.isBlack(centerJ, i)) {\r
 181       stateCount[2]++;\r
 182       i--;\r
 183     }\r
 184     if (i < 0) {\r
 185       return Float.NaN;\r
 186     }\r
 187     while (i >= 0 && !image.isBlack(centerJ, i) && stateCount[1] <= maxCount) {\r
 188       stateCount[1]++;\r
 189       i--;\r
 190     }\r
 191     // If already too many modules in this state or ran off the edge:\r
 192     if (i < 0 || stateCount[1] > maxCount) {\r
 193       return Float.NaN;\r
 194     }\r
 195     while (i >= 0 && image.isBlack(centerJ, i) && stateCount[0] <= maxCount) {\r
 196       stateCount[0]++;\r
 197       i--;\r
 198     }\r
 199     if (i < 0 || stateCount[0] > maxCount) {\r
 200       return Float.NaN;\r
 201     }\r
 202 \r
 203     i = startI + 1;\r
 204     while (i < maxI && image.isBlack(centerJ, i)) {\r
 205       stateCount[2]++;\r
 206       i++;\r
 207     }\r
 208     if (i == maxI) {\r
 209       return Float.NaN;\r
 210     }\r
 211     while (i < maxI && !image.isBlack(centerJ, i) && stateCount[3] < maxCount) {\r
 212       stateCount[3]++;\r
 213       i++;\r
 214     }\r
 215     if (i == maxI || stateCount[3] >= maxCount) {\r
 216       return Float.NaN;\r
 217     }\r
 218     while (i < maxI && image.isBlack(centerJ, i) && stateCount[4] < maxCount) {\r
 219       stateCount[4]++;\r
 220       i++;\r
 221     }\r
 222     if (stateCount[4] >= maxCount) {\r
 223       return Float.NaN;\r
 224     }\r
 225 \r
 226     return foundPatternCross(stateCount) ? centerFromEnd(stateCount, i) : Float.NaN;\r
 227   }\r
 228 \r
 229   private float crossCheckHorizontal(int startJ, int centerI, int maxCount) {\r
 230     MonochromeBitmapSource image = this.image;\r
 231 \r
 232     int maxJ = image.getWidth();\r
 233     int[] stateCount = new int[5];\r
 234 \r
 235     int j = startJ;\r
 236     while (j >= 0 && image.isBlack(j, centerI)) {\r
 237       stateCount[2]++;\r
 238       j--;\r
 239     }\r
 240     if (j < 0) {\r
 241       return Float.NaN;\r
 242     }\r
 243     while (j >= 0 && !image.isBlack(j, centerI) && stateCount[1] <= maxCount) {\r
 244       stateCount[1]++;\r
 245       j--;\r
 246     }\r
 247     // If already too many modules in this state or ran off the edge:\r
 248     if (j < 0 || stateCount[1] > maxCount) {\r
 249       return Float.NaN;\r
 250     }\r
 251     while (j >= 0 && image.isBlack(j, centerI) && stateCount[0] <= maxCount) {\r
 252       stateCount[0]++;\r
 253       j--;\r
 254     }\r
 255     if (j < 0 || stateCount[0] > maxCount) {\r
 256       return Float.NaN;\r
 257     }\r
 258 \r
 259     j = startJ + 1;\r
 260     while (j < maxJ && image.isBlack(j, centerI)) {\r
 261       stateCount[2]++;\r
 262       j++;\r
 263     }\r
 264     if (j == maxJ) {\r
 265       return Float.NaN;\r
 266     }\r
 267     while (j < maxJ && !image.isBlack(j, centerI) && stateCount[3] < maxCount) {\r
 268       stateCount[3]++;\r
 269       j++;\r
 270     }\r
 271     if (j == maxJ || stateCount[3] >= maxCount) {\r
 272       return Float.NaN;\r
 273     }\r
 274     while (j < maxJ && image.isBlack(j, centerI) && stateCount[4] < maxCount) {\r
 275       stateCount[4]++;\r
 276       j++;\r
 277     }\r
 278     if (stateCount[4] >= maxCount) {\r
 279       return Float.NaN;\r
 280     }\r
 281 \r
 282     return foundPatternCross(stateCount) ? centerFromEnd(stateCount, j) : Float.NaN;\r
 283   }\r
 284 \r
 285   private boolean handlePossibleCenter(int[] stateCount,\r
 286                                        int i,\r
 287                                        int j) {\r
 288     float centerJ = centerFromEnd(stateCount, j);\r
 289     float centerI = crossCheckVertical(i, (int) centerJ, stateCount[2]);\r
 290     if (!Float.isNaN(centerI)) {\r
 291       // Re-cross check\r
 292       centerJ = crossCheckHorizontal((int) centerJ, (int) centerI, stateCount[2]);\r
 293       if (!Float.isNaN(centerJ)) {\r
 294         float estimatedModuleSize = (float) (stateCount[0] +\r
 295             stateCount[1] +\r
 296             stateCount[2] +\r
 297             stateCount[3] +\r
 298             stateCount[4]) / 7.0f;\r
 299         boolean found = false;\r
 300         int max = possibleCenters.size();\r
 301         for (int index = 0; index < max; index++) {\r
 302           FinderPattern center = (FinderPattern) possibleCenters.elementAt(index);\r
 303           // Look for about the same center and module size:\r
 304           if (center.aboutEquals(estimatedModuleSize, centerI, centerJ)) {\r
 305             center.incrementCount();\r
 306             found = true;\r
 307             break;\r
 308           }\r
 309         }\r
 310         if (!found) {\r
 311           possibleCenters.addElement(\r
 312               new FinderPattern(centerJ, centerI, estimatedModuleSize));\r
 313         }\r
 314         return true;\r
 315       }\r
 316     }\r
 317     return false;\r
 318   }\r
 319 \r
 320   private int findRowSkip() {\r
 321     int max = possibleCenters.size();\r
 322     if (max <= 1) {\r
 323       return 0;\r
 324     }\r
 325     FinderPattern firstConfirmedCenter = null;\r
 326     for (int i = 0; i < max; i++) {\r
 327       FinderPattern center = (FinderPattern) possibleCenters.elementAt(i);\r
 328       if (center.getCount() >= CENTER_QUORUM) {\r
 329         if (firstConfirmedCenter == null) {\r
 330           firstConfirmedCenter = center;\r
 331         } else {\r
 332           // We have two confirmed centers\r
 333           // How far down can we skip before resuming looking for the next\r
 334           // pattern? In the worst case, only the difference between the\r
 335           // difference in the x / y coordinates of the two centers.\r
 336           // This is the case where you find top left first. Draw it out.\r
 337           hasSkipped = true;\r
 338           return (int) Math.abs(Math.abs(firstConfirmedCenter.getX() - center.getX()) -\r
 339                                 Math.abs(firstConfirmedCenter.getY() - center.getY()));\r
 340         }\r
 341       }\r
 342     }\r
 343     return 0;\r
 344   }\r
 345 \r
 346   private boolean haveMulitplyConfirmedCenters() {\r
 347     int count = 0;\r
 348     int max = possibleCenters.size();\r
 349     for (int i = 0; i < max; i++) {\r
 350       if (((FinderPattern) possibleCenters.elementAt(i)).getCount() >= CENTER_QUORUM) {\r
 351         if (++count == 3) {\r
 352           return true;\r
 353         }\r
 354       }\r
 355     }\r
 356     return false;\r
 357   }\r
 358 \r
 359   private FinderPattern[] selectBestPatterns() throws ReaderException {\r
 360     Collections.insertionSort(possibleCenters, new CenterComparator());\r
 361     int size = 0;\r
 362     int max = possibleCenters.size();\r
 363     while (size < max) {\r
 364       if (((FinderPattern) possibleCenters.elementAt(size)).getCount() < CENTER_QUORUM) {\r
 365         break;\r
 366       }\r
 367       size++;\r
 368     }\r
 369 \r
 370     if (size < 3) {\r
 371       // Couldn't find enough finder patterns\r
 372       throw new ReaderException("Could not find three finder patterns");\r
 373     }\r
 374 \r
 375     if (size == 3) {\r
 376       // Found just enough -- hope these are good!\r
 377       // toArray() is not available\r
 378       FinderPattern[] result = new FinderPattern[possibleCenters.size()];\r
 379       for (int i = 0; i < possibleCenters.size(); i++) {\r
 380         result[i] = (FinderPattern) possibleCenters.elementAt(i);\r
 381       }\r
 382       return result;\r
 383     }\r
 384 \r
 385     possibleCenters.setSize(size);\r
 386 \r
 387     // Hmm, multiple found. We need to pick the best three. Find the most\r
 388     // popular ones whose module size is nearest the average\r
 389 \r
 390     float averageModuleSize = 0.0f;\r
 391     for (int i = 0; i < size; i++) {\r
 392       averageModuleSize += ((FinderPattern) possibleCenters.elementAt(i)).getEstimatedModuleSize();\r
 393     }\r
 394     averageModuleSize /= (float) size;\r
 395 \r
 396     Collections.insertionSort(\r
 397         possibleCenters,\r
 398         new ClosestToAverageComparator(averageModuleSize));\r
 399 \r
 400     //return confirmedCenters.subList(0, 3).toArray(new FinderPattern[3]);\r
 401     FinderPattern[] result = new FinderPattern[3];\r
 402     for (int i = 0; i < 3; i++) {\r
 403       result[i] = (FinderPattern) possibleCenters.elementAt(i);\r
 404     }\r
 405     return result;\r
 406   }\r
 407 \r
 408   private static FinderPattern[] orderBestPatterns(FinderPattern[] patterns) {\r
 409 \r
 410     // Find distances between pattern centers\r
 411     float abDistance = distance(patterns[0], patterns[1]);\r
 412     float bcDistance = distance(patterns[1], patterns[2]);\r
 413     float acDistance = distance(patterns[0], patterns[2]);\r
 414 \r
 415     FinderPattern topLeft;\r
 416     FinderPattern topRight;\r
 417     FinderPattern bottomLeft;\r
 418     // Assume one closest to other two is top left\r
 419     if (bcDistance >= abDistance && bcDistance >= acDistance) {\r
 420       topLeft = patterns[0];\r
 421       topRight = patterns[1]; // These two are guesses at the moment\r
 422       bottomLeft = patterns[2];\r
 423     } else if (acDistance >= bcDistance && acDistance >= abDistance) {\r
 424       topLeft = patterns[1];\r
 425       topRight = patterns[0];\r
 426       bottomLeft = patterns[2];\r
 427     } else {\r
 428       topLeft = patterns[2];\r
 429       topRight = patterns[0];\r
 430       bottomLeft = patterns[1];\r
 431     }\r
 432 \r
 433     // Use cross product to figure out which of other1/2 is the bottom left\r
 434     // pattern. The vector "top-left -> bottom-left" x "top-left -> top-right"\r
 435     // should yield a vector with positive z component\r
 436     if ((bottomLeft.getY() - topLeft.getY()) * (topRight.getX() - topLeft.getX()) <\r
 437         (bottomLeft.getX() - topLeft.getX()) * (topRight.getY() - topLeft.getY())) {\r
 438       FinderPattern temp = topRight;\r
 439       topRight = bottomLeft;\r
 440       bottomLeft = temp;\r
 441     }\r
 442 \r
 443     return new FinderPattern[]{bottomLeft, topLeft, topRight};\r
 444   }\r
 445 \r
 446   static float distance(ResultPoint pattern1, ResultPoint pattern2) {\r
 447     float xDiff = pattern1.getX() - pattern2.getX();\r
 448     float yDiff = pattern1.getY() - pattern2.getY();\r
 449     return (float) Math.sqrt((double) (xDiff * xDiff + yDiff * yDiff));\r
 450   }\r
 451 \r
 452   private static class CenterComparator implements Comparator {\r
 453     public int compare(Object center1, Object center2) {\r
 454       return ((FinderPattern) center2).getCount() - ((FinderPattern) center1).getCount();\r
 455     }\r
 456   }\r
 457 \r
 458   private static class ClosestToAverageComparator implements Comparator {\r
 459     private float averageModuleSize;\r
 460 \r
 461     private ClosestToAverageComparator(float averageModuleSize) {\r
 462       this.averageModuleSize = averageModuleSize;\r
 463     }\r
 464 \r
 465     public int compare(Object center1, Object center2) {\r
 466       return\r
 467           Math.abs(((FinderPattern) center1).getEstimatedModuleSize() - averageModuleSize) <\r
 468               Math.abs(((FinderPattern) center2).getEstimatedModuleSize() - averageModuleSize) ?\r
 469               -1 :\r
 470               1;\r
 471     }\r
 472   }\r
 473 \r
 474 }\r