AlignmentPatternFinder::handlePossibleCenter() - Code Metrics - Inspection of ":sparkles: init from https://github.com/codemasher..." - chillerlan/php-qrcode - Measure and Improve Code Quality continuously with Scrutinizer

Passed

Push — v5 ( 93618e...84eb31 )

by smiley

created 2021-01-24 23:44 UTC

AlignmentPatternFinder::handlePossibleCenter() A

↳ Parent: AlignmentPatternFinder

Complexity

Conditions	4
Paths	3

Size

Total Lines	21
Code Lines	11

Duplication

Lines	0
Ratio	0 %

Importance

Changes	1
Bugs	0	Features	0

Metric	Value
cc	4
eloc	11
c	1
b	0
f	0
nc	3
nop	3
dl	0
loc	21
rs	9.9

<?php
/**
 * Class AlignmentPatternFinder
 *
 * @created      17.01.2021
 * @author       ZXing Authors
 * @author       Smiley <[email protected]>
 * @copyright    2021 Smiley
 * @license      Apache-2.0
 */

namespace chillerlan\QRCode\Detector;

use chillerlan\QRCode\Decoder\BitMatrix;
use function abs, count;


/**
 * <p>This class attempts to find alignment patterns in a QR Code. Alignment patterns look like finder
 * patterns but are smaller and appear at regular intervals throughout the image.</p>
 *
 * <p>At the moment this only looks for the bottom-right alignment pattern.</p>
 *
 * <p>This is mostly a simplified copy of {@link FinderPatternFinder}. It is copied,
 * pasted and stripped down here for maximum performance but does unfortunately duplicate
 * some code.</p>
 *
 * <p>This class is thread-safe but not reentrant. Each thread must allocate its own object.</p>
 *
 * @author Sean Owen
 */
final class AlignmentPatternFinder{

	private BitMatrix $bitMatrix;
	private float     $moduleSize;
	/** @var \chillerlan\QRCode\Detector\AlignmentPattern[] */
	private array $possibleCenters;
	private array $crossCheckStateCount;

	/**
	 * <p>Creates a finder that will look in a portion of the whole image.</p>
	 *
	 * @param \chillerlan\QRCode\Decoder\BitMatrix $image      image to search
	 * @param float                                $moduleSize estimated module size so far
	 */
	public function __construct(BitMatrix $image, float $moduleSize){
		$this->bitMatrix            = $image;
		$this->moduleSize           = $moduleSize;
		$this->possibleCenters      = [];
		$this->crossCheckStateCount = [];
	}

	/**
	 * <p>This method attempts to find the bottom-right alignment pattern in the image. It is a bit messy since
	 * it's pretty performance-critical and so is written to be fast foremost.</p>
	 *
	 * @param int $startX left column from which to start searching
	 * @param int $startY top row from which to start searching
	 * @param int $width  width of region to search
	 * @param int $height height of region to search
	 *
	 * @return \chillerlan\QRCode\Detector\AlignmentPattern|null
	 */
	public function find(int $startX, int $startY, int $width, int $height):?AlignmentPattern{
		$maxJ       = $startX + $width;
		$middleI    = $startY + ($height / 2);
		$stateCount = [];

		// We are looking for black/white/black modules in 1:1:1 ratio;
		// this tracks the number of black/white/black modules seen so far
		for($iGen = 0; $iGen < $height; $iGen++){
			// Search from middle outwards
			$i             = (int)($middleI + (($iGen & 0x01) === 0 ? ($iGen + 1) / 2 : -(($iGen + 1) / 2)));
			$stateCount[0] = 0;
			$stateCount[1] = 0;
			$stateCount[2] = 0;
			$j             = $startX;
			// Burn off leading white pixels before anything else; if we start in the middle of
			// a white run, it doesn't make sense to count its length, since we don't know if the
			// white run continued to the left of the start point
			while($j < $maxJ && !$this->bitMatrix->get($j, $i)){
				$j++;
			}

			$currentState = 0;

			while($j < $maxJ){

				if($this->bitMatrix->get($j, $i)){
					// Black pixel
					if($currentState === 1){ // Counting black pixels
						$stateCount[$currentState]++;
					}
					// Counting white pixels
					else{
						// A winner?
						if($currentState === 2){
							// Yes
							if($this->foundPatternCross($stateCount)){
								$confirmed = $this->handlePossibleCenter($stateCount, $i, $j);

								if($confirmed !== null){
									return $confirmed;
								}
							}

							$stateCount[0] = $stateCount[2];
							$stateCount[1] = 1;
							$stateCount[2] = 0;
							$currentState  = 1;
						}
						else{
							$stateCount[++$currentState]++;
						}
					}
				}
				// White pixel
				else{
					// Counting black pixels
					if($currentState === 1){
						$currentState++;
					}

					$stateCount[$currentState]++;
				}

				$j++;
			}

			if($this->foundPatternCross($stateCount)){
				$confirmed = $this->handlePossibleCenter($stateCount, $i, $maxJ);

				if($confirmed !== null){
					return $confirmed;
				}
			}

		}

		// Hmm, nothing we saw was observed and confirmed twice. If we had
		// any guess at all, return it.
		if(count($this->possibleCenters)){
			return $this->possibleCenters[0];
		}

		return null;
	}

	/**
	 * @param int[] $stateCount count of black/white/black pixels just read
	 *
	 * @return bool true if the proportions of the counts is close enough to the 1/1/1 ratios
	 *         used by alignment patterns to be considered a match
	 */
	private function foundPatternCross(array $stateCount):bool{
		$moduleSize  = $this->moduleSize;
		$maxVariance = $moduleSize / 2.0;

		for($i = 0; $i < 3; $i++){
			if(abs($moduleSize - $stateCount[$i]) >= $maxVariance){
				return false;
			}
		}

		return true;
	}

	/**
	 * <p>This is called when a horizontal scan finds a possible alignment pattern. It will
	 * cross check with a vertical scan, and if successful, will see if this pattern had been
	 * found on a previous horizontal scan. If so, we consider it confirmed and conclude we have
	 * found the alignment pattern.</p>
	 *
	 * @param int[] $stateCount reading state module counts from horizontal scan
	 * @param int   $i          row where alignment pattern may be found
	 * @param int   $j          end of possible alignment pattern in row
	 *
	 * @return \chillerlan\QRCode\Detector\AlignmentPattern|null if we have found the same pattern twice, or null if not
	 */
	private function handlePossibleCenter(array $stateCount, int $i, int $j):?AlignmentPattern{
		$stateCountTotal = $stateCount[0] + $stateCount[1] + $stateCount[2];
		$centerJ         = $this->centerFromEnd($stateCount, $j);
		$centerI         = $this->crossCheckVertical($i, (int)$centerJ, 2 * $stateCount[1], $stateCountTotal);

		if($centerI !== null){
			$estimatedModuleSize = (float)($stateCount[0] + $stateCount[1] + $stateCount[2]) / 3.0;

			foreach($this->possibleCenters as $center){
				// Look for about the same center and module size:
				if($center->aboutEquals($estimatedModuleSize, $centerI, $centerJ)){
					return $center->combineEstimate($centerI, $centerJ, $estimatedModuleSize);
				}
			}

			// Hadn't found this before; save it
			$point                   = new AlignmentPattern($centerJ, $centerI, $estimatedModuleSize);
			$this->possibleCenters[] = $point;
		}

		return null;
	}

	/**
	 * Given a count of black/white/black pixels just seen and an end position,
	 * figures the location of the center of this black/white/black run.
	 *
	 * @param int[] $stateCount
	 * @param int   $end
	 *
	 * @return float
	 */
	private function centerFromEnd(array $stateCount, int $end):float{
		return (float)(($end - $stateCount[2]) - $stateCount[1] / 2.0);
	}

	/**
	 * <p>After a horizontal scan finds a potential alignment pattern, this method
	 * "cross-checks" by scanning down vertically through the center of the possible
	 * alignment pattern to see if the same proportion is detected.</p>
	 *
	 * @param int $startI   row where an alignment pattern was detected
	 * @param int $centerJ  center of the section that appears to cross an alignment pattern
	 * @param int $maxCount maximum reasonable number of modules that should be
	 *                      observed in any reading state, based on the results of the horizontal scan
	 * @param int $originalStateCountTotal
	 *
	 * @return float|null vertical center of alignment pattern, or null if not found
	 */
	private function crossCheckVertical(int $startI, int $centerJ, int $maxCount, int $originalStateCountTotal):?float{
		$maxI          = $this->bitMatrix->getDimension();
		$stateCount    = $this->crossCheckStateCount;
		$stateCount[0] = 0;
		$stateCount[1] = 0;
		$stateCount[2] = 0;

		// Start counting up from center
		$i = $startI;
		while($i >= 0 && $this->bitMatrix->get($centerJ, $i) && $stateCount[1] <= $maxCount){
			$stateCount[1]++;
			$i--;
		}
		// If already too many modules in this state or ran off the edge:
		if($i < 0 || $stateCount[1] > $maxCount){
			return null;
		}

		while($i >= 0 && !$this->bitMatrix->get($centerJ, $i) && $stateCount[0] <= $maxCount){
			$stateCount[0]++;
			$i--;
		}

		if($stateCount[0] > $maxCount){
			return null;
		}

		// Now also count down from center
		$i = $startI + 1;
		while($i < $maxI && $this->bitMatrix->get($centerJ, $i) && $stateCount[1] <= $maxCount){
			$stateCount[1]++;
			$i++;
		}

		if($i == $maxI || $stateCount[1] > $maxCount){
			return null;
		}

		while($i < $maxI && !$this->bitMatrix->get($centerJ, $i) && $stateCount[2] <= $maxCount){
			$stateCount[2]++;
			$i++;
		}

		if($stateCount[2] > $maxCount){
			return null;
		}

		if(5 * abs(($stateCount[0] + $stateCount[1] + $stateCount[2]) - $originalStateCountTotal) >= 2 * $originalStateCountTotal){
			return null;
		}

		if(!$this->foundPatternCross($stateCount)){
			return null;
		}

		return $this->centerFromEnd($stateCount, $i);
	}

}


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

chillerlan / php-qrcode

Push — v5 ( 93618e...84eb31 )

AlignmentPatternFinder::handlePossibleCenter() A

Complexity

Size

Duplication

Importance

Duplication Side-by-Side

Filter issues like