Home | History | Annotate | Download | only in datamatrix 
      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 2008 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 <algorithm>
     24 
     25 #include "xfa/src/fxbarcode/barcode.h"
     26 #include "xfa/src/fxbarcode/BC_ResultPoint.h"
     27 #include "xfa/src/fxbarcode/common/BC_WhiteRectangleDetector.h"
     28 #include "xfa/src/fxbarcode/common/BC_CommonBitMatrix.h"
     29 #include "xfa/src/fxbarcode/qrcode/BC_QRFinderPatternFinder.h"
     30 #include "xfa/src/fxbarcode/qrcode/BC_QRDetectorResult.h"
     31 #include "xfa/src/fxbarcode/qrcode/BC_QRGridSampler.h"
     32 #include "BC_DataMatrixDetector.h"
     33 const int32_t CBC_DataMatrixDetector::INTEGERS[5] = {0, 1, 2, 3, 4};
     34 CBC_DataMatrixDetector::CBC_DataMatrixDetector(CBC_CommonBitMatrix* image)
     35     : m_image(image), m_rectangleDetector(NULL) {}
     36 void CBC_DataMatrixDetector::Init(int32_t& e) {
     37   m_rectangleDetector = new CBC_WhiteRectangleDetector(m_image);
     38   m_rectangleDetector->Init(e);
     39   BC_EXCEPTION_CHECK_ReturnVoid(e);
     40 }
     41 CBC_DataMatrixDetector::~CBC_DataMatrixDetector() {
     42   if (m_rectangleDetector != NULL) {
     43     delete m_rectangleDetector;
     44   }
     45   m_rectangleDetector = NULL;
     46 }
     47 inline FX_BOOL ResultPointsAndTransitionsComparator(void* a, void* b) {
     48   return ((CBC_ResultPointsAndTransitions*)b)->GetTransitions() >
     49          ((CBC_ResultPointsAndTransitions*)a)->GetTransitions();
     50 }
     51 CBC_QRDetectorResult* CBC_DataMatrixDetector::Detect(int32_t& e) {
     52   CFX_PtrArray* cornerPoints = m_rectangleDetector->Detect(e);
     53   BC_EXCEPTION_CHECK_ReturnValue(e, NULL);
     54   CBC_ResultPoint* pointA = (CBC_ResultPoint*)(*cornerPoints)[0];
     55   CBC_ResultPoint* pointB = (CBC_ResultPoint*)(*cornerPoints)[1];
     56   CBC_ResultPoint* pointC = (CBC_ResultPoint*)(*cornerPoints)[2];
     57   CBC_ResultPoint* pointD = (CBC_ResultPoint*)(*cornerPoints)[3];
     58   delete cornerPoints;
     59   cornerPoints = NULL;
     60   CFX_PtrArray transitions;
     61   transitions.Add(TransitionsBetween(pointA, pointB));
     62   transitions.Add(TransitionsBetween(pointA, pointC));
     63   transitions.Add(TransitionsBetween(pointB, pointD));
     64   transitions.Add(TransitionsBetween(pointC, pointD));
     65   BC_FX_PtrArray_Sort(transitions, &ResultPointsAndTransitionsComparator);
     66   delete ((CBC_ResultPointsAndTransitions*)transitions[2]);
     67   delete ((CBC_ResultPointsAndTransitions*)transitions[3]);
     68   CBC_ResultPointsAndTransitions* lSideOne =
     69       (CBC_ResultPointsAndTransitions*)transitions[0];
     70   CBC_ResultPointsAndTransitions* lSideTwo =
     71       (CBC_ResultPointsAndTransitions*)transitions[1];
     72   CFX_MapPtrTemplate<CBC_ResultPoint*, int32_t> pointCount;
     73   Increment(pointCount, lSideOne->GetFrom());
     74   Increment(pointCount, lSideOne->GetTo());
     75   Increment(pointCount, lSideTwo->GetFrom());
     76   Increment(pointCount, lSideTwo->GetTo());
     77   delete ((CBC_ResultPointsAndTransitions*)transitions[1]);
     78   delete ((CBC_ResultPointsAndTransitions*)transitions[0]);
     79   transitions.RemoveAll();
     80   CBC_ResultPoint* maybeTopLeft = NULL;
     81   CBC_ResultPoint* bottomLeft = NULL;
     82   CBC_ResultPoint* maybeBottomRight = NULL;
     83   FX_POSITION itBegin = pointCount.GetStartPosition();
     84   while (itBegin != NULL) {
     85     CBC_ResultPoint* key = 0;
     86     int32_t value = 0;
     87     pointCount.GetNextAssoc(itBegin, key, value);
     88     if (value == 2) {
     89       bottomLeft = key;
     90     } else {
     91       if (maybeBottomRight == NULL) {
     92         maybeBottomRight = key;
     93       } else {
     94         maybeTopLeft = key;
     95       }
     96     }
     97   }
     98   if (maybeTopLeft == NULL || bottomLeft == NULL || maybeBottomRight == NULL) {
     99     delete pointA;
    100     delete pointB;
    101     delete pointC;
    102     delete pointD;
    103     e = BCExceptionNotFound;
    104     return NULL;
    105   }
    106   CFX_PtrArray corners;
    107   corners.SetSize(3);
    108   corners[0] = maybeTopLeft;
    109   corners[1] = bottomLeft;
    110   corners[2] = maybeBottomRight;
    111   OrderBestPatterns(&corners);
    112   CBC_ResultPoint* bottomRight = (CBC_ResultPoint*)corners[0];
    113   bottomLeft = (CBC_ResultPoint*)corners[1];
    114   CBC_ResultPoint* topLeft = (CBC_ResultPoint*)corners[2];
    115   CBC_ResultPoint* topRight = NULL;
    116   int32_t value;
    117   if (!pointCount.Lookup(pointA, value)) {
    118     topRight = pointA;
    119   } else if (!pointCount.Lookup(pointB, value)) {
    120     topRight = pointB;
    121   } else if (!pointCount.Lookup(pointC, value)) {
    122     topRight = pointC;
    123   } else {
    124     topRight = pointD;
    125   }
    126   int32_t dimensionTop = CBC_AutoPtr<CBC_ResultPointsAndTransitions>(
    127                              TransitionsBetween(topLeft, topRight))
    128                              ->GetTransitions();
    129   int32_t dimensionRight = CBC_AutoPtr<CBC_ResultPointsAndTransitions>(
    130                                TransitionsBetween(bottomRight, topRight))
    131                                ->GetTransitions();
    132   if ((dimensionTop & 0x01) == 1) {
    133     dimensionTop++;
    134   }
    135   dimensionTop += 2;
    136   if ((dimensionRight & 0x01) == 1) {
    137     dimensionRight++;
    138   }
    139   dimensionRight += 2;
    140   CBC_AutoPtr<CBC_CommonBitMatrix> bits(NULL);
    141   CBC_AutoPtr<CBC_ResultPoint> correctedTopRight(NULL);
    142   if (4 * dimensionTop >= 7 * dimensionRight ||
    143       4 * dimensionRight >= 7 * dimensionTop) {
    144     correctedTopRight = CBC_AutoPtr<CBC_ResultPoint>(
    145         CorrectTopRightRectangular(bottomLeft, bottomRight, topLeft, topRight,
    146                                    dimensionTop, dimensionRight));
    147     if (correctedTopRight.get() == NULL) {
    148       correctedTopRight = CBC_AutoPtr<CBC_ResultPoint>(topRight);
    149     } else {
    150       delete topRight;
    151       topRight = NULL;
    152     }
    153     dimensionTop = CBC_AutoPtr<CBC_ResultPointsAndTransitions>(
    154                        TransitionsBetween(topLeft, correctedTopRight.get()))
    155                        ->GetTransitions();
    156     dimensionRight =
    157         CBC_AutoPtr<CBC_ResultPointsAndTransitions>(
    158             TransitionsBetween(bottomRight, correctedTopRight.get()))
    159             ->GetTransitions();
    160     if ((dimensionTop & 0x01) == 1) {
    161       dimensionTop++;
    162     }
    163     if ((dimensionRight & 0x01) == 1) {
    164       dimensionRight++;
    165     }
    166     bits = CBC_AutoPtr<CBC_CommonBitMatrix>(
    167         SampleGrid(m_image, topLeft, bottomLeft, bottomRight,
    168                    correctedTopRight.get(), dimensionTop, dimensionRight, e));
    169     BC_EXCEPTION_CHECK_ReturnValue(e, NULL);
    170   } else {
    171     int32_t dimension = std::min(dimensionRight, dimensionTop);
    172     correctedTopRight = CBC_AutoPtr<CBC_ResultPoint>(
    173         CorrectTopRight(bottomLeft, bottomRight, topLeft, topRight, dimension));
    174     if (correctedTopRight.get() == NULL) {
    175       correctedTopRight = CBC_AutoPtr<CBC_ResultPoint>(topRight);
    176     } else {
    177       delete topRight;
    178       topRight = NULL;
    179     }
    180     int32_t dimensionCorrected =
    181         std::max(CBC_AutoPtr<CBC_ResultPointsAndTransitions>(
    182                      TransitionsBetween(topLeft, correctedTopRight.get()))
    183                      ->GetTransitions(),
    184                  CBC_AutoPtr<CBC_ResultPointsAndTransitions>(
    185                      TransitionsBetween(bottomRight, correctedTopRight.get()))
    186                      ->GetTransitions());
    187     dimensionCorrected++;
    188     if ((dimensionCorrected & 0x01) == 1) {
    189       dimensionCorrected++;
    190     }
    191     bits = CBC_AutoPtr<CBC_CommonBitMatrix>(SampleGrid(
    192         m_image, topLeft, bottomLeft, bottomRight, correctedTopRight.get(),
    193         dimensionCorrected, dimensionCorrected, e));
    194     BC_EXCEPTION_CHECK_ReturnValue(e, NULL);
    195   }
    196   CFX_PtrArray* result = new CFX_PtrArray;
    197   result->SetSize(4);
    198   result->Add(topLeft);
    199   result->Add(bottomLeft);
    200   result->Add(bottomRight);
    201   result->Add(correctedTopRight.release());
    202   return new CBC_QRDetectorResult(bits.release(), result);
    203 }
    204 CBC_ResultPoint* CBC_DataMatrixDetector::CorrectTopRightRectangular(
    205     CBC_ResultPoint* bottomLeft,
    206     CBC_ResultPoint* bottomRight,
    207     CBC_ResultPoint* topLeft,
    208     CBC_ResultPoint* topRight,
    209     int32_t dimensionTop,
    210     int32_t dimensionRight) {
    211   FX_FLOAT corr = Distance(bottomLeft, bottomRight) / (FX_FLOAT)dimensionTop;
    212   int32_t norm = Distance(topLeft, topRight);
    213   FX_FLOAT cos = (topRight->GetX() - topLeft->GetX()) / norm;
    214   FX_FLOAT sin = (topRight->GetY() - topLeft->GetY()) / norm;
    215   CBC_AutoPtr<CBC_ResultPoint> c1(new CBC_ResultPoint(
    216       topRight->GetX() + corr * cos, topRight->GetY() + corr * sin));
    217   corr = Distance(bottomLeft, topLeft) / (FX_FLOAT)dimensionRight;
    218   norm = Distance(bottomRight, topRight);
    219   cos = (topRight->GetX() - bottomRight->GetX()) / norm;
    220   sin = (topRight->GetY() - bottomRight->GetY()) / norm;
    221   CBC_AutoPtr<CBC_ResultPoint> c2(new CBC_ResultPoint(
    222       topRight->GetX() + corr * cos, topRight->GetY() + corr * sin));
    223   if (!IsValid(c1.get())) {
    224     if (IsValid(c2.get())) {
    225       return c2.release();
    226     }
    227     return NULL;
    228   } else if (!IsValid(c2.get())) {
    229     return c1.release();
    230   }
    231   int32_t l1 = FXSYS_abs(dimensionTop -
    232                          CBC_AutoPtr<CBC_ResultPointsAndTransitions>(
    233                              TransitionsBetween(topLeft, c1.get()))
    234                              ->GetTransitions()) +
    235                FXSYS_abs(dimensionRight -
    236                          CBC_AutoPtr<CBC_ResultPointsAndTransitions>(
    237                              TransitionsBetween(bottomRight, c1.get()))
    238                              ->GetTransitions());
    239   int32_t l2 = FXSYS_abs(dimensionTop -
    240                          CBC_AutoPtr<CBC_ResultPointsAndTransitions>(
    241                              TransitionsBetween(topLeft, c2.get()))
    242                              ->GetTransitions()) +
    243                FXSYS_abs(dimensionRight -
    244                          CBC_AutoPtr<CBC_ResultPointsAndTransitions>(
    245                              TransitionsBetween(bottomRight, c2.get()))
    246                              ->GetTransitions());
    247   if (l1 <= l2) {
    248     return c1.release();
    249   }
    250   return c2.release();
    251 }
    252 CBC_ResultPoint* CBC_DataMatrixDetector::CorrectTopRight(
    253     CBC_ResultPoint* bottomLeft,
    254     CBC_ResultPoint* bottomRight,
    255     CBC_ResultPoint* topLeft,
    256     CBC_ResultPoint* topRight,
    257     int32_t dimension) {
    258   FX_FLOAT corr = Distance(bottomLeft, bottomRight) / (FX_FLOAT)dimension;
    259   int32_t norm = Distance(topLeft, topRight);
    260   FX_FLOAT cos = (topRight->GetX() - topLeft->GetX()) / norm;
    261   FX_FLOAT sin = (topRight->GetY() - topLeft->GetY()) / norm;
    262   CBC_AutoPtr<CBC_ResultPoint> c1(new CBC_ResultPoint(
    263       topRight->GetX() + corr * cos, topRight->GetY() + corr * sin));
    264   corr = Distance(bottomLeft, bottomRight) / (FX_FLOAT)dimension;
    265   norm = Distance(bottomRight, topRight);
    266   cos = (topRight->GetX() - bottomRight->GetX()) / norm;
    267   sin = (topRight->GetY() - bottomRight->GetY()) / norm;
    268   CBC_AutoPtr<CBC_ResultPoint> c2(new CBC_ResultPoint(
    269       topRight->GetX() + corr * cos, topRight->GetY() + corr * sin));
    270   if (!IsValid(c1.get())) {
    271     if (IsValid(c2.get())) {
    272       return c2.release();
    273     }
    274     return NULL;
    275   } else if (!IsValid(c2.get())) {
    276     return c1.release();
    277   }
    278   int32_t l1 = FXSYS_abs(CBC_AutoPtr<CBC_ResultPointsAndTransitions>(
    279                              TransitionsBetween(topLeft, c1.get()))
    280                              ->GetTransitions() -
    281                          CBC_AutoPtr<CBC_ResultPointsAndTransitions>(
    282                              TransitionsBetween(bottomRight, c1.get()))
    283                              ->GetTransitions());
    284   int32_t l2 = FXSYS_abs(CBC_AutoPtr<CBC_ResultPointsAndTransitions>(
    285                              TransitionsBetween(topLeft, c2.get()))
    286                              ->GetTransitions() -
    287                          CBC_AutoPtr<CBC_ResultPointsAndTransitions>(
    288                              TransitionsBetween(bottomRight, c2.get()))
    289                              ->GetTransitions());
    290   return l1 <= l2 ? c1.release() : c2.release();
    291 }
    292 FX_BOOL CBC_DataMatrixDetector::IsValid(CBC_ResultPoint* p) {
    293   return p->GetX() >= 0 && p->GetX() < m_image->GetWidth() && p->GetY() > 0 &&
    294          p->GetY() < m_image->GetHeight();
    295 }
    296 int32_t CBC_DataMatrixDetector::Round(FX_FLOAT d) {
    297   return (int32_t)(d + 0.5f);
    298 }
    299 int32_t CBC_DataMatrixDetector::Distance(CBC_ResultPoint* a,
    300                                          CBC_ResultPoint* b) {
    301   return Round(
    302       (FX_FLOAT)sqrt((a->GetX() - b->GetX()) * (a->GetX() - b->GetX()) +
    303                      (a->GetY() - b->GetY()) * (a->GetY() - b->GetY())));
    304 }
    305 void CBC_DataMatrixDetector::Increment(
    306     CFX_MapPtrTemplate<CBC_ResultPoint*, int32_t>& table,
    307     CBC_ResultPoint* key) {
    308   int32_t value;
    309   if (table.Lookup(key, value)) {
    310     table.SetAt(key, INTEGERS[value + 1]);
    311   } else {
    312     table.SetAt(key, INTEGERS[1]);
    313   }
    314 }
    315 CBC_CommonBitMatrix* CBC_DataMatrixDetector::SampleGrid(
    316     CBC_CommonBitMatrix* image,
    317     CBC_ResultPoint* topLeft,
    318     CBC_ResultPoint* bottomLeft,
    319     CBC_ResultPoint* bottomRight,
    320     CBC_ResultPoint* topRight,
    321     int32_t dimensionX,
    322     int32_t dimensionY,
    323     int32_t& e) {
    324   CBC_QRGridSampler& sampler = CBC_QRGridSampler::GetInstance();
    325   CBC_CommonBitMatrix* cbm = sampler.SampleGrid(
    326       image, dimensionX, dimensionY, 0.5f, 0.5f, dimensionX - 0.5f, 0.5f,
    327       dimensionX - 0.5f, dimensionY - 0.5f, 0.5f, dimensionY - 0.5f,
    328       topLeft->GetX(), topLeft->GetY(), topRight->GetX(), topRight->GetY(),
    329       bottomRight->GetX(), bottomRight->GetY(), bottomLeft->GetX(),
    330       bottomLeft->GetY(), e);
    331   BC_EXCEPTION_CHECK_ReturnValue(e, NULL);
    332   return cbm;
    333 }
    334 CBC_ResultPointsAndTransitions* CBC_DataMatrixDetector::TransitionsBetween(
    335     CBC_ResultPoint* from,
    336     CBC_ResultPoint* to) {
    337   int32_t fromX = (int32_t)from->GetX();
    338   int32_t fromY = (int32_t)from->GetY();
    339   int32_t toX = (int32_t)to->GetX();
    340   int32_t toY = (int32_t)to->GetY();
    341   FX_BOOL steep = FXSYS_abs(toY - fromY) > FXSYS_abs(toX - fromX);
    342   if (steep) {
    343     int32_t temp = fromX;
    344     fromX = fromY;
    345     fromY = temp;
    346     temp = toX;
    347     toX = toY;
    348     toY = temp;
    349   }
    350   int32_t dx = FXSYS_abs(toX - fromX);
    351   int32_t dy = FXSYS_abs(toY - fromY);
    352   int32_t error = -dx >> 1;
    353   int32_t ystep = fromY < toY ? 1 : -1;
    354   int32_t xstep = fromX < toX ? 1 : -1;
    355   int32_t transitions = 0;
    356   FX_BOOL inBlack = m_image->Get(steep ? fromY : fromX, steep ? fromX : fromY);
    357   for (int32_t x = fromX, y = fromY; x != toX; x += xstep) {
    358     FX_BOOL isBlack = m_image->Get(steep ? y : x, steep ? x : y);
    359     if (isBlack != inBlack) {
    360       transitions++;
    361       inBlack = isBlack;
    362     }
    363     error += dy;
    364     if (error > 0) {
    365       if (y == toY) {
    366         break;
    367       }
    368       y += ystep;
    369       error -= dx;
    370     }
    371   }
    372   return new CBC_ResultPointsAndTransitions(from, to, transitions);
    373 }
    374 void CBC_DataMatrixDetector::OrderBestPatterns(CFX_PtrArray* patterns) {
    375   FX_FLOAT abDistance = (FX_FLOAT)Distance((CBC_ResultPoint*)(*patterns)[0],
    376                                            (CBC_ResultPoint*)(*patterns)[1]);
    377   FX_FLOAT bcDistance = (FX_FLOAT)Distance((CBC_ResultPoint*)(*patterns)[1],
    378                                            (CBC_ResultPoint*)(*patterns)[2]);
    379   FX_FLOAT acDistance = (FX_FLOAT)Distance((CBC_ResultPoint*)(*patterns)[0],
    380                                            (CBC_ResultPoint*)(*patterns)[2]);
    381   CBC_ResultPoint *topLeft, *topRight, *bottomLeft;
    382   if (bcDistance >= abDistance && bcDistance >= acDistance) {
    383     topLeft = (CBC_ResultPoint*)(*patterns)[0];
    384     topRight = (CBC_ResultPoint*)(*patterns)[1];
    385     bottomLeft = (CBC_ResultPoint*)(*patterns)[2];
    386   } else if (acDistance >= bcDistance && acDistance >= abDistance) {
    387     topLeft = (CBC_ResultPoint*)(*patterns)[1];
    388     topRight = (CBC_ResultPoint*)(*patterns)[0];
    389     bottomLeft = (CBC_ResultPoint*)(*patterns)[2];
    390   } else {
    391     topLeft = (CBC_ResultPoint*)(*patterns)[2];
    392     topRight = (CBC_ResultPoint*)(*patterns)[0];
    393     bottomLeft = (CBC_ResultPoint*)(*patterns)[1];
    394   }
    395   if ((bottomLeft->GetY() - topLeft->GetY()) *
    396           (topRight->GetX() - topLeft->GetX()) <
    397       (bottomLeft->GetX() - topLeft->GetX()) *
    398           (topRight->GetY() - topLeft->GetY())) {
    399     CBC_ResultPoint* temp = topRight;
    400     topRight = bottomLeft;
    401     bottomLeft = temp;
    402   }
    403   (*patterns)[0] = bottomLeft;
    404   (*patterns)[1] = topLeft;
    405   (*patterns)[2] = topRight;
    406 }
    407