core/src/com/google/zxing/qrcode/detector/PerspectiveTransform.java

   1 /*\r
   2  * Copyright 2007 Google Inc.\r
   3  *\r
   4  * Licensed under the Apache License, Version 2.0 (the "License");\r
   5  * you may not use this file except in compliance with the License.\r
   6  * You may obtain a copy of the License at\r
   7  *\r
   8  *      http://www.apache.org/licenses/LICENSE-2.0\r
   9  *\r
  10  * Unless required by applicable law or agreed to in writing, software\r
  11  * distributed under the License is distributed on an "AS IS" BASIS,\r
  12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.\r
  13  * See the License for the specific language governing permissions and\r
  14  * limitations under the License.\r
  15  */\r
  16 \r
  17 /**\r
  18  * <p>This class implements a perspective transform in two dimensions. Given four source and four destination\r
  19  * points, it will compute the transformation implied between them. The code is based directly upon section\r
  20  * 3.4.2 of George Wolberg's "Digital Image Warping"; see pages 54-56.</p>\r
  21  *\r
  22  * @author srowen@google.com (Sean Owen)\r
  23  */\r
  24 package com.google.zxing.qrcode.detector;\r
  25 \r
  26 final class PerspectiveTransform {\r
  27 \r
  28   private final float a11, a12, a13, a21, a22, a23, a31, a32, a33;\r
  29 \r
  30   private PerspectiveTransform(float a11, float a21, float a31,\r
  31                                float a12, float a22, float a32,\r
  32                                float a13, float a23, float a33) {\r
  33     this.a11 = a11;\r
  34     this.a12 = a12;\r
  35     this.a13 = a13;\r
  36     this.a21 = a21;\r
  37     this.a22 = a22;\r
  38     this.a23 = a23;\r
  39     this.a31 = a31;\r
  40     this.a32 = a32;\r
  41     this.a33 = a33;\r
  42   }\r
  43 \r
  44   static PerspectiveTransform quadrilateralToQuadrilateral(float x0, float y0,\r
  45                                                            float x1, float y1,\r
  46                                                            float x2, float y2,\r
  47                                                            float x3, float y3,\r
  48                                                            float x0p, float y0p,\r
  49                                                            float x1p, float y1p,\r
  50                                                            float x2p, float y2p,\r
  51                                                            float x3p, float y3p) {\r
  52 \r
  53     PerspectiveTransform qToS = quadrilateralToSquare(x0, y0, x1, y1, x2, y2, x3, y3);\r
  54     PerspectiveTransform sToQ = squareToQuadrilateral(x0p, y0p, x1p, y1p, x2p, y2p, x3p, y3p);\r
  55     PerspectiveTransform product = sToQ.times(qToS);\r
  56     return product;\r
  57   }\r
  58 \r
  59   void transformPoints(float[] points) {\r
  60     int max = points.length;\r
  61     float a11 = this.a11;\r
  62     float a12 = this.a12;\r
  63     float a13 = this.a13;\r
  64     float a21 = this.a21;\r
  65     float a22 = this.a22;\r
  66     float a23 = this.a23;\r
  67           float a31 = this.a31;\r
  68           float a32 = this.a32;\r
  69           float a33 = this.a33;\r
  70     for (int i = 0; i < max; i += 2) {\r
  71       float x = points[i];\r
  72       float y = points[i+1];\r
  73             float denominator = a13*x + a23*y + a33;\r
  74       points[i] = (a11*x + a21*y + a31) / denominator;\r
  75       points[i+1] = (a12*x + a22*y + a32) / denominator;\r
  76     }\r
  77   }\r
  78 \r
  79   static PerspectiveTransform squareToQuadrilateral(float x0, float y0,\r
  80                                                             float x1, float y1,\r
  81                                                             float x2, float y2,\r
  82                                                             float x3, float y3) {\r
  83     float dy2 = y3 - y2;\r
  84     float dy3 = y0 - y1 + y2 - y3;\r
  85     if (dy2 == 0.0f && dy3 == 0.0f) {\r
  86       return new PerspectiveTransform(x1 - x0, x2 - x1, x0,\r
  87                                       y1 - y0, y2 - y1, y0,\r
  88                                       0.0f,    0.0f,    1.0f);\r
  89     } else {\r
  90       float dx1 = x1 - x2;\r
  91       float dx2 = x3 - x2;\r
  92       float dx3 = x0 - x1 + x2 - x3;\r
  93       float dy1 = y1 - y2;\r
  94       float denominator = dx1*dy2 - dx2*dy1;\r
  95       float a13 = (dx3*dy2 - dx2*dy3) / denominator;\r
  96       float a23 = (dx1*dy3 - dx3*dy1) / denominator;\r
  97       return new PerspectiveTransform(x1 - x0 + a13*x1, x3 - x0 + a23*x3, x0,\r
  98                                       y1 - y0 + a13*y1, y3 - y0 + a23*y3, y0,\r
  99                                       a13,              a23,              1.0f);\r
 100     }\r
 101   }\r
 102 \r
 103   static PerspectiveTransform quadrilateralToSquare(float x0, float y0,\r
 104                                                             float x1, float y1,\r
 105                                                             float x2, float y2,\r
 106                                                             float x3, float y3) {\r
 107     // Here, the adjoint serves as the inverse:\r
 108     return squareToQuadrilateral(x0, y0, x1, y1, x2, y2, x3, y3).buildAdjoint();\r
 109   }\r
 110 \r
 111   PerspectiveTransform buildAdjoint() {\r
 112     // Adjoint is the transpose of the cofactor matrix:\r
 113         return new PerspectiveTransform(a22*a33 - a23*a32,\r
 114                                   a23*a31 - a21*a33,\r
 115                                   a21*a32 - a22*a31,\r
 116                                   a13*a32 - a12*a33,\r
 117                                   a11*a33 - a13*a31,\r
 118                                   a12*a31 - a11*a32,\r
 119                                   a12*a23 - a13*a22,\r
 120                                   a13*a21 - a11*a23,\r
 121                                   a11*a22 - a12*a21);\r
 122   }\r
 123 \r
 124   PerspectiveTransform times(PerspectiveTransform other) {\r
 125     return new PerspectiveTransform(a11*other.a11 + a21*other.a12 + a31*other.a13,\r
 126                                     a11*other.a21 + a21*other.a22 + a31*other.a23,\r
 127                                     a11*other.a31 + a21*other.a32 + a31*other.a33,\r
 128                                     a12*other.a11 + a22*other.a12 + a32*other.a13,\r
 129                                     a12*other.a21 + a22*other.a22 + a32*other.a23,\r
 130                                     a12*other.a31 + a22*other.a32 + a32*other.a33,\r
 131                                     a13*other.a11 + a23*other.a12 + a33*other.a13,\r
 132                                     a13*other.a21 + a23*other.a22 + a33*other.a23,\r
 133                                     a13*other.a31 + a23*other.a32 + a33*other.a33);\r
 134 \r
 135   }\r
 136 \r
 137 }\r