How to fix my radon transformation?

Question

I'm building a radon transformation after this article in PHP.

But my output is not of the expected result.

Input:

Expected Result:

Actual Result:

...

I'm deliberately working with RGB instead of grayscale, because I want to use this method for image fingerprinting. In the end the number of channels shouldn't matter too much, right?

---

Time for code now.

Main function:
This is the main function, doing a lot of the actual work:

function RadonTransform($filename)
{
    $i = imagecreatefromjpeg($filename);
    $size = getimagesize($filename);
    $center = new Vector2($size[0] / 2, $size[1] / 2);

    $d = min(array($size[0], $size[1]));
    $u2 = round(M_PI * ($d / 2.0));

    $r = imagecreatetruecolor($u2, $d);

    for ($z = 0; $z < $u2; $z++)
    {
        $w2 = M_PI * ($z / $u2);
        $w4 = M_PI / 2.0;
        $c1 = new Vector2(cos($w2), sin($w2)); $c1->Multiply($d / 2.0)->Add($center);
        $c2 = new Vector2(cos($w2 + M_PI), sin($w2 + M_PI)); $c2->Multiply($d / 2.0)->Add($center);
        $c3 = new Vector2(cos($w2 + $w4), sin($w2 + $w4)); $c3->Multiply($d / 2.0)->Add($center);
        $c4 = new Vector2(cos($w2 + 3 * $w4), sin($w2 + 4 * $w4)); $c4->Multiply($d / 2.0)->Add($center);
        $c = Vector2::sSubstract($c2, $c1)->Divide(2);
        $m = Vector2::sSubstract($c4, $c3);
        for ($x = 0; $x < $d; $x++)
        {
            $p1 = Vector2::sAdd($c3, Vector2::sMultiply($m, ($x / $d)))->Substract($c);
            $p2 = Vector2::sAdd($c3, Vector2::sMultiply($m, ($x / $d)))->Add($c);

            $color = imageGetLine($i, round($p1->x), round($p1->y), round($p2->x), round($p2->y));
            imagesetpixel($r, $z + 1, $x + 1, imagecolorallocate($r, array_sum($color['r']), array_sum($color['g']), array_sum($color['b'])));
        }
    }

    return $r;
}

Supplementary functions:
This is imageGetLine() to get a straight (but maybe diagonal) line of samples from the input image.

function imageGetLine($i, $sx, $sy, $tx, $ty)
{
    $r = array(
        'r' => array(),
        'g' => array(),
        'b' => array()
    );

    if (abs($tx - $sx) > abs($ty - $sy))
    {
        if ($sx > $tx)
        {
            $tmp = $sx;
            $sx = $tx;
            $tx = $tmp;
        }

        for ($x = $sx; $x < $tx; $x++)
        {
            $y = $sy + ($x - $sx) / ($tx - $sx) * ($ty - $sy);

            $color = imageGetColorAt($i, $x, $y);
            $r['r'][] = $color['r'];
            $r['g'][] = $color['g'];
            $r['b'][] = $color['b'];
        }
    }
    else
    {
        if ($sy > $ty)
        {
            $tmp = $sy;
            $sy = $ty;
            $ty = $tmp;
        }

        for ($y = $sy; $y < $ty; $y++)
        {
            $x = $sx + ($y - $sy) / ($ty - $sy) * ($tx - $sx);

            $color = imageGetColorAt($i, $x, $y);
            if ($color === false)
                continue;
            $r['r'][] = $color['r'];
            $r['g'][] = $color['g'];
            $r['b'][] = $color['b'];
        }
    }
    return $r;
}

imageGetColorAt() does nothing but retrieve the color of a pixel at a given position:

function imageGetColorAt($i, $x, $y)
{
    // @todo nearest resampling instead of rounding
    $color = @imagecolorat($i, round($x), round($y));
    if ($color === false)
        return false;
    return array(
        'r' => ($color >> 16) & 0xFF,
        'g' => ($color >> 8) & 0xFF,
        'b' => $color & 0xFF
    );
}

The Vector2 class can be viewed here: https://github.com/cobrafast/prophp/blob/master/Math/vector2.class.php

---

One of the problems I'm facing is, that within imageGetColorAt() I'm getting some out of bounds (because apparently GD counts from 0 to n-1) errors which I just muted with @ and let it return false to skip, as I have no idea how to fix all the fancy mathematics that lead up to the coordinates given to imageGetLine().
Could that be the cause of my massive trouble?

Where have I gone wrong in my endeavours? Do I have missed something?

---

Edit 2013-11-05

After fiddling around with it by myself for a while, I am now this close:

What I added was clipping my color values to {0..255} and dividing the line samples sum by the amount of samples (so I would get the average of a line):

...
for ($x = 0; $x < $d; $x++)
{
    $p1 = Vector2::sAdd($c3, Vector2::sMultiply($m, ($x / $d)))->Substract($c);
    $p2 = Vector2::sAdd($c3, Vector2::sMultiply($m, ($x / $d)))->Add($c);

    $color = imageGetLine($i, round($p1->x), round($p1->y), round($p2->x), round($p2->y));
    $color = normalizeColor(array(
        'r' => array_sum($color['r']) / count($color['r']),
        'g' => array_sum($color['g']) / count($color['g']),
        'b' => array_sum($color['b']) / count($color['b'])
    ));
    imagesetpixel($r, $z + 1, $x + 1, imagecolorallocate($r, $color['r'], $color['g'], $color['b']));
}
...

As said normalizeColor does nothing but:

return array(
    'r' => min(array(255, max(array(0, $color['r'])))),
    'g' => min(array(255, max(array(0, $color['g'])))),
    'b' => min(array(255, max(array(0, $color['b']))))
);

But obviously, there still seems to be something wrong...

Terrance

Please post a real working code including imageGetColorAt() function. I can't get your "Actual results". – Tack

@Tack Alright, I've added more code info. – Terrance

@Cobra_Fast:What's the idea to use it for fingerprint? Can you explain please? – Eyecatching

@Phpdna The idea is to simplify the result and use it as an image fingerprint to identify similar images. There are other articles and resources that present this as a viable and robust technique for this task. So I just wanted to give it a try. – Terrance

@Cobra_Fast:I see. There is much simpler algorithm like phash. – Eyecatching

Answer 1

for ($z = 3*$u2/4; $z < $u2*7/4; $z++) {
  ...
  $c4 = ... sin($w2 + 3 * $w4) ... // it was sin($w2 + 4 * $w4)
  ...
  for ($x = 0; $x < $d; $x++) {
    imagesetpixel($r, $z - 3*$u2/4, $x, ...);
  }
}

Tack

Thank you. This works so far. But would you care to explain a little? Also, your result is mirrored upside down and shifted to the left when comparing it to the expected outcome from the original article. – Terrance

In the cartesian coordinate system Y-axis directed upwards, in computer graphics it is directed downwards. You can fix it with imagesetpixel($r, $z - 3*$u2/4, $d - $x, ...); to inverse by Y-axis. According to the article X-axis = 0 to an angle of Pi, but it's not in this implementation ( = PI*3/4 ... PI*7/4), and i'm not sure why. – Tack

Well yes, your change 3*$u2/4 .. $u2*7/4 is what I don't understand. Where is that coming from? – Terrance

Also it shifted right by 1/4 as i can see... So you need to inverse first 1/4 part by y-axis and append it right. – Tack

I just noticed it when tried $r = imagecreatetruecolor($u2*2, $d); for ($z = 0; $z < $u2*2; $z++) ... – Tack