/*

* Copyright 2020 Axel Waggershauser

*/

// SPDX-License-Identifier: Apache-2.0

#include "ConcentricFinder.h"

#include "LogMatrix.h"

#include "RegressionLine.h"

#include "ZXAlgorithms.h"

namespace ZXing {

std::optional<PointF> AverageEdgePixels(BitMatrixCursorI cur, int range, int numOfEdges)

{

PointF sum = {};

for (int i = 0; i < numOfEdges; ++i) {

if (!cur.isIn())

return {};

cur.stepToEdge(1, range);

sum += centered(cur.p) + centered(cur.p + cur.back());

log(cur.p + cur.back(), 2);

}

return sum / (2 * numOfEdges);

}

std::optional<PointF> CenterOfDoubleCross(const BitMatrix& image, PointI center, int range, int numOfEdges)

{

PointF sum = {};

for (auto d : {PointI{0, 1}, {1, 0}, {1, 1}, {1, -1}}) {

auto avr1 = AverageEdgePixels({image, center, d}, range, numOfEdges);

auto avr2 = AverageEdgePixels({image, center, -d}, range, numOfEdges);

if (!avr1 || !avr2)

return {};

sum += *avr1 + *avr2;

}

return sum / 8;

}

std::optional<PointF> CenterOfRing(const BitMatrix& image, PointI center, int range, int nth, bool requireCircle)

{

#if 0

if (requireCircle) {

// alternative implementation with the aim of discarding closed loops that are not all circle like (M > 5*m)

auto points = CollectRingPoints(image, center, range, std::abs(nth), nth < 0);

if (points.empty())

return {};

auto res = Reduce(points, PointF{}, std::plus{}) / Size(points);

double m = range, M = 0;

for (auto p : points)

UpdateMinMax(m, M, maxAbsComponent(p - res));

if (M > 5 * m)

return {};

return res;

}

#endif

// range is the approximate width/height of the nth ring, if nth>1 then it would be plausible to limit the search radius

// to approximately range / 2 * sqrt(2) == range * 0.75 but it turned out to be too limiting with realworld/noisy data.

int radius = range;

bool inner = nth < 0;

nth = std::abs(nth);

log(center, 3);

BitMatrixCursorI cur(image, center, {0, 1});

if (!cur.stepToEdge(nth, radius, inner))

return {};

cur.turnRight(); // move clock wise and keep edge on the right/left depending on backup

const auto edgeDir = inner ? Direction::LEFT : Direction::RIGHT;

uint32_t neighbourMask = 0;

auto start = cur.p;

PointF sum = {};

int n = 0;

do {

log(cur.p, 4);

sum += centered(cur.p);

++n;

// find out if we come full circle around the center. 8 bits have to be set in the end.

neighbourMask |= (1 << (4 + dot(bresenhamDirection(cur.p - center), PointI(1, 3))));

if (!cur.stepAlongEdge(edgeDir))

return {};

// use L-inf norm, simply because it is a lot faster than L2-norm and sufficiently accurate

if (maxAbsComponent(cur.p - center) > radius || center == cur.p || n > 4 * 2 * range)

return {};

} while (cur.p != start);

if (requireCircle && neighbourMask != 0b111101111)

return {};

return sum / n;

}

std::optional<PointF> CenterOfRings(const BitMatrix& image, PointF center, int range, int numOfRings)

{

int n = 1;

PointF sum = center;

for (int i = 2; i < numOfRings + 1; ++i) {

auto c = CenterOfRing(image, PointI(center), range, i);

if (!c) {

if (n == 1)

return {};

else

return sum / n;

} else if (distance(*c, center) > range / numOfRings / 2) {

return {};

}

sum += *c;

n++;

}

return sum / n;

}

static std::vector<PointF> CollectRingPoints(const BitMatrix& image, PointF center, int range, int edgeIndex, bool backup)

{

PointI centerI(center);

int radius = range;

BitMatrixCursorI cur(image, centerI, {0, 1});

if (!cur.stepToEdge(edgeIndex, radius, backup))

return {};

cur.turnRight(); // move clock wise and keep edge on the right/left depending on backup

const auto edgeDir = backup ? Direction::LEFT : Direction::RIGHT;

uint32_t neighbourMask = 0;

auto start = cur.p;

std::vector<PointF> points;

points.reserve(4 * range);

do {

log(cur.p, 4);

points.push_back(centered(cur.p));

// find out if we come full circle around the center. 8 bits have to be set in the end.

neighbourMask |= (1 << (4 + dot(bresenhamDirection(cur.p - centerI), PointI(1, 3))));

if (!cur.stepAlongEdge(edgeDir))

return {};

// use L-inf norm, simply because it is a lot faster than L2-norm and sufficiently accurate

if (maxAbsComponent(cur.p - centerI) > radius || centerI == cur.p || Size(points) > 4 * 2 * range)

return {};

} while (cur.p != start);

if (neighbourMask != 0b111101111)

return {};

return points;

}

static std::optional<QuadrilateralF> FitQadrilateralToPoints(PointF center, std::vector<PointF>& points)

{

auto dist2Center = [c = center](auto a, auto b) { return distance(a, c) < distance(b, c); };

auto [minDistElem, maxDistElem] = std::minmax_element(points.begin(), points.end(), dist2Center);

// check if points are on a circle: for a square the min/max ratio is 0.7, for a circle it is 1

if (distance(center, *minDistElem) / distance(center, *maxDistElem) > 0.85)

return {};

// rotate points such that the first one is the furthest away from the center (hence, a corner)

std::rotate(points.begin(), maxDistElem, points.end());

std::array<const PointF*, 4> corners;

corners[0] = &points[0];

// find the oposite corner by looking for the farthest point near the oposite point

corners[2] = std::max_element(&points[Size(points) * 3 / 8], &points[Size(points) * 5 / 8], dist2Center);

// find the two in between corners by looking for the points farthest from the long diagonal

auto dist2Diagonal = [l = RegressionLine(*corners[0], *corners[2])](auto a, auto b) { return l.distance(a) < l.distance(b); };

corners[1] = std::max_element(&points[Size(points) * 1 / 8], &points[Size(points) * 3 / 8], dist2Diagonal);

corners[3] = std::max_element(&points[Size(points) * 5 / 8], &points[Size(points) * 7 / 8], dist2Diagonal);

std::array lines{RegressionLine{corners[0] + 1, corners[1]}, RegressionLine{corners[1] + 1, corners[2]},

RegressionLine{corners[2] + 1, corners[3]}, RegressionLine{corners[3] + 1, &points.back() + 1}};

if (std::any_of(lines.begin(), lines.end(), [](auto line) { return !line.isValid(); }))

return {};

std::array<const PointF*, 4> beg = {corners[0] + 1, corners[1] + 1, corners[2] + 1, corners[3] + 1};

std::array<const PointF*, 4> end = {corners[1], corners[2], corners[3], &points.back() + 1};

// check if all points belonging to each line segment are sufficiently close to that line

for (int i = 0; i < 4; ++i)

for (const PointF* p = beg[i]; p != end[i]; ++p) {

auto len = std::distance(beg[i], end[i]);

if (len > 3 && lines[i].distance(*p) > std::max(1., std::min(8., len / 8.))) {

#ifdef PRINT_DEBUG

printf("%d: %.2f > %.2f @ %.fx%.f\n", i, lines[i].distance(*p), std::distance(beg[i], end[i]) / 1., p->x, p->y);

#endif

return {};

}

}

QuadrilateralF res;

for (int i = 0; i < 4; ++i)

res[i] = intersect(lines[i], lines[(i + 1) % 4]);

return res;

}

static bool QuadrilateralIsPlausibleSquare(const QuadrilateralF q, int lineIndex)

{

double m, M;

m = M = distance(q[0], q[3]);

for (int i = 1; i < 4; ++i)

UpdateMinMax(m, M, distance(q[i - 1], q[i]));

return m >= lineIndex * 2 && m > M / 3;

}

std::optional<QuadrilateralF> FitSquareToPoints(const BitMatrix& image, PointF center, int range, int lineIndex, bool backup)

{

auto points = CollectRingPoints(image, center, range, lineIndex, backup);

if (points.empty())

return {};

auto res = FitQadrilateralToPoints(center, points);

if (!res || !QuadrilateralIsPlausibleSquare(*res, lineIndex - backup))

return {};

return res;

}

std::optional<QuadrilateralF> FindConcentricPatternCorners(const BitMatrix& image, PointF center, int range, int lineIndex)

{

auto innerCorners = FitSquareToPoints(image, center, range, lineIndex, false);

if (!innerCorners)

return {};

auto outerCorners = FitSquareToPoints(image, center, range, lineIndex + 1, true);

if (!outerCorners)

return {};

auto res = Blend(*innerCorners, *outerCorners);

for (auto p : *innerCorners)

log(p, 3);

for (auto p : *outerCorners)

log(p, 3);

for (auto p : res)

log(p, 3);

return res;

}

std::optional<PointF> FinetuneConcentricPatternCenter(const BitMatrix& image, PointF center, int range, int finderPatternSize)

{

// make sure we have at least one path of white around the center

if (auto res1 = CenterOfRing(image, PointI(center), range, 1); res1 && image.get(*res1)) {

// and then either at least one more ring around that

if (auto res2 = CenterOfRings(image, *res1, range, finderPatternSize / 2); res2 && image.get(*res2))

return res2;

// or the center can be approximated by a square

if (FitSquareToPoints(image, *res1, range, 1, false))

return res1;

// TODO: this is currently only keeping #258 alive, evaluate if still worth it

if (auto res2 = CenterOfDoubleCross(image, PointI(*res1), range, finderPatternSize / 2 + 1); res2 && image.get(*res2))

return res2;

}

return {};

}

} // ZXing