Debian Codegraph @

vendor/chillerlan/php-qrcode/src/Decoder/Binarizer.php

raw
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 }