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