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;
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 {
- 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
}
}
- // 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
*
*/
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 =
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();
// 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?
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) {
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