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