AlignmentPatternFinder::handlePossibleCenter() - Code Metrics - Inspection of "Deploying to gh-pages from @ chillerlan/php-qrcode..." - chillerlan/php-qrcode - Measure and Improve Code Quality continuously with Scrutinizer

Passed

Push — gh-pages ( 20c441...dd59e5 )

unknown

created 2021-11-18 13:01 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;

	/**
	 * <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      = [];
	}

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

chillerlan / php-qrcode

Push — gh-pages ( 20c441...dd59e5 )

AlignmentPatternFinder::handlePossibleCenter() A

Complexity

Size

Duplication

Importance

Duplication Side-by-Side

Filter issues like