模型建立

問(wèn)題1

邊緣相似度

問(wèn)題一給出的是一單頁(yè)頁(yè)面僅縱切出的 19 條碎紙片，確定碎紙片排列的順序，就能很好的還原出原來(lái)的完整紙片。因?yàn)樗榧埰男螤钜?guī)則且大小相等，因此不能夠通過(guò)碎紙片邊緣形狀來(lái)確定相鄰紙片，只能通過(guò)分析邊緣文字特征進(jìn)行拼接?？梢钥闯?，碎紙片之間的切口都是整齊的直線，碎紙片邊緣保留了字符信息。通過(guò)比較兩個(gè)紙片邊緣相似度，可以確定兩張紙片是否相鄰，從而得到正確的拼接序列。

一般來(lái)講，從圖像的連通性考慮，相鄰的兩個(gè)碎紙片的邊緣像素應(yīng)當(dāng)是相似、甚至是相同的。這樣我們可以將兩個(gè)邊緣的匹配指標(biāo)用兩個(gè)向量的距離來(lái)衡量：

圖1

其中，x和y表示兩張碎紙圖片的像素矩陣的邊緣列向量。如果兩個(gè)由像素組成的向量間的距離為0，則可以肯定兩張碎紙片肯定相鄰，但這是理想的情況，如圖2所示，碎紙圖片不是矢量圖形，在顯示點(diǎn)陣字體時(shí)，會(huì)出現(xiàn)鋸齒現(xiàn)象，文字邊緣由里向外，會(huì)有從黑到白之間的過(guò)渡，所以兩個(gè)相鄰像素向量間的距離一般較小，但不一定為0。雖然像素分開了，由于漢字字體或者英文字體大部分是連體的，所以這些碎片的圖像灰度信息會(huì)有一定的相關(guān)性或者說(shuō)是連續(xù)性。我們就能利用這些碎片之間的相關(guān)性還原出完整紙片。

圖2

貪心算法

由于存在鋸齒現(xiàn)象，兩個(gè)向量間距離不一定為零，一個(gè)碎紙圖片可能與多張其他碎紙片有相關(guān)性。所以，我們選擇主要的步驟是找出一個(gè)起始碎片作為起點(diǎn)，然后把這個(gè)碎片像素矩陣的最右邊緣向量跟其他碎片的最左邊緣向量進(jìn)行比較，選擇匹配度最高的碎片進(jìn)行匹配，然后以新匹配到的碎片為開始，再對(duì)余下碎片進(jìn)行最優(yōu)匹配，不斷循環(huán)，直到所有碎紙片都匹配結(jié)束。如圖3所示，由于選擇的起始碎片對(duì)算法影響較大，為拼接出正確的紙片，我們需要找出原紙片中最左邊的碎紙片編號(hào)。通過(guò)觀察，我們看出文字與頁(yè)面之間存在內(nèi)邊距，左側(cè)留白最多的碎紙片就是原紙片中的最左邊。通過(guò)比較留白大小找出起始碎片后，即可拼接出完整中文紙片。英文字符的碎紙片同樣有相同的規(guī)律，使用相同的算法處理，就能得到英文的完整紙片。

圖片3

問(wèn)題求解

附件一和附件二

在處理附件一和附件二時(shí)，不需要進(jìn)行人工干預(yù)，運(yùn)行算法就能得到拼接順序，最后利用python的PIL庫(kù)完成碎片的 拼接。
最終附件一的拼接順序?yàn)椋?/p>

[8, 14, 12, 15, 3, 10, 2, 16, 1, 4, 5, 9, 13, 18, 11, 7, 17, 0, 6]

附件二的拼接順序?yàn)椋?/p>

[3, 6, 2, 7, 15, 18, 11, 0, 5, 1, 9, 13, 10, 8, 12, 14, 17, 16, 4]

圖4為附件一拼接完成后的效果，圖5為附件二拼接完成的效果

圖片4

圖片5

代碼

附件一和二代碼：

import glob
import numpy as np
from PIL import Image


class PaperRecovery:
    IMAGE_ABS_PATH = 'F:\code\py\paper-recovery\碎紙片1\*.bmp' #圖片存在該目錄下
    img = {}
    finded = set()

    def read_img(self):
        """
        讀取指定目錄下的碎紙圖片，存入字典中，方便使用
        """
        img_name_list = glob.glob(self.IMAGE_ABS_PATH)
        for img_name in img_name_list:
            # k = img_name.replace('.bmp','')[-3:]
            # 使用文件路徑作為字典的鍵，方便找出正確圖片順序后，拼接還原圖片
            k = img_name
            self.img[k] = Image.open(img_name)

    def __init__(self):
        self.read_img()

    def find_match_paper(self,paper_img,direction):
        """
        根據(jù)圖片邊緣的相似度，找出給定碎紙片的相鄰紙片
        """
        self_img_array = np.array(self.img[paper_img])
        sh, sw = self_img_array.shape
        if direction == "r":
            self_edge = self_img_array[0:sh,sw-1:sw]
        elif direction == 'l':
            self_edge = self_img_array[0:sh,0:1]
        min_var = -1
        for k, v in self.img.items():
            if k == paper_img:
                continue
            if k in self.finded:
                continue
            other_img_array = np.array(v)
            h, w = other_img_array.shape
            if direction == "r":
                other_edge = other_img_array[0:h,0:1]
            elif direction == 'l':
                other_edge = other_img_array[0:h,w-1:w]
            else:
                pass
            var = np.sum(abs(self_edge-other_edge))
            if min_var == -1:
                similar_img = k
                min_var = var
            if var < min_var:
                 similar_img = k
                 min_var = var
        self.finded.add(paper_img)
        return similar_img

    def find_edge_paper(self):
        """
        函數(shù)找出原圖片中的最左邊和最右邊的碎紙圖片
        觀察碎紙圖片后，可以看出，在豎切時(shí)
        在完整紙片的最左端和最右端的碎紙片，有一定的留白
        """
        def is_all_white(edge_array):
            """
            判斷一列像素值是否全為255，即全白
            """
            WHITE_RGB = 255
            for k in edge_array:
                if k != WHITE_RGB:
                    return False
            return True

        for k, v in self.img.items():
            img_array = np.array(v)
            h, w = img_array.shape
            right_edge = img_array[0:h,w-1:w]
            left_edge = img_array[0:h,0:1]
            if is_all_white(right_edge):
                right_img_name = k
            elif is_all_white(left_edge):
                left_img_name = k
        return (left_img_name,right_img_name)


    def find_correct_order(self):
        correct_order = []
        left_side_img, right_side_img = self.find_edge_paper()
        correct_order.append(left_side_img)
        paper_list = list(self.img.keys())
        paper_list.remove(left_side_img)
        paper_list.remove(right_side_img)
        while paper_list:
            now_paper = correct_order[len(correct_order)-1]
            next_paper = self.find_match_paper(now_paper,direction="r")
            paper_list.remove(next_paper)
            correct_order.append(next_paper)
        correct_order.append(right_side_img)
        return correct_order

    def combining(self,order):
        """
        復(fù)原豎切的碎紙片
        按照正確的圖片順序（從左到右），將碎紙片拼接成完整的紙片
        """
        UNIT_W, UNIT_H = self.img[order[0]].size
        TARGET_WIDTH = len(order) * UNIT_W
        target = Image.new('RGB', (TARGET_WIDTH, UNIT_H))
        x = 0
        for img_name in order:
            img = self.img[img_name]
            target.paste(img,(x,0))
            x += UNIT_W
        return target
        


if __name__ == "__main__":
    rp = PaperRecovery()
    correct_order = rp.find_correct_order()
    whole_img = rp.combining(correct_order)
    whole_img.save('whole.bmp')
    idx_list = []
    for order in correct_order:
        idx = order[-7:-3]
        idx_list.append(idx)
    print(idx_list)