core/src/com/google/zxing/qrcode/encoder/MaskUtil.java

   1 /*
   2  * Copyright 2008 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.qrcode.encoder;
  18
  19 import com.google.zxing.common.ByteMatrix;
  20
  21 /**
  22  * @author satorux@google.com (Satoru Takabayashi) - creator
  23  * @author dswitkin@google.com (Daniel Switkin) - ported from C++
  24  */
  25 public final class MaskUtil {
  26
  27   private MaskUtil() {
  28     // do nothing
  29   }
  30
  31   // The mask penalty calculation is complicated.  See Table 21 of JISX0510:2004 (p.45) for details.
  32   // Basically it applies four rules and summate all penalties.
  33   public static int calculateMaskPenalty(final ByteMatrix matrix) {
  34     int penalty = 0;
  35     penalty += applyMaskPenaltyRule1(matrix);
  36     penalty += applyMaskPenaltyRule2(matrix);
  37     penalty += applyMaskPenaltyRule3(matrix);
  38     penalty += applyMaskPenaltyRule4(matrix);
  39     return penalty;
  40   }
  41
  42   // Apply mask penalty rule 1 and return the penalty. Find repetitive cells with the same color and
  43   // give penalty to them. Example: 00000 or 11111.
  44   public static int applyMaskPenaltyRule1(final ByteMatrix matrix) {
  45     return applyMaskPenaltyRule1Internal(matrix, true) + applyMaskPenaltyRule1Internal(matrix, false);
  46   }
  47
  48   // Apply mask penalty rule 2 and return the penalty. Find 2x2 blocks with the same color and give
  49   // penalty to them.
  50   public static int applyMaskPenaltyRule2(final ByteMatrix matrix) {
  51     int penalty = 0;
  52     byte[][] array = matrix.getArray();
  53     int width = matrix.width();
  54     int height = matrix.height();
  55     for (int y = 0; y < height - 1; ++y) {
  56       for (int x = 0; x < width - 1; ++x) {
  57         int value = array[y][x];
  58         if (value == array[y][x + 1] && value == array[y + 1][x] && value == array[y + 1][x + 1]) {
  59           penalty += 3;
  60         }
  61       }
  62     }
  63     return penalty;
  64   }
  65
  66   // Apply mask penalty rule 3 and return the penalty. Find consecutive cells of 00001011101 or
  67   // 10111010000, and give penalty to them.  If we find patterns like 000010111010000, we give
  68   // penalties twice (i.e. 40 * 2).
  69   public static int applyMaskPenaltyRule3(final ByteMatrix matrix) {
  70     int penalty = 0;
  71     byte[][] array = matrix.getArray();
  72     int width = matrix.width();
  73     int height = matrix.height();
  74     for (int y = 0; y < height; ++y) {
  75       for (int x = 0; x < width; ++x) {
  76         // Tried to simplify following conditions but failed.
  77         if (x + 6 < width &&
  78             array[y][x] == 1 &&
  79             array[y][x +  1] == 0 &&
  80             array[y][x +  2] == 1 &&
  81             array[y][x +  3] == 1 &&
  82             array[y][x +  4] == 1 &&
  83             array[y][x +  5] == 0 &&
  84             array[y][x +  6] == 1 &&
  85             ((x + 10 < width &&
  86                 array[y][x +  7] == 0 &&
  87                 array[y][x +  8] == 0 &&
  88                 array[y][x +  9] == 0 &&
  89                 array[y][x + 10] == 0) ||
  90                 (x - 4 >= 0 &&
  91                     array[y][x -  1] == 0 &&
  92                     array[y][x -  2] == 0 &&
  93                     array[y][x -  3] == 0 &&
  94                     array[y][x -  4] == 0))) {
  95           penalty += 40;
  96         }
  97         if (y + 6 < height &&
  98             array[y][x] == 1  &&
  99             array[y +  1][x] == 0  &&
 100             array[y +  2][x] == 1  &&
 101             array[y +  3][x] == 1  &&
 102             array[y +  4][x] == 1  &&
 103             array[y +  5][x] == 0  &&
 104             array[y +  6][x] == 1 &&
 105             ((y + 10 < height &&
 106                 array[y +  7][x] == 0 &&
 107                 array[y +  8][x] == 0 &&
 108                 array[y +  9][x] == 0 &&
 109                 array[y + 10][x] == 0) ||
 110                 (y - 4 >= 0 &&
 111                     array[y -  1][x] == 0 &&
 112                     array[y -  2][x] == 0 &&
 113                     array[y -  3][x] == 0 &&
 114                     array[y -  4][x] == 0))) {
 115           penalty += 40;
 116         }
 117       }
 118     }
 119     return penalty;
 120   }
 121
 122   // Apply mask penalty rule 4 and return the penalty. Calculate the ratio of dark cells and give
 123   // penalty if the ratio is far from 50%. It gives 10 penalty for 5% distance. Examples:
 124   // -   0% => 100
 125   // -  40% =>  20
 126   // -  45% =>  10
 127   // -  50% =>   0
 128   // -  55% =>  10
 129   // -  55% =>  20
 130   // - 100% => 100
 131   public static int applyMaskPenaltyRule4(final ByteMatrix matrix) {
 132     int numDarkCells = 0;
 133     byte[][] array = matrix.getArray();
 134     int width = matrix.width();
 135     int height = matrix.height();
 136     for (int y = 0; y < height; ++y) {
 137       for (int x = 0; x < width; ++x) {
 138         if (array[y][x] == 1) {
 139           numDarkCells += 1;
 140         }
 141       }
 142     }
 143     final int numTotalCells = matrix.height() * matrix.width();
 144     double darkRatio = (double) numDarkCells / numTotalCells;
 145     return Math.abs((int) (darkRatio * 100 - 50)) / 5 * 10;
 146   }
 147
 148   // Return the mask bit for "getMaskPattern" at "x" and "y". See 8.8 of JISX0510:2004 for mask
 149   // pattern conditions.
 150   public static int getDataMaskBit(final int maskPattern, final int x, final int y) {
 151     if (!QRCode.isValidMaskPattern(maskPattern)) {
 152       throw new IllegalArgumentException("Invalid mask pattern");
 153     }
 154     switch (maskPattern) {
 155       case 0:
 156         return ((y + x) % 2 == 0) ? 1 : 0;
 157       case 1:
 158         return (y % 2 == 0) ? 1 : 0;
 159       case 2:
 160         return (x % 3 == 0) ? 1 : 0;
 161       case 3:
 162         return ((y + x) % 3 == 0) ? 1 : 0;
 163       case 4:
 164         return (((y / 2) + (x / 3)) % 2 == 0) ? 1 : 0;
 165       case 5:
 166         return (((y * x) % 2) + ((y * x) % 3) == 0) ? 1 : 0;
 167       case 6:
 168         return ((((y * x) % 2) + ((y * x) % 3)) % 2 == 0) ? 1 : 0;
 169       case 7:
 170         return ((((y * x) % 3) + ((y + x) % 2)) % 2 == 0) ? 1 : 0;
 171     }
 172     throw new IllegalArgumentException("invalid mask pattern: " + maskPattern);
 173   }
 174
 175   // Helper function for applyMaskPenaltyRule1. We need this for doing this calculation in both
 176   // vertical and horizontal orders respectively.
 177   private static int applyMaskPenaltyRule1Internal(final ByteMatrix matrix, boolean isHorizontal) {
 178     int penalty = 0;
 179     int numSameBitCells = 0;
 180     int prevBit = -1;
 181     // Horizontal mode:
 182     //   for (int i = 0; i < matrix.height(); ++i) {
 183     //     for (int j = 0; j < matrix.width(); ++j) {
 184     //       int bit = matrix.get(i, j);
 185     // Vertical mode:
 186     //   for (int i = 0; i < matrix.width(); ++i) {
 187     //     for (int j = 0; j < matrix.height(); ++j) {
 188     //       int bit = matrix.get(j, i);
 189     final int iLimit = isHorizontal ? matrix.height() : matrix.width();
 190     final int jLimit = isHorizontal ? matrix.width() : matrix.height();
 191     byte[][] array = matrix.getArray();
 192     for (int i = 0; i < iLimit; ++i) {
 193       for (int j = 0; j < jLimit; ++j) {
 194         final int bit = isHorizontal ? array[i][j] : array[j][i];
 195         if (bit == prevBit) {
 196           numSameBitCells += 1;
 197           // Found five repetitive cells with the same color (bit).
 198           // We'll give penalty of 3.
 199           if (numSameBitCells == 5) {
 200             penalty += 3;
 201           } else if (numSameBitCells > 5) {
 202             // After five repetitive cells, we'll add the penalty one
 203             // by one.
 204             penalty += 1;
 205           }
 206         } else {
 207           numSameBitCells = 1;  // Include the cell itself.
 208           prevBit = bit;
 209         }
 210       }
 211       numSameBitCells = 0;  // Clear at each row/column.
 212     }
 213     return penalty;
 214   }
 215
 216 }