openCVpageDewarp

openCv page Dewarp 분석 -5

openCV, pageDewarp

저번 포스트에서는 윤곽선 검출에 대해서 살펴보았습니다.

이번 포스트에서는 윤곽선을 합치는 것에대해서 살펴보겠습니다.

assemble_spans

1
spans = assemble_spans(name, small, pagemask, cinfo_list)

assemble_spans()를 통해 윤곽선을 합치게 됩니다.

input으로는 파일 이름, resize된 이미지, 마스킹을 위한 이미지, 윤곽선 정보 클래스가 들어갑니다.

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
def assemble_spans(name, small, pagemask, cinfo_list):

    # sort list
    cinfo_list = sorted(cinfo_list, key=lambda cinfo: cinfo.rect[1])

    # generate all candidate edges
    candidate_edges = []

    for i, cinfo_i in enumerate(cinfo_list):
        for j in range(i):
            # note e is of the form (score, left_cinfo, right_cinfo)
            edge = generate_candidate_edge(cinfo_i, cinfo_list[j])
            if edge is not None:
                candidate_edges.append(edge)

    # sort candidate edges by score (lower is better)
    candidate_edges.sort()

    # for each candidate edge
    for _, cinfo_a, cinfo_b in candidate_edges:
        # if left and right are unassigned, join them
        if cinfo_a.succ is None and cinfo_b.pred is None:
            cinfo_a.succ = cinfo_b
            cinfo_b.pred = cinfo_a

    # generate list of spans as output
    spans = []

    # until we have removed everything from the list
    while cinfo_list:

        # get the first on the list
        cinfo = cinfo_list[0]

        # keep following predecessors until none exists
        while cinfo.pred:
            cinfo = cinfo.pred

        # start a new span
        cur_span = []

        width = 0.0

        # follow successors til end of span
        while cinfo:
            # remove from list (sadly making this loop *also* O(n^2)
            cinfo_list.remove(cinfo)
            # add to span
            cur_span.append(cinfo)
            width += cinfo.local_xrng[1] - cinfo.local_xrng[0]
            # set successor
            cinfo = cinfo.succ

        # add if long enough
        if width > SPAN_MIN_WIDTH:
            spans.append(cur_span)

    if DEBUG_LEVEL >= 2:
        visualize_spans(name, small, pagemask, spans)

    return spans

기본적으로 함수의 이름인 assemble_spans은 폭을 모아준다는 뜻입니다. 이전 윤곽선 정보를 모은 최종적인 그림은 아래와 같습니다.

윤곽선 표시

그림을 살펴보면 각 윤곽선 마다 색깔이 틀린 것을 알 수 있습니다. 같은 가로줄에 있어도 윤곽선이 연속되있이 않다고 판단하기 때문입니다. 원할환 처리를 위해서는 같은 가로줄의 윤곽선을 모아줄 필요가 있습니다.

윤곽선 정렬

cinfo_list = sorted(cinfo_list, key=lambda cinfo: cinfo.rect[1]) 첫번째로 등장하는 것은 정렬입니다. sorted는 배열을 정렬된 리스트로 리턴해 줍니다. sort와 다른점은 원본은 유지된다는 것입니다.

key=lambda cinfo: cinfo.rect[1]의 뜻은 cinfo.rect[1](ymin : 좌측 상단의 y값)에 대해서 정렬(내림차순)을 한다는 의미입니다.

윤곽선 후보군 선출

1
2
3
4
5
6
for i, cinfo_i in enumerate(cinfo_list):
    for j in range(i):  # range(i)는 0~(i-1)까지
        # note e is of the form (score, left_cinfo, right_cinfo)
        edge = generate_candidate_edge(cinfo_i, cinfo_list[j])
        if edge is not None:
            candidate_edges.append(edge)

위 for문은 각 윤곽선에 대해서 점수를 부여합니다. edge가 될 수 있는 후보군을 선출하고 알고리즘에 맞춘 점수를 부여합니다.

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
def generate_candidate_edge(cinfo_a, cinfo_b):

    # we want a left of b (so a's successor will be b and b's
    # predecessor will be a) make sure right endpoint of b is to the
    # right of left endpoint of a.
    if cinfo_a.point0[0] > cinfo_b.point1[0]:
        tmp = cinfo_a
        cinfo_a = cinfo_b
        cinfo_b = tmp

    x_overlap_a = cinfo_a.local_overlap(cinfo_b)
    x_overlap_b = cinfo_b.local_overlap(cinfo_a)

    overall_tangent = cinfo_b.center - cinfo_a.center
    overall_angle = np.arctan2(overall_tangent[1], overall_tangent[0])

    delta_angle = max(angle_dist(cinfo_a.angle, overall_angle),
                      angle_dist(cinfo_b.angle, overall_angle)) * 180/np.pi

    # we want the largest overlap in x to be small
    x_overlap = max(x_overlap_a, x_overlap_b)

    dist = np.linalg.norm(cinfo_b.point0 - cinfo_a.point1)

    if (dist > EDGE_MAX_LENGTH or
            x_overlap > EDGE_MAX_OVERLAP or
            delta_angle > EDGE_MAX_ANGLE):
        return None
    else:
        score = dist + delta_angle*EDGE_ANGLE_COST
        return (score, cinfo_a, cinfo_b)

첫번째 조건문은 주석에서 말한 것 처럼 윤곽선의 포인트를 비교해서 가장 좌측에 있는 윤곽선을 cinfo_a로 오게 합니다. 그래서 a의 계승자(successor)는 b가되고 b의 전임자(predecessor)는 a로 간주합니다.

1
2
3
4
5
6
7
x_overlap_a = cinfo_a.local_overlap(cinfo_b)
x_overlap_b = cinfo_b.local_overlap(cinfo_a)

...

    # we want the largest overlap in x to be small
x_overlap = max(x_overlap_a, x_overlap_b)

a와 b를 b와 a의 윤곽선을 포개어서 차이를 측정합니다. 측정한 것 중에 차이가 더 큰것을 x_overlap에 저장합니다.

그후 두 윤곽선의 각도의 차이를 계산한 후 노름(norm)함수를 통해서 길이를 구합니다.

Norm(노름) : 벡터의 길이 혹은 크기를 측정하는 방법(함수)입니다. Norm이 측정한 벡터의 크기는 원점에서 벡터 좌표까지의 거리 혹은 Magnitude라고 합니다.

1
2
3
4
5
6
7
if (dist > EDGE_MAX_LENGTH or
        x_overlap > EDGE_MAX_OVERLAP or
        delta_angle > EDGE_MAX_ANGLE):
    return None
else:
    score = dist + delta_angle*EDGE_ANGLE_COST
    return (score, cinfo_a, cinfo_b)

거리가 100보다 크거나 제일큰 측정 간격 차이가 1보다 크거나 각도가 윤곽선 각도 차이가 7.5도 이상이 아니라면 해당 윤곽선들에 점수(score)를 매깁니다.
해당 이유는 위 조건이 충족되지 않으면 연속적인 가로줄이라고 보기 힘들다고 판단하기 때문입니다.

윤곽선의 계승자와 전임자 설정

1
2
3
4
5
6
7
8
9
# sort candidate edges by score (lower is better)
candidate_edges.sort()

# for each candidate edge
for _, cinfo_a, cinfo_b in candidate_edges:
    # if left and right are unassigned, join them
    if cinfo_a.succ is None and cinfo_b.pred is None:
        cinfo_a.succ = cinfo_b
        cinfo_b.pred = cinfo_a

전에 측정한 점수(score)는 작은 값일 수록 더 좋다고 판단합니다. 그렇기 때문에 sort()로 정렬을 합니다.

그다음 for문을 통해 후보군 중 서로의 정보가 저장되있지 않는 후보군들의 윤곽선 정보 클래스에 서로의 정보를 저장합니다.

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
# generate list of spans as output
spans = []

# until we have removed everything from the list
while cinfo_list:

    # get the first on the list
    cinfo = cinfo_list[0]

    # keep following predecessors until none exists
    while cinfo.pred:
        cinfo = cinfo.pred

    # start a new span
    cur_span = []

    width = 0.0

    # follow successors til end of span
    while cinfo:
        # remove from list (sadly making this loop *also* O(n^2)
        cinfo_list.remove(cinfo)
        # add to span
        cur_span.append(cinfo)
        width += cinfo.local_xrng[1] - cinfo.local_xrng[0]
        # set successor
        cinfo = cinfo.succ

    # add if long enough
    if width > SPAN_MIN_WIDTH:
        spans.append(cur_span)

이제 최종적으로 윤곽선을 붙이는 작업을 시작합니다. 앞에서 서로 이어 붙이기가 가능한 윤곽선 끼리는 서로의 정보를 cinfo.pred와 cinfo.succ로 저장했습니다.(윤곽선의 앞, 뒤정보)

이제 윤곽선을 while문으로 하나씩 탐색합니다. 

1
2
while cinfo.pred:
    cinfo = cinfo.pred

처음으로 가장 끝에있는 전임자(pred)를 찾습니다. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
        # follow successors til end of span
        while cinfo:
            # remove from list (sadly making this loop *also* O(n^2)
            cinfo_list.remove(cinfo)
            # add to span
            cur_span.append(cinfo)
            width += cinfo.local_xrng[1] - cinfo.local_xrng[0]
            # set successor
            cinfo = cinfo.succ
```            

그러고 그 정보를 원래의 윤곽선 정보클래스(cinfo_list)에서 제거합니다. 그후 `cur_span`배열에 내용을 저장합니다. 그후 후임자(succ)로 이동하여(앞으로 이동) 계속 같은 작업을 반복합니다.

```py
        # add if long enough
        if width > SPAN_MIN_WIDTH:
            spans.append(cur_span)

마지막 까지 정보를 취합하고 총 넓이가 충분한지 판단합니다. 넓이가 충분하다면 값을 저장합니다.

visualize_spans

디버깅을 위해 생성한 span을 이미지를 통해 보여줍니다.

1
2
3
4
5
6
7
8
def visualize_spans(name, small, pagemask, spans):

    regions = np.zeros_like(small)

    for i, span in enumerate(spans):
        contours = [cinfo.contour for cinfo in span]
        cv2.drawContours(regions, contours, -1,
                         CCOLORS[i*3 % len(CCOLORS)], -1)

일단 이미지와 같은 크기의 (0으로 채운)배열을 생성합니다. 그후 for문을 통해 윤곽선을 그려줍니다.

span in resions

1
2
3
4
5
6
7
mask = (regions.max(axis=2) != 0)

display = small.copy()
display[mask] = (display[mask]/2) + (regions[mask]/2)
display[pagemask == 0] /= 4

debug_show(name, 2, 'spans', display)

다음으로 윤곽선이 그려진 좌표만을 mask배열에 저장합니다. resions는 기본적으로 검정색 배경(0,0,0)에 윤곽선이 그려진 형태이기 때문에 max(axis=2) != 0으로 판단하면 윤곽선의 좌표만을 취득할 수 있습니다.

그것을 기존 이미지에 덮습니다. 일단 기존이미지의 윤곽선 부분을 흐릿하게 만듭니다. 방법은 mask의 좌표 부분만 2를 나누어(display[mask]/2) 검정에 가깝게 만듭니다.

display[mask]/2

역시 기존 이미지에 윤곽선 부분(mask)에 색깔을 입힌 것(regions[mask]/2)을 설정합니다.

regions[mask]/2

두 이미지를 합쳐 형광펜처럼 색깔을 입힌 후 테두리 부분을 나누기 4(display[pagemask == 0] //= 4)를 해서 액자처럼 테두리를 어둡게 만듭니다.

spans

텍스트가 부족할때

텍스트가 부족해서 충분한 윤곽선(3개 이상)이 확보되지 않으면 이미지에서 가로줄을 탐색합니다.

1
2
3
4
5
6
if len(spans) < 3:
    print ('  detecting lines because only', len(spans), 'text spans')
    cinfo_list = get_contours(name, small, pagemask, 'line')
    spans2 = assemble_spans(name, small, pagemask, cinfo_list)
    if len(spans2) > len(spans):
        spans = spans2

아래 이미지처럼 텍스트로 가로 윤곽선이 부족하고 line을통해 찾을 수 있다면 line을 탐색합니다.

line 이미지

1
2
3
if len(spans) < 1:
    print ('skipping', name, 'because only', len(spans), 'spans')
    continue

text와 line 모두 윤곽선 탐색이 불가능하면 page dewarp 작업을 중지합니다.

공유하기