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
  37   private final BitMatrix image;
  38   private final int height;
  39   private final int width;
  40
  41   public WhiteRectangleDetector(BitMatrix image) {
  42     this.image = image;
  43     height = image.getHeight();
  44     width = image.getWidth();
  45   }
  46
  47   /**
  48    * <p>
  49    * Detects a candidate barcode-like rectangular region within an image. It
  50    * starts around the center of the image, increases the size of the candidate
  51    * region until it finds a white rectangular region.
  52    * </p>
  53    *
  54    * @return {@link ResultPoint}[] describing the corners of the rectangular
  55    *         region. The first and last points are opposed on the diagonal, as
  56    *         are the second and third. The first point will be the topmost
  57    *         point and the last, the bottommost. The second point will be
  58    *         leftmost and the third, the rightmost
  59    * @throws NotFoundException if no Data Matrix Code can be found
  60    */
  61   public ResultPoint[] detect() throws NotFoundException {
  62
  63     int left = (width - INIT_SIZE) / 2;
  64     int right = (width + INIT_SIZE) / 2;
  65     int up = (height - INIT_SIZE) / 2;
  66     int down = (height + INIT_SIZE) / 2;
  67     boolean sizeExceeded = false;
  68     boolean aBlackPointFoundOnBorder = true;
  69     boolean atLeastOneBlackPointFoundOnBorder = false;
  70
  71     while (aBlackPointFoundOnBorder) {
  72
  73       aBlackPointFoundOnBorder = false;
  74
  75       // .....
  76       // .   |
  77       // .....
  78       boolean rightBorderNotWhite = true;
  79       while (rightBorderNotWhite && right < width) {
  80         rightBorderNotWhite = containsBlackPoint(up, down, right, false);
  81         if (rightBorderNotWhite) {
  82           right++;
  83           aBlackPointFoundOnBorder = true;
  84         }
  85       }
  86
  87       // .....
  88       // .   .
  89       // .___.
  90       boolean bottomBorderNotWhite = true;
  91       while (bottomBorderNotWhite && down < height) {
  92         bottomBorderNotWhite = containsBlackPoint(left, right, down, true);
  93         if (bottomBorderNotWhite) {
  94           down++;
  95           aBlackPointFoundOnBorder = true;
  96         }
  97       }
  98
  99       // .....
 100       // |   .
 101       // .....
 102       boolean leftBorderNotWhite = true;
 103       while (leftBorderNotWhite && left >= 0) {
 104         leftBorderNotWhite = containsBlackPoint(up, down, left, false);
 105         if (leftBorderNotWhite) {
 106           left--;
 107           aBlackPointFoundOnBorder = true;
 108         }
 109       }
 110
 111       // .___.
 112       // .   .
 113       // .....
 114       boolean topBorderNotWhite = true;
 115       while (topBorderNotWhite && up >= 0) {
 116         topBorderNotWhite = containsBlackPoint(left, right, up, true);
 117         if (topBorderNotWhite) {
 118           up--;
 119           aBlackPointFoundOnBorder = true;
 120         }
 121       }
 122
 123       if (right >= width || down >= height || up < 0 || left < 0) {
 124         sizeExceeded = true;
 125         break;
 126       }
 127
 128       if (aBlackPointFoundOnBorder) {
 129         atLeastOneBlackPointFoundOnBorder = true;
 130       }
 131
 132     }
 133
 134     if (!sizeExceeded && atLeastOneBlackPointFoundOnBorder) {
 135
 136         ResultPoint x=null, y=null, z=null, t=null;
 137
 138         final int max_size = right-left;
 139
 140         for (int i = 1; i < max_size; i++){
 141             ResultPoint a = new ResultPoint(left, down-i);
 142             ResultPoint b = new ResultPoint(left+i, down);
 143             z = getBlackPointOnSegment(a, b);
 144             if (z != null){
 145                 break;
 146             }
 147         }
 148
 149         if (z == null){
 150             throw NotFoundException.getNotFoundInstance();
 151         }
 152
 153         //go down right
 154         for (int i = 1; i < max_size; i++){
 155             ResultPoint a = new ResultPoint(left, up+i);
 156             ResultPoint b = new ResultPoint(left+i, up);
 157             t = getBlackPointOnSegment(a, b);
 158             if (t != null){
 159                 break;
 160             }
 161         }
 162
 163         if (t == null){
 164             throw NotFoundException.getNotFoundInstance();
 165         }
 166
 167         //go down left
 168         for (int i = 1; i < max_size; i++){
 169             ResultPoint a = new ResultPoint(right, up+i);
 170             ResultPoint b = new ResultPoint(right-i, up);
 171             x = getBlackPointOnSegment(a, b);
 172             if (x != null){
 173                 break;
 174             }
 175         }
 176
 177         if (x == null){
 178             throw NotFoundException.getNotFoundInstance();
 179         }
 180
 181         //go up left
 182         for (int i = 1; i < max_size; i++){
 183             ResultPoint a = new ResultPoint(right, down-i);
 184             ResultPoint b = new ResultPoint(right-i, down);
 185             y = getBlackPointOnSegment(a, b);
 186             if (y != null){
 187                 break;
 188             }
 189         }
 190
 191         if (y == null){
 192             throw NotFoundException.getNotFoundInstance();
 193         }
 194
 195         return centerEdges(y, z, x, t);
 196
 197     } else {
 198         throw NotFoundException.getNotFoundInstance();
 199     }
 200   }
 201
 202
 203     private ResultPoint getBlackPointOnSegment(ResultPoint a, ResultPoint b) {
 204         int dist = distanceL2(a, b);
 205         float xStep = (b.getX()-a.getX())/dist;
 206         float yStep = (b.getY()-a.getY())/dist;
 207
 208         for (int i = 0; i < dist; i++){
 209             if (image.get(Math.round(a.getX()+i*xStep), Math.round(a.getY()+i*yStep))){
 210                 return new ResultPoint(Math.round(a.getX()+i*xStep), Math.round(a.getY()+i*yStep));
 211             }
 212         }
 213         return null;
 214     }
 215
 216     private static int distanceL2(ResultPoint a, ResultPoint b) {
 217         return (int) Math.round(Math.sqrt((a.getX() - b.getX())
 218                 * (a.getX() - b.getX()) + (a.getY() - b.getY())
 219                 * (a.getY() - b.getY())));
 220     }
 221
 222   /**
 223    * recenters the points of a constant distance towards the center
 224    *
 225    * @param y bottom most point
 226    * @param z left most point
 227    * @param x right most point
 228    * @param t top most point
 229    * @return {@link ResultPoint}[] describing the corners of the rectangular
 230    *         region. The first and last points are opposed on the diagonal, as
 231    *         are the second and third. The first point will be the topmost
 232    *         point and the last, the bottommost. The second point will be
 233    *         leftmost and the third, the rightmost
 234    */
 235   private ResultPoint[] centerEdges(ResultPoint y, ResultPoint z,
 236                                     ResultPoint x, ResultPoint t) {
 237
 238     //
 239     //       t            t
 240     //  z                      x
 241     //        x    OR    z
 242     //   y                    y
 243     //
 244
 245     float yi = y.getX(), yj = y.getY(), zi = z.getX(), zj = z.getY(), xi = x
 246         .getX(), xj = x.getY(), ti = t.getX(), tj = t.getY();
 247
 248     final int corr = 1;
 249     if (yi < width / 2) {
 250       return new ResultPoint[]{new ResultPoint(ti - corr, tj + corr),
 251           new ResultPoint(zi + corr, zj + corr),
 252           new ResultPoint(xi - corr, xj - corr),
 253           new ResultPoint(yi + corr, yj - corr)};
 254     } else {
 255       return new ResultPoint[]{new ResultPoint(ti + corr, tj + corr),
 256           new ResultPoint(zi + corr, zj - corr),
 257           new ResultPoint(xi - corr, xj + corr),
 258           new ResultPoint(yi - corr, yj - corr)};
 259     }
 260   }
 261
 262   /**
 263    * Determines whether a segment contains a black point
 264    *
 265    * @param a          min value of the scanned coordinate
 266    * @param b          max value of the scanned coordinate
 267    * @param fixed      value of fixed coordinate
 268    * @param horizontal set to true if scan must be horizontal, false if vertical
 269    * @return true if a black point has been found, else false.
 270    */
 271   private boolean containsBlackPoint(int a, int b, int fixed, boolean horizontal) {
 272
 273     if (horizontal) {
 274       for (int x = a; x < b; x++) {
 275         if (image.get(x, fixed)) {
 276           return true;
 277         }
 278       }
 279     } else {
 280       for (int y = a; y < b; y++) {
 281         if (image.get(fixed, y)) {
 282           return true;
 283                                 }
 284                         }
 285                 }
 286
 287                 return false;
 288         }
 289
 290 }