December 29, 2012

Robotic Plotter Arm

I was required in my school work to design and implement an embedded system. I thought it would be great to make something robotic. I recalled the movie Hugo. I was impressed and later fascinated by the automaton appeared in the movie. I decided to make one with similar functionality by modern robotics.
I quickly designed the mechanical structure of the robotic arm. It is really standard practices from what I saw on the internet. I got some help in hammering the aluminium plates. Then I embedded 3 servo motors in the joints.


We do embedded C on STM32. The only hardware interfacing was the 3 PWM outputs controlling each motor. I did struggle for some time in producing a signal with the correct frequency and pulse width, and to varies the pulse width smoothly at a desired speed.

Luckily the control algorithm is not hard.

In order to design the desired Hugo's drawing, I scratched up a simple vector graphics editor. The editor can export a vector design into a format accepted by the embedded program.
The designer is where magic happens. I traced the Hugo's automaton's drawing, though dropped a lot of lines for fear that the robotic arm cannot be that accurate.


Finally it gave me this drawing.

Compare with the drawing by Hugo's automaton.

It took smaller amount of time and effort than I had expected to finish this arm. That's 10 days of spare time and 3 days of full time.
There is indeed much room for improvement of accuracy. But then I am satisfied by how pieces of hardware and software work together to create the artistic outcome.



Appendix I - photo album
sample sketches produced by the arm
making of

Appendix II - presentation slides


Appendix III - demonstration video


Appendix VI - source code
https://github.com/tyt2y3/plotterarm

September 13, 2012

中文輸入法概論

前言

中文輸入法五花八門,各有各其標榜易學,快速。究竟輸入法之間有何大同小異? 我們可以用一套定量的理論去評定輸入法的優劣嗎? 本文分別以 組合數學,分類學 及 附加功能,以工程學角度論述之。

組合數學 Combinatorics

從功能上來說,中文輸入法就是 "輸入一個碼,輸出一個字元" 的一個過程。
從組合數學上來說,中文輸入法 就是一個 將對應到中文字元的函數。
A function Q mapping keys K to characters C.
而一個碼是由不同的r 串列而成。A key k is a sequence of elements from roots R.
而C, K, R 分別是字元c, 碼k, 根r的 集。
where .
為令大家容易理解,以倉頡為例,
字元c=你, 碼k=人弓火, 根r=(人,弓,火)
建立了數學基礎,我們就可以探討C, K, R的特性。

字元集C

以Big 5大五碼為例,共收錄13,060個常用中文字。加上特殊字,中文字字元可以有8萬多個。輸入法最少要收錄5000字才夠日常使用。

碼表K

可用碼數取決於 根的數目n 及 碼的長度l。
 where n is the number of roots and l is length f a key.
這裏,我指的碼表包含所有可用的碼,包括不指向任何字元的碼。
倉頡為例,字母(根)有24個,最短為一碼最長為五碼,所以可用碼數是,八百多萬,足夠覆蓋所有中文字。
九方字型為例,每個位置的碼有九個根,碼的長度是3,尾碼可選"確定"(0),所以可用碼數是9*9*10=810,十分少。
可以見到,可用碼數決定了"重碼"的問題:
倉頡中,幾乎每個字的碼都是獨特的(unique), almost a one-to-one function.
九方字型中,一個碼可指向多個字元, one-to-many.
所有拼音輸入法都有同音字的問題,以國語最為嚴重。
而一個碼可否指向多個字元,決定了輸入法是否需要選字,決定了輸入的速度。(一個碼有30個字元可選,一定要慢吧)

重碼商數

是用來描述打一個字時,受重碼影響而產生的延遲。
重碼率 是出現選字情況的機會率,而平均重碼字元數 則假設選字延遲可選字數成線性關係。
選字延遲系數 = 重碼率 * 平均重碼字元數
 = (重碼數 / 使用碼數) * (重碼字元總數 / 重碼數 )
 = 重碼字元總數 / 使用碼數
 = (字元總數 - 使用碼數) / 使用碼數
 = (字元總數 / 使用碼數) - 1
 = 重碼商數 - 1
這個商數給我們的結論是,若輸入法都有大小相同的字庫,則使用碼數越多,總體的選字延遲越少。

字元
1
子, 丑
2
寅, 卯
3
辰, 巳
4
午, 未
5
申, 酉
6
7
...
(一個字元)
10
(一個字元)
重碼商數 = 15/10 = 1.5

字元
1
子, 丑, 寅, 卯, 辰, 巳, 午, 未, 申, 酉
2
3
...
(一個字元)
6
(一個字元)
重碼商數 = 15/6 = 2.5

根的數目n

根的數目越多,輸入法越難學。手機的五筆連傻仔都識,倉頡卻不是人人都懂。
在手機只有十粒按鍵的年代裏,根的數目多於十只會製造更多麻煩。即使用輕觸式屏幕手機,按鍵的面積太細亦會提高錯按率。(若果為求準確而使用觸控筆,又會失去雙手打字的優勢)。
根數不足又會提高重碼數。
由此可見,根的數目是需要巧妙平衡的工程參數。
為了使輸入法更易學習,採用位置相關的編碼方式是有幫助的。例如拼音輸入法,第一碼是較少數的聲母。九方字型 第一碼及第二碼用兩組不同的根,是很聰明的做法。

碼的長度l

碼越長,輸入越慢。
碼的長度每加一,可以提升可用碼數一個次方,因此是補足根的數目的重要參數。

分類學 Classification

輸入法中的分類學,俗稱拆碼,是指 以貼近人類的概念,配合拆碼規則,建立分類樹,將每個字元在放到樹上一個位置。
中文作為一種語言的特性,使我們有了多樣的分類法則。傳統字典提供一種歷史悠久的分類法則(部首,筆劃,劃數),而輸入法都會自創一套。分類法則的 簡潔,模糊(撞到衝突的處理方式) 等定性因素亦很大程度決定了輸入法是否 易記,易學。

以語分類,即是拼音。是人類為方言建立拼音系統後,最自然的分類方法。國語,廣東話,普通話,及上海話 都可以有一種輸入法。普通話有21個聲母,37個韻母,4個聲調。相較之下,9聲的廣東話同音字比較少。
最寶貴的特性是,盲人也可以學懂。

以視覺特性將字分類。
分類樹的第一層一般都會運用 人類直覺上的 分割技巧(partitioning)。
倉頡分九種字型,九方字型只有三種。
第二層或以上的拆碼法則,每種輸入法都大不同,因此不能詳述。

分類樹

1) 碼的長度等同樹的層數,而分枝數目等同碼根的數目。兩個參數影響了樹的形態。
2) 分枝平衡。如果某一分枝特別"繁盛"的話,其實代表分類能力不足。例如,以漢字造字六書作分類的話,形聲就比其他分枝(如會意)粗很多。這時,就需要增加層數 或 增加底層葉的數量。
3) 拆碼上較簡單的字元可以用較短的碼。除九方外,很多輸入法的碼都不是劃一長度的。

附加功能

輸入法常見的附加功能包括 動態選字,頻率統計,關聯字,使用者偏好等。
動態選字,是指每打出一個碼根,輸入程式都會更新 字元選擇,逐步收窄搜尋範圍,直到使用者打出完整的碼為止。對手機五筆這種 有十分長的碼 的輸入法來說,這個功能是 維持一定輸入速度的關鍵。
當 字元選擇 超過一頁,就有必要為字元排序。一般做法是分析大量文章,統計每個字的出現頻率 作為排序參數。
關聯字,包括近音字,上下聯詞,成語,甚麼甚麼都有。是推廣部最愛的宣傳功能。
使用者偏好,則是跟據 使用者的使用習慣,改變排序,詞庫等。

認知科學

熟能生巧,其實使用任何一種輸入法久了,就會建立反射弧,無需再思考如何拆碼,心想哪個字,手就會打出來。
從這一角度去看,其實輸入法只是一種訓練反射弧的方法而已。的確,是有些人能靠背unicode編碼打中文的。
可惜,所有附加功能都是 訓練反射弧的障礙。動態選字 令你不能盲打,關聯字令你只懂打西瓜不懂打傻瓜使用者偏好令你無法在另一部電腦工作自如。
附加功能並不是輸入法理論的一部分。
可惜,有些開發商賣輸入法賣到上市,卻無能力從理論上去改善一種輸入法,只懂持續優化附加功能,造成本末倒置。

結語

本文為中文輸入法理論寫下了一個框架,從組合數學,分類學 貫穿到認知科學。讀畢本文,不難明白其實我們還沒有一套最佳輸入法。我希望,輸入法研究者 可以有所啟發,輸入法學習者 能學得更得心應手,爭論哪套輸入法是最佳的人 能爭論得更科學一點。

延伸閱讀

中文輸入法大勢評議 http://shuowen.net/DaShiPingYi.htm
妙筆中文輸入法 http://mkho.hk-123.com/input1/
中文输入到底是简体字快,还是繁体字强? http://www.shcmusic.edu.cn/html/yywz/tpzs/89779.html