将 Voronoi 图单元格区域转换为像素坐标列表
Converting Voronoi Diagram Cell Areas to Lists of Pixel Coordinates
我正在使用 Voronoi 图进行图像处理 (procedurally generated stippling)。
为此，我需要创建元组（x，y 像素位置）列表（coords_within_cell）的列表（单元格）。
我已经开发了几个蛮力算法来完成这个（见下文），但它们太慢无法处理超过 ~10 个点。 scipy 空间实用程序的效率似乎提高了 1000 倍以上。因此，我想使用 scipy 来生成 Voronoi 图：
https://docs.scipy.org/doc/scipy/reference/generated/scipy.spatial.Voronoi.html
使用 scipy 生成 Voronoi 图相当简单，但遗憾的是我不知道如何将单元格区域转换为像素坐标。最好的方法是什么？
我找到了一个相关的问题，但是没有答案，被删除了：https://web.archive.org/web/20200120151304/
蛮力算法 1（太慢）
import math
import random
from PIL import Image
def distance(x1, y1, x2, y2):
return math.hypot(x2 - x1, y2 - y1)
# define the size of the x and y bounds
screen_width = 1260
screen_height = 1260
# define the number of points that should be used
number_of_points = 16
# randomly generate a list of n points within the given x and y bounds
point_x_coordinates = random.sample(range(0, screen_width), number_of_points)
point_y_coordinates = random.sample(range(0, screen_height), number_of_points)
points = list(zip(point_x_coordinates, point_y_coordinates))
# each point needs to have a corresponding list of pixels
point_pixels = []
for i in range(len(points)):
point_pixels.append([])
# for each pixel within bounds, determine which point it is closest to and add it to the corresponding list in point_pixels
for pixel_y_coordinate in range(screen_height):
for pixel_x_coordinate in range(screen_width):
distance_to_closest_point = float('inf')
closest_point_index = 1
for point_index, point in enumerate(points):
distance_to_point = distance(pixel_x_coordinate, pixel_y_coordinate, point[0], point[1])
if(distance_to_point < distance_to_closest_point):
closest_point_index = point_index
distance_to_closest_point = distance_to_point
point_pixels[closest_point_index].append((pixel_x_coordinate, pixel_y_coordinate))
# each point needs to have a corresponding centroid
point_pixels_centroid = []
for pixel_group in point_pixels:
x_sum = 0
y_sum = 0
for pixel in pixel_group:
x_sum += pixel[0]
y_sum += pixel[1]
x_average = x_sum / len(pixel_group)
y_average = y_sum / len(pixel_group)
point_pixels_centroid.append((round(x_average), round(y_average)))
# display the resulting voronoi diagram
display_voronoi = Image.new("RGB", (screen_width, screen_height), "white")
for pixel_group in point_pixels:
rgb = random.sample(range(0, 255), 3)
for pixel in pixel_group:
display_voronoi.putpixel( pixel, (rgb[0], rgb[1], rgb[2], 255) )
for centroid in point_pixels_centroid:
print(centroid)
display_voronoi.putpixel( centroid, (1, 1, 1, 255) )
display_voronoi.show()
蛮力算法 2（也太慢了）：
Based on this concept.
import math
import random
from PIL import Image
def distance(x1, y1, x2, y2):
return math.hypot(x2 - x1, y2 - y1)
# define the size of the x and y bounds
screen_width = 500
screen_height = 500
# define the number of points that should be used
number_of_points = 4
# randomly generate a list of n points within the given x and y bounds
point_x_coordinates = random.sample(range(0, screen_width), number_of_points)
point_y_coordinates = random.sample(range(0, screen_height), number_of_points)
points = list(zip(point_x_coordinates, point_y_coordinates))
# each point needs to have a corresponding list of pixels
point_pixels = []
for i in range(len(points)):
point_pixels.append([])
# for each pixel within bounds, determine which point it is closest to and add it to the corresponding list in point_pixels
# do this by continuously growing circles outwards from the points
# if circles overlap then whoever was their first claims the location
# keep track of whether pixels have been used or not
# this is done via a 2D list of booleans
is_drawn_on = []
for i in range(screen_width):
is_drawn_on.append([])
for j in range(screen_height):
is_drawn_on[i].append(False)
circles_are_growing = True
radius = 1
while(circles_are_growing):
circles_are_growing = False
for point_index, point in enumerate(points):
for i in range(point[0] - radius, point[0] + radius):
for j in range(point[1] - radius, point[1] + radius):
# print(str(i)+" vs "+str(len(is_drawn_on)))
if(i >= 0 and i < len(is_drawn_on)):
if(j >= 0 and j < len(is_drawn_on[i])):
if(not is_drawn_on[i][j] and distance(i, j, point[0], point[1]) <= radius):
point_pixels[point_index].append((i, j))
circles_are_growing = True
is_drawn_on[i][j] = True
radius += 1
# each point needs to have a corresponding centroid
point_pixels_centroid = []
for pixel_group in point_pixels:
x_sum = 0
y_sum = 0
for pixel in pixel_group:
x_sum += pixel[0]
y_sum += pixel[1]
x_average = x_sum / len(pixel_group)
y_average = y_sum / len(pixel_group)
point_pixels_centroid.append((round(x_average), round(y_average)))
# display the resulting voronoi diagram
display_voronoi = Image.new("RGB", (screen_width, screen_height), "white")
for pixel_group in point_pixels:
rgb = random.sample(range(0, 255), 3)
for pixel in pixel_group:
display_voronoi.putpixel( pixel, (rgb[0], rgb[1], rgb[2], 255) )
for centroid in point_pixels_centroid:
print(centroid)
display_voronoi.putpixel( centroid, (1, 1, 1, 255) )
display_voronoi.show()
与直接构建和查询 Voronoi 图相比，构建和查询标准搜索树更容易。下面是我对您的代码的修改，使用 scipy.spatial.KDTree 确定每个像素位置的最近点，然后是结果图像（具有 500 个 Voronoi 点的 500x500 图像）。
代码仍然有点慢，但现在可以很好地缩放 Voronoi 点数。如果您避免为每个 Voronoi 单元构建像素位置列表，而是直接在图像中设置数据，这可能会更快。
最快的解决方案可能涉及构建 Voronoi diagam 并一次遍历它并关联最近的 Voronoi 单元，在需要时查看相邻的 Voronoi 单元（因为前一个像素可以很好地猜测找到下一个像素的 Voronoi 单元）。但这将涉及编写更多的代码，像这样天真地使用 KDTree 并且可能不会产生巨大的收益：此时代码的缓慢部分正在构建所有可以清理的 per-pixel arrays/data独立起来。
import math
import random
from PIL import Image
from scipy import spatial
import numpy as np
# define the size of the x and y bounds
screen_width = 500
screen_height = 500
# define the number of points that should be used
number_of_points = 500
# randomly generate a list of n points within the given x and y bounds
point_x_coordinates = random.sample(range(0, screen_width), number_of_points)
point_y_coordinates = random.sample(range(0, screen_height), number_of_points)
points = list(zip(point_x_coordinates, point_y_coordinates))
# each point needs to have a corresponding list of pixels
point_pixels = []
for i in range(len(points)):
point_pixels.append([])
# build a search tree
tree = spatial.KDTree(points)
# build a list of pixed coordinates to query
pixel_coordinates = np.zeros((screen_height*screen_width, 2));
i = 0
for pixel_y_coordinate in range(screen_height):
for pixel_x_coordinate in range(screen_width):
pixel_coordinates[i] = np.array([pixel_x_coordinate, pixel_y_coordinate])
i = i+1
# for each pixel within bounds, determine which point it is closest to and add it to the corresponding list in point_pixels
[distances, indices] = tree.query(pixel_coordinates)
i = 0
for pixel_y_coordinate in range(screen_height):
for pixel_x_coordinate in range(screen_width):
point_pixels[indices[i]].append((pixel_x_coordinate, pixel_y_coordinate))
i = i+1
# each point needs to have a corresponding centroid
point_pixels_centroid = []
for pixel_group in point_pixels:
x_sum = 0
y_sum = 0
for pixel in pixel_group:
x_sum += pixel[0]
y_sum += pixel[1]
x_average = x_sum / max(len(pixel_group),1)
y_average = y_sum / max(len(pixel_group),1)
point_pixels_centroid.append((round(x_average), round(y_average)))
# display the resulting voronoi diagram
display_voronoi = Image.new("RGB", (screen_width, screen_height), "white")
for pixel_group in point_pixels:
rgb = random.sample(range(0, 255), 3)
for pixel in pixel_group:
display_voronoi.putpixel( pixel, (rgb[0], rgb[1], rgb[2], 255) )
for centroid in point_pixels_centroid:
#print(centroid)
display_voronoi.putpixel( centroid, (1, 1, 1, 255) )
#display_voronoi.show()
display_voronoi.save("test.png")
scipy.interpolate.griddata 正是这样做的，并且或多或少地使用与
中相同的方法
import numpy as np
from numpy.random import default_rng
from scipy.interpolate import griddata
# define the size of the x and y bounds
screen_width = 1260
screen_height = 1260
# define the number of points that should be used
number_of_points = 16
# randomly generate a list of n points within the given x and y bounds
rng = default_rng()
points = rng.random((number_of_points,2)) * [screen_width, screen_height]
grid_x, grid_y = np.mgrid[0:screen_width, 0:screen_height]
labels = griddata(points, np.arange(number_of_points), (grid_x, grid_y), method='nearest')
然后，您可以使用 np.where(labels==10) 获取属于单元格 #10 的所有像素的坐标。
或者您可以使用 scipy.ndimage 中的所有机器来测量标记区域的各种属性。比如重心。
如果要显示彩色单元格：
from matplotlib.pyplot import imsave
rgb = rng.integers(0, 255, size=(number_of_points,3))
rgb_labels = rgb[labels]
imsave('test.png', rgb_labels)
我正在使用 Voronoi 图进行图像处理 (procedurally generated stippling)。 为此，我需要创建元组（x，y 像素位置）列表（coords_within_cell）的列表（单元格）。
我已经开发了几个蛮力算法来完成这个（见下文），但它们太慢无法处理超过 ~10 个点。 scipy 空间实用程序的效率似乎提高了 1000 倍以上。因此，我想使用 scipy 来生成 Voronoi 图： https://docs.scipy.org/doc/scipy/reference/generated/scipy.spatial.Voronoi.html
使用 scipy 生成 Voronoi 图相当简单，但遗憾的是我不知道如何将单元格区域转换为像素坐标。最好的方法是什么？
我找到了一个相关的问题，但是没有答案，被删除了：https://web.archive.org/web/20200120151304/
蛮力算法 1（太慢）
import math
import random
from PIL import Image
def distance(x1, y1, x2, y2):
return math.hypot(x2 - x1, y2 - y1)
# define the size of the x and y bounds
screen_width = 1260
screen_height = 1260
# define the number of points that should be used
number_of_points = 16
# randomly generate a list of n points within the given x and y bounds
point_x_coordinates = random.sample(range(0, screen_width), number_of_points)
point_y_coordinates = random.sample(range(0, screen_height), number_of_points)
points = list(zip(point_x_coordinates, point_y_coordinates))
# each point needs to have a corresponding list of pixels
point_pixels = []
for i in range(len(points)):
point_pixels.append([])
# for each pixel within bounds, determine which point it is closest to and add it to the corresponding list in point_pixels
for pixel_y_coordinate in range(screen_height):
for pixel_x_coordinate in range(screen_width):
distance_to_closest_point = float('inf')
closest_point_index = 1
for point_index, point in enumerate(points):
distance_to_point = distance(pixel_x_coordinate, pixel_y_coordinate, point[0], point[1])
if(distance_to_point < distance_to_closest_point):
closest_point_index = point_index
distance_to_closest_point = distance_to_point
point_pixels[closest_point_index].append((pixel_x_coordinate, pixel_y_coordinate))
# each point needs to have a corresponding centroid
point_pixels_centroid = []
for pixel_group in point_pixels:
x_sum = 0
y_sum = 0
for pixel in pixel_group:
x_sum += pixel[0]
y_sum += pixel[1]
x_average = x_sum / len(pixel_group)
y_average = y_sum / len(pixel_group)
point_pixels_centroid.append((round(x_average), round(y_average)))
# display the resulting voronoi diagram
display_voronoi = Image.new("RGB", (screen_width, screen_height), "white")
for pixel_group in point_pixels:
rgb = random.sample(range(0, 255), 3)
for pixel in pixel_group:
display_voronoi.putpixel( pixel, (rgb[0], rgb[1], rgb[2], 255) )
for centroid in point_pixels_centroid:
print(centroid)
display_voronoi.putpixel( centroid, (1, 1, 1, 255) )
display_voronoi.show()
蛮力算法 2（也太慢了）： Based on this concept.
import math
import random
from PIL import Image
def distance(x1, y1, x2, y2):
return math.hypot(x2 - x1, y2 - y1)
# define the size of the x and y bounds
screen_width = 500
screen_height = 500
# define the number of points that should be used
number_of_points = 4
# randomly generate a list of n points within the given x and y bounds
point_x_coordinates = random.sample(range(0, screen_width), number_of_points)
point_y_coordinates = random.sample(range(0, screen_height), number_of_points)
points = list(zip(point_x_coordinates, point_y_coordinates))
# each point needs to have a corresponding list of pixels
point_pixels = []
for i in range(len(points)):
point_pixels.append([])
# for each pixel within bounds, determine which point it is closest to and add it to the corresponding list in point_pixels
# do this by continuously growing circles outwards from the points
# if circles overlap then whoever was their first claims the location
# keep track of whether pixels have been used or not
# this is done via a 2D list of booleans
is_drawn_on = []
for i in range(screen_width):
is_drawn_on.append([])
for j in range(screen_height):
is_drawn_on[i].append(False)
circles_are_growing = True
radius = 1
while(circles_are_growing):
circles_are_growing = False
for point_index, point in enumerate(points):
for i in range(point[0] - radius, point[0] + radius):
for j in range(point[1] - radius, point[1] + radius):
# print(str(i)+" vs "+str(len(is_drawn_on)))
if(i >= 0 and i < len(is_drawn_on)):
if(j >= 0 and j < len(is_drawn_on[i])):
if(not is_drawn_on[i][j] and distance(i, j, point[0], point[1]) <= radius):
point_pixels[point_index].append((i, j))
circles_are_growing = True
is_drawn_on[i][j] = True
radius += 1
# each point needs to have a corresponding centroid
point_pixels_centroid = []
for pixel_group in point_pixels:
x_sum = 0
y_sum = 0
for pixel in pixel_group:
x_sum += pixel[0]
y_sum += pixel[1]
x_average = x_sum / len(pixel_group)
y_average = y_sum / len(pixel_group)
point_pixels_centroid.append((round(x_average), round(y_average)))
# display the resulting voronoi diagram
display_voronoi = Image.new("RGB", (screen_width, screen_height), "white")
for pixel_group in point_pixels:
rgb = random.sample(range(0, 255), 3)
for pixel in pixel_group:
display_voronoi.putpixel( pixel, (rgb[0], rgb[1], rgb[2], 255) )
for centroid in point_pixels_centroid:
print(centroid)
display_voronoi.putpixel( centroid, (1, 1, 1, 255) )
display_voronoi.show()
与直接构建和查询 Voronoi 图相比，构建和查询标准搜索树更容易。下面是我对您的代码的修改，使用 scipy.spatial.KDTree 确定每个像素位置的最近点，然后是结果图像（具有 500 个 Voronoi 点的 500x500 图像）。
代码仍然有点慢，但现在可以很好地缩放 Voronoi 点数。如果您避免为每个 Voronoi 单元构建像素位置列表，而是直接在图像中设置数据，这可能会更快。
最快的解决方案可能涉及构建 Voronoi diagam 并一次遍历它并关联最近的 Voronoi 单元，在需要时查看相邻的 Voronoi 单元（因为前一个像素可以很好地猜测找到下一个像素的 Voronoi 单元）。但这将涉及编写更多的代码，像这样天真地使用 KDTree 并且可能不会产生巨大的收益：此时代码的缓慢部分正在构建所有可以清理的 per-pixel arrays/data独立起来。
import math
import random
from PIL import Image
from scipy import spatial
import numpy as np
# define the size of the x and y bounds
screen_width = 500
screen_height = 500
# define the number of points that should be used
number_of_points = 500
# randomly generate a list of n points within the given x and y bounds
point_x_coordinates = random.sample(range(0, screen_width), number_of_points)
point_y_coordinates = random.sample(range(0, screen_height), number_of_points)
points = list(zip(point_x_coordinates, point_y_coordinates))
# each point needs to have a corresponding list of pixels
point_pixels = []
for i in range(len(points)):
point_pixels.append([])
# build a search tree
tree = spatial.KDTree(points)
# build a list of pixed coordinates to query
pixel_coordinates = np.zeros((screen_height*screen_width, 2));
i = 0
for pixel_y_coordinate in range(screen_height):
for pixel_x_coordinate in range(screen_width):
pixel_coordinates[i] = np.array([pixel_x_coordinate, pixel_y_coordinate])
i = i+1
# for each pixel within bounds, determine which point it is closest to and add it to the corresponding list in point_pixels
[distances, indices] = tree.query(pixel_coordinates)
i = 0
for pixel_y_coordinate in range(screen_height):
for pixel_x_coordinate in range(screen_width):
point_pixels[indices[i]].append((pixel_x_coordinate, pixel_y_coordinate))
i = i+1
# each point needs to have a corresponding centroid
point_pixels_centroid = []
for pixel_group in point_pixels:
x_sum = 0
y_sum = 0
for pixel in pixel_group:
x_sum += pixel[0]
y_sum += pixel[1]
x_average = x_sum / max(len(pixel_group),1)
y_average = y_sum / max(len(pixel_group),1)
point_pixels_centroid.append((round(x_average), round(y_average)))
# display the resulting voronoi diagram
display_voronoi = Image.new("RGB", (screen_width, screen_height), "white")
for pixel_group in point_pixels:
rgb = random.sample(range(0, 255), 3)
for pixel in pixel_group:
display_voronoi.putpixel( pixel, (rgb[0], rgb[1], rgb[2], 255) )
for centroid in point_pixels_centroid:
#print(centroid)
display_voronoi.putpixel( centroid, (1, 1, 1, 255) )
#display_voronoi.show()
display_voronoi.save("test.png")
scipy.interpolate.griddata 正是这样做的，并且或多或少地使用与
import numpy as np
from numpy.random import default_rng
from scipy.interpolate import griddata
# define the size of the x and y bounds
screen_width = 1260
screen_height = 1260
# define the number of points that should be used
number_of_points = 16
# randomly generate a list of n points within the given x and y bounds
rng = default_rng()
points = rng.random((number_of_points,2)) * [screen_width, screen_height]
grid_x, grid_y = np.mgrid[0:screen_width, 0:screen_height]
labels = griddata(points, np.arange(number_of_points), (grid_x, grid_y), method='nearest')
然后，您可以使用 np.where(labels==10) 获取属于单元格 #10 的所有像素的坐标。
或者您可以使用 scipy.ndimage 中的所有机器来测量标记区域的各种属性。比如重心。
如果要显示彩色单元格：
from matplotlib.pyplot import imsave
rgb = rng.integers(0, 255, size=(number_of_points,3))
rgb_labels = rgb[labels]
imsave('test.png', rgb_labels)