Improve/speed up distance function between two raster images

[tomasmahlberg]

At the moment this function is very slow and can consume several seconds per image comparison. It should be possible to optimize this function, for example by parallelizing it.

[marcusnaslund]

To improve performance, it could potentially be made less precise as well (not comparing every pixel)?

[marcusnaslund]

Any thoughts @davidpiuva ?

[davidpiuva]

For now, skipping half of the pixels should be enough.

Later, gpu comparisons can apply some erosion and dilation for a more flexible tolerance. Do the comparison and vertical pass on the gpu, read back an image of height 1 and do the horozontal pass from single row to single value on the cpu.

[marcusnaslund]

@niklasborwell - can you suggest a better approach?

[niklasborwell]

Honestly, I think we should probably write another more well defined function in parallel and start using that one instead, because a) There is no reference what this is based on (and I have no idea) and b) This comparison is pretty bad cause the result will scale with the number of pixels compared.
A less time consuming option would be to do a classic micro optimization of this loop. Replace indices with pointers and such. Would probably help a lot.

[marcusnaslund]

I can try doing it with pointers.

Related ideas/thoughts/observations:

• Each call to the [,] operator also does a function call to make sure that the given (x,y) coordinates are within the image. Should this be done inside a safe block?
• Most tests (at least in kean) are looking for distance == 0. We could implement some equals method that just does a memcmp on the two images' buffers.
• We could try adding a coverage parameter to the distance function (default all pixels, or 50%, etc.).

[davidpiuva]

I tried using a one dimensional index to get rid of the multiplication. I measured with and without the erosion feature. With erosion, the compiler made a better job at optimizing it so performance became worse. Without erosion, 140 milliseconds could be gained but the cost in lost spatial tolerance is unacceptable.

2D index, with erosion 19.15 s (Original)
1D index, with erosion 19.27 s (Slower)
2D index, no erosion 18.87 s (Useless)
1D index, no erosion 18.73 s (Not worth it)

[ghost]

It doesn't look like we're gonna replace distance anytime soon, so first step to improve the performance : #1823
I guess a direct equality test with memcmp and then parallel execution (if still needed, but only for large enough images) is what we should do next.

[marcusnaslund]

And as a I said above, many/most tests are looking for distance == 0, which could be replaced by an equality operator on images (doing a memcmp). We don't need an actual distance, we just need to know if it's zero or not.

[ghost]

I'm thinking about having an abstract Metric class and implement different comparison methods in specialized subclasses like:

Metric: abstract class {
    distance: abstract func (a, b: Image) -> Double
}

RootMeanSquareMetric: class extends Metric {
    distance: override func (a, b: Image) -> Double {
        // convert images to some preferred format and run L^2 metric with normalization
    }
}

MemcmpMetric: class extends Metric {
    distance: override func (a, b: Image) -> Double {
        // run memcmp on byte buffers
    }
}

SupremumMetric: ... // not sure if useful for us
...

This way we could keep all the distance implementations away from Raster* classes.
Then we could have an extension in Fixture, so we can write:

a: RasterMonochrome
b: RasterMonochrome
...
expect(a, distanceTo(b) in(RootMeanSquareMetric) is less than(10.0))
expect(a, distanceTo(a) in(MemcmpMetric) is equal to(0.0))
expect(a, distanceTo(b) is less than(10.0)) // rms could be the default

It solves two main issues with distance:

1. we will have a well-defined distance implementation
2. code which is used only for testing is kept in separate module

@marcusnaslund ?

[marcusnaslund]

1. we will have a well-defined distance implementation
2. code which is used only for testing is kept in separate module

Sounds like a reasonable idea to me.