csharp/qrcode/detector/AlignmentPatternFinder.cs

   1 /*\r
   2 * Copyright 2007 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 using System;\r
  17 using com.google.zxing;\r
  18 using com.google.zxing.common;\r
  19 \r
  20 namespace com.google.zxing.qrcode.detector\r
  21 {\r
  22     public sealed class AlignmentPatternFinder\r
  23     { \r
  24           private  MonochromeBitmapSource image;\r
  25           private  System.Collections.ArrayList possibleCenters;\r
  26           private  int startX;\r
  27           private  int startY;\r
  28           private  int width;\r
  29           private  int height;\r
  30           private  float moduleSize;\r
  31           private  int[] crossCheckStateCount;\r
  32 \r
  33           /**\r
  34            * <p>Creates a finder that will look in a portion of the whole image.</p>\r
  35            *\r
  36            * @param image image to search\r
  37            * @param startX left column from which to start searching\r
  38            * @param startY top row from which to start searching\r
  39            * @param width width of region to search\r
  40            * @param height height of region to search\r
  41            * @param moduleSize estimated module size so far\r
  42            */\r
  43           public AlignmentPatternFinder(MonochromeBitmapSource image,\r
  44                                  int startX,\r
  45                                  int startY,\r
  46                                  int width,\r
  47                                  int height,\r
  48                                  float moduleSize) {\r
  49             this.image = image;\r
  50             this.possibleCenters = new System.Collections.ArrayList(5);\r
  51             this.startX = startX;\r
  52             this.startY = startY;\r
  53             this.width = width;\r
  54             this.height = height;\r
  55             this.moduleSize = moduleSize;\r
  56             this.crossCheckStateCount = new int[3];\r
  57           }\r
  58 \r
  59           /**\r
  60            * <p>This method attempts to find the bottom-right alignment pattern in the image. It is a bit messy since\r
  61            * it's pretty performance-critical and so is written to be fast foremost.</p>\r
  62            *\r
  63            * @return {@link AlignmentPattern} if found\r
  64            * @throws ReaderException if not found\r
  65            */\r
  66           public AlignmentPattern find() {\r
  67             int startX = this.startX;\r
  68             int height = this.height;\r
  69             int maxJ = startX + width;\r
  70             int middleI = startY + (height >> 1);\r
  71             BitArray luminanceRow = new BitArray(width);\r
  72             // We are looking for black/white/black modules in 1:1:1 ratio;\r
  73             // this tracks the number of black/white/black modules seen so far\r
  74             int[] stateCount = new int[3];\r
  75             for (int iGen = 0; iGen < height; iGen++) {\r
  76               // Search from middle outwards\r
  77               int i = middleI + ((iGen & 0x01) == 0 ? ((iGen + 1) >> 1) : -((iGen + 1) >> 1));\r
  78               image.getBlackRow(i, luminanceRow, startX, width);\r
  79               stateCount[0] = 0;\r
  80               stateCount[1] = 0;\r
  81               stateCount[2] = 0;\r
  82               int j = startX;\r
  83               // Burn off leading white pixels before anything else; if we start in the middle of\r
  84               // a white run, it doesn't make sense to count its length, since we don't know if the\r
  85               // white run continued to the left of the start point\r
  86               while (j < maxJ && !luminanceRow.get(j - startX)) {\r
  87                 j++;\r
  88               }\r
  89               int currentState = 0;\r
  90               while (j < maxJ) {\r
  91                 if (luminanceRow.get(j - startX)) {\r
  92                   // Black pixel\r
  93                   if (currentState == 1) { // Counting black pixels\r
  94                     stateCount[currentState]++;\r
  95                   } else { // Counting white pixels\r
  96                     if (currentState == 2) { // A winner?\r
  97                       if (foundPatternCross(stateCount)) { // Yes\r
  98                         AlignmentPattern confirmed = handlePossibleCenter(stateCount, i, j);\r
  99                         if (confirmed != null) {\r
 100                           return confirmed;\r
 101                         }\r
 102                       }\r
 103                       stateCount[0] = stateCount[2];\r
 104                       stateCount[1] = 1;\r
 105                       stateCount[2] = 0;\r
 106                       currentState = 1;\r
 107                     } else {\r
 108                       stateCount[++currentState]++;\r
 109                     }\r
 110                   }\r
 111                 } else { // White pixel\r
 112                   if (currentState == 1) { // Counting black pixels\r
 113                     currentState++;\r
 114                   }\r
 115                   stateCount[currentState]++;\r
 116                 }\r
 117                 j++;\r
 118               }\r
 119               if (foundPatternCross(stateCount)) {\r
 120                 AlignmentPattern confirmed = handlePossibleCenter(stateCount, i, maxJ);\r
 121                 if (confirmed != null) {\r
 122                   return confirmed;\r
 123                 }\r
 124               }\r
 125 \r
 126             }\r
 127 \r
 128             // Hmm, nothing we saw was observed and confirmed twice. If we had\r
 129             // any guess at all, return it.\r
 130             if (!(possibleCenters.Count==0)) {\r
 131               return (AlignmentPattern) possibleCenters[0];\r
 132             }\r
 133 \r
 134             throw new ReaderException();\r
 135           }\r
 136 \r
 137           /**\r
 138            * Given a count of black/white/black pixels just seen and an end position,\r
 139            * figures the location of the center of this black/white/black run.\r
 140            */\r
 141           private static float centerFromEnd(int[] stateCount, int end) {\r
 142             return (float) (end - stateCount[2]) - stateCount[1] / 2.0f;\r
 143           }\r
 144 \r
 145           /**\r
 146            * @param stateCount count of black/white/black pixels just read\r
 147            * @return true iff the proportions of the counts is close enough to the 1/1/1 ratios\r
 148            *         used by alignment patterns to be considered a match\r
 149            */\r
 150           private bool foundPatternCross(int[] stateCount) {\r
 151             float moduleSize = this.moduleSize;\r
 152             float maxVariance = moduleSize / 2.0f;\r
 153             for (int i = 0; i < 3; i++) {\r
 154               if (Math.Abs(moduleSize - stateCount[i]) >= maxVariance) {\r
 155                 return false;\r
 156               }\r
 157             }\r
 158             return true;\r
 159           }\r
 160 \r
 161           /**\r
 162            * <p>After a horizontal scan finds a potential alignment pattern, this method\r
 163            * "cross-checks" by scanning down vertically through the center of the possible\r
 164            * alignment pattern to see if the same proportion is detected.</p>\r
 165            *\r
 166            * @param startI row where an alignment pattern was detected\r
 167            * @param centerJ center of the section that appears to cross an alignment pattern\r
 168            * @param maxCount maximum reasonable number of modules that should be\r
 169            * observed in any reading state, based on the results of the horizontal scan\r
 170            * @return vertical center of alignment pattern, or {@link Float#NaN} if not found\r
 171            */\r
 172           private float crossCheckVertical(int startI, int centerJ, int maxCount, int originalStateCountTotal) {\r
 173             MonochromeBitmapSource image = this.image;\r
 174 \r
 175             int maxI = image.getHeight();\r
 176             int[] stateCount = crossCheckStateCount;\r
 177             stateCount[0] = 0;\r
 178             stateCount[1] = 0;\r
 179             stateCount[2] = 0;\r
 180 \r
 181             // Start counting up from center\r
 182             int i = startI;\r
 183             while (i >= 0 && image.isBlack(centerJ, i) && stateCount[1] <= maxCount) {\r
 184               stateCount[1]++;\r
 185               i--;\r
 186             }\r
 187             // If already too many modules in this state or ran off the edge:\r
 188             if (i < 0 || stateCount[1] > maxCount) {\r
 189               return float.NaN;\r
 190             }\r
 191             while (i >= 0 && !image.isBlack(centerJ, i) && stateCount[0] <= maxCount) {\r
 192               stateCount[0]++;\r
 193               i--;\r
 194             }\r
 195             if (stateCount[0] > maxCount) {\r
 196                 return float.NaN;\r
 197             }\r
 198 \r
 199             // Now also count down from center\r
 200             i = startI + 1;\r
 201             while (i < maxI && image.isBlack(centerJ, i) && stateCount[1] <= maxCount) {\r
 202               stateCount[1]++;\r
 203               i++;\r
 204             }\r
 205             if (i == maxI || stateCount[1] > maxCount) {\r
 206                 return float.NaN;\r
 207             }\r
 208             while (i < maxI && !image.isBlack(centerJ, i) && stateCount[2] <= maxCount) {\r
 209               stateCount[2]++;\r
 210               i++;\r
 211             }\r
 212             if (stateCount[2] > maxCount) {\r
 213                 return float.NaN;\r
 214             }\r
 215 \r
 216             int stateCountTotal = stateCount[0] + stateCount[1] + stateCount[2];\r
 217             if (5 * Math.Abs(stateCountTotal - originalStateCountTotal) >= originalStateCountTotal) {\r
 218                 return float.NaN;\r
 219             }\r
 220 \r
 221             return foundPatternCross(stateCount) ? centerFromEnd(stateCount, i) : float.NaN;\r
 222           }\r
 223 \r
 224           /**\r
 225            * <p>This is called when a horizontal scan finds a possible alignment pattern. It will\r
 226            * cross check with a vertical scan, and if successful, will see if this pattern had been\r
 227            * found on a previous horizontal scan. If so, we consider it confirmed and conclude we have\r
 228            * found the alignment pattern.</p>\r
 229            *\r
 230            * @param stateCount reading state module counts from horizontal scan\r
 231            * @param i row where alignment pattern may be found\r
 232            * @param j end of possible alignment pattern in row\r
 233            * @return {@link AlignmentPattern} if we have found the same pattern twice, or null if not\r
 234            */\r
 235           private AlignmentPattern handlePossibleCenter(int[] stateCount, int i, int j) {\r
 236             int stateCountTotal = stateCount[0] + stateCount[1] + stateCount[2];\r
 237             float centerJ = centerFromEnd(stateCount, j);\r
 238             float centerI = crossCheckVertical(i, (int) centerJ, 2 * stateCount[1], stateCountTotal);\r
 239             if (!Single.IsNaN(centerI))\r
 240             {\r
 241               float estimatedModuleSize = (float) (stateCount[0] + stateCount[1] + stateCount[2]) / 3.0f;\r
 242               int max = possibleCenters.Count;\r
 243               for (int index = 0; index < max; index++) {\r
 244                 AlignmentPattern center = (AlignmentPattern) possibleCenters[index];\r
 245                 // Look for about the same center and module size:\r
 246                 if (center.aboutEquals(estimatedModuleSize, centerI, centerJ)) {\r
 247                   return new AlignmentPattern(centerJ, centerI, estimatedModuleSize);\r
 248                 }\r
 249               }\r
 250               // Hadn't found this before; save it\r
 251               possibleCenters.Add(new AlignmentPattern(centerJ, centerI, estimatedModuleSize));\r
 252             }\r
 253             return null;\r
 254           }\r
 255     \r
 256     \r
 257     }\r
 258 }