这篇文章将接续这个系列Part 1及Part 2的说明向大家说明multi-touch背后软体运作的原理。这篇文章会尽量用简单的方式说明原理和实做，希望能让懂得基本程式设计的读者都能看懂。
这篇文章会说明怎么从摄影机中撷取图片，并取得手指所反射出的光点位置，并对每个点做追踪。下图是同时追踪四个手指的范例：
在上一篇已经介绍过我们所需要的硬体，包括红外线投射灯、红外线摄影机、及反光贴片。这些硬体很重要的功能是让我们双手的手指头能反射大量红外线，透过红外线滤光片的协助，我们的摄影机(iSight)就只会看到手指头产生的亮点，而不会看到其余和手指无关的背景。
上图为我们的摄影机所看到的画面，画面中除了手指上两块方形反光贴片外，其它什么都看不到。这样子的画面，对于电脑来说远比一般含有整个手掌、人、背景等图片还来得容易处理，而我们用红外线来替代原本的可见光的用意就在这里。
接下来，我们将开始解说怎么利用这些影像来取得手指的位置，进而追踪每只手指的移动过程。我们将利用C++写个程式出来分析这些影像，并将结果变成上层应用程式可以接受的event。整个程式需要做的事，简单说来可以分为以下这些步骤：
从摄影机撷取影像从影像中找出每个亮点中心的位置对于之后撷取到的每张画面追踪每个亮点位置的变化产生对应的event，发送给上层的应用程式做处理在这边我推荐用Intel的OpenCV来做处理。OpenCV是非常有名的电脑视觉函式库，提供了一大票的电脑视觉及影像处理相关函式，甚至连从摄影机撷取影像都能帮你解决。OpenCV还有个好处是它是跨平台的函式库，在各大平台都能运作，所以我们接下来写的程式除了在Mac上外，也能在Linux及Windows上运作。
要开始找出亮点位置前，我先简单交代一下怎么用OpenCV从摄影机撷取影像出来(以下程式码都用C++填写)。
#include <cv.h> #include <highgui.h> int main ( int argc, char** argv ) { CvCapture* capture; IplImage *img; capture = cvCaptureFromCAM ( 0 ); cvNamedWindow ( "mainWin", CV_WINDOW_AUTOSIZE ); cvMoveWindow ( "mainWin", 0, 100 ); while (cvGrabFrame (capture ) ) { img=cvRetrieveFrame (capture ); // process img here … cvShowImage ( "mainWin", img ); int key=cvWaitKey ( 10 ); if (key == 27 ) // 27=ESC break; } cvReleaseCapture (&capture ); return 0; }上面是OpenCV从摄影机撷取影像并画在一个视窗内最基本的程式码，我们之后对于影像所有的处理都插在第14行那里就可以了。
观察我们取得的影像可以发现，我们要找的亮点是实心的方形，且没有特定颜色和图样。所以要找出这些亮点中心的位置其实很简单。第一步，我们可以先去除颜色，将全彩(RGB 24bits)转为只有两种颜色（黑白）的影像。而剩下来白色的部份就是我们感兴趣的区块。
在OpenCV中，我们需要先将含有3个channel (RGB)的输入转为单一channel的灰阶图。灰阶图的意义是它只包含了亮度的资讯，最亮的地方会是白色(255)，最暗就是黑色(0)。得到灰阶图后，我们就可以设定一个threshold，将一定亮度以上的pixel全变成白色，剩余的地方全设成黑色。透过这样子得到的图片将只剩下黑白两色，对于我们之后的处理会简单很多。这部份的程式码很简单，我把它写成了一个称为convertToBinary的函式，其中设定threshold为40，也就是说值超过40的pixel都会变成255，剩余都变0。
#define BINARY_THRESHOLD 40 IplImage* convertToBinary (IplImage *in, IplImage *out ) { cvCvtColor (in, out, CV_BGR2GRAY ); cvThreshold (out, out, BINARY_THRESHOLD, 255, CV_THRESH_BINARY ); }处理后如下面两张图所示，左边为灰阶，右边为黑白两色。
下一步我们要扫描整个画面，找到这些白色区块的位置和形状，接着就能计算出中心位置。OpenCV提供了一个函式称为cvFindContours，这个函式能在画面中找到白色区块的轮廓(contour)。有了轮廓后，就能透过cvBoundingRect找到这个轮廓的bounding box，也就是我们所要的白色区块位置。
下面的函式findBlobs需要一个只含黑白两色的图作为输入，它可以找出图中所有白色区块的位置，但目前还不会输出任何东西。找出轮廓后，可以用14~18行的程式码把轮廓和bounding box画在debug_img上。（通常我们会开另一个视窗专门画这种debug用的画面）
void findBlobs (IplImage *bin_img, IplImage *debug_img ) { static CvMemStorage *storage = cvCreateMemStorage ( 0 ); CvSeq * contour; cvFindContours ( bin_img, storage, &contour, sizeof (CvContour ), CV_RETR_CCOMP, CV_CHAIN_APPROX_NONE ); for (; contour; contour = contour->h_next ) { CvRect rect = cvBoundingRect (contour, 1 ); CvPoint pt1 = cvPoint (rect. x, rect. y ), pt2 = cvPoint (rect. x+rect. width, rect. y+rect. height ); // The center of rect is (rect.x+rect.width/2, rect.y+rect.height/2) if (debug_img ) { cvRectangle (debug_img, pt1, pt2, CV_RGB ( 255, 0, 0 ), 2 ); cvDrawContours (debug_img, contour, CV_RGB ( 255, 0, 0 ), CV_RGB ( 255, 0, 0 ), 0, 2, 8 ); } } }下面两张图即是OpenCV找到的轮廓和bounding box。
经过上面两个函式的处理，我们已经能在摄影机撷取出的每个frame标定出光点的位置。但我们要做的可是multi-touch的介面，也就是说每个frame会有不定个数的亮点，可能只有1个，也可能有2个，甚至有10个。我们必须持续追踪这些亮点的变化，包括每个点是什么时候出现、中间移动的轨迹、以及什么时候消失的。在OpenCV中有提供现成的tracker CAMSHIFT，但它实在太复杂，我还没有时间把它搞懂，所以我决定自己写一个简易版的tracker。（所谓的简易版就是没那么完美，可是大部分情况是work的）
如果我们的tracker只面对一个点，那么问题很简单。在下图中，圆形为前一个frame光点的位置，方形为目前这个frame的位置。在单一个点的情况，可以直接断定圆形和方形是同一个光点，并且移动路径是A。
但如果是多点，情况就没这么单纯了。下图展示了两个点的情况，我们要怎么判断两个光点是走了路径A或路径B呢？也就是说这两个方形，到底谁是光点1？谁是光点2？
其实上图还有更复杂的可能，像是光点2其实已经消失，而某个方形是新出现的光点3。在每个光点都是相同的情况下，其实我们是没办法区别这种奇怪的可能性，所以为了简化我们先暂时忽略这种可能。在这个问题上，我用一个简单的策略来解决：在两个frame间，相对位移距离越短就越可能是相同的一个点。也就是说在上图中，上方的方形应该是点1，下方是点2，因为这样子两个点移动的距离都比较短。
这个问题如果要求全域的最佳解（让每个点移动的距离和最短），可以转化成图论中的Bipartite matching问题来解。但在这篇以简单易懂为前提的教学中，我们还是用简单的方法吧。我的配对方法如下：
假设前一个frame的所有光点集合为A，目前frame的则为B对于A中的所有点a，计算出到B中所有点b的edge长度，并放进一个阵列E中把阵列E中距离太远的edge剔除掉将E按edge长度排序，从小排到大从E的开头开始，每取出一条edge前先看看edge的两端点是否已经配对成功过，若两端没有则标记两端点为同一光点重复上一步直到取出所有edge为止跑完上面的演算法，我们就可以标记出两个frame中所有对应的光点，并且可以产生出对应的FINGER_MOVE event。而A和B中剩下来没被配对到的点，就代表这些点只存在其中一个frame，要不是刚消失就是刚出现，所以我们就能把它们分别对应到FINGER_UP及FINGER_DOWN event。
採用这个简单的策略，就能很快解决这个配对问题，还能顺便产生出对应的event出来。详细的程式码太长就不列在这边，有兴趣的可以看下载整个原始码回去看BlobTracker.cpp。
到此我们已经能顺利辨识并追踪画面上的多个光点，并产生出上层应用程式所需的event。但要怎么把这些event送出去呢？这部份目前仍是一片迷雾，因为主流作业系统都还不支援multi-touch API。在缺乏有力的标准下，目前许多multi-touch应用程式是使用TUIO protocol。但我比较想直接和作业系统结合，所以我还在研究这部份要怎么解决。
这篇文章所用的完整原始码：BlobTracker (有人需要执行档吗？） 2008-07-27更新: 释出支援TUIO的BlobTracker(这个版本需要oscpack，我已经附在里面，但注意非OS X平台必须自己重新make过oscpack内的lib。)基本上在各个平台只要有g++和opencv，打make就能编译完成。在Mac OS X下需要另外安装xcode和opencv。opencv可以用darwin ports安装。
这篇文章所叙述的演算法并不是完美的，已知有下列问题：
当两个光点相黏在一起时会变成一个。这是因为我们直接找connected component的轮廓当作光点的关系，比较好的作法进一步是比对光点的形状。光点追踪的演算法算出来的配对不是全域最佳解。改用CAMSHIFT可能(?)会比较好。Q: 这三篇文章介绍的东西能在Macbook以外的notebook上用吗？ A: 当然可以。硬体跟作业系统无关，软体是跨平台的，只要有OpenCV就能跑。唯一要注意的是有的摄影机内建了IR-block filter，会把红外线挡掉，碰到这种就不能用了。实验方法是随便拿个遥控器对着摄影机按，看会不会发光就知道了。
Q: 这样做出来的multi-touch能操作Mac里支援multi-touch的程式吗？ A: 目前还不可以。因为我不知道怎么伪装成OS X的multi-touch event长什么样，也不知道怎么塞到OS的event queue中。说不定Mac OS X根本就还没有multi-touch event这种东西。
Q: 那做出来的东西可以干么？ A: 只要把我自订的event转成TUIO message送出，就可以驱动所有支援TUIO的multi-touch应用程式。但如果没写这段，就…….只能给自己娱乐用。
Q: 之后会释出支援TUIO的程式吗？ A: 如果我没研究出来怎么送Mac OS X的event应该就会改用TUIO。A: 已经释出。(2008-07-27更新)
Posted in Uncategorized | 22 Comments »
接续Part 1的说明，这次要解说如何自己制作必要的硬体设备，包括红外线LED、红外线摄影机、以及红外线反射贴片。
红外线LED可以在电子材料行轻易买到，一颗约NT$ 5~8元。如果会基本的电路制作，说穿了就只是买一大堆LED，插在一块板子上，然后接上一个电阻和电池就行了。虽然很简单，但我不建议这么做。因为太费工了，我实验过要取得够好的效果，至少要用上50颗LED，才能勉强让使用者的手直接从键盘上拿起来就能控制。我不想花那么多时间慢慢焊50颗LED，所以决定买现成的红外线LED灯来用。
所谓现成的红外线LED灯，其实就是现在很多支援夜视功能的监视器上所用的红外线投射器。
红外线监视器的原理其实就是在夜晚时，利用镜头旁边装设的这一圈红外线LED发出的红外线光来取代白天的可见光作为照明。而监视器用的这一圈红外线LED刚好就非常符合我们的需求：中间有个洞能放镜头，旁边有48颗红外线LED。我在台中的电子街买到这东西，大约要NT$ 6xx元。（如果自己做同样的东西只需要一半的价钱，可见这东西多好赚）
这个LED灯背后有个小插座，只要接上12V的电就能运作。要特别注意的是这种给监视器用的灯，都附有一个光敏开关（上图正面右下角那一个特别突出的圆柱），这个开关是用来侦测环境的光源亮度，如果天黑了就会启动红外线照明。因为我们需要它一直开着，所以就拿个不透明胶带把这个开关贴起来骗它现在是晚上就行了。
我另外在电子材料行买了两个加长型的塑胶铜柱（就是把电脑主机板固定在机壳上的铜柱），可以锁在这个红外线投射器上，以方便固定在Macbook的镜头上。组合时稍微把铜柱的前端用刀片削一下，会比较好插进去旋转。最后组合起来会像这样：
完成后就能直接把这个LED灯放到Macbook的镜头上了：
Macbook内建的iSight摄影机其实本来就能看到红外线，最简单的实验方法是打开Photo Booth，然后拿出Macbook附赠的小遥控器（长得很像旧款iPod Shuffle的那个遥控器），对着iSight按一按，你就能看到遥控器里有一闪一闪的亮光。这个亮光就是从遥控器内的红外线LED发出，直接用肉眼是看不见的。
虽然iSight看得到红外线，但有个严重的问题是它也看得到可见光。参考上图的光谱，我们可以知道红外线的波长比可见光还长，而iSight的可视范围就是从可见光区一直往上延伸到红外线区。如果我们想让iSight只能看到红外线的话，就需要另外加上一片只让红外线通过的滤光片（IR-pass filter)。这个滤光片价钱不便宜，而且不容易买到，但还好我们能用很简单的方法自己做一个，成本只要NT$ 32元就能搞定。
只要到书局买像上图这种有色的透明包装纸，一个蓝的，一个红的就行了。这种有色的透明包装纸其实就是最简单的滤光片，对人来说，红色就是只能透过红光，而蓝色就只能透过蓝光。但事实上这两种包装纸都还能让红外线穿透，也就是说我们只要把两种颜色的包装纸叠起来，就能把可见光全部滤掉，只让红外线通过。
我试了几种排列组合，最后决定用一片红色加两片蓝色。接着把它们用胶带黏在一起，就能得到一片简易的IR-pass filter。完成后可以直接用胶带贴在iSight的镜头前，这样原本的iSight就摇身一变成为只能看到红外线的摄影机了。
下面是一个简单的demo影片，我直接拿一颗IR LED接上一颗AAA电池在镜头前晃来晃去，搭配我自己写的blob tracking程式，这样就能当作一种虚拟手写板来玩了
有了IR-pass filter后，我们就能把它放到红外线投射灯中间，最后再把整个投射灯架到iSight前面，就完成了红外线的发射+接收装置。
最后要做的一个小东西是可以黏在手指上，加强红外线反射的反光贴片。有了这种贴片后，手指在红外线摄影机前就会变成特别亮的一个光点，这样我们后续要做光点追踪就容易多了。
我在家里附近的什么都有卖的五金杂货店（X北百货）搜刮了四种反光片及反光胶带，分别测试过后找到一种效果还蛮好的「安全反光带」（就是交通警察身上都会有的那种萤光色反光带）。
我把这个反光带剪成几块小片，用双面胶贴在手指上，就能得到不错的效果。请见下面的video：
到此我们已经完成了所有必要的硬体配备，总成本不超过NT$ 750。总共有下列配备：
红外线摄影机: 内建的iSight + 自制IR-pass filter NT$ 32红外线LED发射器(外加一些小零件，铜柱、电池、铜线..) NT$ 6xx反光贴片 NT$30硬体部份到此就能全部完成，最麻烦的其实是自制红外线灯，但不想自己焊的多花点钱也是能买到现成的来用。剩下的IR-pass filter和反光贴片只要去文具店买，拿回来剪剪贴贴就能完成了。很简单吧
下一篇将会介绍软体的部份。软体是最复杂的地方，可能要等我下次放假才能完成了。
Posted in Uncategorized | 15 Comments »
Apple虽然已经把multi-touch扩展到iPhone以外的Macbook Air和Macbook Pro，可是唯独Macbook还是没有multi-touch trackpad能用。在看了前阵子CMU HCII的PhD学生Johnny Lee利用Wiimote做了个multi-touch demo后，就让我兴起在自己的Macbook上也搞一个来玩的念头。这整个过程我会发表在这blog上，让有兴趣的人可以参考。
multi-touch的实做方法很多，最简单的一种称为 FTIR (Frustrated Total Internal Reflection)。FTIR是在压克力面板内打入红外线，当手指按上去时会产生反射，接着在面板后用一个红外线摄影机去追踪这些因为反射而亮起来的地方。
在Johnny Lee的Wiimote demo中，其实也是用了相同的概念。他用自制的红外线LED灯(注意看影片，上面可是有100颗LED…)往user的方向照，而红外线碰到手指会反射回去（他在手指上贴了反射片，能拉大手指和身体其他部位反射的差距），最后再利用Wiimote内建的红外线摄影机来做tracking。这里要特别说明的是，Wiimote非常神奇的内建了硬体的光点追踪(blob tracking)，最多可以支援到四个光点，而Johnny Lee就是利用了这个内建功能轻易的完成了multi-touch控制器（严格说起来没有”touch”，应该叫做multi-point才对）。
根据以上的说明，我们可以知道要自己DIY一个最简单的multi-touch device需要下列材料：
红外线LED x N红外线摄影机 x 1一块压克力板, 或是可以贴在手指上的反射片光点追踪软体或硬体整个project最后目标是能接到Mac OS X底层的API，让这个DIY装置的输出直接变成OS X能接受的event。后来研究一下才发现，Apple根本就还没公佈什么multi-touch API，虽然我猜已经有未公开的API了，但我不知道怎么查，如果有人知道请告诉我，我会非常感激你的
因为我想在Macbook上做到multi-touch control，又不想破坏我的爱机，所以只好採用非接触式的控制方式，也就是像Johnny Lee那样在空中挥动手指就能感应。
我上个星期趁放假花了三天，已经完成了第一阶段的prototype，证实这个idea是真的能运作的。有图有真相：
这篇先写到这，下一篇将开始介绍硬体部份的制作。
