基於動態規劃與狀態機之形狀辨識研究

Shape Recognition Based on Dynamic Programming and State Machine

卓青福(Cing-Fu Jhuo)

指導教授 ： 侯雍聰

國立虎尾科技大學/管理學院/資訊管理研究所/碩士(2014年)

https://doi.org/10.6827/NFU.2014.00004

摘要

本論文探討於 iOS 系統下之形狀辨識系統研究與開發，其目的在於辨識使用者利用手寫所輸入的形狀，例如數字和幾何圖形等等，並使用動態規劃 (Dynamic programming) 與狀態機 (State machine) 之演算法進行識別機制的運算。
在國內外有關文字或圖形辨識的研究不勝枚舉，但是將這些研究進行整理後，發現對於行動裝置手寫輸入的辨識仍然有很大的改進空間，因此本研究利用動態規劃與狀態機提高辨識正確的機率，在本研究中將會進行不同演算法的比較，並且使用 iOS 系統進行開發。
本文將使用者輸入的形狀拆解成不同的區段，包含直線和彎曲等等不同之特徵，並將其與事先建立好的形狀模型進行比對，透過動態規劃演算法應用中的最長共同子序列 (Longest common subsequence, LCS) 應用來進行手寫系統的模式比對，本研究主要針對數字的字元進行辨識，但可應用於其他形狀，並加上狀態機的使用是為了修正手寫抖動等等的些微變化，利用狀態機可以將手寫的各種可能變化表達並轉換其狀態，讓本研究辨識率能大幅提高。另外最後以簡單圖形作為本論文的延伸研究。

關鍵字

形狀辨識 ； 動態規劃 ； 最長共同子序列 ； 狀態機

並列摘要

We will discuss the research of shape recognition system and development in iOS system, in order to identify users’ shape input by handwriting, such as numbers and shapes, and use the algorithm of dynamic programming with state machine to calculate the identification process.

There are many researches about recognition of text or graphics around the world. But after going through these studies, we found that handwriting recognition in mobile devices still has much space to improve.
So in this research, we will improve recognition accuracy probability by dynamic programming and state machine. We compare it with different algorithms, and develop in iOS system.

In this paper, the shape of the user input is divided into different sections, which include the difference between straight and curved features, etc, then we compare it with pre-setup shape model. Through the application of LCS (Longest common subsequence) of dynamic programming algorithms, it can be applied to handwriting mode system. This study is mainly about the identification of digital characters, but it also can be applied to other shape, and correct the handwriting jitter, etc, by state machine. By the use of state machine, we can express a variety of possible changes in handwriting and convert its state, so this research can significantly increase its recognition rate. In addition, identifying some simple graphics is an extension of the final study of this research.

並列關鍵字

Shape Recognition ； Dynamic Programming ； Longest Common Subsequence ； State Machine

參考文獻

[1] IDC Worldwide Mobile Phone Tracker (n. d.). Retrieved March 27, 2014, from http://www.idc.com/getdoc.jsp?containerId=prUS24645514

[2] Dan Rowinski. (2013, January 30).The Data Doesn't Lie: iOS Apps Are Better Than Android. Retrieved March 27, 2014, from http://readwrite.com/2013/01/30/the-data-doesnt-lie-ios-apps-are-better-quality-than-android#awesm=~oFA32T8YtZUvpx

[3] T客邦 (無日期)。讓數據說話，看看 iOS 與 Android 誰才是真正的贏家。2014年5月29日，取自：http://www.techbang.com/posts/13056-let-the-data-speak-look-at-ios-and-android-who-the-real-winner

[4] Wiki (n. d.). Optical Character Recognition. Retrieved March 29, 2014, from http://zh.wikipedia.org/wiki/%E5%85%89%E5%AD%A6%E5%AD%97%E7%AC%A6%E8%AF%86%E5%88%AB

[5] Cohen, I., Ayache, N., & Sulger, P. (1992, January). Tracking points on deformable objects using curvature information. In Computer Vision—ECCV'92 (pp. 458-466). Springer Berlin Heidelberg.