From d53ae9ecbbca9d76982c98199e0e92f87449a919 Mon Sep 17 00:00:00 2001 From: srowen Date: Thu, 8 Nov 2007 03:58:13 +0000 Subject: [PATCH] Replace JAIPerspectiveTransform with PerspectiveTransform git-svn-id: http://zxing.googlecode.com/svn/trunk@21 59b500cc-1b3d-0410-9834-0bbf25fbcc57 --- .../qrcode/detector/DefaultGridSampler.java | 4 +- .../zxing/qrcode/detector/GridSampler.java | 47 +++++- .../detector/JAIPerspectiveTransform.java | 142 ------------------ .../qrcode/detector/PerspectiveTransform.java | 123 +++++++++++++++ 4 files changed, 168 insertions(+), 148 deletions(-) delete mode 100644 core/src/com/google/zxing/qrcode/detector/JAIPerspectiveTransform.java create mode 100644 core/src/com/google/zxing/qrcode/detector/PerspectiveTransform.java diff --git a/core/src/com/google/zxing/qrcode/detector/DefaultGridSampler.java b/core/src/com/google/zxing/qrcode/detector/DefaultGridSampler.java index a836cbe4..4f6bbed2 100644 --- a/core/src/com/google/zxing/qrcode/detector/DefaultGridSampler.java +++ b/core/src/com/google/zxing/qrcode/detector/DefaultGridSampler.java @@ -43,7 +43,7 @@ public final class DefaultGridSampler extends GridSampler { } float dimMinusThree = (float) dimension - 3.5f; - JAIPerspectiveTransform transform = JAIPerspectiveTransform.getQuadToQuad( + PerspectiveTransform transform = PerspectiveTransform.quadrilateralToQuadrilateral( 3.5f, 3.5f, dimMinusThree, @@ -70,7 +70,7 @@ public final class DefaultGridSampler extends GridSampler { points[j] = (float) (j >> 1) + 0.5f; points[j + 1] = iValue; } - transform.transform(points); + transform.transformPoints(points); // Quick check to see if points transformed to something inside the image; // sufficent to check the endpoints checkEndpoint(image, points); diff --git a/core/src/com/google/zxing/qrcode/detector/GridSampler.java b/core/src/com/google/zxing/qrcode/detector/GridSampler.java index b4bb4784..36f99311 100644 --- a/core/src/com/google/zxing/qrcode/detector/GridSampler.java +++ b/core/src/com/google/zxing/qrcode/detector/GridSampler.java @@ -35,12 +35,17 @@ import com.google.zxing.common.BitMatrix; */ public abstract class GridSampler { - private static final String DEFAULT_IMPL_CLASS = - "com.google.zxing.qrcode.detector.DefaultGridSampler"; + private static final String DEFAULT_IMPL_CLASS = "com.google.zxing.qrcode.detector.DefaultGridSampler"; private static String gridSamplerClassName = DEFAULT_IMPL_CLASS; private static GridSampler gridSampler; + /** + *

Sets the (fully-qualified) name of the implementation of {@link GridSampler} which will be + * returned from {@link #getInstance()}.

+ * + * @param className {@link GridSampler} implementation to instantiate + */ public static void setGridSamplerClassName(String className) { if (className == null) { throw new IllegalArgumentException(); @@ -48,12 +53,21 @@ public abstract class GridSampler { gridSamplerClassName = className; } + /** + * @return the current implementation of {@link GridSampler}, instantiating one if one does + * not already exist. The class which is instantied may be set by + * {@link #setGridSamplerClassName(String)} + */ public static GridSampler getInstance() { if (gridSampler == null) { + // We don't need to synchronize this -- don't really care if two threads initialize at once. + // The second one will win. try { Class gridSamplerClass = Class.forName(gridSamplerClassName); gridSampler = (GridSampler) gridSamplerClass.newInstance(); } catch (ClassNotFoundException cnfe) { + // The exceptions below would represent bad programming errors; + // For J2ME we're punting them out with RuntimeException throw new RuntimeException(cnfe.toString()); } catch (IllegalAccessException iae) { throw new RuntimeException(iae.toString()); @@ -64,6 +78,22 @@ public abstract class GridSampler { return gridSampler; } + /** + *

Given an image, locations of a QR Code's finder patterns and bottom-right alignment pattern, + * and the presumed dimension in modules of the QR Code, implemntations of this method extract + * the QR Code from the image by sampling the points in the image which should correspond to the + * modules of the QR Code.

+ * + * @param image image to sample + * @param topLeft top-left finder pattern location + * @param topRight top-right finder pattern location + * @param bottomLeft bottom-left finder pattern location + * @param alignmentPattern bottom-right alignment pattern location + * @param dimension dimension of QR Code + * @return {@link BitMatrix} representing QR Code's modules + * @throws ReaderException if QR Code cannot be reasonably sampled -- for example if the location + * of the finder patterns imply a transformation that would require sampling off the image + */ protected abstract BitMatrix sampleGrid(MonochromeBitmapSource image, FinderPattern topLeft, FinderPattern topRight, @@ -71,8 +101,17 @@ public abstract class GridSampler { AlignmentPattern alignmentPattern, int dimension) throws ReaderException; - protected static void checkEndpoint(MonochromeBitmapSource image, float[] points) - throws ReaderException { + /** + *

Checks a set of points that have been transformed to sample points on an image against + * the image's dimensions to see if the endpoints are even within the image. + * This method actually only checks the endpoints since the points are assumed to lie + * on a line.

+ * + * @param image image into which the points should map + * @param points actual points in x1,y1,...,xn,yn form + * @throws ReaderException if an endpoint is lies outside the image boundaries + */ + protected static void checkEndpoint(MonochromeBitmapSource image, float[] points) throws ReaderException { int x = (int) points[0]; int y = (int) points[1]; if (x < 0 || x >= image.getWidth() || y < 0 || y >= image.getHeight()) { diff --git a/core/src/com/google/zxing/qrcode/detector/JAIPerspectiveTransform.java b/core/src/com/google/zxing/qrcode/detector/JAIPerspectiveTransform.java deleted file mode 100644 index b6ee8eee..00000000 --- a/core/src/com/google/zxing/qrcode/detector/JAIPerspectiveTransform.java +++ /dev/null @@ -1,142 +0,0 @@ -package com.google.zxing.qrcode.detector; - -/** - * TODO need to reimplement this from scratch. This is derived from jai-core from Sun - * and it is not clear we can redistribute this modification. - */ -final class JAIPerspectiveTransform { - - private float m00, m01, m02, m10, m11, m12, m20, m21, m22; - - JAIPerspectiveTransform() { - m00 = m11 = m22 = 1.0f; - m01 = m02 = m10 = m12 = m20 = m21 = 0.0f; - } - - private void makeAdjoint() { - float m00p = m11 * m22 - m12 * m21; - float m01p = m12 * m20 - m10 * m22; // flipped sign - float m02p = m10 * m21 - m11 * m20; - float m10p = m02 * m21 - m01 * m22; // flipped sign - float m11p = m00 * m22 - m02 * m20; - float m12p = m01 * m20 - m00 * m21; // flipped sign - float m20p = m01 * m12 - m02 * m11; - float m21p = m02 * m10 - m00 * m12; // flipped sign - float m22p = m00 * m11 - m01 * m10; - // Transpose and copy sub-determinants - m00 = m00p; - m01 = m10p; - m02 = m20p; - m10 = m01p; - m11 = m11p; - m12 = m21p; - m20 = m02p; - m21 = m12p; - m22 = m22p; - } - - private static void getSquareToQuad(float x0, float y0, - float x1, float y1, - float x2, float y2, - float x3, float y3, - JAIPerspectiveTransform tx) { - float dx3 = x0 - x1 + x2 - x3; - float dy3 = y0 - y1 + y2 - y3; - tx.m22 = 1.0f; - if ((dx3 == 0.0f) && (dy3 == 0.0f)) { // to do: use tolerance - tx.m00 = x1 - x0; - tx.m01 = x2 - x1; - tx.m02 = x0; - tx.m10 = y1 - y0; - tx.m11 = y2 - y1; - tx.m12 = y0; - tx.m20 = 0.0f; - tx.m21 = 0.0f; - } else { - float dx1 = x1 - x2; - float dy1 = y1 - y2; - float dx2 = x3 - x2; - float dy2 = y3 - y2; - float invdet = 1.0f / (dx1 * dy2 - dx2 * dy1); - tx.m20 = (dx3 * dy2 - dx2 * dy3) * invdet; - tx.m21 = (dx1 * dy3 - dx3 * dy1) * invdet; - tx.m00 = x1 - x0 + tx.m20 * x1; - tx.m01 = x3 - x0 + tx.m21 * x3; - tx.m02 = x0; - tx.m10 = y1 - y0 + tx.m20 * y1; - tx.m11 = y3 - y0 + tx.m21 * y3; - tx.m12 = y0; - } - } - - private static JAIPerspectiveTransform getSquareToQuad(float x0, float y0, - float x1, float y1, - float x2, float y2, - float x3, float y3) { - JAIPerspectiveTransform tx = new JAIPerspectiveTransform(); - getSquareToQuad(x0, y0, x1, y1, x2, y2, x3, y3, tx); - return tx; - } - - private static JAIPerspectiveTransform getQuadToSquare(float x0, float y0, - float x1, float y1, - float x2, float y2, - float x3, float y3) { - JAIPerspectiveTransform tx = new JAIPerspectiveTransform(); - getSquareToQuad(x0, y0, x1, y1, x2, y2, x3, y3, tx); - tx.makeAdjoint(); - return tx; - } - - static JAIPerspectiveTransform getQuadToQuad(float x0, float y0, - float x1, float y1, - float x2, float y2, - float x3, float y3, - float x0p, float y0p, - float x1p, float y1p, - float x2p, float y2p, - float x3p, float y3p) { - JAIPerspectiveTransform tx1 = getQuadToSquare(x0, y0, x1, y1, x2, y2, x3, y3); - JAIPerspectiveTransform tx2 = getSquareToQuad(x0p, y0p, x1p, y1p, x2p, y2p, x3p, y3p); - tx1.concatenate(tx2); - return tx1; - } - - private void concatenate(JAIPerspectiveTransform Tx) { - float m00p = m00 * Tx.m00 + m10 * Tx.m01 + m20 * Tx.m02; - float m10p = m00 * Tx.m10 + m10 * Tx.m11 + m20 * Tx.m12; - float m20p = m00 * Tx.m20 + m10 * Tx.m21 + m20 * Tx.m22; - float m01p = m01 * Tx.m00 + m11 * Tx.m01 + m21 * Tx.m02; - float m11p = m01 * Tx.m10 + m11 * Tx.m11 + m21 * Tx.m12; - float m21p = m01 * Tx.m20 + m11 * Tx.m21 + m21 * Tx.m22; - float m02p = m02 * Tx.m00 + m12 * Tx.m01 + m22 * Tx.m02; - float m12p = m02 * Tx.m10 + m12 * Tx.m11 + m22 * Tx.m12; - float m22p = m02 * Tx.m20 + m12 * Tx.m21 + m22 * Tx.m22; - m00 = m00p; - m10 = m10p; - m20 = m20p; - m01 = m01p; - m11 = m11p; - m21 = m21p; - m02 = m02p; - m12 = m12p; - m22 = m22p; - } - - void transform(float[] points) { - int max = points.length; - for (int offset = 0; offset < max; offset += 2) { - float x = points[offset]; - float y = points[offset + 1]; - float w = m20 * x + m21 * y + m22; - if (w == 0.0f) { - points[offset] = x; - points[offset + 1] = y; - } else { - float oneOverW = 1.0f / w; - points[offset] = (m00 * x + m01 * y + m02) * oneOverW; - points[offset + 1] = (m10 * x + m11 * y + m12) * oneOverW; - } - } - } -} \ No newline at end of file diff --git a/core/src/com/google/zxing/qrcode/detector/PerspectiveTransform.java b/core/src/com/google/zxing/qrcode/detector/PerspectiveTransform.java new file mode 100644 index 00000000..c9e9820c --- /dev/null +++ b/core/src/com/google/zxing/qrcode/detector/PerspectiveTransform.java @@ -0,0 +1,123 @@ +/* + * Copyright 2007 Google Inc. + * + * 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. + */ + +/** + *

This class implements a perspective transform in two dimensions. Given four source and four destination + * points, it will compute the transformation implied between them. The code is based directly upon section + * 3.4.2 of George Wolberg's "Digital Image Warping"; see pages 54-56.

+ * + * @author srowen@google.com (Sean Owen) + */ +package com.google.zxing.qrcode.detector; + +final class PerspectiveTransform { + + private final float a11, a12, a13, a21, a22, a23, a31, a32, a33; + + private PerspectiveTransform(float a11, float a12, float a13, + float a21, float a22, float a23, + float a31, float a32, float a33) { + this.a11 = a11; + this.a12 = a12; + this.a13 = a13; + this.a21 = a21; + this.a22 = a22; + this.a23 = a23; + this.a31 = a31; + this.a32 = a32; + this.a33 = a33; + } + + static PerspectiveTransform quadrilateralToQuadrilateral(float x0, float y0, + float x1, float y1, + float x2, float y2, + float x3, float y3, + float x0p, float y0p, + float x1p, float y1p, + float x2p, float y2p, + float x3p, float y3p) { + return quadrilateralToSquare(x0, y0, x1, y1, x2, y2, x3, y3).times( + squareToQuadrilateral(x0p, y0p, x1p, y1p, x2p, y2p, x3p, y3p)); + } + + void transformPoints(float[] points) { + for (int i = 0; i < points.length; i += 2) { + float x = points[i]; + float y = points[i+1]; + points[i] = a11*x + a12*y + a13; + points[i+1] = a21*x + a22*y + a23; + } + } + + private static PerspectiveTransform squareToQuadrilateral(float x0, float y0, + float x1, float y1, + float x2, float y2, + float x3, float y3) { + float dx1 = x1 - x2; + float dx2 = x3 - x2; + float dx3 = x0 - x1 + x2 - x3; + float dy1 = y1 - y2; + float dy2 = y3 - y2; + float dy3 = y0 - y1 + y2 - y3; + float denominator = dx1*dy2 - dx2*dy1; + float a13 = (dx3*dy2 - dx2*dy3) / denominator; + float a23 = (dx1*dy3 - dx3*dy1) / denominator; + + return new PerspectiveTransform(x1 - x0 + a13*x1, + y1 - y0 + a13*y1, + a13, + x3 - x0 + a23*x3, + y3 - y0 + a23*y3, + a23, + x0, + y0, + 1.0f); + } + + private static PerspectiveTransform quadrilateralToSquare(float x0, float y0, + float x1, float y1, + float x2, float y2, + float x3, float y3) { + // Here, the adjoint serves as the inverse: + return squareToQuadrilateral(x0, y0, x1, y1, x2, y2, x3, y3).buildAdjoint(); + } + + private PerspectiveTransform buildAdjoint() { + // Adjoint is the transpose of the cofactor matrix: + return new PerspectiveTransform(a22*a33 - a23*a32, + a12*a33 - a13*a32, + a12*a23 - a13*a22, + a21*a33 - a23*a31, + a11*a33 - a13*a31, + a11*a23 - a13*a21, + a21*a32 - a22*a31, + a11*a32 - a12*a31, + a11*a22 - a12*a21); + } + + private PerspectiveTransform times(PerspectiveTransform other) { + return new PerspectiveTransform(a11*other.a11 + a12*other.a21 + a13*other.a31, + a11*other.a12 + a12*other.a22 + a13*other.a32, + a11*other.a13 + a12*other.a23 + a13*other.a33, + a21*other.a11 + a22*other.a21 + a23*other.a31, + a21*other.a12 + a22*other.a22 + a23*other.a32, + a21*other.a13 + a22*other.a23 + a23*other.a33, + a31*other.a11 + a32*other.a21 + a33*other.a31, + a31*other.a12 + a32*other.a22 + a33*other.a33, + a31*other.a13 + a32*other.a23 + a33*other.a33); + } + +} -- 2.20.1