2 * Copyright 2010 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.NotFoundException;
20 import com.google.zxing.ResultPoint;
21 import com.google.zxing.common.BitMatrix;
25 * Detects a candidate barcode-like rectangular region within an image. It
26 * starts around the center of the image, increases the size of the candidate
27 * region until it finds a white rectangular region. By keeping track of the
28 * last black points it encountered, it determines the corners of the barcode.
31 * @author David Olivier
33 public final class WhiteRectangleDetector {
35 private static final int INIT_SIZE = 40;
36 private static final int MIN_SIZE = 20;
38 private final BitMatrix image;
39 private final int height;
40 private final int width;
42 public WhiteRectangleDetector(BitMatrix image) {
44 height = image.getHeight();
45 width = image.getWidth();
50 * Detects a candidate barcode-like rectangular region within an image. It
51 * starts around the center of the image, increases the size of the candidate
52 * region until it finds a white rectangular region.
55 * @return {@link ResultPoint}[] describing the corners of the rectangular
56 * region. The first and last points are opposed on the diagonal, as
57 * are the second and third. The first point will be the topmost
58 * point and the last, the bottommost. The second point will be
59 * leftmost and the third, the rightmost
60 * @throws NotFoundException if no Data Matrix Code can be found
62 public ResultPoint[] detect() throws NotFoundException {
64 int left = (width - INIT_SIZE) / 2;
65 int right = (width + INIT_SIZE) / 2;
66 int up = (height - INIT_SIZE) / 2;
67 int down = (height + INIT_SIZE) / 2;
68 boolean sizeExceeded = false;
69 boolean aBlackPointFoundOnBorder = true;
70 boolean atLeastOneBlackPointFoundOnBorder = false;
72 while (aBlackPointFoundOnBorder) {
74 aBlackPointFoundOnBorder = false;
79 boolean rightBorderNotWhite = true;
80 while (rightBorderNotWhite && right < width) {
81 rightBorderNotWhite = containsBlackPoint(up, down, right, false);
82 if (rightBorderNotWhite) {
84 aBlackPointFoundOnBorder = true;
91 boolean bottomBorderNotWhite = true;
92 while (bottomBorderNotWhite && down < height) {
93 bottomBorderNotWhite = containsBlackPoint(left, right, down, true);
94 if (bottomBorderNotWhite) {
96 aBlackPointFoundOnBorder = true;
103 boolean leftBorderNotWhite = true;
104 while (leftBorderNotWhite && left >= 0) {
105 leftBorderNotWhite = containsBlackPoint(up, down, left, false);
106 if (leftBorderNotWhite) {
108 aBlackPointFoundOnBorder = true;
115 boolean topBorderNotWhite = true;
116 while (topBorderNotWhite && up >= 0) {
117 topBorderNotWhite = containsBlackPoint(left, right, up, true);
118 if (topBorderNotWhite) {
120 aBlackPointFoundOnBorder = true;
124 if (right >= width || down >= height || up < 0 || left < 0) {
129 if (aBlackPointFoundOnBorder) {
130 atLeastOneBlackPointFoundOnBorder = true;
135 if (!sizeExceeded && atLeastOneBlackPointFoundOnBorder) {
142 ResultPoint x = getBlackPoint(up, down, right - 1, false);
143 ResultPoint y = getBlackPoint(left, right, down - 1, true);
144 ResultPoint z = getBlackPoint(up, down, left + 1, false);
145 ResultPoint t = getBlackPoint(left, right, up + 1, true);
147 // if the rectangle if perfectly horizontal (mostly in test cases)
148 // then we end up with:
153 if (distance(z, t) < MIN_SIZE) {
154 ResultPoint u = getBlackPointInverted(up, down, right - 1, false);
159 return centerEdges(y, z, x, t);
162 throw NotFoundException.getNotFoundInstance();
167 * recenters the points of a constant distance towards the center
169 * @param y bottom most point
170 * @param z left most point
171 * @param x right most point
172 * @param t top most point
173 * @return {@link ResultPoint}[] describing the corners of the rectangular
174 * region. The first and last points are opposed on the diagonal, as
175 * are the second and third. The first point will be the topmost
176 * point and the last, the bottommost. The second point will be
177 * leftmost and the third, the rightmost
179 private ResultPoint[] centerEdges(ResultPoint y, ResultPoint z,
180 ResultPoint x, ResultPoint t) {
189 float yi = y.getX(), yj = y.getY(), zi = z.getX(), zj = z.getY(), xi = x
190 .getX(), xj = x.getY(), ti = t.getX(), tj = t.getY();
193 if (yi < width / 2) {
194 return new ResultPoint[]{new ResultPoint(ti - corr, tj + corr),
195 new ResultPoint(zi + corr, zj + corr),
196 new ResultPoint(xi - corr, xj - corr),
197 new ResultPoint(yi + corr, yj - corr)};
199 return new ResultPoint[]{new ResultPoint(ti + corr, tj + corr),
200 new ResultPoint(zi + corr, zj - corr),
201 new ResultPoint(xi - corr, xj + corr),
202 new ResultPoint(yi - corr, yj - corr)};
206 // L1 distance (metropolitan distance)
207 private static float distance(ResultPoint a, ResultPoint b) {
208 return Math.abs(a.getX() - b.getX()) + Math.abs(a.getY() - b.getY());
212 * Gets the coordinate of an extreme black point of a segment
214 * @param a min value of the scanned coordinate
215 * @param b max value of the scanned coordinate
216 * @param fixed value of fixed coordinate
217 * @param horizontal set to true if scan must be horizontal, false if vertical
218 * @return {@link ResultPoint} describing the black point. If scan is horizontal,
219 * the returned point is the first encountered if it is on the left of the image,
220 * else the last one. If scan is vertical, the returned point is the first encountered
221 * if it is on the top of the image, else the last one.
222 * {@link ResultPoint} is null if not black point has been found
224 private ResultPoint getBlackPoint(int a, int b, int fixed, boolean horizontal) {
226 ResultPoint last = null;
229 for (int x = a; x < b; x++) {
230 if (image.get(x, fixed)) {
232 return new ResultPoint(x, fixed);
234 while (x < width && image.get(x, fixed)) {
238 last = new ResultPoint(x, fixed);
243 for (int y = a; y < b; y++) {
244 if (image.get(fixed, y)) {
245 if (y < height / 2) {
246 return new ResultPoint(fixed, y);
248 while (y < height && image.get(fixed, y)) {
252 last = new ResultPoint(fixed, y);
262 * Same as getBlackPoint, but returned point is the last one found.
264 * @param a min value of the scanned coordinate
265 * @param b max value of the scanned coordinate
266 * @param fixed value of fixed coordinate
267 * @param horizontal set to true if scan must be horizontal, false if vertical
268 * @return {@link ResultPoint} describing the black point.
270 private ResultPoint getBlackPointInverted(int a, int b, int fixed, boolean horizontal) {
273 for (int x = b + 1; x >= a; x--) {
274 if (image.get(x, fixed)) {
275 return new ResultPoint(x, fixed);
279 for (int y = b + 1; y >= a; y--) {
280 if (image.get(fixed, y)) {
281 return new ResultPoint(fixed, y);
290 * Determines whether a segment contains a black point
292 * @param a min value of the scanned coordinate
293 * @param b max value of the scanned coordinate
294 * @param fixed value of fixed coordinate
295 * @param horizontal set to true if scan must be horizontal, false if vertical
296 * @return true if a black point has been found, else false.
298 private boolean containsBlackPoint(int a, int b, int fixed, boolean horizontal) {
301 for (int x = a; x < b; x++) {
302 if (image.get(x, fixed)) {
307 for (int y = a; y < b; y++) {
308 if (image.get(fixed, y)) {