研究生: |
周霈忻 Pei-Hsin Chou |
---|---|
論文名稱: |
應用電腦視覺技術於計算三角錐點集管制區域 Applying Computer Vision Technology on Calculating Triangular Cone Point Set Area |
指導教授: |
楊朝龍
Chao-Lung Yang |
口試委員: |
楊朝龍
Chao-Lung Yang 花凱龍 Kai-Lung Hua 許嘉裕 Chia-Yu Hsu |
學位類別: |
碩士 Master |
系所名稱: |
管理學院 - 工業管理系 Department of Industrial Management |
論文出版年: | 2023 |
畢業學年度: | 111 |
語文別: | 中文 |
論文頁數: | 54 |
中文關鍵詞: | 電腦視覺 、YOLO物件辨識 、凸包 、凹包 、德勞內三角化 、蟻群演算法 |
外文關鍵詞: | Computer Vision, YOLO Object Detection, Convex Hull, Concave Hull, Delaunay Triangulation, Ant Colony Optimization |
相關次數: | 點閱:206 下載:2 |
分享至: |
查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報 |
於日常生活中,三角錐大量應用於各式施工場域、警戒區域、道路等地方,作為一個界線效果。雖然電腦視覺技術可辨識出三角錐,但因實務上,三角錐擺放通常混亂無章,且攝影機畫面有時無法完全涵蓋三角錐及管制區域,經常造成區塊式切斷三角錐圍繞之管制區域,導致無法精確判別出三角錐的管控區域,以及此區域實際涵蓋範圍與界線路徑。本研究旨在開發一個基於電腦視覺物件偵測技術的多情境三角錐管控區域計算框架。本研究共提出三種方法,方法一利用德勞內三角化(Delaunay Triangulation),取得合格的有效邊作為凹包(Concave Hull);方法二利用凸包拆解方式,取得各個線段信心度,作為計算基準;方法三應用蟻群演算法(Ant Colony Optimization, ACO),計算點集之間的最合理連線路徑。為驗證結果,首先,本研究蒐集206張具有三角錐的工地與市容影像資料。利用物件偵測模型YOLOV5獲取三角錐影像資訊,建立二維座標點集。針對兩種情境的管控區域,計算區域面積、界線長度等各個影像在不同判別法中與實際解的重疊資訊用以驗證準確度。最後以opencv對最優解進行視覺化,判定為影像的三角錐管制區域。本實驗以兩種影像中三角錐實際常見的排列方式作為驗證的主題:(1)60張涵蓋完整三角錐區域的影像;(2)41張三角錐作為界線的影像。研究結果發現若是以本研究所提出的Concave Hull判斷法,足以達成面積範圍區域平均準確率為98.78%;以蟻群演算法的界線平均準確率為98.36%。最後將三種方法與現有的Convex Hull判斷法做比較。
The objective of this research is to calculating the point setting area of triangular cones by applying computer vision technology. There are three methods proposed in this research. The first one is to use Delaunay triangle to obtain the qualified effective edge as Concave Hull, and the second one is to disassemble the Convex Hull to obtain the confidence of each line segment as the basis for calculation. Third, by applying the Ant Colony Optimization to calculate the most reasonable connection path between point sets. In order to verify the experimental results, 206 images of construction sites and cityscapes with triangular cones should be collected first. Then, the model of object detection is used to obtain the triangular cone image information and create a 2D coordinate point set. For the control area of two situations, calculate the overlap information between the area and boundary length of each image and the actual solution in different discriminatory methods. Finally, the best solution is visualized by opencv and determined as the triangular cone control area of the image. The most common arrangement of triangular cones in two images are used as the subject of this experiment:(1)60 images covering the complete triangular cone area;(2)41 images with triangular cones as the boundary. The experimental results show that the Concave Hull can achieve an accuracy of(98.78%)for the complete triangular cone area in average. The average accuracy of the boundary of the ant colony algorithm can reach(98.36%).
[1] I. Katsamenis et al., "TraCon: A novel dataset for real-time traffic cones detection using deep learning," in Novel & Intelligent Digital Systems: Proceedings of the 2nd International Conference (NiDS 2022), Athens, Greece, 2022, pp. 382-391: Springer.
[2] Q. Su et al., "Real‐time traffic cone detection for autonomous driving based on YOLOv4," IET Intelligent Transport Systems, vol. 16, no. 10, pp. 1380-1390, 2022.
[3] F. Zhou, H. Zhao, and Z. Nie, "Safety helmet detection based on YOLOv5," in 2021 IEEE International conference on power electronics, computer applications (ICPECA), Shenyang, China, 2021, pp. 6-11: IEEE.
[4] E. L. Lawler, "The traveling salesman problem: a guided tour of combinatorial optimization," Wiley-Interscience Series in Discrete Mathematics, 1985.
[5] M. W. Padberg and S. Hong, On the symmetric travelling salesman problem: a computational study. Springer, 1980.
[6] M. Jayaram and H. Fleyeh, "Convex hulls in image processing: a scoping review," American Journal of Intelligent Systems, vol. 6, no. 2, pp. 48-58, 2016.
[7] P. T. An, P. T. T. Huyen, and N. T. Le, "A modified Graham’s convex hull algorithm for finding the connected orthogonal convex hull of a finite planar point set," Applied Mathematics Computation, vol. 397, p. 125889, 2021.
[8] J. Bai and X. Feng, "Image denoising and decomposition using non-convex functional," Chinese Journal of electronics, vol. 21, no. 1, pp. 102-106, 2012.
[9] K. Mirzoyan, H. Mirzaakbar, and K. Alisher, "The construction of local convex hull on the task of pattern recognition," Procedia Computer Science, vol. 186, pp. 360-365, 2021.
[10] H. Cevikalp, H. S. Yavuz, and B. Triggs, "Face recognition based on videos by using convex hulls," IEEE Transactions on Circuits Systems for Video Technology, vol. 30, no. 12, pp. 4481-4495, 2019.
[11] P. D. Singh, R. Kaur, K. D. Singh, and G. Dhiman, "A novel ensemble-based classifier for detecting the COVID-19 disease for infected patients," Information Systems Frontiers, vol. 23, pp. 1385-1401, 2021.
[12] B. Kenwright, "Convex Hulls: Surface Mapping onto a Sphere," arXiv preprint arXiv:.04079, 2023.
[13] D. Avis and D. Bremner, "How good are convex hull algorithms?," in Proceedings of the eleventh annual symposium on Computational geometry, Vancouver, B.C., Canada, 1995, pp. 20-28: ACM.
[14] R. L. Graham, "An efficient algorithm for determining the convex hull of a finite planar set," Information processing letters, vol. 1, pp. 132-133, 1972.
[15] R. A. Jarvis, "On the identification of the convex hull of a finite set of points in the plane," Information processing letters, vol. 2, no. 1, pp. 18-21, 1973.
[16] T. M. Chan, "Optimal output-sensitive convex hull algorithms in two and three dimensions," Discrete Computational Geometry, vol. 16, no. 4, pp. 361-368, 1996.
[17] A. M. Andrew, "Another efficient algorithm for convex hulls in two dimensions," Information Processing Letters, vol. 9, no. 5, pp. 216-219, 1979.
[18] C. B. Barber, D. P. Dobkin, and H. Huhdanpaa, "The quickhull algorithm for convex hulls," ACM Transactions on Mathematical Software, vol. 22, no. 4, pp. 469-483, 1996.
[19] R. Chadnov and A. Skvortsov, "Convex hull algorithms review," in The 8th Russian-Korean International Symposium on Science and Technology,2004., Tomsk, Russia, 2004, vol. 2, pp. 112-115: IEEE.
[20] A. Galton and M. Duckham, "What is the region occupied by a set of points?," in Geographic Information Science: 4th International Conference, GIScience 2006,. Proceedings 4, Münster, Germany, 2006, pp. 81-98: Springer.
[21] A. Moreira and M. Y. Santos, "Concave hull: A k-nearest neighbours approach for the computation of the region occupied by a set of points," proceedings of the International Conference on Computer Graphics Theory and Applications, pp. 61-68, 2007.
[22] J.-S. Park and S.-J. Oh, "A new concave hull algorithm and concaveness measure for n-dimensional datasets," Information science engineering, vol. 28, no. 3, pp. 587-600, 2012.
[23] H. Edelsbrunner, D. Kirkpatrick, and R. Seidel, "On the shape of a set of points in the plane," IEEE Transactions on information theory, vol. 29, no. 4, pp. 551-559, 1983.
[24] S. Asaeedi, F. Didehvar, and A. Mohades, "α-Concave hull, a generalization of convex hull," Theoretical Computer Science, vol. 702, pp. 48-59, 2017.
[25] B. Delaunay, "Sur la sphere vide," Izv. Akad. Nauk SSSR, Otdelenie Matematicheskii i Estestvennyka Nauk, vol. 7, no. 793-800, pp. 1-2, 1934.
[26] S. Hornus and J.-D. Boissonnat, "An efficient implementation of Delaunay triangulations in medium dimensions," INRIA, 2008.
[27] A. Arampatzis et al., "Web-based delineation of imprecise regions," Computers, Environment Urban Systems, vol. 30, no. 4, pp. 436-459, 2006.
[28] L. H. de Figueiredo and A. Paiva, "Region reconstruction with the sphere-of-influence diagram," Computers Graphics, vol. 107, pp. 252-263, 2022.
[29] M. Duckham, L. Kulik, M. Worboys, and A. Galton, "Efficient generation of simple polygons for characterizing the shape of a set of points in the plane," Pattern recognition, vol. 41, no. 10, pp. 3224-3236, 2008.
[30] Z. Yang et al., "Dense reppoints: Representing visual objects with dense point sets," in Computer Vision–ECCV 2020: 16th European Conference, Glasgow, UK, 2020, pp. 227-244: Springer.
[31] D. Novoa-Paradela, O. Fontenla-Romero, and B. Guijarro-Berdiñas, "A one-class classification method based on expanded non-convex hulls," Information Fusion, vol. 89, pp. 1-15, 2023.
[32] K. Xenitidis, K. Ioannou, and G. Tsantopoulos, "An innovative methodology for the determination of wind farms installation location characteristics using GIS and Delaunay Triangulation," Energy for Sustainable Development, vol. 75, pp. 25-39, 2023.
[33] Z. Sun, H. Liu, C. Xu, and H. Kong, "Graph Gain: A Concave-Hull Based Volumetric Gain for Robotic Exploration," arXiv preprint arXiv:.10698, 2022.
[34] A. Colorni, M. Dorigo, and V. Maniezzo, "Distributed optimization by ant colonies," in Proceedings of the first European conference on artificial life, Paris, France, 1991, vol. 142, pp. 134-142: The MIT Press.
[35] M. Dorigo, V. Maniezzo, and A. Colorni, "Ant system: optimization by a colony of cooperating agents," IEEE Transactions on Systems, vol. 26, no. 1, pp. 29-41, 1996.
[36] M. Dorigo and L. M. Gambardella, "Ant colony system: a cooperative learning approach to the traveling salesman problem," IEEE Transactions on evolutionary computation, vol. 1, no. 1, pp. 53-66, 1997.
[37] L. Li, S. Ju, and Y. Zhang, "Improved ant colony optimization for the traveling salesman problem," in 2008 international conference on intelligent computation technology and automation (icicta), Changsha, Hunan, China, 2008, vol. 1, pp. 76-80: IEEE.
[38] H. M. Naimi and N. Taherinejad, "New robust and efficient ant colony algorithms: Using new interpretation of local updating process," Expert Systems with Applications, vol. 36, no. 1, pp. 481-488, 2009.
[39] M. Liu, X. You, X. Yu, and S. Liu, "KL divergence-based pheromone fusion for heterogeneous multi-colony ant optimization," IEEE Access, vol. 7, pp. 152646-152657, 2019.
[40] W. Yong, "Hybrid max–min ant system with four vertices and three lines inequality for traveling salesman problem," Soft Computing, vol. 19, pp. 585-596, 2015.
[41] D. Zhang, X. You, S. Liu, and K. Yang, "Multi-colony ant colony optimization based on generalized jaccard similarity recommendation strategy," IEEE Access, vol. 7, pp. 157303-157317, 2019.
[42] W. Gao, "New ant colony optimization algorithm for the traveling salesman problem," International Journal of Computational Intelligence Systems, vol. 13, no. 1, pp. 44-55, 2020.
[43] S. Ebadinezhad, "DEACO: Adopting dynamic evaporation strategy to enhance ACO algorithm for the traveling salesman problem," Engineering Applications of Artificial Intelligence, vol. 92, p. 103649, 2020.
[44] W. Liu, "Route optimization for last-mile distribution of rural E-commerce logistics based on ant colony optimization," IEEE Access, vol. 8, pp. 12179-12187, 2020.
[45] J. Chen, F. Ling, Y. Zhang, T. You, Y. Liu, and X. Du, "Coverage path planning of heterogeneous unmanned aerial vehicles based on ant colony system," Swarm Evolutionary Computation, vol. 69, p. 101005, 2022.
[46] Q. Luo, H. Wang, Y. Zheng, and J. He, "Research on path planning of mobile robot based on improved ant colony algorithm," Neural Computing Applications, vol. 32, pp. 1555-1566, 2020.
[47] M. Kurdi, "Ant colony optimization with a new exploratory heuristic information approach for open shop scheduling problem," Knowledge-Based Systems, vol. 242, p. 108323, 2022.
[48] S.-H. Huang, Y.-H. Huang, C. A. Blazquez, and C.-Y. Chen, "Solving the vehicle routing problem with drone for delivery services using an ant colony optimization algorithm," Advanced Engineering Informatics, vol. 51, p. 101536, 2022.
[49] X. Xia and Y. Zhou, "Performance analysis of ACO on the quadratic assignment problem," Chinese journal of electronics, vol. 27, no. 1, pp. 26-34, 2018.
[50] K. F. Riley, M. P. Hobson, and S. J. Bence, "Mathematical methods for physics and engineering," ed: American Association of Physics Teachers, 1999.
[51] I. Katsamenis et al., "Robotic maintenance of road infrastructures: The heron project," in Proceedings of the 15th International Conference on PErvasive Technologies Related to Assistive Environments, Corfu,Greece, 2022, pp. 628-635: Association for Computing Machinery.