core/src/com/google/zxing/common/detector/WhiteRectangleDetector.java

   1 /*
   2  * Copyright 2010 ZXing authors
   3  *
   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
   7  *
   8  *      http://www.apache.org/licenses/LICENSE-2.0
   9  *
  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.
  15  */
  16
  17 package com.google.zxing.common.detector;
  18
  19 import com.google.zxing.NotFoundException;
  20 import com.google.zxing.ResultPoint;
  21 import com.google.zxing.common.BitMatrix;
  22
  23 /**
  24  * <p>
  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.
  29  * </p>
  30  *
  31  * @author David Olivier
  32  */
  33 public final class WhiteRectangleDetector {
  34
  35   private static final int INIT_SIZE = 40;
  36   private static final int CORR = 1;
  37
  38   private final BitMatrix image;
  39   private final int height;
  40   private final int width;
  41
  42   public WhiteRectangleDetector(BitMatrix image) {
  43     this.image = image;
  44     height = image.getHeight();
  45     width = image.getWidth();
  46   }
  47
  48   /**
  49    * <p>
  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.
  53    * </p>
  54    *
  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
  61    */
  62   public ResultPoint[] detect() throws NotFoundException {
  63
  64     int left = (width - INIT_SIZE) >> 1;
  65     int right = (width + INIT_SIZE) >> 1;
  66     int up = (height - INIT_SIZE) >> 1;
  67     int down = (height + INIT_SIZE) >> 1;
  68     boolean sizeExceeded = false;
  69     boolean aBlackPointFoundOnBorder = true;
  70     boolean atLeastOneBlackPointFoundOnBorder = false;
  71
  72     while (aBlackPointFoundOnBorder) {
  73
  74       aBlackPointFoundOnBorder = false;
  75
  76       // .....
  77       // .   |
  78       // .....
  79       boolean rightBorderNotWhite = true;
  80       while (rightBorderNotWhite && right < width) {
  81         rightBorderNotWhite = containsBlackPoint(up, down, right, false);
  82         if (rightBorderNotWhite) {
  83           right++;
  84           aBlackPointFoundOnBorder = true;
  85         }
  86       }
  87
  88       if (right >= width) {
  89         sizeExceeded = true;
  90         break;
  91       }
  92
  93       // .....
  94       // .   .
  95       // .___.
  96       boolean bottomBorderNotWhite = true;
  97       while (bottomBorderNotWhite && down < height) {
  98         bottomBorderNotWhite = containsBlackPoint(left, right, down, true);
  99         if (bottomBorderNotWhite) {
 100           down++;
 101           aBlackPointFoundOnBorder = true;
 102         }
 103       }
 104
 105       if (down >= height) {
 106         sizeExceeded = true;
 107         break;
 108       }
 109
 110       // .....
 111       // |   .
 112       // .....
 113       boolean leftBorderNotWhite = true;
 114       while (leftBorderNotWhite && left >= 0) {
 115         leftBorderNotWhite = containsBlackPoint(up, down, left, false);
 116         if (leftBorderNotWhite) {
 117           left--;
 118           aBlackPointFoundOnBorder = true;
 119         }
 120       }
 121
 122       if (left < 0) {
 123         sizeExceeded = true;
 124         break;
 125       }
 126
 127       // .___.
 128       // .   .
 129       // .....
 130       boolean topBorderNotWhite = true;
 131       while (topBorderNotWhite && up >= 0) {
 132         topBorderNotWhite = containsBlackPoint(left, right, up, true);
 133         if (topBorderNotWhite) {
 134           up--;
 135           aBlackPointFoundOnBorder = true;
 136         }
 137       }
 138
 139       if (up < 0) {
 140         sizeExceeded = true;
 141         break;
 142       }
 143
 144       if (aBlackPointFoundOnBorder) {
 145         atLeastOneBlackPointFoundOnBorder = true;
 146       }
 147
 148     }
 149
 150     if (!sizeExceeded && atLeastOneBlackPointFoundOnBorder) {
 151
 152       int maxSize = right - left;
 153
 154       ResultPoint z = null;
 155       for (int i = 1; i < maxSize; i++) {
 156         z = getBlackPointOnSegment(left, down - i, left + i, down);
 157         if (z != null) {
 158           break;
 159         }
 160       }
 161
 162       if (z == null) {
 163         throw NotFoundException.getNotFoundInstance();
 164       }
 165
 166       ResultPoint t = null;
 167       //go down right
 168       for (int i = 1; i < maxSize; i++) {
 169         t = getBlackPointOnSegment(left, up + i, left + i, up);
 170         if (t != null) {
 171           break;
 172         }
 173       }
 174
 175       if (t == null) {
 176         throw NotFoundException.getNotFoundInstance();
 177       }
 178
 179       ResultPoint x = null;
 180       //go down left
 181       for (int i = 1; i < maxSize; i++) {
 182         x = getBlackPointOnSegment(right, up + i, right - i, up);
 183         if (x != null) {
 184           break;
 185         }
 186       }
 187
 188       if (x == null) {
 189         throw NotFoundException.getNotFoundInstance();
 190       }
 191
 192       ResultPoint y = null;
 193       //go up left
 194       for (int i = 1; i < maxSize; i++) {
 195         y = getBlackPointOnSegment(right, down - i, right - i, down);
 196         if (y != null) {
 197           break;
 198         }
 199       }
 200
 201       if (y == null) {
 202         throw NotFoundException.getNotFoundInstance();
 203       }
 204
 205       return centerEdges(y, z, x, t);
 206
 207     } else {
 208       throw NotFoundException.getNotFoundInstance();
 209     }
 210   }
 211
 212   /**
 213    * Ends up being a bit faster than Math.round(). This merely rounds its
 214    * argument to the nearest int, where x.5 rounds up.
 215    */
 216   private static int round(float d) {
 217     return (int) (d + 0.5f);
 218   }
 219
 220   private ResultPoint getBlackPointOnSegment(float aX, float aY, float bX, float bY) {
 221     int dist = distanceL2(aX, aY, bX, bY);
 222     float xStep = (bX - aX) / dist;
 223     float yStep = (bY - aY) / dist;
 224
 225     for (int i = 0; i < dist; i++) {
 226       int x = round(aX + i * xStep);
 227       int y = round(aY + i * yStep);
 228       if (image.get(x, y)) {
 229         return new ResultPoint(x, y);
 230       }
 231     }
 232     return null;
 233   }
 234
 235   private static int distanceL2(float aX, float aY, float bX, float bY) {
 236     float xDiff = aX - bX;
 237     float yDiff = aY - bY;
 238     return round((float) Math.sqrt(xDiff * xDiff + yDiff * yDiff));
 239   }
 240
 241   /**
 242    * recenters the points of a constant distance towards the center
 243    *
 244    * @param y bottom most point
 245    * @param z left most point
 246    * @param x right most point
 247    * @param t top most point
 248    * @return {@link ResultPoint}[] describing the corners of the rectangular
 249    *         region. The first and last points are opposed on the diagonal, as
 250    *         are the second and third. The first point will be the topmost
 251    *         point and the last, the bottommost. The second point will be
 252    *         leftmost and the third, the rightmost
 253    */
 254   private ResultPoint[] centerEdges(ResultPoint y, ResultPoint z,
 255                                     ResultPoint x, ResultPoint t) {
 256
 257     //
 258     //       t            t
 259     //  z                      x
 260     //        x    OR    z
 261     //   y                    y
 262     //
 263
 264     float yi = y.getX();
 265     float yj = y.getY();
 266     float zi = z.getX();
 267     float zj = z.getY();
 268     float xi = x.getX();
 269     float xj = x.getY();
 270     float ti = t.getX();
 271     float tj = t.getY();
 272
 273     if (yi < width / 2) {
 274       return new ResultPoint[]{
 275           new ResultPoint(ti - CORR, tj + CORR),
 276           new ResultPoint(zi + CORR, zj + CORR),
 277           new ResultPoint(xi - CORR, xj - CORR),
 278           new ResultPoint(yi + CORR, yj - CORR)};
 279     } else {
 280       return new ResultPoint[]{
 281           new ResultPoint(ti + CORR, tj + CORR),
 282           new ResultPoint(zi + CORR, zj - CORR),
 283           new ResultPoint(xi - CORR, xj + CORR),
 284           new ResultPoint(yi - CORR, yj - CORR)};
 285     }
 286   }
 287
 288   /**
 289    * Determines whether a segment contains a black point
 290    *
 291    * @param a          min value of the scanned coordinate
 292    * @param b          max value of the scanned coordinate
 293    * @param fixed      value of fixed coordinate
 294    * @param horizontal set to true if scan must be horizontal, false if vertical
 295    * @return true if a black point has been found, else false.
 296    */
 297   private boolean containsBlackPoint(int a, int b, int fixed, boolean horizontal) {
 298
 299     if (horizontal) {
 300       for (int x = a; x <= b; x++) {
 301         if (image.get(x, fixed)) {
 302           return true;
 303         }
 304       }
 305     } else {
 306       for (int y = a; y <= b; y++) {
 307         if (image.get(fixed, y)) {
 308           return true;
 309         }
 310       }
 311     }
 312
 313     return false;
 314   }
 315
 316 }