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

相关文章

Java中的Lambda表达式及其应用小结

《Java中的Lambda表达式及其应用小结》Java中的Lambda表达式是一项极具创新性的特性,它使得Java代码更加简洁和高效,尤其是在集合操作和并行处理方面,:本文主要介绍Java中的La... 目录前言1. 什么是Lambda表达式?2. Lambda表达式的基本语法例子1:最简单的Lambda表

Python结合PyWebView库打造跨平台桌面应用

《Python结合PyWebView库打造跨平台桌面应用》随着Web技术的发展,将HTML/CSS/JavaScript与Python结合构建桌面应用成为可能,本文将系统讲解如何使用PyWebView... 目录一、技术原理与优势分析1.1 架构原理1.2 核心优势二、开发环境搭建2.1 安装依赖2.2 验

Java字符串操作技巧之语法、示例与应用场景分析

《Java字符串操作技巧之语法、示例与应用场景分析》在Java算法题和日常开发中,字符串处理是必备的核心技能,本文全面梳理Java中字符串的常用操作语法,结合代码示例、应用场景和避坑指南,可快速掌握字... 目录引言1. 基础操作1.1 创建字符串1.2 获取长度1.3 访问字符2. 字符串处理2.1 子字

SpringShell命令行之交互式Shell应用开发方式

《SpringShell命令行之交互式Shell应用开发方式》本文将深入探讨SpringShell的核心特性、实现方式及应用场景,帮助开发者掌握这一强大工具,具有很好的参考价值,希望对大家有所帮助,如... 目录引言一、Spring Shell概述二、创建命令类三、命令参数处理四、命令分组与帮助系统五、自定

SpringBoot应用中出现的Full GC问题的场景与解决

《SpringBoot应用中出现的FullGC问题的场景与解决》这篇文章主要为大家详细介绍了SpringBoot应用中出现的FullGC问题的场景与解决方法,文中的示例代码讲解详细,感兴趣的小伙伴可... 目录Full GC的原理与触发条件原理触发条件对Spring Boot应用的影响示例代码优化建议结论F

openCV中KNN算法的实现

《openCV中KNN算法的实现》KNN算法是一种简单且常用的分类算法,本文主要介绍了openCV中KNN算法的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的... 目录KNN算法流程使用OpenCV实现KNNOpenCV 是一个开源的跨平台计算机视觉库,它提供了各

MySQL 分区与分库分表策略应用小结

《MySQL分区与分库分表策略应用小结》在大数据量、复杂查询和高并发的应用场景下,单一数据库往往难以满足性能和扩展性的要求,本文将详细介绍这两种策略的基本概念、实现方法及优缺点,并通过实际案例展示如... 目录mysql 分区与分库分表策略1. 数据库水平拆分的背景2. MySQL 分区策略2.1 分区概念

Spring Shell 命令行实现交互式Shell应用开发

《SpringShell命令行实现交互式Shell应用开发》本文主要介绍了SpringShell命令行实现交互式Shell应用开发,能够帮助开发者快速构建功能丰富的命令行应用程序,具有一定的参考价... 目录引言一、Spring Shell概述二、创建命令类三、命令参数处理四、命令分组与帮助系统五、自定义S

C语言函数递归实际应用举例详解

《C语言函数递归实际应用举例详解》程序调用自身的编程技巧称为递归,递归做为一种算法在程序设计语言中广泛应用,:本文主要介绍C语言函数递归实际应用举例的相关资料,文中通过代码介绍的非常详细,需要的朋... 目录前言一、递归的概念与思想二、递归的限制条件 三、递归的实际应用举例(一)求 n 的阶乘(二)顺序打印

springboot+dubbo实现时间轮算法

《springboot+dubbo实现时间轮算法》时间轮是一种高效利用线程资源进行批量化调度的算法,本文主要介绍了springboot+dubbo实现时间轮算法,文中通过示例代码介绍的非常详细,对大家... 目录前言一、参数说明二、具体实现1、HashedwheelTimer2、createWheel3、n