| 1 |
<?php |
| 2 |
/** |
| 3 |
* Class FinderPatternFinder |
| 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\Detector; |
| 14 |
|
| 15 |
use chillerlan\QRCode\Decoder\BitMatrix; |
| 16 |
use function abs, count, intdiv, usort; |
| 17 |
use const PHP_FLOAT_MAX; |
| 18 |
|
| 19 |
/** |
| 20 |
* This class attempts to find finder patterns in a QR Code. Finder patterns are the square |
| 21 |
* markers at three corners of a QR Code. |
| 22 |
* |
| 23 |
* This class is thread-safe but not reentrant. Each thread must allocate its own object. |
| 24 |
* |
| 25 |
* @author Sean Owen |
| 26 |
*/ |
| 27 |
final class FinderPatternFinder{ |
| 28 |
|
| 29 |
private const MIN_SKIP = 2; |
| 30 |
private const MAX_MODULES = 177; // 1 pixel/module times 3 modules/center |
| 31 |
private const CENTER_QUORUM = 2; // support up to version 10 for mobile clients |
| 32 |
/** @var int[] */ |
| 33 |
private const crossCheckStateCount = [0, 0, 0, 0, 0]; |
| 34 |
private BitMatrix $matrix; |
| 35 |
/** @var \chillerlan\QRCode\Detector\FinderPattern[] */ |
| 36 |
private array $possibleCenters; |
| 37 |
private bool $hasSkipped = false; |
| 38 |
|
| 39 |
/** |
| 40 |
* Creates a finder that will search the image for three finder patterns. |
| 41 |
* |
| 42 |
* @param BitMatrix $matrix image to search |
| 43 |
*/ |
| 44 |
public function __construct(BitMatrix $matrix){ |
| 45 |
$this->matrix = $matrix; |
| 46 |
$this->possibleCenters = []; |
| 47 |
} |
| 48 |
|
| 49 |
/** |
| 50 |
* @return \chillerlan\QRCode\Detector\FinderPattern[] |
| 51 |
*/ |
| 52 |
public function find():array{ |
| 53 |
$dimension = $this->matrix->getSize(); |
| 54 |
|
| 55 |
// We are looking for black/white/black/white/black modules in |
| 56 |
// 1:1:3:1:1 ratio; this tracks the number of such modules seen so far |
| 57 |
// Let's assume that the maximum version QR Code we support takes up 1/4 the height of the |
| 58 |
// image, and then account for the center being 3 modules in size. This gives the smallest |
| 59 |
// number of pixels the center could be, so skip this often. |
| 60 |
$iSkip = intdiv((3 * $dimension), (4 * self::MAX_MODULES)); |
| 61 |
|
| 62 |
if($iSkip < self::MIN_SKIP){ |
| 63 |
$iSkip = self::MIN_SKIP; |
| 64 |
} |
| 65 |
|
| 66 |
$done = false; |
| 67 |
|
| 68 |
for($i = ($iSkip - 1); ($i < $dimension) && !$done; $i += $iSkip){ |
| 69 |
// Get a row of black/white values |
| 70 |
$stateCount = self::crossCheckStateCount; |
| 71 |
$currentState = 0; |
| 72 |
|
| 73 |
for($j = 0; $j < $dimension; $j++){ |
| 74 |
|
| 75 |
// Black pixel |
| 76 |
if($this->matrix->check($j, $i)){ |
| 77 |
// Counting white pixels |
| 78 |
if(($currentState & 1) === 1){ |
| 79 |
$currentState++; |
| 80 |
} |
| 81 |
|
| 82 |
$stateCount[$currentState]++; |
| 83 |
} |
| 84 |
// White pixel |
| 85 |
else{ |
| 86 |
// Counting black pixels |
| 87 |
if(($currentState & 1) === 0){ |
| 88 |
// A winner? |
| 89 |
if($currentState === 4){ |
| 90 |
// Yes |
| 91 |
if($this->foundPatternCross($stateCount)){ |
| 92 |
$confirmed = $this->handlePossibleCenter($stateCount, $i, $j); |
| 93 |
|
| 94 |
if($confirmed){ |
| 95 |
// Start examining every other line. Checking each line turned out to be too |
| 96 |
// expensive and didn't improve performance. |
| 97 |
$iSkip = 3; |
| 98 |
|
| 99 |
if($this->hasSkipped){ |
| 100 |
$done = $this->haveMultiplyConfirmedCenters(); |
| 101 |
} |
| 102 |
else{ |
| 103 |
$rowSkip = $this->findRowSkip(); |
| 104 |
|
| 105 |
if($rowSkip > $stateCount[2]){ |
| 106 |
// Skip rows between row of lower confirmed center |
| 107 |
// and top of presumed third confirmed center |
| 108 |
// but back up a bit to get a full chance of detecting |
| 109 |
// it, entire width of center of finder pattern |
| 110 |
|
| 111 |
// Skip by rowSkip, but back off by $stateCount[2] (size of last center |
| 112 |
// of pattern we saw) to be conservative, and also back off by iSkip which |
| 113 |
// is about to be re-added |
| 114 |
$i += ($rowSkip - $stateCount[2] - $iSkip); |
| 115 |
$j = ($dimension - 1); |
| 116 |
} |
| 117 |
} |
| 118 |
} |
| 119 |
else{ |
| 120 |
$stateCount = $this->doShiftCounts2($stateCount); |
| 121 |
$currentState = 3; |
| 122 |
|
| 123 |
continue; |
| 124 |
} |
| 125 |
// Clear state to start looking again |
| 126 |
$currentState = 0; |
| 127 |
$stateCount = self::crossCheckStateCount; |
| 128 |
} |
| 129 |
// No, shift counts back by two |
| 130 |
else{ |
| 131 |
$stateCount = $this->doShiftCounts2($stateCount); |
| 132 |
$currentState = 3; |
| 133 |
} |
| 134 |
} |
| 135 |
else{ |
| 136 |
$stateCount[++$currentState]++; |
| 137 |
} |
| 138 |
} |
| 139 |
// Counting white pixels |
| 140 |
else{ |
| 141 |
$stateCount[$currentState]++; |
| 142 |
} |
| 143 |
} |
| 144 |
} |
| 145 |
|
| 146 |
if($this->foundPatternCross($stateCount)){ |
| 147 |
$confirmed = $this->handlePossibleCenter($stateCount, $i, $dimension); |
| 148 |
|
| 149 |
if($confirmed){ |
| 150 |
$iSkip = $stateCount[0]; |
| 151 |
|
| 152 |
if($this->hasSkipped){ |
| 153 |
// Found a third one |
| 154 |
$done = $this->haveMultiplyConfirmedCenters(); |
| 155 |
} |
| 156 |
} |
| 157 |
} |
| 158 |
} |
| 159 |
|
| 160 |
return $this->orderBestPatterns($this->selectBestPatterns()); |
| 161 |
} |
| 162 |
|
| 163 |
/** |
| 164 |
* @param int[] $stateCount |
| 165 |
* |
| 166 |
* @return int[] |
| 167 |
*/ |
| 168 |
private function doShiftCounts2(array $stateCount):array{ |
| 169 |
$stateCount[0] = $stateCount[2]; |
| 170 |
$stateCount[1] = $stateCount[3]; |
| 171 |
$stateCount[2] = $stateCount[4]; |
| 172 |
$stateCount[3] = 1; |
| 173 |
$stateCount[4] = 0; |
| 174 |
|
| 175 |
return $stateCount; |
| 176 |
} |
| 177 |
|
| 178 |
/** |
| 179 |
* Given a count of black/white/black/white/black pixels just seen and an end position, |
| 180 |
* figures the location of the center of this run. |
| 181 |
* |
| 182 |
* @param int[] $stateCount |
| 183 |
*/ |
| 184 |
private function centerFromEnd(array $stateCount, int $end):float{ |
| 185 |
return (float)(($end - $stateCount[4] - $stateCount[3]) - $stateCount[2] / 2); |
| 186 |
} |
| 187 |
|
| 188 |
/** |
| 189 |
* @param int[] $stateCount |
| 190 |
*/ |
| 191 |
private function foundPatternCross(array $stateCount):bool{ |
| 192 |
// Allow less than 50% variance from 1-1-3-1-1 proportions |
| 193 |
return $this->foundPatternVariance($stateCount, 2.0); |
| 194 |
} |
| 195 |
|
| 196 |
/** |
| 197 |
* @param int[] $stateCount |
| 198 |
*/ |
| 199 |
private function foundPatternDiagonal(array $stateCount):bool{ |
| 200 |
// Allow less than 75% variance from 1-1-3-1-1 proportions |
| 201 |
return $this->foundPatternVariance($stateCount, 1.333); |
| 202 |
} |
| 203 |
|
| 204 |
/** |
| 205 |
* @param int[] $stateCount count of black/white/black/white/black pixels just read |
| 206 |
* |
| 207 |
* @return bool true if the proportions of the counts is close enough to the 1/1/3/1/1 ratios |
| 208 |
* used by finder patterns to be considered a match |
| 209 |
*/ |
| 210 |
private function foundPatternVariance(array $stateCount, float $variance):bool{ |
| 211 |
$totalModuleSize = 0; |
| 212 |
|
| 213 |
for($i = 0; $i < 5; $i++){ |
| 214 |
$count = $stateCount[$i]; |
| 215 |
|
| 216 |
if($count === 0){ |
| 217 |
return false; |
| 218 |
} |
| 219 |
|
| 220 |
$totalModuleSize += $count; |
| 221 |
} |
| 222 |
|
| 223 |
if($totalModuleSize < 7){ |
| 224 |
return false; |
| 225 |
} |
| 226 |
|
| 227 |
$moduleSize = ($totalModuleSize / 7.0); |
| 228 |
$maxVariance = ($moduleSize / $variance); |
| 229 |
|
| 230 |
return |
| 231 |
abs($moduleSize - $stateCount[0]) < $maxVariance |
| 232 |
&& abs($moduleSize - $stateCount[1]) < $maxVariance |
| 233 |
&& abs(3.0 * $moduleSize - $stateCount[2]) < (3 * $maxVariance) |
| 234 |
&& abs($moduleSize - $stateCount[3]) < $maxVariance |
| 235 |
&& abs($moduleSize - $stateCount[4]) < $maxVariance; |
| 236 |
} |
| 237 |
|
| 238 |
/** |
| 239 |
* After a vertical and horizontal scan finds a potential finder pattern, this method |
| 240 |
* "cross-cross-cross-checks" by scanning down diagonally through the center of the possible |
| 241 |
* finder pattern to see if the same proportion is detected. |
| 242 |
* |
| 243 |
* @param int $centerI row where a finder pattern was detected |
| 244 |
* @param int $centerJ center of the section that appears to cross a finder pattern |
| 245 |
* |
| 246 |
* @return bool true if proportions are withing expected limits |
| 247 |
*/ |
| 248 |
private function crossCheckDiagonal(int $centerI, int $centerJ):bool{ |
| 249 |
$stateCount = self::crossCheckStateCount; |
| 250 |
|
| 251 |
// Start counting up, left from center finding black center mass |
| 252 |
$i = 0; |
| 253 |
|
| 254 |
while($centerI >= $i && $centerJ >= $i && $this->matrix->check(($centerJ - $i), ($centerI - $i))){ |
| 255 |
$stateCount[2]++; |
| 256 |
$i++; |
| 257 |
} |
| 258 |
|
| 259 |
if($stateCount[2] === 0){ |
| 260 |
return false; |
| 261 |
} |
| 262 |
|
| 263 |
// Continue up, left finding white space |
| 264 |
while($centerI >= $i && $centerJ >= $i && !$this->matrix->check(($centerJ - $i), ($centerI - $i))){ |
| 265 |
$stateCount[1]++; |
| 266 |
$i++; |
| 267 |
} |
| 268 |
|
| 269 |
if($stateCount[1] === 0){ |
| 270 |
return false; |
| 271 |
} |
| 272 |
|
| 273 |
// Continue up, left finding black border |
| 274 |
while($centerI >= $i && $centerJ >= $i && $this->matrix->check(($centerJ - $i), ($centerI - $i))){ |
| 275 |
$stateCount[0]++; |
| 276 |
$i++; |
| 277 |
} |
| 278 |
|
| 279 |
if($stateCount[0] === 0){ |
| 280 |
return false; |
| 281 |
} |
| 282 |
|
| 283 |
$dimension = $this->matrix->getSize(); |
| 284 |
|
| 285 |
// Now also count down, right from center |
| 286 |
$i = 1; |
| 287 |
// phpcs:ignore |
| 288 |
while(($centerI + $i) < $dimension && ($centerJ + $i) < $dimension && $this->matrix->check(($centerJ + $i), ($centerI + $i))){ |
| 289 |
$stateCount[2]++; |
| 290 |
$i++; |
| 291 |
} |
| 292 |
|
| 293 |
// phpcs:ignore |
| 294 |
while(($centerI + $i) < $dimension && ($centerJ + $i) < $dimension && !$this->matrix->check(($centerJ + $i), ($centerI + $i))){ |
| 295 |
$stateCount[3]++; |
| 296 |
$i++; |
| 297 |
} |
| 298 |
|
| 299 |
if($stateCount[3] === 0){ |
| 300 |
return false; |
| 301 |
} |
| 302 |
|
| 303 |
// phpcs:ignore |
| 304 |
while(($centerI + $i) < $dimension && ($centerJ + $i) < $dimension && $this->matrix->check(($centerJ + $i), ($centerI + $i))){ |
| 305 |
$stateCount[4]++; |
| 306 |
$i++; |
| 307 |
} |
| 308 |
|
| 309 |
if($stateCount[4] === 0){ |
| 310 |
return false; |
| 311 |
} |
| 312 |
|
| 313 |
return $this->foundPatternDiagonal($stateCount); |
| 314 |
} |
| 315 |
|
| 316 |
/** |
| 317 |
* After a horizontal scan finds a potential finder pattern, this method |
| 318 |
* "cross-checks" by scanning down vertically through the center of the possible |
| 319 |
* finder pattern to see if the same proportion is detected. |
| 320 |
* |
| 321 |
* $startI row where a finder pattern was detected |
| 322 |
* $centerJ center of the section that appears to cross a finder pattern |
| 323 |
* $maxCount maximum reasonable number of modules that should be |
| 324 |
* observed in any reading state, based on the results of the horizontal scan |
| 325 |
* $originalStateCountTotal |
| 326 |
* |
| 327 |
* returns vertical center of finder pattern, or null if not found |
| 328 |
* |
| 329 |
* @noinspection DuplicatedCode |
| 330 |
*/ |
| 331 |
private function crossCheckVertical(int $startI, int $centerJ, int $maxCount, int $originalStateCountTotal):float|null{ |
| 332 |
$maxI = $this->matrix->getSize(); |
| 333 |
$stateCount = self::crossCheckStateCount; |
| 334 |
|
| 335 |
// Start counting up from center |
| 336 |
$i = $startI; |
| 337 |
while($i >= 0 && $this->matrix->check($centerJ, $i)){ |
| 338 |
$stateCount[2]++; |
| 339 |
$i--; |
| 340 |
} |
| 341 |
|
| 342 |
if($i < 0){ |
| 343 |
return null; |
| 344 |
} |
| 345 |
|
| 346 |
while($i >= 0 && !$this->matrix->check($centerJ, $i) && $stateCount[1] <= $maxCount){ |
| 347 |
$stateCount[1]++; |
| 348 |
$i--; |
| 349 |
} |
| 350 |
|
| 351 |
// If already too many modules in this state or ran off the edge: |
| 352 |
if($i < 0 || $stateCount[1] > $maxCount){ |
| 353 |
return null; |
| 354 |
} |
| 355 |
|
| 356 |
while($i >= 0 && $this->matrix->check($centerJ, $i) && $stateCount[0] <= $maxCount){ |
| 357 |
$stateCount[0]++; |
| 358 |
$i--; |
| 359 |
} |
| 360 |
|
| 361 |
if($stateCount[0] > $maxCount){ |
| 362 |
return null; |
| 363 |
} |
| 364 |
|
| 365 |
// Now also count down from center |
| 366 |
$i = ($startI + 1); |
| 367 |
while($i < $maxI && $this->matrix->check($centerJ, $i)){ |
| 368 |
$stateCount[2]++; |
| 369 |
$i++; |
| 370 |
} |
| 371 |
|
| 372 |
if($i === $maxI){ |
| 373 |
return null; |
| 374 |
} |
| 375 |
|
| 376 |
while($i < $maxI && !$this->matrix->check($centerJ, $i) && $stateCount[3] < $maxCount){ |
| 377 |
$stateCount[3]++; |
| 378 |
$i++; |
| 379 |
} |
| 380 |
|
| 381 |
if($i === $maxI || $stateCount[3] >= $maxCount){ |
| 382 |
return null; |
| 383 |
} |
| 384 |
|
| 385 |
while($i < $maxI && $this->matrix->check($centerJ, $i) && $stateCount[4] < $maxCount){ |
| 386 |
$stateCount[4]++; |
| 387 |
$i++; |
| 388 |
} |
| 389 |
|
| 390 |
if($stateCount[4] >= $maxCount){ |
| 391 |
return null; |
| 392 |
} |
| 393 |
|
| 394 |
// If we found a finder-pattern-like section, but its size is more than 40% different from |
| 395 |
// the original, assume it's a false positive |
| 396 |
$stateCountTotal = ($stateCount[0] + $stateCount[1] + $stateCount[2] + $stateCount[3] + $stateCount[4]); |
| 397 |
|
| 398 |
if((5 * abs($stateCountTotal - $originalStateCountTotal)) >= (2 * $originalStateCountTotal)){ |
| 399 |
return null; |
| 400 |
} |
| 401 |
|
| 402 |
if(!$this->foundPatternCross($stateCount)){ |
| 403 |
return null; |
| 404 |
} |
| 405 |
|
| 406 |
return $this->centerFromEnd($stateCount, $i); |
| 407 |
} |
| 408 |
|
| 409 |
/** |
| 410 |
* Like #crossCheckVertical(int, int, int, int), and in fact is basically identical, |
| 411 |
* except it reads horizontally instead of vertically. This is used to cross-cross |
| 412 |
* check a vertical cross-check and locate the real center of the alignment pattern. |
| 413 |
* @noinspection DuplicatedCode |
| 414 |
*/ |
| 415 |
private function crossCheckHorizontal(int $startJ, int $centerI, int $maxCount, int $originalStateCountTotal):float|null{ |
| 416 |
$maxJ = $this->matrix->getSize(); |
| 417 |
$stateCount = self::crossCheckStateCount; |
| 418 |
|
| 419 |
$j = $startJ; |
| 420 |
while($j >= 0 && $this->matrix->check($j, $centerI)){ |
| 421 |
$stateCount[2]++; |
| 422 |
$j--; |
| 423 |
} |
| 424 |
|
| 425 |
if($j < 0){ |
| 426 |
return null; |
| 427 |
} |
| 428 |
|
| 429 |
while($j >= 0 && !$this->matrix->check($j, $centerI) && $stateCount[1] <= $maxCount){ |
| 430 |
$stateCount[1]++; |
| 431 |
$j--; |
| 432 |
} |
| 433 |
|
| 434 |
if($j < 0 || $stateCount[1] > $maxCount){ |
| 435 |
return null; |
| 436 |
} |
| 437 |
|
| 438 |
while($j >= 0 && $this->matrix->check($j, $centerI) && $stateCount[0] <= $maxCount){ |
| 439 |
$stateCount[0]++; |
| 440 |
$j--; |
| 441 |
} |
| 442 |
|
| 443 |
if($stateCount[0] > $maxCount){ |
| 444 |
return null; |
| 445 |
} |
| 446 |
|
| 447 |
$j = ($startJ + 1); |
| 448 |
while($j < $maxJ && $this->matrix->check($j, $centerI)){ |
| 449 |
$stateCount[2]++; |
| 450 |
$j++; |
| 451 |
} |
| 452 |
|
| 453 |
if($j === $maxJ){ |
| 454 |
return null; |
| 455 |
} |
| 456 |
|
| 457 |
while($j < $maxJ && !$this->matrix->check($j, $centerI) && $stateCount[3] < $maxCount){ |
| 458 |
$stateCount[3]++; |
| 459 |
$j++; |
| 460 |
} |
| 461 |
|
| 462 |
if($j === $maxJ || $stateCount[3] >= $maxCount){ |
| 463 |
return null; |
| 464 |
} |
| 465 |
|
| 466 |
while($j < $maxJ && $this->matrix->check($j, $centerI) && $stateCount[4] < $maxCount){ |
| 467 |
$stateCount[4]++; |
| 468 |
$j++; |
| 469 |
} |
| 470 |
|
| 471 |
if($stateCount[4] >= $maxCount){ |
| 472 |
return null; |
| 473 |
} |
| 474 |
|
| 475 |
// If we found a finder-pattern-like section, but its size is significantly different from |
| 476 |
// the original, assume it's a false positive |
| 477 |
$stateCountTotal = ($stateCount[0] + $stateCount[1] + $stateCount[2] + $stateCount[3] + $stateCount[4]); |
| 478 |
|
| 479 |
if((5 * abs($stateCountTotal - $originalStateCountTotal)) >= $originalStateCountTotal){ |
| 480 |
return null; |
| 481 |
} |
| 482 |
|
| 483 |
if(!$this->foundPatternCross($stateCount)){ |
| 484 |
return null; |
| 485 |
} |
| 486 |
|
| 487 |
return $this->centerFromEnd($stateCount, $j); |
| 488 |
} |
| 489 |
|
| 490 |
/** |
| 491 |
* This is called when a horizontal scan finds a possible alignment pattern. It will |
| 492 |
* cross-check with a vertical scan, and if successful, will, ah, cross-cross-check |
| 493 |
* with another horizontal scan. This is needed primarily to locate the real horizontal |
| 494 |
* center of the pattern in cases of extreme skew. |
| 495 |
* And then we cross-cross-cross check with another diagonal scan. |
| 496 |
* |
| 497 |
* If that succeeds the finder pattern location is added to a list that tracks |
| 498 |
* the number of times each location has been nearly-matched as a finder pattern. |
| 499 |
* Each additional find is more evidence that the location is in fact a finder |
| 500 |
* pattern center |
| 501 |
* |
| 502 |
* @param int[] $stateCount reading state module counts from horizontal scan |
| 503 |
* @param int $i row where finder pattern may be found |
| 504 |
* @param int $j end of possible finder pattern in row |
| 505 |
* |
| 506 |
* @return bool if a finder pattern candidate was found this time |
| 507 |
*/ |
| 508 |
private function handlePossibleCenter(array $stateCount, int $i, int $j):bool{ |
| 509 |
$stateCountTotal = ($stateCount[0] + $stateCount[1] + $stateCount[2] + $stateCount[3] + $stateCount[4]); |
| 510 |
$centerJ = $this->centerFromEnd($stateCount, $j); |
| 511 |
$centerI = $this->crossCheckVertical($i, (int)$centerJ, $stateCount[2], $stateCountTotal); |
| 512 |
|
| 513 |
if($centerI !== null){ |
| 514 |
// Re-cross check |
| 515 |
$centerJ = $this->crossCheckHorizontal((int)$centerJ, (int)$centerI, $stateCount[2], $stateCountTotal); |
| 516 |
if($centerJ !== null && ($this->crossCheckDiagonal((int)$centerI, (int)$centerJ))){ |
| 517 |
$estimatedModuleSize = ($stateCountTotal / 7.0); |
| 518 |
$found = false; |
| 519 |
|
| 520 |
// cautious (was in for fool in which $this->possibleCenters is updated) |
| 521 |
$count = count($this->possibleCenters); |
| 522 |
|
| 523 |
for($index = 0; $index < $count; $index++){ |
| 524 |
$center = $this->possibleCenters[$index]; |
| 525 |
// Look for about the same center and module size: |
| 526 |
if($center->aboutEquals($estimatedModuleSize, $centerI, $centerJ)){ |
| 527 |
$this->possibleCenters[$index] = $center->combineEstimate($centerI, $centerJ, $estimatedModuleSize); |
| 528 |
$found = true; |
| 529 |
break; |
| 530 |
} |
| 531 |
} |
| 532 |
|
| 533 |
if(!$found){ |
| 534 |
$point = new FinderPattern($centerJ, $centerI, $estimatedModuleSize); |
| 535 |
$this->possibleCenters[] = $point; |
| 536 |
} |
| 537 |
|
| 538 |
return true; |
| 539 |
} |
| 540 |
} |
| 541 |
|
| 542 |
return false; |
| 543 |
} |
| 544 |
|
| 545 |
/** |
| 546 |
* @return int number of rows we could safely skip during scanning, based on the first |
| 547 |
* two finder patterns that have been located. In some cases their position will |
| 548 |
* allow us to infer that the third pattern must lie below a certain point farther |
| 549 |
* down in the image. |
| 550 |
*/ |
| 551 |
private function findRowSkip():int{ |
| 552 |
$max = count($this->possibleCenters); |
| 553 |
|
| 554 |
if($max <= 1){ |
| 555 |
return 0; |
| 556 |
} |
| 557 |
|
| 558 |
$firstConfirmedCenter = null; |
| 559 |
|
| 560 |
foreach($this->possibleCenters as $center){ |
| 561 |
|
| 562 |
if($center->getCount() >= self::CENTER_QUORUM){ |
| 563 |
|
| 564 |
if($firstConfirmedCenter === null){ |
| 565 |
$firstConfirmedCenter = $center; |
| 566 |
} |
| 567 |
else{ |
| 568 |
// We have two confirmed centers |
| 569 |
// How far down can we skip before resuming looking for the next |
| 570 |
// pattern? In the worst case, only the difference between the |
| 571 |
// difference in the x / y coordinates of the two centers. |
| 572 |
// This is the case where you find top left last. |
| 573 |
$this->hasSkipped = true; |
| 574 |
|
| 575 |
return (int)((abs($firstConfirmedCenter->getX() - $center->getX()) - |
| 576 |
abs($firstConfirmedCenter->getY() - $center->getY())) / 2); |
| 577 |
} |
| 578 |
} |
| 579 |
} |
| 580 |
|
| 581 |
return 0; |
| 582 |
} |
| 583 |
|
| 584 |
/** |
| 585 |
* @return bool true if we have found at least 3 finder patterns that have been detected |
| 586 |
* at least #CENTER_QUORUM times each, and, the estimated module size of the |
| 587 |
* candidates is "pretty similar" |
| 588 |
*/ |
| 589 |
private function haveMultiplyConfirmedCenters():bool{ |
| 590 |
$confirmedCount = 0; |
| 591 |
$totalModuleSize = 0.0; |
| 592 |
$max = count($this->possibleCenters); |
| 593 |
|
| 594 |
foreach($this->possibleCenters as $pattern){ |
| 595 |
if($pattern->getCount() >= self::CENTER_QUORUM){ |
| 596 |
$confirmedCount++; |
| 597 |
$totalModuleSize += $pattern->getEstimatedModuleSize(); |
| 598 |
} |
| 599 |
} |
| 600 |
|
| 601 |
if($confirmedCount < 3){ |
| 602 |
return false; |
| 603 |
} |
| 604 |
// OK, we have at least 3 confirmed centers, but, it's possible that one is a "false positive" |
| 605 |
// and that we need to keep looking. We detect this by asking if the estimated module sizes |
| 606 |
// vary too much. We arbitrarily say that when the total deviation from average exceeds |
| 607 |
// 5% of the total module size estimates, it's too much. |
| 608 |
$average = ($totalModuleSize / (float)$max); |
| 609 |
$totalDeviation = 0.0; |
| 610 |
|
| 611 |
foreach($this->possibleCenters as $pattern){ |
| 612 |
$totalDeviation += abs($pattern->getEstimatedModuleSize() - $average); |
| 613 |
} |
| 614 |
|
| 615 |
return $totalDeviation <= (0.05 * $totalModuleSize); |
| 616 |
} |
| 617 |
|
| 618 |
/** |
| 619 |
* @return \chillerlan\QRCode\Detector\FinderPattern[] the 3 best FinderPatterns from our list of candidates. The "best" are |
| 620 |
* those that have been detected at least #CENTER_QUORUM times, and whose module |
| 621 |
* size differs from the average among those patterns the least |
| 622 |
* @throws \chillerlan\QRCode\Detector\QRCodeDetectorException if 3 such finder patterns do not exist |
| 623 |
*/ |
| 624 |
private function selectBestPatterns():array{ |
| 625 |
$startSize = count($this->possibleCenters); |
| 626 |
|
| 627 |
if($startSize < 3){ |
| 628 |
throw new QRCodeDetectorException('could not find enough finder patterns'); |
| 629 |
} |
| 630 |
|
| 631 |
usort( |
| 632 |
$this->possibleCenters, |
| 633 |
fn(FinderPattern $a, FinderPattern $b) => ($a->getEstimatedModuleSize() <=> $b->getEstimatedModuleSize()), |
| 634 |
); |
| 635 |
|
| 636 |
$distortion = PHP_FLOAT_MAX; |
| 637 |
$bestPatterns = []; |
| 638 |
|
| 639 |
for($i = 0; $i < ($startSize - 2); $i++){ |
| 640 |
$fpi = $this->possibleCenters[$i]; |
| 641 |
$minModuleSize = $fpi->getEstimatedModuleSize(); |
| 642 |
|
| 643 |
for($j = ($i + 1); $j < ($startSize - 1); $j++){ |
| 644 |
$fpj = $this->possibleCenters[$j]; |
| 645 |
$squares0 = $fpi->getSquaredDistance($fpj); |
| 646 |
|
| 647 |
for($k = ($j + 1); $k < $startSize; $k++){ |
| 648 |
$fpk = $this->possibleCenters[$k]; |
| 649 |
$maxModuleSize = $fpk->getEstimatedModuleSize(); |
| 650 |
|
| 651 |
// module size is not similar |
| 652 |
if($maxModuleSize > ($minModuleSize * 1.4)){ |
| 653 |
continue; |
| 654 |
} |
| 655 |
|
| 656 |
$a = $squares0; |
| 657 |
$b = $fpj->getSquaredDistance($fpk); |
| 658 |
$c = $fpi->getSquaredDistance($fpk); |
| 659 |
|
| 660 |
// sorts ascending - inlined |
| 661 |
if($a < $b){ |
| 662 |
if($b > $c){ |
| 663 |
if($a < $c){ |
| 664 |
$temp = $b; |
| 665 |
$b = $c; |
| 666 |
$c = $temp; |
| 667 |
} |
| 668 |
else{ |
| 669 |
$temp = $a; |
| 670 |
$a = $c; |
| 671 |
$c = $b; |
| 672 |
$b = $temp; |
| 673 |
} |
| 674 |
} |
| 675 |
} |
| 676 |
else{ |
| 677 |
if($b < $c){ |
| 678 |
if($a < $c){ |
| 679 |
$temp = $a; |
| 680 |
$a = $b; |
| 681 |
$b = $temp; |
| 682 |
} |
| 683 |
else{ |
| 684 |
$temp = $a; |
| 685 |
$a = $b; |
| 686 |
$b = $c; |
| 687 |
$c = $temp; |
| 688 |
} |
| 689 |
} |
| 690 |
else{ |
| 691 |
$temp = $a; |
| 692 |
$a = $c; |
| 693 |
$c = $temp; |
| 694 |
} |
| 695 |
} |
| 696 |
|
| 697 |
// a^2 + b^2 = c^2 (Pythagorean theorem), and a = b (isosceles triangle). |
| 698 |
// Since any right triangle satisfies the formula c^2 - b^2 - a^2 = 0, |
| 699 |
// we need to check both two equal sides separately. |
| 700 |
// The value of |c^2 - 2 * b^2| + |c^2 - 2 * a^2| increases as dissimilarity |
| 701 |
// from isosceles right triangle. |
| 702 |
$d = (abs($c - 2 * $b) + abs($c - 2 * $a)); |
| 703 |
|
| 704 |
if($d < $distortion){ |
| 705 |
$distortion = $d; |
| 706 |
$bestPatterns = [$fpi, $fpj, $fpk]; |
| 707 |
} |
| 708 |
} |
| 709 |
} |
| 710 |
} |
| 711 |
|
| 712 |
if($distortion === PHP_FLOAT_MAX){ |
| 713 |
throw new QRCodeDetectorException('finder patterns may be too distorted'); |
| 714 |
} |
| 715 |
|
| 716 |
return $bestPatterns; |
| 717 |
} |
| 718 |
|
| 719 |
/** |
| 720 |
* Orders an array of three ResultPoints in an order [A,B,C] such that AB is less than AC |
| 721 |
* and BC is less than AC, and the angle between BC and BA is less than 180 degrees. |
| 722 |
* |
| 723 |
* @param \chillerlan\QRCode\Detector\FinderPattern[] $patterns array of three FinderPattern to order |
| 724 |
* |
| 725 |
* @return \chillerlan\QRCode\Detector\FinderPattern[] |
| 726 |
*/ |
| 727 |
private function orderBestPatterns(array $patterns):array{ |
| 728 |
|
| 729 |
// Find distances between pattern centers |
| 730 |
$zeroOneDistance = $patterns[0]->getDistance($patterns[1]); |
| 731 |
$oneTwoDistance = $patterns[1]->getDistance($patterns[2]); |
| 732 |
$zeroTwoDistance = $patterns[0]->getDistance($patterns[2]); |
| 733 |
|
| 734 |
// Assume one closest to other two is B; A and C will just be guesses at first |
| 735 |
if($oneTwoDistance >= $zeroOneDistance && $oneTwoDistance >= $zeroTwoDistance){ |
| 736 |
[$pointB, $pointA, $pointC] = $patterns; |
| 737 |
} |
| 738 |
elseif($zeroTwoDistance >= $oneTwoDistance && $zeroTwoDistance >= $zeroOneDistance){ |
| 739 |
[$pointA, $pointB, $pointC] = $patterns; |
| 740 |
} |
| 741 |
else{ |
| 742 |
[$pointA, $pointC, $pointB] = $patterns; |
| 743 |
} |
| 744 |
|
| 745 |
// Use cross product to figure out whether A and C are correct or flipped. |
| 746 |
// This asks whether BC x BA has a positive z component, which is the arrangement |
| 747 |
// we want for A, B, C. If it's negative, then we've got it flipped around and |
| 748 |
// should swap A and C. |
| 749 |
if($this->crossProductZ($pointA, $pointB, $pointC) < 0.0){ |
| 750 |
$temp = $pointA; |
| 751 |
$pointA = $pointC; |
| 752 |
$pointC = $temp; |
| 753 |
} |
| 754 |
|
| 755 |
return [$pointA, $pointB, $pointC]; |
| 756 |
} |
| 757 |
|
| 758 |
/** |
| 759 |
* Returns the z component of the cross product between vectors BC and BA. |
| 760 |
*/ |
| 761 |
private function crossProductZ(FinderPattern $pointA, FinderPattern $pointB, FinderPattern $pointC):float{ |
| 762 |
$bX = $pointB->getX(); |
| 763 |
$bY = $pointB->getY(); |
| 764 |
|
| 765 |
return ((($pointC->getX() - $bX) * ($pointA->getY() - $bY)) - (($pointC->getY() - $bY) * ($pointA->getX() - $bX))); |
| 766 |
} |
| 767 |
|
| 768 |
} |