| // 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/fxcrt/include/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 m_possibleCenters[i]; |
| } |
| |
| 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_ArrayTemplate<CBC_QRFinderPattern*>* |
| 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_ArrayTemplate<CBC_QRFinderPattern*>> patternInfo( |
| SelectBestpatterns(e)); |
| BC_EXCEPTION_CHECK_ReturnValue(e, nullptr); |
| OrderBestPatterns(patternInfo.get()); |
| return new CBC_QRFinderPatternInfo(patternInfo.get()); |
| } |
| void CBC_QRFinderPatternFinder::OrderBestPatterns( |
| CFX_ArrayTemplate<CBC_QRFinderPattern*>* patterns) { |
| FX_FLOAT abDistance = Distance((*patterns)[0], (*patterns)[1]); |
| FX_FLOAT bcDistance = Distance((*patterns)[1], (*patterns)[2]); |
| FX_FLOAT acDistance = Distance((*patterns)[0], (*patterns)[2]); |
| CBC_QRFinderPattern* topLeft; |
| CBC_QRFinderPattern* topRight; |
| CBC_QRFinderPattern* bottomLeft; |
| if (bcDistance >= abDistance && bcDistance >= acDistance) { |
| topLeft = (*patterns)[0]; |
| topRight = (*patterns)[1]; |
| bottomLeft = (*patterns)[2]; |
| } else if (acDistance >= bcDistance && acDistance >= abDistance) { |
| topLeft = (*patterns)[1]; |
| topRight = (*patterns)[0]; |
| bottomLeft = (*patterns)[2]; |
| } else { |
| topLeft = (*patterns)[2]; |
| topRight = (*patterns)[0]; |
| bottomLeft = (*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 = 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 = nullptr; |
| for (int32_t i = 0; i < max; i++) { |
| CBC_QRFinderPattern* center = m_possibleCenters[i]; |
| if (center->GetCount() >= CENTER_QUORUM) { |
| if (firstConfirmedCenter) { |
| m_hasSkipped = TRUE; |
| return (int32_t)((fabs(firstConfirmedCenter->GetX() - center->GetX()) - |
| fabs(firstConfirmedCenter->GetY() - center->GetY())) / |
| 2); |
| } |
| firstConfirmedCenter = center; |
| } |
| } |
| 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 = 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 = m_possibleCenters[i]; |
| totalDeviation += fabs(pattern->GetEstimatedModuleSize() - average); |
| } |
| return totalDeviation <= 0.05f * totalModuleSize; |
| } |
| |
| CFX_ArrayTemplate<CBC_QRFinderPattern*>* |
| CBC_QRFinderPatternFinder::SelectBestpatterns(int32_t& e) { |
| int32_t startSize = m_possibleCenters.GetSize(); |
| if (m_possibleCenters.GetSize() < 3) { |
| e = BCExceptionRead; |
| BC_EXCEPTION_CHECK_ReturnValue(e, nullptr); |
| } |
| FX_FLOAT average = 0.0f; |
| if (startSize > 3) { |
| FX_FLOAT totalModuleSize = 0.0f; |
| for (int32_t i = 0; i < startSize; i++) |
| totalModuleSize += 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 = m_possibleCenters[j]; |
| if (fabs(pattern->GetEstimatedModuleSize() - average) > 0.2f * average) { |
| delete pattern; |
| m_possibleCenters.RemoveAt(j); |
| j--; |
| } |
| } |
| } |
| if (m_possibleCenters.GetSize() > 3) { |
| std::sort(m_possibleCenters.GetData(), |
| m_possibleCenters.GetData() + m_possibleCenters.GetSize(), |
| [](const CBC_QRFinderPattern* a, CBC_QRFinderPattern* b) { |
| return a->GetCount() > b->GetCount(); // e.g. Descending. |
| }); |
| } |
| CFX_ArrayTemplate<CBC_QRFinderPattern*>* vec = |
| new CFX_ArrayTemplate<CBC_QRFinderPattern*>(); |
| vec->SetSize(3); |
| (*vec)[0] = m_possibleCenters[0]->Clone(); |
| (*vec)[1] = m_possibleCenters[1]->Clone(); |
| (*vec)[2] = m_possibleCenters[2]->Clone(); |
| return vec; |
| } |
