csharp/qrcode/detector/FinderPatternFinder.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 DecodeHintType = com.google.zxing.DecodeHintType;\r
  18 using ReaderException = com.google.zxing.ReaderException;\r
  19 using ResultPoint = com.google.zxing.ResultPoint;\r
  20 using ResultPointCallback = com.google.zxing.ResultPointCallback;\r
  21 using Collections = com.google.zxing.common.Collections;\r
  22 using Comparator = com.google.zxing.common.Comparator;\r
  23 using BitMatrix = com.google.zxing.common.BitMatrix;\r
  24 namespace com.google.zxing.qrcode.detector\r
  25 {\r
  26         \r
  27         /// <summary> <p>This class attempts to find finder patterns in a QR Code. Finder patterns are the square\r
  28         /// markers at three corners of a QR Code.</p>\r
  29         /// \r
  30         /// <p>This class is thread-safe but not reentrant. Each thread must allocate its own object.\r
  31         /// \r
  32         /// </summary>\r
  33         /// <author>  Sean Owen\r
  34         /// </author>\r
  35         /// <author>www.Redivivus.in (suraj.supekar@redivivus.in) - Ported from ZXING Java Source \r
  36         /// </author>\r
  37         public class FinderPatternFinder\r
  38         {\r
  39                 virtual protected internal BitMatrix Image\r
  40                 {\r
  41                         get\r
  42                         {\r
  43                                 return image;\r
  44                         }\r
  45                         \r
  46                 }\r
  47                 virtual protected internal System.Collections.ArrayList PossibleCenters\r
  48                 {\r
  49                         get\r
  50                         {\r
  51                                 return possibleCenters;\r
  52                         }\r
  53                         \r
  54                 }\r
  55                 private int[] CrossCheckStateCount\r
  56                 {\r
  57                         get\r
  58                         {\r
  59                                 crossCheckStateCount[0] = 0;\r
  60                                 crossCheckStateCount[1] = 0;\r
  61                                 crossCheckStateCount[2] = 0;\r
  62                                 crossCheckStateCount[3] = 0;\r
  63                                 crossCheckStateCount[4] = 0;\r
  64                                 return crossCheckStateCount;\r
  65                         }\r
  66                         \r
  67                 }\r
  68                 \r
  69                 private const int CENTER_QUORUM = 2;\r
  70                 protected internal const int MIN_SKIP = 3; // 1 pixel/module times 3 modules/center\r
  71                 protected internal const int MAX_MODULES = 57; // support up to version 10 for mobile clients\r
  72                 private const int INTEGER_MATH_SHIFT = 8;\r
  73                 \r
  74                 //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
  75                 private BitMatrix image;\r
  76                 //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
  77                 private System.Collections.ArrayList possibleCenters;\r
  78                 private bool hasSkipped;\r
  79                 //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
  80                 private int[] crossCheckStateCount;\r
  81                 //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
  82                 private ResultPointCallback resultPointCallback;\r
  83                 \r
  84                 /// <summary> <p>Creates a finder that will search the image for three finder patterns.</p>\r
  85                 /// \r
  86                 /// </summary>\r
  87                 /// <param name="image">image to search\r
  88                 /// </param>\r
  89                 public FinderPatternFinder(BitMatrix image):this(image, null)\r
  90                 {\r
  91                 }\r
  92                 \r
  93                 public FinderPatternFinder(BitMatrix image, ResultPointCallback resultPointCallback)\r
  94                 {\r
  95                         this.image = image;\r
  96                         this.possibleCenters = System.Collections.ArrayList.Synchronized(new System.Collections.ArrayList(10));\r
  97                         this.crossCheckStateCount = new int[5];\r
  98                         this.resultPointCallback = resultPointCallback;\r
  99                 }\r
 100                 \r
 101                 internal virtual FinderPatternInfo find(System.Collections.Hashtable hints)\r
 102                 {\r
 103                         bool tryHarder = hints != null && hints.ContainsKey(DecodeHintType.TRY_HARDER);\r
 104                         int maxI = image.Height;\r
 105                         int maxJ = image.Width;\r
 106                         // We are looking for black/white/black/white/black modules in\r
 107                         // 1:1:3:1:1 ratio; this tracks the number of such modules seen so far\r
 108                         \r
 109                         // Let's assume that the maximum version QR Code we support takes up 1/4 the height of the\r
 110                         // image, and then account for the center being 3 modules in size. This gives the smallest\r
 111                         // number of pixels the center could be, so skip this often. When trying harder, look for all\r
 112                         // QR versions regardless of how dense they are.\r
 113                         int iSkip = (3 * maxI) / (4 * MAX_MODULES);\r
 114                         if (iSkip < MIN_SKIP || tryHarder)\r
 115                         {\r
 116                                 iSkip = MIN_SKIP;\r
 117                         }\r
 118                         \r
 119                         bool done = false;\r
 120                         int[] stateCount = new int[5];\r
 121                         for (int i = iSkip - 1; i < maxI && !done; i += iSkip)\r
 122                         {\r
 123                                 // Get a row of black/white values\r
 124                                 stateCount[0] = 0;\r
 125                                 stateCount[1] = 0;\r
 126                                 stateCount[2] = 0;\r
 127                                 stateCount[3] = 0;\r
 128                                 stateCount[4] = 0;\r
 129                                 int currentState = 0;\r
 130                                 for (int j = 0; j < maxJ; j++)\r
 131                                 {\r
 132                                         if (image.get_Renamed(j, i))\r
 133                                         {\r
 134                                                 // Black pixel\r
 135                                                 if ((currentState & 1) == 1)\r
 136                                                 {\r
 137                                                         // Counting white pixels\r
 138                                                         currentState++;\r
 139                                                 }\r
 140                                                 stateCount[currentState]++;\r
 141                                         }\r
 142                                         else\r
 143                                         {\r
 144                                                 // White pixel\r
 145                                                 if ((currentState & 1) == 0)\r
 146                                                 {\r
 147                                                         // Counting black pixels\r
 148                                                         if (currentState == 4)\r
 149                                                         {\r
 150                                                                 // A winner?\r
 151                                                                 if (foundPatternCross(stateCount))\r
 152                                                                 {\r
 153                                                                         // Yes\r
 154                                                                         bool confirmed = handlePossibleCenter(stateCount, i, j);\r
 155                                                                         if (confirmed)\r
 156                                                                         {\r
 157                                                                                 // Start examining every other line. Checking each line turned out to be too\r
 158                                                                                 // expensive and didn't improve performance.\r
 159                                                                                 iSkip = 2;\r
 160                                                                                 if (hasSkipped)\r
 161                                                                                 {\r
 162                                                                                         done = haveMultiplyConfirmedCenters();\r
 163                                                                                 }\r
 164                                                                                 else\r
 165                                                                                 {\r
 166                                                                                         int rowSkip = findRowSkip();\r
 167                                                                                         if (rowSkip > stateCount[2])\r
 168                                                                                         {\r
 169                                                                                                 // Skip rows between row of lower confirmed center\r
 170                                                                                                 // and top of presumed third confirmed center\r
 171                                                                                                 // but back up a bit to get a full chance of detecting\r
 172                                                                                                 // it, entire width of center of finder pattern\r
 173                                                                                                 \r
 174                                                                                                 // Skip by rowSkip, but back off by stateCount[2] (size of last center\r
 175                                                                                                 // of pattern we saw) to be conservative, and also back off by iSkip which\r
 176                                                                                                 // is about to be re-added\r
 177                                                                                                 i += rowSkip - stateCount[2] - iSkip;\r
 178                                                                                                 j = maxJ - 1;\r
 179                                                                                         }\r
 180                                                                                 }\r
 181                                                                         }\r
 182                                                                         else\r
 183                                                                         {\r
 184                                                                                 // Advance to next black pixel\r
 185                                                                                 do \r
 186                                                                                 {\r
 187                                                                                         j++;\r
 188                                                                                 }\r
 189                                                                                 while (j < maxJ && !image.get_Renamed(j, i));\r
 190                                                                                 j--; // back up to that last white pixel\r
 191                                                                         }\r
 192                                                                         // Clear state to start looking again\r
 193                                                                         currentState = 0;\r
 194                                                                         stateCount[0] = 0;\r
 195                                                                         stateCount[1] = 0;\r
 196                                                                         stateCount[2] = 0;\r
 197                                                                         stateCount[3] = 0;\r
 198                                                                         stateCount[4] = 0;\r
 199                                                                 }\r
 200                                                                 else\r
 201                                                                 {\r
 202                                                                         // No, shift counts back by two\r
 203                                                                         stateCount[0] = stateCount[2];\r
 204                                                                         stateCount[1] = stateCount[3];\r
 205                                                                         stateCount[2] = stateCount[4];\r
 206                                                                         stateCount[3] = 1;\r
 207                                                                         stateCount[4] = 0;\r
 208                                                                         currentState = 3;\r
 209                                                                 }\r
 210                                                         }\r
 211                                                         else\r
 212                                                         {\r
 213                                                                 stateCount[++currentState]++;\r
 214                                                         }\r
 215                                                 }\r
 216                                                 else\r
 217                                                 {\r
 218                                                         // Counting white pixels\r
 219                                                         stateCount[currentState]++;\r
 220                                                 }\r
 221                                         }\r
 222                                 }\r
 223                                 if (foundPatternCross(stateCount))\r
 224                                 {\r
 225                                         bool confirmed = handlePossibleCenter(stateCount, i, maxJ);\r
 226                                         if (confirmed)\r
 227                                         {\r
 228                                                 iSkip = stateCount[0];\r
 229                                                 if (hasSkipped)\r
 230                                                 {\r
 231                                                         // Found a third one\r
 232                                                         done = haveMultiplyConfirmedCenters();\r
 233                                                 }\r
 234                                         }\r
 235                                 }\r
 236                         }\r
 237                         \r
 238                         FinderPattern[] patternInfo = selectBestPatterns();\r
 239                         ResultPoint.orderBestPatterns(patternInfo);\r
 240                         \r
 241                         return new FinderPatternInfo(patternInfo);\r
 242                 }\r
 243                 \r
 244                 /// <summary> Given a count of black/white/black/white/black pixels just seen and an end position,\r
 245                 /// figures the location of the center of this run.\r
 246                 /// </summary>\r
 247                 private static float centerFromEnd(int[] stateCount, int end)\r
 248                 {\r
 249                         //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
 250                         return (float) (end - stateCount[4] - stateCount[3]) - stateCount[2] / 2.0f;\r
 251                 }\r
 252                 \r
 253                 /// <param name="stateCount">count of black/white/black/white/black pixels just read\r
 254                 /// </param>\r
 255                 /// <returns> true iff the proportions of the counts is close enough to the 1/1/3/1/1 ratios\r
 256                 /// used by finder patterns to be considered a match\r
 257                 /// </returns>\r
 258                 protected internal static bool foundPatternCross(int[] stateCount)\r
 259                 {\r
 260                         int totalModuleSize = 0;\r
 261                         for (int i = 0; i < 5; i++)\r
 262                         {\r
 263                                 int count = stateCount[i];\r
 264                                 if (count == 0)\r
 265                                 {\r
 266                                         return false;\r
 267                                 }\r
 268                                 totalModuleSize += count;\r
 269                         }\r
 270                         if (totalModuleSize < 7)\r
 271                         {\r
 272                                 return false;\r
 273                         }\r
 274                         int moduleSize = (totalModuleSize << INTEGER_MATH_SHIFT) / 7;\r
 275                         int maxVariance = moduleSize / 2;\r
 276                         // Allow less than 50% variance from 1-1-3-1-1 proportions\r
 277                         return System.Math.Abs(moduleSize - (stateCount[0] << INTEGER_MATH_SHIFT)) < maxVariance && System.Math.Abs(moduleSize - (stateCount[1] << INTEGER_MATH_SHIFT)) < maxVariance && System.Math.Abs(3 * moduleSize - (stateCount[2] << INTEGER_MATH_SHIFT)) < 3 * maxVariance && System.Math.Abs(moduleSize - (stateCount[3] << INTEGER_MATH_SHIFT)) < maxVariance && System.Math.Abs(moduleSize - (stateCount[4] << INTEGER_MATH_SHIFT)) < maxVariance;\r
 278                 }\r
 279                 \r
 280                 /// <summary> <p>After a horizontal scan finds a potential finder pattern, this method\r
 281                 /// "cross-checks" by scanning down vertically through the center of the possible\r
 282                 /// finder pattern to see if the same proportion is detected.</p>\r
 283                 /// \r
 284                 /// </summary>\r
 285                 /// <param name="startI">row where a finder pattern was detected\r
 286                 /// </param>\r
 287                 /// <param name="centerJ">center of the section that appears to cross a finder pattern\r
 288                 /// </param>\r
 289                 /// <param name="maxCount">maximum reasonable number of modules that should be\r
 290                 /// observed in any reading state, based on the results of the horizontal scan\r
 291                 /// </param>\r
 292                 /// <returns> vertical center of finder pattern, or {@link Float#NaN} if not found\r
 293                 /// </returns>\r
 294                 private float crossCheckVertical(int startI, int centerJ, int maxCount, int originalStateCountTotal)\r
 295                 {\r
 296                         BitMatrix image = this.image;\r
 297                         \r
 298                         int maxI = image.Height;\r
 299                         int[] stateCount = CrossCheckStateCount;\r
 300                         \r
 301                         // Start counting up from center\r
 302                         int i = startI;\r
 303                         while (i >= 0 && image.get_Renamed(centerJ, i))\r
 304                         {\r
 305                                 stateCount[2]++;\r
 306                                 i--;\r
 307                         }\r
 308                         if (i < 0)\r
 309                         {\r
 310                                 return System.Single.NaN;\r
 311                         }\r
 312                         while (i >= 0 && !image.get_Renamed(centerJ, i) && stateCount[1] <= maxCount)\r
 313                         {\r
 314                                 stateCount[1]++;\r
 315                                 i--;\r
 316                         }\r
 317                         // If already too many modules in this state or ran off the edge:\r
 318                         if (i < 0 || stateCount[1] > maxCount)\r
 319                         {\r
 320                                 return System.Single.NaN;\r
 321                         }\r
 322                         while (i >= 0 && image.get_Renamed(centerJ, i) && stateCount[0] <= maxCount)\r
 323                         {\r
 324                                 stateCount[0]++;\r
 325                                 i--;\r
 326                         }\r
 327                         if (stateCount[0] > maxCount)\r
 328                         {\r
 329                                 return System.Single.NaN;\r
 330                         }\r
 331                         \r
 332                         // Now also count down from center\r
 333                         i = startI + 1;\r
 334                         while (i < maxI && image.get_Renamed(centerJ, i))\r
 335                         {\r
 336                                 stateCount[2]++;\r
 337                                 i++;\r
 338                         }\r
 339                         if (i == maxI)\r
 340                         {\r
 341                                 return System.Single.NaN;\r
 342                         }\r
 343                         while (i < maxI && !image.get_Renamed(centerJ, i) && stateCount[3] < maxCount)\r
 344                         {\r
 345                                 stateCount[3]++;\r
 346                                 i++;\r
 347                         }\r
 348                         if (i == maxI || stateCount[3] >= maxCount)\r
 349                         {\r
 350                                 return System.Single.NaN;\r
 351                         }\r
 352                         while (i < maxI && image.get_Renamed(centerJ, i) && stateCount[4] < maxCount)\r
 353                         {\r
 354                                 stateCount[4]++;\r
 355                                 i++;\r
 356                         }\r
 357                         if (stateCount[4] >= maxCount)\r
 358                         {\r
 359                                 return System.Single.NaN;\r
 360                         }\r
 361                         \r
 362                         // If we found a finder-pattern-like section, but its size is more than 40% different than\r
 363                         // the original, assume it's a false positive\r
 364                         int stateCountTotal = stateCount[0] + stateCount[1] + stateCount[2] + stateCount[3] + stateCount[4];\r
 365                         if (5 * System.Math.Abs(stateCountTotal - originalStateCountTotal) >= 2 * originalStateCountTotal)\r
 366                         {\r
 367                                 return System.Single.NaN;\r
 368                         }\r
 369                         \r
 370                         return foundPatternCross(stateCount)?centerFromEnd(stateCount, i):System.Single.NaN;\r
 371                 }\r
 372                 \r
 373                 /// <summary> <p>Like {@link #crossCheckVertical(int, int, int, int)}, and in fact is basically identical,\r
 374                 /// except it reads horizontally instead of vertically. This is used to cross-cross\r
 375                 /// check a vertical cross check and locate the real center of the alignment pattern.</p>\r
 376                 /// </summary>\r
 377                 private float crossCheckHorizontal(int startJ, int centerI, int maxCount, int originalStateCountTotal)\r
 378                 {\r
 379                         BitMatrix image = this.image;\r
 380                         \r
 381                         int maxJ = image.Width;\r
 382                         int[] stateCount = CrossCheckStateCount;\r
 383                         \r
 384                         int j = startJ;\r
 385                         while (j >= 0 && image.get_Renamed(j, centerI))\r
 386                         {\r
 387                                 stateCount[2]++;\r
 388                                 j--;\r
 389                         }\r
 390                         if (j < 0)\r
 391                         {\r
 392                                 return System.Single.NaN;\r
 393                         }\r
 394                         while (j >= 0 && !image.get_Renamed(j, centerI) && stateCount[1] <= maxCount)\r
 395                         {\r
 396                                 stateCount[1]++;\r
 397                                 j--;\r
 398                         }\r
 399                         if (j < 0 || stateCount[1] > maxCount)\r
 400                         {\r
 401                                 return System.Single.NaN;\r
 402                         }\r
 403                         while (j >= 0 && image.get_Renamed(j, centerI) && stateCount[0] <= maxCount)\r
 404                         {\r
 405                                 stateCount[0]++;\r
 406                                 j--;\r
 407                         }\r
 408                         if (stateCount[0] > maxCount)\r
 409                         {\r
 410                                 return System.Single.NaN;\r
 411                         }\r
 412                         \r
 413                         j = startJ + 1;\r
 414                         while (j < maxJ && image.get_Renamed(j, centerI))\r
 415                         {\r
 416                                 stateCount[2]++;\r
 417                                 j++;\r
 418                         }\r
 419                         if (j == maxJ)\r
 420                         {\r
 421                                 return System.Single.NaN;\r
 422                         }\r
 423                         while (j < maxJ && !image.get_Renamed(j, centerI) && stateCount[3] < maxCount)\r
 424                         {\r
 425                                 stateCount[3]++;\r
 426                                 j++;\r
 427                         }\r
 428                         if (j == maxJ || stateCount[3] >= maxCount)\r
 429                         {\r
 430                                 return System.Single.NaN;\r
 431                         }\r
 432                         while (j < maxJ && image.get_Renamed(j, centerI) && stateCount[4] < maxCount)\r
 433                         {\r
 434                                 stateCount[4]++;\r
 435                                 j++;\r
 436                         }\r
 437                         if (stateCount[4] >= maxCount)\r
 438                         {\r
 439                                 return System.Single.NaN;\r
 440                         }\r
 441                         \r
 442                         // If we found a finder-pattern-like section, but its size is significantly different than\r
 443                         // the original, assume it's a false positive\r
 444                         int stateCountTotal = stateCount[0] + stateCount[1] + stateCount[2] + stateCount[3] + stateCount[4];\r
 445                         if (5 * System.Math.Abs(stateCountTotal - originalStateCountTotal) >= originalStateCountTotal)\r
 446                         {\r
 447                                 return System.Single.NaN;\r
 448                         }\r
 449                         \r
 450                         return foundPatternCross(stateCount)?centerFromEnd(stateCount, j):System.Single.NaN;\r
 451                 }\r
 452                 \r
 453                 /// <summary> <p>This is called when a horizontal scan finds a possible alignment pattern. It will\r
 454                 /// cross check with a vertical scan, and if successful, will, ah, cross-cross-check\r
 455                 /// with another horizontal scan. This is needed primarily to locate the real horizontal\r
 456                 /// center of the pattern in cases of extreme skew.</p>\r
 457                 /// \r
 458                 /// <p>If that succeeds the finder pattern location is added to a list that tracks\r
 459                 /// the number of times each location has been nearly-matched as a finder pattern.\r
 460                 /// Each additional find is more evidence that the location is in fact a finder\r
 461                 /// pattern center\r
 462                 /// \r
 463                 /// </summary>\r
 464                 /// <param name="stateCount">reading state module counts from horizontal scan\r
 465                 /// </param>\r
 466                 /// <param name="i">row where finder pattern may be found\r
 467                 /// </param>\r
 468                 /// <param name="j">end of possible finder pattern in row\r
 469                 /// </param>\r
 470                 /// <returns> true if a finder pattern candidate was found this time\r
 471                 /// </returns>\r
 472                 protected internal virtual bool handlePossibleCenter(int[] stateCount, int i, int j)\r
 473                 {\r
 474                         int stateCountTotal = stateCount[0] + stateCount[1] + stateCount[2] + stateCount[3] + stateCount[4];\r
 475                         float centerJ = centerFromEnd(stateCount, j);\r
 476                         //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
 477                         float centerI = crossCheckVertical(i, (int) centerJ, stateCount[2], stateCountTotal);\r
 478                         if (!System.Single.IsNaN(centerI))\r
 479                         {\r
 480                                 // Re-cross check\r
 481                                 //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
 482                                 centerJ = crossCheckHorizontal((int) centerJ, (int) centerI, stateCount[2], stateCountTotal);\r
 483                                 if (!System.Single.IsNaN(centerJ))\r
 484                                 {\r
 485                                         //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
 486                                         float estimatedModuleSize = (float) stateCountTotal / 7.0f;\r
 487                                         bool found = false;\r
 488                                         int max = possibleCenters.Count;\r
 489                                         for (int index = 0; index < max; index++)\r
 490                                         {\r
 491                                                 FinderPattern center = (FinderPattern) possibleCenters[index];\r
 492                                                 // Look for about the same center and module size:\r
 493                                                 if (center.aboutEquals(estimatedModuleSize, centerI, centerJ))\r
 494                                                 {\r
 495                                                         center.incrementCount();\r
 496                                                         found = true;\r
 497                                                         break;\r
 498                                                 }\r
 499                                         }\r
 500                                         if (!found)\r
 501                                         {\r
 502                                                 ResultPoint point = new FinderPattern(centerJ, centerI, estimatedModuleSize);\r
 503                                                 possibleCenters.Add(point);\r
 504                                                 if (resultPointCallback != null)\r
 505                                                 {\r
 506                                                         resultPointCallback.foundPossibleResultPoint(point);\r
 507                                                 }\r
 508                                         }\r
 509                                         return true;\r
 510                                 }\r
 511                         }\r
 512                         return false;\r
 513                 }\r
 514                 \r
 515                 /// <returns> number of rows we could safely skip during scanning, based on the first\r
 516                 /// two finder patterns that have been located. In some cases their position will\r
 517                 /// allow us to infer that the third pattern must lie below a certain point farther\r
 518                 /// down in the image.\r
 519                 /// </returns>\r
 520                 private int findRowSkip()\r
 521                 {\r
 522                         int max = possibleCenters.Count;\r
 523                         if (max <= 1)\r
 524                         {\r
 525                                 return 0;\r
 526                         }\r
 527                         FinderPattern firstConfirmedCenter = null;\r
 528                         for (int i = 0; i < max; i++)\r
 529                         {\r
 530                                 FinderPattern center = (FinderPattern) possibleCenters[i];\r
 531                                 if (center.Count >= CENTER_QUORUM)\r
 532                                 {\r
 533                                         if (firstConfirmedCenter == null)\r
 534                                         {\r
 535                                                 firstConfirmedCenter = center;\r
 536                                         }\r
 537                                         else\r
 538                                         {\r
 539                                                 // We have two confirmed centers\r
 540                                                 // How far down can we skip before resuming looking for the next\r
 541                                                 // pattern? In the worst case, only the difference between the\r
 542                                                 // difference in the x / y coordinates of the two centers.\r
 543                                                 // This is the case where you find top left last.\r
 544                                                 hasSkipped = true;\r
 545                                                 //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
 546                                                 return (int) (System.Math.Abs(firstConfirmedCenter.X - center.X) - System.Math.Abs(firstConfirmedCenter.Y - center.Y)) / 2;\r
 547                                         }\r
 548                                 }\r
 549                         }\r
 550                         return 0;\r
 551                 }\r
 552                 \r
 553                 /// <returns> true iff we have found at least 3 finder patterns that have been detected\r
 554                 /// at least {@link #CENTER_QUORUM} times each, and, the estimated module size of the\r
 555                 /// candidates is "pretty similar"\r
 556                 /// </returns>\r
 557                 private bool haveMultiplyConfirmedCenters()\r
 558                 {\r
 559                         int confirmedCount = 0;\r
 560                         float totalModuleSize = 0.0f;\r
 561                         int max = possibleCenters.Count;\r
 562                         for (int i = 0; i < max; i++)\r
 563                         {\r
 564                                 FinderPattern pattern = (FinderPattern) possibleCenters[i];\r
 565                                 if (pattern.Count >= CENTER_QUORUM)\r
 566                                 {\r
 567                                         confirmedCount++;\r
 568                                         totalModuleSize += pattern.EstimatedModuleSize;\r
 569                                 }\r
 570                         }\r
 571                         if (confirmedCount < 3)\r
 572                         {\r
 573                                 return false;\r
 574                         }\r
 575                         // OK, we have at least 3 confirmed centers, but, it's possible that one is a "false positive"\r
 576                         // and that we need to keep looking. We detect this by asking if the estimated module sizes\r
 577                         // vary too much. We arbitrarily say that when the total deviation from average exceeds\r
 578                         // 5% of the total module size estimates, it's too much.\r
 579                         //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
 580                         float average = totalModuleSize / (float) max;\r
 581                         float totalDeviation = 0.0f;\r
 582                         for (int i = 0; i < max; i++)\r
 583                         {\r
 584                                 FinderPattern pattern = (FinderPattern) possibleCenters[i];\r
 585                                 totalDeviation += System.Math.Abs(pattern.EstimatedModuleSize - average);\r
 586                         }\r
 587                         return totalDeviation <= 0.05f * totalModuleSize;\r
 588                 }\r
 589                 \r
 590                 /// <returns> the 3 best {@link FinderPattern}s from our list of candidates. The "best" are\r
 591                 /// those that have been detected at least {@link #CENTER_QUORUM} times, and whose module\r
 592                 /// size differs from the average among those patterns the least\r
 593                 /// </returns>\r
 594                 /// <throws>  ReaderException if 3 such finder patterns do not exist </throws>\r
 595                 private FinderPattern[] selectBestPatterns()\r
 596                 {\r
 597                         \r
 598                         int startSize = possibleCenters.Count;\r
 599                         if (startSize < 3)\r
 600                         {\r
 601                                 // Couldn't find enough finder patterns\r
 602                                 throw ReaderException.Instance;\r
 603                         }\r
 604                         \r
 605                         // Filter outlier possibilities whose module size is too different\r
 606                         if (startSize > 3)\r
 607                         {\r
 608                                 // But we can only afford to do so if we have at least 4 possibilities to choose from\r
 609                                 float totalModuleSize = 0.0f;\r
 610                                 for (int i = 0; i < startSize; i++)\r
 611                                 {\r
 612                                         totalModuleSize += ((FinderPattern) possibleCenters[i]).EstimatedModuleSize;\r
 613                                 }\r
 614                                 //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
 615                                 float average = totalModuleSize / (float) startSize;\r
 616                                 for (int i = 0; i < possibleCenters.Count && possibleCenters.Count > 3; i++)\r
 617                                 {\r
 618                                         FinderPattern pattern = (FinderPattern) possibleCenters[i];\r
 619                                         if (System.Math.Abs(pattern.EstimatedModuleSize - average) > 0.2f * average)\r
 620                                         {\r
 621                                                 possibleCenters.RemoveAt(i);\r
 622                                                 i--;\r
 623                                         }\r
 624                                 }\r
 625                         }\r
 626                         \r
 627                         if (possibleCenters.Count > 3)\r
 628                         {\r
 629                                 // Throw away all but those first size candidate points we found.\r
 630                                 Collections.insertionSort(possibleCenters, new CenterComparator());\r
 631                                 SupportClass.SetCapacity(possibleCenters, 3);\r
 632                         }\r
 633                         \r
 634                         return new FinderPattern[]{(FinderPattern) possibleCenters[0], (FinderPattern) possibleCenters[1], (FinderPattern) possibleCenters[2]};\r
 635                 }\r
 636                 \r
 637                 /// <summary> <p>Orders by {@link FinderPattern#getCount()}, descending.</p></summary>\r
 638                 private class CenterComparator : Comparator\r
 639                 {\r
 640                         public virtual int compare(System.Object center1, System.Object center2)\r
 641                         {\r
 642                                 return ((FinderPattern) center2).Count - ((FinderPattern) center1).Count;\r
 643                         }\r
 644                 }\r
 645         }\r
 646 }