--- /dev/null
+/*\r
+ * Copyright 2008 ZXing authors\r
+ *\r
+ * Licensed under the Apache License, Version 2.0 (the "License");\r
+ * you may not use this file except in compliance with the License.\r
+ * You may obtain a copy of the License at\r
+ *\r
+ * http://www.apache.org/licenses/LICENSE-2.0\r
+ *\r
+ * Unless required by applicable law or agreed to in writing, software\r
+ * distributed under the License is distributed on an "AS IS" BASIS,\r
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.\r
+ * See the License for the specific language governing permissions and\r
+ * limitations under the License.\r
+ */\r
+using System;\r
+using System.Collections.Generic;\r
+using System.Linq;\r
+using System.Text;\r
+using com.google.zxing;\r
+using com.google.zxing.common; \r
+\r
+namespace com.google.zxing.datamatrix.detector\r
+{\r
+ /**\r
+ * <p>Encapsulates logic that can detect a Data Matrix Code in an image, even if the Data Matrix Code\r
+ * is rotated or skewed, or partially obscured.</p>\r
+ *\r
+ * @author Sean Owen\r
+ */\r
+ public sealed class Detector\r
+ {\r
+ private static int MAX_MODULES = 32;\r
+\r
+ // Trick to avoid creating new int objects below -- a sort of crude copy of\r
+ // the int.valueOf(int) optimization added in Java 5, not in J2ME\r
+ private static int[] intS =\r
+ {0, 1, 2, 3, 4};\r
+\r
+ private MonochromeBitmapSource image;\r
+\r
+ public Detector(MonochromeBitmapSource image) {\r
+ this.image = image;\r
+ }\r
+\r
+ /**\r
+ * <p>Detects a Data Matrix Code in an image.</p>\r
+ *\r
+ * @return {@link DetectorResult} encapsulating results of detecting a QR Code\r
+ * @throws ReaderException if no Data Matrix Code can be found\r
+ */\r
+ public DetectorResult detect() {\r
+\r
+ if (!BlackPointEstimationMethod.TWO_D_SAMPLING.Equals(image.getLastEstimationMethod())) {\r
+ image.estimateBlackPoint(BlackPointEstimationMethod.TWO_D_SAMPLING, 0);\r
+ }\r
+\r
+ int height = image.getHeight();\r
+ int width = image.getWidth();\r
+ int halfHeight = height >> 1;\r
+ int halfWidth = width >> 1;\r
+ int iSkip = Math.Max(1, height / (MAX_MODULES << 3));\r
+ int jSkip = Math.Max(1, width / (MAX_MODULES << 3));\r
+\r
+ int minI = 0;\r
+ int maxI = height;\r
+ int minJ = 0;\r
+ int maxJ = width;\r
+ ResultPoint pointA = findCornerFromCenter(halfHeight, -iSkip, minI, maxI, halfWidth, 0, minJ, maxJ, halfWidth >> 1);\r
+ minI = (int) pointA.getY() - 1;\r
+ ResultPoint pointB = findCornerFromCenter(halfHeight, 0, minI, maxI, halfWidth, -jSkip, minJ, maxJ, halfHeight >> 1);\r
+ minJ = (int) pointB.getX() - 1;\r
+ ResultPoint pointC = findCornerFromCenter(halfHeight, 0, minI, maxI, halfWidth, jSkip, minJ, maxJ, halfHeight >> 1);\r
+ maxJ = (int) pointC.getX() + 1;\r
+ ResultPoint pointD = findCornerFromCenter(halfHeight, iSkip, minI, maxI, halfWidth, 0, minJ, maxJ, halfWidth >> 1);\r
+ maxI = (int) pointD.getY() + 1;\r
+ // Go try to find point A again with better information -- might have been off at first.\r
+ pointA = findCornerFromCenter(halfHeight, -iSkip, minI, maxI, halfWidth, 0, minJ, maxJ, halfWidth >> 2);\r
+\r
+ // Point A and D are across the diagonal from one another,\r
+ // as are B and C. Figure out which are the solid black lines\r
+ // by counting transitions\r
+ System.Collections.ArrayList transitions = new System.Collections.ArrayList(4);\r
+ transitions.Add(transitionsBetween(pointA, pointB));\r
+ transitions.Add(transitionsBetween(pointA, pointC));\r
+ transitions.Add(transitionsBetween(pointB, pointD));\r
+ transitions.Add(transitionsBetween(pointC, pointD));\r
+ Collections.insertionSort(transitions, new ResultPointsAndTransitionsComparator());\r
+\r
+ // Sort by number of transitions. First two will be the two solid sides; last two\r
+ // will be the two alternating black/white sides\r
+ ResultPointsAndTransitions lSideOne = (ResultPointsAndTransitions) transitions[0];\r
+ ResultPointsAndTransitions lSideTwo = (ResultPointsAndTransitions) transitions[1];\r
+\r
+ // Figure out which point is their intersection by tallying up the number of times we see the\r
+ // endpoints in the four endpoints. One will show up twice.\r
+ System.Collections.Hashtable pointCount = new System.Collections.Hashtable();\r
+ increment(pointCount, lSideOne.getFrom());\r
+ increment(pointCount, lSideOne.getTo());\r
+ increment(pointCount, lSideTwo.getFrom());\r
+ increment(pointCount, lSideTwo.getTo());\r
+\r
+ ResultPoint maybeTopLeft = null;\r
+ ResultPoint bottomLeft = null;\r
+ ResultPoint maybeBottomRight = null;\r
+ System.Collections.IEnumerator points = pointCount.GetEnumerator();\r
+\r
+ while (points.MoveNext()) {\r
+ ResultPoint point = (ResultPoint) points.Current;\r
+ int value = (int) pointCount[point];\r
+ if (value == 2) {\r
+ bottomLeft = point; // this is definitely the bottom left, then -- end of two L sides\r
+ } else {\r
+ // Otherwise it's either top left or bottom right -- just assign the two arbitrarily now\r
+ if (maybeTopLeft == null) {\r
+ maybeTopLeft = point;\r
+ } else {\r
+ maybeBottomRight = point;\r
+ }\r
+ }\r
+ }\r
+\r
+ if (maybeTopLeft == null || bottomLeft == null || maybeBottomRight == null) {\r
+ throw new ReaderException();\r
+ }\r
+\r
+ // Bottom left is correct but top left and bottom right might be switched\r
+ ResultPoint[] corners = { maybeTopLeft, bottomLeft, maybeBottomRight };\r
+ // Use the dot product trick to sort them out\r
+ GenericResultPoint.orderBestPatterns(corners);\r
+\r
+ // Now we know which is which:\r
+ ResultPoint bottomRight = corners[0];\r
+ bottomLeft = corners[1];\r
+ ResultPoint topLeft = corners[2];\r
+\r
+ // Which point didn't we find in relation to the "L" sides? that's the top right corner\r
+ ResultPoint topRight;\r
+ if (!pointCount.ContainsKey(pointA)) {\r
+ topRight = pointA;\r
+ } else if (!pointCount.ContainsKey(pointB)) {\r
+ topRight = pointB;\r
+ } else if (!pointCount.ContainsKey(pointC)) {\r
+ topRight = pointC;\r
+ } else {\r
+ topRight = pointD;\r
+ }\r
+\r
+ // Next determine the dimension by tracing along the top or right side and counting black/white\r
+ // transitions. Since we start inside a black module, we should see a number of transitions\r
+ // equal to 1 less than the code dimension. Well, actually 2 less, because we are going to\r
+ // end on a black module:\r
+\r
+ // The top right point is actually the corner of a module, which is one of the two black modules\r
+ // adjacent to the white module at the top right. Tracing to that corner from either the top left\r
+ // or bottom right should work here, but, one will be more reliable since it's traced straight\r
+ // up or across, rather than at a slight angle. We use dot products to figure out which is\r
+ // better to use:\r
+ int dimension;\r
+ if (GenericResultPoint.crossProductZ(bottomLeft, bottomRight, topRight) <\r
+ GenericResultPoint.crossProductZ(topRight, topLeft, bottomLeft)) {\r
+ dimension = transitionsBetween(topLeft, topRight).getTransitions();\r
+ } else {\r
+ dimension = transitionsBetween(bottomRight, topRight).getTransitions();\r
+ }\r
+ dimension += 2;\r
+\r
+ BitMatrix bits = sampleGrid(image, topLeft, bottomLeft, bottomRight, dimension);\r
+ return new DetectorResult(bits, new ResultPoint[] {pointA, pointB, pointC, pointD});\r
+ }\r
+\r
+ /**\r
+ * Attempts to locate a corner of the barcode by scanning up, down, left or right from a center\r
+ * point which should be within the barcode.\r
+ *\r
+ * @param centerI center's i componennt (vertical)\r
+ * @param di change in i per step. If scanning up this is negative; down, positive; left or right, 0\r
+ * @param minI minimum value of i to search through (meaningless when di == 0)\r
+ * @param maxI maximum value of i\r
+ * @param centerJ center's j component (horizontal)\r
+ * @param dj same as di but change in j per step instead\r
+ * @param minJ see minI\r
+ * @param maxJ see minJ\r
+ * @param maxWhiteRun maximum run of white pixels that can still be considered to be within\r
+ * the barcode\r
+ * @return a {@link ResultPoint} encapsulating the corner that was found\r
+ * @throws ReaderException if such a point cannot be found\r
+ */\r
+ private ResultPoint findCornerFromCenter(int centerI, int di, int minI, int maxI,\r
+ int centerJ, int dj, int minJ, int maxJ,\r
+ int maxWhiteRun) {\r
+ int[] lastRange = null;\r
+ for (int i = centerI, j = centerJ;\r
+ i < maxI && i >= minI && j < maxJ && j >= minJ;\r
+ i += di, j += dj) {\r
+ int[] range;\r
+ if (dj == 0) {\r
+ // horizontal slices, up and down\r
+ range = blackWhiteRange(i, maxWhiteRun, minJ, maxJ, true);\r
+ } else {\r
+ // vertical slices, left and right\r
+ range = blackWhiteRange(j, maxWhiteRun, minI, maxI, false);\r
+ }\r
+ if (range == null) {\r
+ if (lastRange == null) {\r
+ throw new ReaderException();\r
+ }\r
+ // lastRange was found\r
+ if (dj == 0) {\r
+ int lastI = i - di;\r
+ if (lastRange[0] < centerJ) {\r
+ if (lastRange[1] > centerJ) {\r
+ // straddle, choose one or the other based on direction\r
+ return new GenericResultPoint(di > 0 ? lastRange[0] : lastRange[1], lastI);\r
+ }\r
+ return new GenericResultPoint(lastRange[0], lastI);\r
+ } else {\r
+ return new GenericResultPoint(lastRange[1], lastI);\r
+ }\r
+ } else {\r
+ int lastJ = j - dj;\r
+ if (lastRange[0] < centerI) {\r
+ if (lastRange[1] > centerI) {\r
+ return new GenericResultPoint(lastJ, dj < 0 ? lastRange[0] : lastRange[1]);\r
+ }\r
+ return new GenericResultPoint(lastJ, lastRange[0]);\r
+ } else {\r
+ return new GenericResultPoint(lastJ, lastRange[1]);\r
+ }\r
+ }\r
+ }\r
+ lastRange = range;\r
+ }\r
+ throw new ReaderException();\r
+ }\r
+\r
+ /**\r
+ * Increments the int associated with a key by one.\r
+ */\r
+ private static void increment(System.Collections.Hashtable table, ResultPoint key) {\r
+ int value = (int) table[key];\r
+ table[key] = value.Equals(null) ? intS[1] : intS[value + 1];\r
+ //table.put(key, value == null ? intS[1] : intS[value.intValue() + 1]);\r
+ }\r
+\r
+ /**\r
+ * Computes the start and end of a region of pixels, either horizontally or vertically, that could be\r
+ * part of a Data Matrix barcode.\r
+ *\r
+ * @param fixedDimension if scanning horizontally, this is the row (the fixed vertical location) where\r
+ * we are scanning. If scanning vertically it's the colummn, the fixed horizontal location\r
+ * @param maxWhiteRun largest run of white pixels that can still be considered part of the barcode region\r
+ * @param minDim minimum pixel location, horizontally or vertically, to consider\r
+ * @param maxDim maximum pixel location, horizontally or vertically, to consider\r
+ * @param horizontal if true, we're scanning left-right, instead of up-down\r
+ * @return int[] with start and end of found range, or null if no such range is found (e.g. only white was found)\r
+ */\r
+ private int[] blackWhiteRange(int fixedDimension, int maxWhiteRun, int minDim, int maxDim, bool horizontal) {\r
+\r
+ int center = (minDim + maxDim) / 2;\r
+\r
+ BitArray rowOrColumn = horizontal ? image.getBlackRow(fixedDimension, null, 0, image.getWidth())\r
+ : image.getBlackColumn(fixedDimension, null, 0, image.getHeight());\r
+\r
+ // Scan left/up first\r
+ int start = center;\r
+ while (start >= minDim) {\r
+ if (rowOrColumn.get(start)) {\r
+ start--;\r
+ } else {\r
+ int whiteRunStart = start;\r
+ do {\r
+ start--;\r
+ } while (start >= minDim && !rowOrColumn.get(start));\r
+ int whiteRunSize = whiteRunStart - start;\r
+ if (start < minDim || whiteRunSize > maxWhiteRun) {\r
+ start = whiteRunStart + 1; // back up\r
+ break;\r
+ }\r
+ }\r
+ }\r
+ start++;\r
+\r
+ // Then try right/down\r
+ int end = center;\r
+ while (end < maxDim) {\r
+ if (rowOrColumn.get(end)) {\r
+ end++;\r
+ } else {\r
+ int whiteRunStart = end;\r
+ do {\r
+ end++;\r
+ } while (end < maxDim && !rowOrColumn.get(end));\r
+ int whiteRunSize = end - whiteRunStart;\r
+ if (end >= maxDim || whiteRunSize > maxWhiteRun) {\r
+ end = whiteRunStart - 1;\r
+ break;\r
+ }\r
+ }\r
+ }\r
+ end--;\r
+\r
+ if (end > start) {\r
+ return new int[] { start, end };\r
+ } else {\r
+ return null;\r
+ }\r
+ }\r
+\r
+ private static BitMatrix sampleGrid(MonochromeBitmapSource image,\r
+ ResultPoint topLeft,\r
+ ResultPoint bottomLeft,\r
+ ResultPoint bottomRight,\r
+ int dimension) {\r
+\r
+ // We make up the top right point for now, based on the others.\r
+ // TODO: we actually found a fourth corner above and figured out which of two modules\r
+ // it was the corner of. We could use that here and adjust for perspective distortion.\r
+ float topRightX = (bottomRight.getX() - bottomLeft.getX()) + topLeft.getX();\r
+ float topRightY = (bottomRight.getY() - bottomLeft.getY()) + topLeft.getY();\r
+\r
+ // Note that unlike in the QR Code sampler, we didn't find the center of modules, but the\r
+ // very corners. So there is no 0.5f here; 0.0f is right.\r
+ GridSampler sampler = GridSampler.Instance;\r
+ return sampler.sampleGrid(\r
+ image,\r
+ dimension,\r
+ 0.0f,\r
+ 0.0f,\r
+ dimension,\r
+ 0.0f,\r
+ dimension,\r
+ dimension,\r
+ 0.0f,\r
+ dimension,\r
+ topLeft.getX(),\r
+ topLeft.getY(),\r
+ topRightX,\r
+ topRightY,\r
+ bottomRight.getX(),\r
+ bottomRight.getY(),\r
+ bottomLeft.getX(),\r
+ bottomLeft.getY());\r
+ }\r
+\r
+ /**\r
+ * Counts the number of black/white transitions between two points, using something like Bresenham's algorithm.\r
+ */\r
+ private ResultPointsAndTransitions transitionsBetween(ResultPoint from, ResultPoint to) {\r
+ // See QR Code Detector, sizeOfBlackWhiteBlackRun()\r
+ int fromX = (int) from.getX();\r
+ int fromY = (int) from.getY();\r
+ int toX = (int) to.getX();\r
+ int toY = (int) to.getY();\r
+ bool steep = Math.Abs(toY - fromY) > Math.Abs(toX - fromX);\r
+ if (steep) {\r
+ int temp = fromX;\r
+ fromX = fromY;\r
+ fromY = temp;\r
+ temp = toX;\r
+ toX = toY;\r
+ toY = temp;\r
+ }\r
+\r
+ int dx = Math.Abs(toX - fromX);\r
+ int dy = Math.Abs(toY - fromY);\r
+ int error = -dx >> 1;\r
+ int ystep = fromY < toY ? 1 : -1;\r
+ int xstep = fromX < toX ? 1 : -1;\r
+ int transitions = 0;\r
+ bool inBlack = image.isBlack(steep ? fromY : fromX, steep ? fromX : fromY);\r
+ for (int x = fromX, y = fromY; x != toX; x += xstep) {\r
+ bool isBlack = image.isBlack(steep ? y : x, steep ? x : y);\r
+ if (isBlack == !inBlack) {\r
+ transitions++;\r
+ inBlack = isBlack;\r
+ }\r
+ error += dy;\r
+ if (error > 0) {\r
+ y += ystep;\r
+ error -= dx;\r
+ }\r
+ }\r
+ return new ResultPointsAndTransitions(from, to, transitions);\r
+ }\r
+\r
+ /**\r
+ * Simply encapsulates two points and a number of transitions between them.\r
+ */\r
+ private class ResultPointsAndTransitions {\r
+ private ResultPoint from;\r
+ private ResultPoint to;\r
+ private int transitions;\r
+\r
+ public ResultPointsAndTransitions(ResultPoint from, ResultPoint to, int transitions) {\r
+ this.from = from;\r
+ this.to = to;\r
+ this.transitions = transitions;\r
+ }\r
+\r
+ public ResultPoint getFrom() {\r
+ return from;\r
+ }\r
+ public ResultPoint getTo() {\r
+ return to;\r
+ }\r
+ public int getTransitions() {\r
+ return transitions;\r
+ }\r
+ public String toString() {\r
+ return from + "/" + to + '/' + transitions;\r
+ }\r
+ }\r
+\r
+ /**\r
+ * Orders ResultPointsAndTransitions by number of transitions, ascending.\r
+ */\r
+ private class ResultPointsAndTransitionsComparator : Comparator {\r
+ public int compare(Object o1, Object o2) {\r
+ return ((ResultPointsAndTransitions) o1).getTransitions() - ((ResultPointsAndTransitions) o2).getTransitions();\r
+ }\r
+ }\r
+ }\r
+}\r
projects / zxing.git / blobdiff