csharp/datamatrix/detector/Detector.cs

   1 /*\r
   2  * Copyright 2008 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 System.Collections.Generic;\r
  18 using System.Linq;\r
  19 using System.Text;\r
  20 using com.google.zxing;\r
  21 using com.google.zxing.common; \r
  22 \r
  23 namespace com.google.zxing.datamatrix.detector\r
  24 {\r
  25     /**\r
  26      * <p>Encapsulates logic that can detect a Data Matrix Code in an image, even if the Data Matrix Code\r
  27      * is rotated or skewed, or partially obscured.</p>\r
  28      *\r
  29      * @author Sean Owen\r
  30      */\r
  31     public sealed class Detector\r
  32     {\r
  33           private static  int MAX_MODULES = 32;\r
  34 \r
  35           // Trick to avoid creating new int objects below -- a sort of crude copy of\r
  36           // the int.valueOf(int) optimization added in Java 5, not in J2ME\r
  37           private static  int[] intS =\r
  38               {0, 1, 2, 3, 4};\r
  39 \r
  40           private  MonochromeBitmapSource image;\r
  41 \r
  42           public Detector(MonochromeBitmapSource image) {\r
  43             this.image = image;\r
  44           }\r
  45 \r
  46           /**\r
  47            * <p>Detects a Data Matrix Code in an image.</p>\r
  48            *\r
  49            * @return {@link DetectorResult} encapsulating results of detecting a QR Code\r
  50            * @throws ReaderException if no Data Matrix Code can be found\r
  51            */\r
  52           public DetectorResult detect() {\r
  53 \r
  54             if (!BlackPointEstimationMethod.TWO_D_SAMPLING.Equals(image.getLastEstimationMethod())) {\r
  55               image.estimateBlackPoint(BlackPointEstimationMethod.TWO_D_SAMPLING, 0);\r
  56             }\r
  57 \r
  58             int height = image.getHeight();\r
  59             int width = image.getWidth();\r
  60             int halfHeight = height >> 1;\r
  61             int halfWidth = width >> 1;\r
  62             int iSkip = Math.Max(1, height / (MAX_MODULES << 3));\r
  63             int jSkip = Math.Max(1, width / (MAX_MODULES << 3));\r
  64 \r
  65             int minI = 0;\r
  66             int maxI = height;\r
  67             int minJ = 0;\r
  68             int maxJ = width;\r
  69             ResultPoint pointA = findCornerFromCenter(halfHeight, -iSkip, minI, maxI, halfWidth,      0, minJ, maxJ, halfWidth >> 1);\r
  70             minI = (int) pointA.getY() - 1;\r
  71             ResultPoint pointB = findCornerFromCenter(halfHeight, 0,      minI, maxI, halfWidth, -jSkip, minJ, maxJ, halfHeight >> 1);\r
  72             minJ = (int) pointB.getX() - 1;\r
  73             ResultPoint pointC = findCornerFromCenter(halfHeight, 0,      minI, maxI, halfWidth,  jSkip, minJ, maxJ, halfHeight >> 1);\r
  74             maxJ = (int) pointC.getX() + 1;\r
  75             ResultPoint pointD = findCornerFromCenter(halfHeight,  iSkip, minI, maxI, halfWidth,      0, minJ, maxJ, halfWidth >> 1);\r
  76             maxI = (int) pointD.getY() + 1;\r
  77             // Go try to find point A again with better information -- might have been off at first.\r
  78             pointA = findCornerFromCenter(halfHeight, -iSkip, minI, maxI, halfWidth,      0, minJ, maxJ, halfWidth >> 2);\r
  79 \r
  80             // Point A and D are across the diagonal from one another,\r
  81             // as are B and C. Figure out which are the solid black lines\r
  82             // by counting transitions\r
  83             System.Collections.ArrayList transitions = new System.Collections.ArrayList(4);\r
  84             transitions.Add(transitionsBetween(pointA, pointB));\r
  85             transitions.Add(transitionsBetween(pointA, pointC));\r
  86             transitions.Add(transitionsBetween(pointB, pointD));\r
  87             transitions.Add(transitionsBetween(pointC, pointD));\r
  88             Collections.insertionSort(transitions, new ResultPointsAndTransitionsComparator());\r
  89 \r
  90             // Sort by number of transitions. First two will be the two solid sides; last two\r
  91             // will be the two alternating black/white sides\r
  92             ResultPointsAndTransitions lSideOne = (ResultPointsAndTransitions) transitions[0];\r
  93             ResultPointsAndTransitions lSideTwo = (ResultPointsAndTransitions) transitions[1];\r
  94 \r
  95             // Figure out which point is their intersection by tallying up the number of times we see the\r
  96             // endpoints in the four endpoints. One will show up twice.\r
  97             System.Collections.Hashtable pointCount = new System.Collections.Hashtable();\r
  98             increment(pointCount, lSideOne.getFrom());\r
  99             increment(pointCount, lSideOne.getTo());\r
 100             increment(pointCount, lSideTwo.getFrom());\r
 101             increment(pointCount, lSideTwo.getTo());\r
 102 \r
 103             ResultPoint maybeTopLeft = null;\r
 104             ResultPoint bottomLeft = null;\r
 105             ResultPoint maybeBottomRight = null;\r
 106             System.Collections.IEnumerator points = pointCount.GetEnumerator();\r
 107 \r
 108             while (points.MoveNext()) {\r
 109               ResultPoint point = (ResultPoint) points.Current;\r
 110               int value = (int) pointCount[point];\r
 111               if (value == 2) {\r
 112                 bottomLeft = point; // this is definitely the bottom left, then -- end of two L sides\r
 113               } else {\r
 114                 // Otherwise it's either top left or bottom right -- just assign the two arbitrarily now\r
 115                 if (maybeTopLeft == null) {\r
 116                   maybeTopLeft = point;\r
 117                 } else {\r
 118                   maybeBottomRight = point;\r
 119                 }\r
 120               }\r
 121             }\r
 122 \r
 123             if (maybeTopLeft == null || bottomLeft == null || maybeBottomRight == null) {\r
 124               throw new ReaderException();\r
 125             }\r
 126 \r
 127             // Bottom left is correct but top left and bottom right might be switched\r
 128             ResultPoint[] corners = { maybeTopLeft, bottomLeft, maybeBottomRight };\r
 129             // Use the dot product trick to sort them out\r
 130             GenericResultPoint.orderBestPatterns(corners);\r
 131 \r
 132             // Now we know which is which:\r
 133             ResultPoint bottomRight = corners[0];\r
 134             bottomLeft = corners[1];\r
 135             ResultPoint topLeft = corners[2];\r
 136 \r
 137             // Which point didn't we find in relation to the "L" sides? that's the top right corner\r
 138             ResultPoint topRight;\r
 139             if (!pointCount.ContainsKey(pointA)) {\r
 140               topRight = pointA;\r
 141             } else if (!pointCount.ContainsKey(pointB)) {\r
 142               topRight = pointB;\r
 143             } else if (!pointCount.ContainsKey(pointC)) {\r
 144               topRight = pointC;\r
 145             } else {\r
 146               topRight = pointD;\r
 147             }\r
 148 \r
 149             // Next determine the dimension by tracing along the top or right side and counting black/white\r
 150             // transitions. Since we start inside a black module, we should see a number of transitions\r
 151             // equal to 1 less than the code dimension. Well, actually 2 less, because we are going to\r
 152             // end on a black module:\r
 153 \r
 154             // The top right point is actually the corner of a module, which is one of the two black modules\r
 155             // adjacent to the white module at the top right. Tracing to that corner from either the top left\r
 156             // or bottom right should work here, but, one will be more reliable since it's traced straight\r
 157             // up or across, rather than at a slight angle. We use dot products to figure out which is\r
 158             // better to use:\r
 159             int dimension;\r
 160             if (GenericResultPoint.crossProductZ(bottomLeft, bottomRight, topRight) <\r
 161                 GenericResultPoint.crossProductZ(topRight, topLeft, bottomLeft)) {\r
 162               dimension = transitionsBetween(topLeft, topRight).getTransitions();\r
 163             } else {\r
 164               dimension = transitionsBetween(bottomRight, topRight).getTransitions();\r
 165             }\r
 166             dimension += 2;\r
 167 \r
 168             BitMatrix bits = sampleGrid(image, topLeft, bottomLeft, bottomRight, dimension);\r
 169             return new DetectorResult(bits, new ResultPoint[] {pointA, pointB, pointC, pointD});\r
 170           }\r
 171 \r
 172           /**\r
 173            * Attempts to locate a corner of the barcode by scanning up, down, left or right from a center\r
 174            * point which should be within the barcode.\r
 175            *\r
 176            * @param centerI center's i componennt (vertical)\r
 177            * @param di change in i per step. If scanning up this is negative; down, positive; left or right, 0\r
 178            * @param minI minimum value of i to search through (meaningless when di == 0)\r
 179            * @param maxI maximum value of i\r
 180            * @param centerJ center's j component (horizontal)\r
 181            * @param dj same as di but change in j per step instead\r
 182            * @param minJ see minI\r
 183            * @param maxJ see minJ\r
 184            * @param maxWhiteRun maximum run of white pixels that can still be considered to be within\r
 185            *  the barcode\r
 186            * @return a {@link ResultPoint} encapsulating the corner that was found\r
 187            * @throws ReaderException if such a point cannot be found\r
 188            */\r
 189           private ResultPoint findCornerFromCenter(int centerI, int di, int minI, int maxI,\r
 190                                                    int centerJ, int dj, int minJ, int maxJ,\r
 191                                                    int maxWhiteRun) {\r
 192             int[] lastRange = null;\r
 193             for (int i = centerI, j = centerJ;\r
 194                  i < maxI && i >= minI && j < maxJ && j >= minJ;\r
 195                  i += di, j += dj) {\r
 196               int[] range;\r
 197               if (dj == 0) {\r
 198                 // horizontal slices, up and down\r
 199                 range = blackWhiteRange(i, maxWhiteRun, minJ, maxJ, true);\r
 200               } else {\r
 201                 // vertical slices, left and right\r
 202                 range = blackWhiteRange(j, maxWhiteRun, minI, maxI, false);\r
 203               }\r
 204               if (range == null) {\r
 205                 if (lastRange == null) {\r
 206                   throw new ReaderException();\r
 207                 }\r
 208                 // lastRange was found\r
 209                 if (dj == 0) {\r
 210                   int lastI = i - di;\r
 211                   if (lastRange[0] < centerJ) {\r
 212                     if (lastRange[1] > centerJ) {\r
 213                       // straddle, choose one or the other based on direction\r
 214                       return new GenericResultPoint(di > 0 ? lastRange[0] : lastRange[1], lastI);\r
 215                     }\r
 216                     return new GenericResultPoint(lastRange[0], lastI);\r
 217                   } else {\r
 218                     return new GenericResultPoint(lastRange[1], lastI);\r
 219                   }\r
 220                 } else {\r
 221                   int lastJ = j - dj;\r
 222                   if (lastRange[0] < centerI) {\r
 223                     if (lastRange[1] > centerI) {\r
 224                       return new GenericResultPoint(lastJ, dj < 0 ? lastRange[0] : lastRange[1]);\r
 225                     }\r
 226                     return new GenericResultPoint(lastJ, lastRange[0]);\r
 227                   } else {\r
 228                     return new GenericResultPoint(lastJ, lastRange[1]);\r
 229                   }\r
 230                 }\r
 231               }\r
 232               lastRange = range;\r
 233             }\r
 234             throw new ReaderException();\r
 235           }\r
 236 \r
 237           /**\r
 238            * Increments the int associated with a key by one.\r
 239            */\r
 240           private static void increment(System.Collections.Hashtable table, ResultPoint key) {\r
 241             int value = (int) table[key];\r
 242             table[key] = value.Equals(null) ? intS[1] : intS[value + 1];\r
 243             //table.put(key, value == null ? intS[1] : intS[value.intValue() + 1]);\r
 244           }\r
 245 \r
 246           /**\r
 247            * Computes the start and end of a region of pixels, either horizontally or vertically, that could be\r
 248            * part of a Data Matrix barcode.\r
 249            *\r
 250            * @param fixedDimension if scanning horizontally, this is the row (the fixed vertical location) where\r
 251            *  we are scanning. If scanning vertically it's the colummn, the fixed horizontal location\r
 252            * @param maxWhiteRun largest run of white pixels that can still be considered part of the barcode region\r
 253            * @param minDim minimum pixel location, horizontally or vertically, to consider\r
 254            * @param maxDim maximum pixel location, horizontally or vertically, to consider\r
 255            * @param horizontal if true, we're scanning left-right, instead of up-down\r
 256            * @return int[] with start and end of found range, or null if no such range is found (e.g. only white was found)\r
 257            */\r
 258           private int[] blackWhiteRange(int fixedDimension, int maxWhiteRun, int minDim, int maxDim, bool horizontal) {\r
 259 \r
 260             int center = (minDim + maxDim) / 2;\r
 261 \r
 262             BitArray rowOrColumn = horizontal ? image.getBlackRow(fixedDimension, null, 0, image.getWidth())\r
 263                                               : image.getBlackColumn(fixedDimension, null, 0, image.getHeight());\r
 264 \r
 265             // Scan left/up first\r
 266             int start = center;\r
 267             while (start >= minDim) {\r
 268               if (rowOrColumn.get(start)) {\r
 269                 start--;\r
 270               } else {\r
 271                 int whiteRunStart = start;\r
 272                 do {\r
 273                   start--;\r
 274                 } while (start >= minDim && !rowOrColumn.get(start));\r
 275                 int whiteRunSize = whiteRunStart - start;\r
 276                 if (start < minDim || whiteRunSize > maxWhiteRun) {\r
 277                   start = whiteRunStart + 1; // back up\r
 278                   break;\r
 279                 }\r
 280               }\r
 281             }\r
 282             start++;\r
 283 \r
 284             // Then try right/down\r
 285             int end = center;\r
 286             while (end < maxDim) {\r
 287               if (rowOrColumn.get(end)) {\r
 288                 end++;\r
 289               } else {\r
 290                 int whiteRunStart = end;\r
 291                 do {\r
 292                   end++;\r
 293                 } while (end < maxDim && !rowOrColumn.get(end));\r
 294                 int whiteRunSize = end - whiteRunStart;\r
 295                 if (end >= maxDim || whiteRunSize > maxWhiteRun) {\r
 296                   end = whiteRunStart - 1;\r
 297                   break;\r
 298                 }\r
 299               }\r
 300             }\r
 301             end--;\r
 302 \r
 303             if (end > start) {\r
 304               return new int[] { start, end };\r
 305             } else {\r
 306               return null;\r
 307             }\r
 308           }\r
 309 \r
 310           private static BitMatrix sampleGrid(MonochromeBitmapSource image,\r
 311                                               ResultPoint topLeft,\r
 312                                               ResultPoint bottomLeft,\r
 313                                               ResultPoint bottomRight,\r
 314                                               int dimension) {\r
 315 \r
 316             // We make up the top right point for now, based on the others.\r
 317             // TODO: we actually found a fourth corner above and figured out which of two modules\r
 318             // it was the corner of. We could use that here and adjust for perspective distortion.\r
 319             float topRightX = (bottomRight.getX() - bottomLeft.getX()) + topLeft.getX();\r
 320             float topRightY = (bottomRight.getY() - bottomLeft.getY()) + topLeft.getY();\r
 321 \r
 322             // Note that unlike in the QR Code sampler, we didn't find the center of modules, but the\r
 323             // very corners. So there is no 0.5f here; 0.0f is right.\r
 324             GridSampler sampler = GridSampler.Instance;\r
 325             return sampler.sampleGrid(\r
 326                 image,\r
 327                 dimension,\r
 328                 0.0f,\r
 329                 0.0f,\r
 330                 dimension,\r
 331                 0.0f,\r
 332                 dimension,\r
 333                 dimension,\r
 334                 0.0f,\r
 335                 dimension,\r
 336                 topLeft.getX(),\r
 337                 topLeft.getY(),\r
 338                 topRightX,\r
 339                 topRightY,\r
 340                 bottomRight.getX(),\r
 341                 bottomRight.getY(),\r
 342                 bottomLeft.getX(),\r
 343                 bottomLeft.getY());\r
 344           }\r
 345 \r
 346           /**\r
 347            * Counts the number of black/white transitions between two points, using something like Bresenham's algorithm.\r
 348            */\r
 349           private ResultPointsAndTransitions transitionsBetween(ResultPoint from, ResultPoint to) {\r
 350             // See QR Code Detector, sizeOfBlackWhiteBlackRun()\r
 351             int fromX = (int) from.getX();\r
 352             int fromY = (int) from.getY();\r
 353             int toX = (int) to.getX();\r
 354             int toY = (int) to.getY();\r
 355             bool steep = Math.Abs(toY - fromY) > Math.Abs(toX - fromX);\r
 356             if (steep) {\r
 357               int temp = fromX;\r
 358               fromX = fromY;\r
 359               fromY = temp;\r
 360               temp = toX;\r
 361               toX = toY;\r
 362               toY = temp;\r
 363             }\r
 364 \r
 365             int dx = Math.Abs(toX - fromX);\r
 366             int dy = Math.Abs(toY - fromY);\r
 367             int error = -dx >> 1;\r
 368             int ystep = fromY < toY ? 1 : -1;\r
 369             int xstep = fromX < toX ? 1 : -1;\r
 370             int transitions = 0;\r
 371             bool inBlack = image.isBlack(steep ? fromY : fromX, steep ? fromX : fromY);\r
 372             for (int x = fromX, y = fromY; x != toX; x += xstep) {\r
 373               bool isBlack = image.isBlack(steep ? y : x, steep ? x : y);\r
 374               if (isBlack == !inBlack) {\r
 375                 transitions++;\r
 376                 inBlack = isBlack;\r
 377               }\r
 378               error += dy;\r
 379               if (error > 0) {\r
 380                 y += ystep;\r
 381                 error -= dx;\r
 382               }\r
 383             }\r
 384             return new ResultPointsAndTransitions(from, to, transitions);\r
 385           }\r
 386 \r
 387           /**\r
 388            * Simply encapsulates two points and a number of transitions between them.\r
 389            */\r
 390           private class ResultPointsAndTransitions {\r
 391             private  ResultPoint from;\r
 392             private  ResultPoint to;\r
 393             private  int transitions;\r
 394 \r
 395             public ResultPointsAndTransitions(ResultPoint from, ResultPoint to, int transitions) {\r
 396               this.from = from;\r
 397               this.to = to;\r
 398               this.transitions = transitions;\r
 399             }\r
 400 \r
 401             public ResultPoint getFrom() {\r
 402               return from;\r
 403             }\r
 404             public ResultPoint getTo() {\r
 405               return to;\r
 406             }\r
 407             public int getTransitions() {\r
 408               return transitions;\r
 409             }\r
 410             public String toString() {\r
 411               return from + "/" + to + '/' + transitions;\r
 412             }\r
 413           }\r
 414 \r
 415           /**\r
 416            * Orders ResultPointsAndTransitions by number of transitions, ascending.\r
 417            */\r
 418           private class ResultPointsAndTransitionsComparator : Comparator {\r
 419             public int compare(Object o1, Object o2) {\r
 420               return ((ResultPointsAndTransitions) o1).getTransitions() - ((ResultPointsAndTransitions) o2).getTransitions();\r
 421             }\r
 422           }\r
 423     }\r
 424 }\r