| 1 |
<?php |
| 2 |
|
| 3 |
/** |
| 4 |
* Class Binarizer |
| 5 |
* |
| 6 |
* @created 17.01.2021 |
| 7 |
* @author ZXing Authors |
| 8 |
* @author Smiley <smiley@chillerlan.net> |
| 9 |
* @copyright 2021 Smiley |
| 10 |
* @license Apache-2.0 |
| 11 |
*/ |
| 12 |
namespace WCPOS\Vendor\chillerlan\QRCode\Decoder; |
| 13 |
|
| 14 |
use WCPOS\Vendor\chillerlan\QRCode\Common\LuminanceSourceInterface; |
| 15 |
use WCPOS\Vendor\chillerlan\QRCode\Data\QRMatrix; |
| 16 |
use function array_fill, count, intdiv, max; |
| 17 |
/** |
| 18 |
* This class implements a local thresholding algorithm, which while slower than the |
| 19 |
* GlobalHistogramBinarizer, is fairly efficient for what it does. It is designed for |
| 20 |
* high frequency images of barcodes with black data on white backgrounds. For this application, |
| 21 |
* it does a much better job than a global blackpoint with severe shadows and gradients. |
| 22 |
* However, it tends to produce artifacts on lower frequency images and is therefore not |
| 23 |
* a good general purpose binarizer for uses outside ZXing. |
| 24 |
* |
| 25 |
* This class extends GlobalHistogramBinarizer, using the older histogram approach for 1D readers, |
| 26 |
* and the newer local approach for 2D readers. 1D decoding using a per-row histogram is already |
| 27 |
* inherently local, and only fails for horizontal gradients. We can revisit that problem later, |
| 28 |
* but for now it was not a win to use local blocks for 1D. |
| 29 |
* |
| 30 |
* This Binarizer is the default for the unit tests and the recommended class for library users. |
| 31 |
* |
| 32 |
* @author dswitkin@google.com (Daniel Switkin) |
| 33 |
*/ |
| 34 |
final class Binarizer |
| 35 |
{ |
| 36 |
// This class uses 5x5 blocks to compute local luminance, where each block is 8x8 pixels. |
| 37 |
// So this is the smallest dimension in each axis we can accept. |
| 38 |
private const BLOCK_SIZE_POWER = 3; |
| 39 |
private const BLOCK_SIZE = 8; |
| 40 |
// ...0100...00 |
| 41 |
private const BLOCK_SIZE_MASK = 7; |
| 42 |
// ...0011...11 |
| 43 |
private const MINIMUM_DIMENSION = 40; |
| 44 |
private const MIN_DYNAMIC_RANGE = 24; |
| 45 |
# private const LUMINANCE_BITS = 5; |
| 46 |
private const LUMINANCE_SHIFT = 3; |
| 47 |
private const LUMINANCE_BUCKETS = 32; |
| 48 |
private LuminanceSourceInterface $source; |
| 49 |
private array $luminances; |
| 50 |
/** |
| 51 |
* |
| 52 |
*/ |
| 53 |
public function __construct(LuminanceSourceInterface $source) |
| 54 |
{ |
| 55 |
$this->source = $source; |
| 56 |
$this->luminances = $this->source->getLuminances(); |
| 57 |
} |
| 58 |
/** |
| 59 |
* @throws \chillerlan\QRCode\Decoder\QRCodeDecoderException |
| 60 |
*/ |
| 61 |
private function estimateBlackPoint(array $buckets) : int |
| 62 |
{ |
| 63 |
// Find the tallest peak in the histogram. |
| 64 |
$numBuckets = count($buckets); |
| 65 |
$maxBucketCount = 0; |
| 66 |
$firstPeak = 0; |
| 67 |
$firstPeakSize = 0; |
| 68 |
for ($x = 0; $x < $numBuckets; $x++) { |
| 69 |
if ($buckets[$x] > $firstPeakSize) { |
| 70 |
$firstPeak = $x; |
| 71 |
$firstPeakSize = $buckets[$x]; |
| 72 |
} |
| 73 |
if ($buckets[$x] > $maxBucketCount) { |
| 74 |
$maxBucketCount = $buckets[$x]; |
| 75 |
} |
| 76 |
} |
| 77 |
// Find the second-tallest peak which is somewhat far from the tallest peak. |
| 78 |
$secondPeak = 0; |
| 79 |
$secondPeakScore = 0; |
| 80 |
for ($x = 0; $x < $numBuckets; $x++) { |
| 81 |
$distanceToBiggest = $x - $firstPeak; |
| 82 |
// Encourage more distant second peaks by multiplying by square of distance. |
| 83 |
$score = $buckets[$x] * $distanceToBiggest * $distanceToBiggest; |
| 84 |
if ($score > $secondPeakScore) { |
| 85 |
$secondPeak = $x; |
| 86 |
$secondPeakScore = $score; |
| 87 |
} |
| 88 |
} |
| 89 |
// Make sure firstPeak corresponds to the black peak. |
| 90 |
if ($firstPeak > $secondPeak) { |
| 91 |
$temp = $firstPeak; |
| 92 |
$firstPeak = $secondPeak; |
| 93 |
$secondPeak = $temp; |
| 94 |
} |
| 95 |
// If there is too little contrast in the image to pick a meaningful black point, throw rather |
| 96 |
// than waste time trying to decode the image, and risk false positives. |
| 97 |
if ($secondPeak - $firstPeak <= $numBuckets / 16) { |
| 98 |
throw new QRCodeDecoderException('no meaningful dark point found'); |
| 99 |
// @codeCoverageIgnore |
| 100 |
} |
| 101 |
// Find a valley between them that is low and closer to the white peak. |
| 102 |
$bestValley = $secondPeak - 1; |
| 103 |
$bestValleyScore = -1; |
| 104 |
for ($x = $secondPeak - 1; $x > $firstPeak; $x--) { |
| 105 |
$fromFirst = $x - $firstPeak; |
| 106 |
$score = $fromFirst * $fromFirst * ($secondPeak - $x) * ($maxBucketCount - $buckets[$x]); |
| 107 |
if ($score > $bestValleyScore) { |
| 108 |
$bestValley = $x; |
| 109 |
$bestValleyScore = $score; |
| 110 |
} |
| 111 |
} |
| 112 |
return $bestValley << self::LUMINANCE_SHIFT; |
| 113 |
} |
| 114 |
/** |
| 115 |
* Calculates the final BitMatrix once for all requests. This could be called once from the |
| 116 |
* constructor instead, but there are some advantages to doing it lazily, such as making |
| 117 |
* profiling easier, and not doing heavy lifting when callers don't expect it. |
| 118 |
* |
| 119 |
* Converts a 2D array of luminance data to 1 bit data. As above, assume this method is expensive |
| 120 |
* and do not call it repeatedly. This method is intended for decoding 2D barcodes and may or |
| 121 |
* may not apply sharpening. Therefore, a row from this matrix may not be identical to one |
| 122 |
* fetched using getBlackRow(), so don't mix and match between them. |
| 123 |
* |
| 124 |
* @return \chillerlan\QRCode\Decoder\BitMatrix The 2D array of bits for the image (true means black). |
| 125 |
*/ |
| 126 |
public function getBlackMatrix() : BitMatrix |
| 127 |
{ |
| 128 |
$width = $this->source->getWidth(); |
| 129 |
$height = $this->source->getHeight(); |
| 130 |
if ($width >= self::MINIMUM_DIMENSION && $height >= self::MINIMUM_DIMENSION) { |
| 131 |
$subWidth = $width >> self::BLOCK_SIZE_POWER; |
| 132 |
if (($width & self::BLOCK_SIZE_MASK) !== 0) { |
| 133 |
$subWidth++; |
| 134 |
} |
| 135 |
$subHeight = $height >> self::BLOCK_SIZE_POWER; |
| 136 |
if (($height & self::BLOCK_SIZE_MASK) !== 0) { |
| 137 |
$subHeight++; |
| 138 |
} |
| 139 |
return $this->calculateThresholdForBlock($subWidth, $subHeight, $width, $height); |
| 140 |
} |
| 141 |
// If the image is too small, fall back to the global histogram approach. |
| 142 |
return $this->getHistogramBlackMatrix($width, $height); |
| 143 |
} |
| 144 |
/** |
| 145 |
* |
| 146 |
*/ |
| 147 |
private function getHistogramBlackMatrix(int $width, int $height) : BitMatrix |
| 148 |
{ |
| 149 |
// Quickly calculates the histogram by sampling four rows from the image. This proved to be |
| 150 |
// more robust on the blackbox tests than sampling a diagonal as we used to do. |
| 151 |
$buckets = array_fill(0, self::LUMINANCE_BUCKETS, 0); |
| 152 |
$right = intdiv($width * 4, 5); |
| 153 |
$x = intdiv($width, 5); |
| 154 |
for ($y = 1; $y < 5; $y++) { |
| 155 |
$row = intdiv($height * $y, 5); |
| 156 |
$localLuminances = $this->source->getRow($row); |
| 157 |
for (; $x < $right; $x++) { |
| 158 |
$pixel = $localLuminances[$x] & 0xff; |
| 159 |
$buckets[$pixel >> self::LUMINANCE_SHIFT]++; |
| 160 |
} |
| 161 |
} |
| 162 |
$blackPoint = $this->estimateBlackPoint($buckets); |
| 163 |
// We delay reading the entire image luminance until the black point estimation succeeds. |
| 164 |
// Although we end up reading four rows twice, it is consistent with our motto of |
| 165 |
// "fail quickly" which is necessary for continuous scanning. |
| 166 |
$matrix = new BitMatrix(max($width, $height)); |
| 167 |
for ($y = 0; $y < $height; $y++) { |
| 168 |
$offset = $y * $width; |
| 169 |
for ($x = 0; $x < $width; $x++) { |
| 170 |
$matrix->set($x, $y, ($this->luminances[$offset + $x] & 0xff) < $blackPoint, QRMatrix::M_DATA); |
| 171 |
} |
| 172 |
} |
| 173 |
return $matrix; |
| 174 |
} |
| 175 |
/** |
| 176 |
* Calculates a single black point for each block of pixels and saves it away. |
| 177 |
* See the following thread for a discussion of this algorithm: |
| 178 |
* |
| 179 |
* @see http://groups.google.com/group/zxing/browse_thread/thread/d06efa2c35a7ddc0 |
| 180 |
*/ |
| 181 |
private function calculateBlackPoints(int $subWidth, int $subHeight, int $width, int $height) : array |
| 182 |
{ |
| 183 |
$blackPoints = array_fill(0, $subHeight, array_fill(0, $subWidth, 0)); |
| 184 |
for ($y = 0; $y < $subHeight; $y++) { |
| 185 |
$yoffset = $y << self::BLOCK_SIZE_POWER; |
| 186 |
$maxYOffset = $height - self::BLOCK_SIZE; |
| 187 |
if ($yoffset > $maxYOffset) { |
| 188 |
$yoffset = $maxYOffset; |
| 189 |
} |
| 190 |
for ($x = 0; $x < $subWidth; $x++) { |
| 191 |
$xoffset = $x << self::BLOCK_SIZE_POWER; |
| 192 |
$maxXOffset = $width - self::BLOCK_SIZE; |
| 193 |
if ($xoffset > $maxXOffset) { |
| 194 |
$xoffset = $maxXOffset; |
| 195 |
} |
| 196 |
$sum = 0; |
| 197 |
$min = 255; |
| 198 |
$max = 0; |
| 199 |
for ($yy = 0, $offset = $yoffset * $width + $xoffset; $yy < self::BLOCK_SIZE; $yy++, $offset += $width) { |
| 200 |
for ($xx = 0; $xx < self::BLOCK_SIZE; $xx++) { |
| 201 |
$pixel = (int) $this->luminances[(int) ($offset + $xx)] & 0xff; |
| 202 |
$sum += $pixel; |
| 203 |
// still looking for good contrast |
| 204 |
if ($pixel < $min) { |
| 205 |
$min = $pixel; |
| 206 |
} |
| 207 |
if ($pixel > $max) { |
| 208 |
$max = $pixel; |
| 209 |
} |
| 210 |
} |
| 211 |
// short-circuit min/max tests once dynamic range is met |
| 212 |
if ($max - $min > self::MIN_DYNAMIC_RANGE) { |
| 213 |
// finish the rest of the rows quickly |
| 214 |
for ($yy++, $offset += $width; $yy < self::BLOCK_SIZE; $yy++, $offset += $width) { |
| 215 |
for ($xx = 0; $xx < self::BLOCK_SIZE; $xx++) { |
| 216 |
$sum += (int) $this->luminances[(int) ($offset + $xx)] & 0xff; |
| 217 |
} |
| 218 |
} |
| 219 |
} |
| 220 |
} |
| 221 |
// The default estimate is the average of the values in the block. |
| 222 |
$average = $sum >> self::BLOCK_SIZE_POWER * 2; |
| 223 |
if ($max - $min <= self::MIN_DYNAMIC_RANGE) { |
| 224 |
// If variation within the block is low, assume this is a block with only light or only |
| 225 |
// dark pixels. In that case we do not want to use the average, as it would divide this |
| 226 |
// low contrast area into black and white pixels, essentially creating data out of noise. |
| 227 |
// |
| 228 |
// The default assumption is that the block is light/background. Since no estimate for |
| 229 |
// the level of dark pixels exists locally, use half the min for the block. |
| 230 |
$average = $min / 2; |
| 231 |
if ($y > 0 && $x > 0) { |
| 232 |
// Correct the "white background" assumption for blocks that have neighbors by comparing |
| 233 |
// the pixels in this block to the previously calculated black points. This is based on |
| 234 |
// the fact that dark barcode symbology is always surrounded by some amount of light |
| 235 |
// background for which reasonable black point estimates were made. The bp estimated at |
| 236 |
// the boundaries is used for the interior. |
| 237 |
// The (min < bp) is arbitrary but works better than other heuristics that were tried. |
| 238 |
$averageNeighborBlackPoint = ($blackPoints[$y - 1][$x] + 2 * $blackPoints[$y][$x - 1] + $blackPoints[$y - 1][$x - 1]) / 4; |
| 239 |
if ($min < $averageNeighborBlackPoint) { |
| 240 |
$average = $averageNeighborBlackPoint; |
| 241 |
} |
| 242 |
} |
| 243 |
} |
| 244 |
$blackPoints[$y][$x] = $average; |
| 245 |
} |
| 246 |
} |
| 247 |
return $blackPoints; |
| 248 |
} |
| 249 |
/** |
| 250 |
* For each block in the image, calculate the average black point using a 5x5 grid |
| 251 |
* of the surrounding blocks. Also handles the corner cases (fractional blocks are computed based |
| 252 |
* on the last pixels in the row/column which are also used in the previous block). |
| 253 |
*/ |
| 254 |
private function calculateThresholdForBlock(int $subWidth, int $subHeight, int $width, int $height) : BitMatrix |
| 255 |
{ |
| 256 |
$matrix = new BitMatrix(max($width, $height)); |
| 257 |
$blackPoints = $this->calculateBlackPoints($subWidth, $subHeight, $width, $height); |
| 258 |
for ($y = 0; $y < $subHeight; $y++) { |
| 259 |
$yoffset = $y << self::BLOCK_SIZE_POWER; |
| 260 |
$maxYOffset = $height - self::BLOCK_SIZE; |
| 261 |
if ($yoffset > $maxYOffset) { |
| 262 |
$yoffset = $maxYOffset; |
| 263 |
} |
| 264 |
for ($x = 0; $x < $subWidth; $x++) { |
| 265 |
$xoffset = $x << self::BLOCK_SIZE_POWER; |
| 266 |
$maxXOffset = $width - self::BLOCK_SIZE; |
| 267 |
if ($xoffset > $maxXOffset) { |
| 268 |
$xoffset = $maxXOffset; |
| 269 |
} |
| 270 |
$left = $this->cap($x, 2, $subWidth - 3); |
| 271 |
$top = $this->cap($y, 2, $subHeight - 3); |
| 272 |
$sum = 0; |
| 273 |
for ($z = -2; $z <= 2; $z++) { |
| 274 |
$br = $blackPoints[$top + $z]; |
| 275 |
$sum += $br[$left - 2] + $br[$left - 1] + $br[$left] + $br[$left + 1] + $br[$left + 2]; |
| 276 |
} |
| 277 |
$average = (int) ($sum / 25); |
| 278 |
// Applies a single threshold to a block of pixels. |
| 279 |
for ($j = 0, $o = $yoffset * $width + $xoffset; $j < self::BLOCK_SIZE; $j++, $o += $width) { |
| 280 |
for ($i = 0; $i < self::BLOCK_SIZE; $i++) { |
| 281 |
// Comparison needs to be <= so that black == 0 pixels are black even if the threshold is 0. |
| 282 |
$v = ((int) $this->luminances[$o + $i] & 0xff) <= $average; |
| 283 |
$matrix->set($xoffset + $i, $yoffset + $j, $v, QRMatrix::M_DATA); |
| 284 |
} |
| 285 |
} |
| 286 |
} |
| 287 |
} |
| 288 |
return $matrix; |
| 289 |
} |
| 290 |
/** |
| 291 |
* @noinspection PhpSameParameterValueInspection |
| 292 |
*/ |
| 293 |
private function cap(int $value, int $min, int $max) : int |
| 294 |
{ |
| 295 |
if ($value < $min) { |
| 296 |
return $min; |
| 297 |
} |
| 298 |
if ($value > $max) { |
| 299 |
return $max; |
| 300 |
} |
| 301 |
return $value; |
| 302 |
} |
| 303 |
} |
| 304 |
|
