處理原始定序資料之圖形分割演算法與硬體加速設計

An Algorithm and Hardware Accelerator Design for Image Segmentation of Raw Sequencing Data

黃筱漩(Xiao-Xuan Huang)

指導教授 ： 盧奕璋

國立臺灣大學/電機資訊學院/電子工程學研究所/碩士(2011年)

https://doi.org/10.6342/NTU.2011.10165

摘要

在本篇論文中，我們提出了一個適用於循環陣列定序系統之螢光影像處理的演算法。在循環陣列定序實驗影像中，部分平台輸出影像裡的螢光點位置為隨機分布，且循環陣列定序實驗之螢光點尺寸很小，增加了螢光點的辨識難度。
考慮目前已發表的影像處理方法，均值移動演算法具有無母數特性，不需事先輸入亮點數量或亮點位置等參數，較適合上述的循環陣列定序實驗影像問題。然而，均值移動演算法中，同等地將灰階值與空間資訊視為向量維度，使像素值與像素位置兩資訊之間的相對比重不明確，而且運算相當消耗資源。
因此，我們根據均值移動演算法的概念，提出步階移動演算法。不同於均值移動算出實際均值，步階移動藉由觀察像素與其各個方向相鄰像素的相關度，決定該像素點移動方向，再循著方向得到該點的模點位置，達到保留邊緣的平滑與去雜訊的效果，使之適用於循環陣列定序實驗的亮點辨認。
為加速此影像處理，我們將此演算法實現在管線架構的硬體上。以TSMC90製程實現，晶片尺寸為312823um2，核心尺寸為159378um2，運作頻率設計為100MHz。

關鍵字

定序影像處理 ； 均值移動 ； 步階移動 ； 硬體架構實現

並列摘要

In this study, we proposed an algorithm and hardware design for image segmentation of raw sequencing data. On some next generation sequencing platforms, fluorescent spots are randomly distributed and the sizes of these spots are small, which make spot segmentation more challenging.
Among various image segmentation methods, Nonparametric Mean Shift algorithm is suitable for these problems since it does not require certain parameters such as the total number or the rough positions of the spots in advance. However, Mean Shift algorithm does not treat color space and spatial coordinates differently, but concatenates them into a joint spatial-color domain, in which the relative weights between the color space and spatial coordinates need to be specified empirically. Moreover, the Mean Shift algorithm is computationally intensive, which is also a problem.
Therefore, based on the concept of Mean Shift algorithm, we proposed a modified version, Step Shift algorithm. The direction of each shift is obtained from the correlation between each pixel and its neighbors, and the shifts repeat until reaching the mode of the pixels. The process smoothes and removes image noise while preserving all the edges. Consequently, this algorithm is suitable for image segmentation.
To speed up the process for future real-time applications, we also implemented a hardware processor based on our algorithm. The chip is implemented with TSMC 90nm technology. The chip size is 312823 um2, and the core size is 159378um2, and the chip operates at 100MHz.

並列關鍵字

Sequencing Image ； Mean Shift ； Step Shift ； Hardware Implementation

參考文獻

[1] J. Shendure, R. D. Mitra, C. Varma, and G. M. Church, "Advanced sequencing technologies: methods and goals," Nature Reviews Genetics, vol. 5, pp. 335-344, 2004.

[2] J. Shendure and H. Ji, "Next-generation DNA sequencing," Nature Biotechnology, vol. 26, pp. 1135-1145, 2008.

[Online]. Available: http://rana.lbl.gov/EisenSoftware.htm

[7] R. Adams and L. Bischof, "Seeded region growing," IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 16, no. 6, pp. 641–647, Jun. 1994.

[8] L. Vincent and P. Soille, "Watersheds in digital spaces: an efficient algorithm based on immersion simulations," IEEE Transactions on Pattern Analysis and Machine Intelligence, vol.13, no.6, pp.583-598, Jun 1991.