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 ReaderException = com.google.zxing.ReaderException;\r
  18 using ResultPoint = com.google.zxing.ResultPoint;\r
  19 using ResultPointCallback = com.google.zxing.ResultPointCallback;\r
  20 using BitMatrix = com.google.zxing.common.BitMatrix;\r
  21 namespace com.google.zxing.qrcode.detector\r
  22 {\r
  23         \r
  24         /// <summary> <p>This class attempts to find alignment patterns in a QR Code. Alignment patterns look like finder\r
  25         /// patterns but are smaller and appear at regular intervals throughout the image.</p>\r
  26         /// \r
  27         /// <p>At the moment this only looks for the bottom-right alignment pattern.</p>\r
  28         /// \r
  29         /// <p>This is mostly a simplified copy of {@link FinderPatternFinder}. It is copied,\r
  30         /// pasted and stripped down here for maximum performance but does unfortunately duplicate\r
  31         /// some code.</p>\r
  32         /// \r
  33         /// <p>This class is thread-safe but not reentrant. Each thread must allocate its own object.\r
  34         /// \r
  35         /// </summary>\r
  36         /// <author>  Sean Owen\r
  37         /// </author>\r
  38         /// <author>www.Redivivus.in (suraj.supekar@redivivus.in) - Ported from ZXING Java Source \r
  39         /// </author>\r
  40         sealed class AlignmentPatternFinder\r
  41         {\r
  42                 \r
  43                 //UPGRADE_NOTE: Final was removed from the declaration of 'image '. "ms-help://MS.VSCC.v80/dv_commoner/local/redirect.htm?index='!DefaultContextWindowIndex'&keyword='jlca1003'"\r
  44                 private BitMatrix image;\r
  45                 //UPGRADE_NOTE: Final was removed from the declaration of 'possibleCenters '. "ms-help://MS.VSCC.v80/dv_commoner/local/redirect.htm?index='!DefaultContextWindowIndex'&keyword='jlca1003'"\r
  46                 private System.Collections.ArrayList possibleCenters;\r
  47                 //UPGRADE_NOTE: Final was removed from the declaration of 'startX '. "ms-help://MS.VSCC.v80/dv_commoner/local/redirect.htm?index='!DefaultContextWindowIndex'&keyword='jlca1003'"\r
  48                 private int startX;\r
  49                 //UPGRADE_NOTE: Final was removed from the declaration of 'startY '. "ms-help://MS.VSCC.v80/dv_commoner/local/redirect.htm?index='!DefaultContextWindowIndex'&keyword='jlca1003'"\r
  50                 private int startY;\r
  51                 //UPGRADE_NOTE: Final was removed from the declaration of 'width '. "ms-help://MS.VSCC.v80/dv_commoner/local/redirect.htm?index='!DefaultContextWindowIndex'&keyword='jlca1003'"\r
  52                 private int width;\r
  53                 //UPGRADE_NOTE: Final was removed from the declaration of 'height '. "ms-help://MS.VSCC.v80/dv_commoner/local/redirect.htm?index='!DefaultContextWindowIndex'&keyword='jlca1003'"\r
  54                 private int height;\r
  55                 //UPGRADE_NOTE: Final was removed from the declaration of 'moduleSize '. "ms-help://MS.VSCC.v80/dv_commoner/local/redirect.htm?index='!DefaultContextWindowIndex'&keyword='jlca1003'"\r
  56                 private float moduleSize;\r
  57                 //UPGRADE_NOTE: Final was removed from the declaration of 'crossCheckStateCount '. "ms-help://MS.VSCC.v80/dv_commoner/local/redirect.htm?index='!DefaultContextWindowIndex'&keyword='jlca1003'"\r
  58                 private int[] crossCheckStateCount;\r
  59                 //UPGRADE_NOTE: Final was removed from the declaration of 'resultPointCallback '. "ms-help://MS.VSCC.v80/dv_commoner/local/redirect.htm?index='!DefaultContextWindowIndex'&keyword='jlca1003'"\r
  60                 private ResultPointCallback resultPointCallback;\r
  61                 \r
  62                 /// <summary> <p>Creates a finder that will look in a portion of the whole image.</p>\r
  63                 /// \r
  64                 /// </summary>\r
  65                 /// <param name="image">image to search\r
  66                 /// </param>\r
  67                 /// <param name="startX">left column from which to start searching\r
  68                 /// </param>\r
  69                 /// <param name="startY">top row from which to start searching\r
  70                 /// </param>\r
  71                 /// <param name="width">width of region to search\r
  72                 /// </param>\r
  73                 /// <param name="height">height of region to search\r
  74                 /// </param>\r
  75                 /// <param name="moduleSize">estimated module size so far\r
  76                 /// </param>\r
  77                 internal AlignmentPatternFinder(BitMatrix image, int startX, int startY, int width, int height, float moduleSize, ResultPointCallback resultPointCallback)\r
  78                 {\r
  79                         this.image = image;\r
  80                         this.possibleCenters = System.Collections.ArrayList.Synchronized(new System.Collections.ArrayList(5));\r
  81                         this.startX = startX;\r
  82                         this.startY = startY;\r
  83                         this.width = width;\r
  84                         this.height = height;\r
  85                         this.moduleSize = moduleSize;\r
  86                         this.crossCheckStateCount = new int[3];\r
  87                         this.resultPointCallback = resultPointCallback;\r
  88                 }\r
  89                 \r
  90                 /// <summary> <p>This method attempts to find the bottom-right alignment pattern in the image. It is a bit messy since\r
  91                 /// it's pretty performance-critical and so is written to be fast foremost.</p>\r
  92                 /// \r
  93                 /// </summary>\r
  94                 /// <returns> {@link AlignmentPattern} if found\r
  95                 /// </returns>\r
  96                 /// <throws>  ReaderException if not found </throws>\r
  97                 internal AlignmentPattern find()\r
  98                 {\r
  99                         int startX = this.startX;\r
 100                         int height = this.height;\r
 101                         int maxJ = startX + width;\r
 102                         int middleI = startY + (height >> 1);\r
 103                         // We are looking for black/white/black modules in 1:1:1 ratio;\r
 104                         // this tracks the number of black/white/black modules seen so far\r
 105                         int[] stateCount = new int[3];\r
 106                         for (int iGen = 0; iGen < height; iGen++)\r
 107                         {\r
 108                                 // Search from middle outwards\r
 109                                 int i = middleI + ((iGen & 0x01) == 0?((iGen + 1) >> 1):- ((iGen + 1) >> 1));\r
 110                                 stateCount[0] = 0;\r
 111                                 stateCount[1] = 0;\r
 112                                 stateCount[2] = 0;\r
 113                                 int j = startX;\r
 114                                 // Burn off leading white pixels before anything else; if we start in the middle of\r
 115                                 // a white run, it doesn't make sense to count its length, since we don't know if the\r
 116                                 // white run continued to the left of the start point\r
 117                                 while (j < maxJ && !image.get_Renamed(j, i))\r
 118                                 {\r
 119                                         j++;\r
 120                                 }\r
 121                                 int currentState = 0;\r
 122                                 while (j < maxJ)\r
 123                                 {\r
 124                                         if (image.get_Renamed(j, i))\r
 125                                         {\r
 126                                                 // Black pixel\r
 127                                                 if (currentState == 1)\r
 128                                                 {\r
 129                                                         // Counting black pixels\r
 130                                                         stateCount[currentState]++;\r
 131                                                 }\r
 132                                                 else\r
 133                                                 {\r
 134                                                         // Counting white pixels\r
 135                                                         if (currentState == 2)\r
 136                                                         {\r
 137                                                                 // A winner?\r
 138                                                                 if (foundPatternCross(stateCount))\r
 139                                                                 {\r
 140                                                                         // Yes\r
 141                                                                         AlignmentPattern confirmed = handlePossibleCenter(stateCount, i, j);\r
 142                                                                         if (confirmed != null)\r
 143                                                                         {\r
 144                                                                                 return confirmed;\r
 145                                                                         }\r
 146                                                                 }\r
 147                                                                 stateCount[0] = stateCount[2];\r
 148                                                                 stateCount[1] = 1;\r
 149                                                                 stateCount[2] = 0;\r
 150                                                                 currentState = 1;\r
 151                                                         }\r
 152                                                         else\r
 153                                                         {\r
 154                                                                 stateCount[++currentState]++;\r
 155                                                         }\r
 156                                                 }\r
 157                                         }\r
 158                                         else\r
 159                                         {\r
 160                                                 // White pixel\r
 161                                                 if (currentState == 1)\r
 162                                                 {\r
 163                                                         // Counting black pixels\r
 164                                                         currentState++;\r
 165                                                 }\r
 166                                                 stateCount[currentState]++;\r
 167                                         }\r
 168                                         j++;\r
 169                                 }\r
 170                                 if (foundPatternCross(stateCount))\r
 171                                 {\r
 172                                         AlignmentPattern confirmed = handlePossibleCenter(stateCount, i, maxJ);\r
 173                                         if (confirmed != null)\r
 174                                         {\r
 175                                                 return confirmed;\r
 176                                         }\r
 177                                 }\r
 178                         }\r
 179                         \r
 180                         // Hmm, nothing we saw was observed and confirmed twice. If we had\r
 181                         // any guess at all, return it.\r
 182                         if (!(possibleCenters.Count == 0))\r
 183                         {\r
 184                                 return (AlignmentPattern) possibleCenters[0];\r
 185                         }\r
 186                         \r
 187                         throw ReaderException.Instance;\r
 188                 }\r
 189                 \r
 190                 /// <summary> Given a count of black/white/black pixels just seen and an end position,\r
 191                 /// figures the location of the center of this black/white/black run.\r
 192                 /// </summary>\r
 193                 private static float centerFromEnd(int[] stateCount, int end)\r
 194                 {\r
 195                         //UPGRADE_WARNING: Data types in Visual C# might be different.  Verify the accuracy of narrowing conversions. "ms-help://MS.VSCC.v80/dv_commoner/local/redirect.htm?index='!DefaultContextWindowIndex'&keyword='jlca1042'"\r
 196                         return (float) (end - stateCount[2]) - stateCount[1] / 2.0f;\r
 197                 }\r
 198                 \r
 199                 /// <param name="stateCount">count of black/white/black pixels just read\r
 200                 /// </param>\r
 201                 /// <returns> true iff the proportions of the counts is close enough to the 1/1/1 ratios\r
 202                 /// used by alignment patterns to be considered a match\r
 203                 /// </returns>\r
 204                 private bool foundPatternCross(int[] stateCount)\r
 205                 {\r
 206                         float moduleSize = this.moduleSize;\r
 207                         float maxVariance = moduleSize / 2.0f;\r
 208                         for (int i = 0; i < 3; i++)\r
 209                         {\r
 210                                 if (System.Math.Abs(moduleSize - stateCount[i]) >= maxVariance)\r
 211                                 {\r
 212                                         return false;\r
 213                                 }\r
 214                         }\r
 215                         return true;\r
 216                 }\r
 217                 \r
 218                 /// <summary> <p>After a horizontal scan finds a potential alignment pattern, this method\r
 219                 /// "cross-checks" by scanning down vertically through the center of the possible\r
 220                 /// alignment pattern to see if the same proportion is detected.</p>\r
 221                 /// \r
 222                 /// </summary>\r
 223                 /// <param name="startI">row where an alignment pattern was detected\r
 224                 /// </param>\r
 225                 /// <param name="centerJ">center of the section that appears to cross an alignment pattern\r
 226                 /// </param>\r
 227                 /// <param name="maxCount">maximum reasonable number of modules that should be\r
 228                 /// observed in any reading state, based on the results of the horizontal scan\r
 229                 /// </param>\r
 230                 /// <returns> vertical center of alignment pattern, or {@link Float#NaN} if not found\r
 231                 /// </returns>\r
 232                 private float crossCheckVertical(int startI, int centerJ, int maxCount, int originalStateCountTotal)\r
 233                 {\r
 234                         BitMatrix image = this.image;\r
 235                         \r
 236                         int maxI = image.Height;\r
 237                         int[] stateCount = crossCheckStateCount;\r
 238                         stateCount[0] = 0;\r
 239                         stateCount[1] = 0;\r
 240                         stateCount[2] = 0;\r
 241                         \r
 242                         // Start counting up from center\r
 243                         int i = startI;\r
 244                         while (i >= 0 && image.get_Renamed(centerJ, i) && stateCount[1] <= maxCount)\r
 245                         {\r
 246                                 stateCount[1]++;\r
 247                                 i--;\r
 248                         }\r
 249                         // If already too many modules in this state or ran off the edge:\r
 250                         if (i < 0 || stateCount[1] > maxCount)\r
 251                         {\r
 252                                 return System.Single.NaN;\r
 253                         }\r
 254                         while (i >= 0 && !image.get_Renamed(centerJ, i) && stateCount[0] <= maxCount)\r
 255                         {\r
 256                                 stateCount[0]++;\r
 257                                 i--;\r
 258                         }\r
 259                         if (stateCount[0] > maxCount)\r
 260                         {\r
 261                                 return System.Single.NaN;\r
 262                         }\r
 263                         \r
 264                         // Now also count down from center\r
 265                         i = startI + 1;\r
 266                         while (i < maxI && image.get_Renamed(centerJ, i) && stateCount[1] <= maxCount)\r
 267                         {\r
 268                                 stateCount[1]++;\r
 269                                 i++;\r
 270                         }\r
 271                         if (i == maxI || stateCount[1] > maxCount)\r
 272                         {\r
 273                                 return System.Single.NaN;\r
 274                         }\r
 275                         while (i < maxI && !image.get_Renamed(centerJ, i) && stateCount[2] <= maxCount)\r
 276                         {\r
 277                                 stateCount[2]++;\r
 278                                 i++;\r
 279                         }\r
 280                         if (stateCount[2] > maxCount)\r
 281                         {\r
 282                                 return System.Single.NaN;\r
 283                         }\r
 284                         \r
 285                         int stateCountTotal = stateCount[0] + stateCount[1] + stateCount[2];\r
 286                         if (5 * System.Math.Abs(stateCountTotal - originalStateCountTotal) >= 2 * originalStateCountTotal)\r
 287                         {\r
 288                                 return System.Single.NaN;\r
 289                         }\r
 290                         \r
 291                         return foundPatternCross(stateCount)?centerFromEnd(stateCount, i):System.Single.NaN;\r
 292                 }\r
 293                 \r
 294                 /// <summary> <p>This is called when a horizontal scan finds a possible alignment pattern. It will\r
 295                 /// cross check with a vertical scan, and if successful, will see if this pattern had been\r
 296                 /// found on a previous horizontal scan. If so, we consider it confirmed and conclude we have\r
 297                 /// found the alignment pattern.</p>\r
 298                 /// \r
 299                 /// </summary>\r
 300                 /// <param name="stateCount">reading state module counts from horizontal scan\r
 301                 /// </param>\r
 302                 /// <param name="i">row where alignment pattern may be found\r
 303                 /// </param>\r
 304                 /// <param name="j">end of possible alignment pattern in row\r
 305                 /// </param>\r
 306                 /// <returns> {@link AlignmentPattern} if we have found the same pattern twice, or null if not\r
 307                 /// </returns>\r
 308                 private AlignmentPattern handlePossibleCenter(int[] stateCount, int i, int j)\r
 309                 {\r
 310                         int stateCountTotal = stateCount[0] + stateCount[1] + stateCount[2];\r
 311                         float centerJ = centerFromEnd(stateCount, j);\r
 312                         //UPGRADE_WARNING: Data types in Visual C# might be different.  Verify the accuracy of narrowing conversions. "ms-help://MS.VSCC.v80/dv_commoner/local/redirect.htm?index='!DefaultContextWindowIndex'&keyword='jlca1042'"\r
 313                         float centerI = crossCheckVertical(i, (int) centerJ, 2 * stateCount[1], stateCountTotal);\r
 314                         if (!System.Single.IsNaN(centerI))\r
 315                         {\r
 316                                 //UPGRADE_WARNING: Data types in Visual C# might be different.  Verify the accuracy of narrowing conversions. "ms-help://MS.VSCC.v80/dv_commoner/local/redirect.htm?index='!DefaultContextWindowIndex'&keyword='jlca1042'"\r
 317                                 float estimatedModuleSize = (float) (stateCount[0] + stateCount[1] + stateCount[2]) / 3.0f;\r
 318                                 int max = possibleCenters.Count;\r
 319                                 for (int index = 0; index < max; index++)\r
 320                                 {\r
 321                                         AlignmentPattern center = (AlignmentPattern) possibleCenters[index];\r
 322                                         // Look for about the same center and module size:\r
 323                                         if (center.aboutEquals(estimatedModuleSize, centerI, centerJ))\r
 324                                         {\r
 325                                                 return new AlignmentPattern(centerJ, centerI, estimatedModuleSize);\r
 326                                         }\r
 327                                 }\r
 328                                 // Hadn't found this before; save it\r
 329                                 ResultPoint point = new AlignmentPattern(centerJ, centerI, estimatedModuleSize);\r
 330                                 possibleCenters.Add(point);\r
 331                                 if (resultPointCallback != null)\r
 332                                 {\r
 333                                         resultPointCallback.foundPossibleResultPoint(point);\r
 334                                 }\r
 335                         }\r
 336                         return null;\r
 337                 }\r
 338         }\r
 339 }