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       if (right >= width) {
  88           sizeExceeded = true;
  89           break;
  90       }
  91
  92       // .....
  93       // .   .
  94       // .___.
  95       boolean bottomBorderNotWhite = true;
  96       while (bottomBorderNotWhite && down < height) {
  97         bottomBorderNotWhite = containsBlackPoint(left, right, down, true);
  98         if (bottomBorderNotWhite) {
  99           down++;
 100           aBlackPointFoundOnBorder = true;
 101         }
 102       }
 103
 104       if (down >= height) {
 105           sizeExceeded = true;
 106           break;
 107       }
 108
 109       // .....
 110       // |   .
 111       // .....
 112       boolean leftBorderNotWhite = true;
 113       while (leftBorderNotWhite && left >= 0) {
 114         leftBorderNotWhite = containsBlackPoint(up, down, left, false);
 115         if (leftBorderNotWhite) {
 116           left--;
 117           aBlackPointFoundOnBorder = true;
 118         }
 119       }
 120
 121       if (left < 0) {
 122           sizeExceeded = true;
 123           break;
 124       }
 125
 126       // .___.
 127       // .   .
 128       // .....
 129       boolean topBorderNotWhite = true;
 130       while (topBorderNotWhite && up >= 0) {
 131         topBorderNotWhite = containsBlackPoint(left, right, up, true);
 132         if (topBorderNotWhite) {
 133           up--;
 134           aBlackPointFoundOnBorder = true;
 135         }
 136       }
 137
 138       if (up < 0) {
 139         sizeExceeded = true;
 140         break;
 141       }
 142
 143       if (aBlackPointFoundOnBorder) {
 144         atLeastOneBlackPointFoundOnBorder = true;
 145       }
 146
 147     }
 148
 149     if (!sizeExceeded && atLeastOneBlackPointFoundOnBorder) {
 150
 151         ResultPoint x=null, y=null, z=null, t=null;
 152
 153         final int max_size = right-left;
 154
 155         for (int i = 1; i < max_size; i++){
 156             ResultPoint a = new ResultPoint(left, down-i);
 157             ResultPoint b = new ResultPoint(left+i, down);
 158             z = getBlackPointOnSegment(a, b);
 159             if (z != null){
 160                 break;
 161             }
 162         }
 163
 164         if (z == null){
 165             throw NotFoundException.getNotFoundInstance();
 166         }
 167
 168         //go down right
 169         for (int i = 1; i < max_size; i++){
 170             ResultPoint a = new ResultPoint(left, up+i);
 171             ResultPoint b = new ResultPoint(left+i, up);
 172             t = getBlackPointOnSegment(a, b);
 173             if (t != null){
 174                 break;
 175             }
 176         }
 177
 178         if (t == null){
 179             throw NotFoundException.getNotFoundInstance();
 180         }
 181
 182         //go down left
 183         for (int i = 1; i < max_size; i++){
 184             ResultPoint a = new ResultPoint(right, up+i);
 185             ResultPoint b = new ResultPoint(right-i, up);
 186             x = getBlackPointOnSegment(a, b);
 187             if (x != null){
 188                 break;
 189             }
 190         }
 191
 192         if (x == null){
 193             throw NotFoundException.getNotFoundInstance();
 194         }
 195
 196         //go up left
 197         for (int i = 1; i < max_size; i++){
 198             ResultPoint a = new ResultPoint(right, down-i);
 199             ResultPoint b = new ResultPoint(right-i, down);
 200             y = getBlackPointOnSegment(a, b);
 201             if (y != null){
 202                 break;
 203             }
 204         }
 205
 206         if (y == null){
 207             throw NotFoundException.getNotFoundInstance();
 208         }
 209
 210         return centerEdges(y, z, x, t);
 211
 212     } else {
 213         throw NotFoundException.getNotFoundInstance();
 214     }
 215   }
 216
 217
 218     private ResultPoint getBlackPointOnSegment(ResultPoint a, ResultPoint b) {
 219         int dist = distanceL2(a, b);
 220         float xStep = (b.getX()-a.getX())/dist;
 221         float yStep = (b.getY()-a.getY())/dist;
 222
 223         for (int i = 0; i < dist; i++){
 224             if (image.get(Math.round(a.getX()+i*xStep), Math.round(a.getY()+i*yStep))){
 225                 return new ResultPoint(Math.round(a.getX()+i*xStep), Math.round(a.getY()+i*yStep));
 226             }
 227         }
 228         return null;
 229     }
 230
 231     private static int distanceL2(ResultPoint a, ResultPoint b) {
 232         return (int) Math.round(Math.sqrt((a.getX() - b.getX())
 233                 * (a.getX() - b.getX()) + (a.getY() - b.getY())
 234                 * (a.getY() - b.getY())));
 235     }
 236
 237   /**
 238    * recenters the points of a constant distance towards the center
 239    *
 240    * @param y bottom most point
 241    * @param z left most point
 242    * @param x right most point
 243    * @param t top most point
 244    * @return {@link ResultPoint}[] describing the corners of the rectangular
 245    *         region. The first and last points are opposed on the diagonal, as
 246    *         are the second and third. The first point will be the topmost
 247    *         point and the last, the bottommost. The second point will be
 248    *         leftmost and the third, the rightmost
 249    */
 250   private ResultPoint[] centerEdges(ResultPoint y, ResultPoint z,
 251                                     ResultPoint x, ResultPoint t) {
 252
 253     //
 254     //       t            t
 255     //  z                      x
 256     //        x    OR    z
 257     //   y                    y
 258     //
 259
 260     float yi = y.getX(), yj = y.getY(), zi = z.getX(), zj = z.getY(), xi = x
 261         .getX(), xj = x.getY(), ti = t.getX(), tj = t.getY();
 262
 263     final int corr = 1;
 264     if (yi < width / 2) {
 265       return new ResultPoint[]{new ResultPoint(ti - corr, tj + corr),
 266           new ResultPoint(zi + corr, zj + corr),
 267           new ResultPoint(xi - corr, xj - corr),
 268           new ResultPoint(yi + corr, yj - corr)};
 269     } else {
 270       return new ResultPoint[]{new ResultPoint(ti + corr, tj + corr),
 271           new ResultPoint(zi + corr, zj - corr),
 272           new ResultPoint(xi - corr, xj + corr),
 273           new ResultPoint(yi - corr, yj - corr)};
 274     }
 275   }
 276
 277   /**
 278    * Determines whether a segment contains a black point
 279    *
 280    * @param a          min value of the scanned coordinate
 281    * @param b          max value of the scanned coordinate
 282    * @param fixed      value of fixed coordinate
 283    * @param horizontal set to true if scan must be horizontal, false if vertical
 284    * @return true if a black point has been found, else false.
 285    */
 286   private boolean containsBlackPoint(int a, int b, int fixed, boolean horizontal) {
 287
 288     if (horizontal) {
 289       for (int x = a; x <= b; x++) {
 290           if (x>=480 || x < 0 || fixed >= 360 || fixed < 0){
 291                   x++;
 292           }
 293         if (image.get(x, fixed)) {
 294           return true;
 295         }
 296       }
 297     } else {
 298       for (int y = a; y <= b; y++) {
 299           if (y>=360 || y < 0 || fixed >= 480 || fixed < 0){
 300                   y++;
 301           }
 302         if (image.get(fixed, y)) {
 303           return true;
 304                                 }
 305                 }
 306         }
 307
 308         return false;
 309   }
 310
 311 }