Debian Codegraph @

vendor/chillerlan/php-qrcode/src/Detector/AlignmentPatternFinder.php

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