当前位置：文档之家 › 基于降维和筛选的立体图快速生成算法

基于降维和筛选的立体图快速生成算法

  • 格式：pdf
  • 大小：164.62 KB
  • 文档页数：5

收稿日期：2008-09-25基金项目：国家自然科学基金资助项目（60673028）；国家自然科学基金国际（地区）合作交流资助项目（60573174）；合肥市科研计划资助项目（）作者简介：刘晓平（6）

，男，山东济南人，教授，主要研究方向为建模、仿真与协同计算。三维立体图是一种利用人眼的双目视觉特

性巧妙设计的二维图像，其纹理在水平方向上保持一定的重复性，并根据需要表现的三维模型的

形状做必要的变化。图像由众多相关点组成，每组相关点都能使人的两个眼睛在裸眼状态下聚

焦到图像后方一个预先设计的深度，从而整幅图像构成一个完整的三维模型。不同于通常的具有

透视或者光照和阴影效果的二维图像，三维立体2010年工程图学学报2010第2期JOURNALOFENGINEERINGGRAPHICSNo.2

基于降维和筛选的立体图快速生成算法

刘晓平，习雅思

（合肥工业大学计算机与信息学院VCC研究室，安徽合肥230009）

摘要：在基于求交测试的立体图生成过程中，提高计算速度是立体图生成的重要问题。首先通过将空间三角形和空间射线分别映射成平面包围盒和二维点，达到降维的目的；然后，依据当前扫描点的坐标，在模型的所有三角面片中筛选出少数可能的相交三角形，只对筛选出的三角形进行三维求交测试。应用此方法，在不影响立体图效果的情况下，显著提高了基于求交测试的立体图生成速度。

关键词：计算机应用；立体图生成算法；求交测试；降维；筛选

中图分类号：TP391文献标识码：A文章编号：1003-0158(2010)02-0063-05

AFastAlgorithmofGeneratingStereogramBasedon

DimensionReductionandScreening

LIUXiao-ping,XIYa-si

(VCCDivision,SchoolofComputerandInformation,HefeiUniversityofTechnology,HefeiAnhui230009,China)

Abstract:Itisakeyproblemtoraisegenerationspeedinintersection-test-basedautostereogramgenerationprocess.Firstly,spatialtrianglesandspatiallinesaremappedintoplanarboundingboxesandtwodimensionalpoints,thusreducingdimensions;thenafewpossibleintersectingtrianglesarescreenedoutofallthetrianglesofthemodelaccordingtothecoordinatesofthepresentscanningpoint,andfinallyintersectiontestismadewiththesmallamountofscreenedouttriangles.Thismethodhasbeenappliedinthegenerationofstereogramandthegeneratingspeedhasbeenremarkablyincreasedwithoutanydegradationofthestereogram.

Keywords:computerapplication;stereogramgenerationalgorithm;intersectiontest;dimensionreduction;screening

2007-1004194-图从人眼的双目立体成像原理出发，充分利用了

人的双眼对空间深度信息的感知，从而能够给人一种更加真实的立体沉浸感。

1960年，Julesz发现嵌有立体信息的两幅图像，用双眼可以感知到深度信息[1]，Tyler此基础

上将两幅随机点立体图像合并到一个单幅图像

中，得到了所谓的单幅随机点立体图像(Singleimagerandomdotstereogram)，即自动立体图

(Autostereograms)[2-3]。自从Tyler[3]提出基本立体图生成原理以来，

众多学者对立体图的重影(Echo)[4-5]、隐藏面消除

(HSR)[4,6]、随机纹理[7]及立体图的分层效应(Stratifiedcharacter)[8]等问题进行了深入研究。

然而，基本立体图生成算法，即用射线和三维模型求交的方式生成立体图的方法，对任意三维模

型生成立体图，计算量较大，生成速度缓慢，对

此国内外学者没有进行必要的改进。本文提出了一种基于降维和筛选的快速立体图生成方法，该

方法通过降维和筛选大幅度减少计算量，可以在不影响立体图效果的情况下获得较快的生成速

度。

1立体图基本原理

1.1立体图成像原理三维立体图是由众多约束点[4]组成的，所谓

的约束点就是一对相关的像素点，其颜色值、垂直坐标相同，而水平坐标不同。图1是立体图生

成系统的顶视图，Aleft和Aright是成像平面（立体

图）上的一对约束点，由于这两点间距小于人两眼间距，因此左眼和右眼分别通过这两点往成像

平面后面看去，两眼的视线会聚焦于成像平面后面的一点A。立体图上存在众多这样的约束点，

不同的约束点位置和间距不同，如图2所示，从

而人眼聚焦点的位置和远近也不同，众多的聚焦点组成了一个位于成像平面后面的虚拟的三维

模型。由于人的两眼是用同样的原理，即双目立体成像来感知物体远近的，因而立体图成像原理

完全符合人眼视觉特性，通过立体图看到的三维

模型具有强烈的立体沉浸感。1.2立体图生成原理

同成像原理——由约束点聚焦到模型——相反，生成立体图是由模型计算约束点坐标，然后复制约束点颜色值的过程[7]。下面以最简单的列

优先从左到右的扫描顺序为例来说明。

左眼右眼AC

AleftArightBleftBright背景平面

立体图模型B

CleftCright

初始纹理图成像平面

图1立体图原理

AleftAright

初始纹理图立体图BleftBrightCleftCright

图2约束点的颜色复制

按照从左到右的扫描顺序，当前扫描点以及

该点右侧所有的点的颜色是未知的，而当前扫描

点左侧所有点的颜色是已知的，初始纹理图——

立体图中将重复出现的纹理——紧靠在立体图

的左侧。如图1所示，若当前扫描点是Bright，从

右眼到Bright点做一条射线并与模型或背景平面

相交于B点，B点和左眼的连线交成像平面于Bleft点，该点就是Bright的约束点，将Bleft点的颜色值

复制给Bright点。对于图中A点的情形，Aright的约束

点Aleft不在立体图范围内，而位于其左侧的初始

纹理图中，这时，将初始纹理图中Aleft处的颜色

复制到Aright点。对立体图中所有像素点按照列优

先的顺序从下到上、从左到右依次扫描，并使用

上述方法计算约束点坐标、复制约束点颜色值，

就得到了一幅立体图。64工程图学学报2010年2基于降维和筛选的加速算法

基于求交测试的方法是通过人眼与成像平面像素点的连线和模型求交，并反求约束点来生

成立体图的，由于每生成一个像素点，都要对模型中所有三角面片进行求交测试，因而该方法存

在计算速度慢的致命缺点。为此，本文提出一种

基于降维和筛选的立体图快速生成算法。算法描述如下：

预处理对模型进行降维；For(按序扫描的立体图中每列像素点){

筛选1：对该列进行筛选操作得到三角

面片集合U1；For(当前扫描列中的每个像素点I1){

筛选2：根据当前像素点的行坐标对集合U1进行筛选，得到集合U2；

连接右眼和当前像素点的射线与

集合U2中的三角面片求交，求得最近交点P；求连接左眼和P的连线在成像平

面上的交点I2，并将I2颜色值复制给I1；}

}

该算法的关键在于降维预处理和对三角面片的筛选两项操作，下面对其分别进行介绍。

2.1降维预处理如图3，计算任一像素点I1的颜色值，用右

眼P和I1的连线同模型中的每个三角面片

△012VVV求交点。空间三角形△012VVV、射线1PI

的表示及二者交点的参数计算分别如下

,,012,1uvwwuvwuv=++++=IVVV（1）

(),tt=+=LPddIP（2）

()()()

()()()()

()()()

()()()2010

01020

200

0101tu

v=×

×

×

×dVVVV

PVVVVV

dVVPV

PVVVd（3）

这里需要P、I1、V0、V1、V2五个线性无关

的三维向量，数据维数是15。本文算法的降维预处理是指在进行真正的

三维求交测试之前，将模型中每个空间三角形△012VVV映射为成像平面上的平面三角形

△012′′′VVV，继而将△012′′′VVV用其包围盒的4个

参数(xmin,ymin,xmax,ymax)来表示，同时将射线1PI

用成像平面上的二维点I1'来表示。即

()

()()

()()

()()

()()()0000000

1111111minminmaxmax

2222222,,,,,

,,,

,,,,,,

,,,PPPIIIIIxyzxyxyz

xyzxy

xyzxyxyxy

xyzxy′→

′→

′→→

′→包围盒PII

VV

VV

VV

如图3，P点和空间三角形△012VVV顶点的三条

连线分别交成像平面于0′V、1′V、2′V三点，得到

平面三角形△012′′′VVV。对I1点只取其在成像平

面上的二维坐标，得到I1'点。由此，数据的维数从原先的15维降到了6维，其目的在于降低下面的筛选操作的计算复杂度。2.2筛选操作由图3可见，成像平面上位于包围盒(xmin,ymin,xmax,ymax)以内的任一点与右眼的连线有可能和△012VVV有交点，而位于包围盒以外的任一

点与右眼的连线和△012VVV一定没有交点。由此

给出以下筛选标准()()()()minmaxminmaxIIIIxxxxyyyy∧∧∧≤≤≥≥

（4）

图3降维预处理

遍历模型中的所有空间三角形，将满足筛选第2期刘晓平等：基于降维和筛选的立体图快速生成算法65

合集下载

立体拟合算法用途

立体拟合算法用途

立体拟合算法用途

立体拟合算法(Surface Fitting Algorithm)，简称SFA，是一种用于对二维或三维数据表示的复杂图像表面建模的算法。SFA可以将一系列横向和/或纵向面表示为一个各向同性的曲面，可以有效解决有限个点拟合形状复杂的表面的问题，从而解决3D视觉测量中的复杂表面重建问题。

SFA的经典应用是三维重建，尤其是在计算机视觉任务中，它可以从拍摄的照片中恢复3D模型。它可以有效地提取表面特征，用于3D场景重建、物体模型拟合等应用。除此之外，它还用于机器视觉，如物体检测，模式匹配，图像位移等。另外，SFA还可用于航空航天与测绘领域中的地形表面重建。它使用较少的点云边缘和表面，可以快速准确地模拟表面，以生成三维图像。

SFA主要步骤包括：数据准备、表面估计、优化拟合、表面重建等。数据准备是指数据准备的过程，其中包括数据的清理、处理和排序，用于最终重建表面。表面估计是指对给定点云数据集的简单拟合，检测表面的质量，提取表面特征和细节，并在拟合过程中估计表面法向量。优化拟合是指利用已估计的表面法向量，应用数学方法，最小化误差平方和，从而实现对拟合表面的优化。

立体图像中间视点生成算法

立体图像中间视点生成算法

立体图像中间视点生成算法

杨嘉琛;安坤;王斌

【摘 要】To solve the problems of looking around within a three

dimensional scene by freely choosing views and the difficulties of filming

stereoscopic scene with multi-view, this paper presented an intermediate

view synthesis algorithm. The algorithm originally extracted feature points

using the edges of objects in the image, then set up Delaunay triangle

mesh using the feature points and calculated disparity vector field by mesh

mapping, and finally generated intermediate view image through

interpolation algorithm. Experimental results show that intermediate view

image has good quality , and it can rightly reflect the content of the

original views. It also has a good visual effect.%针对观看三维场景时如何自由选择视点与立体景物多视点拍摄困难的问题,提出了一种立体图像中间视点生成算法.算法首次使用图像中物体边缘进行特征点提取,然后利用特征点建立Delaunay

三角形网格,并通过网格映射进行视差矢量场快速计算,最后通过内插算法进行中间视点图像生成.实验结果表明,合成的中间视点图像质量良好,可以正确地反映原有左右视点内容,并且具有良好的视觉效果.

pca筛选特征

pca筛选特征

主成分分析（PCA）是一种常用的降维技术，可以用于筛选特征。下面是使用 PCA 进行特征筛选的一般步骤：

1. 收集和准备数据：收集你要分析的数据，并确保数据已经清理和预处理，例如去除缺失值、标准化或正规化数据等。

2. 计算 PCA：使用 PCA 算法对数据进行计算。这通常可以通过调用现有的 PCA 库或使用编程语言中的相关函数来完成。

3. 提取主成分：PCA 将计算出数据的主成分，这些主成分是原始特征的线性组合，它们代表了数据中的主要模式和变异。

4. 选择主成分：根据你的需求和问题的性质，选择其中一部分主成分作为特征。通常，你可以选择前几个主成分，因为它们解释了大部分数据的变异。

5. 解释和分析：对选择的主成分进行解释和分析。你可以查看每个主成分的载荷图，以了解它们与原始特征之间的关系，以及它们在数据中的重要性。

6. 特征筛选：根据主成分的重要性和解释能力，选择你认为最相关和最有意义的特征。

需要注意的是，PCA 是一种无监督的特征筛选方法，它基于数据的统计特性而不是特定的任务或目标。因此，在使用 PCA 进行特征筛选时，你可能需要结合其他监督学习方法或领域知识来进一步优化特征选择。

isomap降维算法

isomap降维算法

isomap降维算法

降维算法分为线性和非线性两大类，主成分分析PCA属于经典的线性降维，而t-SNE, MDS等属于非线性降维。在非线性降维中，有一个重要的概念叫做流形学习manifold learing。

首先来看下什么叫做流形，流形是一般几何对象的总称，包括各种维度的曲线和曲面，简单理解就是数据本身的分布满足一定的几何特征，以下图中的"瑞士卷"为例

可以看到，在三维空间中，样本点的分布构成了一个瑞士卷的形状，这个瑞士卷就是一个流形。通过流形学习来降维，就是假设数据的分布存在一个潜在的流形，降维其实是将流形在低维空间展开。

从而延伸出了测地线的概念，以上图中的两个黑色点为例，如果不考虑流形的情况下，计算二者的距离可能直接就是欧式距离了，但是在考虑流形的情况下，数据只能在流形上移动，通过邻近点的欧式距离累加来计算，如下图所示

终慢慢延伸，得出两点之间的距离就是红色曲线标记的距离。所谓流形学习，就是在降维时，考虑数据的流形。

在流形学习中，isomap和局部性嵌入LLE都是典型的算法。isomap全称如下

isometric mapping

称之为等距映射，该算法的本质是通过流形中的测地距离来表示高维空间的距离，然后通过MDS算法进行降维。具体的步骤如下

1. 构建邻接图，有两种方法，第一种指定半径阈值，半径内的点为邻近点，第二种为K近邻，在邻近点之间基于欧式距离构建一个邻接图

2. 计算样本点测地距离矩阵，本质是计算邻接图中样本点之间的最短路径，可以选择Floyd-Warshall或者Dijkstra算法

3. 通过MDS算法对测地距离矩阵进行降维

在sickit-learn中使用isomap的代码如下

>>> from sklearn.datasets import load_digits >>> from sklearn.manifold import Isomap

>>> X, _ = load_digits(return_X_y=True)