高效的热图插值方法

Question

我正在写一个程序，用来创建温度的可视化图像。数据有200个点，分布在一个网格上，我使用插值的方法来填充这些点之间的像素。

我写了一个程序，利用反距离加权（在这里是修改过的Shepard方法）来输出我想要的数据，生成的图像如下所示：

为了简化内容（比如去掉图像库的部分），下面是创建这个图像的代码：

首先，计算每个点到每个管道的距离和总距离（因为这些是固定不变的）。在这部分，我不太担心耗时，因为这只需要做一次，但我还是把代码放上来，让你看看这些值是怎么存储的。

#set_tubes creates an array of tubes (which is the data I'm working on)
#each tube has an x position in pixels, a y position in pixels and a temperature

self.set_tubes()
self.dists = []
for x in range(1,BASE_WIDTH-1):
    self.summed_dists.append([])
    self.dists.append([])
    for y in range(1,BASE_HEIGHT-1):
        self.summed_dists[x-1].append([])
        self.dists[x-1].append([])
        self.summed_dists[x-1][y-1]=0
        for row in range(10):
            self.dists[x-1][y-1].append([])
            for tube in range(20):
                dist = np.sqrt((x-self.tubes[row][tube].xPos)**2+(y-self.tubes[row][tube].yPos)**2)+0.1
                #The -3 in the next two lines is simply a weighting factor
                self.dists[x-1][y-1][row].append(dist**(-3))
                self.summed_dists[x-1][y-1] = self.summed_dists[x-1][y-1] + dist**(-3)

然后进行插值（这个过程会随着温度的变化而重复进行）。这部分的耗时就比较重要了。

def other_proc_calc_temp(ret_queue, dists, tubes,summed_dists):
    heat_values = list()
    for x in range (BASE_WIDTH):
        heat_values.append([])
        for y in range(BASE_HEIGHT):
            summed = 0
            for row in range(10):
                for tube in range(20):
                    dist = dists[x][y][row][tube]
                    temp = tubes[row][tube].temp
                    summed = summed + temp* dist/summed_dists[x-1][y-1]
            heat_values[x].append(summed)

我遇到的问题是速度，对于一个200*200像素的图像，我的电脑在运行代码的第二部分时大约需要30秒。有没有更快的方法来达到相同或类似的效果，或者我的代码中有没有明显的低效之处？

我尝试过双线性和双三次插值，但对生成的图像不太满意。

我还限制了影响单个像素的数据点的邻域，以期加快速度，这确实有帮助，但我觉得我已经把这个限制到极限了，否则图像中会出现明显的线条。

感谢你能提供的任何帮助。

Answer 1

这里有一个可能会让代码更好的改进：

试着把 dists[x][y] 和 tubes[row] 移到最里面的循环外面。这样做可能会减少每次循环中查找数组索引的次数（这要看Python解释器的聪明程度）：

def other_proc_calc_temp(ret_queue, dists, tubes,summed_dists):
    heat_values = list()
    for x in range (BASE_WIDTH):
        heat_values.append([])
        for y in range(BASE_HEIGHT):
            outer_dist = dists[x][y]
            summed = 0
            for row in range(10):
                inner_dist = outer_dist[row]
                inner_tube = tubes[row]
                for tube in range(20):
                    dist = inner_dist[tube]
                    temp = inner_tubes[tube].temp
                    summed = summed + temp* dist/summed_dists[x-1][y-1]
            heat_values[x].append(summed)

如果Python解释器足够聪明，知道这些值没有改变，那么这样做只是让代码看起来更复杂。但如果Python解释器每次都重新计算这些数组索引，那就会浪费很多时间。

我之前在这里写了一段关于提前设置数组大小，而不是用 .append() 来动态增加数组的内容。gnibbler 说 .append() 是一个 O(1) 的摊销操作，这意味着在这里可能没有太多优化的空间。如果你感兴趣，可以查看编辑历史，看看我之前写了什么。