src/com/google/zxing/qrcode/detector/AlignmentPatternFinder.java

   1 /*\r
   2  * Copyright 2007 Google Inc.\r
   3  *\r
   4  * Licensed under the Apache License, Version 2.0 (the "License");\r
   5  * you may not use this file except in compliance with the License.\r
   6  * You may obtain a copy of the License at\r
   7  *\r
   8  *      http://www.apache.org/licenses/LICENSE-2.0\r
   9  *\r
  10  * Unless required by applicable law or agreed to in writing, software\r
  11  * distributed under the License is distributed on an "AS IS" BASIS,\r
  12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.\r
  13  * See the License for the specific language governing permissions and\r
  14  * limitations under the License.\r
  15  */\r
  16 \r
  17 package com.google.zxing.qrcode.detector;\r
  18 \r
  19 import com.google.zxing.MonochromeBitmapSource;\r
  20 import com.google.zxing.ReaderException;\r
  21 import com.google.zxing.common.BitArray;\r
  22 \r
  23 import java.util.Vector;\r
  24 \r
  25 /**\r
  26  * <p>At the moment this only looks for the bottom-right alignment pattern.</p>\r
  27  *\r
  28  * <p>This class is not thread-safe.</p>\r
  29  *\r
  30  * @author srowen@google.com (Sean Owen)\r
  31  */\r
  32 final class AlignmentPatternFinder {\r
  33 \r
  34   private final MonochromeBitmapSource image;\r
  35   private final Vector possibleCenters;\r
  36   private final int startX;\r
  37   private final int startY;\r
  38   private final int width;\r
  39   private final int height;\r
  40   private final float moduleSize;\r
  41 \r
  42   AlignmentPatternFinder(MonochromeBitmapSource image,\r
  43                          int startX,\r
  44                          int startY,\r
  45                          int width,\r
  46                          int height,\r
  47                          float moduleSize) {\r
  48     this.image = image;\r
  49     this.possibleCenters = new Vector(5);\r
  50     this.startX = startX;\r
  51     this.startY = startY;\r
  52     this.width = width;\r
  53     this.height = height;\r
  54     this.moduleSize = moduleSize;\r
  55   }\r
  56 \r
  57   AlignmentPattern find() throws ReaderException {\r
  58     int startX = this.startX;\r
  59     int height = this.height;\r
  60     int maxJ = startX + width;\r
  61     int middleI = startY + (height >> 1);\r
  62     BitArray luminanceRow = new BitArray(width);\r
  63     int[] stateCount = new int[3]; // looking for 1 1 1\r
  64     for (int iGen = 0; iGen < height; iGen++) {\r
  65       // Search from middle outwards\r
  66       int i = middleI +\r
  67           ((iGen & 0x01) == 0 ? ((iGen + 1) >> 1) : -((iGen + 1) >> 1));\r
  68       image.getBlackRow(i, luminanceRow, startX, width);\r
  69       stateCount[0] = 0;\r
  70       stateCount[1] = 0;\r
  71       stateCount[2] = 0;\r
  72       int currentState = 0;\r
  73       int j = startX;\r
  74       // Burn off leading white pixels before anything else; if we start in the middle of\r
  75       // a white run, it doesn't make sense to count its length, since we don't know if the\r
  76       // white run continued to the left of the start point\r
  77       while (!luminanceRow.get(j - startX) && j < maxJ) {\r
  78         j++;\r
  79       }\r
  80       while (j < maxJ) {\r
  81         if (luminanceRow.get(j - startX)) {\r
  82           // Black pixel\r
  83           if (currentState == 1) { // Counting black pixels\r
  84             stateCount[currentState]++;\r
  85           } else { // Counting white pixels\r
  86             if (currentState == 2) { // A winner?\r
  87               if (foundPatternCross(stateCount)) { // Yes\r
  88                 AlignmentPattern confirmed =\r
  89                     handlePossibleCenter(stateCount, i, j);\r
  90                 if (confirmed != null) {\r
  91                   return confirmed;\r
  92                 }\r
  93               }\r
  94               stateCount[0] = stateCount[2];\r
  95               stateCount[1] = 1;\r
  96               stateCount[2] = 0;\r
  97               currentState = 1;\r
  98             } else {\r
  99               stateCount[++currentState]++;\r
 100             }\r
 101           }\r
 102         } else { // White pixel\r
 103           if (currentState == 1) { // Counting black pixels\r
 104             currentState++;\r
 105           }\r
 106           stateCount[currentState]++;\r
 107         }\r
 108         j++;\r
 109       }\r
 110       if (foundPatternCross(stateCount)) {\r
 111         AlignmentPattern confirmed = handlePossibleCenter(stateCount, i, maxJ);\r
 112         if (confirmed != null) {\r
 113           return confirmed;\r
 114         }\r
 115       }\r
 116 \r
 117     }\r
 118 \r
 119     // Hmm, nothing we saw was observed and confirmed twice. If we had\r
 120     // any guess at all, return it.\r
 121     if (!possibleCenters.isEmpty()) {\r
 122       return (AlignmentPattern) possibleCenters.elementAt(0);\r
 123     }\r
 124 \r
 125     throw new ReaderException("Could not find alignment pattern");\r
 126   }\r
 127 \r
 128   private static float centerFromEnd(int[] stateCount, int end) {\r
 129     return (float) (end - stateCount[2]) - stateCount[1] / 2.0f;\r
 130   }\r
 131 \r
 132   private boolean foundPatternCross(int[] stateCount) {\r
 133     float moduleSize = this.moduleSize;\r
 134     for (int i = 0; i < 3; i++) {\r
 135       if (2.0f * Math.abs(moduleSize - stateCount[i]) >= moduleSize) {\r
 136         return false;\r
 137       }\r
 138     }\r
 139     return true;\r
 140   }\r
 141 \r
 142   private float crossCheckVertical(int startI, int centerJ, int maxCount) {\r
 143     MonochromeBitmapSource image = this.image;\r
 144 \r
 145     int maxI = image.getHeight();\r
 146     int[] stateCount = new int[3];\r
 147     int i = startI;\r
 148     while (i >= 0 && image.isBlack(centerJ, i) && stateCount[1] <= maxCount) {\r
 149       stateCount[1]++;\r
 150       i--;\r
 151     }\r
 152     if (i < 0 || stateCount[1] > maxCount) {\r
 153       return Float.NaN;\r
 154     }\r
 155     while (i >= 0 && !image.isBlack(centerJ, i) && stateCount[0] <= maxCount) {\r
 156       stateCount[0]++;\r
 157       i--;\r
 158     }\r
 159     if (stateCount[0] > maxCount) {\r
 160       return Float.NaN;\r
 161     }\r
 162 \r
 163     i = startI + 1;\r
 164     while (i < maxI && image.isBlack(centerJ, i) &&\r
 165         stateCount[1] <= maxCount) {\r
 166       stateCount[1]++;\r
 167       i++;\r
 168     }\r
 169     if (i == maxI || stateCount[1] > maxCount) {\r
 170       return Float.NaN;\r
 171     }\r
 172     while (i < maxI && !image.isBlack(centerJ, i) &&\r
 173         stateCount[2] <= maxCount) {\r
 174       stateCount[2]++;\r
 175       i++;\r
 176     }\r
 177     if (stateCount[2] > maxCount) {\r
 178       return Float.NaN;\r
 179     }\r
 180 \r
 181     return\r
 182         foundPatternCross(stateCount) ?\r
 183             centerFromEnd(stateCount, i) :\r
 184             Float.NaN;\r
 185   }\r
 186 \r
 187   private AlignmentPattern handlePossibleCenter(int[] stateCount,\r
 188                                                 int i,\r
 189                                                 int j) {\r
 190     float centerJ = centerFromEnd(stateCount, j);\r
 191     float centerI = crossCheckVertical(i, (int) centerJ, 2 * stateCount[1]);\r
 192     if (!Float.isNaN(centerI)) {\r
 193       float estimatedModuleSize = (float) (stateCount[0] +\r
 194           stateCount[1] +\r
 195           stateCount[2]) / 3.0f;\r
 196       int max = possibleCenters.size();\r
 197       for (int index = 0; index < max; index++) {\r
 198         AlignmentPattern center = (AlignmentPattern) possibleCenters.elementAt(index);\r
 199         // Look for about the same center and module size:\r
 200         if (center.aboutEquals(estimatedModuleSize, centerI, centerJ)) {\r
 201           return new AlignmentPattern(centerJ, centerI, estimatedModuleSize);\r
 202         }\r
 203       }\r
 204       // Hadn't found this before; save it\r
 205       possibleCenters.addElement(new AlignmentPattern(centerJ, centerI, estimatedModuleSize));\r
 206     }\r
 207     return null;\r
 208   }\r
 209 \r
 210 }