// Copyright 2014 PDFium Authors. All rights reserved. | |
// Use of this source code is governed by a BSD-style license that can be | |
// found in the LICENSE file. | |
// Original code copyright 2014 Foxit Software Inc. http://www.foxitsoftware.com | |
// Original code is licensed as follows: | |
/* | |
* Copyright 2008 ZXing authors | |
* | |
* Licensed under the Apache License, Version 2.0 (the "License"); | |
* you may not use this file except in compliance with the License. | |
* You may obtain a copy of the License at | |
* | |
* http://www.apache.org/licenses/LICENSE-2.0 | |
* | |
* Unless required by applicable law or agreed to in writing, software | |
* distributed under the License is distributed on an "AS IS" BASIS, | |
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. | |
* See the License for the specific language governing permissions and | |
* limitations under the License. | |
*/ | |
#include <algorithm> | |
#include "xfa/src/fxbarcode/barcode.h" | |
#include "xfa/src/fxbarcode/BC_ResultPoint.h" | |
#include "xfa/src/fxbarcode/common/BC_WhiteRectangleDetector.h" | |
#include "xfa/src/fxbarcode/common/BC_CommonBitMatrix.h" | |
#include "xfa/src/fxbarcode/qrcode/BC_QRFinderPatternFinder.h" | |
#include "xfa/src/fxbarcode/qrcode/BC_QRDetectorResult.h" | |
#include "xfa/src/fxbarcode/qrcode/BC_QRGridSampler.h" | |
#include "BC_DataMatrixDetector.h" | |
const int32_t CBC_DataMatrixDetector::INTEGERS[5] = {0, 1, 2, 3, 4}; | |
CBC_DataMatrixDetector::CBC_DataMatrixDetector(CBC_CommonBitMatrix* image) | |
: m_image(image), m_rectangleDetector(NULL) {} | |
void CBC_DataMatrixDetector::Init(int32_t& e) { | |
m_rectangleDetector = new CBC_WhiteRectangleDetector(m_image); | |
m_rectangleDetector->Init(e); | |
BC_EXCEPTION_CHECK_ReturnVoid(e); | |
} | |
CBC_DataMatrixDetector::~CBC_DataMatrixDetector() { | |
if (m_rectangleDetector != NULL) { | |
delete m_rectangleDetector; | |
} | |
m_rectangleDetector = NULL; | |
} | |
inline FX_BOOL ResultPointsAndTransitionsComparator(void* a, void* b) { | |
return ((CBC_ResultPointsAndTransitions*)b)->GetTransitions() > | |
((CBC_ResultPointsAndTransitions*)a)->GetTransitions(); | |
} | |
CBC_QRDetectorResult* CBC_DataMatrixDetector::Detect(int32_t& e) { | |
CFX_PtrArray* cornerPoints = m_rectangleDetector->Detect(e); | |
BC_EXCEPTION_CHECK_ReturnValue(e, NULL); | |
CBC_ResultPoint* pointA = (CBC_ResultPoint*)(*cornerPoints)[0]; | |
CBC_ResultPoint* pointB = (CBC_ResultPoint*)(*cornerPoints)[1]; | |
CBC_ResultPoint* pointC = (CBC_ResultPoint*)(*cornerPoints)[2]; | |
CBC_ResultPoint* pointD = (CBC_ResultPoint*)(*cornerPoints)[3]; | |
delete cornerPoints; | |
cornerPoints = NULL; | |
CFX_PtrArray transitions; | |
transitions.Add(TransitionsBetween(pointA, pointB)); | |
transitions.Add(TransitionsBetween(pointA, pointC)); | |
transitions.Add(TransitionsBetween(pointB, pointD)); | |
transitions.Add(TransitionsBetween(pointC, pointD)); | |
BC_FX_PtrArray_Sort(transitions, &ResultPointsAndTransitionsComparator); | |
delete ((CBC_ResultPointsAndTransitions*)transitions[2]); | |
delete ((CBC_ResultPointsAndTransitions*)transitions[3]); | |
CBC_ResultPointsAndTransitions* lSideOne = | |
(CBC_ResultPointsAndTransitions*)transitions[0]; | |
CBC_ResultPointsAndTransitions* lSideTwo = | |
(CBC_ResultPointsAndTransitions*)transitions[1]; | |
CFX_MapPtrTemplate<CBC_ResultPoint*, int32_t> pointCount; | |
Increment(pointCount, lSideOne->GetFrom()); | |
Increment(pointCount, lSideOne->GetTo()); | |
Increment(pointCount, lSideTwo->GetFrom()); | |
Increment(pointCount, lSideTwo->GetTo()); | |
delete ((CBC_ResultPointsAndTransitions*)transitions[1]); | |
delete ((CBC_ResultPointsAndTransitions*)transitions[0]); | |
transitions.RemoveAll(); | |
CBC_ResultPoint* maybeTopLeft = NULL; | |
CBC_ResultPoint* bottomLeft = NULL; | |
CBC_ResultPoint* maybeBottomRight = NULL; | |
FX_POSITION itBegin = pointCount.GetStartPosition(); | |
while (itBegin != NULL) { | |
CBC_ResultPoint* key = 0; | |
int32_t value = 0; | |
pointCount.GetNextAssoc(itBegin, key, value); | |
if (value == 2) { | |
bottomLeft = key; | |
} else { | |
if (maybeBottomRight == NULL) { | |
maybeBottomRight = key; | |
} else { | |
maybeTopLeft = key; | |
} | |
} | |
} | |
if (maybeTopLeft == NULL || bottomLeft == NULL || maybeBottomRight == NULL) { | |
delete pointA; | |
delete pointB; | |
delete pointC; | |
delete pointD; | |
e = BCExceptionNotFound; | |
return NULL; | |
} | |
CFX_PtrArray corners; | |
corners.SetSize(3); | |
corners[0] = maybeTopLeft; | |
corners[1] = bottomLeft; | |
corners[2] = maybeBottomRight; | |
OrderBestPatterns(&corners); | |
CBC_ResultPoint* bottomRight = (CBC_ResultPoint*)corners[0]; | |
bottomLeft = (CBC_ResultPoint*)corners[1]; | |
CBC_ResultPoint* topLeft = (CBC_ResultPoint*)corners[2]; | |
CBC_ResultPoint* topRight = NULL; | |
int32_t value; | |
if (!pointCount.Lookup(pointA, value)) { | |
topRight = pointA; | |
} else if (!pointCount.Lookup(pointB, value)) { | |
topRight = pointB; | |
} else if (!pointCount.Lookup(pointC, value)) { | |
topRight = pointC; | |
} else { | |
topRight = pointD; | |
} | |
int32_t dimensionTop = CBC_AutoPtr<CBC_ResultPointsAndTransitions>( | |
TransitionsBetween(topLeft, topRight)) | |
->GetTransitions(); | |
int32_t dimensionRight = CBC_AutoPtr<CBC_ResultPointsAndTransitions>( | |
TransitionsBetween(bottomRight, topRight)) | |
->GetTransitions(); | |
if ((dimensionTop & 0x01) == 1) { | |
dimensionTop++; | |
} | |
dimensionTop += 2; | |
if ((dimensionRight & 0x01) == 1) { | |
dimensionRight++; | |
} | |
dimensionRight += 2; | |
CBC_AutoPtr<CBC_CommonBitMatrix> bits(NULL); | |
CBC_AutoPtr<CBC_ResultPoint> correctedTopRight(NULL); | |
if (4 * dimensionTop >= 7 * dimensionRight || | |
4 * dimensionRight >= 7 * dimensionTop) { | |
correctedTopRight = CBC_AutoPtr<CBC_ResultPoint>( | |
CorrectTopRightRectangular(bottomLeft, bottomRight, topLeft, topRight, | |
dimensionTop, dimensionRight)); | |
if (correctedTopRight.get() == NULL) { | |
correctedTopRight = CBC_AutoPtr<CBC_ResultPoint>(topRight); | |
} else { | |
delete topRight; | |
topRight = NULL; | |
} | |
dimensionTop = CBC_AutoPtr<CBC_ResultPointsAndTransitions>( | |
TransitionsBetween(topLeft, correctedTopRight.get())) | |
->GetTransitions(); | |
dimensionRight = | |
CBC_AutoPtr<CBC_ResultPointsAndTransitions>( | |
TransitionsBetween(bottomRight, correctedTopRight.get())) | |
->GetTransitions(); | |
if ((dimensionTop & 0x01) == 1) { | |
dimensionTop++; | |
} | |
if ((dimensionRight & 0x01) == 1) { | |
dimensionRight++; | |
} | |
bits = CBC_AutoPtr<CBC_CommonBitMatrix>( | |
SampleGrid(m_image, topLeft, bottomLeft, bottomRight, | |
correctedTopRight.get(), dimensionTop, dimensionRight, e)); | |
BC_EXCEPTION_CHECK_ReturnValue(e, NULL); | |
} else { | |
int32_t dimension = std::min(dimensionRight, dimensionTop); | |
correctedTopRight = CBC_AutoPtr<CBC_ResultPoint>( | |
CorrectTopRight(bottomLeft, bottomRight, topLeft, topRight, dimension)); | |
if (correctedTopRight.get() == NULL) { | |
correctedTopRight = CBC_AutoPtr<CBC_ResultPoint>(topRight); | |
} else { | |
delete topRight; | |
topRight = NULL; | |
} | |
int32_t dimensionCorrected = | |
std::max(CBC_AutoPtr<CBC_ResultPointsAndTransitions>( | |
TransitionsBetween(topLeft, correctedTopRight.get())) | |
->GetTransitions(), | |
CBC_AutoPtr<CBC_ResultPointsAndTransitions>( | |
TransitionsBetween(bottomRight, correctedTopRight.get())) | |
->GetTransitions()); | |
dimensionCorrected++; | |
if ((dimensionCorrected & 0x01) == 1) { | |
dimensionCorrected++; | |
} | |
bits = CBC_AutoPtr<CBC_CommonBitMatrix>(SampleGrid( | |
m_image, topLeft, bottomLeft, bottomRight, correctedTopRight.get(), | |
dimensionCorrected, dimensionCorrected, e)); | |
BC_EXCEPTION_CHECK_ReturnValue(e, NULL); | |
} | |
CFX_PtrArray* result = new CFX_PtrArray; | |
result->SetSize(4); | |
result->Add(topLeft); | |
result->Add(bottomLeft); | |
result->Add(bottomRight); | |
result->Add(correctedTopRight.release()); | |
return new CBC_QRDetectorResult(bits.release(), result); | |
} | |
CBC_ResultPoint* CBC_DataMatrixDetector::CorrectTopRightRectangular( | |
CBC_ResultPoint* bottomLeft, | |
CBC_ResultPoint* bottomRight, | |
CBC_ResultPoint* topLeft, | |
CBC_ResultPoint* topRight, | |
int32_t dimensionTop, | |
int32_t dimensionRight) { | |
FX_FLOAT corr = Distance(bottomLeft, bottomRight) / (FX_FLOAT)dimensionTop; | |
int32_t norm = Distance(topLeft, topRight); | |
FX_FLOAT cos = (topRight->GetX() - topLeft->GetX()) / norm; | |
FX_FLOAT sin = (topRight->GetY() - topLeft->GetY()) / norm; | |
CBC_AutoPtr<CBC_ResultPoint> c1(new CBC_ResultPoint( | |
topRight->GetX() + corr * cos, topRight->GetY() + corr * sin)); | |
corr = Distance(bottomLeft, topLeft) / (FX_FLOAT)dimensionRight; | |
norm = Distance(bottomRight, topRight); | |
cos = (topRight->GetX() - bottomRight->GetX()) / norm; | |
sin = (topRight->GetY() - bottomRight->GetY()) / norm; | |
CBC_AutoPtr<CBC_ResultPoint> c2(new CBC_ResultPoint( | |
topRight->GetX() + corr * cos, topRight->GetY() + corr * sin)); | |
if (!IsValid(c1.get())) { | |
if (IsValid(c2.get())) { | |
return c2.release(); | |
} | |
return NULL; | |
} else if (!IsValid(c2.get())) { | |
return c1.release(); | |
} | |
int32_t l1 = FXSYS_abs(dimensionTop - | |
CBC_AutoPtr<CBC_ResultPointsAndTransitions>( | |
TransitionsBetween(topLeft, c1.get())) | |
->GetTransitions()) + | |
FXSYS_abs(dimensionRight - | |
CBC_AutoPtr<CBC_ResultPointsAndTransitions>( | |
TransitionsBetween(bottomRight, c1.get())) | |
->GetTransitions()); | |
int32_t l2 = FXSYS_abs(dimensionTop - | |
CBC_AutoPtr<CBC_ResultPointsAndTransitions>( | |
TransitionsBetween(topLeft, c2.get())) | |
->GetTransitions()) + | |
FXSYS_abs(dimensionRight - | |
CBC_AutoPtr<CBC_ResultPointsAndTransitions>( | |
TransitionsBetween(bottomRight, c2.get())) | |
->GetTransitions()); | |
if (l1 <= l2) { | |
return c1.release(); | |
} | |
return c2.release(); | |
} | |
CBC_ResultPoint* CBC_DataMatrixDetector::CorrectTopRight( | |
CBC_ResultPoint* bottomLeft, | |
CBC_ResultPoint* bottomRight, | |
CBC_ResultPoint* topLeft, | |
CBC_ResultPoint* topRight, | |
int32_t dimension) { | |
FX_FLOAT corr = Distance(bottomLeft, bottomRight) / (FX_FLOAT)dimension; | |
int32_t norm = Distance(topLeft, topRight); | |
FX_FLOAT cos = (topRight->GetX() - topLeft->GetX()) / norm; | |
FX_FLOAT sin = (topRight->GetY() - topLeft->GetY()) / norm; | |
CBC_AutoPtr<CBC_ResultPoint> c1(new CBC_ResultPoint( | |
topRight->GetX() + corr * cos, topRight->GetY() + corr * sin)); | |
corr = Distance(bottomLeft, bottomRight) / (FX_FLOAT)dimension; | |
norm = Distance(bottomRight, topRight); | |
cos = (topRight->GetX() - bottomRight->GetX()) / norm; | |
sin = (topRight->GetY() - bottomRight->GetY()) / norm; | |
CBC_AutoPtr<CBC_ResultPoint> c2(new CBC_ResultPoint( | |
topRight->GetX() + corr * cos, topRight->GetY() + corr * sin)); | |
if (!IsValid(c1.get())) { | |
if (IsValid(c2.get())) { | |
return c2.release(); | |
} | |
return NULL; | |
} else if (!IsValid(c2.get())) { | |
return c1.release(); | |
} | |
int32_t l1 = FXSYS_abs(CBC_AutoPtr<CBC_ResultPointsAndTransitions>( | |
TransitionsBetween(topLeft, c1.get())) | |
->GetTransitions() - | |
CBC_AutoPtr<CBC_ResultPointsAndTransitions>( | |
TransitionsBetween(bottomRight, c1.get())) | |
->GetTransitions()); | |
int32_t l2 = FXSYS_abs(CBC_AutoPtr<CBC_ResultPointsAndTransitions>( | |
TransitionsBetween(topLeft, c2.get())) | |
->GetTransitions() - | |
CBC_AutoPtr<CBC_ResultPointsAndTransitions>( | |
TransitionsBetween(bottomRight, c2.get())) | |
->GetTransitions()); | |
return l1 <= l2 ? c1.release() : c2.release(); | |
} | |
FX_BOOL CBC_DataMatrixDetector::IsValid(CBC_ResultPoint* p) { | |
return p->GetX() >= 0 && p->GetX() < m_image->GetWidth() && p->GetY() > 0 && | |
p->GetY() < m_image->GetHeight(); | |
} | |
int32_t CBC_DataMatrixDetector::Round(FX_FLOAT d) { | |
return (int32_t)(d + 0.5f); | |
} | |
int32_t CBC_DataMatrixDetector::Distance(CBC_ResultPoint* a, | |
CBC_ResultPoint* b) { | |
return Round( | |
(FX_FLOAT)sqrt((a->GetX() - b->GetX()) * (a->GetX() - b->GetX()) + | |
(a->GetY() - b->GetY()) * (a->GetY() - b->GetY()))); | |
} | |
void CBC_DataMatrixDetector::Increment( | |
CFX_MapPtrTemplate<CBC_ResultPoint*, int32_t>& table, | |
CBC_ResultPoint* key) { | |
int32_t value; | |
if (table.Lookup(key, value)) { | |
table.SetAt(key, INTEGERS[value + 1]); | |
} else { | |
table.SetAt(key, INTEGERS[1]); | |
} | |
} | |
CBC_CommonBitMatrix* CBC_DataMatrixDetector::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) { | |
CBC_QRGridSampler& sampler = CBC_QRGridSampler::GetInstance(); | |
CBC_CommonBitMatrix* cbm = sampler.SampleGrid( | |
image, dimensionX, dimensionY, 0.5f, 0.5f, dimensionX - 0.5f, 0.5f, | |
dimensionX - 0.5f, dimensionY - 0.5f, 0.5f, dimensionY - 0.5f, | |
topLeft->GetX(), topLeft->GetY(), topRight->GetX(), topRight->GetY(), | |
bottomRight->GetX(), bottomRight->GetY(), bottomLeft->GetX(), | |
bottomLeft->GetY(), e); | |
BC_EXCEPTION_CHECK_ReturnValue(e, NULL); | |
return cbm; | |
} | |
CBC_ResultPointsAndTransitions* CBC_DataMatrixDetector::TransitionsBetween( | |
CBC_ResultPoint* from, | |
CBC_ResultPoint* to) { | |
int32_t fromX = (int32_t)from->GetX(); | |
int32_t fromY = (int32_t)from->GetY(); | |
int32_t toX = (int32_t)to->GetX(); | |
int32_t toY = (int32_t)to->GetY(); | |
FX_BOOL steep = FXSYS_abs(toY - fromY) > FXSYS_abs(toX - fromX); | |
if (steep) { | |
int32_t temp = fromX; | |
fromX = fromY; | |
fromY = temp; | |
temp = toX; | |
toX = toY; | |
toY = temp; | |
} | |
int32_t dx = FXSYS_abs(toX - fromX); | |
int32_t dy = FXSYS_abs(toY - fromY); | |
int32_t error = -dx >> 1; | |
int32_t ystep = fromY < toY ? 1 : -1; | |
int32_t xstep = fromX < toX ? 1 : -1; | |
int32_t transitions = 0; | |
FX_BOOL inBlack = m_image->Get(steep ? fromY : fromX, steep ? fromX : fromY); | |
for (int32_t x = fromX, y = fromY; x != toX; x += xstep) { | |
FX_BOOL isBlack = m_image->Get(steep ? y : x, steep ? x : y); | |
if (isBlack != inBlack) { | |
transitions++; | |
inBlack = isBlack; | |
} | |
error += dy; | |
if (error > 0) { | |
if (y == toY) { | |
break; | |
} | |
y += ystep; | |
error -= dx; | |
} | |
} | |
return new CBC_ResultPointsAndTransitions(from, to, transitions); | |
} | |
void CBC_DataMatrixDetector::OrderBestPatterns(CFX_PtrArray* patterns) { | |
FX_FLOAT abDistance = (FX_FLOAT)Distance((CBC_ResultPoint*)(*patterns)[0], | |
(CBC_ResultPoint*)(*patterns)[1]); | |
FX_FLOAT bcDistance = (FX_FLOAT)Distance((CBC_ResultPoint*)(*patterns)[1], | |
(CBC_ResultPoint*)(*patterns)[2]); | |
FX_FLOAT acDistance = (FX_FLOAT)Distance((CBC_ResultPoint*)(*patterns)[0], | |
(CBC_ResultPoint*)(*patterns)[2]); | |
CBC_ResultPoint *topLeft, *topRight, *bottomLeft; | |
if (bcDistance >= abDistance && bcDistance >= acDistance) { | |
topLeft = (CBC_ResultPoint*)(*patterns)[0]; | |
topRight = (CBC_ResultPoint*)(*patterns)[1]; | |
bottomLeft = (CBC_ResultPoint*)(*patterns)[2]; | |
} else if (acDistance >= bcDistance && acDistance >= abDistance) { | |
topLeft = (CBC_ResultPoint*)(*patterns)[1]; | |
topRight = (CBC_ResultPoint*)(*patterns)[0]; | |
bottomLeft = (CBC_ResultPoint*)(*patterns)[2]; | |
} else { | |
topLeft = (CBC_ResultPoint*)(*patterns)[2]; | |
topRight = (CBC_ResultPoint*)(*patterns)[0]; | |
bottomLeft = (CBC_ResultPoint*)(*patterns)[1]; | |
} | |
if ((bottomLeft->GetY() - topLeft->GetY()) * | |
(topRight->GetX() - topLeft->GetX()) < | |
(bottomLeft->GetX() - topLeft->GetX()) * | |
(topRight->GetY() - topLeft->GetY())) { | |
CBC_ResultPoint* temp = topRight; | |
topRight = bottomLeft; | |
bottomLeft = temp; | |
} | |
(*patterns)[0] = bottomLeft; | |
(*patterns)[1] = topLeft; | |
(*patterns)[2] = topRight; | |
} |