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