본 논문은 명암 영상에서 최단 경로 알고리즘을 이용해 인쇄체 접합 문자를 비선형으로 분리하는 방법을 제안한다. 기존의 최단 경로 알고리즘은 특정한 형태의 접합문자를 분할하지 못하는 단점을 가지고 있다. 우리는 기존 알고리즘이 실패하는 상황을 분석하고, 분석 결과를 활용하여 기존 알고리즘이 사용하는 규칙의 문제점을 파악하였다. 그런 후 기존 알고리즘을 두 가지 방향에서 개선하였다. 첫째, 새로운 벌칙항을 추가하여 보다 정교한 경로를 추정하였다. 둘째, 경로 탐색 시 상향 탐색과 하향 탐색을 병행하고 보다 좋은 해를 선택하였다. 실험을 통해 제안하는 알고리즘이 기존 알고리즘에 비해 분할 성공률 면에서 3~4%정도 우수함을 입증하였다.
The paper proposes an algorithm which finds a nonlinear cut path for a printed grayscale touching character image. The conventional algorithms were observed to fail in situations of complicated touching. We analyzed those situations, and based on the analysis results we identified problematic issues of the conventional algorithms. We modified the conventional algorithms in two aspects. First we propose a new penalizing term which is probable to guide correctly the cut path for touching situations difficult to separate. Second the preposed algorithm adopts a strategy of producing both the downward and upward paths and selecting better one. The experimental results on actual touching character images showed that the proposed algorithm was superior th conventional algorithms by 3~4% in terms of success ratio of separation.
