四月 14, 2009
» [DIY] Dominion Travel Box

最近閒來無事就會找朋友玩board game,而Dominion目前是在我的收藏中最好玩也最耐玩的一套(強力推薦!)。dominion最大的特色是有500張卡片,每次遊戲是從25種行動卡中挑10種出來玩,而每次看到不同的行動卡都得擬定不同的策略和牌組來取勝。不同的行動卡有不同功能,遊戲中購買卡片時要仔細思考並互相搭配行動卡組成連續技才能發揮最大效用。除此之外,遊戲的勝利條件是要購買勝利點數,在適當的時機開始買點數並保持自己牌組的平衡也是遊戲的一大挑戰。Dominion的規則超簡單,但卻很耐玩;它耐玩的地方在於每次都只挑其中10種行動卡,所以變化非常多,每次用亂數決定也很難玩到重複的組合。而且隨著玩家經驗的累積,常常會發展出不同的策略和打法,即使是同樣的牌組多玩幾次也有不同樂趣。但有點可惜的是Dominion只能最多4個人玩,人太多就沒辦法玩了。(其實我們有試過5個人玩過,同時修改一下遊戲結束條件也還是很好玩。另外,其實5月Dominion就要推出擴充版了,最多可以同時6個人玩一桌,或是8個人玩兩桌XD)

雖然dominion是純卡片遊戲,但因為它的卡片種類實在太多,每一種卡都要分開來放,所以導致它的盒子非常的大,每次如果要帶出去,就很難再帶其他的board game了..。為了解決這個困擾,我的DIY魂又燃燒了起來,於是最近在玩時都一直碎碎念:「既然買不到小盒子乾脆就自己做吧!」。

我的目標是設計一個可以剛好放進500張卡片的盒子,大小要便於攜帶,而且也要容易把想要的卡片拿出來。google一下後發現也有人做了同樣的事。但我照他的設計圖做了一個prototype後發現他的盒子有點太大了,而且他的圖上沒有畫黏接面,剪好後沒辦法黏起來XD 所以我就依他的設計修改了一下,讓盒子的尺寸能剛好塞進沒上過牌套的500張卡片加上33張分隔卡。以下是我的設計圖:

dominion travel box design

dominion travel box design

盒子主體和蓋子我是拿有點硬度的壁報紙做,但我後來覺得應該要拿更厚更硬的紙板才會夠堅固。盒子的角落會有4個70×70的正方形,我把其中兩個對半剪開加上雙面膠拿來固定四個角落。盒子完成後,蓋子也是如法炮製,只是尺寸稍大一點而已。我做完後發現上蓋的長寬可以再小一點,其實應該比主體各多2mm就足夠了。但我已經懶得再做第三次,就留給有心人去試吧。

分隔卡總共要33張,包括25張行動卡、3張錢幣卡、3張勝利點數、1張詛咒卡、1張place holder。我用上面那個連結裡的設計圖,把他的每張分隔卡上半部剪下來,自己貼在70×90的紙板上,重複33次就完成了..。(手工藝真是很累orz)

成品與原盒的比較。 From [DIY] Dominion Travel Box
33張分隔卡。 From [DIY] Dominion Travel Box
把卡片全部放進去的完成品。 From [DIY] Dominion Travel Box

四月 18, 2008
» HOWTO: 在Macbook上DIY窮人的multi-touch (Part 3 - END)

這篇文章將接續這個系列Part 1Part 2的說明向大家說明multi-touch背後軟體運作的原理。這篇文章會盡量用簡單的方式說明原理和實做,希望能讓懂得基本程式設計的讀者都能看懂。

這篇文章會說明怎麼從攝影機中擷取圖片,並取得手指所反射出的光點位置,並對每個點做追蹤。下圖是同時追蹤四個手指的範例:

在上一篇已經介紹過我們所需要的硬體,包括紅外線投射燈、紅外線攝影機、及反光貼片。這些硬體很重要的功能是讓我們雙手的手指頭能反射大量紅外線,透過紅外線濾光片的協助,我們的攝影機(iSight)就只會看到手指頭產生的亮點,而不會看到其餘和手指無關的背景。

上圖為我們的攝影機所看到的畫面,畫面中除了手指上兩塊方形反光貼片外,其它什麼都看不到。這樣子的畫面,對於電腦來說遠比一般含有整個手掌、人、背景等圖片還來得容易處理,而我們用紅外線來替代原本的可見光的用意就在這裡。

接下來,我們將開始解說怎麼利用這些影像來取得手指的位置,進而追蹤每隻手指的移動過程。我們將利用C++寫個程式出來分析這些影像,並將結果變成上層應用程式可以接受的event。整個程式需要做的事,簡單說來可以分為以下這些步驟:

  1. 從攝影機擷取影像
  2. 從影像中找出每個亮點中心的位置
  3. 對於之後擷取到的每張畫面追蹤每個亮點位置的變化
  4. 產生對應的event,發送給上層的應用程式做處理

從攝影機擷取影像

在這邊我推薦用Intel的OpenCV來做處理。OpenCV是非常有名的電腦視覺函式庫,提供了一大票的電腦視覺及影像處理相關函式,甚至連從攝影機擷取影像都能幫你解決。OpenCV還有個好處是它是跨平台的函式庫,在各大平台都能運作,所以我們接下來寫的程式除了在Mac上外,也能在Linux及Windows上運作。

要開始找出亮點位置前,我先簡單交代一下怎麼用OpenCV從攝影機擷取影像出來(以下程式碼都用C++填寫)。

  1.  
  2. #include <cv.h>
  3. #include <highgui.h>
  4.  
  5. int main(int argc, char** argv)
  6. {
  7.    CvCapture* capture;
  8.    IplImage *img;
  9.    capture = cvCaptureFromCAM(0);
  10.    cvNamedWindow("mainWin", CV_WINDOW_AUTOSIZE);
  11.    cvMoveWindow("mainWin", 0, 100);
  12.    while(cvGrabFrame(capture)){
  13.       img=cvRetrieveFrame(capture);
  14.       // process img here …
  15.       cvShowImage("mainWin", img);
  16.       int key=cvWaitKey(10);
  17.       if(key == 27) // 27=ESC
  18.          break;
  19.    }
  20.  
  21.    cvReleaseCapture(&capture);
  22.    return 0;
  23. }
  24.  

上面是OpenCV從攝影機擷取影像並畫在一個視窗內最基本的程式碼,我們之後對於影像所有的處理都插在第14行那裡就可以了。

偵測亮點位置

觀察我們取得的影像可以發現,我們要找的亮點是實心的方形,且沒有特定顏色和圖樣。所以要找出這些亮點中心的位置其實很簡單。第一步,我們可以先去除顏色,將全彩(RGB 24bits)轉為只有兩種顏色(黑白)的影像。而剩下來白色的部份就是我們感興趣的區塊。

在OpenCV中,我們需要先將含有3個channel (RGB)的輸入轉為單一channel的灰階圖。灰階圖的意義是它只包含了亮度的資訊,最亮的地方會是白色(255),最暗就是黑色(0)。得到灰階圖後,我們就可以設定一個threshold,將一定亮度以上的pixel全變成白色,剩餘的地方全設成黑色。透過這樣子得到的圖片將只剩下黑白兩色,對於我們之後的處理會簡單很多。這部份的程式碼很簡單,我把它寫成了一個稱為convertToBinary的函式,其中設定threshold為40,也就是說值超過40的pixel都會變成255,剩餘都變0。

  1.  
  2. #define BINARY_THRESHOLD 40
  3.  
  4. IplImage* convertToBinary(IplImage *in, IplImage *out){
  5.    cvCvtColor(in, out, CV_BGR2GRAY);
  6.    cvThreshold(out, out, BINARY_THRESHOLD, 255, CV_THRESH_BINARY);
  7. }
  8.  

處理後如下面兩張圖所示,左邊為灰階,右邊為黑白兩色。

下一步我們要掃描整個畫面,找到這些白色區塊的位置和形狀,接著就能計算出中心位置。OpenCV提供了一個函式稱為cvFindContours,這個函式能在畫面中找到白色區塊的輪廓(contour)。有了輪廓後,就能透過cvBoundingRect找到這個輪廓的bounding box,也就是我們所要的白色區塊位置。

下面的函式findBlobs需要一個只含黑白兩色的圖作為輸入,它可以找出圖中所有白色區塊的位置,但目前還不會輸出任何東西。找出輪廓後,可以用14~18行的程式碼把輪廓和bounding box畫在debug_img上。(通常我們會開另一個視窗專門畫這種debug用的畫面)

  1.  
  2. void findBlobs(IplImage *bin_img, IplImage *debug_img){
  3.    static CvMemStorage *storage = cvCreateMemStorage(0);
  4.    CvSeq * contour;
  5.      
  6.    cvFindContours( bin_img, storage, &contour, sizeof(CvContour),
  7.        CV_RETR_CCOMP, CV_CHAIN_APPROX_NONE);
  8.      
  9.    for(; contour; contour = contour->h_next){
  10.       CvRect rect = cvBoundingRect(contour, 1);
  11.       CvPoint pt1 = cvPoint(rect.x, rect.y),
  12.               pt2 = cvPoint(rect.x+rect.width, rect.y+rect.height);
  13.       // The center of rect is (rect.x+rect.width/2, rect.y+rect.height/2)
  14.       if(debug_img){
  15.          cvRectangle(debug_img, pt1, pt2, CV_RGB(255,0,0),2);
  16.          cvDrawContours(debug_img, contour,
  17.             CV_RGB(255,0,0), CV_RGB(255, 0, 0), 0, 2, 8);
  18.       }
  19.  
  20.    }
  21. }
  22.  

下面兩張圖即是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問題來解。但在這篇以簡單易懂為前提的教學中,我們還是用簡單的方法吧。我的配對方法如下:

  1. 假設前一個frame的所有光點集合為A,目前frame的則為B
  2. 對於A中的所有點a,計算出到B中所有點b的edge長度,並放進一個陣列E中
  3. 把陣列E中距離太遠的edge剔除掉
  4. 將E按edge長度排序,從小排到大
  5. 從E的開頭開始,每取出一條edge前先看看edge的兩端點是否已經配對成功過,若兩端沒有則標記兩端點為同一光點
  6. 重複上一步直到取出所有edge為止

跑完上面的演算法,我們就可以標記出兩個frame中所有對應的光點,並且可以產生出對應的FINGER_MOVE event。而A和B中剩下來沒被配對到的點,就代表這些點只存在其中一個frame,要不是剛消失就是剛出現,所以我們就能把它們分別對應到FINGER_UP及FINGER_DOWN event。

採用這個簡單的策略,就能很快解決這個配對問題,還能順便產生出對應的event出來。詳細的程式碼太長就不列在這邊,有興趣的可以看下載整個原始碼回去看BlobTracker.cpp。

與multi-touch應用程式的結合

到此我們已經能順利辨識並追蹤畫面上的多個光點,並產生出上層應用程式所需的event。但要怎麼把這些event送出去呢?這部份目前仍是一片迷霧,因為主流作業系統都還不支援multi-touch API。在缺乏有力的標準下,目前許多multi-touch應用程式是使用TUIO protocol。但我比較想直接和作業系統結合,所以我還在研究這部份要怎麼解決。

下載

這篇文章所用的完整原始碼:BlobTracker (有人需要執行檔嗎?)
基本上在各個平台只要有g++和opencv,打make就能編譯完成。
在Mac OS X下需要另外安裝xcode和opencv。opencv可以用darwin ports安裝。

相關討論

這篇文章所敘述的演算法並不是完美的,已知有下列問題:

  • 當兩個光點相黏在一起時會變成一個。這是因為我們直接找connected component的輪廓當作光點的關係,比較好的作法進一步是比對光點的形狀。
  • 光點追蹤的演算法算出來的配對不是全域最佳解。改用CAMSHIFT可能(?)會比較好。

FAQ

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。

四月 16, 2008
» HOWTO: 在Macbook上DIY窮人的multi-touch (Part 2)

接續Part 1的說明,這次要解說如何自己製作必要的硬體設備,包括紅外線LED、紅外線攝影機、以及紅外線反射貼片。

紅外線LED(Infrared LED, 簡稱為IR 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程式,這樣就能當作一種虛擬手寫板來玩了 :-D

有了IR-pass filter後,我們就能把它放到紅外線投射燈中間,最後再把整個投射燈架到iSight前面,就完成了紅外線的發射+接收裝置。

紅外線反射貼片

最後要做的一個小東西是可以黏在手指上,加強紅外線反射的反光貼片。有了這種貼片後,手指在紅外線攝影機前就會變成特別亮的一個光點,這樣我們後續要做光點追蹤就容易多了。

我在家裡附近的什麼都有賣的五金雜貨店(X北百貨)搜刮了四種反光片及反光膠帶,分別測試過後找到一種效果還蠻好的「安全反光帶」(就是交通警察身上都會有的那種螢光色反光帶)。

我把這個反光帶剪成幾塊小片,用雙面膠貼在手指上,就能得到不錯的效果。請見下面的video:

到此我們已經完成了所有必要的硬體配備,總成本不超過NT$ 750。總共有下列配備:

  • 紅外線攝影機: 內建的iSight + 自製IR-pass filter NT$ 32
  • 紅外線LED發射器(外加一些小零件,銅柱、電池、銅線..) NT$ 6xx
  • 反光貼片 NT$30

硬體部份到此就能全部完成,最麻煩的其實是自製紅外線燈,但不想自己焊的多花點錢也是能買到現成的來用。剩下的IR-pass filter和反光貼片只要去文具店買,拿回來剪剪貼貼就能完成了。很簡單吧 :-D

下一篇將會介紹軟體的部份。軟體是最複雜的地方,可能要等我下次放假才能完成了。

四月 15, 2008
» HOWTO: 在Macbook上DIY窮人的multi-touch (Part 1)

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需要下列材料:

  1. 紅外線LED x N
  2. 紅外線攝影機 x 1
  3. 一塊壓克力板, 或是可以貼在手指上的反射片
  4. 光點追蹤軟體或硬體

目標

整個project最後目標是能接到Mac OS X底層的API,讓這個DIY裝置的輸出直接變成OS X能接受的event。後來研究一下才發現,Apple根本就還沒公佈什麼multi-touch API,雖然我猜已經有未公開的API了,但我不知道怎麼查,如果有人知道請告訴我,我會非常感激你的 :-D

因為我想在Macbook上做到multi-touch control,又不想破壞我的愛機,所以只好採用非接觸式的控制方式,也就是像Johnny Lee那樣在空中揮動手指就能感應。

我上個星期趁放假花了三天,已經完成了第一階段的prototype,證實這個idea是真的能運作的。
有圖有真相:

這篇先寫到這,下一篇將開始介紹硬體部份的製作。

biggo.com.tw

A Django site.