At the moment this only looks for the bottom-right alignment pattern.
* *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.
* *This class is thread-safe but not reentrant. Each thread must allocate its own object.
* * @author Sean Owen */ final class AlignmentPatternFinder { private $image; private $possibleCenters; private $startX; private $startY; private $width; private $height; private $moduleSize; private $crossCheckStateCount; private $resultPointCallback; /** *Creates a finder that will look in a portion of the whole image.
* * @param image image to search * @param startX left column from which to start searching * @param startY top row from which to start searching * @param width width of region to search * @param height height of region to search * @param moduleSize estimated module size so far */ public function __construct($image, $startX, $startY, $width, $height, $moduleSize, $resultPointCallback) { $this->image = $image; $this->possibleCenters = []; $this->startX = $startX; $this->startY = $startY; $this->width = $width; $this->height = $height; $this->moduleSize = $moduleSize; $this->crossCheckStateCount = []; $this->resultPointCallback = $resultPointCallback; } /** *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.
* * @return {@link AlignmentPattern} if found * @throws NotFoundException if not found */ public function find() { $startX = $this->startX; $height = $this->height; $maxJ = $startX + $this->width; $middleI = $this->startY + ($height / 2); // 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 $stateCount = []; for ($iGen = 0; $iGen < $height; $iGen++) { // Search from middle outwards $i = $middleI + (($iGen & 0x01) == 0 ? ($iGen + 1) / 2 : -(($iGen + 1) / 2)); $i = (int)($i); $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->image->get($j, $i)) { $j++; } $currentState = 0; while ($j < $maxJ) { if ($this->image->get($j, $i)) { // Black pixel if ($currentState == 1) { // Counting black pixels $stateCount[$currentState]++; } else { // Counting white pixels if ($currentState == 2) { // A winner? if ($this->foundPatternCross($stateCount)) { // Yes $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]++; } } } else { // White pixel if ($currentState == 1) { // Counting black pixels $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]; } throw NotFoundException::getNotFoundInstance(); } /** * @param stateCount count of black/white/black pixels just read * * @return true iff 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($stateCount) { $moduleSize = $this->moduleSize; $maxVariance = $moduleSize / 2.0; for ($i = 0; $i < 3; $i++) { if (abs($moduleSize - $stateCount[$i]) >= $maxVariance) { return false; } } return true; } /** *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.
* * @param stateCount reading state module counts from horizontal scan * @param i row where alignment pattern may be found * @param j end of possible alignment pattern in row * * @return {@link AlignmentPattern} if we have found the same pattern twice, or null if not */ private function handlePossibleCenter($stateCount, $i, $j) { $stateCountTotal = $stateCount[0] + $stateCount[1] + $stateCount[2]; $centerJ = $this->centerFromEnd($stateCount, $j); $centerI = $this->crossCheckVertical($i, (int)$centerJ, 2 * $stateCount[1], $stateCountTotal); if (!is_nan($centerI)) { $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; if ($this->resultPointCallback != null) { $this->resultPointCallback->foundPossibleResultPoint($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. */ private static function centerFromEnd($stateCount, $end) { return (float)($end - $stateCount[2]) - $stateCount[1] / 2.0; } /** *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.
* * @param startI row where an alignment pattern was detected * @param centerJ center of the section that appears to cross an alignment pattern * @param maxCount maximum reasonable number of modules that should be * observed in any reading state, based on the results of the horizontal scan * * @return vertical center of alignment pattern, or {@link Float#NaN} if not found */ private function crossCheckVertical($startI, $centerJ, $maxCount, $originalStateCountTotal) { $image = $this->image; $maxI = $image->getHeight(); $stateCount = $this->crossCheckStateCount; $stateCount[0] = 0; $stateCount[1] = 0; $stateCount[2] = 0; // Start counting up from center $i = $startI; while ($i >= 0 && $image->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 NAN; } while ($i >= 0 && !$image->get($centerJ, $i) && $stateCount[0] <= $maxCount) { $stateCount[0]++; $i--; } if ($stateCount[0] > $maxCount) { return NAN; } // Now also count down from center $i = $startI + 1; while ($i < $maxI && $image->get($centerJ, $i) && $stateCount[1] <= $maxCount) { $stateCount[1]++; $i++; } if ($i == $maxI || $stateCount[1] > $maxCount) { return NAN; } while ($i < $maxI && !$image->get($centerJ, $i) && $stateCount[2] <= $maxCount) { $stateCount[2]++; $i++; } if ($stateCount[2] > $maxCount) { return NAN; } $stateCountTotal = $stateCount[0] + $stateCount[1] + $stateCount[2]; if (5 * abs($stateCountTotal - $originalStateCountTotal) >= 2 * $originalStateCountTotal) { return NAN; } return $this->foundPatternCross($stateCount) ? $this->centerFromEnd($stateCount, $i) : NAN; } }