Improved datamatrix reader with new algorithm

git-svn-id: http://zxing.googlecode.com/svn/trunk@1574 59b500cc-1b3d-0410-9834-0bbf25fbcc57

diff --git a/core/src/com/google/zxing/common/detector/WhiteRectangleDetector.java b/core/src/com/google/zxing/common/detector/WhiteRectangleDetector.java
index 66a3219..030d3a2 100644 (file)
--- a/core/src/com/google/zxing/common/detector/WhiteRectangleDetector.java
+++ b/core/src/com/google/zxing/common/detector/WhiteRectangleDetector.java
@@ -33,7 +33,6 @@ import com.google.zxing.common.BitMatrix;
 public final class WhiteRectangleDetector {
 
   private static final int INIT_SIZE = 40;
 public final class WhiteRectangleDetector {
 
   private static final int INIT_SIZE = 40;

-  private static final int MIN_SIZE = 20;

 
   private final BitMatrix image;
   private final int height;
 
   private final BitMatrix image;
   private final int height;


@@ -134,34 +133,91 @@ public final class WhiteRectangleDetector {
 
     if (!sizeExceeded && atLeastOneBlackPointFoundOnBorder) {
 
 
     if (!sizeExceeded && atLeastOneBlackPointFoundOnBorder) {
 

-      //     t            t
-      //z                      x
-      //      x    OR    z
-      // y                    y
-
-      ResultPoint x = getBlackPoint(up, down, right - 1, false);
-      ResultPoint y = getBlackPoint(left, right, down - 1, true);
-      ResultPoint z = getBlackPoint(up, down, left + 1, false);
-      ResultPoint t = getBlackPoint(left, right, up + 1, true);
-
-      // if the rectangle if perfectly horizontal (mostly in test cases)
-      // then we end up with:
-      // zt     x
-      //
-      // y
-
-      if (distance(z, t) < MIN_SIZE) {
-        ResultPoint u = getBlackPointInverted(up, down, right - 1, false);
-        t = x;
-        x = u;
-      }
+        ResultPoint x=null, y=null, z=null, t=null;
+        
+        final int max_size = right-left;
+        
+        for (int i = 1; i < max_size; i++){
+            ResultPoint a = new ResultPoint(left, down-i);
+            ResultPoint b = new ResultPoint(left+i, down);
+            z = getBlackPointOnSegment(a, b);
+            if (z != null){
+                break;
+            }
+        }
+        
+        if (z == null){
+            throw NotFoundException.getNotFoundInstance();
+        }

 
 

-      return centerEdges(y, z, x, t);
+        //go down right
+        for (int i = 1; i < max_size; i++){
+            ResultPoint a = new ResultPoint(left, up+i);
+            ResultPoint b = new ResultPoint(left+i, up);
+            t = getBlackPointOnSegment(a, b);
+            if (t != null){
+                break;
+            }
+        }
+        
+        if (t == null){
+            throw NotFoundException.getNotFoundInstance();
+        }
+        
+        //go down left
+        for (int i = 1; i < max_size; i++){
+            ResultPoint a = new ResultPoint(right, up+i);
+            ResultPoint b = new ResultPoint(right-i, up);
+            x = getBlackPointOnSegment(a, b);
+            if (x != null){
+                break;
+            }
+        }
+        
+        if (x == null){
+            throw NotFoundException.getNotFoundInstance();
+        }
+        
+        //go up left
+        for (int i = 1; i < max_size; i++){
+            ResultPoint a = new ResultPoint(right, down-i);
+            ResultPoint b = new ResultPoint(right-i, down);
+            y = getBlackPointOnSegment(a, b);
+            if (y != null){
+                break;
+            }
+        }
+        
+        if (y == null){
+            throw NotFoundException.getNotFoundInstance();
+        }
+
+        return centerEdges(y, z, x, t);

 
     } else {
 
     } else {

-      throw NotFoundException.getNotFoundInstance();
+        throw NotFoundException.getNotFoundInstance();

     }
   }
     }
   }

+  
+
+    private ResultPoint getBlackPointOnSegment(ResultPoint a, ResultPoint b) {
+        int dist = distanceL2(a, b);
+        float xStep = (b.getX()-a.getX())/dist;
+        float yStep = (b.getY()-a.getY())/dist;
+        
+        for (int i = 0; i < dist; i++){
+            if (image.get(Math.round(a.getX()+i*xStep), Math.round(a.getY()+i*yStep))){
+                return new ResultPoint(Math.round(a.getX()+i*xStep), Math.round(a.getY()+i*yStep));
+            }
+        }
+        return null;
+    }
+
+    private static int distanceL2(ResultPoint a, ResultPoint b) {
+        return (int) Math.round(Math.sqrt((a.getX() - b.getX())
+                * (a.getX() - b.getX()) + (a.getY() - b.getY())
+                * (a.getY() - b.getY())));
+    }

 
   /**
    * recenters the points of a constant distance towards the center
 
   /**
    * recenters the points of a constant distance towards the center


@@ -203,89 +259,6 @@ public final class WhiteRectangleDetector {
     }
   }
 
     }
   }
 

-  // L1 distance (metropolitan distance)
-  private static float distance(ResultPoint a, ResultPoint b) {
-    return Math.abs(a.getX() - b.getX()) + Math.abs(a.getY() - b.getY());
-  }
-
-  /**
-   * Gets the coordinate of an extreme black point of a segment
-   *
-   * @param a          min value of the scanned coordinate
-   * @param b          max value of the scanned coordinate
-   * @param fixed      value of fixed coordinate
-   * @param horizontal set to true if scan must be horizontal, false if vertical
-   * @return {@link ResultPoint} describing the black point. If scan is horizontal,
-   *         the returned point is the first encountered if it is on the left of the image,
-   *         else the last one. If scan is vertical, the returned point is the first encountered
-   *         if it is on the top of the image, else the last one.
-   *         {@link ResultPoint} is null if not black point has been found
-   */
-  private ResultPoint getBlackPoint(int a, int b, int fixed, boolean horizontal) {
-
-    ResultPoint last = null;
-
-    if (horizontal) {
-      for (int x = a; x < b; x++) {
-        if (image.get(x, fixed)) {
-          if (x < width / 2) {
-            return new ResultPoint(x, fixed);
-          } else {
-            while (x < width && image.get(x, fixed)) {
-              x++;
-            }
-            x--;
-            last = new ResultPoint(x, fixed);
-          }
-        }
-      }
-    } else {
-      for (int y = a; y < b; y++) {
-        if (image.get(fixed, y)) {
-          if (y < height / 2) {
-            return new ResultPoint(fixed, y);
-          } else {
-            while (y < height && image.get(fixed, y)) {
-              y++;
-            }
-            y--;
-            last = new ResultPoint(fixed, y);
-          }
-        }
-      }
-    }
-
-    return last;
-  }
-
-  /**
-   * Same as getBlackPoint, but returned point is the last one found.
-   *
-   * @param a          min value of the scanned coordinate
-   * @param b          max value of the scanned coordinate
-   * @param fixed      value of fixed coordinate
-   * @param horizontal set to true if scan must be horizontal, false if vertical
-   * @return {@link ResultPoint} describing the black point.
-   */
-  private ResultPoint getBlackPointInverted(int a, int b, int fixed, boolean horizontal) {
-
-    if (horizontal) {
-      for (int x = b + 1; x >= a; x--) {
-        if (image.get(x, fixed)) {
-          return new ResultPoint(x, fixed);
-        }
-      }
-    } else {
-      for (int y = b + 1; y >= a; y--) {
-        if (image.get(fixed, y)) {
-          return new ResultPoint(fixed, y);
-        }
-      }
-    }
-
-    return null;
-  }
-

   /**
    * Determines whether a segment contains a black point
    *
   /**
    * Determines whether a segment contains a black point
    *

diff --git a/core/src/com/google/zxing/datamatrix/detector/Detector.java b/core/src/com/google/zxing/datamatrix/detector/Detector.java
index 512a35f..206e518 100644 (file)
--- a/core/src/com/google/zxing/datamatrix/detector/Detector.java
+++ b/core/src/com/google/zxing/datamatrix/detector/Detector.java
@@ -37,8 +37,6 @@ import java.util.Vector;
  */
 public final class Detector {
 
  */
 public final class Detector {
 

-  private static final int MIN_GIVEUP_THRESHOLD = 3;
-

   // Trick to avoid creating new Integer objects below -- a sort of crude copy of
   // the Integer.valueOf(int) optimization added in Java 5, not in J2ME
   private static final Integer[] INTEGERS =
   // Trick to avoid creating new Integer objects below -- a sort of crude copy of
   // the Integer.valueOf(int) optimization added in Java 5, not in J2ME
   private static final Integer[] INTEGERS =


@@ -82,12 +80,6 @@ public final class Detector {
     ResultPointsAndTransitions lSideOne = (ResultPointsAndTransitions) transitions.elementAt(0);
     ResultPointsAndTransitions lSideTwo = (ResultPointsAndTransitions) transitions.elementAt(1);
 
     ResultPointsAndTransitions lSideOne = (ResultPointsAndTransitions) transitions.elementAt(0);
     ResultPointsAndTransitions lSideTwo = (ResultPointsAndTransitions) transitions.elementAt(1);
 

-    //give up if there is no chance we'll decode something...
-    if (lSideOne.transitions > MIN_GIVEUP_THRESHOLD ||
-        lSideTwo.transitions > MIN_GIVEUP_THRESHOLD) {
-      throw NotFoundException.getNotFoundInstance();
-    }
-

     // Figure out which point is their intersection by tallying up the number of times we see the
     // endpoints in the four endpoints. One will show up twice.
     Hashtable pointCount = new Hashtable();
     // Figure out which point is their intersection by tallying up the number of times we see the
     // endpoints in the four endpoints. One will show up twice.
     Hashtable pointCount = new Hashtable();


@@ -149,7 +141,7 @@ public final class Detector {
     // The top right point is actually the corner of a module, which is one of the two black modules
     // adjacent to the white module at the top right. Tracing to that corner from either the top left
     // or bottom right should work here.
     // The top right point is actually the corner of a module, which is one of the two black modules
     // adjacent to the white module at the top right. Tracing to that corner from either the top left
     // or bottom right should work here.

-    int dimension = Math.max(transitionsBetween(topLeft, topRight).getTransitions(),
+    int dimension = Math.min(transitionsBetween(topLeft, topRight).getTransitions(),

                              transitionsBetween(bottomRight, topRight).getTransitions());
     if ((dimension & 0x01) == 1) {
       // it can't be odd, so, round... up?
                              transitionsBetween(bottomRight, topRight).getTransitions());
     if ((dimension & 0x01) == 1) {
       // it can't be odd, so, round... up?


@@ -161,7 +153,7 @@ public final class Detector {
     ResultPoint correctedTopRight = correctTopRight(bottomLeft, bottomRight, topLeft, topRight, dimension);
 
     //We redetermine the dimension using the corrected top right point
     ResultPoint correctedTopRight = correctTopRight(bottomLeft, bottomRight, topLeft, topRight, dimension);
 
     //We redetermine the dimension using the corrected top right point

-    int dimension2 = Math.min(transitionsBetween(topLeft, correctedTopRight).getTransitions(),
+    int dimension2 = Math.max(transitionsBetween(topLeft, correctedTopRight).getTransitions(),

                               transitionsBetween(bottomRight, correctedTopRight).getTransitions());
     dimension2++;
     if ((dimension2 & 0x01) == 1) {
                               transitionsBetween(bottomRight, correctedTopRight).getTransitions());
     dimension2++;
     if ((dimension2 & 0x01) == 1) {


@@ -181,48 +173,29 @@ public final class Detector {
                                       ResultPoint topLeft,
                                       ResultPoint topRight,
                                       int dimension) {
                                       ResultPoint topLeft,
                                       ResultPoint topRight,
                                       int dimension) {

-    float corr = distance(bottomLeft, bottomRight) / (float) dimension;
-    float corrx = 0.0f;
-    float corry = 0.0f;
-    int norm = distance(topLeft, topRight);
-    float cos = (topRight.getX() - topLeft.getX()) / norm;
-    float sin = -(topRight.getY() - topLeft.getY()) / norm;
-
-    if (cos > 0.0f && sin > 0.0f) {
-      if (cos > sin) {
-        corrx = corr * cos;
-        corry = -corr * sin;
-      } else {
-        corrx = -corr * sin;
-        corry = -corr * cos;
-      }
-    } else if (cos > 0.0f && sin < 0.0f) {
-      if (cos > -sin) {
-        corrx = -corr * sin;
-        corry = -corr * cos;
-      } else {
-        corrx = corr * cos;
-        corry = -corr * sin;
-      }
-    } else if (cos < 0.0f && sin < 0.0f) {
-      if (-cos > -sin) {
-        corrx = corr * cos;
-        corry = -corr * sin;
-      } else {
-        corrx = -corr * sin;
-        corry = -corr * cos;
-      }
-    } else if (cos < 0.0f && sin > 0.0f) {
-      if (-cos > sin) {
-        corrx = -corr * sin;
-        corry = -corr * cos;
-      } else {
-        corrx = corr * cos;
-        corry = -corr * sin;
-      }
-    }
-
-    return new ResultPoint(topRight.getX() + corrx, topRight.getY() + corry);
+               
+               float corr = distance(bottomLeft, bottomRight) / (float)dimension;
+               int norm = distance(topLeft, topRight);
+               float cos = (topRight.getX() - topLeft.getX()) / norm;
+               float sin = (topRight.getY() - topLeft.getY()) / norm;
+               
+               ResultPoint c1 = new ResultPoint(topRight.getX()+corr*cos, topRight.getY()+corr*sin);
+       
+               corr = distance(bottomLeft, bottomRight) / (float)dimension;
+               norm = distance(bottomRight, topRight);
+               cos = (topRight.getX() - bottomRight.getX()) / norm;
+               sin = (topRight.getY() - bottomRight.getY()) / norm;
+               
+               ResultPoint c2 = new ResultPoint(topRight.getX()+corr*cos, topRight.getY()+corr*sin);
+
+               int l1 = Math.abs(transitionsBetween(topLeft, c1).getTransitions() - transitionsBetween(bottomRight, c1).getTransitions());
+               int l2 = Math.abs(transitionsBetween(topLeft, c2).getTransitions() - transitionsBetween(bottomRight, c2).getTransitions());
+               
+               if (l1 <= l2){
+                       return c1;
+               }
+               
+               return c2;

   }
 
   // L2 distance
   }
 
   // L2 distance

diff --git a/core/test/src/com/google/zxing/datamatrix/DataMatrixBlackBox1TestCase.java b/core/test/src/com/google/zxing/datamatrix/DataMatrixBlackBox1TestCase.java
index 14cc3cb..5dc4c85 100644 (file)
--- a/core/test/src/com/google/zxing/datamatrix/DataMatrixBlackBox1TestCase.java
+++ b/core/test/src/com/google/zxing/datamatrix/DataMatrixBlackBox1TestCase.java
@@ -28,9 +28,9 @@ public final class DataMatrixBlackBox1TestCase extends AbstractBlackBoxTestCase
     // TODO use MultiFormatReader here once Data Matrix decoder is done
     super("test/data/blackbox/datamatrix-1", new DataMatrixReader(), BarcodeFormat.DATA_MATRIX);
     addTest(7, 7, 0.0f);
     // TODO use MultiFormatReader here once Data Matrix decoder is done
     super("test/data/blackbox/datamatrix-1", new DataMatrixReader(), BarcodeFormat.DATA_MATRIX);
     addTest(7, 7, 0.0f);

-    addTest(4, 4, 90.0f);
-    addTest(6, 6, 180.0f);
-    addTest(6, 6, 270.0f);
+    addTest(7, 7, 90.0f);
+    addTest(7, 7, 180.0f);
+    addTest(7, 7, 270.0f);

   }
 
 }
\ No newline at end of file
   }
 
 }
\ No newline at end of file

diff --git a/core/test/src/com/google/zxing/datamatrix/DataMatrixBlackBox2TestCase.java b/core/test/src/com/google/zxing/datamatrix/DataMatrixBlackBox2TestCase.java
index 817ada7..a08f0be 100644 (file)
--- a/core/test/src/com/google/zxing/datamatrix/DataMatrixBlackBox2TestCase.java
+++ b/core/test/src/com/google/zxing/datamatrix/DataMatrixBlackBox2TestCase.java
@@ -27,10 +27,10 @@ public final class DataMatrixBlackBox2TestCase extends AbstractBlackBoxTestCase
   public DataMatrixBlackBox2TestCase() {
     // TODO use MultiFormatReader here once Data Matrix decoder is done
     super("test/data/blackbox/datamatrix-2", new DataMatrixReader(), BarcodeFormat.DATA_MATRIX);
   public DataMatrixBlackBox2TestCase() {
     // TODO use MultiFormatReader here once Data Matrix decoder is done
     super("test/data/blackbox/datamatrix-2", new DataMatrixReader(), BarcodeFormat.DATA_MATRIX);

-    addTest(5, 5, 0.0f);
-    addTest(6, 6, 90.0f);
-    addTest(7, 7, 180.0f);
-    addTest(7, 7, 270.0f);
+    addTest(10, 10, 0.0f);
+    addTest(13, 13, 90.0f);
+    addTest(16, 16, 180.0f);
+    addTest(12, 12, 270.0f);

   }
 
 }
   }
 
 }