+++ /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