將旅行推銷員問題和啟發式解法應用於ILDA檔案之路徑重整

Abstract

雷射投影被廣泛的應用在藝術展演或顯示裝置上，假如個人要使用雷射投影機，可以選擇使用小台的雷射投影機，因價格較便宜且功能也已夠使用，而就算是能一次處理大量資料的投影機，只要沒處理路徑規劃，投影出來之影像的品質也會受到輸入影像的影響，例如太多的點數使frame rate(又稱FPS)降低造成閃爍效果，或是路徑上有許多大角度的轉動造成線段扭曲，如果能透過預先重整輸入圖檔的路徑，就能提高成像品質也能減少控制雷射位置的元件的耗損。ILDA檔案的產生方式可使用圖像(jpg或png等等)轉換成svg格式再透過轉換軟體轉換而成或者直接從網路上下載公開的檔案，但經常會有不合邏輯或者不必要的路徑，於是本論文研究提出將原始圖檔的資料經處理後應用到有名的旅行推銷員問題(travelling salesman Problem)來重新調整路徑，以及使用啟發式解法(heuristic algorithm)求解，最後的結果除了能讓輸入圖不會有不必要的點和路徑外，更能夠提升雷射投影機之投射品質。Laser projection is commonly used in the performing arts or display devices. If we need to use laser projector for indivisuals, we can use a compact size laser projector. There is enough function of a compact size laser projector and it is cheaper than the big laser projector.Even if a laser projector can process large amount of data, it will affect the quality of laser projection result by the input data. For example, the frame rate (also known as FPS) will get lower and look flickering because of a lot of data in the input. Additionally, the visible line will be deformed because of the big angle rotation in the path. If we can rearrange the path of input data before projecting, we can get the higher quality of laser projection result and decrease mechanical components loss. In order to get the input file, we can transform the image data (jpg or png etc.) to svg format and then transform svg to ILDA format or downlod the public file from the Internet. However, it is commonly found illogical or unnecessary path in the file. Thus, in this thesis, we introduce the method to preprocess data and apply to travelling salesman problem (TSP) rearrange the path. Besides, we also use the heuristic algorithm to solve the TSP. After rearranging the path, we can get not only a clear input data but also a better laser projection result.