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