Multidimensional Scaling(MDS多维缩放)算法及其应用

2023-12-06 23:04

本文主要是介绍Multidimensional Scaling(MDS多维缩放)算法及其应用,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

在这篇博客中,我将与大家分享在流形分析领域的一个非常重要的方法,即多维缩放MDS。整体来说,该方法提供了一种将内蕴距离映射到显性欧氏空间的计算,为非刚性形状分析提供了一种解决方案。当初就是因为读了Bronstein的相关工作【1】,才下定决心在人脸数据分析中使用内蕴度量来建立特征分析方法,可以说MDS对我的学术之路起到了很大的影响作用。


1. 前言

在非刚性形状匹配中,我们希望找到两个曲面的对应关系。由于受到非刚性形变影响,使得我们不能直接建立基于类似ICP一样的方法来实现对准。提到非刚性分析,很自然的就会让人联想到使用基于曲面第一基本形式的内蕴几何特征来建立分析方法。对于人脸人体这种非刚性形变分析对象,由于受到骨架的约束,使得其非刚性形变满足近似等距的特性,这里的等距指测地线。曲面第一基本形式对应曲面曲线,刚好可以使用测地线作为表示。那么,我们只要基于测地线来建立几何特征表达,就能够实现近似等距条件下的形状分析,进而满足非刚性形状分析要求。

关于测地线的计算,我在之前的博客已经有所介绍,有兴趣的同学可以翻看:

Fast Marching算法及其在点云测地线计算中的应用-CSDN博客

Geodesic in Heat: 一种测地线计算方法-CSDN博客

在有了测地线作为内蕴几何特征的显性表示后,我们希望对原始曲面建立一种形状度量,这种度量由测地线定义,能够反映形状之间的相似程度,进而推出点的对应关系。一个最直接的想法是利用参数化的方法。通过参数化,我们能够对原始的曲面进行“摊平”,进而在摊平后的参数域建立对应。然而,参数化需要指定边界和控制点,其本身的计算也相对复杂。如果对于拓扑相对复杂的形状建立参数化,其对原始测地线距离将会产生严重扭曲,即不再是可控的近似等距变换。我们希望使用类似ICP那样的直接距离对应方法,对基于测地线表示的曲面进行匹配。一个理想的方案是将点对间的测地距离,变换到一个m维的欧氏空间。在该欧氏空间中,点与点的欧氏距离与未变换前的点对测地距离存在一种对应关系。这样,我们只需要在变换后的形状进行刚性配准,点对的结果就对应了原始数据的非刚性对应结果。这就是使用MDS方法实现非刚性形状分析的初始想法。


2. MDS介绍

如前所述,MDS的目的就是将点间的测地距离嵌入到一个新的欧氏空间中,使得内蕴距离获得显性化的表达。在相关工作【2】中,这种嵌入后的曲面表达被称为bending-invariant canonical forms。具体过程如下:

首先我们给出一个测地线的表示δij,表示两点pi和pj的测地距离。我们把所有点的行列组成矩阵形式,使用δij填满,ij相等为0。然后,我们对δij求平方,重写矩阵里的项:

Δ所表达的矩阵在等距变换下是不变的,但是其形式会因为点序号的变化而变化。我们希望获得一个测地距离不变的表示,且具有唯一性。这时,就可以利用MDS将其嵌入到一个低维的欧氏空间中,该过程等价于:

嵌入误差可以写为:

MDS方法也包含很多类别,Bronstein在论文【3】中提到一种称为classical scaling【4】的方法来实现MDS:

首先对Δ进行中心化操作,即double-centering。J=I-1/2U,I是单位矩阵,U是一个完全由1组成的矩阵。之后对B进行主成分分析,获得对应的m个特征值和特征向量:

i对应点的序号,j对应m的维度,一般m取3,即将原始形状基于测地距离映射会三维欧氏空间。这样经过特征向量e表达的新坐标x在欧氏空间组成一个新的形状,在工作【1】中被称为Canonical form,以我的观点来看,即内蕴型。


3. 应用

Bronstein在最开始设计算法的时候,目标就是解决三维人脸识别中的表情鲁棒问题。他在论文中已经提到了一般性非刚性形状分析可以转换为对内蕴距离向欧氏空间的嵌入,如下图:

上面的例子充分说明将测地线嵌入回欧氏空间,对应的形状所具备的近似等距特性。原来手指的欧氏距离,一定会因为非刚性形变发生变化,但是对应的测地距离是稳定的。将测地距离嵌入回欧氏空间,得到右边的Canonical form,其点的欧氏距离就具备了原来点的测地距离特性。这时我们再使用类似ICP的方法,就能够非常方便的建立对应关系。

表情即被认为是一种近似等距的非刚性形变,如果我们对人脸数据进行类似Canonical form的变换,那么变换的结果自然会获得对表情不变的结果。原论文中给出了示意图:

可以看到第一行的人脸是具有多种不同的表情的。但是这些人脸的Canonical form具有极其相近的几何表示。在Canonical form的基础上,设计三维人脸识别算法,自然能获得表情鲁棒特性。论文中还给了一个系统界面:

整个算法流程还是非常清晰的。但是求Δ需要的庞大计算量,限制了该算法的效率。

Reference

[1] Bronstein AM, Bronstein MM, Kimmel R. Three-dimensional face recognition[J]. International Journal of Computer Vision, 2005, 64: 5-30.

[2] Elad A, Kimmel R. Bending Invariant Representations for Surfaces[C]. Proceedings of the Conference on Computer Vision and Pattern Recognition, 2001, 2: 168-168.

[3] Bronstein AM, Bronstein MM, Kimmel R. Expression-invariant 3D face recognition[C]. International conference on Audio-and video-based biometric person authentication, 2003: 62-70.

[4] Young G, Householder A S. Discussion of a set of points in terms of their mutual distances[J]. Psychometrika, 1938, 3(1): 19-22.

这篇关于Multidimensional Scaling(MDS多维缩放)算法及其应用的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/463678

相关文章

Python中随机休眠技术原理与应用详解

《Python中随机休眠技术原理与应用详解》在编程中,让程序暂停执行特定时间是常见需求,当需要引入不确定性时,随机休眠就成为关键技巧,下面我们就来看看Python中随机休眠技术的具体实现与应用吧... 目录引言一、实现原理与基础方法1.1 核心函数解析1.2 基础实现模板1.3 整数版实现二、典型应用场景2

SpringBoot实现MD5加盐算法的示例代码

《SpringBoot实现MD5加盐算法的示例代码》加盐算法是一种用于增强密码安全性的技术,本文主要介绍了SpringBoot实现MD5加盐算法的示例代码,文中通过示例代码介绍的非常详细,对大家的学习... 目录一、什么是加盐算法二、如何实现加盐算法2.1 加盐算法代码实现2.2 注册页面中进行密码加盐2.

Python Dash框架在数据可视化仪表板中的应用与实践记录

《PythonDash框架在数据可视化仪表板中的应用与实践记录》Python的PlotlyDash库提供了一种简便且强大的方式来构建和展示互动式数据仪表板,本篇文章将深入探讨如何使用Dash设计一... 目录python Dash框架在数据可视化仪表板中的应用与实践1. 什么是Plotly Dash?1.1

Android Kotlin 高阶函数详解及其在协程中的应用小结

《AndroidKotlin高阶函数详解及其在协程中的应用小结》高阶函数是Kotlin中的一个重要特性,它能够将函数作为一等公民(First-ClassCitizen),使得代码更加简洁、灵活和可... 目录1. 引言2. 什么是高阶函数?3. 高阶函数的基础用法3.1 传递函数作为参数3.2 Lambda

Java时间轮调度算法的代码实现

《Java时间轮调度算法的代码实现》时间轮是一种高效的定时调度算法,主要用于管理延时任务或周期性任务,它通过一个环形数组(时间轮)和指针来实现,将大量定时任务分摊到固定的时间槽中,极大地降低了时间复杂... 目录1、简述2、时间轮的原理3. 时间轮的实现步骤3.1 定义时间槽3.2 定义时间轮3.3 使用时

Java中&和&&以及|和||的区别、应用场景和代码示例

《Java中&和&&以及|和||的区别、应用场景和代码示例》:本文主要介绍Java中的逻辑运算符&、&&、|和||的区别,包括它们在布尔和整数类型上的应用,文中通过代码介绍的非常详细,需要的朋友可... 目录前言1. & 和 &&代码示例2. | 和 ||代码示例3. 为什么要使用 & 和 | 而不是总是使

Python循环缓冲区的应用详解

《Python循环缓冲区的应用详解》循环缓冲区是一个线性缓冲区,逻辑上被视为一个循环的结构,本文主要为大家介绍了Python中循环缓冲区的相关应用,有兴趣的小伙伴可以了解一下... 目录什么是循环缓冲区循环缓冲区的结构python中的循环缓冲区实现运行循环缓冲区循环缓冲区的优势应用案例Python中的实现库

SpringBoot整合MybatisPlus的基本应用指南

《SpringBoot整合MybatisPlus的基本应用指南》MyBatis-Plus,简称MP,是一个MyBatis的增强工具,在MyBatis的基础上只做增强不做改变,下面小编就来和大家介绍一下... 目录一、MyBATisPlus简介二、SpringBoot整合MybatisPlus1、创建数据库和

python中time模块的常用方法及应用详解

《python中time模块的常用方法及应用详解》在Python开发中,时间处理是绕不开的刚需场景,从性能计时到定时任务,从日志记录到数据同步,时间模块始终是开发者最得力的工具之一,本文将通过真实案例... 目录一、时间基石:time.time()典型场景:程序性能分析进阶技巧:结合上下文管理器实现自动计时

Java逻辑运算符之&&、|| 与&、 |的区别及应用

《Java逻辑运算符之&&、||与&、|的区别及应用》:本文主要介绍Java逻辑运算符之&&、||与&、|的区别及应用的相关资料,分别是&&、||与&、|,并探讨了它们在不同应用场景中... 目录前言一、基本概念与运算符介绍二、短路与与非短路与:&& 与 & 的区别1. &&:短路与(AND)2. &:非短