csharp/qrcode/detector/Detector.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     using Version = com.google.zxing.qrcode.decoder.Version;    \r
  23 \r
  24     public sealed class Detector\r
  25     { \r
  26           private  MonochromeBitmapSource image;\r
  27 \r
  28           public Detector(MonochromeBitmapSource image) {\r
  29             this.image = image;\r
  30           }\r
  31 \r
  32           /**\r
  33            * <p>Detects a QR Code in an image, simply.</p>\r
  34            *\r
  35            * @return {@link DetectorResult} encapsulating results of detecting a QR Code\r
  36            * @throws ReaderException if no QR Code can be found\r
  37            */\r
  38           public DetectorResult detect(){\r
  39               try{\r
  40                 return detect(null);\r
  41               }catch(Exception e){\r
  42                 throw new ReaderException(e.Message);\r
  43               }           \r
  44           }\r
  45 \r
  46           /**\r
  47            * <p>Detects a QR Code in an image, simply.</p>\r
  48            *\r
  49            * @param hints optional hints to detector\r
  50            * @return {@link DetectorResult} encapsulating results of detecting a QR Code\r
  51            * @throws ReaderException if no QR Code can be found\r
  52            */\r
  53           public DetectorResult detect(System.Collections.Hashtable hints) {\r
  54 \r
  55             MonochromeBitmapSource image = this.image;\r
  56             if (!BlackPointEstimationMethod.TWO_D_SAMPLING.Equals(image.getLastEstimationMethod())) {\r
  57               image.estimateBlackPoint(BlackPointEstimationMethod.TWO_D_SAMPLING, 0);\r
  58             }\r
  59 \r
  60             FinderPatternFinder finder = new FinderPatternFinder(image);\r
  61             FinderPatternInfo info = finder.find(hints);\r
  62 \r
  63             FinderPattern topLeft = info.getTopLeft();\r
  64             FinderPattern topRight = info.getTopRight();\r
  65             FinderPattern bottomLeft = info.getBottomLeft();\r
  66 \r
  67             float moduleSize = calculateModuleSize(topLeft, topRight, bottomLeft);\r
  68             if (moduleSize < 1.0f) {\r
  69               throw new ReaderException();\r
  70             }\r
  71             int dimension = computeDimension(topLeft, topRight, bottomLeft, moduleSize);\r
  72 \r
  73             Version provisionalVersion = Version.getProvisionalVersionForDimension(dimension);\r
  74             int modulesBetweenFPCenters = provisionalVersion.getDimensionForVersion() - 7;\r
  75 \r
  76             AlignmentPattern alignmentPattern = null;\r
  77             // Anything above version 1 has an alignment pattern\r
  78             if (provisionalVersion.getAlignmentPatternCenters().Length > 0) {\r
  79 \r
  80               // Guess where a "bottom right" finder pattern would have been\r
  81               float bottomRightX = topRight.getX() - topLeft.getX() + bottomLeft.getX();\r
  82               float bottomRightY = topRight.getY() - topLeft.getY() + bottomLeft.getY();\r
  83 \r
  84               // Estimate that alignment pattern is closer by 3 modules\r
  85               // from "bottom right" to known top left location\r
  86               float correctionToTopLeft = 1.0f - 3.0f / (float) modulesBetweenFPCenters;\r
  87               int estAlignmentX = (int) (topLeft.getX() + correctionToTopLeft * (bottomRightX - topLeft.getX()));\r
  88               int estAlignmentY = (int) (topLeft.getY() + correctionToTopLeft * (bottomRightY - topLeft.getY()));\r
  89 \r
  90               // Kind of arbitrary -- expand search radius before giving up\r
  91               for (int i = 4; i <= 16; i <<= 1) {\r
  92                 try {\r
  93                   alignmentPattern = findAlignmentInRegion(moduleSize,\r
  94                       estAlignmentX,\r
  95                       estAlignmentY,\r
  96                       (float) i);\r
  97                   break;\r
  98                 } catch (ReaderException re) {\r
  99                   // try next round\r
 100                 }\r
 101               }\r
 102               if (alignmentPattern == null) {\r
 103                 throw new ReaderException();\r
 104               }\r
 105 \r
 106             }\r
 107 \r
 108             BitMatrix bits = sampleGrid(image, topLeft, topRight, bottomLeft, alignmentPattern, dimension);\r
 109 \r
 110             ResultPoint[] points;\r
 111             if (alignmentPattern == null) {\r
 112               points = new ResultPoint[]{bottomLeft, topLeft, topRight};\r
 113             } else {\r
 114               points = new ResultPoint[]{bottomLeft, topLeft, topRight, alignmentPattern};\r
 115             }\r
 116             return new DetectorResult(bits, points);\r
 117           }\r
 118 \r
 119           private static BitMatrix sampleGrid(MonochromeBitmapSource image,\r
 120                                               ResultPoint topLeft,\r
 121                                               ResultPoint topRight,\r
 122                                               ResultPoint bottomLeft,\r
 123                                               ResultPoint alignmentPattern,\r
 124                                               int dimension) {\r
 125             float dimMinusThree = (float) dimension - 3.5f;\r
 126             float bottomRightX;\r
 127             float bottomRightY;\r
 128             float sourceBottomRightX;\r
 129             float sourceBottomRightY;\r
 130             if (alignmentPattern != null) {\r
 131               bottomRightX = alignmentPattern.getX();\r
 132               bottomRightY = alignmentPattern.getY();\r
 133               sourceBottomRightX = sourceBottomRightY = dimMinusThree - 3.0f;\r
 134             } else {\r
 135               // Don't have an alignment pattern, just make up the bottom-right point\r
 136               bottomRightX = (topRight.getX() - topLeft.getX()) + bottomLeft.getX();\r
 137               bottomRightY = (topRight.getY() - topLeft.getY()) + bottomLeft.getY();\r
 138               sourceBottomRightX = sourceBottomRightY = dimMinusThree;\r
 139             }\r
 140 \r
 141             GridSampler sampler = GridSampler.Instance;\r
 142             return sampler.sampleGrid(\r
 143                 image,\r
 144                 dimension,\r
 145                 3.5f,\r
 146                 3.5f,\r
 147                 dimMinusThree,\r
 148                 3.5f,\r
 149                 sourceBottomRightX,\r
 150                 sourceBottomRightY,\r
 151                 3.5f,\r
 152                 dimMinusThree,\r
 153                 topLeft.getX(),\r
 154                 topLeft.getY(),\r
 155                 topRight.getX(),\r
 156                 topRight.getY(),\r
 157                 bottomRightX,\r
 158                 bottomRightY,\r
 159                 bottomLeft.getX(),\r
 160                 bottomLeft.getY());\r
 161           }\r
 162 \r
 163           /**\r
 164            * <p>Computes the dimension (number of modules on a size) of the QR Code based on the position\r
 165            * of the finder patterns and estimated module size.</p>\r
 166            */\r
 167           private static int computeDimension(ResultPoint topLeft,\r
 168                                               ResultPoint topRight,\r
 169                                               ResultPoint bottomLeft,\r
 170                                               float moduleSize) {\r
 171             int tltrCentersDimension = round(GenericResultPoint.distance(topLeft, topRight) / moduleSize);\r
 172             int tlblCentersDimension = round(GenericResultPoint.distance(topLeft, bottomLeft) / moduleSize);\r
 173             int dimension = ((tltrCentersDimension + tlblCentersDimension) >> 1) + 7;\r
 174             switch (dimension & 0x03) { // mod 4\r
 175               case 0:\r
 176                 dimension++;\r
 177                 break;\r
 178                 // 1? do nothing\r
 179               case 2:\r
 180                 dimension--;\r
 181                 break;\r
 182               case 3:\r
 183                 throw new ReaderException();\r
 184             }\r
 185             return dimension;\r
 186           }\r
 187 \r
 188           /**\r
 189            * <p>Computes an average estimated module size based on estimated derived from the positions\r
 190            * of the three finder patterns.</p>\r
 191            */\r
 192           private float calculateModuleSize(ResultPoint topLeft, ResultPoint topRight, ResultPoint bottomLeft) {\r
 193             // Take the average\r
 194             return (calculateModuleSizeOneWay(topLeft, topRight) +\r
 195                 calculateModuleSizeOneWay(topLeft, bottomLeft)) / 2.0f;\r
 196           }\r
 197 \r
 198           /**\r
 199            * <p>Estimates module size based on two finder patterns -- it uses\r
 200            * {@link #sizeOfBlackWhiteBlackRunBothWays(int, int, int, int)} to figure the\r
 201            * width of each, measuring along the axis between their centers.</p>\r
 202            */\r
 203           private float calculateModuleSizeOneWay(ResultPoint pattern, ResultPoint otherPattern) {\r
 204             float moduleSizeEst1 = sizeOfBlackWhiteBlackRunBothWays((int) pattern.getX(),\r
 205                 (int) pattern.getY(),\r
 206                 (int) otherPattern.getX(),\r
 207                 (int) otherPattern.getY());\r
 208             float moduleSizeEst2 = sizeOfBlackWhiteBlackRunBothWays((int) otherPattern.getX(),\r
 209                 (int) otherPattern.getY(),\r
 210                 (int) pattern.getX(),\r
 211                 (int) pattern.getY());\r
 212             if (Single.IsNaN(moduleSizeEst1)) {\r
 213               return moduleSizeEst2;\r
 214             }\r
 215             if (Single.IsNaN(moduleSizeEst2))\r
 216             {\r
 217               return moduleSizeEst1;\r
 218             }\r
 219             // Average them, and divide by 7 since we've counted the width of 3 black modules,\r
 220             // and 1 white and 1 black module on either side. Ergo, divide sum by 14.\r
 221             return (moduleSizeEst1 + moduleSizeEst2) / 14.0f;\r
 222           }\r
 223 \r
 224           /**\r
 225            * See {@link #sizeOfBlackWhiteBlackRun(int, int, int, int)}; computes the total width of\r
 226            * a finder pattern by looking for a black-white-black run from the center in the direction\r
 227            * of another point (another finder pattern center), and in the opposite direction too.</p>\r
 228            */\r
 229           private float sizeOfBlackWhiteBlackRunBothWays(int fromX, int fromY, int toX, int toY) {\r
 230 \r
 231             float result = sizeOfBlackWhiteBlackRun(fromX, fromY, toX, toY);\r
 232 \r
 233             // Now count other way -- don't run off image though of course\r
 234             int otherToX = fromX - (toX - fromX);\r
 235             if (otherToX < 0) {\r
 236               // "to" should the be the first value not included, so, the first value off\r
 237               // the edge is -1\r
 238               otherToX = -1;\r
 239             } else if (otherToX >= image.getWidth()) {\r
 240               otherToX = image.getWidth();\r
 241             }\r
 242             int otherToY = fromY - (toY - fromY);\r
 243             if (otherToY < 0) {\r
 244               otherToY = -1;\r
 245             } else if (otherToY >= image.getHeight()) {\r
 246               otherToY = image.getHeight();\r
 247             }\r
 248             result += sizeOfBlackWhiteBlackRun(fromX, fromY, otherToX, otherToY);\r
 249             return result - 1.0f; // -1 because we counted the middle pixel twice\r
 250           }\r
 251 \r
 252           /**\r
 253            * <p>This method traces a line from a point in the image, in the direction towards another point.\r
 254            * It begins in a black region, and keeps going until it finds white, then black, then white again.\r
 255            * It reports the distance from the start to this point.</p>\r
 256            *\r
 257            * <p>This is used when figuring out how wide a finder pattern is, when the finder pattern\r
 258            * may be skewed or rotated.</p>\r
 259            */\r
 260           private float sizeOfBlackWhiteBlackRun(int fromX, int fromY, int toX, int toY) {\r
 261             // Mild variant of Bresenham's algorithm;\r
 262             // see http://en.wikipedia.org/wiki/Bresenham's_line_algorithm\r
 263             bool steep = Math.Abs(toY - fromY) > Math.Abs(toX - fromX);\r
 264             if (steep) {\r
 265               int temp = fromX;\r
 266               fromX = fromY;\r
 267               fromY = temp;\r
 268               temp = toX;\r
 269               toX = toY;\r
 270               toY = temp;\r
 271             }\r
 272 \r
 273             int dx = Math.Abs(toX - fromX);\r
 274             int dy = Math.Abs(toY - fromY);\r
 275             int error = -dx >> 1;\r
 276             int ystep = fromY < toY ? 1 : -1;\r
 277             int xstep = fromX < toX ? 1 : -1;\r
 278             int state = 0; // In black pixels, looking for white, first or second time\r
 279             int diffX =0;\r
 280             int diffY =0;\r
 281 \r
 282             for (int x = fromX, y = fromY; x != toX; x += xstep) {\r
 283 \r
 284               int realX = steep ? y : x;\r
 285               int realY = steep ? x : y;\r
 286               if (state == 1) { // In white pixels, looking for black\r
 287                 if (image.isBlack(realX, realY)) {\r
 288                   state++;\r
 289                 }\r
 290               } else {\r
 291                 if (!image.isBlack(realX, realY)) {\r
 292                   state++;\r
 293                 }\r
 294               }\r
 295 \r
 296               if (state == 3) { // Found black, white, black, and stumbled back onto white; done\r
 297                 diffX = x - fromX;\r
 298                 diffY = y - fromY;\r
 299                 return (float) Math.Sqrt((double) (diffX * diffX + diffY * diffY));\r
 300               }\r
 301               error += dy;\r
 302               if (error > 0) {\r
 303                 y += ystep;\r
 304                 error -= dx;\r
 305               }\r
 306             }\r
 307 \r
 308             diffX = toX - fromX;\r
 309             diffY = toY - fromY;\r
 310             return (float) Math.Sqrt((double) (diffX * diffX + diffY * diffY));\r
 311           }\r
 312 \r
 313           /**\r
 314            * <p>Attempts to locate an alignment pattern in a limited region of the image, which is\r
 315            * guessed to contain it. This method uses {@link AlignmentPattern}.</p>\r
 316            *\r
 317            * @param overallEstModuleSize estimated module size so far\r
 318            * @param estAlignmentX x coordinate of center of area probably containing alignment pattern\r
 319            * @param estAlignmentY y coordinate of above\r
 320            * @param allowanceFactor number of pixels in all directons to search from the center\r
 321            * @return {@link AlignmentPattern} if found, or null otherwise\r
 322            * @throws ReaderException if an unexpected error occurs during detection\r
 323            */\r
 324           private AlignmentPattern findAlignmentInRegion(float overallEstModuleSize,\r
 325                                                          int estAlignmentX,\r
 326                                                          int estAlignmentY,\r
 327                                                          float allowanceFactor){\r
 328             // Look for an alignment pattern (3 modules in size) around where it\r
 329             // should be\r
 330             int allowance = (int) (allowanceFactor * overallEstModuleSize);\r
 331             int alignmentAreaLeftX = Math.Max(0, estAlignmentX - allowance);\r
 332             int alignmentAreaRightX = Math.Min(image.getWidth() - 1, estAlignmentX + allowance);\r
 333             if (alignmentAreaRightX - alignmentAreaLeftX < overallEstModuleSize * 3) {\r
 334               throw new ReaderException();\r
 335             }\r
 336 \r
 337             int alignmentAreaTopY = Math.Max(0, estAlignmentY - allowance);\r
 338             int alignmentAreaBottomY = Math.Min(image.getHeight() - 1, estAlignmentY + allowance);\r
 339 \r
 340             AlignmentPatternFinder alignmentFinder =\r
 341                 new AlignmentPatternFinder(\r
 342                     image,\r
 343                     alignmentAreaLeftX,\r
 344                     alignmentAreaTopY,\r
 345                     alignmentAreaRightX - alignmentAreaLeftX,\r
 346                     alignmentAreaBottomY - alignmentAreaTopY,\r
 347                     overallEstModuleSize);\r
 348             return alignmentFinder.find();\r
 349           }\r
 350 \r
 351           /**\r
 352            * Ends up being a bit faster than Math.round(). This merely rounds its argument to the nearest int,\r
 353            * where x.5 rounds up.\r
 354            */\r
 355           private static int round(float d) {\r
 356             return (int) (d + 0.5f);\r
 357           }\r
 358     \r
 359     }\r
 360 \r
 361 \r
 362 }