MultiFinderPatternFinder.cpp Example File

 // -*- mode:c++; tab-width:2; indent-tabs-mode:nil; c-basic-offset:2 -*-
 /*
  *  Copyright 2011 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 <cmath>
 #include <algorithm>
 #include <zxing/multi/qrcode/detector/MultiFinderPatternFinder.h>
 #include <zxing/DecodeHints.h>
 #include <zxing/ReaderException.h>

 using std::abs;
 using std::min;
 using std::sort;
 using std::vector;
 using zxing::Ref;
 using zxing::BitMatrix;
 using zxing::ReaderException;
 using zxing::qrcode::FinderPattern;
 using zxing::qrcode::FinderPatternInfo;
 using zxing::multi::MultiFinderPatternFinder;

 // VC++

 using zxing::BitMatrix;
 using zxing::ResultPointCallback;
 using zxing::DecodeHints;

 const float MultiFinderPatternFinder::MAX_MODULE_COUNT_PER_EDGE = 180;
 const float MultiFinderPatternFinder::MIN_MODULE_COUNT_PER_EDGE = 9;
 const float MultiFinderPatternFinder::DIFF_MODSIZE_CUTOFF_PERCENT = 0.05f;
 const float MultiFinderPatternFinder::DIFF_MODSIZE_CUTOFF = 0.5f;

 namespace {

 bool compareModuleSize(Ref<FinderPattern> a, Ref<FinderPattern> b){
   float value = a->getEstimatedModuleSize() - b->getEstimatedModuleSize();
   return value < 0.0;
 }

 }

 MultiFinderPatternFinder::MultiFinderPatternFinder(Ref<BitMatrix> image,
                                                    Ref<ResultPointCallback> resultPointCallback)
     : FinderPatternFinder(image, resultPointCallback)
 {
 }

 MultiFinderPatternFinder::~MultiFinderPatternFinder(){}

 vector<Ref<FinderPatternInfo> > MultiFinderPatternFinder::findMulti(DecodeHints const& hints){
   bool tryHarder = hints.getTryHarder();
   Ref<BitMatrix> image = image_; // Protected member
   int maxI = image->getHeight();
   int maxJ = image->getWidth();
   // We are looking for black/white/black/white/black modules in
   // 1:1:3:1:1 ratio; this tracks the number of such modules seen so far

   // Let's assume that the maximum version QR Code we support takes up 1/4 the height of the
   // image, and then account for the center being 3 modules in size. This gives the smallest
   // number of pixels the center could be, so skip this often. When trying harder, look for all
   // QR versions regardless of how dense they are.
   int iSkip = (int) (maxI / (MAX_MODULES * 4.0f) * 3);
   if (iSkip < MIN_SKIP || tryHarder) {
     iSkip = MIN_SKIP;
   }

   int stateCount[5];
   for (int i = iSkip - 1; i < maxI; i += iSkip) {
     // Get a row of black/white values
     stateCount[0] = 0;
     stateCount[1] = 0;
     stateCount[2] = 0;
     stateCount[3] = 0;
     stateCount[4] = 0;
     int currentState = 0;
     for (int j = 0; j < maxJ; j++) {
       if (image->get(j, i)) {
         // Black pixel
         if ((currentState & 1) == 1) { // Counting white pixels
           currentState++;
         }
         stateCount[currentState]++;
       } else { // White pixel
         if ((currentState & 1) == 0) { // Counting black pixels
           if (currentState == 4) { // A winner?
             if (foundPatternCross(stateCount) && handlePossibleCenter(stateCount, i, j)) { // Yes
               // Clear state to start looking again
               currentState = 0;
               stateCount[0] = 0;
               stateCount[1] = 0;
               stateCount[2] = 0;
               stateCount[3] = 0;
               stateCount[4] = 0;
             } else { // No, shift counts back by two
               stateCount[0] = stateCount[2];
               stateCount[1] = stateCount[3];
               stateCount[2] = stateCount[4];
               stateCount[3] = 1;
               stateCount[4] = 0;
               currentState = 3;
             }
           } else {
             stateCount[++currentState]++;
           }
         } else { // Counting white pixels
           stateCount[currentState]++;
         }
       }
     } // for j=...

     if (foundPatternCross(stateCount)) {
       handlePossibleCenter(stateCount, i, maxJ);
     } // end if foundPatternCross
   } // for i=iSkip-1 ...
   vector<vector<Ref<FinderPattern> > > patternInfo = selectBestPatterns();
   vector<Ref<FinderPatternInfo> > result;
   for (unsigned int i = 0; i < patternInfo.size(); i++) {
     vector<Ref<FinderPattern> > pattern = patternInfo[i];
     pattern = FinderPatternFinder::orderBestPatterns(pattern);
     result.push_back(Ref<FinderPatternInfo>(new FinderPatternInfo(pattern)));
   }
   return result;
 }

 vector<vector<Ref<FinderPattern> > > MultiFinderPatternFinder::selectBestPatterns(){
   vector<Ref<FinderPattern> > possibleCenters = possibleCenters_;

   int size = possibleCenters.size();

   if (size < 3) {
     // Couldn't find enough finder patterns
     throw ReaderException("No code detected");
   }

   vector<vector<Ref<FinderPattern> > > results;

   /*
    * Begin HE modifications to safely detect multiple codes of equal size
    */
   if (size == 3) {
     results.push_back(possibleCenters_);
     return results;
   }

   // Sort by estimated module size to speed up the upcoming checks
   //TODO do a sort based on module size
   sort(possibleCenters.begin(), possibleCenters.end(), compareModuleSize);

   /*
    * Now lets start: build a list of tuples of three finder locations that
    *  - feature similar module sizes
    *  - are placed in a distance so the estimated module count is within the QR specification
    *  - have similar distance between upper left/right and left top/bottom finder patterns
    *  - form a triangle with 90° angle (checked by comparing top right/bottom left distance
    *    with pythagoras)
    *
    * Note: we allow each point to be used for more than one code region: this might seem
    * counterintuitive at first, but the performance penalty is not that big. At this point,
    * we cannot make a good quality decision whether the three finders actually represent
    * a QR code, or are just by chance layouted so it looks like there might be a QR code there.
    * So, if the layout seems right, lets have the decoder try to decode.
    */

   for (int i1 = 0; i1 < (size - 2); i1++) {
     Ref<FinderPattern> p1 = possibleCenters[i1];
     for (int i2 = i1 + 1; i2 < (size - 1); i2++) {
       Ref<FinderPattern> p2 = possibleCenters[i2];
       // Compare the expected module sizes; if they are really off, skip
       float vModSize12 = (p1->getEstimatedModuleSize() - p2->getEstimatedModuleSize()) / min(p1->getEstimatedModuleSize(), p2->getEstimatedModuleSize());
       float vModSize12A = abs(p1->getEstimatedModuleSize() - p2->getEstimatedModuleSize());
       if (vModSize12A > DIFF_MODSIZE_CUTOFF && vModSize12 >= DIFF_MODSIZE_CUTOFF_PERCENT) {
         // break, since elements are ordered by the module size deviation there cannot be
         // any more interesting elements for the given p1.
         break;
       }
       for (int i3 = i2 + 1; i3 < size; i3++) {
         Ref<FinderPattern> p3 = possibleCenters[i3];
         // Compare the expected module sizes; if they are really off, skip
         float vModSize23 = (p2->getEstimatedModuleSize() - p3->getEstimatedModuleSize()) / min(p2->getEstimatedModuleSize(), p3->getEstimatedModuleSize());
         float vModSize23A = abs(p2->getEstimatedModuleSize() - p3->getEstimatedModuleSize());
         if (vModSize23A > DIFF_MODSIZE_CUTOFF && vModSize23 >= DIFF_MODSIZE_CUTOFF_PERCENT) {
           // break, since elements are ordered by the module size deviation there cannot be
           // any more interesting elements for the given p1.
           break;
         }
         vector<Ref<FinderPattern> > test;
         test.push_back(p1);
         test.push_back(p2);
         test.push_back(p3);
         test = FinderPatternFinder::orderBestPatterns(test);
         // Calculate the distances: a = topleft-bottomleft, b=topleft-topright, c = diagonal
         Ref<FinderPatternInfo> info = Ref<FinderPatternInfo>(new FinderPatternInfo(test));
         float dA = FinderPatternFinder::distance(info->getTopLeft(), info->getBottomLeft());
         float dC = FinderPatternFinder::distance(info->getTopRight(), info->getBottomLeft());
         float dB = FinderPatternFinder::distance(info->getTopLeft(), info->getTopRight());
         // Check the sizes
         float estimatedModuleCount = (dA + dB) / (p1->getEstimatedModuleSize() * 2.0f);
         if (estimatedModuleCount > MAX_MODULE_COUNT_PER_EDGE || estimatedModuleCount < MIN_MODULE_COUNT_PER_EDGE) {
           continue;
         }
         // Calculate the difference of the edge lengths in percent
         float vABBC = abs((dA - dB) / min(dA, dB));
         if (vABBC >= 0.1f) {
           continue;
         }
         // Calculate the diagonal length by assuming a 90° angle at topleft
         float dCpy = (float) sqrt(dA * dA + dB * dB);
         // Compare to the real distance in %
         float vPyC = abs((dC - dCpy) / min(dC, dCpy));
         if (vPyC >= 0.1f) {
           continue;
         }
         // All tests passed!
         results.push_back(test);
       } // end iterate p3
     } // end iterate p2
   } // end iterate p1
   if (results.empty()){
     // Nothing found!
     throw ReaderException("No code detected");
   }
   return results;
 }