Max Max - 11 days ago 7
Java Question

Show lines found with Rosetta Code Hough Transform in original image

I have been using the Rosetta Code Java implementation of Hough Transform, and it also nicely generates the visualization of the accumulator.

Given an input image like this:

enter image description here

The accumulator looks like this:

Accumulator Space

Given that I cpompile and invoke the class like this:

$ javac HoughTransform.java && java HoughTransform pentagram.png out.png 640 480 100


Which makes sense. Now I would like to overlay the original images with the lines I found, but this gives me serious trouble.

I could only find an example which does what I want written in C++:


...
int x1, y1, x2, y2;
x1 = y1 = x2 = y2 = 0;

if(t >= 45 && t <= 135)
{
//y = (r - x cos(t)) / sin(t)
x1 = 0;
y1 = ((double)(r-(_accu_h/2)) - ((x1 - (_img_w/2) ) * cos(t * DEG2RAD))) / sin(t * DEG2RAD) + (_img_h / 2);
x2 = _img_w - 0;
y2 = ((double)(r-(_accu_h/2)) - ((x2 - (_img_w/2) ) * cos(t * DEG2RAD))) / sin(t * DEG2RAD) + (_img_h / 2);
}
else
{
//x = (r - y sin(t)) / cos(t);
y1 = 0;
x1 = ((double)(r-(_accu_h/2)) - ((y1 - (_img_h/2) ) * sin(t * DEG2RAD))) / cos(t * DEG2RAD) + (_img_w / 2);
y2 = _img_h - 0;
x2 = ((double)(r-(_accu_h/2)) - ((y2 - (_img_h/2) ) * sin(t * DEG2RAD))) / cos(t * DEG2RAD) + (_img_w / 2);
}
...


From https://github.com/brunokeymolen/hough/blob/master/hough.cpp#L125


I tried adapting the code at least to see if I can get the general idea, but the implementation for the C++ version and the Rosetta code version seem kind of different.

I implemented:

public static void getLines(String filename, int thetaAxisSize, ArrayData arrayData) throws IOException
{
BufferedImage inputImage = ImageIO.read(new File(filename));

double[] sinTable = new double[thetaAxisSize];
double[] cosTable = new double[thetaAxisSize];
for (int theta = thetaAxisSize - 1; theta >= 0; theta--)
{
double thetaRadians = theta * Math.PI / thetaAxisSize;
sinTable[theta] = Math.sin(thetaRadians);
cosTable[theta] = Math.cos(thetaRadians);
}


java.awt.Color color = new java.awt.Color(255, 0, 0);

int max = arrayData.getMax();
System.out.println("Max value: " + max);

for (int r = 0; r < arrayData.height; r++)
{
for (int theta = 0; theta < arrayData.width; theta++)
{
int val = arrayData.get(theta, r);

if (val < max - 1) {
continue;
}

System.out.println("Found val: " + val + ", r: " + r + ", theta: " + theta);

int x = (int)(r * cosTable[theta]);
int y = (int)(r * sinTable[theta]);

System.out.println("Found val: " + val + ", r: " + r + ", theta: " + theta + ", x/y: " + x + "/" + y);
}
}

ImageIO.write(inputImage, "PNG", new File("/tmp/hough-overlay.png"));
}


But then got stuck, as the result is already non-sensical to me:

Max value: 217 (this one still makes sense)
Found val: 216, r: 275, theta: 342
Found val: 216, r: 275, theta: 342, x/y: -29/273
Found val: 216, r: 276, theta: 340
Found val: 216, r: 276, theta: 340, x/y: -27/274
Found val: 217, r: 277, theta: 337
Found val: 217, r: 277, theta: 337, x/y: -23/276
Found val: 217, r: 277, theta: 339
Found val: 217, r: 277, theta: 339, x/y: -25/275
Found val: 217, r: 278, theta: 336
Found val: 217, r: 278, theta: 336, x/y: -21/277
Found val: 216, r: 279, theta: 334
Found val: 216, r: 279, theta: 334, x/y: -19/278


My mathematics is not good enough to find out how I can transform
r
and
theta
back to the image space, given a line is found. I read many whitepapers and articles on Hough Transform, I still don't understand. The few implementations that I found, like the C++ version, all seem to do it a little bit different from the Java version that I have.

So I wonder, has anyone used the Rosetta Code Java implementation for Hough Transform and managed to transform the lines back from the polar space into the original image?

MBo MBo
Answer

You have parameters rho, theta of "normal" line equation and want to get two points defining the same line

 x *  Cos(Theta) + y * sin(Theta) - Rho = 0

Special cases: check whether Rho = 0 or Theta is 90*K (horizontal or vertical).

  1. Rho = 0 - line through coordinate origin. So the first point is (0,0). If Theta = 0, take (0, 1) as second point, otherwise take (1, Cotangent(Theta))

  2. If Theta = 0 or 180 (vertical) - just make vertical line X=Rho (for example, points (Rho, 0) and (Rho,1))

  3. If Theta = 90/270 (horizontal) - just make horizontal line Y=Rho (for example, points (0, Rho) and (1, Rho))

Otherwise - let's choose intersections with coordinate axes as base line points. Substitute x=0 and y=0 in equation and get coordinates:

 0 *  Cos(Theta) + y * sin(Theta) - Rho = 0
 y = Rho / Sin(Theta)

 x *  Cos(Theta) + 0 * sin(Theta) - Rho = 0      
 x = Rho / Cos(Theta)

So points are (0, Rho / Sin(Theta)) and (Rho / Cos(Theta), 0)

Quick check for Theta = 45, Rho = 0.7071: (0, 1) and (1, 0) - OK

Comments