我有一个2维图像充满黑色和白色像素。现在我想知道每个白色像素(距离)最近的黑色像素,以及我想知道的每个黑色像素(距离)最近的白色像素。高效计算距离图
一个天真的算法是:
for(var y = 0; y < height; y++)
{
for(var x = 0; x < width; x++)
{
var min = float.MaxValue;
var me = image[x,y];
for(var sy = 0; sy < height; sy++)
{
for(var sx = 0; sx < width; sx++)
{
var target = image[sx,sx];
if(target != me)
{
// target is the opposite color
var distance = Distance(x, y, sx, sy);
if(distance < min)
{
min = distance;
}
}
}
}
distanecImage[x,y] = min;
}
}
我认为这是二次型的复杂性。有什么方法可以加快速度吗?我有一个想法,如果你知道所有邻居的最接近的目标像素,你可以计算你自己的最近距离,而不必循环整个图像。但是我很难用这个想法来生成一个算法,或者如何调用这样的算法。
我只限于DirectX9级别的硬件,但如果需要的话,我可以使用GPU来加快速度。最大尺寸约为256x256。
4'for'循环表示双二次时间复杂度'O(n^4)' – sds
朴素方法是O(n^2)中的图像像素数。无论你将它们安排在2D,3D还是N-D中,它的数量无关紧要。 –
好的,它的像素数量是二次的,但像素的数量在图像的线性维度上是二次的。 – sds