[發明專利]基于親緣關系的照片自動排版方法

有效

• 申請號: 201310046289.6
• 申請日: 2013-02-05
• 公開（公告）號: CN103176960A
• 公開（公告）日: 2013-06-26
• 發明（設計）人: 孫欽東;田敏穎;張景鵬;王倩;黃新波
• 申請（專利權）人: 西安理工大學
• 主分類號: G06F17/25
• 分類號: G06F17/25
• 代理公司: 西安弘理專利事務所 61214
• 代理人: 李娜

技術領域

本發明屬于矩形件優化排樣技術領域，涉及一種基于親緣關系的照片自動排版方法。

背景技術

隨著計算機技術的迅速發展和各種數碼設備的廣泛應用，數碼相機已逐步取代了傳統相機，數碼相機在成像質量、可操作性、性價比等方面都已遠遠超越傳統相機，尤其是數碼照片在后期處理、存儲以及傳輸方面所具有的優勢，使得數碼相機逐步成為了普通家庭攝影的首選工具，與此同時數碼照片的數量也呈現出爆炸式增長，這也帶來了海量的照片沖印需求。

由于要沖印輸出的數碼照片尺寸大小不一、規格繁多，而輸出設備及使用的相紙的規格是統一的，通常為24英寸、30英寸及50英寸。為提高沖印效率，充分利用相紙，就需要先把要沖印的照片排成符合相紙寬度的版面，以滿足相紙的尺寸要求，達到節省成本的目的。因此對于數碼沖印企業而言，選擇一個高效的排版軟件至關重要，而排版方法則是排版軟件的核心。

對照片版面進行排版屬于矩形件優化排樣問題，在此之前，矩形件優化排樣問題廣泛地出現于機械制造、輕工、家具、造紙及玻璃切割等行業，它是將許多小矩形件盡可能多地、無重疊地排放到一個定寬、定長（或無限長）的矩形板材上，使其利用率達到最大。

由于優化排樣是一個經典的NP(Nondeterministic?Problem)完全問題，以目前的計算理論和算法，要么根本無法求解，要么求解的過程需要的機時和費用是無法接受的，因此，目前的研究都在求其有效近似最優解。隨著對排樣問題的深入研究，這些算法可大致分為兩類：一類是啟發式算法，例如背包算法、基于占穴思想的啟發式算法、最低水平線排放算法。另一類算法主要是利用現代智能算法，例如遺傳算法、模擬退火算法、蟻群算法、粒子群算法等，結合某種排放規則，進行優化排樣。

以上這些算法在矩形件的排樣上都取得了較好效果，但是也都有效果不佳的實例。目前為止，對矩形件優化排樣問題還沒有完全有效的解決方法，尤其是應用于照片排版時，更是有不足之處。上述提到的這些算法都是對大量的圖片進行完全混排，才達到這樣的效果，所使用的樣本圖片都具有無序性，所有樣本圖片間是沒有任何關聯的，在特定的版面格局下，只要符合要求的圖片都可以排放到當前位置，排版過程具有很大的隨機性和多樣性。

然而，對于影樓、寫真館、數碼沖印企業，在實際操作中待排版的照片是按照不同的客戶進行分類，相同客戶提供的照片又會按照照片尺寸或是不同的后期處理效果再次分類。每進行一次歸類，具有著某種相似性的照片就會聚簇一次，因而這些照片彼此間是具有一定的有序性的。若是在排版過程打破照片間的這種關系，后期分片過程中，就要通過人工作業手動地將這些具有著某種相似性的照片從海量的已排版版面中挑揀出來，逐一進行分片歸類。就“排版—沖印—分片”這一實際工作流程來說，混合排版并未達到預期結果。因此，研究一種既能提高相紙利用率，又能充分考慮后期分片方便性的排版算法具有非常大的實際應用價值。

發明內容

本發明提供了一種基于親緣關系的照片自動排版方法，解決了現有照片排版技術存在的理片麻煩、排版效率低等問題。

本發明采用的技術方案是，一種基于親緣關系的照片自動排版方法，具體按照以下步驟實施：

步驟1、將所有待排版的照片添加至系統，在開始排版之前，照片按照所在文件夾編號從小到大排序，同文件夾內的照片按照其面積從大到小排序；

步驟2、若當前最低可排放邊的高h不小于母版的高H時，或所有照片均被排放完，或當前狀態已排不下剩余的任何照片，則轉到步驟5；否則進入步驟3；

步驟3、對當前狀態下的所有可排放邊，利用如下方法尋找排放最優組合，設第i個可排放邊的長度為Li，i=1,2,...,n，按照照片編號及面積排序的待排版照片鏈表中選擇照片進行測試，在排版過程中，首先選擇編號小面積大的照片排放，

3.1）若Li為凹形可排放邊：

3.1.1)選擇盡可能多的照片豎排，使得最小，記錄d1_i以及能夠豎排的所有照片；

3.1.2)選擇盡可能多的照片橫排，使得記錄d2i以及能夠橫排的所有照片；

3.1.3)照片豎排橫排混合

a)首先根據步驟3.1.2)方法，記錄能夠橫排的照片數目n以及照片；

b)在版面上依次橫排i張相應的照片，待排放好i張照片后對于剩余的水平線，從所有的待排照片中以豎排方式選擇排版組合，每進行一次測試，記錄排放后的水平線差值minus_i；