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