基于遗传算法的自动拼图(三)

Posted on | In , |

交叉配对

初始化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Crossover(object):

    def __init__(self, first_parent, second_parent):
        self._parents = (first_parent, second_parent)
        self._pieces_length = len(first_parent.pieces)

        self._child_rows = first_parent.rows
        self._child_columns = first_parent.columns

        # Borders of growing kernel
        self._min_row = 0
        self._max_row = 0
        self._min_column = 0
        self._max_column = 0
 # 初始化第一哥小拼图块的位置(0,0)，如果其下方没有拼图快，则可以在(0,-1)处继续放拼图块 此时min_row=-1
        
        #字典{piece_id：(row, column)}
        self._kernel = {}

        self._taken_positions = set()

        # Priority queue
        #[(priority, (position, piece_id), relative_piece(piece_id, orientation))]
        self._candidate_pieces = []

run函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def run(self):
    self._initialize_kernel()

    while len(self._candidate_pieces) > 0:
        _, (position, piece_id), relative_piece = heapq.heappop(self._candidate_pieces)

        if position in self._taken_positions:
            continue

        # If piece is already placed, find new piece candidate and put it back to
        # priority queue
        if piece_id in self._kernel:
            self.add_piece_candidate(relative_piece[0], relative_piece[1], position)
            continue

        self._put_piece_to_kernel(piece_id, position)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
def _initialize_kernel(self):
        root_piece = self._parents[0].pieces[int(random.uniform(0, self._pieces_length))]
        self._put_piece_to_kernel(root_piece.id, (0, 0))

    def _put_piece_to_kernel(self, piece_id, position):
        self._kernel[piece_id] = position
        self._taken_positions.add(position)
        self._update_candidate_pieces(piece_id, position)

    def _update_candidate_pieces(self, piece_id, position):
        available_boundaries = self._available_boundaries(position)

        for orientation, position in available_boundaries:
            #原拼图块，方向，空着的拼图块的位置
            self.add_piece_candidate(piece_id, orientation, position)

    def add_piece_candidate(self, piece_id, orientation, position):
        #返回父母共享的那个方向的拼图块的id
        shared_piece = self._get_shared_piece(piece_id, orientation)
        if self._is_valid_piece(shared_piece):
        #共享块的ID,坐标，原相邻拼图块的ID,相对于原相邻拼图块的方向
            self._add_shared_piece_candidate(shared_piece, position, (piece_id, orientation))
            return
        #如果没有父母共享的那个方向的拼图块的id
        #根据色差相似度fitness比较 返回跟父母中某一个一样相似的拼图块ID
        buddy_piece = self._get_buddy_piece(piece_id, orientation)
        if self._is_valid_piece(buddy_piece):
        #相似块的ID,坐标，原相邻拼图块的ID,相对于原相邻拼图块的方向
            self._add_buddy_piece_candidate(buddy_piece, position, (piece_id, orientation))
            return
        #如果和父母都不相似
        #返回根据色差相似度fitness比较 最佳匹配的拼图块
        best_match_piece, priority = self._get_best_match_piece(piece_id, orientation)
        if self._is_valid_piece(best_match_piece):
            self._add_best_match_piece_candidate(best_match_piece, position, priority, (piece_id, orientation))
            return

    def _get_shared_piece(self, piece_id, orientation):
        first_parent, second_parent = self._parents
        first_parent_edge = first_parent.edge(piece_id, orientation)
        second_parent_edge = second_parent.edge(piece_id, orientation)

        if first_parent_edge == second_parent_edge:
            return first_parent_edge

    def _get_buddy_piece(self, piece_id, orientation):
        first_buddy = ImageAnalysis.best_match(piece_id, orientation)
        second_buddy = ImageAnalysis.best_match(first_buddy, complementary_orientation(orientation))

        if second_buddy == piece_id:
            #和父母中任何一个的edge的一样即可
            for edge in [parent.edge(piece_id, orientation) for parent in self._parents]:
                if edge == first_buddy:
                    return edge

    def _get_best_match_piece(self, piece_id, orientation):
        for piece, dissimilarity_measure in ImageAnalysis.best_match_table[piece_id][orientation]:
            if self._is_valid_piece(piece):
                return piece, dissimilarity_measure

    def _add_shared_piece_candidate(self, piece_id, position, relative_piece):
        piece_candidate = (SHARED_PIECE_PRIORITY, (position, piece_id), relative_piece)
        heapq.heappush(self._candidate_pieces, piece_candidate)

判断该拼图块是否合理 is_valid_piece

1
2
def _is_valid_piece(self, piece_id):
    return piece_id is not None and piece_id not in self._kernel

返回其子代

1
2
3
4
5
6
7
8
def child(self):
    pieces = [None] * self._pieces_length

    for piece, (row, column) in self._kernel.items():
        index = (row - self._min_row) * self._child_columns + (column - self._min_column)
        pieces[index] = self._parents[0].piece_by_id(piece)
    #通过piece的id找到id对应的那一块拼图
    return Individual(pieces, self._child_rows, self._child_columns, shuffle=False)