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.BinaryBitmap;
20 import com.google.zxing.ReaderException;
21 import com.google.zxing.ResultPoint;
22 import com.google.zxing.common.BitArray;
25 * <p>A somewhat generic detector that looks for a barcode-like rectangular region within an image.
26 * It looks within a mostly white region of an image for a region of black and white, but mostly
27 * black. It returns the four corners of the region, as best it can determine.</p>
31 public final class MonochromeRectangleDetector {
33 private static final int MAX_MODULES = 32;
35 private final BinaryBitmap image;
37 public MonochromeRectangleDetector(BinaryBitmap image) {
42 * <p>Detects a rectangular region of black and white -- mostly black -- with a region of mostly
43 * white, in an image.</p>
45 * @return {@link ResultPoint}[] describing the corners of the rectangular region. The first and
46 * last points are opposed on the diagonal, as are the second and third. The first point will be
47 * the topmost point and the last, the bottommost. The second point will be leftmost and the
48 * third, the rightmost
49 * @throws ReaderException if no Data Matrix Code can be found
51 public ResultPoint[] detect() throws ReaderException {
52 int height = image.getHeight();
53 int width = image.getWidth();
54 int halfHeight = height >> 1;
55 int halfWidth = width >> 1;
56 int iSkip = Math.max(1, height / (MAX_MODULES << 3));
57 int jSkip = Math.max(1, width / (MAX_MODULES << 3));
63 ResultPoint pointA = findCornerFromCenter(halfHeight, -iSkip, minI, maxI, halfWidth, 0,
64 minJ, maxJ, halfWidth >> 1);
65 minI = (int) pointA.getY() - 1;
66 ResultPoint pointB = findCornerFromCenter(halfHeight, 0, minI, maxI, halfWidth, -jSkip,
67 minJ, maxJ, halfHeight >> 1);
68 minJ = (int) pointB.getX() - 1;
69 ResultPoint pointC = findCornerFromCenter(halfHeight, 0, minI, maxI, halfWidth, jSkip,
70 minJ, maxJ, halfHeight >> 1);
71 maxJ = (int) pointC.getX() + 1;
72 ResultPoint pointD = findCornerFromCenter(halfHeight, iSkip, minI, maxI, halfWidth, 0,
73 minJ, maxJ, halfWidth >> 1);
74 maxI = (int) pointD.getY() + 1;
75 // Go try to find point A again with better information -- might have been off at first.
76 pointA = findCornerFromCenter(halfHeight, -iSkip, minI, maxI, halfWidth, 0, minJ, maxJ,
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 centerI center's i componennt (vertical)
87 * @param di change in i per step. If scanning up this is negative; down, positive;
89 * @param minI minimum value of i to search through (meaningless when di == 0)
90 * @param maxI maximum value of i
91 * @param centerJ center's j component (horizontal)
92 * @param dj same as di but change in j per step instead
93 * @param minJ see minI
94 * @param maxJ see minJ
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 centerI, int di, int minI, int maxI,
101 int centerJ, int dj, int minJ, int maxJ,
102 int maxWhiteRun) throws ReaderException {
103 int[] lastRange = null;
104 for (int i = centerI, j = centerJ;
105 i < maxI && i >= minI && j < maxJ && j >= minJ;
109 // horizontal slices, up and down
110 range = blackWhiteRange(i, maxWhiteRun, minJ, maxJ, true);
112 // vertical slices, left and right
113 range = blackWhiteRange(j, maxWhiteRun, minI, maxI, false);
116 if (lastRange == null) {
117 throw ReaderException.getInstance();
119 // lastRange was found
122 if (lastRange[0] < centerJ) {
123 if (lastRange[1] > centerJ) {
124 // straddle, choose one or the other based on direction
125 return new ResultPoint(di > 0 ? lastRange[0] : lastRange[1], lastI);
127 return new ResultPoint(lastRange[0], lastI);
129 return new ResultPoint(lastRange[1], lastI);
133 if (lastRange[0] < centerI) {
134 if (lastRange[1] > centerI) {
135 return new ResultPoint(lastJ, dj < 0 ? lastRange[0] : lastRange[1]);
137 return new ResultPoint(lastJ, lastRange[0]);
139 return new ResultPoint(lastJ, lastRange[1]);
145 throw ReaderException.getInstance();
149 * Computes the start and end of a region of pixels, either horizontally or vertically, that could
150 * be part of a Data Matrix barcode.
152 * @param fixedDimension if scanning horizontally, this is the row (the fixed vertical location)
153 * where we are scanning. If scanning vertically it's the colummn, the fixed horizontal location
154 * @param maxWhiteRun largest run of white pixels that can still be considered part of the
156 * @param minDim minimum pixel location, horizontally or vertically, to consider
157 * @param maxDim maximum pixel location, horizontally or vertically, to consider
158 * @param horizontal if true, we're scanning left-right, instead of up-down
159 * @return int[] with start and end of found range, or null if no such range is found
160 * (e.g. only white was found)
162 private int[] blackWhiteRange(int fixedDimension, int maxWhiteRun, int minDim, int maxDim,
163 boolean horizontal) throws ReaderException {
165 int center = (minDim + maxDim) >> 1;
167 BitArray rowOrColumn = horizontal ?
168 image.getBlackRow(fixedDimension, null, 0, image.getWidth()) :
169 image.getBlackColumn(fixedDimension, null, 0, image.getHeight());
171 // Scan left/up first
173 while (start >= minDim) {
174 if (rowOrColumn.get(start)) {
177 int whiteRunStart = start;
180 } while (start >= minDim && !rowOrColumn.get(start));
181 int whiteRunSize = whiteRunStart - start;
182 if (start < minDim || whiteRunSize > maxWhiteRun) {
183 start = whiteRunStart;
190 // Then try right/down
192 while (end < maxDim) {
193 if (rowOrColumn.get(end)) {
196 int whiteRunStart = end;
199 } while (end < maxDim && !rowOrColumn.get(end));
200 int whiteRunSize = end - whiteRunStart;
201 if (end >= maxDim || whiteRunSize > maxWhiteRun) {
209 return end > start ? new int[]{start, end} : null;