python - 使用最小/最有效路径(Scipy distance.cdist)3D 浏览坐标？

Question

我使用 Jupyter Notebook 用 IPython 编写了代码，可以查找图像的所有黑色像素并找到它们之间的最短路径。

我想要类似的 3D 内容。使用点云，我拥有在 3D 空间中定义对象的点的坐标。我怎样才能找到它们之间最短/最逻辑的路径来绘制它们/将点连接成一行。

是否可以调整 2D 代码(删除与像素有关的任何内容，仅输入 x、y、z 坐标？)

The Goal: Input 3D coordinates, find the most logical/least messy path connecting them all, using this new path, reorder the coordinates from start --> end of the path, output these organized coordinates.

这是我当前的二维代码:

class ImageObject:
    def __init__(self, url):
        self.url = url
        response = requests.get(url)
        self.img = Image.open(BytesIO(response.content))
        self.og_size = self.img.size

    def show(self):
        imshow(np.asarray(self.img))

    def monochrome(self, scale=3, threshold=200):

        # convert image to monochrome
        image = self.img.convert('L')
        image_array = np.array(image)

        # Binarize a numpy array using threshold as cutoff
        for i in range(len(image_array)):
            for j in range(len(image_array[0])):
                if image_array[i][j] > threshold:
                    image_array[i][j] = 255
                else:
                    image_array[i][j] = 0

        image = Image.fromarray(image_array)

        # scale image down to reduce number of non-zero pixels
        img_sm = image.resize(tuple([int(v/scale) for v in image.size]),Image.ANTIALIAS)

        # convert image to black and white
        img_bw = img_sm.convert(mode='1', dither=2) 
        self.bw_img = img_bw
        self.pixels = (1 - np.asarray(img_bw).astype(int))
        self.pixels_flat = np.reshape(self.pixels, self.pixels.size)

    def show_bw(self):
        print("Dimensions: {}".format(self.bw_img.size))
        print("Num. pixels: {}".format(self.pixels.sum()))
        imshow(np.asarray(self.bw_img))

    def get_tour(self, starting_point="random", plot=True):
        # Get greedy tour through pixels

        absolute_index = np.where(self.pixels_flat > 0)[0] # positions of non-zero pixels
        relative_index = np.array(range(1, len(absolute_index)+1 ))

        # Replace each non-zero pixel in the array with its number
        # i.e., the 10th non-zero pixel will have 10 in its place
        flat_img_mod = deepcopy(self.pixels_flat)
        for rel, pix in enumerate(absolute_index):
            flat_img_mod[pix] = rel+1

        # Get coordiantes for each non-zero pixel
        img_idx = np.reshape(flat_img_mod, self.pixels.shape)
        self.coord_list = []
        for p1 in relative_index:
            p1_coords = tuple([int(c) for c in np.where(img_idx==p1)])
            self.coord_list.append(list(p1_coords))

        # Calcualte distance between each pair of coords
        dist_mat = distance.cdist(self.coord_list, self.coord_list, 'euclidean')

        # Initialize search space with nearest neighbor tour
        cities = self.coord_list
        num_cities = len(cities)
        if starting_point=="random":
            start = int(np.random.choice(range(num_cities),size=1))
        else:
            assert starting_point < num_cities
            start = starting_point
        tour = [start]
        active_city = start
        for step in range(0, num_cities):
            dist_row = deepcopy(dist_mat[active_city,:])
            for done in tour:
                dist_row[done] = np.inf
            nearest_neighbor = np.argmin(dist_row)
            if nearest_neighbor not in tour:
                tour.append(nearest_neighbor)
            active_city = nearest_neighbor

        y_tour = -np.array([cities[tour[i % num_cities]] for i in range(num_cities+1) ])[:,0]
        y_tour = y_tour - y_tour[0]#- min(y_tour)
        x_tour = np.array([cities[tour[i % num_cities]] for i in range(num_cities+1) ])[:,1]    
        x_tour = x_tour - x_tour[0]#- min(x_tour)

        # Circle tour back to beginning
        np.append(x_tour, x_tour[0])
        np.append(y_tour, y_tour[0])
        num_cities = num_cities + 1

        self.x_tour = x_tour
        self.y_tour = y_tour
        self.num_pixels = num_cities

        if plot:
            plt.plot(self.x_tour, self.y_tour)

    def get_splines(self, degree=5, plot=True):
        # Convert tours into parametric spline curves

        x_spl = UnivariateSpline(list(range(0,self.num_pixels)), self.x_tour, k=degree)
        y_spl = UnivariateSpline(list(range(0,self.num_pixels)), self.y_tour, k=degree)

        self.x_spl = x_spl
        self.y_spl = y_spl

        if plot:
            p = plt.plot(*zip(*[(x_spl(v), y_spl(v)) for v in np.linspace(0, self.num_pixels-1, 1000)]))


    def plot_parametric(self, num_points=1000):
        # num_points = number of points at which to sample the curves
        t_vals, x_vals = zip(*[
            (v, self.x_spl(v)) for v in np.linspace(0, self.num_pixels, num_points)
        ])
        x_vals = np.array(x_vals)
        y_vals = np.array([self.y_spl(v) for v in np.linspace(0, self.num_pixels, num_points)])
        t_vals = np.array(t_vals)

        plt.plot(t_vals, x_vals)
        plt.plot(t_vals, y_vals)

Answer 1

使用mathematica的FindShortestTour函数

Find the length and ordering of the shortest tour through points in the plane:

In[1]:= 
 Click for copyable input
✕
pts = {{1, 1}, {1, 2}, {1, 3}, {1, 4}, {1, 5}, {2, 1}, {2, 3}, {2, 
5}, {3, 1}, {3, 2}, {3, 4}, {3, 5}, {4, 1}, {4, 3}, {4, 5}, {5, 
1}, {5, 2}, {5, 3}, {5, 4}};
Copy to clipboard.
In[2]:= 
 Click for copyable input
✕
pts = {{1, 1}, {1, 2}, {1, 3}, {1, 4}, {1, 5}, {2, 1}, {2, 3}, {2, 
5}, {3, 1}, {3, 2}, {3, 4}, {3, 5}, {4, 1}, {4, 3}, {4, 5}, {5, 
1}, {5, 2}, {5, 3}, {5, 4}};
FindShortestTour[%]
Copy to clipboard.
Out[2]= 

Order the points according to the tour found:

In[3]:= 
 Click for copyable input
✕
pts = {{1, 1}, {1, 2}, {1, 3}, {1, 4}, {1, 5}, {2, 1}, {2, 3}, {2, 
5}, {3, 1}, {3, 2}, {3, 4}, {3, 5}, {4, 1}, {4, 3}, {4, 5}, {5, 
1}, {5, 2}, {5, 3}, {5, 4}};
FindShortestTour[%];
pts[[Last[%]]]
Copy to clipboard.
Out[3]= 

Plot the tour:

In[4]:= 
 Click for copyable input
Copy to clipboard.
Out[4]=