diff options
Diffstat (limited to 'xfa/fxbarcode/qrcode/BC_QRFinderPatternFinder.cpp')
| -rw-r--r-- | xfa/fxbarcode/qrcode/BC_QRFinderPatternFinder.cpp | 477 |
1 files changed, 477 insertions, 0 deletions
diff --git a/xfa/fxbarcode/qrcode/BC_QRFinderPatternFinder.cpp b/xfa/fxbarcode/qrcode/BC_QRFinderPatternFinder.cpp new file mode 100644 index 0000000000..5ccbd9804b --- /dev/null +++ b/xfa/fxbarcode/qrcode/BC_QRFinderPatternFinder.cpp @@ -0,0 +1,477 @@ +// Copyright 2014 PDFium Authors. All rights reserved. +// Use of this source code is governed by a BSD-style license that can be +// found in the LICENSE file. + +// Original code copyright 2014 Foxit Software Inc. http://www.foxitsoftware.com +// Original code is licensed as follows: +/* + * Copyright 2007 ZXing authors + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#include "xfa/fxbarcode/qrcode/BC_QRFinderPatternFinder.h" + +#include <memory> + +#include "core/include/fxcrt/fx_basic.h" +#include "xfa/fxbarcode/BC_ResultPoint.h" +#include "xfa/fxbarcode/common/BC_CommonBitMatrix.h" +#include "xfa/fxbarcode/qrcode/BC_FinderPatternInfo.h" +#include "xfa/fxbarcode/qrcode/BC_QRFinderPattern.h" +#include "xfa/fxbarcode/utils.h" + +const int32_t CBC_QRFinderPatternFinder::CENTER_QUORUM = 2; +const int32_t CBC_QRFinderPatternFinder::MIN_SKIP = 3; +const int32_t CBC_QRFinderPatternFinder::MAX_MODULES = 57; +const int32_t CBC_QRFinderPatternFinder::INTEGER_MATH_SHIFT = 8; + +CBC_QRFinderPatternFinder::CBC_QRFinderPatternFinder( + CBC_CommonBitMatrix* image) { + m_image = image; + m_crossCheckStateCount.SetSize(5); + m_hasSkipped = FALSE; +} +CBC_QRFinderPatternFinder::~CBC_QRFinderPatternFinder() { + for (int32_t i = 0; i < m_possibleCenters.GetSize(); i++) { + delete (CBC_QRFinderPattern*)m_possibleCenters[i]; + } + m_possibleCenters.RemoveAll(); +} +class ClosestToAverageComparator { + private: + FX_FLOAT m_averageModuleSize; + + public: + ClosestToAverageComparator(FX_FLOAT averageModuleSize) + : m_averageModuleSize(averageModuleSize) {} + int32_t operator()(FinderPattern* a, FinderPattern* b) { + FX_FLOAT dA = + (FX_FLOAT)fabs(a->GetEstimatedModuleSize() - m_averageModuleSize); + FX_FLOAT dB = + (FX_FLOAT)fabs(b->GetEstimatedModuleSize() - m_averageModuleSize); + return dA < dB ? -1 : dA > dB ? 1 : 0; + } +}; +class CenterComparator { + public: + int32_t operator()(FinderPattern* a, FinderPattern* b) { + return b->GetCount() - a->GetCount(); + } +}; +CBC_CommonBitMatrix* CBC_QRFinderPatternFinder::GetImage() { + return m_image; +} +CFX_Int32Array& CBC_QRFinderPatternFinder::GetCrossCheckStateCount() { + m_crossCheckStateCount[0] = 0; + m_crossCheckStateCount[1] = 0; + m_crossCheckStateCount[2] = 0; + m_crossCheckStateCount[3] = 0; + m_crossCheckStateCount[4] = 0; + return m_crossCheckStateCount; +} +CFX_PtrArray* CBC_QRFinderPatternFinder::GetPossibleCenters() { + return &m_possibleCenters; +} +CBC_QRFinderPatternInfo* CBC_QRFinderPatternFinder::Find(int32_t hint, + int32_t& e) { + int32_t maxI = m_image->GetHeight(); + int32_t maxJ = m_image->GetWidth(); + int32_t iSkip = (3 * maxI) / (4 * MAX_MODULES); + if (iSkip < MIN_SKIP || 0) { + iSkip = MIN_SKIP; + } + FX_BOOL done = FALSE; + CFX_Int32Array stateCount; + stateCount.SetSize(5); + for (int32_t i = iSkip - 1; i < maxI && !done; i += iSkip) { + stateCount[0] = 0; + stateCount[1] = 0; + stateCount[2] = 0; + stateCount[3] = 0; + stateCount[4] = 0; + int32_t currentState = 0; + for (int32_t j = 0; j < maxJ; j++) { + if (m_image->Get(j, i)) { + if ((currentState & 1) == 1) { + currentState++; + } + stateCount[currentState]++; + } else { + if ((currentState & 1) == 0) { + if (currentState == 4) { + if (FoundPatternCross(stateCount)) { + FX_BOOL confirmed = HandlePossibleCenter(stateCount, i, j); + if (confirmed) { + iSkip = 2; + if (m_hasSkipped) { + done = HaveMultiplyConfirmedCenters(); + } else { + int32_t rowSkip = FindRowSkip(); + if (rowSkip > stateCount[2]) { + i += rowSkip - stateCount[2] - iSkip; + j = maxJ - 1; + } + } + } else { + do { + j++; + } while (j < maxJ && !m_image->Get(j, i)); + j--; + } + currentState = 0; + stateCount[0] = 0; + stateCount[1] = 0; + stateCount[2] = 0; + stateCount[3] = 0; + stateCount[4] = 0; + } else { + stateCount[0] = stateCount[2]; + stateCount[1] = stateCount[3]; + stateCount[2] = stateCount[4]; + stateCount[3] = 1; + stateCount[4] = 0; + currentState = 3; + } + } else { + stateCount[++currentState]++; + } + } else { + stateCount[currentState]++; + } + } + } + if (FoundPatternCross(stateCount)) { + FX_BOOL confirmed = HandlePossibleCenter(stateCount, i, maxJ); + if (confirmed) { + iSkip = stateCount[0]; + if (m_hasSkipped) { + done = HaveMultiplyConfirmedCenters(); + } + } + } + } + std::unique_ptr<CFX_PtrArray> patternInfo(SelectBestpatterns(e)); + BC_EXCEPTION_CHECK_ReturnValue(e, NULL); + OrderBestPatterns(patternInfo.get()); + return new CBC_QRFinderPatternInfo(patternInfo.get()); +} +void CBC_QRFinderPatternFinder::OrderBestPatterns(CFX_PtrArray* patterns) { + FX_FLOAT abDistance = Distance((CBC_ResultPoint*)(*patterns)[0], + (CBC_ResultPoint*)(*patterns)[1]); + FX_FLOAT bcDistance = Distance((CBC_ResultPoint*)(*patterns)[1], + (CBC_ResultPoint*)(*patterns)[2]); + FX_FLOAT acDistance = Distance((CBC_ResultPoint*)(*patterns)[0], + (CBC_ResultPoint*)(*patterns)[2]); + CBC_QRFinderPattern *topLeft, *topRight, *bottomLeft; + if (bcDistance >= abDistance && bcDistance >= acDistance) { + topLeft = (CBC_QRFinderPattern*)(*patterns)[0]; + topRight = (CBC_QRFinderPattern*)(*patterns)[1]; + bottomLeft = (CBC_QRFinderPattern*)(*patterns)[2]; + } else if (acDistance >= bcDistance && acDistance >= abDistance) { + topLeft = (CBC_QRFinderPattern*)(*patterns)[1]; + topRight = (CBC_QRFinderPattern*)(*patterns)[0]; + bottomLeft = (CBC_QRFinderPattern*)(*patterns)[2]; + } else { + topLeft = (CBC_QRFinderPattern*)(*patterns)[2]; + topRight = (CBC_QRFinderPattern*)(*patterns)[0]; + bottomLeft = (CBC_QRFinderPattern*)(*patterns)[1]; + } + if ((bottomLeft->GetY() - topLeft->GetY()) * + (topRight->GetX() - topLeft->GetX()) < + (bottomLeft->GetX() - topLeft->GetX()) * + (topRight->GetY() - topLeft->GetY())) { + CBC_QRFinderPattern* temp = topRight; + topRight = bottomLeft; + bottomLeft = temp; + } + (*patterns)[0] = bottomLeft; + (*patterns)[1] = topLeft; + (*patterns)[2] = topRight; +} +FX_FLOAT CBC_QRFinderPatternFinder::Distance(CBC_ResultPoint* point1, + CBC_ResultPoint* point2) { + FX_FLOAT dx = point1->GetX() - point2->GetX(); + FX_FLOAT dy = point1->GetY() - point2->GetY(); + return (FX_FLOAT)FXSYS_sqrt(dx * dx + dy * dy); +} +FX_FLOAT CBC_QRFinderPatternFinder::CenterFromEnd( + const CFX_Int32Array& stateCount, + int32_t end) { + return (FX_FLOAT)(end - stateCount[4] - stateCount[3]) - stateCount[2] / 2.0f; +} +FX_BOOL CBC_QRFinderPatternFinder::FoundPatternCross( + const CFX_Int32Array& stateCount) { + int32_t totalModuleSize = 0; + for (int32_t i = 0; i < 5; i++) { + int32_t count = stateCount[i]; + if (count == 0) { + return FALSE; + } + totalModuleSize += count; + } + if (totalModuleSize < 7) { + return FALSE; + } + int32_t moduleSize = (totalModuleSize << INTEGER_MATH_SHIFT) / 7; + int32_t maxVariance = moduleSize / 2; + return FXSYS_abs(moduleSize - (stateCount[0] << INTEGER_MATH_SHIFT)) < + maxVariance && + FXSYS_abs(moduleSize - (stateCount[1] << INTEGER_MATH_SHIFT)) < + maxVariance && + FXSYS_abs(3 * moduleSize - (stateCount[2] << INTEGER_MATH_SHIFT)) < + 3 * maxVariance && + FXSYS_abs(moduleSize - (stateCount[3] << INTEGER_MATH_SHIFT)) < + maxVariance && + FXSYS_abs(moduleSize - (stateCount[4] << INTEGER_MATH_SHIFT)) < + maxVariance; +} +FX_FLOAT CBC_QRFinderPatternFinder::CrossCheckVertical( + int32_t startI, + int32_t centerJ, + int32_t maxCount, + int32_t originalStateCountTotal) { + CBC_CommonBitMatrix* image = m_image; + int32_t maxI = image->GetHeight(); + CFX_Int32Array& stateCount = GetCrossCheckStateCount(); + int32_t i = startI; + while (i >= 0 && image->Get(centerJ, i)) { + stateCount[2]++; + i--; + } + if (i < 0) { + return FXSYS_nan(); + } + while (i >= 0 && !image->Get(centerJ, i) && stateCount[1] <= maxCount) { + stateCount[1]++; + i--; + } + if (i < 0 || stateCount[1] > maxCount) { + return FXSYS_nan(); + } + while (i >= 0 && image->Get(centerJ, i) && stateCount[0] <= maxCount) { + stateCount[0]++; + i--; + } + if (stateCount[0] > maxCount) { + return FXSYS_nan(); + } + i = startI + 1; + while (i < maxI && image->Get(centerJ, i)) { + stateCount[2]++; + i++; + } + if (i == maxI) { + return FXSYS_nan(); + } + while (i < maxI && !image->Get(centerJ, i) && stateCount[3] < maxCount) { + stateCount[3]++; + i++; + } + if (i == maxI || stateCount[3] >= maxCount) { + return FXSYS_nan(); + } + while (i < maxI && image->Get(centerJ, i) && stateCount[4] < maxCount) { + stateCount[4]++; + i++; + } + if (stateCount[4] >= maxCount) { + return FXSYS_nan(); + } + int32_t stateCountTotal = stateCount[0] + stateCount[1] + stateCount[2] + + stateCount[3] + stateCount[4]; + if (5 * FXSYS_abs(stateCountTotal - originalStateCountTotal) >= + originalStateCountTotal) { + return FXSYS_nan(); + } + return FoundPatternCross(stateCount) ? CenterFromEnd(stateCount, i) + : FXSYS_nan(); +} +FX_FLOAT CBC_QRFinderPatternFinder::CrossCheckHorizontal( + int32_t startJ, + int32_t centerI, + int32_t maxCount, + int32_t originalStateCountTotal) { + CBC_CommonBitMatrix* image = m_image; + int32_t maxJ = image->GetWidth(); + CFX_Int32Array& stateCount = GetCrossCheckStateCount(); + int32_t j = startJ; + while (j >= 0 && image->Get(j, centerI)) { + stateCount[2]++; + j--; + } + if (j < 0) { + return FXSYS_nan(); + } + while (j >= 0 && !image->Get(j, centerI) && stateCount[1] <= maxCount) { + stateCount[1]++; + j--; + } + if (j < 0 || stateCount[1] > maxCount) { + return FXSYS_nan(); + } + while (j >= 0 && image->Get(j, centerI) && stateCount[0] <= maxCount) { + stateCount[0]++; + j--; + } + if (stateCount[0] > maxCount) { + return FXSYS_nan(); + } + j = startJ + 1; + while (j < maxJ && image->Get(j, centerI)) { + stateCount[2]++; + j++; + } + if (j == maxJ) { + return FXSYS_nan(); + } + while (j < maxJ && !image->Get(j, centerI) && stateCount[3] < maxCount) { + stateCount[3]++; + j++; + } + if (j == maxJ || stateCount[3] >= maxCount) { + return FXSYS_nan(); + } + while (j < maxJ && image->Get(j, centerI) && stateCount[4] < maxCount) { + stateCount[4]++; + j++; + } + if (stateCount[4] >= maxCount) { + return FXSYS_nan(); + } + int32_t stateCountTotal = stateCount[0] + stateCount[1] + stateCount[2] + + stateCount[3] + stateCount[4]; + if (5 * FXSYS_abs(stateCountTotal - originalStateCountTotal) >= + originalStateCountTotal) { + return FXSYS_nan(); + } + return FoundPatternCross(stateCount) ? CenterFromEnd(stateCount, j) + : FXSYS_nan(); +} +FX_BOOL CBC_QRFinderPatternFinder::HandlePossibleCenter( + const CFX_Int32Array& stateCount, + int32_t i, + int32_t j) { + int32_t stateCountTotal = stateCount[0] + stateCount[1] + stateCount[2] + + stateCount[3] + stateCount[4]; + FX_FLOAT centerJ = CenterFromEnd(stateCount, j); + FX_FLOAT centerI = + CrossCheckVertical(i, (int32_t)centerJ, stateCount[2], stateCountTotal); + if (!FXSYS_isnan(centerI)) { + centerJ = CrossCheckHorizontal((int32_t)centerJ, (int32_t)centerI, + stateCount[2], stateCountTotal); + if (!FXSYS_isnan(centerJ)) { + FX_FLOAT estimatedModuleSize = (FX_FLOAT)stateCountTotal / 7.0f; + FX_BOOL found = FALSE; + int32_t max = m_possibleCenters.GetSize(); + for (int32_t index = 0; index < max; index++) { + CBC_QRFinderPattern* center = + (CBC_QRFinderPattern*)(m_possibleCenters[index]); + if (center->AboutEquals(estimatedModuleSize, centerI, centerJ)) { + center->IncrementCount(); + found = TRUE; + break; + } + } + if (!found) { + m_possibleCenters.Add( + new CBC_QRFinderPattern(centerJ, centerI, estimatedModuleSize)); + } + return TRUE; + } + } + return FALSE; +} +int32_t CBC_QRFinderPatternFinder::FindRowSkip() { + int32_t max = m_possibleCenters.GetSize(); + if (max <= 1) { + return 0; + } + FinderPattern* firstConfirmedCenter = NULL; + for (int32_t i = 0; i < max; i++) { + CBC_QRFinderPattern* center = (CBC_QRFinderPattern*)m_possibleCenters[i]; + if (center->GetCount() >= CENTER_QUORUM) { + if (firstConfirmedCenter == NULL) { + firstConfirmedCenter = center; + } else { + m_hasSkipped = TRUE; + return (int32_t)((fabs(firstConfirmedCenter->GetX() - center->GetX()) - + fabs(firstConfirmedCenter->GetY() - center->GetY())) / + 2); + } + } + } + return 0; +} +FX_BOOL CBC_QRFinderPatternFinder::HaveMultiplyConfirmedCenters() { + int32_t confirmedCount = 0; + FX_FLOAT totalModuleSize = 0.0f; + int32_t max = m_possibleCenters.GetSize(); + int32_t i; + for (i = 0; i < max; i++) { + CBC_QRFinderPattern* pattern = (CBC_QRFinderPattern*)m_possibleCenters[i]; + if (pattern->GetCount() >= CENTER_QUORUM) { + confirmedCount++; + totalModuleSize += pattern->GetEstimatedModuleSize(); + } + } + if (confirmedCount < 3) { + return FALSE; + } + FX_FLOAT average = totalModuleSize / (FX_FLOAT)max; + FX_FLOAT totalDeviation = 0.0f; + for (i = 0; i < max; i++) { + CBC_QRFinderPattern* pattern = (CBC_QRFinderPattern*)m_possibleCenters[i]; + totalDeviation += fabs(pattern->GetEstimatedModuleSize() - average); + } + return totalDeviation <= 0.05f * totalModuleSize; +} +inline FX_BOOL centerComparator(void* a, void* b) { + return ((CBC_QRFinderPattern*)b)->GetCount() < + ((CBC_QRFinderPattern*)a)->GetCount(); +} +CFX_PtrArray* CBC_QRFinderPatternFinder::SelectBestpatterns(int32_t& e) { + int32_t startSize = m_possibleCenters.GetSize(); + if (m_possibleCenters.GetSize() < 3) { + e = BCExceptionRead; + BC_EXCEPTION_CHECK_ReturnValue(e, NULL); + } + FX_FLOAT average = 0.0f; + if (startSize > 3) { + FX_FLOAT totalModuleSize = 0.0f; + for (int32_t i = 0; i < startSize; i++) { + totalModuleSize += ((CBC_QRFinderPattern*)m_possibleCenters[i]) + ->GetEstimatedModuleSize(); + } + average = totalModuleSize / (FX_FLOAT)startSize; + for (int32_t j = 0; + j < m_possibleCenters.GetSize() && m_possibleCenters.GetSize() > 3; + j++) { + CBC_QRFinderPattern* pattern = (CBC_QRFinderPattern*)m_possibleCenters[j]; + if (fabs(pattern->GetEstimatedModuleSize() - average) > 0.2f * average) { + delete pattern; + m_possibleCenters.RemoveAt(j); + j--; + } + } + } + if (m_possibleCenters.GetSize() > 3) { + BC_FX_PtrArray_Sort(m_possibleCenters, centerComparator); + } + CFX_PtrArray* vec = new CFX_PtrArray(); + vec->SetSize(3); + (*vec)[0] = ((CBC_QRFinderPattern*)m_possibleCenters[0])->Clone(); + (*vec)[1] = ((CBC_QRFinderPattern*)m_possibleCenters[1])->Clone(); + (*vec)[2] = ((CBC_QRFinderPattern*)m_possibleCenters[2])->Clone(); + return vec; +} |