2001最佳碩博士論文獎論文摘要

九十年度中華民國資訊學會得獎論文之論文摘要

學號： 688410004
論文名稱：在行動特殊網路中以穩定度為基礎的多路徑繞徑演算法
Stability Based Multiple Path Routing in Mobile Ad-Hoc Networks
研究生：江天賜 (Tien-Tzu Chiang)
指導教授：林俊宏 (Chun-Hung Lin，中山大學資訊工程研究所)
校院：中正大學
系所：資訊工程研究所
學位：碩士
學年度： 90
語文：中/英文
頁數： 56
關鍵字：行動特殊網 (Ad Hoc Mobile Networks)
繞徑演算法 (Routing)
服務品質 (Quality of Service)
[提要]
現存在行動特殊網路中的繞徑演算法大抵都是去尋找到目的地的最短路徑。直覺上，如果這條到目的地的路徑長度比較短應該會比較長的路徑有較小路徑斷裂的風險。但是我們並不把路徑長度當作主要考量依據，我們所考量的是希望能找到一條可以用較長一段時間的路徑，也就是我們所謂的"穩定路徑"。路徑穩定度會比路徑長度更適合當作路徑品質的指標。可以期待穩定路徑會比一般路徑有較少路徑斷裂的機會，因此我們可以節省很多重新找路徑所要花費的昂貴代價。在這篇論文中，我們提出一個以路徑穩定度為基礎的多重路徑繞徑方法。它以AODV (Ad-Hoc On-demand Distance Vector Routing) 和 DSR (Dynamic Source Routing) 這兩個協定為基礎，他不僅保持住AODV (也就是有做路徑維護及較小的回應時間)和DSR (也就是在cache中存有多條路徑)的好特性，我們所提出的這個協定還會以路徑穩定度為考量依據找出適合的路徑。我們視一個路徑片段斷裂為錯誤，而以多重路徑來達到容錯。我們的協定會建構出從傳送點到目的地的一個以穩定為依歸的多重路徑的傳輸骨幹。模擬結果顯示，多重穩定路徑可以提升繞徑時的表現，效能優於AODV。而且，它可適用於大範圍行動特殊網路環境。
Most routing protocols in mobile ad-hoc networks are inclined to find the shortest path to destinations. Intuitively, if one route is shorter, the probability of one or more link failure is less than the longer one. In our consideration, the hop length of a route is no longer the main concern. What we really care is how to find a stable route which can be used for longer time without rerouting to recover from the path breakage. Thus we can save the cost of rerouting overheads to enhance the performance. In this paper, we present a stability based multipath routing protocol with path redundancy based on AODV (Ad-hoc On-demand Distance Vector routing) and DSR (Dynamic Source Routing). Our protocol not only remains the features of AODV (i.e., the distance vector, route maintenance, and lower latency, etc.) and DSR (i.e., multiple routes in cache), but also is able to find all the eligible paths. We consider a broken path as a fault and use the path redundancy for fault-tolerance. It chooses multiple stable routes based on the host mobility to form the transmission backbone from the source to the destination. The simulation results show that the proposed stable path routing with path redundancy can enhance the routing performance and outperform the AODV scheme. Also it can scale to large mobile populations in ad-hoc networks.

學號： 8802515
論文名稱： MP3音樂物件之自動特徵值的擷取與時序上的分段
Automatic Feature Extraction and Temporal Segmentation of MP3 Music Objects
研究生：郭威儀 Wei-Yi Kuo
指導教授：劉志俊 Chih-Chin Liu
校院：中華大學
系所：資訊工程研究所
學位：碩士
學年度： 89
語文：中文
頁數： 60
關鍵字： MP3
聲音分段 Audio Segmentation
內涵式查詢 Content-Based Data Retrieval
MP3資料庫 MP3 Databases
[中文摘要]
由於網際網路的快速興起、儲存設備的容量增加以及傳輸、壓縮技術的逐漸成熟，MP3音樂資料庫成為一項重要的課題。在本文中，我們分析MP3音樂的內涵，找出有用的特徵值，建立MP3內涵式的索引結構。我們特別針對MP3的音樂進行深入的探討，首先我們分析國語流行歌曲的結構，找出有規則的部分，接著使用知覺性的特徵來描述MP3的內涵，最後利用能量的大小及時間的變化，將音樂中有意義的部分擷取出來，當成索引及查詢的單位。
[英文摘要]
Because the rapid growth of Internet, the improvement of storage devices and advanced compression techniques, MP3 music database becomes an important research area.
In this paper, we propose an approach to segment MP3 music objects based on their content. First, we analyze Chinese pop songs to find some heuristic rules. Then we represent MP3's content based on their perceptual features. The change in music intensity is used as the feature to segment an MP3 music object into MP3 phonemes. The intervals of MP3 phonemes and finals are used to estimate the place where each MP3 phrase begin at. Experiments are performed and analyzed to show the effectiveness of the proposed method.

學號： R88526017
論文名稱：以電腦視覺為基礎之道路上障礙物偵測
On-Road Computer-Vision Based Obstacle Detection
研究生：孫正泰 Zheng-Tie, Sun
指導教授：傅立成 Li-Chen, Fu
校院：國立台灣大學電機資訊學院
系所：資訊工程所
學位：碩士
學年度： 89學年度
語文：英文
頁數： 79頁
關鍵字：電腦視覺 Computer Vision
汽車駕駛安全警告系統 Safety Waring System for Vehicle Driving
障礙物偵測 Obstacle Detection
立體視覺 Stereo Vision
顏色資訊 Color Information
行人偵測 Pedestrian Detection
機車腳踏車偵測 Bike Detection
汽車偵測 Vehicle Detection

[提要]
在本篇論文裡對於不同的障礙物，我們依據它們不同的外觀特性採用不同的比對及確認方式，對於行人及機車腳踏車我們採用M-Estimation based Hausdorff distance來做模板的比對以解決它們外型上的變動性，對於行人我們更採用一模板投票程式，藉此我們可以把模板比對的次數降到最低。對於車輛，我們則利用一些啟發性的方式來確認是否為車輛。在擷取分析出影像中障礙物之後，它們的位置及色彩資訊將會被儲存下來做為以後追蹤之用

In this paper, for searching and verifying pedestrians, we adopt a fast template matching method - template voting procedure (TVP) - based on M-estimation Hausdorff distance (M-HD) measure, which can accommodate the variety of shapes of pedestrians. For bikes, we just apply some fixed number of templates for M-HD matching based on the common shape of bikes from back-view and front-view. On the other hand, we adopt some heuristic verification steps for confirming whether it is a real vehicle………….

學號： R86126011
論文名稱：大學圖書館網站資訊架構可用性之研究－以國立臺灣大學圖書館網站為例
The Study of Usability of Information Architecture of the University Library's Web Site-A Case Study of the National Taiwan University Library's Web Site
研究生：藍素華 Lan Su-Hua
指導教授：謝寶煖 Hsieh Pao-Nien
校院：臺灣大學
系所：圖書資訊學系
學位：碩士
學年度： 89
語文：中文
頁數： 275
關鍵字：網站資訊架構 Information Architecture of Web Sites
　　　　　可用性 Usability

[論文摘要]
使用者如何評估與利用大學圖書館網站所提供的各項資訊與服務，使用者是否可以快速且便利地從大學圖書館網站找到所需的服務或資訊，均與大學圖書館網站資訊架構的可用性習習相關。由於Web化服務的提供方式與網路環境，讓圖書館能夠主動掌握各種網路資訊服務的規劃、架構與呈現方式，因此由大學圖書館網站使用者的角度研究網站資訊架構的可用性，能夠有效幫助圖書館了解網站資訊架構的可用性問題，進而提昇使用者利用大學圖書館網站的便利性與效率性。
網站資訊架構的可用性是由使用者決定的，不同的使用者會因為使用網站的便利性、效率性與滿意度，決定網站資訊架構的可用性程度。本研究即以使用者角度探討大學圖書館網站資訊架構的可用性，希藉由找出網站資訊架構可用性的決定因素與可用性問題，幫助圖書館改善網站服務，因此本研究採用內容分析法、問卷法和log自動記錄法，分由三面向分析網站資訊架構的可用性。首先選擇十所美國著名大學圖書館網站進行內容分析，以了解美國大學圖書館網站的服務現況，並與臺大圖書館網站評比異同；最後彙整各面向之研究結果，予以綜合分析與討論。續由使用者角度出發，以臺大圖書館網站為研究個案，分由使用者問卷調查和網站流量分析兩方面探討個案網站資訊架構可用性與滿意度。
由網站內容分析結果發現，美國大學圖書書館均已建置完善的網站，且對網站內容的組織、整理與提供方式，有獨到的特色，在課程資源的收集整理、學科資源的整理提供方面，尤為出色，值得參酌學習。
由使用者問卷調查結果得知，在臺大圖書館網站資訊架構的可用性認知方面，使用者最為重視的是資訊內容標示構面，其次是網站資訊架構構面；在經驗方面，使用者最滿意的是網站畫面設計構面和內容標示；使用者既重視又滿意的構面是內容標示，顯示使用者對臺大圖書館網站內容標示有高度評價。整體言之，使用者對於臺大圖書館網站資訊架構可用性評價的落差是一致的。由滿意度調查結果分析可知，使用者對於網站的有效使用、易於使用與滿意度均在中間水準之上，顯示使用者對於臺大圖書館網站的整體滿意度相當高。
由網站流量分析結果得知，臺大圖書館網站的使用人次與利用情況相當頻繁，使用者大多數來自臺大校內，使用者以利用館藏目錄、資料庫檢索最多，使用者的瀏覽路徑多半為首頁－最新消息－館藏目錄，顯示使用者最常使用的服務均出現於網頁上明顯位置，使用者能夠很輕易地利用這些服務。
本研究由文獻分析彙整網站可用性評估項目與網站資訊架構可用性評估項目，並綜合上述三面向之研究結果，歸納下列三項結論：1.美國大學圖書館網站服務內容與提供方式，實值得參酌學習；2.使用者希望能很有效率、很便利、很快速地從網站取得資訊，因此對於網站資訊的完整性、即時性最為重視，而由研究結果發現臺大圖書館網站與使用者的期望有一定程度的落差，顯示網站資訊架構的可用性有提昇的空間；3.臺大圖書館網站為臺大師生利用圖書館資源的主要管道，且臺大圖書館網站廣受使用者的認同與喜愛。
本研究最後針對研究結果提出六項建議：一、大學圖書館網站之資訊架構應以使用者為導向設計；二、大學圖書館網站應彰顯支援教學與研究之功能；三、應用新興科技於大學圖書館網站服務；四、強化數位化資源檢索系統；五、參考其他圖書館網站服務；六、持續不斷的評估。
We tested 1784 subjects who were the National Taiwan University Library's users, investigated the users about the cognitive and experience scores of National Taiwan University library web site in order to see how they use, how they think about and how they satisfied by the library web site, and we transcribed the user searching and browsing behaviors from web log reports to learn how the users do exactly. It was found that the top 10 university web sites are worth learning, and the usability of the information architecture of National Taiwan University library web site could be promote to some extent. The users usually use the library resources from library web site and satisfied by the library web site mostly. We suggested that user oriented library web site information architecture could augment the performance of the users information searching and browsing task, and the library web site should be evaluated iteratively.

學號： R88526026
論文名稱：一個高效率的即時高解析度動態全螢幕擷取系統
An Efficient Real-Time High Resolution Animated Full Screen Capture System
研究生：劉德懿 Te-Yi Liu
指導教授：陳文進 Wen-Chin Chen
校院：國立台灣大學
系所：資訊工程研究所
學位：碩士
學年度： 89
語文： English
頁數： 62
關鍵字：螢幕擷取 Screen Capture
網路串流技術 Internet Streaming
互動技術 Interactive Technology
遠端教學 Remote Education

[提要]
本篇論文提出一個能夠即時(Real-Time)連續擷取電腦螢幕影像並壓縮成為影片的系統。與市面上已經存在的系統相較，我們提出的方法是目前唯一可以達到即時擷取(Real-Time Capture)功能的，並且最佳可在1600 1200 True Color(32-bit)的高解析度下擷取能力達到一秒三十張。本系統最重要的應用在於可製作即時的自動簡報及軟體教學影片，此影片可放進套裝軟體中取代傳統的紙製使用說明書。除此之外，因為這樣的影片可以透過Intranet或Internet即時傳送(Streaming)到遠端的電腦，故本系統亦可發展為遠端教學或線上訓練的應用程式。我們相信本系統不但比傳統的紙製使用說明書方便而且更有效率。此外，因為我們採用的方法只需擷取兩張相鄰螢幕影像(Snapshot)的差異值而非每次都擷取整張螢幕影像，所以我們所提出的方法比市面上任何一個類似軟體都要有效率，此外，本系統特別針對螢幕影像的特性設計一個壓縮演算法，因此本系統亦可得到較小的影片檔案。

In this thesis, we propose a novel approach that can real-time capture and compress the full screen of PC into a video clip. It is real-time in that it can capture to 30 frames per second under the resolution of 1600x1200 True Color. One application of this system is to produce a digital presentation clip for instruction or tutorial. Moreover, as the video clips can be streamed over Internet or Intranet, they can be used for remote education or training. We believe this approach is clearer and more efficient than conventional text manual or handbook. As our system only captures the differences of successive snapshots instead of every single screen, it is more efficient and produced more compact clips than other existing systems. In addition, the compression algorithm adopted in our system is also described in this thesis.

學號： R88630006
論文名稱：人力網站可使用性設計準則之研究
The Study of Job Web Site Usability Design Guidelines
研究生：王郁青 Yu-Ching Wang
指導教授：岳修平 Hsiu-Ping Yueh
校院：國立台灣大學
系所：農業推廣研究所
學位：碩士
學年度： 89
語文：中文
頁數： 126
關鍵字：人力網站 Job Web Site
可使用性 Usability
設計準則 Design Guidelines

[提要]
自1980年線上招募出現以來，人力網站即成為另一新興的求職與求才管道，而相較於傳統企業招募利用報紙等平面媒體而言，人力網站具備迅速、方便、成本低廉的優勢，使得愈來愈多的求職與求才者仰賴此一網路途徑找尋符合需求的工作機會與合適人才。
但近年來眾多良莠不齊的人力網站，除使網路化的人力市場逐漸達到飽和外，缺乏完善規劃的網站也造成使用者使用上的不便，再者，科技的進步以及對使用者介面設計的日益重視，也使得人力網站不僅存在許多空間尚待改進，也有許多可供發掘的潛能存在，因此如何提供符合使用者需求的人力網站確實是當務之急。
本研究即是由可使用性的角度切入，探討人力網站應如何設計功能與介面以符合使用者之需求，並瞭解使用者對當前使用人力網站經驗的意見與看法，藉以提出重要設計準則，以提供未來人力網站規劃網站介面設計的重要參考，進而幫助求職者能更順利的找到符合期望之工作。而就另一方面而言，建構校園專屬人力網站幫助應屆畢業生找到工作，在國外已儼然成為一新趨勢，但國內卻還缺乏這樣的機制，故本研究亦蒐集學生對校園人力網站的相關建議，以提供各大學作為參考依據。研究設計部份共分為三大項，實驗一與實驗二請受試者分別針對本研究所設計的人力網站不同首頁與履歷類型進行評估，實驗三則是請受試者評估人力網各項服務功能，填寫評估問卷。
研究結果發現受試者較偏好人力網站的首頁為資訊較豐富且為長版面的設計，履歷版面也期待適度分頁、分步驟操作的設計介面，但不同的電腦能力以及人力網使用經驗則有差異存在。另外，提供個人化的功能以及智慧型的查詢機制也是使用者所期待的未來人力網站，而學生也皆贊同建置與現有人力網有區隔特色的校園專屬人力網站。此外，本研究最後亦提出七個人力網站可使用性設計準則如下：(1) 首頁設計架構需清楚並且強調性地呈現重要資訊；（2）妥善規劃版面配置善用有意義之圖像減低使用者記憶負擔；（3）履歷版面應朝彈性、清楚與容易操作填寫與檔案管理的方式設計；（4）加強人力網站查詢機制功能，提供基本與進階等之複合式查詢選擇；（5）發展個人化應用功能，增加系統彈性學習與符合使用者經驗與需求的功能設計；（6）增強資料保密與安全考量，確保使用用者對人力網站的信賴程度；（7）整合規劃全方位的求職求才服務，提供人力網站整體效率與使用者之滿意程度；（8）校園人力網站應朝學校的專業與特色發展設計，並依學生需求提供求職重要資訊。
本研究最大的貢獻在於以使用者的角度深入探討人力網站的功能與介面設計，提出可使用性設計準則。這是過去研究者較少探觸的議題，因此藉由本研究將可為人力資源、心理學、人機互動、教育科技等各相關領域提供重要研究參考，並經由本研究所提之結論與建議應可對人機介面與可使用性，以及人力資源之招募策略帶來理論與實務兩方面之重要貢獻。

學號： M8802108
論文名稱：從數值資料產生模糊規則之新方法
New Methods for Generating Fuzzy Rules from Numerical Data
研究生：張志豪 Chi-Hao Chang
指導教授：陳錫明 Shyi-Ming Chen
校院：台灣科技大學
系所：電子工程研究所
學位：碩士
學年度： 89
語文： English
頁數： 104
關鍵字：模糊分類系統 Fuzzy Classification Systems
模糊集合 Fuzzy Sets
歸屬函數 Membership Functions
加權式模糊規則 Weighted Fuzzy Rules

[提要]
模糊分類系統是模糊集合理論中的一個重要的應用。模糊分類系統可以處理分類問題中資料的不確定性。在發展一個模糊分類系統的過程中，一個重要的課題是如何定義各個屬性的歸屬函數以及產生合適的模糊規則。一般而言有兩種方法可以用來定義各個屬性的歸屬函數及從訓練資料中產生合適的模糊規則以處理某一特定之分類問題，其中一種是透過人類專家的協助，也就是由知識工程師詢問專家，或是藉由知識粹取工具的協助以獲得相關的知識。另外一種方法則是透過機器學習的方法讓模糊分類系統能夠由訓練資料中自行定義各個屬性的歸屬函數並產生模糊規則。
近年來，有許多學者專家提出許多不同的方法使系統能夠由訓練資料中自行定義各屬性的歸屬函數並進而產生模糊規則。然而目前已存在的方法中仍有些缺點，亦即(1)有些方法需要人類專家事先定義各個屬性的初始歸屬函數，也就是說這些方法無法完全自動的由訓練資料中定義各屬性的歸屬函數。(2)有些方法太過複雜及需要太多的運算時間。(3)有些方法產生的模糊規則數太多。
在本論文中，我們提出兩種方法來定義各個屬性的歸屬函數及產生模糊規則以解決模糊分類的問題。第一種方法的基礎概念是排除不需要的屬性項目，此方法的平均分類準確度比目前已存在的方法高，所產生的模糊規則數目也比目前已存在的方法少。第二種方法則是從訓練資料中產生加權式模糊規則，此方法的特點是在產生各個屬性的歸屬函數時，完全不需要人類專家的協助，同時此方法所產生的模糊規則也比目前已存在的方法少。
The fuzzy classification system is an important application of the fuzzy set theory. Fuzzy classification systems can deal with perceptual uncertainties in classification problems. In order to design a fuzzy classification system, it is an important task to construct the membership function for each attribute and generate fuzzy rules from training instances for handling a specific classification problem. There are two approaches to construct the membership function for each attribute and generate fuzzy rules from training instances. One approach is based on human experts' assistance, and the other approach is by applying machine learning techniques, such that the fuzzy classification system can construct membership functions and generate fuzzy rules from the training instances automatically.
In recent years, many researchers have proposed different methods to construct membership functions and to generate fuzzy rules for handling fuzzy classification problems. However, there are some drawbacks in the existing methods: (1) Some existing methods need human experts to predefine initial membership functions, i.e., these methods can not construct membership functions from the training data set fully automatically. (2) Some existing methods are too complicated and need a lot of computation time. (3) Some existing methods generate too many fuzzy rules.
In this thesis, we proposed two methods to construct the membership function for each attribute and to generate fuzzy rules automatically from training instances for handling fuzzy classification problems. The first method is based on the exclusion of attribute terms that can achieve a higher average classification accuracy rate and generate less fuzzy rules than the existing methods. The second method generates weighted fuzzy rules from training instances that can construct membership functions automatically without any human experts' interaction and can generate less fuzzy rules than the existing methods.

學號： 8817527
論文名稱：針對VLIW-based DSP指令排程方法的研究及其模擬環境的研製
A Study of Instruction Scheduling Techniques for VLIW-based DSP and
Implementation of Its Simulation and Evaluation Environment
研究生：蔡明龍 Ming-Lung Tsai
指導教授：陳正 Cheng Chen
校院：國立交通大學
系所：資訊工程研究所
學位：碩士
學年度： 89
語文： English
頁數： 85
關鍵字：指令排程 Instruction Scheduling
分時 Retiming
數位訊號處理 Digital Signal Processing
超長指令字集 Very Long Instruction Word

[論文摘要]
近年來，隨著個人攜帶式應用產品的普及，於影音資料與即時性資料的需求日益增加，因此，數位訊號處理器扮演的角色也日趨重要。如何能使資料即時且正確地展現在使用者面前成為了一個重要的課題，而指令的排程在整個過程中是一個很關鍵的步驟。在本論文中，我們以Push-up Scheduling Method為基礎，利用Retiming的觀念，在有限資源情況下，找到近乎最佳化的指令排程。接下來，我們在此排程方法中整合尋找schedule vector的程序，並放寬其中的限制，以建構我們的Relax Push-up Scheduling Method。我們的Relax Push-up Scheduling Method可以找到適用於該程式的schedule vector，使其執行時間為最佳化。在本文中，我們也研製了一套針對TI TMS320C62X系列DSP為對象的模擬與評估環境，將 Relax Push-up Scheduling Method在此環境上進行數項實驗，並與Push-up Scheduling Method及實際晶片上的效能作比較，更進一步驗證其優越的執行效能及的確能夠找出適當的schedule vector。我們會在接下來的本文中介紹Relax Push-up Scheduling Method演算法的詳細內容。

Digital signal processing on images and real-time data are more and more important by the popularization of portable devices recently. How to process data correctly in real-time is one of the most interesting topics to be investigated. The instruction scheduling is an important step through the whole process. In this thesis, we propose an effective algorithm, named Relax Push-up Scheduling Method (RPUSM), using the concept of retiming to find the near optimal solution under resource constraints. Our algorithm is based on Push-up Scheduling Method (PUSM) by relaxing its constraints and incorporating the procedure of finding suitable schedule vector. Our Relax Push-up Scheduling Method (RPUSM) can find the suitable schedule vector to obtain better execution time. For evaluating our algorithm, we also implement a simulation environment to verify it. According to our evaluations, our algorithms perform a well performance and find the more suitable schedule vector indeed. The detail descriptions of our algorithms will be given in the contents.

學號： 8817505
論文名稱： iSOHO: 無線網際網路服務平台之實作
iSOHO: A Wireless Internet Service
研究生：皇甫建君 Chien-Chun Huang-Fu
指導教授：林一平博士 Dr. Yi-Bing Lin
校院：國立交通大學
系所：資訊工程研究所
學位：碩士
學年度： 89學年度
語文：中文
頁數： 71頁
關鍵字：全球式行動通訊系統 Global System for Mobile Communication
(GSM)
短訊服務 Short Message Service (SMS)
網際網路 Internet
全球資訊網 World Wide Web (WWW)
無線通訊協定 Wireless Application Protocol (WAP)

[提要]
隨著無線通訊的蓬勃發展，短訊服務(Short Message Service; SMS)已成為廣泛使用的無線通訊服務之一。現在大部份的數位行動電話系統，皆提供短訊服務做為其加值服務。本文介紹以iSMS閘道器所架構之iSOHO無線服務平台。此平台將網際網路上的許多服務應用在短訊服務上，使用者可藉此隨時隨地利用短訊控制其家用電器的開關狀態，也可以透過短訊服務獲得網際網路上的各項資訊及服務。

Short Message Service (SMS) has become one of the most popular wireless services. Recently, most modern digital mobile phone systems offer SMS as a profitable added-value service. In this paper, we introduce iSOHO wireless service platform based on iSMS Gateway architecture. With this platform, many Internet applications can be run through SMS. For example, users can control their home appliances and access information and services from Internet by using SMS anytime and anywhere.

學號： 8611626
論文名稱：以即時協定為基礎的網際網路電話研究
The Study of Internet Telephony based on Real Time Protocol
研究生：游良福 Liang-Fu You
指導教授：李鎮宜教授 Dr. Chen-Yi Leev
校院：交通大學
系所：電子工程研究所
學位：碩士
學年度： 89
語文： English
頁數： 35
關鍵字：
即時協定 Document Filing
網際網路電話 Internet telephony
電腦電話閘道器 Computer telephony gateway
網際網路電話閘道器 Internet telephony gateway
公眾電話網路 Public Switch Telephone Network, PSTN
專用電話交換總機 Private Branch (telephone) exchange
封包遺失 Packet loss
封包延遲 Packet delay
封包顫動 Jitter
極長時間延遲 Spike
音頻放大器 Audio amplifier
混合轉換器 Hybrid transformer
線性預測編碼 Linear Prediction Coding, LPC
調適性的脈波編碼調變 Adaptive Differential Pulse Code Modulation , ADPCM

[論文提要]
現在網際網路是電信的一部份，以後電信將成為網際網路的一部份。電腦電話閘道器(或稱為網際網路電話閘道器)是電信與網際網路的溝通橋樑，通常使用電腦加裝電話語音卡，成為電腦電話閘道器。本論文首先提出兩種利用每部個人電腦通常就具備的數據機、聲霸卡和網路卡，來完成電腦電話閘道器的功能架構。
雖然寬頻網路時代的來臨，有助於在網際網路傳送的語音品質的提昇，但網路分享的網路特性，更多的多媒體與語音資料，在同時使用有限的頻寬，因此仍需要有效地使用頻寬。目前利用雜訊降低、回音消除、語音壓縮、動態撥放暫存(Adaptive playout buffer)及即時協定(RTP)等技術來提昇語音在網際網路傳送的品質，其中語音壓縮技術是能否有效運用頻寬的關鍵，而且壓縮技術之發展已臻成熟。
經由網際網路電話軟體SpeakFreely之實測結果可知，語音封包的遺失發生於頻寬不足，極長的語音延遲(spike)發生於網路擁塞。本論文提出由即時協定的語音封包接收情形，計算出目前之網路頻寬的數學公式，以便選用最適合的語音壓縮技術；並提出改善的spike偵側公式，於spike發生的最初期，立即改用較高壓縮率的語音壓縮方法。藉spike和頻寬不足之偵測及解決的演算法，來改善網際網路電話的語音品質。

Now the internet is a part of the telecommunication, but in the future telecommunication will be a part of the internet. The computer telephony gateway (or called internet telephony gateway) is the bridge between telecommunication and internet. Usually using a computer added a telephony interface card becomes a computer telephony gateway. The thesis first offers two architecture of the internet telephony gateway using modems, a sound card and a network interface card that every personal computer already has.
Although the age of broadband network comes, there are more multimedia and voice data share the finite bandwidth at the same time, it still need to use bandwidth efficiently with the characteristic of network sharing. The technology of noise reduction, echo canceling, voice compression, adaptive playout buffer and Real Time Protocol (RTP) are used to improve the voice quality in internet telephony. And the technology of voice compression is the key to use bandwidth efficiently and developed maturely.
With the internet telephony software "SpeakFreely" we experimented and found out that the packet loss took place in insufficient bandwidth and the spike took place in network jam. The thesis offers a mathematic formula to measure the network bandwidth with RTP voice packets, then chose the optimal voice compression, and offers an improved spike detection formula to early detect the spike and change to the more compact compression method at the beginning of the spike. With the algorithm for detection and solution of spike/bandwidth insufficient, the voice quality of internet telephony is improved.

學號： P76881265
論文名稱：處理2D&3D多邊形體的形變之極佳有效的內插演算法
Efficient 3D/2D Polygon Metamorphosis System
研究生：黃柏華 Po-Hua Huang
指導教授：李同益 Tony-Yee Lee
校院：國立成功大學工學院
系所：資訊工程所
學位：碩士
學年度： 89
語文：中文
頁數： 125
關鍵字：內插 interpolation
變形 morphing
攤平 flatten
合併 merge
塊面 patch
微調 relaxation
重新三角化 remesh

[提要]
Morphing為電腦圖學領域中熱門的研究題目，因其所帶來的視覺特效每每令人瞠目結舌，例如電影魔鬼終結者II中的液態金屬人在影面當中就常常有變形的動作發生，像是從一個男人變成一個女人，或是將手變成一把刀子等，這些都是由Morphing所帶來的電影特效
本論文對於Morphing領域的兩大問題-(1)對應問題與(2)內插軌跡問題-皆有深入地探討，我們希望能夠建立一套完整的Morphing演算法，以突顯出本論文在Morphing領域的貢獻
首先，本論文研發出一套簡單易懂的2D內插演算法，當中不需要複雜的計算公式，只利用角度與長度的線性內插而已，同時也不需要像文獻[3]一樣涉及最佳化求解，我們巧妙地利用階層式架構來避免這方面的需要，因此整個演算法的執行效率幾乎是即時完成。雖然我們的演算法非常簡單，但是在內插的結果上卻可以和文獻[3]的結果一樣完美。另外，本論文還提出了三項具世界級困難度的內插問題，藉由本論文的內插演算法可以輕易解決。
我們的對應演算法主要的流程架構是(1)設計一套良好的介面提供給使用者在物體表面上點選圈選點;(2)利用最短路徑將圈選點作兩兩相連，以切割勿體表面;(3)利用Relaxation的方式進行攤平的目的;(4)利用Warping技術以增進使用者的便利性，因此無須圈選太多快patch以精確對齊物體的特徵，同時還提供一套自行避免相交情況的演算法以保證不相交;(5)我們研發出一套極快速的merge演算法，其利用最小輪廓涵蓋結構而有效地達成區域搜尋與區域merge，因此在效率上達到O(n+k);(6)最後藉由Remesh與3D位置資訊的建立，重構出對應的結果整體而言，透過本論文所研發的對應演算法將不用花費太多的執行時間，因此符合經濟效益。

Morphing algorithm has received considerable attention in computer graphics and image processing. Morphing has become a standard technique in movie and entertainment industry. Although computer generated images, which are rendered from 3D models, are common today, the majority of methods developed so far focuses on the problem of interpolating between 2D images.
In this thesis, we present new methods for solving the two main problems of morphing technique-(1) the corresponding problem and (2) the interpolation problem. The algorithms we propose are very easy to be implemented and generate the fine results efficiently.
We present a new approach for interpolating the two polygons. We only use the stick structure (linear interpolation of the length and the angle of the stick) and the hierarchical structure to generate the shape result as good as [3]. However, [3] not only use the singular value decomposition (SVD), but also the least square to get optimal interpolating matrix. So our algorithm is more efficient than [3]. Further, we propose the three most difficult interpolation problem. Our algorithm can solve the three problems easily.
We present an efficient approach for generating the correspondence between two homeomorphic 3D polyhedral models. The user can select vertices on the polyhedra to decompose the boundary of each polyhedron into the same number of morphing patches. Further, the user can specify the feature points on the morphing patch pairs to improve the morph. After the morphing patch pairs are be mapped to 2D regular polygons, they are merged and reconstructed to generate a morph. In the main procedures of our approach, we propose an easy mapping method and a foldover-free warping technique. And we also propose a most efficient merging algorithm. The merging can be completed in O(n+k).

學號： 883975
論文名稱：植基於通訊通道架構下之多媒體數位浮水印技術
A Multimedia Digital Watermarking Technique Based on Communication Channel Model
研究生：李建儒 Chien-Ju Li
指導教授：許文星 Wen-Hsing Hsu
校院：國立清華大學
系所：電機工程學系
學位：碩士
學年度： 89
語文： English
頁數： 82
關鍵字：數位浮水印 Digital Watermarking
雜訊通道模型 Noise Channel Model
人類視覺系統 Human Visual System

[論文摘要]
隨著通訊及網路的日益發達，數位化資訊的傳播變的快速而簡便。因此，在人人皆可任意取得數位資訊的情況下，如何保護未經授權的多媒體資料不被複製及任意的散佈為一重要之課題。
數位浮水印技術(Digital Watermarking)為近年來新興的技術，它能將資訊隱藏於多媒體資料中用來宣告所有權、著作權或認證。和一般加密系統最大不同的是，在密碼學中，資料經加密後只在傳送過程中受保護，然而一旦解密後，資料就可被任意複製、傳播。利用數位浮水印技術，任何人都可以讀取多媒體資料，若有版權爭議便可擷取出資料中隱藏的浮水印以供認證。
植基於小波轉換之壓縮技術，諸如EZW、SPIHT及EBCOT等演算法可提供極佳的壓縮效率及影像品質，且已成為未來壓縮標準JPEG-2000及MPEG-4之核心技術。本論文提出一個新穎的數位浮水印技術。除了具備一般強韌浮水印(Robust Watermarking)的特性：不可視性、不易消除、無法經統計分析偵測、可抵抗失真壓縮及訊號處理破壞外，我們的系統中亦考慮了新一代壓縮技術MPEG-4及JPEG-2000對浮水印的影響；再者隨著無線通訊技術的進步，新一代的通訊技術(W-CDMA)、Wireless Lan、Bluetooth使用展頻的技巧。隨著傳輸頻寬增加的同時，多媒體的傳輸雖然變的迅速、方便，卻也同時產生了通道雜訊的干擾。因此，在此部分我們的亦分析了AWGN(Additive White Gaussian Noise)對數位浮水印系統的影響。
本文將數位浮水印系統比擬成通訊系統，原始媒體資訊(影像)之頻域軸為傳輸通道，而浮水印資料為傳輸訊號，可能遇到的攻擊或破壞則視為通道雜訊。基植於此架構下，我們提出了一個雜訊通道模型之跳頻式數位浮水印技術，此外，並結合同步化的觀念進而有效的抵抗失真壓縮及影像偏移之攻擊。由於我們將影像頻域之多重解析模擬成白色高斯雜訊之通道，因此在此雜訊模型下，我們可有效的將加諸於影像上之各種攻擊視為隨機雜訊。
我們的數位浮水印技術不需原始影像資料輔助擷取浮水印，然而為了更增加系統的安全性及強韌度，我們將"小波分解/合成之濾波器"，"額外資訊"及"虛擬亂數碼"視為安全金鑰。此外，我們的浮水印為可視性之圖案或簽章，結合安全金鑰可有效的防止SWICO之攻擊。值得一題的是我們的系統亦可有效的應用於DVD之防盜考機制上，最後，由實驗結果可看出我們提出的方法的確是有效且受肯定的。

With the rapid development of communication and network, the transmission of multimedia, such as image, video and audio, is becoming more and more convenient. Hence, there exists a very important issue for the protection of intellectual property rights.
Digital watermarking is a novel and developing technology, it has evolved very quickly for the past few years. A digital watermarking is the information, which is robustly and imperceptibly embedded in the multimedia data. Applications include copyright protection, authentication and data tracking. The distinct difference between the watermarking and encryption is that the data is only protected during the transmission using the traditional cryptography. After decrypting, however, the digital data is no longer protected, thus it is clear; it can still be copied and distributed. In contrast to cryptography, anyone can use the multimedia data, once the dispute about the ownership of data happened, we can extract the information from the host data to authenticate and characterize the owner by watermarking technique.

Wavelet based coding, such as EZW and SPIHT, is an extremely successful compression algorithm, and has become the core technology of the up-coming image/video compression standards, which is well known, JPEG-2000 and MPEG-4. In this thesis, we will introduce a new multiresolution watermarking technology. The method is based on the discrete wavelet transform. Owing to the rapid growth of wireless communication, the transmission of multimedia is becoming fast and convenient. However, the data in transmission will suffer the channel noise and drop the quality of the transmission. To reduce the interference of channel noise, we also discuss the affection of additive white gaussian noise (AWGN) in our system.
In this thesis, we interpret the watermarking technology based on communication concepts. The watermark is transmission signal, the frequency domain of original image is the transmission channel and the attacks are regarded as channel noise. Based on this architecture, we propose a quasi-blind watermarking technique and synchronization ideal, which can against JPEG coding, Wavelet-based coding and image shift attacks efficiently. In this framework, the attacks can be regarded as random noise, and which cannot affect the characteristic of AWGN channel (noise model). In addition, our watermarking technique does not need the original cover data to extract watermark, but some keys like "wavelet filters", "side information" and "PN code" are necessary to increase robustness and security, on the other hand, the watermark is visually recognizable patterns; those are useful to against SWICO attack. To deserve to be mentioned, our proposed system can further be used in the DVD copy protection, the watermark can be used as copy control bits or embedded into video to prevent playback attacks. Consequently, the experimental results show our proposed system that is feasible and effective.

學號： P76881168
論文名稱：三維多面體攤平技術與其應用
Three Dimensional Polyhedron Flattening Technique and its Applications
研究生：林漢盈 Hanying Lin
指導教授：李同益 Tongyee Lee
校院：國立成功大學
系所：資訊工程研究所
學位：碩士
學年度： 89
語文：中文
頁數： 110
關鍵字：攤平 flatten
微調 relaxation
變形 Morphing
映對 mapping
半徑基底函數 radial basis function
拓樸邏輯 topology
平滑 smooth
貼圖 texture mapping

[論文摘要]
拜電腦進步神速之賜，使得圖學和影像的研究有如雨後春筍般地蓬勃發展，不僅將圖學和影像大量地應用於日常生活中的娛樂-遊戲，也常被應用於生物醫學方面，甚至藉由影像辨識處理來過濾可疑的犯人，成為破案的關鍵。雖然三維影像可以使我們以三百六十度中之任一角度觀察到，不過，若是三維物體本身凹凸得很嚴重，那麼其內凹的部份，將永不見天日。換而言之，若我們想要瞭解物體表面的所有資訊，必須想出一個能將物體表面展開的方法；直覺想到的方式便是將物體攤平至二維的平面上，也就說要將物體平面化。因此，本論文主要是發展一個攤平演算法，以成就其它須建構於其上之應用，舉凡有三維多面體變形、醫學、貼圖和比對方面等應用。
本論文之攤平方式，主要是將使用者選定好之三維多面體表面區域，攤平至二維圓盤( disc)上，圓盤之圓周其實是一個多邊形，邊數和邊長分別來自於三維物體邊界（boundary）之邊數和邊長比例。圓盤內部之點依調整（relaxation）的方式得到，最後，圓盤所有內部頂點處於靜力平衡的狀態。為了增加視覺效果，我們提供一些將攤平後之網格圖著色方法，主要是以相對應之三維頂點的顏色、法向量和曲度作為調色之依據。將物體表面展開，除了拓樸邏輯結構不能改變外，其幾何結構亦須一致，使得distortion能夠很小。評估攤平結果好壞的最簡單方式便是考慮三維至二維之間長度、面積和角度的縮放比例是否一致，若趨近於一致，表示此攤平結果是好的。因此，我們實際繪出兩種統計圖來觀察，並且計算攤平的誤差。最後，由眾多的實驗結果可以證明我們的攤平演算法的確是相當穩健且有效率的。
透過攤平處理，許多的研究得以撥雲見日，急速發展。本論文主要的應用-三維多面體變形，便是因它而生。變形著眼於兩物體對應關係之尋找，對好後便可內插出各個時刻的物體。我們變形的處理過程，主要是將兩物體分別攤平至二維的兩個圓盤上，再以RBF（Radial Basis Function）作扭曲使得特徵點能對齊，接著合併兩個圓盤形成一個重新三角化後的新圓盤，此新圓盤具有原始兩物體之共同屬性，最後內插圓盤上頂點的來源和目的三維座標，得到變形物體，此外，我們也利用SLP來平滑物體，使得外表更美觀。除了變形應用外，醫學的應用亦是不落人後，我們以人類體內摺皺得很厲害的兩個器官（大腦和大腸）作實驗，幫助醫生瞭解病患受損的部位，以做更一步的處理。我們也將攤平應用於貼圖上，以增加物體的真實性。最後，利用RBF處理二維影像變形，效果相當卓越。

Although three dimensional image can be observed in any direction, we never see concave area of the polyhedron. We decide to develop an algorithm for flattening the surface of the polyhedron. After flattening the surface, we can understand the region we can not see in three dimensional space. We present a flattening method based on relaxation procedure to find the vertex correspondence between 3D and 2D. Our algorithm is applicable for arbitrary polyhedron that are homeomorphic to the three dimensional sphere or the two dimensional disk. In our algorithm, 3D object patch in which user is interested is embedded to the circular disk on the plane. We must consider similarity between 3D patch and 2D disk. In other words, it is very important for reducing the distortion from flattening 3D patch. Our flattening algorithm consider three important shape evaluated factor: length, area and angle respectively. Two pictographs and distortion error are used to judge that a flattening map is good or bad. We also offer some method to render the disk so that user can clearly understand the difference or the area that distorts very seriously between 3D and 2D. Finally, many experimental results show that our flattening technique is indeed a stable and efficient. In addition to the flattening algorithm, we also use it in many applications, such as Metamorphosis(or morphing),medical aspect and texture mapping. In our morphing method, each of two 3D objects is first embedded to the disk. The embedded model has the same graph structure as its 3D objects. Second, we warp the two disks respectively by using Radial Basis Function to align the features of original models. Third, we merge those two embedded models to become a new one, we can establish correspondence between two objects. Forth, by using this correspondence, intermediate objects between two models are easily generated by interpolating source and target coordinates of vertices from the new embedded model. Finally, we use SLP to smooth the models. There are still two other applications that can not be neglected, medical aspect and texture mapping. In medical application, two complex organs, cortex and colon, are flattened and rendered to help medical doctors understand patient's destroyed place. In texture mapping, it makes the 3D models more glory and real.

學號： 883331M
論文名稱：從數值型資料挖掘模糊多層級關連規則及模糊順序性樣式
Mining Fuzzy Multiple-level Association Rules and Fuzzy Sequential Patterns from Quantitative Data
研究生：林桂英 Kuei-Ying Lin
指導教授：洪宗貝 Dr. Tzung-Pei Hong
校院：義守大學
系所：資訊工程研究所
學位：碩士
學年度： 89
語文： English
頁數：
關鍵字：瀏覽樣式 Browsing patterns
資料挖掘 Data mining
模糊集合 Fuzzy set
一般化關聯規則 Generalized association rule
機器學? Machine learning
數量值 Quantitative value
順序性樣式 Sequential patterns
分類階層 Taxonomy,
網路挖掘 Web mining

[論文摘要]
因為資料挖掘提供了從大型資料庫中發現有用資訊和重要相關樣式的機會，因此有許多在資料庫及機器學習領域上的研究者對其非常感興趣。過去大部份的研究皆著重於如何處理二元值的交易資料。但在真實世界的交易資料中通常包含了數量值，所以如何設計出一個能夠處理多種資料型態的資料挖掘方法便成為此領域研究者的一大挑戰。
因此本篇論文提出兩種類型的模糊資料挖掘演算法，分別為挖掘多層級關連規則及挖掘模糊順序性樣式，以從數量值的交易資料中萃取所含的知識。我們所提的演算法首先將交易資料中的數量值轉成語意詞，接著修改傳統資料挖掘演算法以過濾這些語意詞來發現關連規則或者是順序性樣式。?個項目可只用有最大模糊出現個數的語意詞或使用所有可能語意詞在後續的挖掘過程。如果只使用具有最大模糊出現個數的語意詞，則被處理的模糊區數目將和原始項目數目相同，因此此種演算法可著重於最重要的語意詞以降低它的時間複雜度。若?掘的過程中是使用所有的語意詞，則雖然計算會更加複雜但被導引出的規則會更加完整。另外我們也提出從全球資訊網中挖掘模糊瀏覽樣式的演算法。這些被挖掘出來的關連規則和順序性樣式可展現出在資料庫中重要的數量規律性，而這些數量規律性可以提供一些建議給適合的管理者參考。

Many researchers in database and machine learning fields are primarily interested in data mining because it offers opportunities to discover useful information and important relevant patterns in large databases. Most previous studies have shown how binary valued transaction data may be handled. Transaction data in real-world applications usually consist of quantitative values, so designing a sophisticated data-mining algorithm able to deal with various types of data presents a challenge to workers in this research field.
This paper thus proposes two kinds of fuzzy mining algorithms, respectively for multiple-level association rules and sequential patterns, to extract knowledge implicit in transactions stored as quantitative values. The proposed fuzzy mining algorithms first transform quantitative values in transactions into linguistic terms, then filter them to find fuzzy association rules or sequential patterns by modifying the conventional mining algorithms. Each quantitative item uses only the linguistic term with the maximum cardinality or uses all possible linguistic terms in the mining processes. If only the linguistic terms with the maximum cardinalities are used, the number of fuzzy regions to be processed is the same as that of the original items. The algorithms therefore focus on the most important linguistic terms and reduce their time complexity. If all linguistic terms are used in the mining process, the derived set of rules or patterns is more complete, although computation is more complex. In addition, a web mining algorithm for fuzzy browsing patterns from the world wide web has also been proposed. The association rules and sequential patterns mined out thus exhibit important quantitative regularity in databases and can be used to provide some suggestions to appropriate supervisors.

學號： F83503020
論文名稱：全光多波長分工光纖網路之容錯及協定設計
Fault Tolerance and Protocol Design for All-Optical WDM Networks
研究生：蘇銓清 Chuan-Ching Sue
指導教授：郭斯彥 Sy-Yen Kuo
校院：臺灣大學
系所：電機系
學位：博士
學年度： 89
語文：英文
頁數： 176頁
關鍵字：多波長分工 Wavelength Division Multiplexing (WDM)
容錯 Fault Tolerance
協定設計 Protocol Design
波長路由 Wavelength Routed
重繞 Rerouting

[論文摘要]
中文摘要
由於網路使用者數量的急速擴張以及應用程式的複雜性增加，我們需要一個能夠提供大頻寬、大容量的超高速網路。多波長分工光纖網路（Wavelength Division Multiplexing）將單模態光纖之中所擁有巨大的傳輸容量切割成許多平行的通道，目前已成為光纖網路的新興技術。伴隨著多媒體服務程式的出現例如分散式資料處理、廣播系統、視訊會議、以及頻寬隨選系統等等，在下一代網際網路上所用的多波長分工光纖網路必須有效率地提供全光路徑傳輸。本論文旨在探討多波長分工光纖網路上實現全光路徑傳輸協定 (Protocol) 及容錯 (Fault Tolerance) 設計的一些問題。

首先，我們提出一個同步流量控制 (Synchronous Flow Control) 機制來實現蟲洞路由 (Wormhole Routing) 的光纖網路,希望能將蟲洞路由的好處(短延遲及少量緩衝器)整合在光纖網路內。由於光纖網路是一個單向性廣播網路，無法直接利用雙向式非同步後推式 (backpressure) 流量控制，因此我們提出同步流量控制，可以利用無死結式 (Deadlock-free) 的虛擬通道 (Virtual Channel) 的方法來將控制訊息廣播出去，所以蟲洞路由的優點可以輕易的整合入光纖路由。
其次，我們提出一個兩階段式 (Two-phase) 的傳輸協定，來規劃一對一 (Unicast) 及一對多 (Multicast) 的需求，在第一階段中先利用即時 (Online) 的時槽規劃 (Time Slot Scheduling) ，所推導出的時槽矩陣 (Time Slot Matrix) ，來免去一般演算法所預設已知的需求量矩陣 (Demand Traffic Matrix) ，而在第二階段中持續找出時槽中可能閒置的波長及接收器，這樣的協定是很容易實現，並且從實驗結果中顯示，想要達到好的效能必須在傳輸特性及網路負載中作取捨。
接著，我們提出加速型預先配置協定 (Accelerative Pre-allocation WDMA) ，來克服預先配置協定 (Pre-allocation WDMA) 的缺點並保留其優點。加速型預先配置協定只利用簡單的公式而非像保留型配置法 (Reservation WDMA) ，動用大量記錄，雖然加速型預先配置協定使用一條專屬的控制波長來傳送控制封包，但是它可以利用網路管理機制來充份使用在不同延遲下的空閒時間。它更可利用我們所提的三個演算法來做波長分享，所以非常適合於波長有限的光纖網路。透過分析結果，可以發現加速型預先配置協定的效能，主要的影響因素包括了波長數目、流量型態 (Traffic Type) 、波長分享程度及波長間的不平衡負載程度。
進而，我們提出可容忍鏈結錯誤 (Link Fault) 、傳送器或接收器所產生的波長錯誤、光交換器錯誤 (Optical switch fault) 等等的光纖路由器 (Optical Crossconnect) 。它主要是在原有的光纖路由器架構上增加光纖交換器輸出輸入埠及一些波長轉換器 (Wavelength Converter) 。實際的回復程序有兩階段，第一階段先採鏈結式 (Link-based)，第二階段再採來源式(Source-based)。有了這樣的容錯光纖路由器 (Fault Tolerant Optical Crossconnect) ，在每一鏈結中正常及備用 (spare) 波長數目，便可以根據負載及系統可靠度的要求來做動態調整。
為了改良一般以路徑保護共享備用光路徑 (Path Protection With Spare Sharing) 傳統方法，我們另外提出波長重配置的備用路徑重繞路法 (Spare Rerouting with wavelength Reassignment) 來改進阻斷機率 (Blocking Probability) 之餘，還能減少所須的備用資源。經過深入的模擬結果，我們發現提波長重配置的備用路徑重繞路法，可以在動態的環境下改進阻斷機率,並能減少所須的備用重繞 (Rerouted) 路徑的數目。
最後，我們將容錯問題延伸到可以快速回復並容忍多數錯誤的環境。我們利用簡單的往回走 (Loop-back) 機制，來達到快速回復的機制，並將找出可容忍多數錯誤的問題，模型化成環形覆蓋集合 (Ring Cover Set) 的問題。因而提出三個簡單方法 (Heuristic Methods) 來找出可容忍多錯誤的有效環形集合。從結果中我們發現雖然加入少數的可波長轉換的節點 (Wavelength Convertible Node) ，可以有效的降低阻斷機率，卻無法對多重錯誤的回復性 (Restorability) 提供明顯幫助。
英文摘要 The increasing sophistication of a rapid expansion of network users demands for very high-speed networks, which can support high-bandwidth, large-volume services. Wavelength Division Multiplexing (WDM) networks are emerging as the major technology to divide the enormous information-carrying capacity of a single-mode fiber into concurrent channels. Accompanied with the advent of multimedia services such as distributed data processing, broadcasting systems, teleconferencing, and bandwidth-on-demand applications, WDM networks for the next generation internet need efficient protocols and dependable infrastructures. This dissertation studies the problems related to the implementation of protocols for WDM broadcast-and-select networks and design of the fault tolerance on WDM wavelength-routed networks.
First, we propose a synchronous flow control mechanism in wormhole routed optical networks. It is expected that optical networks will have the benefits of shorter routing delay and smaller buffer size requirement, as those in wormhole routing will exist in optical networks. Different from the traditional bi-directional asynchronous backpressure flow control, the flow control is modified to be unidirectional and synchronous. The proposed flow control takes advantage of the restricted order of accessing channels in deadlock-free routing to broadcast their control information in a corresponding restricted order. Furthermore, in order to reduce the buffer size to one, the virtual channels that share the same physical channel must be able to transmit data concurrently.
A two-phase media access protocol is presented next to provide an efficient mechanism for scheduling unicast and multicast traffic. In the first phase, the protocol uses an on-line slot scheduling algorithm to derive the heuristic slot matrices. In the second phase, the protocol continuously finds the idle channels and receivers in the next slot matrix to refill it until the heuristic slot matrices in the first phase are finished. The protocol is simple to implement, and the simulation results suggest that the protocol with proper tradeoff considerations between session characteristics (length, size, and multicast ratio) and network loads would result in better performance.
A new media access control (MAC) protocol, AP-WDMA (accelerative pre-allocation), is proposed to overcome the disadvantages of P-WDMA (Pre-allocation) and retain its advantages. AP-WDMA relieves the technology constraints by restricting the wavelength tunability at only one end of communication link, removes the channel and station status tables required by R-WDMA (Reservation), and uses simple arithmetics instead of a pre-allocation map to allocate channels. In addition, it is well suitable for wavelength-limited networks. Three heuristic methods for channel sharing: Interleaved (I), Neighborhood (N), and Weighted-Balanced (WBH), are evaluated. We also evaluate the impact on the performance of AP-WDMA from the number of channels, the four traffic types (mesh, disconnected, ring, and uniform), the degree of channel sharing, and the unbalanced load among channels.
Then we propose a fault tolerant optical crossconnect (OXC) which can tolerate link, channel, and internal optical switch failures via spare optical channels, extra input/output (I/O) ports for an optical switch, and associated wavelength converters. The restoration process has two phases, one is link-based and the other source-based. For link-based restoration, if a physical link/channel or optical switch fails, the fault tolerant OXC (FTOXC) restores the lightpaths, which pass through the failed link/channel or the optical switch, simply by redirecting these lightpaths to the spare channels to continue their transmissions. As for source-based restoration, the source node finds the routing paths when a link-based restoration path can not be found. Thus, the proposed restoration scheme is based on a unified restoration process and a fault tolerant wavelength routing algorithm (FTWRA). The FTOXC and FTWRA can be applied to any all-optical network and can recover many types of failures. To find a global optimal setting of working and spare channels, the problem is formulated as an integer linear program (ILP). The number of working and spare channels in each link can be dynamically adjusted according to the traffic loads and the system reliability requirements. The tradeoff between these two conflicting objectives is analyzed by the Markov decision process (MDP).
We also present techniques to construct dependable all-optical WDM networks. Path protection using shared spare lightpaths is a general wavelength routing method to improving the blocking probability while minimizing the required spare resources. However, in a dynamic traffic environment, this method may still lead to poor performance because it is highly likely that a wavelength on a link is continuously held by a spare lightpath and can not be assigned to the working lightpath of a new connection. Therefore, the new connection is blocked. This paper presents a spare rerouting with wavelength reassignment (SR_WR) mechanism to reduce the blocking probability. Spare rerouting (SR) rearranges spare lightpaths of existing connections to accommodate a new connection without any disruption on the working lightpaths of existing connections. SR_WR has two phases. Phase I uses an occupancy function q with or without the conflict table Tc to obtain a working-spare lightpath pair with minimum cost. Tc maintains the relationship between every pair of wavelength and link. Whether to use Tc or not depends on the complexity and performance requirements. Phase II uses a tuning function g to get a least cost lightpath pair with minimum weighted number of rerouted spare lightpaths. SR can further be classified as SR_A (reroute to available lightpaths, including both free and shared spares) which uses Tc, and SR_V (reroute to free lightpaths only) which dose not use Tc. Extensive simulation experiments were conducted to study the performance of the proposed SR_WR method.
Finally, we address the problem of achieving fast restoration and tolerating as many faults as possible in wavelength-routed wavelength division multiplexing (WDM) networks with and without wavelength conversion. The basic idea is a simple loop-back mechanism implemented directly in the optical layer to ensure fast restoration with little coordination overhead. The problem of finding maximum number of faults that can be tolerated is modeled as a constrained ring cover set problem, which is a decomposition problem with exponential complexity. Three heuristic methods, each can tolerate one or more faults, are proposed. A marked-link (ML) method is also proposed to enhance the performance by making some links, which are originally used for protection, be used for normal transmission. The fault management overhead is insignificant in networks without wavelength conversion because the loop-back mechanism does not need to take care of wavelength conversion. In contrast, a two-phase control must be used to manage the restoration process in networks with sparse wavelength conversion, which have few wavelength convertible nodes. From the analytical results for networks without wavelength conversion, we know that the maximum number of faults tolerated is dependent on the network topology. Apart from the conclusions of previous studies on wavelength conversion that only a small number of wavelength convertible nodes are enough in a network, we found that the number of wavelength convertible nodes plays an important role in the tradeoff between the blocking probability, the restorability, and the two-phase control overhead.
學號： D85526008
論文名稱：區塊對應、最近鄰居搜尋、與 DNA 序列搜尋之快速演算法
Fast Algorithms for Block Matching, Nearest Neighbor Search, and DNA Sequence Search
研究生：陳永昇 Yong-Sheng Chen
指導教授：洪一平 Yi-Ping Hung
傅楸善 Chiou-Shann Fuh
校院：國立臺灣大學
系所：資訊工程學研究所
學位：博士
學年度： 89
語文： English
頁數： 156
關鍵字：樣版比對 template matching
區塊對應 block matching
最近鄰居搜尋 nearest neighbor search
DNA 序列搜尋 DNA sequence search
快速演算法 fast algorithm
贏者更新 winner-update

[提要]
樣版比對技術的應用範圍非常廣泛，舉凡影像與視訊壓縮、視覺追蹤、立體對應、圖型分類、物體辨識、資料庫資訊擷取等應用，都可利用樣版比對來搜尋相類似的物體。樣版比對的主要困難之一，是在於其所需的運算量非常龐大，特別是在處理大量的資料時。在本論文中，我們提出許多快速運算技術，在保證找到最佳搜尋結果的前提下，能大幅減少樣版比對所需的運算量。同時，我們也應用這些技術來提升區塊對應、最近鄰居搜尋、與 DNA 序列資料庫搜尋等樣版比對應用的執行效率。
我們所提出之快速樣版比對技術其主要構想，是在於距離下限的利用。由於我們的目標是要在搜尋範圍內，尋找與樣版間具有全域最短距離的樣本，因此對每個樣本而言，若其任一個距離下限值已經大於全域最短距離時，我們就可以省去該樣本與樣版間距離的計算。由於我們所利用之距離下限的計算量比起距離本身來的少，因而可以加速整個搜尋過程。同時，我們也利用贏者更新搜尋策略，來減少真正所需計算的距離下限個數。為了更進一步加速，我們也使用多種資料轉換技術來使所計算得之距離下限值更貼近其距離值本身。
針對在視訊壓縮與視覺追蹤中常用的區塊對應技術，我們提出了一個新的快速演算法。這個演算法利用贏者更新搜尋策略，並使用一個比對誤差之遞增下限序列來決定贏家。對每個搜尋位置而言，若其任一個誤差下限已經大於全域最小比對誤差時，該位置的比對誤差計算就可以被節省下來。基於下述三個原因，我們所提出之演算法可大幅加速區塊對應的過程。其一，我們所使用之誤差下限的計算量比起誤差本身來的少。其二，對於在遞增下限序列中的每一個下限而言，只有當它的前一個下限比全域最小比對誤差還小時，我們才需計算該下限。其三，對很多搜尋位置而言，我們通常只需計算其下限序列中前面少數個下限。根據我們對一些常被用來測試的視訊所進行的運動估測實驗結果顯示，這個演算法可減少約92％至98％的運算量。此外，我們也將這個演算法應用在一個以視訊為基礎之臉、眼追蹤系統中，可以以視訊頻率（30Hz）的速度即時追蹤使用者臉部、眼睛在影像中的位置。
在本論文中，我們也提出一個快速、多功能的演算法，可以很有效率地進行多種最近鄰居搜尋。在前處理階段時，我們利用聚集式分群法將所有樣本點建構成一個下限樹。每個樣本點與詢問點之間的距離下限就可以利用下限樹中的節點來計算。當所算得之距離下限已經大於最小距離時，該樣本點與詢問點之間的距離計算就可被節省下來。為了減少所真正計算之距離下限個數，我們利用贏者更新搜尋策略來計算下限樹中節點的下限。同時，我們也利用資料轉換技術來更進一步提升搜尋速度。除了能很快地找到最近鄰居之外，我們所提出之演算法也可以很快地找到前 k 個最近鄰居、在某一距離內的所有鄰居、與在最近鄰居附近的所有近鄰。我們的實驗結果顯示，這個演算法可節省非常多的運算量，特別是當詢問點與其最近鄰居間之距離相對遠小於與其他樣本點間之距離時（在許多物體辨識問題中都是這種情形）。當使用 Nayar 等人之物體辨識系統中的影像資料庫時，這個演算法的執行速度是未經加速之徹底搜尋法的一千多倍。這個結果也是目前為止我們所知最快方法的十八倍左右。
在 DNA 序列資料庫搜尋應用中，我們的目標是要在資料庫中找出所有與詢問序列夠相似的序列片段。在本論文中，我們提出一種字串訊號轉換技術，可以將 DNA 序列轉換成多頻道訊號。在不考慮間隙的情形下，計算兩DNA 序列間的相似程度可轉化成計算其相對應訊號間差的絕對值和。論文中所提出之快速樣版比對技術就可被利用來加速資料庫搜尋的過程。除了可以很快地搜尋 DNA 序列資料庫之外，我們這些技術的另一項特點，是可以保證最佳搜尋結果，亦即所有與詢問序列夠相似的序列片段都會被找出來，而沒有任何遺漏。

Template matching has been widely used in image and video compression, visual tracking, stereo vision, pattern classification, object recognition, and information retrieval in database systems. Among the major difficulties of template matching is its high computational cost when dealing with large amount of data. In this thesis we propose techniques that can greatly improve the computational efficiency of template matching while still guaranteeing the optimal search. These techniques are applied to speed up the applications of block matching, nearest neighbor search, and DNA sequence database search.
The key idea of how we speed up the template matching process is the utilization of distance lower bounds. Our goal is to find in a search range the object yielding the minimum distance to the query object. Therefore, calculation of a distance can be skipped if any of its lower bound is larger than the global minimum distance. Since the computation of the distance lower bound utilized in this work costs less than that of the distance itself, the overall process can be accelerated. Moreover, the winner-update search strategy is used to reduce the number of distance lower bounds actually calculated. Several data transformation techniques are also adopted to tighten the distance lower bounds. Thus further speedup is achieved.
For the block matching application in video compression and visual tracking, we propose a new fast algorithm based on the winner-update search strategy which utilizes an ascending lower bound list of the matching error to determine the winner. At each search position, the costly computation of matching error can be avoided when there exists a lower bound larger than the global minimum matching error. The proposed algorithm can significantly speed up the computation of the block matching because (1) computational cost of the lower bound we use is less than that of the matching error itself; (2) an element in the ascending lower bound list will be calculated only when its preceding element has already been smaller than the minimum matching error computed so far; and (3) for many search positions, only the first several lower bounds in the list need to be calculated. Our experiments have shown that, when applying to motion vector estimation for several widely-used test videos, 92% to 98% of operations can be saved. Moreover, we apply the proposed block matching algorithm to a video-based face/eye tracking system. In our experiments, the face and eye positions of the user can be obtained at the video frame rate.
We also propose in this thesis a fast and versatile algorithm which can perform a variety of nearest neighbor searches very efficiently. At the preprocessing stage, the proposed algorithm constructs a lower bound tree (LB-tree) by agglomeratively clustering all the sample points. Given a query point, the lower bound of its distance to each sample point can be calculated by using the internal node of the LB-tree. Calculations of distances from the query point to many sample points can be avoided if their less expensive lower bounds are larger than the minimum distance. To reduce the amount of lower bounds actually calculated, the winner-update search strategy is used for tree traversal. For further efficiency improvement, data transformation can be applied to the sample and query points. In addition to finding the nearest neighbor, the proposed algorithm can also (i) provide the k-nearest neighbors progressively; (ii) find the nearest neighbors within a specified distance threshold; and (iii) identify neighbors close to the nearest neighbor. Our experiments have shown that the proposed algorithm can save substantial computation, particularly when the distance of the query point to its nearest neighbor is relatively very small compared with its distance to most other samples (which is the case for many object recognition problems). When applied to the real database used in Nayar's 100 object recognition system, the proposed algorithm is about one thousand times faster than the exhaustive search. This performance is roughly eighteen times faster than the result attained by Nene and Nayar, whose method is by far the best method we know.
In the application of DNA sequence database search, our goal is to find all the sequence segments in the database that are similar enough (compared to a threshold value) to the query sequence. We propose in this thesis a string-to-signal transform technique which can transform a DNA sequence into multi-channel signals. Without considering gaps, the similar score between two DNA sequences can be calculated as the sum of absolute difference between their corresponding signals. Fast template matching techniques presented in this thesis can then be applied to greatly speed up the search process. Moreover, these techniques guarantee the optimal search. That is, all the sequence segments that are similar enough to the query sequence can be found without any miss.

學號： D83506016
論文名稱：家族競爭演化式方法解最佳化、類神經網路、光學薄膜設計及結構化藥物設計
A Family Competition Evolutionary Approach of Global Optimization in Neural Networks, Optical Thin-film Design, and Structure-based Drug Design
研究生：楊進木 Jinn-Moon Yang
指導教授：高成炎 Cheng-Yan Kao
校院：國立台灣大學
系所：資訊工程學系
學位：博士
學年度： 89
語文： English
頁數： 140
關鍵字: 生物資訊 Bioinformatics
演化式計算 Evolutionary Computation
類神經網路 Neural Networks
光學薄膜設計 Optical Thin-film Design
結構化藥物設計 Structure-based Drug Design
家族競爭 Family Competition
全域性最佳化 Global Optimization
彈性蛋白質結合 Flexible Protein Docking

[論文摘要]
全域性最佳化(global optimization)可應用於各種領域，如工程、自然科學、經濟、生物資訊、及商業等領域上。本論文提出一新的演化式方法論，稱為家族競爭演化式方法(FCEA)，此方法可應用於解全域性最佳化問題及實際的問題上。此方法以家族競爭(family competition)及調適規則(adaptive rules)為基礎，並整合遞減式(decreasing-based)及自我調整式(self-adaptive)的突變(mutation)，使FCEA能具有區域性最佳化及全域性最佳化的搜尋策略。這些策略能緊密結合，因此FCEA具有平衡區域性搜尋及全域性搜尋的能力，使得FCEA解全域性最佳化問題時能獲得好的結果。接著我們應用FCEA於函數最佳化(function optimization)及限制性最佳化(constrained optimization)的問題，實證結果顯示FCEA皆能獲得良好的結果，並優於遺傳演算法(genetic algorithms)、演化式策略(evolution strategies)及演化式規劃(evolutionary programming)等演化式方法。
我們已成功的應用FCEA於類神經網路(neural network)、光學薄膜設計(optical thin-film design)及結構化藥物設計(structure-based drug design)等實際的問題上，並獲得良好的成果。在類神經網路學習上，FCEA可訓練向前回饋式(feed forward)類神經網路解分類問題(classification benchmarks)，如雙螺旋問題(two-spiral problem)及採礦聲納問題( sonar classification)等。FCEA也可訓練回饋式 (recurrent)類神經網路解人工智慧的問題，如人工螞蟻(artificial ant problems)及規則化語言辨識(regular language recognition)等。接著我們設計FCEA成為光學薄膜設計的結合方法(synthesis method)，FCEA已成功設計反反射薄膜問題(antireflection coatings)、光束分歧器(beam splitter)、窄頻濾波(narrowband filter)、及邊界濾波( edge filter)等四種最重要的光學薄膜設計問題。光學薄膜設計能廣泛的應用於各種重要的領域上，如科學器具製造、醫學、及太空科學等。最後FCEA應用於彈性蛋白質結合(flexible ligand docking)問題上，此問題是結構化藥物設計的重要課題。
FCEA在上面五種應用領域上皆能獲得令人滿意的結果，因此我們認為FCEA具有一些良好的特性，我們也分析FCEA的收斂特性、搜尋行為及參數設定等特性。FCEA解全域性最佳化問題時具備彈性和穩定性，因此我們相信FCEA是有效之全域性最佳化的方法論。
Global optimization problems arise in many practical applications, such as engineering, natural sciences, economics, bioinformatics, and business. In this dissertation, a new evolutionary algorithm, called family competition evolutionary approach (FCEA), is proposed not only as the answer to global optimization, but also to be used for several practical applications. Based on family competition and adaptive rules, the proposed approach consists of global and local strategies by integrating decreasing-based mutations and self-adaptive mutations. These smoothly integrated strategies enable FCEA to balance the exploration and exploitation to achieve robust performance for global optimization. FCEA is then applied to certain areas of global optimization such as the
function optimization and general constrained optimization problems. The experiments show that the proposed approach is more robust than other comparative evolutionary algorithms, including genetic algorithms, evolution strategies, and evolutionary programming.
FCEA has produced promising results in a number of applications, including training neural networks, optical thin-film coatings, and flexible ligand docking. For neural networks, FCEA is able to train feedforward neural networks for classification benchmarks, such as two-spiral problem and sonar classification. FCEA also gives promising recurrent neural networks for artificial intelligence problems, such as artificial ant problems and regular language recognition. FCEA is a good synthesis answer for the most important thin-film designs, including antireflection coatings, beam splitter, narrowband filters, and edge filters. Optical thin-film coatings have numerous remarkable applications in many branches of science and technology, such as scientific instrument manufacturing, spectroscope, medicine, and astronomy. Finally, it is verified that FCEA is able to generate low-energy solutions for flexible ligand docking problems, the molecular recognition between two molecules, which are are important for structure-based drug design.
With the encouraging results shown, FCEA can imply certain characteristics. This thesis has also analyzed the global convergence property, search behaviors, and the parameter setting of FCEA. We believe that the flexibility and robustness of FCEA make it an effective tool for global optimization problems.
學號： N28841236
論文名稱：都市移動環境下人體耦合效應對無線行動通訊性能影響之電腦模擬計算
Computer Simulation of the Operator's Body Effects on Communication Performance of the Portable Radiophone in Urban Mobile Environments
研究生：林福林 Fu-Lin Lin
指導教授：莊惠如 Huey-Ru Chuang
校院：國立成功大學
系所：電機工程研究所
學位：博士
學年度： 88
語文： English
頁數： 103
關鍵字：移動通訊 mobile communication
人體耦合效應 human body coupling effect
交叉極性鑑別量 cross polarization discrimination
改良式都卜勒功率頻譜法modified Doppler power spectrum method
直接分離式多重路徑法 direct discrete multipath method
錯誤向量量度 error vector magnitude
[論文摘要]
本論文探討，都市移動環境下，無線通訊手機天線靠近人體狀況時，對行動通訊性能影響之電腦模擬計算。論文提出改良式都卜勒功率頻譜(MDPS)法、及直接分離式多重路徑(DDM)法來分析並模擬計算，通訊性能評估係架構在錯誤向量量度(EVM)及位元錯誤率(BER) ，電腦模擬使用之調變系統為數位調頻(digital FM)及π/4-DQPSK。MDPS法結合了電波在都市行動環境下之交叉極性鑑別量(XPD) 、及人體對手機天線場型之影響，以產生對應的等間隔都卜勒功率頻譜，將此功率頻譜開根號，並乘上複數白色雜訊，透過反向傅利葉轉換(IFFT)即可得到對應的等效低頻殘衰(fading)信號，再與數位調變訊號相乘，並加上相加性白色高斯雜訊(AWGN)即完成此頻道模型。DDM法則是假設:進入手機天線之分離多重路徑電波，每一路徑電波隨機對應到某一入射角度，由於人體對手機天線場型之影響，其增益/衰減量亦隨著入射角度而改變，並假設其入射波之極化角度呈現a-profiler機率密度分佈，機率參數與XPD有關; 最後將多重路徑訊號直接相加，並加上相加性白色高斯雜訊(AWGN)即完成此頻道模型。配合適當的數位調變訊號，計算模擬通訊EVM及BER之性能，如此可評估瞭解在無線都市行動通訊中，人體耦合效應對通訊品質的影響，對天線/射頻設計及鏈路預估皆有相當的幫助。
This thesis presents detailed analysis and computer simulation of the influence of the operator's body on the performance of the portable radiophone in urban mobile environments. An approach called modified Doppler power spectrum (MDPS) method is proposed to study this problem. This approach combines the cross polarization discrimination (XPD) resulted from randomly-oriented scatterers as well as reflectors, and the cross power patterns induced by the operator's body. To validate the results of the MDPS method, a second approach called direct discrete multipath (DDM) method is also presented. It assumes that the multipath is discrete, the incident waves are distributed with an uniform distribution, and the polarization angle are distributed with an a-profile probability density function (PDF). Two modulation schemes, digital FM and π/4-DQPSK, are used in the computer simulation. The performance evaluation is based on the error vector magnitude (EVM) and bit error rate (BER). Computer simulation results of communication performance of the portable radiophone influenced by the human body are useful for the antenna/RF design and the link budget consideration of the portable wireless communication systems.
學號： 834334
論文名稱：內涵式音樂資訊查詢與分析
Content-based Music Information Retrieval and Analysis
研究生：徐嘉連 Jia-Lien Hsu
指導教授：陳良弼 Arbee L.P. Chen
校院：國立清華大學
系所：資訊工程學系
學位：博士
學年度： 89
語文： English
頁數： 108
關鍵字：內涵式音樂資訊查詢 Content-based Music Information Retrieval
音樂特徵擷取 Music Feature Extraction
音樂資料庫 Music Databases
重覆樣型 Repeating Patterns
效能分析 Performance Study
索引與查詢處理 Indexing and Query Processing
[論文摘要]
在本篇論文中我們首先探討內涵式音樂資訊查詢的技術，包括：音樂物件表示法（representation）、相似度衡量（similarity measure）、以及索引和查詢處理。在音樂物件的表示法，我們介紹三種編碼方法（coding scheme）、包括：chord、mubol和music segment，和其相似度衡量的計算式。針對索引和查詢處理的技術，我們歸納suffix tree、n-gram和augmented suffix tree等方法，並進一步做定性的分析和討論。
音樂資訊查詢的各種技術，我們規劃並執行Ultima project，建立一個測試平台（platform）來評估。在這開放式的平台，我們針對各個索引及查詢處理的方法，執行一系列的實驗。特別針對方法的效率（efficiency）和效能（effectiveness），根據定性的討論和定量的實驗數據，整理了關於音樂資訊查詢技術的分析研究報告。
內涵式音樂資訊查詢處理的技術，可以應用在查詢（searching）、分類（classification）、與推薦（recommendation）等方面，其中，我們也深入探討音樂資料的特徵擷取（feature extraction）的問題。在音樂物件中，一段重複出現的音符，我們定義為「重覆樣型（repeating pattern）」。重覆樣型是音樂物件中的一項重要特徵。例如，樂曲中的「主題」就是重覆樣型。針對如何在音樂物件中找出重覆樣型的問題，我們提出兩個方法。在第一個方法，我們設計correlative matrix的資料結構和演算法，能夠有效率地擷取音樂物件中的重覆樣型。在第二個方法，我們定義string-join的方法和RP-tree的資料結構，也能夠有效率地擷取重覆樣型。同時，我們也做實作這兩個方法，並就效率和效能的方面來做分析、比較。
更進一步的，從擷取重覆樣型的問題，延伸到擷取「相似重覆樣型（approximate repeating pattern）」。我們介紹兩個在序列資料（sequence data）中擷取相似重覆樣型的應用。根據三種相似類型（包括：longer_length、shorter_length和equal_length），我們明確地定義了相似重覆樣型的問題。其中，針對longer_length這類型問題，我們利用cut和pattern_join的方法、提出一演算法來解決這問題。另外，特別針對長的重覆樣型（long pattern），我們利用generalized_pattern_join的方法，能更有效率在序列資料中擷取長的重覆樣型。同樣的，我們也以實作來驗證這演算法的效率。
In this dissertation, we first discuss the techniques used in content-based music information retrieval. The techniques include the methods to represent music objects, the similarity measures of music objects, and indexing and query processing for music object retrieval. To represent music objects, we introduce three coding schemes, i.e., chord, mubol, and music segment. Various similarity measures are then presented, followed by various index structures and the associated query processing algorithms. The index structures include suffix tree, n-gram, and augmented suffix tree. A qualitative comparison of these techniques is finally performed to show the intrinsic difficulty of the problem of content-based music information retrieval.
We also initiate the Ultima project which aims to construct a platform for evaluating various approaches of music information retrieval. Three approaches with the corresponding tree-based, list-based, and (n-gram+tree)-based index structures are implemented. A series of experiments has been carried out. With the support of the experiment results, we compare the performance of index construction and query processing of the three approaches and give a summary for efficient content-based music information retrieval.
The feature extraction problem for music objects is also studied to support content-based music information retrieval in searching, classification, recommendation, and so forth. A repeating pattern in music data is defined as a sequence of notes which appears more than once in a music object. The themes are a typical kind of repeating patterns. The themes and other non-trivial repeating patterns are important music features which can be used for both content-based retrieval of music data and music data analysis. We propose two approaches for fast discovering non-trivial repeating patterns in music objects. In the first approach, we develop a data structure called correlative matrix and its associated algorithms for extracting the repeating patterns. In the second approach, we introduce a string-join operation and a data structure called RP-tree for the same purpose. Experiments are performed to compare these two approaches with others. The results are also analyzed to show the efficiency and the effectiveness of our approaches.
Further, we extend the problem of finding exact repeating patterns to the one of finding approximate repeating patterns. First, two applications are introduced to motivate our research of finding approximate repeating patterns from sequence data. An approximate repeating pattern is defined as a sequence of symbols which appears more than once under certain approximation types in a data sequence. We define three approximation types, i.e., longer_length, shorter_length, and equal_length. The problems of finding approximate repeating patterns with respect to the three types are specified. By applying the concept of 'cut' and 'pattern_join' operator, we develop a level-wise approach to solve the problem of finding approximate repeating patterns with respect to the type of longer_length approximation. In addition, we extend the pattern_join operator to the generalized_pattern_join operator for efficiently finding long patterns. The performance study shows that our approach is efficient and also scales well.

回得獎名單