美团面试—手撕numpy之fps点云最远点采样实现_python 最远点采样-程序员宅基地

技术标签： 算法  python  leetcode  八股  

FPS

没有想到不按套路出牌的美团今早就撕了这个。

点云最远点采样，从一堆点集中选出一些点，使得他们尽可能地远离。这样采样出来的点能比较好的表征整个轮廓。在pointnet++中就用到过。

整体思路是：分别维护一个已选取和待选取的点云集合。先从点云集合中选出一个点，然后计算其余所有点到该点的距离，距离最大的那个点是下次要加入的点。当pick集合中有多个点时，距离的定义为到集合每个点距离中的最小距离。
关于距离的计算：维护一个distance列表，对于每次pick出来的点，去更新distance。可以利用前缀性质，不需要重新计算点到集合中所有点的距离了，而是选取原值和到新point的距离中的较小值，即dis = min(dis, newdis)。
关于第一个点的选取：一般用离点云重心最远的点作为初始点

import numpy as np
import matplotlib.pyplot as plt

# def compute_dis(points):
#     ## points: N*3
#     ## return -- distances: N*N
#     points_dis = np.sum(np.power(points, 2), axis=1) # N
#     distances = np.expand_dims(points_dis, axis=1).repeat(points.shape[0], axis=1) # N*N
#     distances = distances + distances.T + 2 * np.dot(points, points.T)
#     return distances

def plot(points, sample_points):
    ax = plt.axes(projection='3d')
    ax.scatter3D(points[:,0], points[:,1], points[:,2])
    ax.scatter3D(sample_points[:,0], sample_points[:,1], sample_points[:,2], c='r', s=60, marker = '^')
    plt.show()
    

def fps(points, k):
    sample_points = np.zeros((k, 3))
    
    ## 用离重心最远的初始化
    barycenter = np.sum(points, axis=0)/points.shape[0]
    print(barycenter)
    distance = np.full((points.shape[0]), np.nan)
    point = barycenter
    
    
#     # 随机初始化
#     point = points[0]
#     points = points[:-1,:]
#     sample_points[0,:] = point
#     distance = np.sum((points - point)**2, axis=1)
    for i in range(k):
        distance = np.minimum(distance, np.sum((points - point)**2, axis=1)) ## 前缀思想更新最小值
        index = np.argmax(distance)
        point = points[index]
        sample_points[i,:] = point
        mask = np.ones((points.shape[0]), dtype=bool)
        mask[index] = False
        points = points[mask]
        distance = distance[mask]
    return sample_points
        
np.random.seed(42)
points = np.random.randint(0, 5, size=(50, 3))
sample_points = fps(points, 10)
plot(points, sample_points)
print(points)
print(sample_points)

在这里插入图片描述
————————————————————————————————————————————
最远点采样（FPS）
三维点云处理05-FPS代码实现
版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://blog.csdn.net/weixin_44398263/article/details/123764153

智能推荐

vue开发环境配置（node多版本切换，nvm安装）_node版本切换-程序员宅基地

文章浏览阅读1.3k次，点赞29次，收藏27次。最近在依赖问题上由于我安装的node版本适配性不全面，因为是在云内断网开发，使用不了nvm工具）有时候会因为node的版本过高或者是太低用命令启动时候而报错，试了一下是否可以安装一个高版本和低版本的node在一个系统中，你如果需要高版本的切换高版本的node，如果需要低版本的切换低版本的node，这样这个问题就会完美解决了。_node版本切换

深度可分离卷积（Depthwise Separable Convolution）_深度可分离卷积的优点-程序员宅基地

文章浏览阅读1.3k次。深度可分离卷积（Depthwise Separable Convolution）是一种卷积神经网络中常用的卷积操作，它在减少计算量的同时保持了较好的特征提取能力，因此被广泛用于轻量化的模型设计中。标准卷积使用一个卷积核对输入数据进行卷积，而深度可分离卷积将卷积操作分解为深度卷积和逐点卷积，从而显著减少了参数量。深度卷积只使用一个卷积核对输入通道逐通道进行卷积，逐点卷积使用1x1的卷积核进行通道之间的混合。深度卷积是在输入的每个通道上分别应用卷积核，生成相同数量的通道，然后将这些通道按通道维度进行堆叠。_深度可分离卷积的优点

〖产品思维训练白宝书 - 产品思维认知篇⑩〗- 产品经理 的思维方式对我们有着什么样的启发_管理思维对具体工作的作用-程序员宅基地

文章浏览阅读3.1w次，点赞11次，收藏6次。今天这一章节就来和各位小伙伴聊一聊，"产品经理" 从工作中总结出来的思考问题的角度，尤其是一些思维方式对于我们普通人来说都具有哪些启发。_管理思维对具体工作的作用

【论文Word排版】使用多级列表设置论文序号_序号1.1 1.2怎么排的-程序员宅基地

文章浏览阅读1.4k次。使用多级列表设置论文序号_序号1.1 1.2怎么排的

“自动获取IP地址”和“使用固定IP地址”的区别是什么？_无线网固定ip和自动分配有啥区别-程序员宅基地

文章浏览阅读8.5k次。自动获取IP地址是动态IP，是通过DHCP来获取IP地址，每次上网这个IP都不一样，在IP地址租期满后就有可能会换IP地址了。 使用固定IP地址是静态IP，是自己指定一个IP地址，ISP随时可以到你家查看。手动设置IP地址有个好处，就是一旦设定好后在不更改的情况下IP地址是固定的。 DHCP介绍：DHCP（Dynamic Host Configuration Protocol，动态主机配置协议）是一个局域网的网络协议，使用UDP协议工作， 主要有两个用途：给内部网络或网络服务供应..._无线网固定ip和自动分配有啥区别

CSRF跨站点伪造请求攻击——脱库及密码修改_csrf备份拖库-程序员宅基地

文章浏览阅读987次。脱库及密码修改CSRF 快速拖库案例拖库’本来是数据库领域的术语，指从数据库中导出数据。到了黑客攻击泛滥的今天，它被用来指网站遭到入侵后，黑客窃取其数据库。网站数据库被拖，直接导致用户信息泄露，造成的危害很大，比如：CSDN 明文密码泄露事件、小米 800W 用户信息泄露事件等等首先，我们先登录一下 discuz 的后台，模拟管理员进行周期性的数据库备份。(admin) Uce..._csrf备份拖库

随便推点

UR机器人数据包解析(python与C++实现)_ur机器人包-程序员宅基地

文章浏览阅读4.2k次，点赞5次，收藏23次。一、与UR机器人进行通讯如果还没有完成电脑与UR机器人的通讯，可以参考这个博客（https://blog.csdn.net/qq_41685265/article/details/104327982）二、数据包解释每一个UR机器人对应的软件手册上边是有机器人返回的包中各数据位代表什么以及每个占多少位的空间的，如下：左边一列是UR机器人的各个参数，后边是类型，包括占用几个..._ur机器人包

从零开始：C++如何实现Kafka生产者客户端_c++ kafka-程序员宅基地

文章浏览阅读3.6k次，点赞7次，收藏31次。一、Kafka 生产者的逻辑。二、Kafka 的C++ API。三、Kafka 生产者客户端开发。_c++ kafka

导入Unity 3D场景后所有物体变成白色（材质丢失）_unity道具拖进去发白-程序员宅基地

文章浏览阅读1.5w次。Unity 3D在导入场景或者导入某个3D模型时会出现材质丢失的情况。如下图中右侧白色部分：找到材质丢失的物体，在Inspector面板重新添加材质。 That's all ...._unity道具拖进去发白

034CSS3盒子模型大小计算方法_css一个属性盒子模型自动计算-程序员宅基地

文章浏览阅读1.3k次。一、分类CSS3 中可以通过 box-sizing属性 来指定盒子模型大小的计算方法，有2个值：即可指定为 content-box、border-box，这样我们计算盒子大小的方式就发生了改变。可以分成两种情况：1. box-sizing: content-box 盒子大小为 width + padding + border （以前默认的）2. box-sizing: border-box 盒子大小为 width如果盒子模型我们改为了box-sizing: border-box ， 那paddi_css一个属性盒子模型自动计算

使用EasyExcel单元格内换行_easyexcel 换行-程序员宅基地

文章浏览阅读2k次，点赞2次，收藏6次。在需要换行的地方String.valueOf((char)10)如有String name= “AAA,BBB,CCC”;不进行换行时，单元格显示的则是：AAABBBCCC。_easyexcel 换行

深度学习（deep learning）发展史_深度学习发展历程-程序员宅基地

文章浏览阅读6.2k次，点赞6次，收藏15次。源 | 小象本文节选自人民邮电出版社最新出版的 AI 圣经《深度学习DEEP LEARNING[1]》。《深度学习DEEP LEARNING[2]》英文版由美国麻省理工学院 MIT 出版社于 2016 年 12 月推出，一经出版就风靡全球。《深度学习DEEP LEARNING[3]》的一大特点是介绍深度学习算法的本质，脱离具体代码实现给出算法背后的逻辑，不写代码的人也完全可以看。由深度学习领域三位_深度学习发展历程

推荐文章

热门文章

相关标签