FinderPatternFinder.php 27 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705
  1. <?php
  2. /*
  3. * Copyright 2007 ZXing authors
  4. *
  5. * Licensed under the Apache License, Version 2.0 (the "License");
  6. * you may not use this file except in compliance with the License.
  7. * You may obtain a copy of the License at
  8. *
  9. * http://www.apache.org/licenses/LICENSE-2.0
  10. *
  11. * Unless required by applicable law or agreed to in writing, software
  12. * distributed under the License is distributed on an "AS IS" BASIS,
  13. * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  14. * See the License for the specific language governing permissions and
  15. * limitations under the License.
  16. */
  17. namespace Zxing\Qrcode\Detector;
  18. use Zxing\DecodeHintType;
  19. use Zxing\NotFoundException;
  20. use Zxing\ResultPoint;
  21. use Zxing\ResultPointCallback;
  22. use Zxing\Common\BitMatrix;
  23. /**
  24. * <p>This class attempts to find finder patterns in a QR Code. Finder patterns are the square
  25. * markers at three corners of a QR Code.</p>
  26. *
  27. * <p>This class is thread-safe but not reentrant. Each thread must allocate its own object.
  28. *
  29. * @author Sean Owen
  30. */
  31. class FinderPatternFinder
  32. {
  33. private static $CENTER_QUORUM = 2;
  34. protected static $MIN_SKIP = 3; // 1 pixel/module times 3 modules/center
  35. protected static $MAX_MODULES = 57; // support up to version 10 for mobile clients
  36. private $image;
  37. private $average;
  38. private $possibleCenters; //private final List<FinderPattern> possibleCenters;
  39. private $hasSkipped = false;
  40. private $crossCheckStateCount;
  41. private $resultPointCallback;
  42. /**
  43. * <p>Creates a finder that will search the image for three finder patterns.</p>
  44. *
  45. * @param image image to search
  46. */
  47. public function __construct($image, $resultPointCallback = null)
  48. {
  49. $this->image = $image;
  50. $this->possibleCenters = array();//new ArrayList<>();
  51. $this->crossCheckStateCount = fill_array(0,5,0);
  52. $this->resultPointCallback = $resultPointCallback;
  53. }
  54. protected final function getImage()
  55. {
  56. return $this->image;
  57. }
  58. protected final function getPossibleCenters()
  59. { //List<FinderPattern> getPossibleCenters()
  60. return $this->possibleCenters;
  61. }
  62. final function find($hints)
  63. {/*final FinderPatternInfo find(Map<DecodeHintType,?> hints) throws NotFoundException {*/
  64. $tryHarder = $hints != null && $hints['TRY_HARDER'];
  65. $pureBarcode = $hints != null && $hints['PURE_BARCODE'];
  66. $maxI = $this->image->getHeight();
  67. $maxJ = $this->image->getWidth();
  68. // We are looking for black/white/black/white/black modules in
  69. // 1:1:3:1:1 ratio; this tracks the number of such modules seen so far
  70. // Let's assume that the maximum version QR Code we support takes up 1/4 the height of the
  71. // image, and then account for the center being 3 modules in size. This gives the smallest
  72. // number of pixels the center could be, so skip this often. When trying harder, look for all
  73. // QR versions regardless of how dense they are.
  74. $iSkip = intval((3 * $maxI) / (4 * self::$MAX_MODULES));
  75. if ($iSkip < self::$MIN_SKIP || $tryHarder) {
  76. $iSkip = self::$MIN_SKIP;
  77. }
  78. $done = false;
  79. $stateCount = array();
  80. for ($i = $iSkip - 1; $i < $maxI && !$done; $i += $iSkip) {
  81. // Get a row of black/white values
  82. $stateCount[0] = 0;
  83. $stateCount[1] = 0;
  84. $stateCount[2] = 0;
  85. $stateCount[3] = 0;
  86. $stateCount[4] = 0;
  87. $currentState = 0;
  88. for ($j = 0; $j < $maxJ; $j++) {
  89. if ($this->image->get($j, $i)) {
  90. // Black pixel
  91. if (($currentState & 1) == 1) { // Counting white pixels
  92. $currentState++;
  93. }
  94. $stateCount[$currentState]++;
  95. } else { // White pixel
  96. if (($currentState & 1) == 0) { // Counting black pixels
  97. if ($currentState == 4) { // A winner?
  98. if ($this->foundPatternCross($stateCount)) { // Yes
  99. $confirmed = $this->handlePossibleCenter($stateCount, $i, $j, $pureBarcode);
  100. if ($confirmed) {
  101. // Start examining every other line. Checking each line turned out to be too
  102. // expensive and didn't improve performance.
  103. $iSkip = 2;
  104. if ($this->hasSkipped) {
  105. $done = $this->haveMultiplyConfirmedCenters();
  106. } else {
  107. $rowSkip = $this->findRowSkip();
  108. if ($rowSkip > $stateCount[2]) {
  109. // Skip rows between row of lower confirmed center
  110. // and top of presumed third confirmed center
  111. // but back up a bit to get a full chance of detecting
  112. // it, entire width of center of finder pattern
  113. // Skip by rowSkip, but back off by $stateCount[2] (size of last center
  114. // of pattern we saw) to be conservative, and also back off by iSkip which
  115. // is about to be re-added
  116. $i += $rowSkip - $stateCount[2] - $iSkip;
  117. $j = $maxJ - 1;
  118. }
  119. }
  120. } else {
  121. $stateCount[0] = $stateCount[2];
  122. $stateCount[1] = $stateCount[3];
  123. $stateCount[2] = $stateCount[4];
  124. $stateCount[3] = 1;
  125. $stateCount[4] = 0;
  126. $currentState = 3;
  127. continue;
  128. }
  129. // Clear state to start looking again
  130. $currentState = 0;
  131. $stateCount[0] = 0;
  132. $stateCount[1] = 0;
  133. $stateCount[2] = 0;
  134. $stateCount[3] = 0;
  135. $stateCount[4] = 0;
  136. } else { // No, shift counts back by two
  137. $stateCount[0] = $stateCount[2];
  138. $stateCount[1] = $stateCount[3];
  139. $stateCount[2] = $stateCount[4];
  140. $stateCount[3] = 1;
  141. $stateCount[4] = 0;
  142. $currentState = 3;
  143. }
  144. } else {
  145. $stateCount[++$currentState]++;
  146. }
  147. } else { // Counting white pixels
  148. $stateCount[$currentState]++;
  149. }
  150. }
  151. }
  152. if ($this->foundPatternCross($stateCount)) {
  153. $confirmed = $this->handlePossibleCenter($stateCount, $i, $maxJ, $pureBarcode);
  154. if ($confirmed) {
  155. $iSkip = $stateCount[0];
  156. if ($this->hasSkipped) {
  157. // Found a third one
  158. $done = $this->haveMultiplyConfirmedCenters();
  159. }
  160. }
  161. }
  162. }
  163. $patternInfo = $this->selectBestPatterns();
  164. $patternInfo = ResultPoint::orderBestPatterns($patternInfo);
  165. return new FinderPatternInfo($patternInfo);
  166. }
  167. /**
  168. * Given a count of black/white/black/white/black pixels just seen and an end position,
  169. * figures the location of the center of this run.
  170. */
  171. private static function centerFromEnd($stateCount, $end)
  172. {
  173. return (float)($end - $stateCount[4] - $stateCount[3]) - $stateCount[2] / 2.0;
  174. }
  175. /**
  176. * @param $stateCount ; count of black/white/black/white/black pixels just read
  177. * @return true iff the proportions of the counts is close enough to the 1/1/3/1/1 ratios
  178. * used by finder patterns to be considered a match
  179. */
  180. protected static function foundPatternCross($stateCount)
  181. {
  182. $totalModuleSize = 0;
  183. for ($i = 0; $i < 5; $i++) {
  184. $count = $stateCount[$i];
  185. if ($count == 0) {
  186. return false;
  187. }
  188. $totalModuleSize += $count;
  189. }
  190. if ($totalModuleSize < 7) {
  191. return false;
  192. }
  193. $moduleSize = $totalModuleSize / 7.0;
  194. $maxVariance = $moduleSize / 2.0;
  195. // Allow less than 50% variance from 1-1-3-1-1 proportions
  196. return
  197. abs($moduleSize - $stateCount[0]) < $maxVariance &&
  198. abs($moduleSize - $stateCount[1]) < $maxVariance &&
  199. abs(3.0 * $moduleSize - $stateCount[2]) < 3 * $maxVariance &&
  200. abs($moduleSize - $stateCount[3]) < $maxVariance &&
  201. abs($moduleSize - $stateCount[4]) < $maxVariance;
  202. }
  203. private function getCrossCheckStateCount()
  204. {
  205. $this->crossCheckStateCount[0] = 0;
  206. $this->crossCheckStateCount[1] = 0;
  207. $this->crossCheckStateCount[2] = 0;
  208. $this->crossCheckStateCount[3] = 0;
  209. $this->crossCheckStateCount[4] = 0;
  210. return $this->crossCheckStateCount;
  211. }
  212. /**
  213. * After a vertical and horizontal scan finds a potential finder pattern, this method
  214. * "cross-cross-cross-checks" by scanning down diagonally through the center of the possible
  215. * finder pattern to see if the same proportion is detected.
  216. *
  217. * @param $startI ; row where a finder pattern was detected
  218. * @param centerJ ; center of the section that appears to cross a finder pattern
  219. * @param $maxCount ; maximum reasonable number of modules that should be
  220. * observed in any reading state, based on the results of the horizontal scan
  221. * @param originalStateCountTotal ; The original state count total.
  222. * @return true if proportions are withing expected limits
  223. */
  224. private function crossCheckDiagonal($startI, $centerJ, $maxCount, $originalStateCountTotal)
  225. {
  226. $stateCount = $this->getCrossCheckStateCount();
  227. // Start counting up, left from center finding black center mass
  228. $i = 0;
  229. $startI = intval($startI);
  230. $centerJ = intval($centerJ);
  231. while ($startI >= $i && $centerJ >= $i && $this->image->get($centerJ - $i, $startI - $i)) {
  232. $stateCount[2]++;
  233. $i++;
  234. }
  235. if ($startI < $i || $centerJ < $i) {
  236. return false;
  237. }
  238. // Continue up, left finding white space
  239. while ($startI >= $i && $centerJ >= $i && !$this->image->get($centerJ - $i, $startI - $i) &&
  240. $stateCount[1] <= $maxCount) {
  241. $stateCount[1]++;
  242. $i++;
  243. }
  244. // If already too many modules in this state or ran off the edge:
  245. if ($startI < $i || $centerJ < $i || $stateCount[1] > $maxCount) {
  246. return false;
  247. }
  248. // Continue up, left finding black border
  249. while ($startI >= $i && $centerJ >= $i && $this->image->get($centerJ - $i, $startI - $i) &&
  250. $stateCount[0] <= $maxCount) {
  251. $stateCount[0]++;
  252. $i++;
  253. }
  254. if ($stateCount[0] > $maxCount) {
  255. return false;
  256. }
  257. $maxI = $this->image->getHeight();
  258. $maxJ = $this->image->getWidth();
  259. // Now also count down, right from center
  260. $i = 1;
  261. while ($startI + $i < $maxI && $centerJ + $i < $maxJ && $this->image->get($centerJ + $i, $startI + $i)) {
  262. $stateCount[2]++;
  263. $i++;
  264. }
  265. // Ran off the edge?
  266. if ($startI + $i >= $maxI || $centerJ + $i >= $maxJ) {
  267. return false;
  268. }
  269. while ($startI + $i < $maxI && $centerJ + $i < $maxJ && !$this->image->get($centerJ + $i, $startI + $i) &&
  270. $stateCount[3] < $maxCount) {
  271. $stateCount[3]++;
  272. $i++;
  273. }
  274. if ($startI + $i >= $maxI || $centerJ + $i >= $maxJ || $stateCount[3] >= $maxCount) {
  275. return false;
  276. }
  277. while ($startI + $i < $maxI && $centerJ + $i < $maxJ && $this->image->get($centerJ + $i, $startI + $i) &&
  278. $stateCount[4] < $maxCount) {
  279. $stateCount[4]++;
  280. $i++;
  281. }
  282. if ($stateCount[4] >= $maxCount) {
  283. return false;
  284. }
  285. // If we found a finder-pattern-like section, but its size is more than 100% different than
  286. // the original, assume it's a false positive
  287. $stateCountTotal = $stateCount[0] + $stateCount[1] + $stateCount[2] + $stateCount[3] + $stateCount[4];
  288. return
  289. abs($stateCountTotal - $originalStateCountTotal) < 2 * $originalStateCountTotal &&
  290. $this->foundPatternCross($stateCount);
  291. }
  292. /**
  293. * <p>After a horizontal scan finds a potential finder pattern, this method
  294. * "cross-checks" by scanning down vertically through the center of the possible
  295. * finder pattern to see if the same proportion is detected.</p>
  296. *
  297. * @param $startI ; row where a finder pattern was detected
  298. * @param centerJ ; center of the section that appears to cross a finder pattern
  299. * @param $maxCount ; maximum reasonable number of modules that should be
  300. * observed in any reading state, based on the results of the horizontal scan
  301. * @return vertical center of finder pattern, or {@link Float#NaN} if not found
  302. */
  303. private function crossCheckVertical($startI, $centerJ, $maxCount,
  304. $originalStateCountTotal)
  305. {
  306. $image = $this->image;
  307. $maxI = $image->getHeight();
  308. $stateCount = $this->getCrossCheckStateCount();
  309. // Start counting up from center
  310. $i = $startI;
  311. while ($i >= 0 && $image->get($centerJ, $i)) {
  312. $stateCount[2]++;
  313. $i--;
  314. }
  315. if ($i < 0) {
  316. return NAN;
  317. }
  318. while ($i >= 0 && !$image->get($centerJ, $i) && $stateCount[1] <= $maxCount) {
  319. $stateCount[1]++;
  320. $i--;
  321. }
  322. // If already too many modules in this state or ran off the edge:
  323. if ($i < 0 || $stateCount[1] > $maxCount) {
  324. return NAN;
  325. }
  326. while ($i >= 0 && $image->get($centerJ, $i) && $stateCount[0] <= $maxCount) {
  327. $stateCount[0]++;
  328. $i--;
  329. }
  330. if ($stateCount[0] > $maxCount) {
  331. return NAN;
  332. }
  333. // Now also count down from center
  334. $i = $startI + 1;
  335. while ($i < $maxI && $image->get($centerJ, $i)) {
  336. $stateCount[2]++;
  337. $i++;
  338. }
  339. if ($i == $maxI) {
  340. return NAN;
  341. }
  342. while ($i < $maxI && !$image->get($centerJ, $i) && $stateCount[3] < $maxCount) {
  343. $stateCount[3]++;
  344. $i++;
  345. }
  346. if ($i == $maxI || $stateCount[3] >= $maxCount) {
  347. return NAN;
  348. }
  349. while ($i < $maxI && $image->get($centerJ, $i) && $stateCount[4] < $maxCount) {
  350. $stateCount[4]++;
  351. $i++;
  352. }
  353. if ($stateCount[4] >= $maxCount) {
  354. return NAN;
  355. }
  356. // If we found a finder-pattern-like section, but its size is more than 40% different than
  357. // the original, assume it's a false positive
  358. $stateCountTotal = $stateCount[0] + $stateCount[1] + $stateCount[2] + $stateCount[3] +
  359. $stateCount[4];
  360. if (5 * abs($stateCountTotal - $originalStateCountTotal) >= 2 * $originalStateCountTotal) {
  361. return NAN;
  362. }
  363. return $this->foundPatternCross($stateCount) ? $this->centerFromEnd($stateCount, $i) : NAN;
  364. }
  365. /**
  366. * <p>Like {@link #crossCheckVertical(int, int, int, int)}, and in fact is basically identical,
  367. * except it reads horizontally instead of vertically. This is used to cross-cross
  368. * check a vertical cross check and locate the real center of the alignment pattern.</p>
  369. */
  370. private function crossCheckHorizontal($startJ, $centerI, $maxCount,
  371. $originalStateCountTotal)
  372. {
  373. $image = $this->image;
  374. $maxJ = $this->image->getWidth();
  375. $stateCount = $this->getCrossCheckStateCount();
  376. $j = $startJ;
  377. while ($j >= 0 && $image->get($j, $centerI)) {
  378. $stateCount[2]++;
  379. $j--;
  380. }
  381. if ($j < 0) {
  382. return NAN;
  383. }
  384. while ($j >= 0 && !$image->get($j, $centerI) && $stateCount[1] <= $maxCount) {
  385. $stateCount[1]++;
  386. $j--;
  387. }
  388. if ($j < 0 || $stateCount[1] > $maxCount) {
  389. return NAN;
  390. }
  391. while ($j >= 0 && $image->get($j, $centerI) && $stateCount[0] <= $maxCount) {
  392. $stateCount[0]++;
  393. $j--;
  394. }
  395. if ($stateCount[0] > $maxCount) {
  396. return NAN;
  397. }
  398. $j = $startJ + 1;
  399. while ($j < $maxJ && $image->get($j, $centerI)) {
  400. $stateCount[2]++;
  401. $j++;
  402. }
  403. if ($j == $maxJ) {
  404. return NAN;
  405. }
  406. while ($j < $maxJ && !$image->get($j, $centerI) && $stateCount[3] < $maxCount) {
  407. $stateCount[3]++;
  408. $j++;
  409. }
  410. if ($j == $maxJ || $stateCount[3] >= $maxCount) {
  411. return NAN;
  412. }
  413. while ($j < $maxJ && $this->image->get($j, $centerI) && $stateCount[4] < $maxCount) {
  414. $stateCount[4]++;
  415. $j++;
  416. }
  417. if ($stateCount[4] >= $maxCount) {
  418. return NAN;
  419. }
  420. // If we found a finder-pattern-like section, but its size is significantly different than
  421. // the original, assume it's a false positive
  422. $stateCountTotal = $stateCount[0] + $stateCount[1] + $stateCount[2] + $stateCount[3] +
  423. $stateCount[4];
  424. if (5 * abs($stateCountTotal - $originalStateCountTotal) >= $originalStateCountTotal) {
  425. return NAN;
  426. }
  427. return $this->foundPatternCross($stateCount) ? $this->centerFromEnd($stateCount, $j) : NAN;
  428. }
  429. /**
  430. * <p>This is called when a horizontal scan finds a possible alignment pattern. It will
  431. * cross check with a vertical scan, and if successful, will, ah, cross-cross-check
  432. * with another horizontal scan. This is needed primarily to locate the real horizontal
  433. * center of the pattern in cases of extreme skew.
  434. * And then we cross-cross-cross check with another diagonal scan.</p>
  435. *
  436. * <p>If that succeeds the finder pattern location is added to a list that tracks
  437. * the number of times each location has been nearly-matched as a finder pattern.
  438. * Each additional find is more evidence that the location is in fact a finder
  439. * pattern center
  440. *
  441. * @param $stateCount reading state module counts from horizontal scan
  442. * @param i row where finder pattern may be found
  443. * @param j end of possible finder pattern in row
  444. * @param pureBarcode true if in "pure barcode" mode
  445. * @return true if a finder pattern candidate was found this time
  446. */
  447. protected final function handlePossibleCenter($stateCount, $i, $j, $pureBarcode)
  448. {
  449. $stateCountTotal = $stateCount[0] + $stateCount[1] + $stateCount[2] + $stateCount[3] +
  450. $stateCount[4];
  451. $centerJ = $this->centerFromEnd($stateCount, $j);
  452. $centerI = $this->crossCheckVertical($i, intval($centerJ), $stateCount[2], $stateCountTotal);
  453. if (!is_nan($centerI)) {
  454. // Re-cross check
  455. $centerJ = $this->crossCheckHorizontal(intval($centerJ), intval($centerI), $stateCount[2], $stateCountTotal);
  456. if (!is_nan($centerJ) &&
  457. (!$pureBarcode || $this->crossCheckDiagonal(intval($centerI), intval($centerJ), $stateCount[2], $stateCountTotal))
  458. ) {
  459. $estimatedModuleSize = (float)$stateCountTotal / 7.0;
  460. $found = false;
  461. for ($index = 0; $index < count($this->possibleCenters); $index++) {
  462. $center = $this->possibleCenters[$index];
  463. // Look for about the same center and module size:
  464. if ($center->aboutEquals($estimatedModuleSize, $centerI, $centerJ)) {
  465. $this->possibleCenters[$index] = $center->combineEstimate($centerI, $centerJ, $estimatedModuleSize);
  466. $found = true;
  467. break;
  468. }
  469. }
  470. if (!$found) {
  471. $point = new FinderPattern($centerJ, $centerI, $estimatedModuleSize);
  472. $this->possibleCenters[] = $point;
  473. if ($this->resultPointCallback != null) {
  474. $this->resultPointCallback->foundPossibleResultPoint($point);
  475. }
  476. }
  477. return true;
  478. }
  479. }
  480. return false;
  481. }
  482. /**
  483. * @return number of rows we could safely skip during scanning, based on the first
  484. * two finder patterns that have been located. In some cases their position will
  485. * allow us to infer that the third pattern must lie below a certain point farther
  486. * down in the image.
  487. */
  488. private function findRowSkip()
  489. {
  490. $max = count($this->possibleCenters);
  491. if ($max <= 1) {
  492. return 0;
  493. }
  494. $firstConfirmedCenter = null;
  495. foreach ($this->possibleCenters as $center) {
  496. if ($center->getCount() >= self::$CENTER_QUORUM) {
  497. if ($firstConfirmedCenter == null) {
  498. $firstConfirmedCenter = $center;
  499. } else {
  500. // We have two confirmed centers
  501. // How far down can we skip before resuming looking for the next
  502. // pattern? In the worst case, only the difference between the
  503. // difference in the x / y coordinates of the two centers.
  504. // This is the case where you find top left last.
  505. $this->hasSkipped = true;
  506. return intval((abs($firstConfirmedCenter->getX() - $center->getX()) -
  507. abs($firstConfirmedCenter->getY() - $center->getY())) / 2);
  508. }
  509. }
  510. }
  511. return 0;
  512. }
  513. /**
  514. * @return true iff we have found at least 3 finder patterns that have been detected
  515. * at least {@link #CENTER_QUORUM} times each, and, the estimated module size of the
  516. * candidates is "pretty similar"
  517. */
  518. private function haveMultiplyConfirmedCenters()
  519. {
  520. $confirmedCount = 0;
  521. $totalModuleSize = 0.0;
  522. $max = count($this->possibleCenters);
  523. foreach ($this->possibleCenters as $pattern) {
  524. if ($pattern->getCount() >= self::$CENTER_QUORUM) {
  525. $confirmedCount++;
  526. $totalModuleSize += $pattern->getEstimatedModuleSize();
  527. }
  528. }
  529. if ($confirmedCount < 3) {
  530. return false;
  531. }
  532. // OK, we have at least 3 confirmed centers, but, it's possible that one is a "false positive"
  533. // and that we need to keep looking. We detect this by asking if the estimated module sizes
  534. // vary too much. We arbitrarily say that when the total deviation from average exceeds
  535. // 5% of the total module size estimates, it's too much.
  536. $average = $totalModuleSize / (float)$max;
  537. $totalDeviation = 0.0;
  538. foreach ($this->possibleCenters as $pattern) {
  539. $totalDeviation += abs($pattern->getEstimatedModuleSize() - $average);
  540. }
  541. return $totalDeviation <= 0.05 * $totalModuleSize;
  542. }
  543. /**
  544. * @return the 3 best {@link FinderPattern}s from our list of candidates. The "best" are
  545. * those that have been detected at least {@link #CENTER_QUORUM} times, and whose module
  546. * size differs from the average among those patterns the least
  547. * @throws NotFoundException if 3 such finder patterns do not exist
  548. */
  549. private function selectBestPatterns()
  550. {
  551. $startSize = count($this->possibleCenters);
  552. if ($startSize < 3) {
  553. // Couldn't find enough finder patterns
  554. throw new NotFoundException;
  555. }
  556. // Filter outlier possibilities whose module size is too different
  557. if ($startSize > 3) {
  558. // But we can only afford to do so if we have at least 4 possibilities to choose from
  559. $totalModuleSize = 0.0;
  560. $square = 0.0;
  561. foreach ($this->possibleCenters as $center) {
  562. $size = $center->getEstimatedModuleSize();
  563. $totalModuleSize += $size;
  564. $square += $size * $size;
  565. }
  566. $this->average = $totalModuleSize / (float)$startSize;
  567. $stdDev = (float)sqrt($square / $startSize - $this->average * $this->average);
  568. usort($this->possibleCenters, array($this,'FurthestFromAverageComparator'));
  569. $limit = max(0.2 * $this->average, $stdDev);
  570. for ($i = 0; $i < count($this->possibleCenters) && count($this->possibleCenters) > 3; $i++) {
  571. $pattern = $this->possibleCenters[$i];
  572. if (abs($pattern->getEstimatedModuleSize() - $this->average) > $limit) {
  573. unset($this->possibleCenters[$i]);//возможно что ключи меняются в java при вызове .remove(i) ???
  574. $this->possibleCenters = array_values($this->possibleCenters);
  575. $i--;
  576. }
  577. }
  578. }
  579. if (count($this->possibleCenters) > 3) {
  580. // Throw away all but those first size candidate points we found.
  581. $totalModuleSize = 0.0;
  582. foreach ($this->possibleCenters as $possibleCenter) {
  583. $totalModuleSize += $possibleCenter->getEstimatedModuleSize();
  584. }
  585. $this->average = $totalModuleSize / (float)count($this->possibleCenters);
  586. usort($this->possibleCenters, array($this,'CenterComparator'));
  587. array_slice($this->possibleCenters, 3, count($this->possibleCenters) - 3);
  588. }
  589. return array($this->possibleCenters[0], $this->possibleCenters[1], $this->possibleCenters[2]);
  590. }
  591. /**
  592. * <p>Orders by furthest from average</p>
  593. */
  594. public function FurthestFromAverageComparator($center1, $center2)
  595. {
  596. $dA = abs($center2->getEstimatedModuleSize() - $this->average);
  597. $dB = abs($center1->getEstimatedModuleSize() - $this->average);
  598. if ($dA < $dB) {
  599. return -1;
  600. } elseif ($dA == $dB) {
  601. return 0;
  602. } else {
  603. return 1;
  604. }
  605. }
  606. /**
  607. * <p>Orders by {@link FinderPattern#getCount()}, descending.</p>
  608. */
  609. //@Override
  610. public function CenterComparator($center1, $center2) {
  611. if ($center2->getCount() == $center1->getCount()) {
  612. $dA = abs($center2->getEstimatedModuleSize() - $this->average);
  613. $dB = abs($center1->getEstimatedModuleSize() - $this->average);
  614. if($dA < $dB){
  615. return 1;
  616. }elseif( $dA == $dB){
  617. return 0;
  618. }else{
  619. return -1;
  620. }
  621. } else {
  622. return $center2->getCount() - $center1->getCount();
  623. }
  624. }
  625. }