cpp/core/src/zxing/datamatrix/detector/Detector.cpp

   1 /*
   2  *  Detector.cpp
   3  *  zxing
   4  *
   5  *  Created by Luiz Silva on 09/02/2010.
   6  *  Copyright 2010 ZXing authors All rights reserved.
   7  *
   8  * Licensed under the Apache License, Version 2.0 (the "License");
   9  * you may not use this file except in compliance with the License.
  10  * You may obtain a copy of the License at
  11  *
  12  *      http://www.apache.org/licenses/LICENSE-2.0
  13  *
  14  * Unless required by applicable law or agreed to in writing, software
  15  * distributed under the License is distributed on an "AS IS" BASIS,
  16  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  17  * See the License for the specific language governing permissions and
  18  * limitations under the License.
  19  */
  20
  21 #include <zxing/common/GridSampler.h>
  22 #include <zxing/datamatrix/detector/Detector.h>
  23 #include <cmath>
  24 #include <sstream>
  25 #include <cstdlib>
  26
  27 namespace zxing {
  28 namespace datamatrix {
  29
  30 using namespace std;
  31
  32 ResultPointsAndTransitions::ResultPointsAndTransitions() {
  33         Ref<CornerPoint> ref(new CornerPoint(0,0));
  34         from_ = ref;
  35         to_ = ref;
  36         transitions_ = 0;
  37 }
  38
  39 ResultPointsAndTransitions::ResultPointsAndTransitions(Ref<CornerPoint> from, Ref<CornerPoint> to, int transitions) {
  40         from_ = from;
  41         to_ = to;
  42         transitions_ = transitions;
  43 }
  44
  45 Ref<CornerPoint> ResultPointsAndTransitions::getFrom() {
  46       return from_;
  47 }
  48
  49 Ref<CornerPoint> ResultPointsAndTransitions::getTo() {
  50       return to_;
  51 }
  52
  53 int ResultPointsAndTransitions::getTransitions() {
  54       return transitions_;
  55 }
  56
  57 Detector::Detector(Ref<BitMatrix> image) : image_(image) { }
  58
  59 Ref<BitMatrix> Detector::getImage() {
  60    return image_;
  61 }
  62
  63 Ref<DetectorResult> Detector::detect() {
  64     Ref<MonochromeRectangleDetector> rectangleDetector_(new MonochromeRectangleDetector(image_));
  65     std::vector<Ref<CornerPoint> > cornerPoints = rectangleDetector_->detect();
  66     Ref<CornerPoint> pointA = cornerPoints[0];
  67     Ref<CornerPoint> pointB = cornerPoints[1];
  68     Ref<CornerPoint> pointC = cornerPoints[2];
  69     Ref<CornerPoint> pointD = cornerPoints[3];
  70
  71     // Point A and D are across the diagonal from one another,
  72     // as are B and C. Figure out which are the solid black lines
  73     // by counting transitions
  74         std::vector<Ref<ResultPointsAndTransitions> > transitions(4);
  75         transitions[0].reset(transitionsBetween(pointA, pointB));
  76         transitions[1].reset(transitionsBetween(pointA, pointC));
  77         transitions[2].reset(transitionsBetween(pointB, pointD));
  78         transitions[3].reset(transitionsBetween(pointC, pointD));
  79     insertionSort(transitions);
  80
  81     // Sort by number of transitions. First two will be the two solid sides; last two
  82     // will be the two alternating black/white sides
  83     Ref<ResultPointsAndTransitions> lSideOne(transitions[0]);
  84     Ref<ResultPointsAndTransitions> lSideTwo(transitions[1]);
  85
  86     // Figure out which point is their intersection by tallying up the number of times we see the
  87     // endpoints in the four endpoints. One will show up twice.
  88     Ref<CornerPoint> maybeTopLeft;
  89     Ref<CornerPoint> bottomLeft;
  90     Ref<CornerPoint> maybeBottomRight;
  91         if (lSideOne->getFrom()->equals(lSideOne->getTo())) {
  92                 bottomLeft = lSideOne->getFrom();
  93                 maybeTopLeft = lSideTwo->getFrom();
  94                 maybeBottomRight = lSideTwo->getTo();
  95         }
  96         else if (lSideOne->getFrom()->equals(lSideTwo->getFrom())) {
  97                 bottomLeft = lSideOne->getFrom();
  98                 maybeTopLeft = lSideOne->getTo();
  99                 maybeBottomRight = lSideTwo->getTo();
 100         }
 101         else if (lSideOne->getFrom()->equals(lSideTwo->getTo())) {
 102                 bottomLeft = lSideOne->getFrom();
 103                 maybeTopLeft = lSideOne->getTo();
 104                 maybeBottomRight = lSideTwo->getFrom();
 105         }
 106         else if (lSideOne->getTo()->equals(lSideTwo->getFrom())) {
 107                 bottomLeft = lSideOne->getTo();
 108                 maybeTopLeft = lSideOne->getFrom();
 109                 maybeBottomRight = lSideTwo->getTo();
 110         }
 111         else if (lSideOne->getTo()->equals(lSideTwo->getTo())) {
 112                 bottomLeft = lSideOne->getTo();
 113                 maybeTopLeft = lSideOne->getFrom();
 114                 maybeBottomRight = lSideTwo->getFrom();
 115         }
 116         else {
 117                 bottomLeft = lSideTwo->getFrom();
 118                 maybeTopLeft = lSideOne->getTo();
 119                 maybeBottomRight = lSideOne->getFrom();
 120         }
 121
 122     // Bottom left is correct but top left and bottom right might be switched
 123     std::vector<Ref<CornerPoint> > corners(3);
 124         corners[0].reset(maybeTopLeft);
 125         corners[1].reset(bottomLeft);
 126         corners[2].reset(maybeBottomRight);
 127     // Use the dot product trick to sort them out
 128     orderBestPatterns(corners);
 129
 130     // Now we know which is which:
 131     Ref<CornerPoint> bottomRight(corners[0]);
 132     bottomLeft = corners[1];
 133     Ref<CornerPoint> topLeft(corners[2]);
 134
 135     // Which point didn't we find in relation to the "L" sides? that's the top right corner
 136     Ref<CornerPoint> topRight;
 137     if (!(pointA->equals(bottomRight) || pointA->equals(bottomLeft) || pointA->equals(topLeft))) {
 138       topRight = pointA;
 139     } else if (!(pointB->equals(bottomRight) || pointB->equals(bottomLeft) || pointB->equals(topLeft))) {
 140       topRight = pointB;
 141     } else if (!(pointC->equals(bottomRight) || pointC->equals(bottomLeft) || pointC->equals(topLeft))) {
 142       topRight = pointC;
 143     } else {
 144       topRight = pointD;
 145     }
 146
 147         float topRightX = (bottomRight->getX() - bottomLeft->getX()) + topLeft->getX();
 148   float topRightY = (bottomRight->getY() - bottomLeft->getY()) + topLeft->getY();
 149         Ref<CornerPoint> topR(new CornerPoint(topRightX,topRightY));
 150
 151     // Next determine the dimension by tracing along the top or right side and counting black/white
 152     // transitions. Since we start inside a black module, we should see a number of transitions
 153     // equal to 1 less than the code dimension. Well, actually 2 less, because we are going to
 154     // end on a black module:
 155     // The top right point is actually the corner of a module, which is one of the two black modules
 156     // adjacent to the white module at the top right. Tracing to that corner from either the top left
 157     // or bottom right should work here. The number of transitions could be higher than it should be
 158     // due to noise. So we try both and take the min.
 159         int dimension = min(transitionsBetween(topLeft, topRight)->getTransitions(),
 160                              transitionsBetween(bottomRight, topRight)->getTransitions());
 161     if ((dimension & 0x01) == 1) {
 162       // it can't be odd, so, round... up?
 163       dimension++;
 164     }
 165     dimension += 2;
 166
 167         Ref<PerspectiveTransform> transform = createTransform(topLeft, topR, bottomLeft, bottomRight, dimension);
 168         Ref<BitMatrix> bits(sampleGrid(image_, dimension, transform));
 169         std::vector<Ref<ResultPoint> > points(4);
 170           points[0].reset(pointA);
 171           points[1].reset(pointB);
 172           points[2].reset(pointC);
 173           points[3].reset(pointD);
 174           Ref<DetectorResult> detectorResult(new DetectorResult(bits, points, transform));
 175     return detectorResult;
 176 }
 177
 178 Ref<ResultPointsAndTransitions> Detector::transitionsBetween(Ref<CornerPoint> from, Ref<CornerPoint> to) {
 179     // See QR Code Detector, sizeOfBlackWhiteBlackRun()
 180     int fromX = (int) from->getX();
 181     int fromY = (int) from->getY();
 182     int toX = (int) to->getX();
 183     int toY = (int) to->getY();
 184     bool steep = labs(toY - fromY) > labs(toX - fromX);
 185     if (steep) {
 186       int temp = fromX;
 187       fromX = fromY;
 188       fromY = temp;
 189       temp = toX;
 190       toX = toY;
 191       toY = temp;
 192     }
 193
 194     int dx = labs(toX - fromX);
 195     int dy = labs(toY - fromY);
 196     int error = -dx >> 1;
 197     int ystep = fromY < toY ? 1 : -1;
 198     int xstep = fromX < toX ? 1 : -1;
 199     int transitions = 0;
 200     bool inBlack = image_->get(steep ? fromY : fromX, steep ? fromX : fromY);
 201     for (int x = fromX, y = fromY; x != toX; x += xstep) {
 202       bool isBlack = image_->get(steep ? y : x, steep ? x : y);
 203       if (isBlack != inBlack) {
 204         transitions++;
 205         inBlack = isBlack;
 206       }
 207       error += dy;
 208       if (error > 0) {
 209         if (y == toY) {
 210           break;
 211         }
 212         y += ystep;
 213         error -= dx;
 214       }
 215     }
 216         Ref<ResultPointsAndTransitions> result(new ResultPointsAndTransitions(from, to, transitions));
 217     return result;
 218   }
 219
 220 Ref<PerspectiveTransform> Detector::createTransform(Ref<ResultPoint> topLeft, Ref<ResultPoint> topRight, Ref <
 221     ResultPoint > bottomLeft, Ref<ResultPoint> bottomRight, int dimension) {
 222
 223   Ref<PerspectiveTransform> transform(PerspectiveTransform::quadrilateralToQuadrilateral(
 224         0.0f,
 225         0.0f,
 226         dimension,
 227         0.0f,
 228         dimension,
 229         dimension,
 230         0.0f,
 231         dimension,
 232         topLeft->getX(),
 233         topLeft->getY(),
 234         topRight->getX(),
 235         topRight->getY(),
 236         bottomRight->getX(),
 237         bottomRight->getY(),
 238         bottomLeft->getX(),
 239         bottomLeft->getY()));
 240   return transform;
 241 }
 242
 243 Ref<BitMatrix> Detector::sampleGrid(Ref<BitMatrix> image, int dimension, Ref<PerspectiveTransform> transform) {
 244   GridSampler &sampler = GridSampler::getInstance();
 245   return sampler.sampleGrid(image, dimension, transform);
 246 }
 247
 248 void Detector::insertionSort(std::vector<Ref<ResultPointsAndTransitions> > &vector) {
 249     int max = vector.size();
 250         bool swapped = true;
 251         Ref<ResultPointsAndTransitions> value;
 252     Ref<ResultPointsAndTransitions> valueB;
 253         do {
 254                 swapped = false;
 255             for (int i = 1; i < max; i++) {
 256           value = vector[i-1];
 257                   if (compare(value, (valueB = vector[i])) > 0) {
 258                         swapped = true;
 259                         vector[i-1].reset(valueB);
 260                         vector[i].reset(value);
 261                   }
 262                 }
 263         } while (swapped);
 264 }
 265 void Detector::orderBestPatterns(std::vector<Ref<CornerPoint> > &patterns) {
 266     // Find distances between pattern centers
 267     float zeroOneDistance = distance(patterns[0]->getX(), patterns[1]->getX(),patterns[0]->getY(), patterns[1]->getY());
 268     float oneTwoDistance = distance(patterns[1]->getX(), patterns[2]->getX(),patterns[1]->getY(), patterns[2]->getY());
 269     float zeroTwoDistance = distance(patterns[0]->getX(), patterns[2]->getX(),patterns[0]->getY(), patterns[2]->getY());
 270
 271     Ref<CornerPoint> pointA, pointB, pointC;
 272     // Assume one closest to other two is B; A and C will just be guesses at first
 273     if (oneTwoDistance >= zeroOneDistance && oneTwoDistance >= zeroTwoDistance) {
 274       pointB = patterns[0];
 275       pointA = patterns[1];
 276       pointC = patterns[2];
 277     } else if (zeroTwoDistance >= oneTwoDistance && zeroTwoDistance >= zeroOneDistance) {
 278       pointB = patterns[1];
 279       pointA = patterns[0];
 280       pointC = patterns[2];
 281     } else {
 282       pointB = patterns[2];
 283       pointA = patterns[0];
 284       pointC = patterns[1];
 285     }
 286
 287     // Use cross product to figure out whether A and C are correct or flipped.
 288     // This asks whether BC x BA has a positive z component, which is the arrangement
 289     // we want for A, B, C. If it's negative, then we've got it flipped around and
 290     // should swap A and C.
 291     if (crossProductZ(pointA, pointB, pointC) < 0.0f) {
 292       Ref<CornerPoint> temp = pointA;
 293       pointA = pointC;
 294       pointC = temp;
 295     }
 296
 297     patterns[0] = pointA;
 298     patterns[1] = pointB;
 299     patterns[2] = pointC;
 300 }
 301
 302 float Detector::distance(float x1, float x2, float y1, float y2) {
 303     float xDiff = x1 - x2;
 304     float yDiff = y1 - y2;
 305     return (float) sqrt((double) (xDiff * xDiff + yDiff * yDiff));
 306   }
 307
 308 int Detector::compare(Ref<ResultPointsAndTransitions> a, Ref<ResultPointsAndTransitions> b) {
 309       return a->getTransitions() - b->getTransitions();
 310     }
 311
 312 float Detector::crossProductZ(Ref<ResultPoint> pointA, Ref<ResultPoint> pointB, Ref<ResultPoint> pointC) {
 313     float bX = pointB->getX();
 314     float bY = pointB->getY();
 315     return ((pointC->getX() - bX) * (pointA->getY() - bY)) - ((pointC->getY() - bY) * (pointA->getX() - bX));
 316   }
 317 }
 318 }