点云模型的谱聚类分割_马腾1
需积分: 0 68 浏览量
2022-08-03
16:49:58
上传
评论
收藏 622KB PDF 举报
第
２４
卷第
１２
期
２０１２
年
１２
月
计算机辅助设计与图形学学报
Ｊｏｕｒｎａｌ
ｏｆ
Ｃｏｍ
ｐ
ｕｔｅｒ
－
Ａｉｄｅｄ
Ｄｅｓｉ
ｇ
ｎ
＆ Ｃｏｍ
ｐ
ｕｔｅｒ
Ｇｒａ
ｐ
ｈｉｃｓ
Ｖｏｌ．２４Ｎｏ．１２
Ｄｅｃ．２０１２
收稿日期
：
２０１１
－
１２
－
３０
；
修回日期
：
２０１２
－
０８
－
２３．
基金项目
：
国家科技支撑计划
（
２００８ＢＡＨ２９Ｂ００
）
．
马
腾
（
１９８３
—），
男
，
博士
，
主要研究方
向为计算机图形学
、
计算几何
、
数字几何处理
；
龙
翔
（
１９６３
—），
男
，
博士
，
教授
，
博士 生导师
，
主要研究方向为计算机体系结构
、
分布 式并行 处
理
、
嵌入式系统
、
计算机网络安全
；
冯
路
（
１９８２
—），
男
，
博士研究生
，
主要研究方向为计算机图形学
、
计算几何
、
计算同调
；
骆
沛
（
１９８３
—），
男
，
博士研究生
，
主要研究方向为计算机图形学
、
图像处理
、
压缩 传感
；
吴壮 志
（
１９６９
—），
男
，
博士
，
副教 授
，
论文 通讯作 者
，
主要研究方向为计算几
何
、
计算机图形学
、
数字几何处理
、
三维人体测量
、
三维视觉测量
．
点云模型的谱聚类分割
马
腾
，
龙
翔
，
冯
路
，
骆
沛
，
吴壮志
＊
（
北京航空航天大学计算机学院
北京
１００１９１
）
（
ｚｚｗｕ
＠
ｂｕａａ．ｅｄｕ．ｃｎ
）
摘 要
：
为了实现点云模型的有意义分割
，
提出一种基于谱聚类的分割算法
．
首先用图
Ｇ
表示点云模型
，
将分割问题
转化为图切割问题
；
然后根据归一化的非对称
Ｌａ
ｐ
ｌａｃｉａｎ
矩阵构造谱聚类空间
；
最后通过移除掉多余的特征向量
，
在
一个更低维的空间中找到了分割问题的松弛解
．
文中还给出了该算法相关定理的证明
，
并通过实验验证了算法的正
确性和有效性
．
关键词
：
点云模型
；
点云分割
；
谱聚类
；
Ｌａ
ｐ
ｌａｃｉａｎ
矩阵
中图法分类号
：
ＴＰ３９１
Ｐｏｉｎｔ
Ｃｌｏｕｄ
Ｓｅ
ｇ
ｍｅｎｔａｔｉｏｎ
Ｂａｓｅｄ
ｏｎ
Ｓ
ｐ
ｅｃｔｒａｌ
Ｃｌｕｓｔｅｒｉｎ
ｇ
Ｍａ
Ｔｅｎ
ｇ
，
Ｌｏｎ
ｇ
Ｘｉａｎ
ｇ
，
Ｆｅｎ
ｇ
Ｌｕ
，
Ｌｕｏ
Ｐｅｉ
，
ａｎｄ
Ｗｕ
Ｚｈｕａｎ
ｇ
ｚｈｉ
＊
（
Ｄｅ
ｐ
ａｒｔｍｅｎｔ
ｏ
ｆ
Ｃｏｍ
ｐ
ｕｔｅｒ
Ｓｃｉｅｎｃｅ
ａｎｄ
Ｔｅｃｈｎｏｌｏ
ｇｙ
，
Ｂｅｉｈａｎ
ｇ
Ｕｎｉｖｅｒｓｉｔ
ｙ
，
Ｂｅｉ
ｊ
ｉｎ
ｇ
１００１９１
）
Ａｂｓｔｒａｃｔ
：
Ａ
ｓ
ｐ
ｅｃｔｒａｌ
ｃｌｕｓｔｅｒｉｎ
ｇ
ｂａｓｅｄ
ｍｅｔｈｏｄ
ｉｓ
ｐ
ｒｏ
ｐ
ｏｓｅｄ
ｔｏ
ｓｅ
ｇ
ｍｅｎｔ
ｐ
ｏｉｎｔ
ｃｌｏｕｄ
ｉｎｔｏ
ｍｅａｎｉｎ
ｇ
ｆｕｌ
ｓｕｂ
ｐ
ａｒｔｓ．Ｂ
ｙ
ｒｅ
ｐ
ｒｅｓｅｎｔｉｎ
ｇ
ｔｈｅ
ｐ
ｏｉｎｔ
ｃｌｏｕｄ
ａｓ
ａ
ｇ
ｒａ
ｐ
ｈ
Ｇ
，
ｔｈｅ
ｓｅ
ｇ
ｍｅｎｔａｔｉｏｎ
ｐ
ｒｏｂｌｅｍ
ｃａｎ
ｂｅ
ｔｕｒｎｅｄ
ｉｎｔｏ
ａ
ｇ
ｒａ
ｐ
ｈ
ｍｉｎ
－
ｃｕｔ
ｐ
ｒｏｂｌｅｍ．Ｔｈｅ
ｎｏｎｓ
ｙ
ｍｍｅｔｒｉｃ
ｎｏｒｍａｌｉｚｅｄ
Ｌａ
ｐ
ｌａｃｉａｎ
ｍａｔｒｉｘ
ｉｓ
ｕｓｅｄ
ｔｏ
ｃｏｎｓｔｒｕｃｔ
ｔｈｅ
ｓ
ｐ
ｅｃｔｒａｌ
ｓ
ｐ
ａｃｅ．Ｂ
ｙ
ｒｅｍｏｖｉｎ
ｇ
ｒｅｄｕｎｄａｎｔ
ｅｉ
ｇ
ｅｎｖｅｃｔｏｒｓ
ｆｒｏｍ
ｔｈｅ
ｓ
ｐ
ｅｃｔｒａｌ
ｄｏｍａｉｎ
，
ｔｈｅ
ｓｅ
ｇ
ｍｅｎｔａｔｉｏｎ
ｓｏｌｕｔｉｏｎ
ｉｓ
ｆｏｕｎｄ
ｉｎ
ａ
ｌｏｗｅｒ
ｄｉｍｅｎｓｉｏｎａｌ
ｓ
ｐ
ａｃｅ．Ｔｈｅ
ｔｈｅｏｒｅｔｉｃａｌ
ｇ
ｕａｒａｎｔｅｅ
ｏｆ
ｔｈｅ
ｐ
ｒｏ
ｐ
ｏｓｅｄ
ｍｅｔｈｏｄ
ｉｓ
ｐ
ｒｏｖｅｄ．Ｔｈｅ
ａｃｃｕｒａｃ
ｙ
ａｎｄ
ｅｆｆｉｃｉｅｎｃ
ｙ
ｏｆ
ｔｈｅ
ａｌ
ｇ
ｏｒｉｔｈｍ
ａｒｅ
ｖｅｒｉｆｉｅｄ
ｂ
ｙ
ｅｘ
ｐ
ｅｒｉｍｅｎｔａｌ
ｒｅｓｕｌｔｓ．
Ｋｅ
ｙ
ｗｏｒｄｓ
：
ｐ
ｏｉｎｔ
ｃｌｏｕｄ
ｍｏｄｅｌ
；
ｐ
ｏｉｎｔ
ｃｌｏｕｄ
ｓｅ
ｇ
ｍｅｎｔａｔｉｏｎ
；
ｓ
ｐ
ｅｃｔｒａｌ
ｃｌｕｓｔｅｒｉｎ
ｇ
；
Ｌａ
ｐ
ｌａｃｉａｎ
ｍａｔｒｉｘ
作为对三维模型做进一步处理的基础
，
模型分
割是近年来国际学术界的一个前沿研究领域
，
它在
计算机图形学
、
计算机辅助几何设计和数字几何处
理等方面有着广泛的应用
．
例如
，
模型简化可以通过
模型分割生成模型的逼近表示
，
模型压缩可以基于
模型分割结果对分割出的部分分别进行压缩
．
此外
，
模型交互编辑
、
模型匹配与检索
、
参数 化 与 纹理映
射
、
碰撞检测
、
几何变形和计算机动画等工作都可能
需要对模型进行分割以方便后续开发
．
模型分割是指根据一定的几何
、
拓扑或语义特
征
，
将三维模型分割为一组数目有限的
、
各自具有简
单形状意义的且各自连通的子部分
［
１
］
．
基于心理物
理学
，
Ｈｏｆｆｍａｎ
等
［
２
］
提 出 了 视 觉 理 论 的 最 小 值 原
则
：
人类在对物体进行识别时
，
往往将复杂的物体看
成简单的基本元素的组合
；
而在将物体分割为几个
组成要素时
，
倾向于把最小的负曲率线定义为各组
成要素的边界
．
根据该规则得到的分割结果称为有
意义的分割
．
尽管三角网格模型是三维模型的主流
表示方式
，
但是这种表示方法也有以下不足
：
１
）
三角网格模型不是扫描设备的标准输出格式
，
评论0