• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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};
CBC_DataMatrixDetector(CBC_CommonBitMatrix * image)34 CBC_DataMatrixDetector::CBC_DataMatrixDetector(CBC_CommonBitMatrix* image)
35     : m_image(image), m_rectangleDetector(NULL) {}
Init(int32_t & e)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 }
~CBC_DataMatrixDetector()41 CBC_DataMatrixDetector::~CBC_DataMatrixDetector() {
42   if (m_rectangleDetector != NULL) {
43     delete m_rectangleDetector;
44   }
45   m_rectangleDetector = NULL;
46 }
ResultPointsAndTransitionsComparator(void * a,void * b)47 inline FX_BOOL ResultPointsAndTransitionsComparator(void* a, void* b) {
48   return ((CBC_ResultPointsAndTransitions*)b)->GetTransitions() >
49          ((CBC_ResultPointsAndTransitions*)a)->GetTransitions();
50 }
Detect(int32_t & e)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 }
CorrectTopRightRectangular(CBC_ResultPoint * bottomLeft,CBC_ResultPoint * bottomRight,CBC_ResultPoint * topLeft,CBC_ResultPoint * topRight,int32_t dimensionTop,int32_t dimensionRight)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 }
CorrectTopRight(CBC_ResultPoint * bottomLeft,CBC_ResultPoint * bottomRight,CBC_ResultPoint * topLeft,CBC_ResultPoint * topRight,int32_t dimension)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 }
IsValid(CBC_ResultPoint * p)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 }
Round(FX_FLOAT d)296 int32_t CBC_DataMatrixDetector::Round(FX_FLOAT d) {
297   return (int32_t)(d + 0.5f);
298 }
Distance(CBC_ResultPoint * a,CBC_ResultPoint * b)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 }
Increment(CFX_MapPtrTemplate<CBC_ResultPoint *,int32_t> & table,CBC_ResultPoint * key)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 }
SampleGrid(CBC_CommonBitMatrix * image,CBC_ResultPoint * topLeft,CBC_ResultPoint * bottomLeft,CBC_ResultPoint * bottomRight,CBC_ResultPoint * topRight,int32_t dimensionX,int32_t dimensionY,int32_t & e)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 }
TransitionsBetween(CBC_ResultPoint * from,CBC_ResultPoint * to)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 }
OrderBestPatterns(CFX_PtrArray * patterns)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