| 1 |
<?php |
| 2 |
/** |
| 3 |
* Class AlignmentPatternFinder |
| 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; |
| 17 |
|
| 18 |
/** |
| 19 |
* This class attempts to find alignment patterns in a QR Code. Alignment patterns look like finder |
| 20 |
* patterns but are smaller and appear at regular intervals throughout the image. |
| 21 |
* |
| 22 |
* At the moment this only looks for the bottom-right alignment pattern. |
| 23 |
* |
| 24 |
* This is mostly a simplified copy of FinderPatternFinder. It is copied, |
| 25 |
* pasted and stripped down here for maximum performance but does unfortunately duplicate |
| 26 |
* some code. |
| 27 |
* |
| 28 |
* This class is thread-safe but not reentrant. Each thread must allocate its own object. |
| 29 |
* |
| 30 |
* @author Sean Owen |
| 31 |
*/ |
| 32 |
final class AlignmentPatternFinder{ |
| 33 |
|
| 34 |
private BitMatrix $matrix; |
| 35 |
private float $moduleSize; |
| 36 |
/** @var \chillerlan\QRCode\Detector\AlignmentPattern[] */ |
| 37 |
private array $possibleCenters; |
| 38 |
|
| 39 |
/** |
| 40 |
* Creates a finder that will look in a portion of the whole image. |
| 41 |
* |
| 42 |
* @param \chillerlan\QRCode\Decoder\BitMatrix $matrix image to search |
| 43 |
* @param float $moduleSize estimated module size so far |
| 44 |
*/ |
| 45 |
public function __construct(BitMatrix $matrix, float $moduleSize){ |
| 46 |
$this->matrix = $matrix; |
| 47 |
$this->moduleSize = $moduleSize; |
| 48 |
$this->possibleCenters = []; |
| 49 |
} |
| 50 |
|
| 51 |
/** |
| 52 |
* This method attempts to find the bottom-right alignment pattern in the image. It is a bit messy since |
| 53 |
* it's pretty performance-critical and so is written to be fast foremost. |
| 54 |
* |
| 55 |
* @param int $startX left column from which to start searching |
| 56 |
* @param int $startY top row from which to start searching |
| 57 |
* @param int $width width of region to search |
| 58 |
* @param int $height height of region to search |
| 59 |
* |
| 60 |
* @return \chillerlan\QRCode\Detector\AlignmentPattern|null |
| 61 |
*/ |
| 62 |
public function find(int $startX, int $startY, int $width, int $height):AlignmentPattern|null{ |
| 63 |
$maxJ = ($startX + $width); |
| 64 |
$middleI = ($startY + ($height / 2)); |
| 65 |
/** @var int[] $stateCount */ |
| 66 |
$stateCount = []; |
| 67 |
|
| 68 |
// We are looking for black/white/black modules in 1:1:1 ratio; |
| 69 |
// this tracks the number of black/white/black modules seen so far |
| 70 |
for($iGen = 0; $iGen < $height; $iGen++){ |
| 71 |
// Search from middle outwards |
| 72 |
$i = (int)($middleI + ((($iGen & 0x01) === 0) ? ($iGen + 1) / 2 : -(($iGen + 1) / 2))); |
| 73 |
$stateCount[0] = 0; |
| 74 |
$stateCount[1] = 0; |
| 75 |
$stateCount[2] = 0; |
| 76 |
$j = $startX; |
| 77 |
// Burn off leading white pixels before anything else; if we start in the middle of |
| 78 |
// a white run, it doesn't make sense to count its length, since we don't know if the |
| 79 |
// white run continued to the left of the start point |
| 80 |
while($j < $maxJ && !$this->matrix->check($j, $i)){ |
| 81 |
$j++; |
| 82 |
} |
| 83 |
|
| 84 |
$currentState = 0; |
| 85 |
|
| 86 |
while($j < $maxJ){ |
| 87 |
|
| 88 |
if($this->matrix->check($j, $i)){ |
| 89 |
// Black pixel |
| 90 |
if($currentState === 1){ // Counting black pixels |
| 91 |
$stateCount[$currentState]++; |
| 92 |
} |
| 93 |
// Counting white pixels |
| 94 |
else{ |
| 95 |
// A winner? |
| 96 |
if($currentState === 2){ |
| 97 |
// Yes |
| 98 |
if($this->foundPatternCross($stateCount)){ |
| 99 |
$confirmed = $this->handlePossibleCenter($stateCount, $i, $j); |
| 100 |
|
| 101 |
if($confirmed !== null){ |
| 102 |
return $confirmed; |
| 103 |
} |
| 104 |
} |
| 105 |
|
| 106 |
$stateCount[0] = $stateCount[2]; |
| 107 |
$stateCount[1] = 1; |
| 108 |
$stateCount[2] = 0; |
| 109 |
$currentState = 1; |
| 110 |
} |
| 111 |
else{ |
| 112 |
$stateCount[++$currentState]++; |
| 113 |
} |
| 114 |
} |
| 115 |
} |
| 116 |
// White pixel |
| 117 |
else{ |
| 118 |
// Counting black pixels |
| 119 |
if($currentState === 1){ |
| 120 |
$currentState++; |
| 121 |
} |
| 122 |
|
| 123 |
$stateCount[$currentState]++; |
| 124 |
} |
| 125 |
|
| 126 |
$j++; |
| 127 |
} |
| 128 |
|
| 129 |
if($this->foundPatternCross($stateCount)){ |
| 130 |
$confirmed = $this->handlePossibleCenter($stateCount, $i, $maxJ); |
| 131 |
|
| 132 |
if($confirmed !== null){ |
| 133 |
return $confirmed; |
| 134 |
} |
| 135 |
} |
| 136 |
|
| 137 |
} |
| 138 |
|
| 139 |
// Hmm, nothing we saw was observed and confirmed twice. If we had |
| 140 |
// any guess at all, return it. |
| 141 |
if(count($this->possibleCenters)){ |
| 142 |
return $this->possibleCenters[0]; |
| 143 |
} |
| 144 |
|
| 145 |
return null; |
| 146 |
} |
| 147 |
|
| 148 |
/** |
| 149 |
* @param int[] $stateCount count of black/white/black pixels just read |
| 150 |
* |
| 151 |
* @return bool true if the proportions of the counts is close enough to the 1/1/1 ratios |
| 152 |
* used by alignment patterns to be considered a match |
| 153 |
*/ |
| 154 |
private function foundPatternCross(array $stateCount):bool{ |
| 155 |
$maxVariance = ($this->moduleSize / 2.0); |
| 156 |
|
| 157 |
for($i = 0; $i < 3; $i++){ |
| 158 |
if(abs($this->moduleSize - $stateCount[$i]) >= $maxVariance){ |
| 159 |
return false; |
| 160 |
} |
| 161 |
} |
| 162 |
|
| 163 |
return true; |
| 164 |
} |
| 165 |
|
| 166 |
/** |
| 167 |
* This is called when a horizontal scan finds a possible alignment pattern. It will |
| 168 |
* cross-check with a vertical scan, and if successful, will see if this pattern had been |
| 169 |
* found on a previous horizontal scan. If so, we consider it confirmed and conclude we have |
| 170 |
* found the alignment pattern. |
| 171 |
* |
| 172 |
* @param int[] $stateCount reading state module counts from horizontal scan |
| 173 |
* @param int $i row where alignment pattern may be found |
| 174 |
* @param int $j end of possible alignment pattern in row |
| 175 |
* |
| 176 |
* @return \chillerlan\QRCode\Detector\AlignmentPattern|null if we have found the same pattern twice, or null if not |
| 177 |
*/ |
| 178 |
private function handlePossibleCenter(array $stateCount, int $i, int $j):AlignmentPattern|null{ |
| 179 |
$stateCountTotal = ($stateCount[0] + $stateCount[1] + $stateCount[2]); |
| 180 |
$centerJ = $this->centerFromEnd($stateCount, $j); |
| 181 |
$centerI = $this->crossCheckVertical($i, (int)$centerJ, (2 * $stateCount[1]), $stateCountTotal); |
| 182 |
|
| 183 |
if($centerI !== null){ |
| 184 |
$estimatedModuleSize = (($stateCount[0] + $stateCount[1] + $stateCount[2]) / 3.0); |
| 185 |
|
| 186 |
foreach($this->possibleCenters as $center){ |
| 187 |
// Look for about the same center and module size: |
| 188 |
if($center->aboutEquals($estimatedModuleSize, $centerI, $centerJ)){ |
| 189 |
return $center->combineEstimate($centerI, $centerJ, $estimatedModuleSize); |
| 190 |
} |
| 191 |
} |
| 192 |
|
| 193 |
// Hadn't found this before; save it |
| 194 |
$point = new AlignmentPattern($centerJ, $centerI, $estimatedModuleSize); |
| 195 |
$this->possibleCenters[] = $point; |
| 196 |
} |
| 197 |
|
| 198 |
return null; |
| 199 |
} |
| 200 |
|
| 201 |
/** |
| 202 |
* Given a count of black/white/black pixels just seen and an end position, |
| 203 |
* figures the location of the center of this black/white/black run. |
| 204 |
* |
| 205 |
* @param int[] $stateCount |
| 206 |
*/ |
| 207 |
private function centerFromEnd(array $stateCount, int $end):float{ |
| 208 |
return (float)(($end - $stateCount[2]) - $stateCount[1] / 2); |
| 209 |
} |
| 210 |
|
| 211 |
/** |
| 212 |
* After a horizontal scan finds a potential alignment pattern, this method |
| 213 |
* "cross-checks" by scanning down vertically through the center of the possible |
| 214 |
* alignment pattern to see if the same proportion is detected. |
| 215 |
* |
| 216 |
* $startI row where an alignment pattern was detected |
| 217 |
* $centerJ center of the section that appears to cross an alignment pattern |
| 218 |
* $maxCount maximum reasonable number of modules that should be |
| 219 |
* observed in any reading state, based on the results of the horizontal scan |
| 220 |
* |
| 221 |
* returns vertical center of alignment pattern, or null if not found |
| 222 |
*/ |
| 223 |
private function crossCheckVertical(int $startI, int $centerJ, int $maxCount, int $originalStateCountTotal):float|null{ |
| 224 |
$maxI = $this->matrix->getSize(); |
| 225 |
$stateCount = []; |
| 226 |
$stateCount[0] = 0; |
| 227 |
$stateCount[1] = 0; |
| 228 |
$stateCount[2] = 0; |
| 229 |
|
| 230 |
// Start counting up from center |
| 231 |
$i = $startI; |
| 232 |
while($i >= 0 && $this->matrix->check($centerJ, $i) && $stateCount[1] <= $maxCount){ |
| 233 |
$stateCount[1]++; |
| 234 |
$i--; |
| 235 |
} |
| 236 |
// If already too many modules in this state or ran off the edge: |
| 237 |
if($i < 0 || $stateCount[1] > $maxCount){ |
| 238 |
return null; |
| 239 |
} |
| 240 |
|
| 241 |
while($i >= 0 && !$this->matrix->check($centerJ, $i) && $stateCount[0] <= $maxCount){ |
| 242 |
$stateCount[0]++; |
| 243 |
$i--; |
| 244 |
} |
| 245 |
|
| 246 |
if($stateCount[0] > $maxCount){ |
| 247 |
return null; |
| 248 |
} |
| 249 |
|
| 250 |
// Now also count down from center |
| 251 |
$i = ($startI + 1); |
| 252 |
while($i < $maxI && $this->matrix->check($centerJ, $i) && $stateCount[1] <= $maxCount){ |
| 253 |
$stateCount[1]++; |
| 254 |
$i++; |
| 255 |
} |
| 256 |
|
| 257 |
if($i === $maxI || $stateCount[1] > $maxCount){ |
| 258 |
return null; |
| 259 |
} |
| 260 |
|
| 261 |
while($i < $maxI && !$this->matrix->check($centerJ, $i) && $stateCount[2] <= $maxCount){ |
| 262 |
$stateCount[2]++; |
| 263 |
$i++; |
| 264 |
} |
| 265 |
|
| 266 |
if($stateCount[2] > $maxCount){ |
| 267 |
return null; |
| 268 |
} |
| 269 |
|
| 270 |
// phpcs:ignore |
| 271 |
if((5 * abs(($stateCount[0] + $stateCount[1] + $stateCount[2]) - $originalStateCountTotal)) >= (2 * $originalStateCountTotal)){ |
| 272 |
return null; |
| 273 |
} |
| 274 |
|
| 275 |
if(!$this->foundPatternCross($stateCount)){ |
| 276 |
return null; |
| 277 |
} |
| 278 |
|
| 279 |
return $this->centerFromEnd($stateCount, $i); |
| 280 |
} |
| 281 |
|
| 282 |
} |