Home | History | Annotate | Download | only in qrcode 
      1 // Copyright 2014 PDFium Authors. All rights reserved.
      2 // Use of this source code is governed by a BSD-style license that can be
      3 // found in the LICENSE file.
      4 
      5 // Original code copyright 2014 Foxit Software Inc. http://www.foxitsoftware.com
      6 // Original code is licensed as follows:
      7 /*
      8  * Copyright 2007 ZXing authors
      9  *
     10  * Licensed under the Apache License, Version 2.0 (the "License");
     11  * you may not use this file except in compliance with the License.
     12  * You may obtain a copy of the License at
     13  *
     14  *      http://www.apache.org/licenses/LICENSE-2.0
     15  *
     16  * Unless required by applicable law or agreed to in writing, software
     17  * distributed under the License is distributed on an "AS IS" BASIS,
     18  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
     19  * See the License for the specific language governing permissions and
     20  * limitations under the License.
     21  */
     22 
     23 #include "xfa/src/fxbarcode/barcode.h"
     24 #include "xfa/src/fxbarcode/BC_ResultPoint.h"
     25 #include "xfa/src/fxbarcode/common/BC_CommonBitMatrix.h"
     26 #include "BC_QRFinderPatternFinder.h"
     27 #include "BC_FinderPatternInfo.h"
     28 #include "BC_QRFinderPattern.h"
     29 const int32_t CBC_QRFinderPatternFinder::CENTER_QUORUM = 2;
     30 const int32_t CBC_QRFinderPatternFinder::MIN_SKIP = 3;
     31 const int32_t CBC_QRFinderPatternFinder::MAX_MODULES = 57;
     32 const int32_t CBC_QRFinderPatternFinder::INTEGER_MATH_SHIFT = 8;
     33 CBC_QRFinderPatternFinder::CBC_QRFinderPatternFinder(
     34     CBC_CommonBitMatrix* image) {
     35   m_image = image;
     36   m_crossCheckStateCount.SetSize(5);
     37   m_hasSkipped = FALSE;
     38 }
     39 CBC_QRFinderPatternFinder::~CBC_QRFinderPatternFinder() {
     40   for (int32_t i = 0; i < m_possibleCenters.GetSize(); i++) {
     41     delete (CBC_QRFinderPattern*)m_possibleCenters[i];
     42   }
     43   m_possibleCenters.RemoveAll();
     44 }
     45 class ClosestToAverageComparator {
     46  private:
     47   FX_FLOAT m_averageModuleSize;
     48 
     49  public:
     50   ClosestToAverageComparator(FX_FLOAT averageModuleSize)
     51       : m_averageModuleSize(averageModuleSize) {}
     52   int32_t operator()(FinderPattern* a, FinderPattern* b) {
     53     FX_FLOAT dA =
     54         (FX_FLOAT)fabs(a->GetEstimatedModuleSize() - m_averageModuleSize);
     55     FX_FLOAT dB =
     56         (FX_FLOAT)fabs(b->GetEstimatedModuleSize() - m_averageModuleSize);
     57     return dA < dB ? -1 : dA > dB ? 1 : 0;
     58   }
     59 };
     60 class CenterComparator {
     61  public:
     62   int32_t operator()(FinderPattern* a, FinderPattern* b) {
     63     return b->GetCount() - a->GetCount();
     64   }
     65 };
     66 CBC_CommonBitMatrix* CBC_QRFinderPatternFinder::GetImage() {
     67   return m_image;
     68 }
     69 CFX_Int32Array& CBC_QRFinderPatternFinder::GetCrossCheckStateCount() {
     70   m_crossCheckStateCount[0] = 0;
     71   m_crossCheckStateCount[1] = 0;
     72   m_crossCheckStateCount[2] = 0;
     73   m_crossCheckStateCount[3] = 0;
     74   m_crossCheckStateCount[4] = 0;
     75   return m_crossCheckStateCount;
     76 }
     77 CFX_PtrArray* CBC_QRFinderPatternFinder::GetPossibleCenters() {
     78   return &m_possibleCenters;
     79 }
     80 CBC_QRFinderPatternInfo* CBC_QRFinderPatternFinder::Find(int32_t hint,
     81                                                          int32_t& e) {
     82   int32_t maxI = m_image->GetHeight();
     83   int32_t maxJ = m_image->GetWidth();
     84   int32_t iSkip = (3 * maxI) / (4 * MAX_MODULES);
     85   if (iSkip < MIN_SKIP || 0) {
     86     iSkip = MIN_SKIP;
     87   }
     88   FX_BOOL done = FALSE;
     89   CFX_Int32Array stateCount;
     90   stateCount.SetSize(5);
     91   for (int32_t i = iSkip - 1; i < maxI && !done; i += iSkip) {
     92     stateCount[0] = 0;
     93     stateCount[1] = 0;
     94     stateCount[2] = 0;
     95     stateCount[3] = 0;
     96     stateCount[4] = 0;
     97     int32_t currentState = 0;
     98     for (int32_t j = 0; j < maxJ; j++) {
     99       if (m_image->Get(j, i)) {
    100         if ((currentState & 1) == 1) {
    101           currentState++;
    102         }
    103         stateCount[currentState]++;
    104       } else {
    105         if ((currentState & 1) == 0) {
    106           if (currentState == 4) {
    107             if (FoundPatternCross(stateCount)) {
    108               FX_BOOL confirmed = HandlePossibleCenter(stateCount, i, j);
    109               if (confirmed) {
    110                 iSkip = 2;
    111                 if (m_hasSkipped) {
    112                   done = HaveMultiplyConfirmedCenters();
    113                 } else {
    114                   int32_t rowSkip = FindRowSkip();
    115                   if (rowSkip > stateCount[2]) {
    116                     i += rowSkip - stateCount[2] - iSkip;
    117                     j = maxJ - 1;
    118                   }
    119                 }
    120               } else {
    121                 do {
    122                   j++;
    123                 } while (j < maxJ && !m_image->Get(j, i));
    124                 j--;
    125               }
    126               currentState = 0;
    127               stateCount[0] = 0;
    128               stateCount[1] = 0;
    129               stateCount[2] = 0;
    130               stateCount[3] = 0;
    131               stateCount[4] = 0;
    132             } else {
    133               stateCount[0] = stateCount[2];
    134               stateCount[1] = stateCount[3];
    135               stateCount[2] = stateCount[4];
    136               stateCount[3] = 1;
    137               stateCount[4] = 0;
    138               currentState = 3;
    139             }
    140           } else {
    141             stateCount[++currentState]++;
    142           }
    143         } else {
    144           stateCount[currentState]++;
    145         }
    146       }
    147     }
    148     if (FoundPatternCross(stateCount)) {
    149       FX_BOOL confirmed = HandlePossibleCenter(stateCount, i, maxJ);
    150       if (confirmed) {
    151         iSkip = stateCount[0];
    152         if (m_hasSkipped) {
    153           done = HaveMultiplyConfirmedCenters();
    154         }
    155       }
    156     }
    157   }
    158   CFX_PtrArray* ptr = SelectBestpatterns(e);
    159   BC_EXCEPTION_CHECK_ReturnValue(e, NULL);
    160   CBC_AutoPtr<CFX_PtrArray> patternInfo(ptr);
    161   OrderBestPatterns(patternInfo.get());
    162   return new CBC_QRFinderPatternInfo(patternInfo.get());
    163 }
    164 void CBC_QRFinderPatternFinder::OrderBestPatterns(CFX_PtrArray* patterns) {
    165   FX_FLOAT abDistance = Distance((CBC_ResultPoint*)(*patterns)[0],
    166                                  (CBC_ResultPoint*)(*patterns)[1]);
    167   FX_FLOAT bcDistance = Distance((CBC_ResultPoint*)(*patterns)[1],
    168                                  (CBC_ResultPoint*)(*patterns)[2]);
    169   FX_FLOAT acDistance = Distance((CBC_ResultPoint*)(*patterns)[0],
    170                                  (CBC_ResultPoint*)(*patterns)[2]);
    171   CBC_QRFinderPattern *topLeft, *topRight, *bottomLeft;
    172   if (bcDistance >= abDistance && bcDistance >= acDistance) {
    173     topLeft = (CBC_QRFinderPattern*)(*patterns)[0];
    174     topRight = (CBC_QRFinderPattern*)(*patterns)[1];
    175     bottomLeft = (CBC_QRFinderPattern*)(*patterns)[2];
    176   } else if (acDistance >= bcDistance && acDistance >= abDistance) {
    177     topLeft = (CBC_QRFinderPattern*)(*patterns)[1];
    178     topRight = (CBC_QRFinderPattern*)(*patterns)[0];
    179     bottomLeft = (CBC_QRFinderPattern*)(*patterns)[2];
    180   } else {
    181     topLeft = (CBC_QRFinderPattern*)(*patterns)[2];
    182     topRight = (CBC_QRFinderPattern*)(*patterns)[0];
    183     bottomLeft = (CBC_QRFinderPattern*)(*patterns)[1];
    184   }
    185   if ((bottomLeft->GetY() - topLeft->GetY()) *
    186           (topRight->GetX() - topLeft->GetX()) <
    187       (bottomLeft->GetX() - topLeft->GetX()) *
    188           (topRight->GetY() - topLeft->GetY())) {
    189     CBC_QRFinderPattern* temp = topRight;
    190     topRight = bottomLeft;
    191     bottomLeft = temp;
    192   }
    193   (*patterns)[0] = bottomLeft;
    194   (*patterns)[1] = topLeft;
    195   (*patterns)[2] = topRight;
    196 }
    197 FX_FLOAT CBC_QRFinderPatternFinder::Distance(CBC_ResultPoint* point1,
    198                                              CBC_ResultPoint* point2) {
    199   FX_FLOAT dx = point1->GetX() - point2->GetX();
    200   FX_FLOAT dy = point1->GetY() - point2->GetY();
    201   return (FX_FLOAT)FXSYS_sqrt(dx * dx + dy * dy);
    202 }
    203 FX_FLOAT CBC_QRFinderPatternFinder::CenterFromEnd(
    204     const CFX_Int32Array& stateCount,
    205     int32_t end) {
    206   return (FX_FLOAT)(end - stateCount[4] - stateCount[3]) - stateCount[2] / 2.0f;
    207 }
    208 FX_BOOL CBC_QRFinderPatternFinder::FoundPatternCross(
    209     const CFX_Int32Array& stateCount) {
    210   int32_t totalModuleSize = 0;
    211   for (int32_t i = 0; i < 5; i++) {
    212     int32_t count = stateCount[i];
    213     if (count == 0) {
    214       return FALSE;
    215     }
    216     totalModuleSize += count;
    217   }
    218   if (totalModuleSize < 7) {
    219     return FALSE;
    220   }
    221   int32_t moduleSize = (totalModuleSize << INTEGER_MATH_SHIFT) / 7;
    222   int32_t maxVariance = moduleSize / 2;
    223   return FXSYS_abs(moduleSize - (stateCount[0] << INTEGER_MATH_SHIFT)) <
    224              maxVariance &&
    225          FXSYS_abs(moduleSize - (stateCount[1] << INTEGER_MATH_SHIFT)) <
    226              maxVariance &&
    227          FXSYS_abs(3 * moduleSize - (stateCount[2] << INTEGER_MATH_SHIFT)) <
    228              3 * maxVariance &&
    229          FXSYS_abs(moduleSize - (stateCount[3] << INTEGER_MATH_SHIFT)) <
    230              maxVariance &&
    231          FXSYS_abs(moduleSize - (stateCount[4] << INTEGER_MATH_SHIFT)) <
    232              maxVariance;
    233 }
    234 FX_FLOAT CBC_QRFinderPatternFinder::CrossCheckVertical(
    235     int32_t startI,
    236     int32_t centerJ,
    237     int32_t maxCount,
    238     int32_t originalStateCountTotal) {
    239   CBC_CommonBitMatrix* image = m_image;
    240   int32_t maxI = image->GetHeight();
    241   CFX_Int32Array& stateCount = GetCrossCheckStateCount();
    242   int32_t i = startI;
    243   while (i >= 0 && image->Get(centerJ, i)) {
    244     stateCount[2]++;
    245     i--;
    246   }
    247   if (i < 0) {
    248     return FXSYS_nan();
    249   }
    250   while (i >= 0 && !image->Get(centerJ, i) && stateCount[1] <= maxCount) {
    251     stateCount[1]++;
    252     i--;
    253   }
    254   if (i < 0 || stateCount[1] > maxCount) {
    255     return FXSYS_nan();
    256   }
    257   while (i >= 0 && image->Get(centerJ, i) && stateCount[0] <= maxCount) {
    258     stateCount[0]++;
    259     i--;
    260   }
    261   if (stateCount[0] > maxCount) {
    262     return FXSYS_nan();
    263   }
    264   i = startI + 1;
    265   while (i < maxI && image->Get(centerJ, i)) {
    266     stateCount[2]++;
    267     i++;
    268   }
    269   if (i == maxI) {
    270     return FXSYS_nan();
    271   }
    272   while (i < maxI && !image->Get(centerJ, i) && stateCount[3] < maxCount) {
    273     stateCount[3]++;
    274     i++;
    275   }
    276   if (i == maxI || stateCount[3] >= maxCount) {
    277     return FXSYS_nan();
    278   }
    279   while (i < maxI && image->Get(centerJ, i) && stateCount[4] < maxCount) {
    280     stateCount[4]++;
    281     i++;
    282   }
    283   if (stateCount[4] >= maxCount) {
    284     return FXSYS_nan();
    285   }
    286   int32_t stateCountTotal = stateCount[0] + stateCount[1] + stateCount[2] +
    287                             stateCount[3] + stateCount[4];
    288   if (5 * FXSYS_abs(stateCountTotal - originalStateCountTotal) >=
    289       originalStateCountTotal) {
    290     return FXSYS_nan();
    291   }
    292   return FoundPatternCross(stateCount) ? CenterFromEnd(stateCount, i)
    293                                        : FXSYS_nan();
    294 }
    295 FX_FLOAT CBC_QRFinderPatternFinder::CrossCheckHorizontal(
    296     int32_t startJ,
    297     int32_t centerI,
    298     int32_t maxCount,
    299     int32_t originalStateCountTotal) {
    300   CBC_CommonBitMatrix* image = m_image;
    301   int32_t maxJ = image->GetWidth();
    302   CFX_Int32Array& stateCount = GetCrossCheckStateCount();
    303   int32_t j = startJ;
    304   while (j >= 0 && image->Get(j, centerI)) {
    305     stateCount[2]++;
    306     j--;
    307   }
    308   if (j < 0) {
    309     return FXSYS_nan();
    310   }
    311   while (j >= 0 && !image->Get(j, centerI) && stateCount[1] <= maxCount) {
    312     stateCount[1]++;
    313     j--;
    314   }
    315   if (j < 0 || stateCount[1] > maxCount) {
    316     return FXSYS_nan();
    317   }
    318   while (j >= 0 && image->Get(j, centerI) && stateCount[0] <= maxCount) {
    319     stateCount[0]++;
    320     j--;
    321   }
    322   if (stateCount[0] > maxCount) {
    323     return FXSYS_nan();
    324   }
    325   j = startJ + 1;
    326   while (j < maxJ && image->Get(j, centerI)) {
    327     stateCount[2]++;
    328     j++;
    329   }
    330   if (j == maxJ) {
    331     return FXSYS_nan();
    332   }
    333   while (j < maxJ && !image->Get(j, centerI) && stateCount[3] < maxCount) {
    334     stateCount[3]++;
    335     j++;
    336   }
    337   if (j == maxJ || stateCount[3] >= maxCount) {
    338     return FXSYS_nan();
    339   }
    340   while (j < maxJ && image->Get(j, centerI) && stateCount[4] < maxCount) {
    341     stateCount[4]++;
    342     j++;
    343   }
    344   if (stateCount[4] >= maxCount) {
    345     return FXSYS_nan();
    346   }
    347   int32_t stateCountTotal = stateCount[0] + stateCount[1] + stateCount[2] +
    348                             stateCount[3] + stateCount[4];
    349   if (5 * FXSYS_abs(stateCountTotal - originalStateCountTotal) >=
    350       originalStateCountTotal) {
    351     return FXSYS_nan();
    352   }
    353   return FoundPatternCross(stateCount) ? CenterFromEnd(stateCount, j)
    354                                        : FXSYS_nan();
    355 }
    356 FX_BOOL CBC_QRFinderPatternFinder::HandlePossibleCenter(
    357     const CFX_Int32Array& stateCount,
    358     int32_t i,
    359     int32_t j) {
    360   int32_t stateCountTotal = stateCount[0] + stateCount[1] + stateCount[2] +
    361                             stateCount[3] + stateCount[4];
    362   FX_FLOAT centerJ = CenterFromEnd(stateCount, j);
    363   FX_FLOAT centerI =
    364       CrossCheckVertical(i, (int32_t)centerJ, stateCount[2], stateCountTotal);
    365   if (!FXSYS_isnan(centerI)) {
    366     centerJ = CrossCheckHorizontal((int32_t)centerJ, (int32_t)centerI,
    367                                    stateCount[2], stateCountTotal);
    368     if (!FXSYS_isnan(centerJ)) {
    369       FX_FLOAT estimatedModuleSize = (FX_FLOAT)stateCountTotal / 7.0f;
    370       FX_BOOL found = FALSE;
    371       int32_t max = m_possibleCenters.GetSize();
    372       for (int32_t index = 0; index < max; index++) {
    373         CBC_QRFinderPattern* center =
    374             (CBC_QRFinderPattern*)(m_possibleCenters[index]);
    375         if (center->AboutEquals(estimatedModuleSize, centerI, centerJ)) {
    376           center->IncrementCount();
    377           found = TRUE;
    378           break;
    379         }
    380       }
    381       if (!found) {
    382         m_possibleCenters.Add(
    383             new CBC_QRFinderPattern(centerJ, centerI, estimatedModuleSize));
    384       }
    385       return TRUE;
    386     }
    387   }
    388   return FALSE;
    389 }
    390 int32_t CBC_QRFinderPatternFinder::FindRowSkip() {
    391   int32_t max = m_possibleCenters.GetSize();
    392   if (max <= 1) {
    393     return 0;
    394   }
    395   FinderPattern* firstConfirmedCenter = NULL;
    396   for (int32_t i = 0; i < max; i++) {
    397     CBC_QRFinderPattern* center = (CBC_QRFinderPattern*)m_possibleCenters[i];
    398     if (center->GetCount() >= CENTER_QUORUM) {
    399       if (firstConfirmedCenter == NULL) {
    400         firstConfirmedCenter = center;
    401       } else {
    402         m_hasSkipped = TRUE;
    403         return (int32_t)((fabs(firstConfirmedCenter->GetX() - center->GetX()) -
    404                           fabs(firstConfirmedCenter->GetY() - center->GetY())) /
    405                          2);
    406       }
    407     }
    408   }
    409   return 0;
    410 }
    411 FX_BOOL CBC_QRFinderPatternFinder::HaveMultiplyConfirmedCenters() {
    412   int32_t confirmedCount = 0;
    413   FX_FLOAT totalModuleSize = 0.0f;
    414   int32_t max = m_possibleCenters.GetSize();
    415   int32_t i;
    416   for (i = 0; i < max; i++) {
    417     CBC_QRFinderPattern* pattern = (CBC_QRFinderPattern*)m_possibleCenters[i];
    418     if (pattern->GetCount() >= CENTER_QUORUM) {
    419       confirmedCount++;
    420       totalModuleSize += pattern->GetEstimatedModuleSize();
    421     }
    422   }
    423   if (confirmedCount < 3) {
    424     return FALSE;
    425   }
    426   FX_FLOAT average = totalModuleSize / (FX_FLOAT)max;
    427   FX_FLOAT totalDeviation = 0.0f;
    428   for (i = 0; i < max; i++) {
    429     CBC_QRFinderPattern* pattern = (CBC_QRFinderPattern*)m_possibleCenters[i];
    430     totalDeviation += fabs(pattern->GetEstimatedModuleSize() - average);
    431   }
    432   return totalDeviation <= 0.05f * totalModuleSize;
    433 }
    434 inline FX_BOOL centerComparator(void* a, void* b) {
    435   return ((CBC_QRFinderPattern*)b)->GetCount() <
    436          ((CBC_QRFinderPattern*)a)->GetCount();
    437 }
    438 CFX_PtrArray* CBC_QRFinderPatternFinder::SelectBestpatterns(int32_t& e) {
    439   int32_t startSize = m_possibleCenters.GetSize();
    440   if (m_possibleCenters.GetSize() < 3) {
    441     e = BCExceptionRead;
    442     BC_EXCEPTION_CHECK_ReturnValue(e, NULL);
    443   }
    444   FX_FLOAT average = 0.0f;
    445   if (startSize > 3) {
    446     FX_FLOAT totalModuleSize = 0.0f;
    447     for (int32_t i = 0; i < startSize; i++) {
    448       totalModuleSize += ((CBC_QRFinderPattern*)m_possibleCenters[i])
    449                              ->GetEstimatedModuleSize();
    450     }
    451     average = totalModuleSize / (FX_FLOAT)startSize;
    452     for (int32_t j = 0;
    453          j < m_possibleCenters.GetSize() && m_possibleCenters.GetSize() > 3;
    454          j++) {
    455       CBC_QRFinderPattern* pattern = (CBC_QRFinderPattern*)m_possibleCenters[j];
    456       if (fabs(pattern->GetEstimatedModuleSize() - average) > 0.2f * average) {
    457         delete pattern;
    458         m_possibleCenters.RemoveAt(j);
    459         j--;
    460       }
    461     }
    462   }
    463   if (m_possibleCenters.GetSize() > 3) {
    464     BC_FX_PtrArray_Sort(m_possibleCenters, centerComparator);
    465   }
    466   CFX_PtrArray* vec = new CFX_PtrArray();
    467   vec->SetSize(3);
    468   (*vec)[0] = ((CBC_QRFinderPattern*)m_possibleCenters[0])->Clone();
    469   (*vec)[1] = ((CBC_QRFinderPattern*)m_possibleCenters[1])->Clone();
    470   (*vec)[2] = ((CBC_QRFinderPattern*)m_possibleCenters[2])->Clone();
    471   return vec;
    472 }
    473