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