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

   1 /*
   2  * Copyright 2009 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.ReaderException;
  20 import com.google.zxing.ResultPoint;
  21 import com.google.zxing.common.BitMatrix;
  22
  23 /**
  24  * <p>A somewhat generic detector that looks for a barcode-like rectangular region within an image.
  25  * It looks within a mostly white region of an image for a region of black and white, but mostly
  26  * black. It returns the four corners of the region, as best it can determine.</p>
  27  *
  28  * @author Sean Owen
  29  */
  30 public final class MonochromeRectangleDetector {
  31
  32   private static final int MAX_MODULES = 32;
  33
  34   private final BitMatrix image;
  35
  36   public MonochromeRectangleDetector(BitMatrix image) {
  37     this.image = image;
  38   }
  39
  40   /**
  41    * <p>Detects a rectangular region of black and white -- mostly black -- with a region of mostly
  42    * white, in an image.</p>
  43    *
  44    * @return {@link ResultPoint}[] describing the corners of the rectangular region. The first and
  45    *  last points are opposed on the diagonal, as are the second and third. The first point will be
  46    *  the topmost point and the last, the bottommost. The second point will be leftmost and the
  47    *  third, the rightmost
  48    * @throws ReaderException if no Data Matrix Code can be found
  49    */
  50   public ResultPoint[] detect() throws ReaderException {
  51     int height = image.getHeight();
  52     int width = image.getWidth();
  53     int halfHeight = height >> 1;
  54     int halfWidth = width >> 1;
  55     int deltaY = Math.max(1, height / (MAX_MODULES << 3));
  56     int deltaX = Math.max(1, width / (MAX_MODULES << 3));
  57
  58     int top = 0;
  59     int bottom = height;
  60     int left = 0;
  61     int right = width;
  62     ResultPoint pointA = findCornerFromCenter(halfWidth, 0, left, right,
  63         halfHeight, -deltaY, top, bottom, halfWidth >> 1);
  64     top = (int) pointA.getY() - 1;
  65     ResultPoint pointB = findCornerFromCenter(halfWidth, -deltaX, left, right,
  66         halfHeight, 0, top, bottom, halfHeight >> 1);
  67     left = (int) pointB.getX() - 1;
  68     ResultPoint pointC = findCornerFromCenter(halfWidth, deltaX, left, right,
  69         halfHeight, 0, top, bottom, halfHeight >> 1);
  70     right = (int) pointC.getX() + 1;
  71     ResultPoint pointD = findCornerFromCenter(halfWidth, 0, left, right,
  72         halfHeight, deltaY, top, bottom, halfWidth >> 1);
  73     bottom = (int) pointD.getY() + 1;
  74
  75     // Go try to find point A again with better information -- might have been off at first.
  76     pointA = findCornerFromCenter(halfWidth, 0, left, right,
  77         halfHeight, -deltaY, top, bottom, halfWidth >> 2);
  78
  79     return new ResultPoint[] { pointA, pointB, pointC, pointD };
  80   }
  81
  82   /**
  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.
  85    *
  86    * @param centerX center's x component (horizontal)
  87    * @param deltaX same as deltaY but change in x per step instead
  88    * @param left minimum value of x
  89    * @param right maximum value of x
  90    * @param centerY center's y component (vertical)
  91    * @param deltaY change in y per step. If scanning up this is negative; down, positive;
  92    *  left or right, 0
  93    * @param top minimum value of y to search through (meaningless when di == 0)
  94    * @param bottom maximum value of y
  95    * @param maxWhiteRun maximum run of white pixels that can still be considered to be within
  96    *  the barcode
  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
  99    */
 100   private ResultPoint findCornerFromCenter(int centerX, int deltaX, int left, int right,
 101       int centerY, int deltaY, int top, int bottom, int maxWhiteRun) throws ReaderException {
 102     int[] lastRange = null;
 103     for (int y = centerY, x = centerX;
 104          y < bottom && y >= top && x < right && x >= left;
 105          y += deltaY, x += deltaX) {
 106       int[] range;
 107       if (deltaX == 0) {
 108         // horizontal slices, up and down
 109         range = blackWhiteRange(y, maxWhiteRun, left, right, true);
 110       } else {
 111         // vertical slices, left and right
 112         range = blackWhiteRange(x, maxWhiteRun, top, bottom, false);
 113       }
 114       if (range == null) {
 115         if (lastRange == null) {
 116           throw ReaderException.getInstance();
 117         }
 118         // lastRange was found
 119         if (deltaX == 0) {
 120           int lastY = y - deltaY;
 121           if (lastRange[0] < centerX) {
 122             if (lastRange[1] > centerX) {
 123               // straddle, choose one or the other based on direction
 124               return new ResultPoint(deltaY > 0 ? lastRange[0] : lastRange[1], lastY);
 125             }
 126             return new ResultPoint(lastRange[0], lastY);
 127           } else {
 128             return new ResultPoint(lastRange[1], lastY);
 129           }
 130         } else {
 131           int lastX = x - deltaX;
 132           if (lastRange[0] < centerY) {
 133             if (lastRange[1] > centerY) {
 134               return new ResultPoint(lastX, deltaX < 0 ? lastRange[0] : lastRange[1]);
 135             }
 136             return new ResultPoint(lastX, lastRange[0]);
 137           } else {
 138             return new ResultPoint(lastX, lastRange[1]);
 139           }
 140         }
 141       }
 142       lastRange = range;
 143     }
 144     throw ReaderException.getInstance();
 145   }
 146
 147   /**
 148    * Computes the start and end of a region of pixels, either horizontally or vertically, that could
 149    * be part of a Data Matrix barcode.
 150    *
 151    * @param fixedDimension if scanning horizontally, this is the row (the fixed vertical location)
 152    *  where we are scanning. If scanning vertically it's the column, the fixed horizontal location
 153    * @param maxWhiteRun largest run of white pixels that can still be considered part of the
 154    *  barcode region
 155    * @param minDim minimum pixel location, horizontally or vertically, to consider
 156    * @param maxDim maximum pixel location, horizontally or vertically, to consider
 157    * @param horizontal if true, we're scanning left-right, instead of up-down
 158    * @return int[] with start and end of found range, or null if no such range is found
 159    *  (e.g. only white was found)
 160    */
 161   private int[] blackWhiteRange(int fixedDimension, int maxWhiteRun, int minDim, int maxDim,
 162       boolean horizontal) {
 163
 164     int center = (minDim + maxDim) >> 1;
 165
 166     // Scan left/up first
 167     int start = center;
 168     while (start >= minDim) {
 169       if (horizontal ? image.get(start, fixedDimension) : image.get(fixedDimension, start)) {
 170         start--;
 171       } else {
 172         int whiteRunStart = start;
 173         do {
 174           start--;
 175         } while (start >= minDim && !(horizontal ? image.get(start, fixedDimension) :
 176             image.get(fixedDimension, start)));
 177         int whiteRunSize = whiteRunStart - start;
 178         if (start < minDim || whiteRunSize > maxWhiteRun) {
 179           start = whiteRunStart;
 180           break;
 181         }
 182       }
 183     }
 184     start++;
 185
 186     // Then try right/down
 187     int end = center;
 188     while (end < maxDim) {
 189       if (horizontal ? image.get(end, fixedDimension) : image.get(fixedDimension, end)) {
 190         end++;
 191       } else {
 192         int whiteRunStart = end;
 193         do {
 194           end++;
 195         } while (end < maxDim && !(horizontal ? image.get(end, fixedDimension) :
 196             image.get(fixedDimension, end)));
 197         int whiteRunSize = end - whiteRunStart;
 198         if (end >= maxDim || whiteRunSize > maxWhiteRun) {
 199           end = whiteRunStart;
 200           break;
 201         }
 202       }
 203     }
 204     end--;
 205
 206     return end > start ? new int[]{start, end} : null;
 207   }
 208
 209 }