2 * Copyright 2009 ZXing authors
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
8 * http://www.apache.org/licenses/LICENSE-2.0
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
17 package com.google.zxing.common.detector;
19 import com.google.zxing.ReaderException;
20 import com.google.zxing.ResultPoint;
21 import com.google.zxing.common.BitMatrix;
24 * <p>A somewhat generic detector that looks for a barcode-like rectangular region within an image.
25 * It looks within a mostly white region of an image for a region of black and white, but mostly
26 * black. It returns the four corners of the region, as best it can determine.</p>
30 public final class MonochromeRectangleDetector {
32 private static final int MAX_MODULES = 32;
34 private final BitMatrix image;
36 public MonochromeRectangleDetector(BitMatrix image) {
41 * <p>Detects a rectangular region of black and white -- mostly black -- with a region of mostly
42 * white, in an image.</p>
44 * @return {@link ResultPoint}[] describing the corners of the rectangular region. The first and
45 * last points are opposed on the diagonal, as are the second and third. The first point will be
46 * the topmost point and the last, the bottommost. The second point will be leftmost and the
47 * third, the rightmost
48 * @throws ReaderException if no Data Matrix Code can be found
50 public ResultPoint[] detect() throws ReaderException {
51 int height = image.getHeight();
52 int width = image.getWidth();
53 int halfHeight = height >> 1;
54 int halfWidth = width >> 1;
55 int deltaY = Math.max(1, height / (MAX_MODULES << 3));
56 int deltaX = Math.max(1, width / (MAX_MODULES << 3));
62 ResultPoint pointA = findCornerFromCenter(halfWidth, 0, left, right,
63 halfHeight, -deltaY, top, bottom, halfWidth >> 1);
64 top = (int) pointA.getY() - 1;
65 ResultPoint pointB = findCornerFromCenter(halfWidth, -deltaX, left, right,
66 halfHeight, 0, top, bottom, halfHeight >> 1);
67 left = (int) pointB.getX() - 1;
68 ResultPoint pointC = findCornerFromCenter(halfWidth, deltaX, left, right,
69 halfHeight, 0, top, bottom, halfHeight >> 1);
70 right = (int) pointC.getX() + 1;
71 ResultPoint pointD = findCornerFromCenter(halfWidth, 0, left, right,
72 halfHeight, deltaY, top, bottom, halfWidth >> 1);
73 bottom = (int) pointD.getY() + 1;
75 // Go try to find point A again with better information -- might have been off at first.
76 pointA = findCornerFromCenter(halfWidth, 0, left, right,
77 halfHeight, -deltaY, top, bottom, halfWidth >> 2);
79 return new ResultPoint[] { pointA, pointB, pointC, pointD };
83 * Attempts to locate a corner of the barcode by scanning up, down, left or right from a center
84 * point which should be within the barcode.
86 * @param centerX center's x component (horizontal)
87 * @param deltaX same as deltaY but change in x per step instead
88 * @param left minimum value of x
89 * @param right maximum value of x
90 * @param centerY center's y component (vertical)
91 * @param deltaY change in y per step. If scanning up this is negative; down, positive;
93 * @param top minimum value of y to search through (meaningless when di == 0)
94 * @param bottom maximum value of y
95 * @param maxWhiteRun maximum run of white pixels that can still be considered to be within
97 * @return a {@link com.google.zxing.ResultPoint} encapsulating the corner that was found
98 * @throws com.google.zxing.ReaderException if such a point cannot be found
100 private ResultPoint findCornerFromCenter(int centerX, int deltaX, int left, int right,
101 int centerY, int deltaY, int top, int bottom, int maxWhiteRun) throws ReaderException {
102 int[] lastRange = null;
103 for (int y = centerY, x = centerX;
104 y < bottom && y >= top && x < right && x >= left;
105 y += deltaY, x += deltaX) {
108 // horizontal slices, up and down
109 range = blackWhiteRange(y, maxWhiteRun, left, right, true);
111 // vertical slices, left and right
112 range = blackWhiteRange(x, maxWhiteRun, top, bottom, false);
115 if (lastRange == null) {
116 throw ReaderException.getInstance();
118 // lastRange was found
120 int lastY = y - deltaY;
121 if (lastRange[0] < centerX) {
122 if (lastRange[1] > centerX) {
123 // straddle, choose one or the other based on direction
124 return new ResultPoint(deltaY > 0 ? lastRange[0] : lastRange[1], lastY);
126 return new ResultPoint(lastRange[0], lastY);
128 return new ResultPoint(lastRange[1], lastY);
131 int lastX = x - deltaX;
132 if (lastRange[0] < centerY) {
133 if (lastRange[1] > centerY) {
134 return new ResultPoint(lastX, deltaX < 0 ? lastRange[0] : lastRange[1]);
136 return new ResultPoint(lastX, lastRange[0]);
138 return new ResultPoint(lastX, lastRange[1]);
144 throw ReaderException.getInstance();
148 * Computes the start and end of a region of pixels, either horizontally or vertically, that could
149 * be part of a Data Matrix barcode.
151 * @param fixedDimension if scanning horizontally, this is the row (the fixed vertical location)
152 * where we are scanning. If scanning vertically it's the column, the fixed horizontal location
153 * @param maxWhiteRun largest run of white pixels that can still be considered part of the
155 * @param minDim minimum pixel location, horizontally or vertically, to consider
156 * @param maxDim maximum pixel location, horizontally or vertically, to consider
157 * @param horizontal if true, we're scanning left-right, instead of up-down
158 * @return int[] with start and end of found range, or null if no such range is found
159 * (e.g. only white was found)
161 private int[] blackWhiteRange(int fixedDimension, int maxWhiteRun, int minDim, int maxDim,
162 boolean horizontal) {
164 int center = (minDim + maxDim) >> 1;
166 // Scan left/up first
168 while (start >= minDim) {
169 if (horizontal ? image.get(start, fixedDimension) : image.get(fixedDimension, start)) {
172 int whiteRunStart = start;
175 } while (start >= minDim && !(horizontal ? image.get(start, fixedDimension) :
176 image.get(fixedDimension, start)));
177 int whiteRunSize = whiteRunStart - start;
178 if (start < minDim || whiteRunSize > maxWhiteRun) {
179 start = whiteRunStart;
186 // Then try right/down
188 while (end < maxDim) {
189 if (horizontal ? image.get(end, fixedDimension) : image.get(fixedDimension, end)) {
192 int whiteRunStart = end;
195 } while (end < maxDim && !(horizontal ? image.get(end, fixedDimension) :
196 image.get(fixedDimension, end)));
197 int whiteRunSize = end - whiteRunStart;
198 if (end >= maxDim || whiteRunSize > maxWhiteRun) {
206 return end > start ? new int[]{start, end} : null;