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

有效

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

1.一種基于親緣關系的照片自動排版方法，其特征在于，具體按照以下步驟實施：

步驟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張照片后對于剩余的水平線，從所有的待排照片中以豎排方式選擇排版組合，每進行一次測試，記錄排放后的水平線差值minusi；

c)根據d3i=min{minus_i}(i=1,2....n)，得到最小差值d3i以及相應的照片及排放方式；

通過步驟3.1.1)到步驟3.1.3)這三步，此凹形水平線排放后的剩余長度d=min{d1i,d2i,d3i}，使得d值最小的排版方式下所選取的照片就是最優排放組合；

3.2）若Li為凸形可排放邊：

尋找是否有照片p使得w=Li或者l=Li，若存在，則差值d=0，最優排放組合為照片p；

步驟4、將步驟3中選擇到的最優排放組合依據親緣關系進行搜索，使得照片盡可能來自于相近的文件夾，確定最終要排放的最優組合，并緊貼對應的可排放邊進行排放，記錄新產生的可排放邊，轉步驟2；

步驟5、若當前最低可排放邊的高≥H，重新生成寬為W、高為H的母版，轉步驟3繼續進行排版；

若所有照片均被排放完，轉步驟6；

步驟6、若最后一版排版效果較好，沒有出現鋸齒狀空白，則得到最終的排版效果，即成；否則進入步驟7；

步驟7、對最后一版按照區域排版方法重新排版，得到最終的排版效果，即成。

2.根據權利要求1所述的基于親緣關系的照片自動排版方法，其特征在于：所述的步驟7中的區域排版方法的具體步驟是：

搜索排放在最后一塊母版上的所有照片，并將照片按照其尺寸分類，對這些照片按長邊由長到短排序，將之保存在鏈表中；取最長的矩形件從版面左上角開始沿其寬度W方向排放，排放的原則是能豎排就不橫排，

排放的個數按照以下公式計算得到：

如果照片按照橫排，則用li取代wi進行計算，從而得到結果，照片Ri排放到版面上以后，劃分空白區域從而得到兩個待排區域r1、r2及相應排放點P1、P2；

逐個判斷各待排區域是否能放得下當前最小的照片，如果放不下則刪除該待排矩形區域及相應排放點；把未刪除的最靠近母版上邊緣的待排矩形區域看作是一塊新的母版，并以相應的排放點作為“母版”起始排樣點，然后按區域排版方式繼續排放，此時應以新的待排區域的長、寬代替計算式中原母版的長和寬數據；這樣每一個待排區域又新生成兩個待排區域，然后對新產生的待排區域進行刪除、排樣操作，如此循環迭代，直到所有照片都排放完為止。