Merge XFA to PDFium master at 4dc95e7 on 10/28/2014
[pdfium.git] / xfa / src / fxbarcode / src / BC_DataMatrixDetector.cpp
1 // Copyright 2014 PDFium Authors. All rights reserved.\r
2 // Use of this source code is governed by a BSD-style license that can be\r
3 // found in the LICENSE file.\r
4 \r
5 // Original code copyright 2014 Foxit Software Inc. http://www.foxitsoftware.com\r
6 \r
7 #include "barcode.h"\r
8 #include "include/BC_DataMatrixDetector.h"\r
9 #include "include/BC_WhiteRectangleDetector.h"\r
10 #include "include/BC_ResultPoint.h"\r
11 #include "include/BC_QRFinderPatternFinder.h"\r
12 #include "include/BC_CommonBitMatrix.h"\r
13 #include "include/BC_QRDetectorResult.h"\r
14 #include "include/BC_QRGridSampler.h"\r
15 const FX_INT32 CBC_DataMatrixDetector::INTEGERS[5] = {0, 1, 2, 3, 4};\r
16 CBC_DataMatrixDetector::CBC_DataMatrixDetector(CBC_CommonBitMatrix *image):\r
17     m_image(image), m_rectangleDetector(NULL)\r
18 {\r
19 }\r
20 void CBC_DataMatrixDetector::Init(FX_INT32 &e)\r
21 {\r
22     m_rectangleDetector = FX_NEW CBC_WhiteRectangleDetector(m_image);\r
23     m_rectangleDetector->Init(e);\r
24     BC_EXCEPTION_CHECK_ReturnVoid(e);\r
25 }\r
26 CBC_DataMatrixDetector::~CBC_DataMatrixDetector()\r
27 {\r
28     if(m_rectangleDetector != NULL) {\r
29         delete m_rectangleDetector;\r
30     }\r
31     m_rectangleDetector = NULL;\r
32 }\r
33 inline FX_BOOL ResultPointsAndTransitionsComparator(FX_LPVOID a, FX_LPVOID b)\r
34 {\r
35     return ((CBC_ResultPointsAndTransitions *)b)->GetTransitions() > ((CBC_ResultPointsAndTransitions *)a)->GetTransitions();\r
36 }\r
37 CBC_QRDetectorResult *CBC_DataMatrixDetector::Detect(FX_INT32 &e)\r
38 {\r
39     CFX_PtrArray* cornerPoints = m_rectangleDetector->Detect(e);\r
40     BC_EXCEPTION_CHECK_ReturnValue(e, NULL);\r
41     CBC_ResultPoint *pointA = (CBC_ResultPoint*)(*cornerPoints)[0];\r
42     CBC_ResultPoint *pointB = (CBC_ResultPoint*)(*cornerPoints)[1];\r
43     CBC_ResultPoint *pointC = (CBC_ResultPoint*)(*cornerPoints)[2];\r
44     CBC_ResultPoint *pointD = (CBC_ResultPoint*)(*cornerPoints)[3];\r
45     delete cornerPoints;\r
46     cornerPoints = NULL;\r
47     CFX_PtrArray transitions;\r
48     transitions.Add(TransitionsBetween(pointA, pointB));\r
49     transitions.Add(TransitionsBetween(pointA, pointC));\r
50     transitions.Add(TransitionsBetween(pointB, pointD));\r
51     transitions.Add(TransitionsBetween(pointC, pointD));\r
52     BC_FX_PtrArray_Sort(transitions, &ResultPointsAndTransitionsComparator);\r
53     delete ( (CBC_ResultPointsAndTransitions *)transitions[2] );\r
54     delete ( (CBC_ResultPointsAndTransitions *)transitions[3] );\r
55     CBC_ResultPointsAndTransitions *lSideOne = (CBC_ResultPointsAndTransitions*)transitions[0];\r
56     CBC_ResultPointsAndTransitions *lSideTwo = (CBC_ResultPointsAndTransitions*)transitions[1];\r
57     CFX_MapPtrTemplate<CBC_ResultPoint*, FX_INT32> pointCount;\r
58     Increment(pointCount, lSideOne->GetFrom());\r
59     Increment(pointCount, lSideOne->GetTo());\r
60     Increment(pointCount, lSideTwo->GetFrom());\r
61     Increment(pointCount, lSideTwo->GetTo());\r
62     delete ( (CBC_ResultPointsAndTransitions *)transitions[1] );\r
63     delete ( (CBC_ResultPointsAndTransitions *)transitions[0] );\r
64     transitions.RemoveAll();\r
65     CBC_ResultPoint *maybeTopLeft = NULL;\r
66     CBC_ResultPoint *bottomLeft = NULL;\r
67     CBC_ResultPoint *maybeBottomRight = NULL;\r
68     FX_POSITION itBegin = pointCount.GetStartPosition();\r
69     while(itBegin != NULL) {\r
70         CBC_ResultPoint *key = 0;\r
71         FX_INT32 value = 0;\r
72         pointCount.GetNextAssoc(itBegin, key, value);\r
73         if(value == 2) {\r
74             bottomLeft = key;\r
75         } else {\r
76             if (maybeBottomRight == NULL) {\r
77                 maybeBottomRight = key;\r
78             } else {\r
79                 maybeTopLeft = key;\r
80             }\r
81         }\r
82     }\r
83     if (maybeTopLeft == NULL || bottomLeft == NULL || maybeBottomRight == NULL) {\r
84         delete pointA;\r
85         delete pointB;\r
86         delete pointC;\r
87         delete pointD;\r
88         e = BCExceptionNotFound;\r
89         return NULL;\r
90     }\r
91     CFX_PtrArray corners;\r
92     corners.SetSize(3);\r
93     corners[0] = maybeTopLeft;\r
94     corners[1] = bottomLeft;\r
95     corners[2] = maybeBottomRight;\r
96     OrderBestPatterns(&corners);\r
97     CBC_ResultPoint *bottomRight = (CBC_ResultPoint*)corners[0];\r
98     bottomLeft = (CBC_ResultPoint*)corners[1];\r
99     CBC_ResultPoint *topLeft = (CBC_ResultPoint*)corners[2];\r
100     CBC_ResultPoint *topRight = NULL;\r
101     FX_INT32 value;\r
102     if (!pointCount.Lookup(pointA, value)) {\r
103         topRight = pointA;\r
104     } else if (!pointCount.Lookup(pointB, value)) {\r
105         topRight = pointB;\r
106     } else if (!pointCount.Lookup(pointC, value)) {\r
107         topRight = pointC;\r
108     } else {\r
109         topRight = pointD;\r
110     }\r
111     FX_INT32 dimensionTop = CBC_AutoPtr<CBC_ResultPointsAndTransitions>(TransitionsBetween(topLeft, topRight))->GetTransitions();\r
112     FX_INT32 dimensionRight = CBC_AutoPtr<CBC_ResultPointsAndTransitions>(TransitionsBetween(bottomRight, topRight))->GetTransitions();\r
113     if ((dimensionTop & 0x01) == 1) {\r
114         dimensionTop++;\r
115     }\r
116     dimensionTop += 2;\r
117     if ((dimensionRight & 0x01) == 1) {\r
118         dimensionRight++;\r
119     }\r
120     dimensionRight += 2;\r
121     CBC_AutoPtr<CBC_CommonBitMatrix> bits(NULL);\r
122     CBC_AutoPtr<CBC_ResultPoint> correctedTopRight(NULL);\r
123     if (4 * dimensionTop >= 7 * dimensionRight || 4 * dimensionRight >= 7 * dimensionTop) {\r
124         correctedTopRight =\r
125             CBC_AutoPtr<CBC_ResultPoint>(CorrectTopRightRectangular(bottomLeft, bottomRight, topLeft, topRight,\r
126                                          dimensionTop, dimensionRight));\r
127         if (correctedTopRight.get() == NULL) {\r
128             correctedTopRight = CBC_AutoPtr<CBC_ResultPoint>(topRight);\r
129         } else {\r
130             delete topRight;\r
131             topRight = NULL;\r
132         }\r
133         dimensionTop = CBC_AutoPtr<CBC_ResultPointsAndTransitions>(TransitionsBetween(topLeft, correctedTopRight.get()))->GetTransitions();\r
134         dimensionRight = CBC_AutoPtr<CBC_ResultPointsAndTransitions>(TransitionsBetween(bottomRight, correctedTopRight.get()))->GetTransitions();\r
135         if ((dimensionTop & 0x01) == 1) {\r
136             dimensionTop++;\r
137         }\r
138         if ((dimensionRight & 0x01) == 1) {\r
139             dimensionRight++;\r
140         }\r
141         bits = CBC_AutoPtr<CBC_CommonBitMatrix>(SampleGrid(m_image, topLeft, bottomLeft, bottomRight,\r
142                                                 correctedTopRight.get(), dimensionTop, dimensionRight, e));\r
143         BC_EXCEPTION_CHECK_ReturnValue(e, NULL);\r
144     } else {\r
145         FX_INT32 dimension = FX_MIN(dimensionRight, dimensionTop);\r
146         correctedTopRight = CBC_AutoPtr<CBC_ResultPoint>(CorrectTopRight(bottomLeft, bottomRight,\r
147                             topLeft, topRight, dimension));\r
148         if (correctedTopRight.get() == NULL) {\r
149             correctedTopRight = CBC_AutoPtr<CBC_ResultPoint>(topRight);\r
150         } else {\r
151             delete topRight;\r
152             topRight = NULL;\r
153         }\r
154         FX_INT32 dimensionCorrected = FX_MAX(CBC_AutoPtr<CBC_ResultPointsAndTransitions>(TransitionsBetween(topLeft, correctedTopRight.get()))->GetTransitions(),\r
155                                              CBC_AutoPtr<CBC_ResultPointsAndTransitions>(TransitionsBetween(bottomRight, correctedTopRight.get()))->GetTransitions());\r
156         dimensionCorrected++;\r
157         if ((dimensionCorrected & 0x01) == 1) {\r
158             dimensionCorrected++;\r
159         }\r
160         bits = CBC_AutoPtr<CBC_CommonBitMatrix>(SampleGrid(m_image,\r
161                                                 topLeft,\r
162                                                 bottomLeft,\r
163                                                 bottomRight,\r
164                                                 correctedTopRight.get(),\r
165                                                 dimensionCorrected,\r
166                                                 dimensionCorrected, e));\r
167         BC_EXCEPTION_CHECK_ReturnValue(e, NULL);\r
168     }\r
169     CFX_PtrArray *result = FX_NEW CFX_PtrArray;\r
170     result->SetSize(4);\r
171     result->Add(topLeft);\r
172     result->Add(bottomLeft);\r
173     result->Add(bottomRight);\r
174     result->Add(correctedTopRight.release());\r
175     return FX_NEW CBC_QRDetectorResult(bits.release(), result);\r
176 }\r
177 CBC_ResultPoint *CBC_DataMatrixDetector::CorrectTopRightRectangular(CBC_ResultPoint *bottomLeft, CBC_ResultPoint *bottomRight, CBC_ResultPoint *topLeft, CBC_ResultPoint *topRight, FX_INT32 dimensionTop, FX_INT32 dimensionRight)\r
178 {\r
179     FX_FLOAT corr = Distance(bottomLeft, bottomRight) / (FX_FLOAT)dimensionTop;\r
180     FX_INT32 norm = Distance(topLeft, topRight);\r
181     FX_FLOAT cos = (topRight->GetX() - topLeft->GetX()) / norm;\r
182     FX_FLOAT sin = (topRight->GetY() - topLeft->GetY()) / norm;\r
183     CBC_AutoPtr<CBC_ResultPoint> c1(FX_NEW CBC_ResultPoint(topRight->GetX() + corr * cos, topRight->GetY() + corr * sin));\r
184     corr = Distance(bottomLeft, topLeft) / (FX_FLOAT)dimensionRight;\r
185     norm = Distance(bottomRight, topRight);\r
186     cos = (topRight->GetX() - bottomRight->GetX()) / norm;\r
187     sin = (topRight->GetY() - bottomRight->GetY()) / norm;\r
188     CBC_AutoPtr<CBC_ResultPoint> c2(FX_NEW CBC_ResultPoint(topRight->GetX() + corr * cos, topRight->GetY() + corr * sin));\r
189     if (!IsValid(c1.get())) {\r
190         if (IsValid(c2.get())) {\r
191             return c2.release();\r
192         }\r
193         return NULL;\r
194     } else if (!IsValid(c2.get())) {\r
195         return c1.release();\r
196     }\r
197     FX_INT32 l1 = FXSYS_abs(dimensionTop - CBC_AutoPtr<CBC_ResultPointsAndTransitions>(TransitionsBetween(topLeft, c1.get()))->GetTransitions()) +\r
198                   FXSYS_abs(dimensionRight - CBC_AutoPtr<CBC_ResultPointsAndTransitions>(TransitionsBetween(bottomRight, c1.get()))->GetTransitions());\r
199     FX_INT32 l2 = FXSYS_abs(dimensionTop - CBC_AutoPtr<CBC_ResultPointsAndTransitions>(TransitionsBetween(topLeft, c2.get()))->GetTransitions()) +\r
200                   FXSYS_abs(dimensionRight - CBC_AutoPtr<CBC_ResultPointsAndTransitions>(TransitionsBetween(bottomRight, c2.get()))->GetTransitions());\r
201     if (l1 <= l2) {\r
202         return c1.release();\r
203     }\r
204     return c2.release();\r
205 }\r
206 CBC_ResultPoint *CBC_DataMatrixDetector::CorrectTopRight(CBC_ResultPoint *bottomLeft, CBC_ResultPoint *bottomRight, CBC_ResultPoint *topLeft, CBC_ResultPoint *topRight, FX_INT32 dimension)\r
207 {\r
208     FX_FLOAT corr = Distance(bottomLeft, bottomRight) / (FX_FLOAT) dimension;\r
209     FX_INT32 norm = Distance(topLeft, topRight);\r
210     FX_FLOAT cos = (topRight->GetX() - topLeft->GetX()) / norm;\r
211     FX_FLOAT sin = (topRight->GetY() - topLeft->GetY()) / norm;\r
212     CBC_AutoPtr<CBC_ResultPoint> c1(FX_NEW CBC_ResultPoint(topRight->GetX() + corr * cos, topRight->GetY() + corr * sin));\r
213     corr = Distance(bottomLeft, bottomRight) / (FX_FLOAT) dimension;\r
214     norm = Distance(bottomRight, topRight);\r
215     cos = (topRight->GetX() - bottomRight->GetX()) / norm;\r
216     sin = (topRight->GetY() - bottomRight->GetY()) / norm;\r
217     CBC_AutoPtr<CBC_ResultPoint> c2(FX_NEW CBC_ResultPoint(topRight->GetX() + corr * cos, topRight->GetY() + corr * sin));\r
218     if (!IsValid(c1.get())) {\r
219         if (IsValid(c2.get())) {\r
220             return c2.release();\r
221         }\r
222         return NULL;\r
223     } else if (!IsValid(c2.get())) {\r
224         return c1.release();\r
225     }\r
226     FX_INT32 l1 = FXSYS_abs(CBC_AutoPtr<CBC_ResultPointsAndTransitions>(TransitionsBetween(topLeft, c1.get()))->GetTransitions() -\r
227                             CBC_AutoPtr<CBC_ResultPointsAndTransitions>(TransitionsBetween(bottomRight, c1.get()))->GetTransitions());\r
228     FX_INT32 l2 = FXSYS_abs(CBC_AutoPtr<CBC_ResultPointsAndTransitions>(TransitionsBetween(topLeft, c2.get()))->GetTransitions() -\r
229                             CBC_AutoPtr<CBC_ResultPointsAndTransitions>(TransitionsBetween(bottomRight, c2.get()))->GetTransitions());\r
230     return l1 <= l2 ? c1.release() : c2.release();\r
231 }\r
232 FX_BOOL CBC_DataMatrixDetector::IsValid(CBC_ResultPoint *p)\r
233 {\r
234     return p->GetX() >= 0 && p->GetX() < m_image->GetWidth() && p->GetY() > 0 && p->GetY() < m_image->GetHeight();\r
235 }\r
236 FX_INT32 CBC_DataMatrixDetector::Round(FX_FLOAT d)\r
237 {\r
238     return (FX_INT32) (d + 0.5f);\r
239 }\r
240 FX_INT32 CBC_DataMatrixDetector::Distance(CBC_ResultPoint *a, CBC_ResultPoint *b)\r
241 {\r
242     return Round((FX_FLOAT) sqrt((a->GetX() - b->GetX())\r
243                                  * (a->GetX() - b->GetX()) + (a->GetY() - b->GetY())\r
244                                  * (a->GetY() - b->GetY())));\r
245 }\r
246 void CBC_DataMatrixDetector::Increment(CFX_MapPtrTemplate<CBC_ResultPoint*, FX_INT32> &table, CBC_ResultPoint *key)\r
247 {\r
248     FX_INT32 value;\r
249     if(table.Lookup(key, value)) {\r
250         table.SetAt(key, INTEGERS[value + 1]);\r
251     } else {\r
252         table.SetAt(key, INTEGERS[1]);\r
253     }\r
254 }\r
255 CBC_CommonBitMatrix *CBC_DataMatrixDetector::SampleGrid(CBC_CommonBitMatrix *image,\r
256         CBC_ResultPoint *topLeft,\r
257         CBC_ResultPoint *bottomLeft,\r
258         CBC_ResultPoint *bottomRight,\r
259         CBC_ResultPoint *topRight,\r
260         FX_INT32 dimensionX, FX_INT32 dimensionY, FX_INT32 &e)\r
261 {\r
262     CBC_QRGridSampler &sampler = CBC_QRGridSampler::GetInstance();\r
263     CBC_CommonBitMatrix* cbm = sampler.SampleGrid(image,\r
264                                dimensionX,\r
265                                dimensionY,\r
266                                0.5f,\r
267                                0.5f,\r
268                                dimensionX - 0.5f,\r
269                                0.5f,\r
270                                dimensionX - 0.5f,\r
271                                dimensionY - 0.5f,\r
272                                0.5f,\r
273                                dimensionY - 0.5f,\r
274                                topLeft->GetX(),\r
275                                topLeft->GetY(),\r
276                                topRight->GetX(),\r
277                                topRight->GetY(),\r
278                                bottomRight->GetX(),\r
279                                bottomRight->GetY(),\r
280                                bottomLeft->GetX(),\r
281                                bottomLeft->GetY(), e);\r
282     BC_EXCEPTION_CHECK_ReturnValue(e, NULL);\r
283     return cbm;\r
284 }\r
285 CBC_ResultPointsAndTransitions *CBC_DataMatrixDetector::TransitionsBetween(CBC_ResultPoint *from, CBC_ResultPoint *to)\r
286 {\r
287     FX_INT32 fromX = (FX_INT32) from->GetX();\r
288     FX_INT32 fromY = (FX_INT32) from->GetY();\r
289     FX_INT32 toX = (FX_INT32) to->GetX();\r
290     FX_INT32 toY = (FX_INT32) to->GetY();\r
291     FX_BOOL steep = FXSYS_abs(toY - fromY) > FXSYS_abs(toX - fromX);\r
292     if (steep) {\r
293         FX_INT32 temp = fromX;\r
294         fromX = fromY;\r
295         fromY = temp;\r
296         temp = toX;\r
297         toX = toY;\r
298         toY = temp;\r
299     }\r
300     FX_INT32 dx = FXSYS_abs(toX - fromX);\r
301     FX_INT32 dy = FXSYS_abs(toY - fromY);\r
302     FX_INT32 error = -dx >> 1;\r
303     FX_INT32 ystep = fromY < toY ? 1 : -1;\r
304     FX_INT32 xstep = fromX < toX ? 1 : -1;\r
305     FX_INT32 transitions = 0;\r
306     FX_BOOL inBlack = m_image->Get(steep ? fromY : fromX, steep ? fromX : fromY);\r
307     for (FX_INT32 x = fromX, y = fromY; x != toX; x += xstep) {\r
308         FX_BOOL isBlack = m_image->Get(steep ? y : x, steep ? x : y);\r
309         if (isBlack != inBlack) {\r
310             transitions++;\r
311             inBlack = isBlack;\r
312         }\r
313         error += dy;\r
314         if (error > 0) {\r
315             if (y == toY) {\r
316                 break;\r
317             }\r
318             y += ystep;\r
319             error -= dx;\r
320         }\r
321     }\r
322     return FX_NEW CBC_ResultPointsAndTransitions(from, to, transitions);\r
323 }\r
324 void CBC_DataMatrixDetector::OrderBestPatterns(CFX_PtrArray *patterns)\r
325 {\r
326     FX_FLOAT abDistance = (FX_FLOAT)Distance((CBC_ResultPoint*)(*patterns)[0], (CBC_ResultPoint*)(*patterns)[1]);\r
327     FX_FLOAT bcDistance = (FX_FLOAT)Distance((CBC_ResultPoint*)(*patterns)[1], (CBC_ResultPoint*)(*patterns)[2]);\r
328     FX_FLOAT acDistance = (FX_FLOAT)Distance((CBC_ResultPoint*)(*patterns)[0], (CBC_ResultPoint*)(*patterns)[2]);\r
329     CBC_ResultPoint *topLeft, *topRight, *bottomLeft;\r
330     if (bcDistance >= abDistance && bcDistance >= acDistance) {\r
331         topLeft = (CBC_ResultPoint*)(*patterns)[0];\r
332         topRight = (CBC_ResultPoint*)(*patterns)[1];\r
333         bottomLeft = (CBC_ResultPoint*)(*patterns)[2];\r
334     } else if (acDistance >= bcDistance && acDistance >= abDistance) {\r
335         topLeft = (CBC_ResultPoint*)(*patterns)[1];\r
336         topRight = (CBC_ResultPoint*)(*patterns)[0];\r
337         bottomLeft = (CBC_ResultPoint*)(*patterns)[2];\r
338     } else {\r
339         topLeft = (CBC_ResultPoint*)(*patterns)[2];\r
340         topRight = (CBC_ResultPoint*)(*patterns)[0];\r
341         bottomLeft = (CBC_ResultPoint*)(*patterns)[1];\r
342     }\r
343     if ((bottomLeft->GetY() - topLeft->GetY()) * (topRight->GetX() - topLeft->GetX()) < (bottomLeft->GetX()\r
344             - topLeft->GetX()) * (topRight->GetY() - topLeft->GetY())) {\r
345         CBC_ResultPoint *temp = topRight;\r
346         topRight = bottomLeft;\r
347         bottomLeft = temp;\r
348     }\r
349     (*patterns)[0] = bottomLeft;\r
350     (*patterns)[1] = topLeft;\r
351     (*patterns)[2] = topRight;\r
352 }\r