月度归档:2014年12月

GraphLab Create使深度学习更easy

版权声明:本文系本站作者自己翻译整理,欢迎转载,但转载请以超链接形式注明文章来源(planckscale.info)、作者信息和本声明,否则将追究法律责任。

消息来源: GraphLab Create关于深度学习的一篇博文

机器学习的一个核心目标是对输入数据进行分类。例如一个训练好的分类器,输入一张图片便可预测这张图中是狗还猫。

dl_simpleclassifier

用来分类的方法有很多,支持向量机、逻辑回归、深度学习等。最近深度学习如日中天,虽然很强大,但其训练起来却是昂贵的,费时费力。你需要确定网络多少层,需要确定每层多少个节点,需要初始化模型的参数等等。简单来说,深度学习模型就像一个带有很多旋钮和表盘的机器,这些旋钮和表盘你没调好它就罢工。

2

最新发布的GraphLab Create 1.1 及1.2使深度学习变得超级简单。它不需要你自己在选择模型和调参上成为专家,就可以玩转神经网络。基于输入数据,neuralnet_classifier.create()函数选择一个网络架构并设置合理的参数值。在MNIST上测试:

3

在测试集上评估这个模型:

4

结果达到了98%的精度。寥寥几行代码,深度学习就这么简单。

这样还不够,GraphLab Create还要求要使深度学习变得更简单。尽管GraphLab Create能选择较好的网络架构和参数,但这种自动化处理往往是不够的。优化设置往往是极端具体的问题,没有好的直觉、没有足够丰富的经验、没有很多PhD学生的话这个问题很难解决。

其实并非所有问题都得从头开始去训练一个深度模型,再者说,你要解决的问题也并不特殊,它与一些已经解决的问题多少有关联。拿分类猫狗的例子,最有名的数据集ImageNet,DNN表现最优异,其训练的模型可将输入从一千种类别中分辨出其属于哪一类。分辨狮子和狐狸类别的那些特征难道对分辨猫狗没用?

当然有用。通过简单移除DNN的输出层,将传播到输出层的信号作为特征喂给任何一种分类器便可解决我们区分猫狗的任务。步骤如下:

第一步:在一个超大的通用的数据集上训练一个DNN分类器。最好的例子是ImageNet,1000种类别120万张图片。GraphLab拥有在ImageNet上训练好的模型,因此当你应用的时候可以跳过这一步,只需下载这个模型:

gl.load_model(‘http://s3.amazonaws.com/GraphLab-Datasets/deeplearning/imagenet_model_iter45’)

第二步:DNN每一层的输出可以看作每张图像的一个有意义的向量表示。对你任务中的图像,提取输出层前面那层的特征向量。

第三步:以这些特征作为输入,训练一个针对你自己任务的新的分类器。

乍一看可能觉得这样比训练一个DNN更复杂。其实不然,第一步可在很多不同的问题上复用,而且GraphLab给你提供了这个模型,所以并不需要你自己去训练。第二步用GraphLab的API就可搞定。第三步随便一个比深度学习模型简单的分类器都可行。这样一套流程下来,无需调参、训练更快、效果更好,即使有时训练数据不够也不影响。另外,即便你的第三步分类任务与第一步训练的任务相对无关,此方法效果依然很好。

5

举个例子,还是分类猫和狗:

第一步,下载在ImageNet上训练好的模型。

6

而后下载狗和猫的图像。因原始ImageNet模型在256x256x3的图像上训练,所以这里调整了一下图像大小。

7

第二步,提取特征

8

第三步,训练一个简单的分类器

9

为看效果,做个评估:

结果达到约96%的精度,为作对比,仅用.create()方法,结果如下:

精度仅60%。很明显,提取特征结合简单的分类器的方法超级强悍。

为了确保此方法具有通用性,在CIFAR-10上验证。CIFAR有6万张32×32的图像,总共分为10类,5万张训练图像,一万张测试图像。少量例图如下:

12

重复上述步骤:

13

做评估:

14

精度接近95%。事实上,这个结果比已公布的任何结果都好,且看齐Kaggle竞赛中获胜的结果。人类的识别精度才94%。

Graph Create在深度学习这块的表现实在令人兴奋。会持续关注之。

 

2014,虚拟现实大爆炸

Venturebeat 的报道,《神庙逃亡》结合三星虚拟现实头戴显示器 Gear VR 推出《神庙逃亡 VR》了。游戏中,玩家通过头戴Gear VR查看游戏画面,通过倾斜身体或跳动躲避障碍。14 (1)14 (2)

虽然三星的Gear VR仅售200美元,但遗憾的是,这货需要Galaxy Note 4手机为其提供显示与处理能力,所以Gear VR不兼容其它Android手机或设备,必须配合Galaxy Note 4才能用。

这是前两天发布的事儿,回头看最近几个月让人震撼的虚拟现实应用铺天盖地,简单说几个我觉有杀伤力的。

Wired报道的Collider,让你拥有穿梭于大型强子对撞机之内的体验。科学家在欧洲粒子物理研究中心的大型强子对撞机里发现了“希格斯玻色子”(又称“上帝粒子”),为了解宇宙开拓了视野。头戴式虚拟现实设备 Oculus Rift 和动作感应设备 Leap Motion 联手打造了 Collider,通过它用户可以以第一视角体验粒子对撞。

用户戴上 Oculus Rift会感觉自己“置身”于对撞机的同步加速器环中,这里正是科学家们观察粒子对撞的地方。在虚拟模型中,人类的手由五条带有骨节标志的线表示,轻微移动即可重置眼前的虚拟世界,仿佛进入巨型万花筒。

collider-03collider-05

不戴虚拟实境设备也可以体验Collider。用户在Leap Motion上方挥挥手,投影仪即投射出相应结果。

collider-08collider-07

 

另外,设计者Lee为Collider加入了模拟玩家手动操作的元素。在用户体验设计方面,3D还是一块未拓荒的土地。其团队在这方面做着前无古人的探索。

另一个是吓死人不偿命的世界首部虚拟现实鬼片《11:57》,观影者头戴Oculus Rift,便可体验360度全方位的惊悚震撼效果。

122303jjl6la82hl8ozayn122303ari2xynvnven4t2u

为了拍摄出360度身临其境的体验效果,Leichsenring和Gillström制造出一项专门的器材,搭载了6部GoPro HERO3+相机用于拍摄。用到了类似我们的技术:多路视频实时拼接融合成360度全景

独自一人呆在黑暗密闭的地下室里,手脚被捆绑在椅子上,360度无死角的惊悚场景全都冲向你来,对于我这种五六年不敢看恐怖片的胆小鬼是要吓哭了。

最近航天上也开始玩虚拟现实。虚拟现实可以让宇航员去沙滩度个假,科学家们正在与Oculus Rift虚拟现实设备合作,希望为长期在太空工作的人们提供“回归地球之旅”,徜徉于沙滩,静坐于山涧,或是和家人享受闲暇时光。这项技术不仅提供视觉仿真,还加入了嗅觉和听觉。

15 (1) 15 (2)

从10月15日起,该技术的测试版本已开始运用于夏威夷的一项火星人居环境模拟项目中。该六人小组将在此呆上八个月,DALI也计划测试南极洲的虚拟实境演示情况。

今年真是虚拟现实的爆炸年,各种应用应接不暇。各大佬也开始活动。

Facebook花20亿美收购Oculus开启了虚拟现实的应用之旅;随后Google在I/O大会上推出了Cardboard,利用过剩的手机配置来实现虚拟现实,促进了其在移动设备上的应用;据说苹果公司在招聘有虚拟现实类相关产品开发经验的工程师,这暗示其在这这方面可能也会有大动作。微软为Xbox one打造了一套虚拟现实智能头戴设备,估计明年6月的E3大展上会发布这一产品。

大佬们的纷纷加入,往往会催化一个产业的成熟。交互革命也许已经拉开序幕,让我们拭目以待吧。

Levenberg-Marquardt算法

匆匆一更。还没写完,对不起我太懒了T_T

版权声明:原创作品,欢迎转载,但转载请以超链接形式注明文章来源(planckscale.info)、作者信息和本声明,否则将追究法律责任。

Levenberg-Marquardt算法(下文简称LM算法)通常用于非线性最小二乘法的目标函数极小化。这是一个置信域方法(Trust-Region Method),为了防止步长太大而跳到非预期的局部极小值,这类算法自适应的调整步长。

假设f(x)为一个向量函数,每个分量都刻画了一个样本和模型预测之间的某种偏差,则非线性最小二乘目标函数为

(1)   \begin{eqnarray*} E&=&\transp{f}f \end{eqnarray*}

通常基于梯度的数值极小化算法,都是用一点的局域特征(如导数)建立该函数变化趋势的模型,以此来推测一个最可取的下降方向和步长。取一阶导数近似是线性模型,用切平面来近似函数在该点附近的变化趋势;取到二阶导数近似则是二阶模型,用一个抛物面来近似。当然,也可以取到更多阶,模型的几何直观也会越来越复杂,越来越精确的逼近真实的函数变化趋势,但是会付出更大的计算代价。当取到无穷阶时,模型在级数收敛区间内可以做到完全精确的刻画函数,此时这就是模型就是函数的泰勒展开了。

我们把f在任一点x附近展开f(x+\delta x)=f(x)+J(x)\delta x,这样Ex附近就是

(2)   \begin{eqnarray*} E(x+\delta x)&=&|f(x)+J(x)\delta x)|^2\\ &=&|f|^2+2\transp{f}J(x)\delta x + |J(x)\delta x|^2 \end{eqnarray*}

注意Jf而非E的导数,这里我们得到了E的二阶展开,即用一个抛物面来近似目标函数E在一点附近的形态。这个二阶模型显然是一个线性最小二乘问题——这正是我们所要的,把一个非线性最小二乘问题转换为一系列线性最小二乘问题来求解。

因此一个简单直接的想法就是,每一迭代步构造这样一个线性最小二乘问题,通过极小化它下降到下一个迭代点,循环直到收敛。但这个方案显然有问题。我们的二阶展开模型只能在一个小邻域上有效,当\delta x增大时,被我们忽略掉的高阶项就会越来越明显,最后让二阶模型彻底失效。这样,直接根据二阶模型计算出来的迭代点对目标函数而言可能并非我们想要的,它的函数值可能比上一点还要高(因而目标函数不降反增);也可能尽管比上一点下降了但是却跳到了另一个我们不想要的凸区域里(因而算法会收敛到离初始猜测解更远的局部极小值点上);更严重的情况,模型甚至可能是退化的,即一种极端形式的抛物面——就像一本被半卷起的书,此时我们在弯折的方向仍能找到极小值,但在其垂直方向已经无法找到极小值(或者说处处极小)。

为了解决以上问题,我们需要给模型加入一些约束,把迭代步长约束在一个合理的范围内,保证在这个范围内模型足够有效。同时,我们也希望在二阶模型退化的时候,约束能够拯救它,保证算法总能求出一个极小值。这个约束很简单,如下

(3)   \begin{eqnarray*} E(x+\delta x)&=&|f(x)+J(x)\delta x)|^2 + \lambda |C(x)\delta x|^2 \end{eqnarray*}

我们加入了一个二次约束项。单独看该项,它是一个中心在x点,开口向上的抛物面,或者说一个二次势阱。这个势阱像一个箍,把\delta x箍在x点附近的小邻域中。通过调节\lambda可以增强或减弱它对\delta x的约束:当\lambda充分大时,约束项成为主要贡献项,这时模型总有一个极小值,且步长较小;当\lambda较小时,约束项几乎可以忽略,算法以大步长快速往极小值接近。

再来看矩阵C(x). 这个矩阵通常被设置为对角的。此时,

(4)   \begin{eqnarray*} |C(x)\delta x|^2 &=& \transp{\delta x}\transp{C}C\delta x\\ &=&\sum_{i} \lambda_i \delta x_i^2 \end{eqnarray*}

\transp{C}C的本征值控制着每个方向上抛物面上升的快慢。可见,如果一个方向相应的本征值被设置的较小,那么该方向的约束项上升缓慢,约束较弱,步长跨度较大;否则反之。现实中使用的模型,目标函数对于各个参数的敏感度不同,有的参数略微调整就可以导致目标函数的强烈变化,有的则反之。C(x)这个参数矩阵使得我们可以针对各个不同的参数设置不同程度的步长约束,从而能够构造出一个稳定的算法。

(未完待补)

算法描述与性能优化的解耦——Halide语言 (1)

版权声明:原创作品,欢迎转载,但转载请以超链接形式注明文章来源(planckscale.info)、作者信息和本声明,否则将追究法律责任。

程序的结构和运行效率常常被人们看作是难以调和的。这个事实源于我们把一个数学上结构清晰良好的(比如,用递归形式刻画的)算法映射到一个现实的不完美的计算模型上,这个模型计算是有代价的,要极小化这个代价就需要尽可能的重用中间计算结果,减少依赖增加指令级并行,充分利用空间和时间的Locality和存储体系的分级结构,等等…

于是长久以来,程序中描述算法要”做什么“的逻辑,掩盖在了用来优化性能,描述”怎么做“的芜杂逻辑之下。当然,我们也有能够只通过清晰刻画”做什么“来编程的语言(如函数式语言家族,尤其是以Haskell为代表的纯函数式语言),这些语言收起了让用户自己规划计算过程的权限,把计算过程的优化交给编译器自动完成。这导致了人们对其效率的不信任,事实上这个问题也确实普遍存在,聪明的编译器只是少数,而且他们也未必能保证给出一个高度优化的程序。所以至今,对高性能有要求的各种库仍然采用C等提供了底层操作的语言实现。

性能优化会破坏软件结构这一点带来了无尽的苦恼,和风险。这使得我们每做一次优化都需要格外慎重。性能优化后的代码基本被凝固,不再具有良好的可维护、可修改性质,这样我们跨平台移植或者改变优化方案时就会面临代码需要大片重写的风险。所以人们确立了”不成熟的优化是万恶之源“这样的信条,强迫自己把性能优化留到最后一步,万不得已时采用最成熟最保守的思路去优化。

真的只能接受这个现状吗?我们知道抽象和解耦是软件的灵魂,当两件不同目的的事情纠缠在同一段代码中时,意味着需要把两件事情各自抽象出来,解耦成简单独立的逻辑。这里我们正面对一个典型的解耦问题:算法描述(做什么)和性能优化(怎么做)需要被解耦。函数式语言虽然能做到这个解耦,但是它把优化工作交给不那么靠谱的编译器了,那能否把这个优化工作交还给设计者自己呢?设想我们如果能够独立构造两个逻辑,就可以利用如纯函数式语言这样具有强大描述力的工具,寥寥数笔刻画出算法;然后再针对具体的硬件平台,实现相应的优化计算方案。不同的平台间的移植只需要替换这个优化方案部分。更好的一点是,我们可以尝试更激进的优化方案,测试各种各样的方案,这不过是个替换而已,而且对算法的功能本身没有影响。

解耦工作的难度一定程度上取决于要解耦的两个概念是否能够清晰的区分开来。算法描述和性能优化的解耦是不容易的,因为一般说来这两个概念不易区分。但在图像处理这样的领域里,计算具有典型的模式(数据在pipeline上流动,被各个节点依次处理),我们仍然可以把二者很好地解耦。

Halide就是这样一门语言。

Halide是由MIT、Adobe和Stanford等机构合作实现的图像处理语言,它的核心思想即解耦算法和优化,事实也证明它是成功的,在各种实例中它均以几分之一的代码量实现出同等或者数倍于手工C++代码的效能,更不用提代码的可维护性和开发效率。

先上例子(来自Halide的文献”Decoupling Algorithms from Schedules for Easy Optimization of Image Processing Pipelines”),三个版本的图像模糊算法,以及他们各自的性能。




void box_filter_3x3(const Image & in, Image & blury) {
	Image blurx(in.width(), in.height()); // allocate blurx array
	for (int y = 0; y < in.height(); y++)
	for (int x = 0; x < in.width(); x++)
		blurx(x, y) = (in(x - 1, y) + in(x, y) + in(x + 1, y)) / 3;
	for (int y = 0; y < in.height(); y++)
	for (int x = 0; x < in.width(); x++)
		blury(x, y) = (blurx(x, y - 1) + blurx(x, y) + blurx(x, y + 1)) / 3;
}



9.96 ms/megapixel
(quad core x86)

代码1.  C++实现图像模糊,结构良好但效率差。




void box_filter_3x3(const Image & in, Image & blury) {
	__m128ione_third = _mm_set1_epi16(21846);
#pragmaomp parallel for
	for (int yTile = 0; yTile < in.height(); yTile += 32) {
		__m128ia, b, c, sum, avg;
		__m128i blurx[(256 / 8)*(32 + 2)]; // allocate tile blurx array
		for (int xTile = 0; xTile < in.width(); xTile += 256) {
			__m128i*blurxPtr = blurx;
			for (int y = -1; y < 32 + 1; y++) {
				const uint16_t *inPtr = & (in[yTile + y][xTile]);
				for (int x = 0; x < 256; x += 8) {
					a = _mm_loadu_si128((__m128i*)(inPtr - 1));
					b = _mm_loadu_si128((__m128i*)(inPtr + 1));
					c = _mm_load_si128((__m128i*)(inPtr));
					sum = _mm_add_epi16(_mm_add_epi16(a, b), c);
					avg = _mm_mulhi_epi16(sum, one_third);
					_mm_store_si128(blurxPtr++, avg);
					inPtr += 8;
				}
			}
			blurxPtr = blurx;
			for (int y = 0; y < 32; y++) {
				__m128i*outPtr = (__m128i*)(& (blury[yTile + y][xTile]));
				for (int x = 0; x < 256; x += 8) {
					a = _mm_load_si128(blurxPtr + (2 * 256) / 8);
					b = _mm_load_si128(blurxPtr + 256 / 8);
					c = _mm_load_si128(blurxPtr++);
					sum = _mm_add_epi16(_mm_add_epi16(a, b), c);
					avg = _mm_mulhi_epi16(sum, one_third);
					_mm_store_si128(outPtr++, avg);
				}
			}
		}
	}
}



11x fasterthan a
naïve implementation
0.9 ms/megapixel
(quad core x86)

代码2.  上一段代码的优化版本,效率好但结构性破坏。




Func halide_blur(Func in) {
	Func tmp, blurred;
	Var x, y, xi, yi;
	// The algorithm
	tmp(x, y) = (in(x - 1, y) + in(x, y) + in(x + 1, y)) / 3;
	blurred(x, y) = (tmp(x, y - 1) + tmp(x, y) + tmp(x, y + 1)) / 3;
	// The schedule
	blurred.tile(x, y, xi, yi, 256, 32)
		.vectorize(xi, 8).parallel(y);
	tmp.chunk(x).vectorize(x, 8);
	return blurred;
}



0.9 ms/megapixel

代码3.  Halide代码,清晰简短,且一样高效。

我们可以看到,在Halide所实现的版本中,代码分成两部分,一部分是描述算法的algorithm部分,采用典型的函数式风格定义出要计算什么;另一部分则是指定”如何计算“的schedule部分。Halide目前没有自己的语法解析器,它的前端直接嵌入在C++里,作为一个库来使用。我们构造出一个图像处理算法后,可以把它编译到诸如x86/SSE, ARM v7/NEON, CUDA, Native Client, OpenCL各种平台上。

用schedule这样一个概念来抽象各种各样的底层优化技巧是整个方案里最关键的一环。不同平台有不同的优化技巧,怎样才能用一个统一的观点去处理它们,使得我们能在一个足够简单、与底层细节无关的世界观里处理优化问题?Halide用这样的观点来统一各种性能优化方法:它们都是控制存储或计算顺序的手段。这样,Halide通过提供一系列控制计算过程中存储和计算顺序的工具而帮助我们描绘性能优化方案。

Halide目前并没有太多的考虑编译器自动优化的问题,但这是一个漂亮的开端。如果将来在手动优化的同时仍有强大的编译器优化做后盾,将会是一番什么景象?

本站将持续跟踪这方面的进展。关于Halide语言进一步的剖析,请等待下篇。

(未完待续)

酷技术:freeD三维场景回放

昨天说了3D全景,今天再搜了下,发现了freeD这个东东。

说起来不新鲜,中文网络上这条信息也已经是一年前的了。这就是一个3D重建的典型应用,在体育场上利用多台(比如官网给出的16-28)高清相机在多个位置多个角度采集同一场景的图像,重建出3D模型。从Demo看重建质量真的不错,但不知实际运行效果如何。

视频1.  freeD三维场景回放技术

3D重建这段时间也是山雨欲来的感觉,之前放出了超炫城市3维重建Demo(视频2)的acute3D公司目前已经把爪伸到中国了,他们通过航拍视频重建出了长城的3D模型

视频2.  acute3D的巴黎三维场景重建Demo

这家公司致力于大规模的三维重建,这是个激动人心的事儿。比如目前百度地图已经有360°*90°的高清全景街景,仅用这些数据就可以重建出相当一部分城市三维面貌来,若再有航拍数据,一个真正的数字化虚拟城市也是可以期待的。如果能用微型无人机航拍采数据,可以实现廉价的大规模重建,基于此能玩出多少花样来,只是个想象力的问题。

对于想亲手玩一下的朋友,不妨试一下VisualSFM或者123D Catch,前者更学术化一些,由PBA的作者Changchang Wu开发(PBA是目前最好的开源Bundle Adjustment实现),后者是个产品。

酷技术:SamSung Project Beyond,实时3D全景

最近几个月各种实时全景拼接技术雨后春笋般冒了出来,看来一项技术到了瓜熟蒂落的时候,是挡也挡不住。今早无聊搜了下实时全景,还是把不关注技术新闻又懒于做技术推广的老夫吓了一跳。

目前市面上大多数产品跟我们类似,无非是给拼接算法一个高性能实现,或者基于FPGA,或者基于CUDA。真正让人眼睛一亮的是三星最近推出的Project Beyond,这款产品配合一个三星的虚拟现实眼镜Gear VR,可以实现真正的身临其境感——对于我们关注技术的人来说,3D,这个词儿是唯一的重点。

beyond_01

图1.  三星Project Beyond

我们知道人类之所以能感知纵深,是因为双眼上像点与场景点构成一个三角,数学上我们可以用三角测量来计算纵深,因此我们双眼感知到的信息里是包含纵深的。3D眼镜正是利用该原理,给双眼不同的图像,利用这个差异产生纵深感。

从目前的报道里,我们可以看出Project Beyond是一个赋予双目纵深感的全景装置,这一点是它超出以往技术的关键。

QQ图片20141219103205

图2.  Project Beyond的构造

如图1,Project Beyond有17个广角相机,其中1个指向天空。它采取了与普通全景相机共中心摆位不一样的摆位方式,这自然是因为要产生3D效果的要求——普通的共中心摆位无法感知到纵深信息,这可以参考我们的《全景拼接算法原理》系列文章。

 

我们也一直有把自己的实时全景技术做成微型硬件设备的想法,可惜各方面因素制约(尤其销售是我们的弱项)尚未实施。现在看起来有些可惜。

我们认为计算机视觉在接下来几年会有狂飙突进的发展——各方面条件都已成熟了,无论是理论还是硬件计算能力。而新型的人机交互手段可能是这其中最重要的一个领域,在PC迅猛发展的这二三十年里,鼠标键盘始终巍然不动,现在是时候改变了。Project Beyond这样的产品只是个开始,各种新的体验正扑面而来。

可触摸的全息影像—-让你在VR中有身临其境的体验

对我们人类来说,感受是可信赖的。虚拟现实总是飘渺无法捕捉的,然而据New Scientist消息,英国 Bristol 大学的Ben Long和他的同事们利用声波投影实现了“可触摸的全息影像”,将虚拟现实带入到我们的物理世界。

给以触觉、视觉和声音这些真实感受会使人们更易沉浸到虚拟现实中,会给人们带来全新体验。例如,拥有了感受虚拟物体形状的能力,医生便可以用手直接去检查CT扫描出来的肿块肿瘤;更甚者,我们去参观博物馆时,也可以好好把玩感受那些珍藏在玻璃柜中价值不菲的收藏。

Ben Long等人改进了他们之前的超声波2D投影技术。当声波触碰到手时,声波的振动会在皮肤上产生压迫感,因而他们利用一组微型扬声器发射高频声波以产生触摸虚拟物体的感觉。

另外,他们增加一个Leap Motion传感器来追踪手的精确位置。知道了手相对于虚拟物体的位置,系统便可以指导超声波在正确的时间以正确的频率来产生触摸物体不同部分的感觉。

目前,研究者们已经在圆及金字塔等几个形状上做了测试。Long认为,虽然感受虚拟物体的细节受到限制,但不影响人们的整体感受,因为人的大脑会歪曲部分它们的感官以适应整个场景。目前他们已经接洽了几家希望把这项技术发展成商业应用的公司,相信不久的将来人人都可触碰虚无。

图像拼接算法原理 2

版权声明:原创作品,欢迎转载,但转载请以超链接形式注明文章来源(planckscale.info)、作者信息和本声明,否则将追究法律责任。

2. 曲面投影

Homography_Near90Degreee

图6. 近90^{\circ}时产生越来越大的畸变

通常简单的图像拼接技术,就是如上节所示的基本原理,找出一张大概处于中间位置的图像,然后利用单应性变换把其他图像变换到该中心图像的视角下,再做一些后续的曝光补偿、图像融合等处理即可。但是这一技术有相当大的局限性,最简单的例子,不能直接用它拼出360^{\circ}的全景图。

为什么呢?让我们来考虑图6中所示情形。可见,三条光线与P^{\prime}相交的三点,原本是近乎等间距均匀分布的,而当它们映射到P平面上后,间距却产生了巨大的差异。表现在图像上,P^{\prime}上的图像变换到P上后,会产生相当大的拉伸畸变。当图中两相机的投影平面越来越趋于垂直时,这个畸变越来越大,以至于P^{\prime}上普通的一点可能会被映射到P平面的无穷远点。这时,这种简单的单应性拼接方案就彻底崩溃了。

Homography_Warp

图7. 曲面投影解决大视场角下的投影畸变问题

怎样得到更宽视场角下的拼接图?解决方法很简单。以上所出现的这种畸变源自于我们将点投影到一个平面上,设想将P掰弯,或者直接弯曲成一个圆柱面,成为图7所示的样子,那原本被投影到P平面无穷远处的点就被拉回来了。我们在圆柱面上选取一个足够均匀的坐标系,把坐标对应到像素坐标,就可以得到一个全景图了。

当然,针对不同的应用,我们还可以选取不同的投影曲面,比如选取球面用于360^{\circ} * 180^{\circ}的球面全景图,甚至也可以选择一个立方体作为投影曲面。

 

3. 后续处理

至此全景拼接的几何原理就大致说完了,虽然我们还没有给出数学表达。为了先居高临下的了解整个拼接流程,我们不妨把后续处理的梗概也在此一说。

实际应用中为了创建出完美的全景图,有很多的问题需要考虑。最典型的问题有两个,一个是如何解决不同照片中曝光不一致的问题;一个是如何在拼接缝处完美平滑的融合两张图像的问题。

第一个由曝光补偿算法来解决,大体思路是估计两张图间的曝光差异,然后进行补偿。此处不多说。

第二个问题也有众多解决方案,最为著名的大概就属Multi-Band融合算法。该算法虽然八十年代就已提出,但其效果至今仍让人赞叹。在通常图像间失配程度不大的情况下,Multi-Band可以达到肉眼几乎不可分辨的融合效果。其原理也不复杂,下面略微一提。

融合两张图像,最直接的方案是在两张图像的重合区域用一个平滑渐变的权重对二者加权叠加。该方法的效果并不理想,关键原因是我们无法兼顾拼缝附近的局域细节和大尺度上两张图片的宏观特征(如光照)。当我们希望局域细节能够完好拼接时,需要用较小的平滑渐变区;而当我们希望要宏观上平滑过渡时,又想要较大的渐变区域。这二者似乎不可调和。

但事实上并非如此。Multi-Band的成功之处就是在于它同时兼顾两种需求,当融合宏观特征时,采用一个大的平滑渐变区;融合局域细节时,则采用小的平滑渐变区。那如何才能把这两种情况分开处理呢?很简单,把图像分解为不同频带的分量之加和,图像的宏观特征在它的低频分量图里,而局域特征在高频分量图里。

所以,Multi-Band算法的过程大致就是:把图像按照频率高低展开成一个金字塔,然后高低频分量各自按照不同的方式平滑加权并叠加,最后把各频带分量重新加和,得到最终的融合结果。

该算法融合效果虽好,但对于计算量要求较大,它需要创建多座金字塔并对金字塔进行各种运算,图像像素较高时,在CPU上要达到实时基本无望。当然,GPU上情况就不一样了,我们自己就实现了实时的Multi-Band融合算法,效果很好。

 

这一系列文章主要以拼接的几何原理为主。下一节开始用数学建模前两节所述的投影模型。

(未完待续)

才发现OpenVX 1.0发布了

我们的反射弧比较长,今天才刚刚发现此消息。

在预览版在Khronos网站上挂了n个月之后,OpenVX 1.0终于在今年十月份Release了。对于CV界来说,这是一个里程碑式的事件。

摘录一段官方的说明。

”这是个开放、免版税的,用于跨平台计算机视觉应用加速的标准。OpenVX实现了计算机视觉处理中性能和能耗方面的优化,特别是嵌入式和实时应用案例中起到重要作用,例如面部、身体和动作跟踪,智能视频监控,高级驾驶协助系统(ADAS),物体和场景重建,增强现实,视觉检测,机器人学等等。除了OpenVX规范,Khronos还开发了一整套一致性测试和采用者计划,让标准执行者可以测试他们的执行,如果通过一致性测试即可使用OpenVX标识。
Khronos计划在2014年底之前完成第一个开源、完全通过一致性测试的、以CPU为基础的OpenVX 1.0执行。关于完整OpenVX 1.0规范以及关于OpenVX采用者计划的具体信息,请浏览www.khronos.org/openvx。
OpenVX定义了比例如OpenCL™那些计算框架更高水平的执行抽象和内存模型,为在更多架构上的执行创新和高效执行带来重大意义,同时确保这是和以往一致的视觉加速API,完全实现应用可移植性。OpenVX开发者表示一个视觉节点的连接图像,作为执行者,可以执行和通过各种技术进行优化,包括:CPU、GPU、DSP或某些硬件上的加速,节点合并,平铺执行,将已经处理的图像保留在本地内存。
构架方面的灵活性将让OpenVX应用可以在各种系统上优化不同水平的能耗和性能,包括很强的电池敏感度、视觉实现、可穿戴呈现“
 

资料链接:

OpenVX 1.0 Specification

OpenVX主页

多路视频实时全景拼接算法

功能

本算法模块对来自多路摄像机的视频图像进行实时的无缝拼接融合,形成一路具有更宽视角的视频。特别的,可以输出360度全景视频,甚至360度*180度的球面全景。

算法分为两部分,一部分为标定过程,在进行实时拼接前,通过拍摄场景图片,计算各相机的畸变系数和相机之间的变换系数;另一部分为实时拼接过程,利用前面计算出的变换系数对来自各相机的图像进行实时去畸变、拼接,曲面投影,MultiBand融合。

根据用户需要,算法可以将全景图投影到圆柱面、球面等曲面上。

性能
模块基于CUDA实现,使用CUDA显卡完成计算,CPU开销很低。

测试环境:
GTX750Ti,I7 4790k 睿频4GHz,8G DDR3 2400MHz,Win8 64.

六路1920*1080拼接,输出6912*1024:
17fps,CPU总占用率百分之15(包含测试程序中未优化的视频解码、显示等开销)。
四路704*576拼接,输出1824*544;
80fps,CPU总占用率百分之12(包含测试程序中未优化的视频解码、显示等开销)。

适用场景与约束
首先,算法要求各相机间的相对位置、角度在实时拼接过程中保持固定,且相邻相机的视野有一定重合区域。
理论上能够变换到同一视角下进行无缝拼接的场景有两种,一种是多摄像机共中心放置,中心开花状;一种是摄像机位置任意,但场景是一个平面。当场景为远景,且场景-摄像机距离远大于摄像机之间的距离时,也可以近似看做第二种情形。上述情形之外的情况均不可拼,这是一个原则性的限制。

理论上算法对输入视频路数、输出分辨率没有限制,实际应用中这个限制来自于显卡计算能力和显存大小。
由于基于CUDA,所以算法可以扩展到多显卡并行处理(目前仍是单显卡架构),这样就可以实现大规模拼接与融合的处理。

拼接结果可参见我们的Youku主页

应用
本算法可以应用于安防监控、智能交通、卫星照片拼接、虚拟场景等领域。

优势
本模块较同类产品的突出优势是性能,由于基于CUDA显卡计算,模块具有高度的实时处理能力,能保证在简单的单显卡上实现出高分辨率多路视频拼接融合的功能,或者在多显卡计算环境下实现大规模视频/图片拼接融合的任务。
基于CUDA计算的另一个优势是,较FPGA等方案,开发周期更短,易维护且成本低廉。目前Nvidia已经推出基于Tegra的嵌入式开发组件Jetson TK1,本模块可以容易的从PC平台移植到嵌入式平台。