From 8b2ac51d63b9daf021376e1203ca31bf263e26ee Mon Sep 17 00:00:00 2001 From: srowen Date: Fri, 14 Mar 2008 18:44:41 +0000 Subject: [PATCH 1/1] Move GridSampler into common package and refactor to ready it for use with Data Matrix git-svn-id: http://zxing.googlecode.com/svn/trunk@278 59b500cc-1b3d-0410-9834-0bbf25fbcc57 --- .../android/AndroidGraphicsGridSampler.java | 58 ++------ .../zxing/common/DefaultGridSampler.java | 65 +++++++++ .../com/google/zxing/common/GridSampler.java | 138 ++++++++++++++++++ .../PerspectiveTransform.java | 4 +- .../zxing/qrcode/detector/Detector.java | 48 +++++- .../common/PerspectiveTransformTestCase.java | 58 ++++++++ 6 files changed, 323 insertions(+), 48 deletions(-) create mode 100644 core/src/com/google/zxing/common/DefaultGridSampler.java create mode 100644 core/src/com/google/zxing/common/GridSampler.java rename core/src/com/google/zxing/{qrcode/detector => common}/PerspectiveTransform.java (96%) create mode 100644 core/test/src/com/google/zxing/common/PerspectiveTransformTestCase.java diff --git a/android/src/com/google/zxing/client/android/AndroidGraphicsGridSampler.java b/android/src/com/google/zxing/client/android/AndroidGraphicsGridSampler.java index d91deda1..a571c491 100755 --- a/android/src/com/google/zxing/client/android/AndroidGraphicsGridSampler.java +++ b/android/src/com/google/zxing/client/android/AndroidGraphicsGridSampler.java @@ -16,14 +16,11 @@ package com.google.zxing.client.android; +import android.graphics.Matrix; import com.google.zxing.MonochromeBitmapSource; import com.google.zxing.ReaderException; import com.google.zxing.common.BitMatrix; -import com.google.zxing.qrcode.detector.AlignmentPattern; -import com.google.zxing.qrcode.detector.FinderPattern; -import com.google.zxing.qrcode.detector.GridSampler; - -import android.graphics.Matrix; +import com.google.zxing.common.GridSampler; /** * Implementation based on Android's @@ -36,49 +33,22 @@ import android.graphics.Matrix; public final class AndroidGraphicsGridSampler extends GridSampler { @Override - protected BitMatrix sampleGrid(MonochromeBitmapSource image, - FinderPattern topLeft, - FinderPattern topRight, - FinderPattern bottomLeft, - AlignmentPattern alignmentPattern, - int dimension) throws ReaderException { - float dimMinusThree = (float) dimension - 3.5f; - float bottomRightX, bottomRightY; - float sourceBottomRightX, sourceBottomRightY; - if (alignmentPattern != null) { - bottomRightX = alignmentPattern.getX(); - bottomRightY = alignmentPattern.getY(); - sourceBottomRightX = sourceBottomRightY = dimMinusThree - 3.0f; - } else { - // Don't have an alignment pattern, just make up the bottom-right point - bottomRightX = (topRight.getX() - topLeft.getX()) + bottomLeft.getX(); - bottomRightY = (topRight.getY() - topLeft.getY()) + bottomLeft.getY(); - sourceBottomRightX = sourceBottomRightY = dimMinusThree; - } + public BitMatrix sampleGrid(MonochromeBitmapSource image, + int dimension, + float p1ToX, float p1ToY, + float p2ToX, float p2ToY, + float p3ToX, float p3ToY, + float p4ToX, float p4ToY, + float p1FromX, float p1FromY, + float p2FromX, float p2FromY, + float p3FromX, float p3FromY, + float p4FromX, float p4FromY) throws ReaderException { Matrix transformMatrix = new Matrix(); boolean succeeded = transformMatrix.setPolyToPoly( - new float[] { - topLeft.getX(), - topLeft.getY(), - topRight.getX(), - topRight.getY(), - bottomLeft.getX(), - bottomLeft.getY(), - bottomRightX, - bottomRightY - }, + new float[] { p1FromX, p1FromY, p2FromX, p2FromY, p3FromX, p3FromY, p4FromX, p4FromY }, 0, - new float[] { - 3.5f, - 3.5f, - dimMinusThree, - 3.5f, - 3.5f, - dimMinusThree, - sourceBottomRightX, - sourceBottomRightY, - }, + new float[] { p1ToX, p1ToY, p2ToX, p2ToY, p3ToX, p3ToY, p4ToX, p4ToY }, 0, 4 ); diff --git a/core/src/com/google/zxing/common/DefaultGridSampler.java b/core/src/com/google/zxing/common/DefaultGridSampler.java new file mode 100644 index 00000000..1cdaf3f9 --- /dev/null +++ b/core/src/com/google/zxing/common/DefaultGridSampler.java @@ -0,0 +1,65 @@ +/* + * 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. + */ + +package com.google.zxing.common; + +import com.google.zxing.MonochromeBitmapSource; +import com.google.zxing.ReaderException; + +/** + * @author srowen@google.com (Sean Owen) + */ +public final class DefaultGridSampler extends GridSampler { + + public BitMatrix sampleGrid(MonochromeBitmapSource image, + int dimension, + float p1ToX, float p1ToY, + float p2ToX, float p2ToY, + float p3ToX, float p3ToY, + float p4ToX, float p4ToY, + float p1FromX, float p1FromY, + float p2FromX, float p2FromY, + float p3FromX, float p3FromY, + float p4FromX, float p4FromY) throws ReaderException { + + PerspectiveTransform transform = PerspectiveTransform.quadrilateralToQuadrilateral( + p1ToX, p1ToY, p2ToX, p2ToY, p3ToX, p3ToY, p4ToX, p4ToY, + p1FromX, p1FromY, p2FromX, p2FromY, p3FromX, p3FromY, p4FromX, p4FromY); + + BitMatrix bits = new BitMatrix(dimension); + float[] points = new float[dimension << 1]; + for (int i = 0; i < dimension; i++) { + int max = points.length; + float iValue = (float) i + 0.5f; + for (int j = 0; j < max; j += 2) { + points[j] = (float) (j >> 1) + 0.5f; + points[j + 1] = iValue; + } + transform.transformPoints(points); + // Quick check to see if points transformed to something inside the image; + // sufficent to check the endpoints + checkEndpoint(image, points); + for (int j = 0; j < max; j += 2) { + if (image.isBlack((int) points[j], (int) points[j + 1])) { + // Black(-ish) pixel + bits.set(i, j >> 1); + } + } + } + return bits; + } + +} \ No newline at end of file diff --git a/core/src/com/google/zxing/common/GridSampler.java b/core/src/com/google/zxing/common/GridSampler.java new file mode 100644 index 00000000..3a203cd7 --- /dev/null +++ b/core/src/com/google/zxing/common/GridSampler.java @@ -0,0 +1,138 @@ +/* + * 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. + */ + +package com.google.zxing.common; + +import com.google.zxing.MonochromeBitmapSource; +import com.google.zxing.ReaderException; + +/** + * Implementations of this class can, given locations of finder patterns for a QR code in an + * image, sample the right points in the image to reconstruct the QR code, accounting for + * perspective distortion. It is abstracted since it is relatively expensive and should be allowed + * to take advantage of platform-specific optimized implementations, like Sun's Java Advanced + * Imaging library, but which may not be available in other environments such as J2ME, and vice + * versa. + * + * The implementation used can be controlled by calling {@link #setGridSampler(GridSampler)} + * with an instance of a class which implements this interface. + * + * @author srowen@google.com (Sean Owen) + */ +public abstract class GridSampler { + + private static GridSampler gridSampler; + + /** + * Sets the implementation of {@link GridSampler} used by the library. One global + * instance is stored, which may sound problematic. But, the implementation provided + * ought to be appropriate for the entire platform, and all uses of this library + * in the whole lifetime of the JVM. For instance, an Android activity can swap in + * an implementation that takes advantage of native platform libraries. + * + * @param newGridSampler + */ + public static void setGridSampler(GridSampler newGridSampler) { + if (newGridSampler == null) { + throw new IllegalArgumentException(); + } + gridSampler = newGridSampler; + } + + /** + * @return the current implementation of {@link GridSampler} + */ + public static GridSampler getInstance() { + if (gridSampler == null) { + gridSampler = new DefaultGridSampler(); + } + return gridSampler; + } + + /** + *

Samples an image for a square matrix of bits of the given dimension. This is used to extract the + * black/white modules of a 2D barcode like a QR Code found in an image. Because this barcode may be + * rotated or perspective-distorted, the caller supplies four points in the source image that define + * known points in the barcode, so that the image may be sampled appropriately.

+ * + *

The last eight "from" parameters are four X/Y coordinate pairs of locations of points in + * the image that define some significant points in the image to be sample. For example, + * these may be the location of finder pattern in a QR Code.

+ * + *

The first eight "to" parameters are four X/Y coordinate pairs measured in the destination + * {@link BitMatrix}, from the top left, where the known points in the image given by the "from" parameters + * map to.

+ * + *

These 16 parameters define the transformation needed to sample the image.

+ * + * @param image image to sample + * @param dimension width/height of {@link BitMatrix} to sample from iamge + * @return {@link BitMatrix} representing a grid of points sampled from the image within a region + * defined by the "from" parameters + * @throws ReaderException if image can't be sampled, for example, if the transformation defined by + * the given points is invalid or results in sampling outside the image boundaries + */ + public abstract BitMatrix sampleGrid(MonochromeBitmapSource image, + int dimension, + float p1ToX, float p1ToY, + float p2ToX, float p2ToY, + float p3ToX, float p3ToY, + float p4ToX, float p4ToY, + float p1FromX, float p1FromY, + float p2FromX, float p2FromY, + float p3FromX, float p3FromY, + float p4FromX, float p4FromY) 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.

+ * + *

This method will actually "nudge" the endpoints back onto the image if they are found to be barely + * (less than 1 pixel) off the image. This accounts for imperfect detection of finder patterns in an image + * where the QR Code runs all the way to the image border.

+ * + * @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 width = image.getWidth(); + int height = image.getHeight(); + checkOneEndpoint(points, (int) points[0], (int) points[1], width, height); + checkOneEndpoint(points, (int) points[points.length - 2], (int) points[points.length - 1], width, height); + } + + private static void checkOneEndpoint(float[] points, int x, int y, int width, int height) throws ReaderException { + if (x < -1 || x > width || y < -1 || y > height) { + throw new ReaderException("Transformed point out of bounds at " + x + ',' + y); + } + if (x == -1) { + points[0] = 0.0f; + } + if (y == -1) { + points[1] = 0.0f; + } + if (x == width) { + points[0] = width - 1; + } + if (y == height) { + points[1] = height - 1; + } + } + +} diff --git a/core/src/com/google/zxing/qrcode/detector/PerspectiveTransform.java b/core/src/com/google/zxing/common/PerspectiveTransform.java similarity index 96% rename from core/src/com/google/zxing/qrcode/detector/PerspectiveTransform.java rename to core/src/com/google/zxing/common/PerspectiveTransform.java index 9f954ceb..642fce30 100644 --- a/core/src/com/google/zxing/qrcode/detector/PerspectiveTransform.java +++ b/core/src/com/google/zxing/common/PerspectiveTransform.java @@ -14,6 +14,8 @@ * limitations under the License. */ +package com.google.zxing.common; + /** *

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 @@ -21,8 +23,6 @@ * * @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; diff --git a/core/src/com/google/zxing/qrcode/detector/Detector.java b/core/src/com/google/zxing/qrcode/detector/Detector.java index 3b5f94f1..fad8b061 100644 --- a/core/src/com/google/zxing/qrcode/detector/Detector.java +++ b/core/src/com/google/zxing/qrcode/detector/Detector.java @@ -22,6 +22,7 @@ import com.google.zxing.ReaderException; import com.google.zxing.ResultPoint; import com.google.zxing.common.BitMatrix; import com.google.zxing.common.DetectorResult; +import com.google.zxing.common.GridSampler; import com.google.zxing.qrcode.decoder.Version; /** @@ -95,8 +96,7 @@ public final class Detector { } - GridSampler sampler = GridSampler.getInstance(); - BitMatrix bits = sampler.sampleGrid(image, topLeft, topRight, bottomLeft, alignmentPattern, dimension); + BitMatrix bits = sampleGrid(image, topLeft, topRight, bottomLeft, alignmentPattern, dimension); ResultPoint[] points; if (alignmentPattern == null) { @@ -107,6 +107,50 @@ public final class Detector { return new DetectorResult(bits, points); } + private static BitMatrix sampleGrid(MonochromeBitmapSource image, + ResultPoint topLeft, + ResultPoint topRight, + ResultPoint bottomLeft, + ResultPoint alignmentPattern, + int dimension) throws ReaderException { + float dimMinusThree = (float) dimension - 3.5f; + float bottomRightX; + float bottomRightY; + float sourceBottomRightX; + float sourceBottomRightY; + if (alignmentPattern != null) { + bottomRightX = alignmentPattern.getX(); + bottomRightY = alignmentPattern.getY(); + sourceBottomRightX = sourceBottomRightY = dimMinusThree - 3.0f; + } else { + // Don't have an alignment pattern, just make up the bottom-right point + bottomRightX = (topRight.getX() - topLeft.getX()) + bottomLeft.getX(); + bottomRightY = (topRight.getY() - topLeft.getY()) + bottomLeft.getY(); + sourceBottomRightX = sourceBottomRightY = dimMinusThree; + } + + GridSampler sampler = GridSampler.getInstance(); + return sampler.sampleGrid( + image, + dimension, + 3.5f, + 3.5f, + dimMinusThree, + 3.5f, + sourceBottomRightX, + sourceBottomRightY, + 3.5f, + dimMinusThree, + topLeft.getX(), + topLeft.getY(), + topRight.getX(), + topRight.getY(), + bottomRightX, + bottomRightY, + bottomLeft.getX(), + bottomLeft.getY()); + } + /** *

Computes the dimension (number of modules on a size) of the QR Code based on the position * of the finder patterns and estimated module size.

diff --git a/core/test/src/com/google/zxing/common/PerspectiveTransformTestCase.java b/core/test/src/com/google/zxing/common/PerspectiveTransformTestCase.java new file mode 100644 index 00000000..5b5834dc --- /dev/null +++ b/core/test/src/com/google/zxing/common/PerspectiveTransformTestCase.java @@ -0,0 +1,58 @@ +/* + * 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. + */ + +package com.google.zxing.common; + +import junit.framework.TestCase; + +/** + * @author srowen@google.com (Sean Owen) + */ +public final class PerspectiveTransformTestCase extends TestCase { + + private static final float EPSILON = 0.0001f; + + public void testSquareToQuadrilateral() { + PerspectiveTransform pt = PerspectiveTransform.squareToQuadrilateral( + 2.0f, 3.0f, 10.0f, 4.0f, 16.0f, 15.0f, 4.0f, 9.0f); + assertPointEquals(2.0f, 3.0f, 0.0f, 0.0f, pt); + assertPointEquals(10.0f, 4.0f, 1.0f, 0.0f, pt); + assertPointEquals(4.0f, 9.0f, 0.0f, 1.0f, pt); + assertPointEquals(16.0f, 15.0f, 1.0f, 1.0f, pt); + assertPointEquals(6.535211f, 6.8873234f, 0.5f, 0.5f, pt); + assertPointEquals(48.0f, 42.42857f, 1.5f, 1.5f, pt); + } + + public void testQuadrilateralToQuadrilateral() { + PerspectiveTransform pt = PerspectiveTransform.quadrilateralToQuadrilateral( + 2.0f, 3.0f, 10.0f, 4.0f, 16.0f, 15.0f, 4.0f, 9.0f, + 103.0f, 110.0f, 300.0f, 120.0f, 290.0f, 270.0f, 150.0f, 280.0f); + assertPointEquals(103.0f, 110.0f, 2.0f, 3.0f, pt); + assertPointEquals(300.0f, 120.0f, 10.0f, 4.0f, pt); + assertPointEquals(290.0f, 270.0f, 16.0f, 15.0f, pt); + assertPointEquals(150.0f, 280.0f, 4.0f, 9.0f, pt); + assertPointEquals(7.1516876f, -64.60185f, 0.5f, 0.5f, pt); + assertPointEquals(328.09116f, 334.16385f, 50.0f, 50.0f, pt); + } + + private static void assertPointEquals(float expectedX, float expectedY, float sourceX, float sourceY, PerspectiveTransform pt) { + float[] points = new float[]{sourceX, sourceY}; + pt.transformPoints(points); + assertEquals(expectedX, points[0], EPSILON); + assertEquals(expectedY, points[1], EPSILON); + } + +} \ No newline at end of file -- 2.20.1