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