臺灣博碩士論文加值系統

我們使用分散式系統，並使用了三種加速的方式來使程式達到即時處理的速度。三種加速的方法分別是：資料分割、函式分割和管線分割。文中，我們分析了三種加速方法的優、缺點，如資料分割的優點是處理器之間的溝通量非常少，但是只適合使用在演算法只使用了區域性的資料的情況下；功能分割可以將不同性質的工作分配給不同處理硬體使得不同的硬體可以被更充分的利用，但是只適合使用在演算法的工作之間沒有輸出和輸入的相依關係；管線分割的優點是易於分割，且可以大量增加產能，但是只適合用於連續的輸入資料的情況，並且會增加系統的反應時間。最後我們提出一個方法整合此三種分割，利用各種分割的優點互相彌補，使系統的平行化處理的程度達到最高，並且能得到最佳的產能。
電腦視覺的領域中，利用二張影像來計算影像中物體的深度是一件已經被討論許久的技術。而要計算影像中物體的深度必須先計算對應點的相差，但是因為這個技術通常需要大量的計算，而無法達到即時處理的速度，也因此限制了這項技術的應用。為了使這項技術能達到即時處理的速度，我們使用一個有效率的計算相差的演算法和分散式系統來計算影像中對應點的相差。這個演算法使用了兩張經過校正的立體影像和一個特別的資料結構來計算影像中對應點的相差。

We use distributed system and three partition schemes to make program achieve real-time performance. The three partition schemes are data partition, function partition, pipelining partition. In the paper, we analysis the advantages and disadvantages of the three partition, for example, advantage of data partition is the communication cost of processors is less, but the data partition is only suitable for the condition of algorithm only use local data, function partition can assign different task to different hardware, this can make more efficient utilization of hardware, but it can only be used when there are no relation of input and output between tasks. Pipelining partition is easy to applied to program and can raise mass throughput, but is only suitable for successive inputs and pipelining partition will raise the response time of system. At the end, we propose a strategy to integrate three partition schemes to make exploit highest parallelism, and get best throughput.
In the field of computer vision, using two images to compute depth of object in images is a long discussed technique. And before compute depth of objects in images, we must computed disparity of corresponding points, but because of the mass computation of the matching of corresponding points , this technique can not be applied to real-time application, and the application is limited. To compute disparity of corresponding points in real-time, we employ an efficient algorithm and a distributed system to compute depth. The algorithm uses two calibrated images and a special data structure to compute disparity of corresponding points in images.

摘要I
AbstractII
目錄III
第一章：簡介1
第二章：文獻探討6
第三章：資料分割9
3.1 定義9
3.2優缺點和限制11
第四章：功能分割15
4.1 定義15
4.2 優缺點和限制16
第五章：管線分割19
5.1 定義19
5.2 優缺點和限制20
第六章：整合三種分割方式22
6.1 為什麼要整合22
6.2 整合方式22
6.3 整合結果分析29
6.3.1 產能和處理器數量的比較30
6.3.2 得到新結果的時間和反應時間的比較32
6.3.3處理器數量和產能的比較34
6.3.4 反應時間和處理器數量的比較36
6.3.5 多種資料分割方式的比較39
6.3.6 結論40
第七章：個案研究：即時實作對應點比對42
7.1 對應點比對演算法42
7.2 整合排程演算法分析結果43
7.3 實驗結果與分析46
第八章：結論與未來研究方向48
8.1 結論48
8.2 未來研究方向48
附錄參考文獻：49

[1].P. Aschwanden and W. Guggenbuhl, “Experimental results from a comparative study on correlation-type registration algorithms“, Robust Computer Vision, Wickmann, pages: 268-289, 1993
[2].S. Banerjee, T. Hamada, Chau, P.M.; Fellman,“Macro pipelining based scheduling on high performance heterogeneous multiprocessor systems” IEEE Transactions on R.D.Signal Processing, Volume: 43 , Issue: 6 pages: 1468-1484 , June 1995
[3].D. N. Bhat and S. K. Nayar, “Original measures for image correspondence”, IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 20, pages: 425-423, 1998
[4].S. Birchfield and C. Tomasi, “Multi-way cut for stereo and motion with slanted surfaces”, Proceedings of International Conference on Computer Vision, vol. 1, pages: 489-495, 1999
[5].Y. Boykov, O. Veksler and R. Zabih, “Fast approximate energy minimization via graph cuts”, IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 23, no. 11, pages: 1222-1239, 2001
[6].M.Z. Brown, D. Burschka, Hager, G.D.,“Advances in computational stereo” IEEE Transactions on Pattern Analysis and Machine Intelligence, Volume: 25 , Issue: 8 pages: 993-1008, Aug. 2003
[7].E.K. Haddad,“Optimal partitioning of random workloads in homogeneous multiprocessor and distributed systems”, Proceedings of the Second IEEE Symposium on Parallel and Distributed Processing, pages:386-393, 9-13 Dec. 1990
[8].R. Hartley,“Multiple View Geometry in Computer Vision”, Cambridge University
[9].H. Hirschmuller, “Improvements in real-time correlation-based stereo vision”, IEEE Workshop on Proceedings of Stereo and Multi-Baseline Vision pages: 141-148, 9-10 Dec. 2001
[10].P.D. Hoang, J.M. Rabaey,“Scheduling of DSP programs onto multiprocessors for maximum throughput” IEEE Transactions on Signal Processing, Volume: 41 , Issue: 6 Pages:2225 — 2235, June 1993
[11].H. Jahn,“Parallel epipolar stereo matching” 15th International Conference Proceedings on Pattern Recognition, Volume: 1 , 3-7 Sept. 2000
[12].H. Jeong, Y. Oh,“A parallel real time implementation of stereo matching” 15th International Proceedings on Parallel and Distributed Processing Symposium. pages: 6, 23-27 April 2001
[13].H. Jing-Jang, C. Yuan-Chieh, D. Frank Anger, and L. Chung-Yee, “Scheduling Precedence Graphs in System with Interprocessor Communication Times”, SIAM Journal on Computing archive Volume 18 , Issue 2 pages: 244-257, April 1989
[14].K. Ki-Il, S. Wonyong, Minseop Jeong, “Multiprocessor scheduling of a signal flow graph for workstation clusters” Conference Record of the Thirtieth Asilomar Conference on Signals, Systems and Computers, vol.2, pages:1364-1367 3-6 Nov. 1996
[15].S. Kimura, T. Kanade, H. Kano, A. Yoshida, E. Kawamura, and K.Oda, “CMU Video-Rate Stereo Machine,” Proc. Mobile Mapping Symp. 1995.
[16].S. Kimura, T. Shinbo, H. Yamaguchi, E. Kawamura, and K. Naka,“A Convolver - Based Real-Time Stereo Machine (SAZAN),” Proc. Computer Vision and Pattern Recognition, vol. 1, pages: 457-463, 1999.
[17].K. Konolige, “Small Vision Systems: Hardware and Implementation, ”Proc. Eighth Int’l Symp. Robotics Research, 1997.
[18].K. Konstantinides, R.T. Kaneshiro, J.R. Tani,“Task allocation and scheduling models for multiprocessor digital signal processing” IEEE Transactions on Acoustics, Speech, and Signal Processing, Volume: 38 , Issue: 12 pages: 2151-2161, Dec. 1990
[19].A. Koschan,“Towards real-time stereo employing parallel algorithms for edge-based and dense stereo matching” Proceedings on Rodehorst, V.Computer Architectures for Machine Perception. 18-20 pages: 234-241, Sept. 1995
[20].E. Laskowski,“ Program graph scheduling in the look-ahead reconfigurable multiprocessor system” Proceedings. International Conference on Parallel Computing in Electrical Engineering. 27-30 pages:106-110, Aug. 2000
[21].G. Moreau, P. Fuchs, A. Doncescu and S. Regis, ”Dense stereo matching method using a quarter of wavelet transform”, IEEE International Conference on Image Processing, Sep. 2002
[22].F. Moreno, A. Tarrida, J. Andrade-Cetto, Sanfeliu,“3D real-time head tracking fusing color histograms and stereovision” International Conference on Pattern Recognition Proceedings. Volume: 1 , 11-15 pages: 368-371, Aug. 2002
[23].Y. Oh, H. Jeong Acoustics,“Trellis-based parallel stereo matching” IEEE International Conference on Speech, and Signal Processing. Volume: 6 pages: 2143-2146 , 5-9 June 2000
[24].J. Ohm, Izquierdo M., “An object-based system for stereoscopic viewpoint synthesis” IEEE Transactions on E.Circuits and Systems for Video Technology. Volume 7 , Issue 5 pages: 801-811, Oct. 1997
[25].M. Pilu, “Uncalibrated stereo correspondence by singular value decomposition” Digital Media Department, HP Laboratories, Bristol , Aug. 1997
[26].Point Grey Research. http://www.ptgrey.com
[27].Schmidt, Niemann, H. Vogt, S.,“Dense disparity maps in real-time with an application to augmented reality” IEEE Workshop on Applications of Computer Vision Proceedings. pages: 225-230, 3-4 Dec. 2002
[28].L. D. Stefano, M. Marchionni, S. Mattoccia and G. Neri, “A fast area-based stereo matching algorithm”, University of Bologna, Italy, 2002
[29].S. Tandri, T.S. Abdelrahman,“Automatic partitioning of data and computations on scalable shared memory multiprocessors” International Conference on Parallel Processing Proceedings. pages: 64-73, 11-15 Aug. 1997
[30].Videre Design. http://www.videredesign.com
[31].J.C.M. van Beek, Lukkien, J.J.,“A parallel algorithm for stereo vision based on correlation” International Conference on High Performance Computing Proceedings. pages: 251-256, 19-22 Dec. 1996
[32].C. Yeh-Ching, Ranka S.,“A parallel programming tool for single program multiple data model on distributed memory multiprocessors” Twenty-Sixth Hawaii International Conference on System Sciences Proceeding. Volume 2 pages: 433-434 vol.2, 5-8 Jan. 1993