Browsing by Author "Lin, Cheng-Hung"

Now showing 1 - 20 of 35

以圖形處理器加速尺度不變特徵轉換演算法
(2013) 蔡睿烝; Tsai, Ruei-Jen
圖像內容檢索（CBIR）為一種電腦視覺技術，使用圖像的內容在大型資料庫中進行檢索，如顏色、形狀、紋理等而非關鍵字、標籤或其他描述方法。許多圖像運算與電腦視覺的技術皆需要擷取圖像中的內容，大部分皆透過尺度不變特徵轉換演算法（SIFT）來達成。尺度不變特徵轉換被廣泛應用於物件辨識、圖像拼接、立體對照、描述圖像特徵等。在特定的應用如圖像內容檢索中，特徵點擷取被視為預處理程序，之後的特徵點比對便成為運算最密集的程序。圖形處理器（GPU）因其在大量資料平行運算的卓越能力收到關注，因此，本研究提出基於圖形處理器平行化的尺度不變特徵轉換演算法，藉此加速線性搜尋法與k-近鄰搜尋法。於實驗結果中，相較於傳統的最近鄰居搜尋法，本研究得到22倍的加速；而相較於傳統的k-近鄰搜尋法，得到11倍的加速。
以圖形處理器加速近似字串比對之位元平行演算法
(2015) 王冠鈜
近似字串比對被廣泛運用到很多領域，例如：網頁搜尋、網路入侵偵測系統、網路安全、去氧核糖核酸序列匹配等。近似字串比對可在輸入字串與樣式字串間容許因為插入、替代、刪除等操作所造成的誤差。因為近似字串比對是一種資料密集的運算，對於大數據的處理，加速近似字串比對成為非常重要的關鍵。本研究提出階層平行化的架構並實現於圖形處理器，以加速位元平行演算法。階層平行化的架構包括兩個階段。第一個階段使用多串流操作，用來隱藏記憶體IO的延遲，而第二個階段運用圖行處理器來加速位元平行演算法。位元平行演算法相較於CPU的平行化版本，GPU版本可獲得約3.5倍效能的改善。實驗結果顯示，相較於其他相關研究，本研究可以獲得5倍的改善。
以多圖形處理器加速近似字串比對
(2012) 張浩平; Chang, Hao-Ping
字串比對在許多領域中被廣泛運用，例如網路入侵偵測系統、網際網路搜尋、去氧核糖核酸序列比對等等；其中，字串比對可區分為固定字串比對與近似字串比對兩類。固定字串比對是指找出所有字串樣式於輸入文字中出現的位置，所有字串樣式必須精確的比對，不容許任何錯誤；而所謂近似字串比對是指所搜尋的字串樣式則可經由插入、刪除及替代等有限次數的動作，轉換成輸入文字中的某部分。近似字串比對的演算法可區分為dynamic programming與bit-parallelism；Dynamic programming需經龐大運算及記憶體空間記錄誤差值，故在處理大量資料時，將為此演算法之瓶頸；反之，bit-parallelism運用邏輯運算子模擬非確定有限狀態自動機進行比對，速度快且節省記憶體。近似字串比對的運算量大且非常耗費時間，尤其在針對大量的輸入文字比對大量的字串樣式時，其耗費的時間更為明顯。本研究將分析並實現bit-parallelism與dynamic programming於NVIDIA GPU上，實驗結果顯示在處理2Gbytes的輸入文字時，執行於單一個GPU的bit-parallelism較執行於單一執行緒CPU版本的bit-parallelism快上7倍的加速。本研究並進一步透過openMP連結多個GPU的加速，其結果顯示在處理2Gbytes的輸入文字時，以2個GPU加速之bit-parallelism較執行於單一執行緒CPU版本的bit-parallelism快上10倍的速度。
以多核心圖形處理器加速影像處理之研究
(2016) 周文瑞; Chou, Wen-Jui
本論文研究以多核心圖形處理器(Multicore Graphic Processing Units)加速影像處理演算法，我們以全向圖(omnidirectional pictures)轉換成全景圖(panoramic pictures)及車牌辨識(vehicle license plate recognition)系統為例，提出平行演算法並以多核心圖形處理器進行相關演算法加速。論文首先針對橢圓拋物曲面全向圖轉換成全景圖的演算法進行平行化研究，本論文提出了一個階層式的平行架構包含資料平行(data parallelism)與任務平行(task parallelism)兩個階層，其中資料平行階層是透過執行圖形處理器的大量執行緒平行轉換每個像素從全向圖移轉至全景圖，而任務平行階層是透過圖形處理器多串流技術(multiple stream)，以管線化(pipelining)的方式平行執行多個影像的轉換。任務平行可以藉由重疊影像處理器的核心運算與資料傳輸的執行時間來改善整體的效能。實驗結果顯示相較於CPU，透過圖形處理器，我們可以得到6.33倍的改善。論文第二部分，我們針對車牌辨識系統進行平行化研究，一個車牌辨識系統主要包含車牌定位、車牌校正、文字切割與文字辨識等四大步驟。首先在車牌定位部分，我們透過灰階轉換、直方圖等化、二值化、輪廓萃取與剛性物體偵測之核心演算法取得車牌的位置，然後在車牌校正方面，我們使用仿射轉換中的單映性以校正歪斜的車牌。在文字分割方面，我們利用輪廓萃取及邊緣偵測將文字與車牌面積進行計算，並將車牌中的文字分割取出。最後在文字辨識部份，我們利用樣板比對法(template matching)作為文字辨識的方法，為了縮短辨識系統計算的時間，我們透過圖形處理器加速車牌文字辨識的計算速度相較於CPU，我們可以得到100倍的改善。關鍵字：多核心圖形處理器、影像處理、全景圖轉換、車牌定位、車牌辨識
以快慢雙流圖卷積神經網路架構實現骨架動作辨識
(2021) 周柏永; Chou, Po-Yung
本論文討論骨架動作辨識任務，此任務在過去的論文中較少討論到時間特徵的學習，大多研究如何學習到更好的空間特徵，而就過去在動作辨識任務中的經驗，時間維度對於動作辨識任務的影響是巨大的，因此我們聚焦在時間維度對此任務之影響，為此提出了一個雙流網路架構來融合不同時間尺度的輸入，以此方法來提取靜態與動態特徵，接著我們進一步針對圖卷積內部的鄰接矩陣作改良，將其設計為可以針對不同時間時間區段學習，進而學習到更精準的骨架相關性，從實驗結果可以得知，混和不同時間尺度特徵可以有效增加準確率，在NTU RGB+D能夠到達94.8%的準確率，經過改良鄰接矩陣後更是能到達95.2%的準確率，由此可以驗證，時間尺度上的特徵對於骨架動作辨識任務是相當重要的。
以輕量化卷積神經網路為核心之自動抄錶系統
(2020) 郭冠毅; Kuo, Kuan-Yi
隨著物聯網技術的蓬勃發展，政府逐漸淘汰了傳統電錶，開始了智能電錶的時代。然而，更換智能電錶的價格昂貴且面臨通訊不良等問題，導致智能電錶佈建緩慢，我們的想法是開發一種低成本的解決方案，該解決方案使用帶有攝影鏡頭的邊緣設備自動辨識傳統電錶，然後將辨識的值上傳到雲端。過去已有研究通過傳統的圖像分割方法自動讀取錶盤，但是由於傳統的電錶大多設置在遮蔽性高、光線昏暗、灰塵多的環境中，因此對於不清晰的電錶圖像，傳統方法難以獲得良好的辨識結果。在本文中，我們提出了一種基於輕量化卷積神經網路的自動讀錶器並實現在邊緣設備上，為了減輕佈建難度和提高錶盤辨識的準確率，我們所提出的錶盤讀取器具有自動調整傾斜錶盤圖像的能力。實驗結果顯示，相較於其他相關方法，所提出的輕量化卷積神經網路在分割錯誤，誤報和運行時間方面取得了顯著改善。
使用監督式K平均分群法與支持向量機之階層式車牌辨識系統
(2017) 劉暐辰; Liu, Wei-Chen
近年來運用車牌辨識技術於路口監視器吸引許多注意，它是實現智慧城市重要的一環，用來偵測肇事或遺失的車輛。過去車牌辨識已經成熟的運用在停車場的管理系統，達到停車免票證，停車位置記錄的功能。不同於停車場固定拍攝角度與光線的環境，運用於路口監視器的車牌辨識會遭遇因為拍攝角度、多車道偵測、車輛行駛速度與環境光影等因素而造成字元辨識困難。除了上述環境條件以外，字元辨識常見挑戰還包含：車牌模糊、髒汙、相異字體、相近字元等變因。本論文提出一個以SVM分類器為核心之車牌辨識系統，系統分為三個部分，包含車牌偵測、字元分割，與字元辨識。車牌偵測的方式，使用Support Vector Machine (SVM)分類器。SVM分類器的目的為分類車牌及非車牌區域，而本研究使用以Histogram of oriented gradient (HOG)為訓練特徵的SVM分類器。為節省計算時間，過程使用圖形處理器(GPU)加速SVM計算。實驗結果顯示，我們的系統在三車道內擁有97.69%的車牌偵測成功率。抓取車牌影像後，將車牌上的字元分離，此步驟透過水平投影去除車牌上下方非字元排列之其他區域，再以垂直投影方法，分離車牌上字元。最後字元辨識部分，本論文提出一個結合supervised K-means與Support Vector Machine的階層架構，先透過supervised K-means，將辨識字元分成子群，對於子群的字元再透過Support Vector Machine進一步分類與辨識，可以降低SVM的複雜度並提升SVM的辨識率。實驗結果顯示我們所提出的階層架構，可達98.89%之字元辨識準確率，相較於純粹使用SVM的車牌辨識技術，我們得到3.6%的辨識率改善。
具有自動點雲預處理的即時點雲動作辨識系統
(2024) 賴彥廷; Lai, Yen-Ting
本論文討論了點雲動作辨識系統的自動化預處理。點雲動作辨識的優點是受到光照和視角變化的影響較小，因為它關注的是物體的三維位置而不是單純像素值。即使在複雜和黑暗的環境中，也能實現強大的識別性能。此外，點雲動作辨識在機器人、虛擬實境、自動駕駛、人機互動、遊戲開發等領域也有廣泛的應用。例如，理解人類行為對於機器人技術中更好的互動和協作至關重要，而在虛擬實境中，它可以捕捉和再現用戶動作以增強真實感和互動性。為了建立運行穩定的點雲動作識別系統，通常需要過濾掉背景和不相關的點，從而獲得乾淨且對齊的點雲數據。在過去的多數方法中，點雲過濾和動作識別通常是分開執行的，很少有系統一起運行。在本文中，我們提出了一種方法，使用戶能夠直接從 Microsoft Azure Kinect DK 取得點雲資料並執行全面的自動化預處理。這將能產生沒有背景點的更乾淨的點雲數據，適合用於動作辨識。我們的方法利用 PSTNet 進行點雲動作識別，並在透過自動預處理獲得的資料集(包括 12 個動作類別)上訓練模型。最後，我們開發了一種結合自動點雲預處理的即時點雲動作辨識系統。
利用圖形處理器與階層式平行技術加速網路入侵偵測系統
(2018) 謝政宏; Hsieh, Cheng-Hung
目前網路入侵偵測系統大多採用多重樣式字串比對的方式，是否含有網路攻擊與異常的封包，透過比對數以千計的攻擊特徵來偵測封包內容。隨著大數據時代的來臨，網路速度與攻擊活動的增加，多重樣式字串比對面臨效能與吞吐量的不足，導致許多封包沒有處理且遺失。為了改善網路入侵偵測系統的效能與吞吐量，本論文提出階層式平行架構，利用多張圖形處理(Multi-GPU)與三種不同層面的平行技術加速網路入侵偵測系統。階層式平行架構由三層不同的平行技術所組成，從上至下來看，第一層實現資料平行(Data Parallelism)於多張圖形處理器；第二層將管線化排程(Pipeline Schedule)實現於個別圖形處理器中，屬於任務平行(Task Parallelism)；第三層則是採用資料平行的技術，優化 Aho-Corasick 演算法。本論文實驗結果顯示，採用四張圖形處理器 Nvidia Titan X 實現於階層式平行架構，總系統吞吐量可高達 70 Gbps，與傳統使用於 Snort 中的 Aho-Corasick 演算法相比，可高達四十倍的改善倍率。當圖形處理器的數量增加，總系統的吞吐量也會隨之增加。除此之外，本論文採用完美雜湊(Perfect Hashing)的方法，壓縮傳統 Aho-Corasick 的狀態機，減少在 Snort 中 99.2%多重樣式字串比對的記憶體使用量，最後本論文將提出的階層式平行架構實現於開源網路入侵偵測系統 Snort。
基於 Transformer 用於物件狀態分析之關聯度計算模型
(2023) 黃柏穎; Huang, Po-Ying
籃球分析系統是現代籃球運動中不可或缺的工具，其中判斷持球者更是重要的任務之一。傳統的做法是先透過物件檢測取得球員與籃球的檢測框，再透過球員與籃球的幾何關係，例如計算球員與籃球的Intersection over Union，或計算球員與籃球的中心座標距離，來判斷球員是否持球。然而我們發現這樣的做法很容易發生誤判，肇因於籃球比賽中存在著複雜的球員重疊情況，幾何關係無法準確判斷球員是否持球，從而出現誤判的情況，這對於分析持球者的任務來說帶來了極大的挑戰。為了解決上述問題，我們提出了「基於Transformer用於物件狀態分析之關聯度計算模型」，藉由加入球員的骨架資訊做為動作特徵，透過self-attention的方法來學習球員與籃球之間彼此的關聯性。實驗結果顯示，我們的架構可以透少量的訓練資料，得到92.3%的持球準確率，這個結果超越了傳統演算法85.1%的持球準確率。最終，更在非訓練使用之測試資料集獲得95.4%的持球準確率。
基於Mask R-CNN之傾斜角度車牌識別系統
(2019) 李穎; Li, Ying
在過去幾年中，車牌辨識系統已經廣泛用於停車場。為了容易識別車牌，停車場中使用的傳統車牌識別系統具有固定的光源和拍攝角度。對於特別傾斜的角度，例如使用超廣角鏡頭或魚眼鏡頭拍攝的車牌影像，車牌特徵變形可能特別嚴重，以致於使用傳統車牌辨識系統的辨識效果不良。本論文中，我們提出了一種基於Mask R-CNN的三階段車牌辨識系統，可用於各種拍攝角度和更傾斜的影像。實驗結果表明，該架構可識別水平傾斜角度超過0~60度的車牌，mAP可達91％。與使用YOLOv2模型的方法相比，本論文提出使用Mask R-CNN的方法在辨識傾斜45度以上的字元方面取得了重大進展。
基於Transformer物件關聯模型應用於籃球賽事分析
(2024) 陳柏諺; Chen, Po-Yen
在籃球賽事分析中，準確識別持球者和判斷得分時機對於確定得分者是關鍵挑戰。傳統的分析方法，比如物件重疊度和相對距離測量，往往在識別持球和進球時刻面臨較高的誤判風險。為了解決這一問題，我們對本團隊先前提出的Transformer-based Object Relationship Finder（ORF）架構的輸入特徵進行了改進，重點關注了幾個關鍵因素：與球密切相關的球員、球員的姿勢，以及不同的物件類型。這一策略顯著提高了架構在識別複雜動作和搶球情況下的準確度，使得持球者的識別準確率從原來的80.79%提升至86.18%，有效地展示了精準特徵選擇的重要性。此外，我們還利用Transformer-based Object Relationship Finder架構來識別進球時機，並結合最後接觸球的持球者信息，從而有效地判斷得分者，相較於傳統方法我們將得分者準確率從63.89%提高到了87.50%，這一成績突顯了Transformer-based Object Relationship Finder在籃球分析中的強大效能和廣泛應用前景。最後，我們開發了一款整合了這些技術的應用工具。這不僅讓教練和分析師能更全面地理解比賽情況，還為未來的籃球研究和技術開發提供了堅實的基礎。
基於光學相干斷層掃描血管造影視網膜圖像的視覺預測多流網路
(2021) 謝承璋; Hsieh, Cheng-Chang
視網膜前膜(Epiretinal Membrane，ERM)是一種慢性眼疾，肇因於視網膜的表面出現微細缺口，導致黃斑部增生一層纖維薄膜而影響視力。黃斑前膜手術為最典型治療方法，惟部分患者在手術後的視力恢復效果不佳，重要的因素之一是缺乏執行內限界膜(Inner Limiting Membrane，ILM)剝離時機的判斷，而此診斷障礙乃因為缺乏判斷黃斑前膜是否影響視力的標準，而導致醫生無法做出診斷，並於早期進行內限界膜剝離手術以提升術後的視力恢復。為了解決這個問題，本論文提出多種多流(multi-stream)神經網路，透過光學共輒斷層掃描(optical coherence tomography，OCT)、非侵入性光學共輒斷層血管掃描 (optical coherence tomography angiography，OCTA)、眼底螢光血管攝影(fundus fluorescence angiography，FFA)進行視力預測。我們收集454位患者上述三種影像並標記其視力資訊以訓練我們提出的多流神經網路，並以不同的影像輸入測試網路的效能。實驗結果顯示透過FFA全層、淺層、深層等三種影像在黃斑前膜患者的視力診斷中達到90.19%的準確性。最後，我們利用梯度權重類別活化映射(gradient-weighted class activation map，Grad-CAM) 可視化視力在OCT、 OCTA和FFA之間的特徵，幫助醫生進行診斷。
基於半監督式骨架動作辨識模型之圖資料增強方法
(2023) 黃弘智; Huang, Hung-Chih
近年來，基於骨架資訊之骨架動作辨識在圖卷積架構的導入下獲得顯著的效能提升。不同於傳統RGB影像動作辨識，骨架動作辨識的輸入資料為人體的關節點資訊，這種輸入資料的特點為不易受到現實中的背景雜訊影響，進而取得更有效率及精確性的動作辨識結果。然而，製作人體關節點的資料需要大量人力資源，這導致在現實應用環境中缺少標註樣本資料進行訓練。另外，採用預訓練好的模型亦需要花費相當的時間成本進行參數調整，成為應用的一個瓶頸。為此，本研究中我們提出多種骨架動作資料的資料強化方法以解決少量標註資料的問題，並結合半監督學習策略有效利用未標註樣本，進而提高骨架動作辨識模型在少量標註資料環境下的辨識能力。我們提出的資料強化方法能在低成本的額外運算下，有效提高資料的多樣性，使模型可以提取更多不同的特徵資訊。在半監督學習策略中，我們採用兩種強度不同的資料增強方法作為輸入，透過計算經不同強化方法產生的辨識結果之相似度作為損失函數以強化模型對於辨識結果的一致性，並期望模型可以學習更多關於辨識決策的有效資訊。此外，我們還透過調整非標註資料加入網路訓練的時間點，在確保準確率的同時，也顯著地降低了模型訓練所需時間。實驗結果顯示，我們提出的架構在NTU RGB+D大型資料集的低資料環境實驗中，達到了84.16%的準確率，相較於原始方法的77.5%的準確率，提升了6.66%；研究結果表明我們所提出之方法在少量標註資料的情況下可以有效提升模型之辨識準確率及泛化能力，為解決實際應用中資料稀缺和降低模型的調整成本問題中提供一個有效的解決方案。
基於最佳化演算法的類神經網路剪枝策略
(2021) 鐘暘; Chung, Yang
隨著深度學習領域不斷的進步，類神經網路的架構比起以往擁有更多的參數量和記憶體的使用量，相對地對於硬體的要求也就更高。如何在有限的記憶體和硬體效能中擁有差不多的辨識效能也成為需要被關注的問題之一，而網路剪枝則是最直接能夠解決參數量過大問題，將網路中不必要的參數刪除，就能夠省去大量的記憶體空間。過去在網路剪枝當中，通常的策略都是將較小的權重刪除。這些網路剪枝方法的主要策略都是假設網路裡較小的權重，對於網路本身的影響較小，而可以被捨棄掉。但是我們認為這個假設對於神經網路而言並不是絕對的。在本篇論文中我們假設小權重也有可能會是重要權重的可能性，我們提出一個最佳化的剪枝策略，在剪枝時不只留下較大權重，還會留下由最佳化策略所挑選出的較小權重，能證明保留網路中重要的較小權重，有益於剪枝網路的準確率，讓剪枝網路能夠在低參數量和高準確度中取得最佳的權衡。實驗結果說明在相較於只留較大權重的做法，透過最佳化的方法留下的較小權重，在相同的剪枝率網路會有更高的準確度。
基於特徵金字塔網路之新型異常圖像偵測系統
(2022) 余佩倫; Yu, Pei-Lun
異常資料偵測在神經網路的安全議題上，是一個值得探討的方向。一旦訓練好的神經網路遇上了無法識別的資料型態，就極有可能發生錯誤的判斷，導致無可挽回的後果，像是自動駕駛以及醫學診斷系統就是其中經典的例子。因此，一個有效的分類器不只應該要能準確的識別原先的類別項目，也要能辨識出不屬於他認知範圍的異常資料。本論文提出一個基於特徵金字塔網路之異常圖像偵測系統。相比起其他異常檢測系統的單一輸入單一預測值，我們將系統結合了特徵金字塔網路，因此針對單一影像輸入，可以輸出多尺度的預測值，透過統整多尺度的預測值，有效地讓系統準確度提升。實驗結果顯示此系統不僅可以保留原先任務需求，且在多個視覺資料集上皆顯示辨識效果有所提升。
基於穩定長期特徵之無空間關係之多目標多相機行人追蹤系統
(2023) 黃鼎傑; Huang, Ding-Jie
多目標多相機行人追蹤系統這項任務的目的是利用多個相機追蹤多個人物。目前的方法通常使用相機位置和畫面作為輸入，首先運用基於線性運動的卡爾曼濾波器對每個相機進行單相機的人物追蹤。同時，在追蹤過程中使用指數移動平均法提取人物特徵，最後利用相機位置和人物外觀特徵進行多相機間的人物匹配。然而，我們發現使用這種卡爾曼濾波器容易發生ID切換(identity switching)的問題。另外，若使用基於相機位置的追蹤系統，當場域切換到相機較多的位置時，需要重新編寫程式邏輯整合相機位置，耗費巨大的成本。如果不使用相機位置作為輸入，如何提取穩定且有效的人物外觀特徵就變得尤為重要。因此，在本研究中，我們提出了一種與過去方法不同的卡爾曼濾波器和一種新的長期特徵存儲方法，可以生成更穩定的外觀特徵，從而解決了使用指數移動平均法存儲的長期特徵可能導致的ID切換問題。此外，在匹配過程中不使用相機位置資訊，使得該系統更容易移植。為了評估我們提出的方法，我們建立了一個自有資料集，包含約40000幀、1080p、30fps的影片。實驗結果表明，我們的方法能夠更好地解決上述問題。在多相機追蹤方面，我們的IDF1性能指標相較於過去方法提升了約15%；在單相機追蹤方面，我們成功恢復了75%被交換的ID。
基於高速球種定位系統之深度集成與漸進訓練策略
(2024) 陳尚德; Chen, Shang-De
近年來，將體育賽事與深度學習架構相結合在應用層面引起了廣泛地關注，其中智能裁判、戰術規劃等結合神經網路進行輔助之需求日漸增加。在相關的應用當中，深度學習架構通常扮演輔助角色，以幫助運動員或團隊針對比賽過程進行分析，從而全面了解當前之比賽狀態，其中又以球類運動為甚。為執行高效之戰術分析，在球類運動當中運動員和球種的位置檢測具有重要意義，其精確檢測與否將大幅影響整體之戰術規劃結果。然而，部分球種之快速、體積小且不易預測的特性使過往常見之物件偵測架構不易進行定位，成為了一個挑戰性的問題。為此，於本文當中我們援引生成網路架構進行高速球種定位系統設計，並提出 ADEPTS 策略以針對該系統之訓練策略進行最佳化。ADEPTS 結合了多尺度特徵融合和漸進式學習方法，使網路能夠更準確地捕捉高速球運動的軌跡特徵，同時提高了訓練效率。研究結果表明，我們設計之高速球種定位系統可取得高定位精度，且 ADEPTS 的加入可以額外減少該架構約 26.14%的訓練時間，這使其成為實際應用中的實用和有效解決方案。
實現於圖形處理器上的雙字元平行字串比對演算法
(2017) 廖重淯; Liao, Chung-Yu
Aho-Corasick 演算法已經被廣泛使用於網路入侵檢測系統（Network Intrusion Detection System，簡稱 NIDS），用來檢查網路封包裡數以千計數的惡意代碼片段。為了提高網路入侵檢測系統的性能，許多基於 Aho-Corasick 衍生出來的演算法使用圖形處理器（GPU）或特殊硬體來加速多字串比對，其中一種方法便是增加每週期處理的字元數來提升多字串比對的速度。然而，增加每週期處理的字元數將會遇到兩個主要問題，第一個問題是輸入對齊問題，第二個問題則是儲存狀態轉換表所需的記憶體空間大幅增加。這兩個問題導致多字元比對的方法變得不太可行。在本文中，我們提出了一種適合在圖形處理器上執行的雙字元平行字串比對演算法。而前述的兩個主要問題，本文提出了一個新形態的狀態機來解決輸入對齊問題，並用完美雜湊壓縮狀態轉換表以解決記憶體空間爆炸問題。實驗結果證明所提出的演算法無論在性能或記憶體空間需求方面均優於目前最先進的方法。
實現於圖形處理器的高性能平行位置檢知近似字串比對演算法
(2017) 黃俊程; Huang, Chun-cheng
近似字串比對被廣泛的應用於各種不同的領域。例如：去氧核糖核酸序列搜尋比對、電腦文字輸入校正、文字資料探勘以及垃圾電子郵件過濾等。近似字串比對的設計是用來搜索文件中所有近似字串文字樣式字串及使用者定義的插入、刪除、取代的容許誤差值搜索後的匹配的位置。在眾多被提出的近似字串比對演算法中，位元平行演算法被認定是最適、最有效率的演算法。然而，傳統的位元平行演算法無法同時偵測樣式字串匹配字串的起始及結束位置。除此之外，因應現代多核心處理器的硬體發展，以及叢集運算、雲端運算以及大數據處理的需求。如何加速位元平行演算法成為當今重要的課題。本研究分別提出利用多串流平行和高維度平行這兩種位置偵測近似字串比對方法並利用圖形運算處理器(GPU)來加速演算法。實驗結果顯示，比較高維度平行演算法在圖形運算處理器(GPU)以及CPU的執行效能，圖形運算處理器(GPU)版本無論是在作業系統執行環境或者是在圖形顯示處理(GPU)核心執行的情況，效能皆得到顯著的提升。相較於其他相關研究，本研究所提出的高維度平行的方法達到了 11 至 105 倍的效能改善。最終，我們開發了一個讓使用者可以在線上執行位置偵測近似字串比對並找出所有樣式字串匹配結果起點及終點位置網路服務。