[논문]DTW와 PCA에 기반한 효과적인 필적 검증

장석우; 허문행; 김계영

doi:10.9708/jksci.2009.14.7.025

DTW와 PCA에 기반한 효과적인 필적 검증
Effective Handwriting Verification through DTW and PCA 원문보기

韓國컴퓨터情報學會論文誌 = Journal of the Korea Society of Computer and Information, v.14 no.7, 2009년, pp.25 - 32

장석우 (안양대학교 디지털미디어학과) , 허문행 (안양대학교 디지털미디어학과) , 김계영 (숭실대학교 IT대학 컴퓨터공학부)

초록
AI-Helper

논문에서는 오프라인 환경에서 패턴분석을 적용하여 두필적의 유사성을 자동으로 분석하여 필적을 검증하는 방법을 제안한다. 제안된 방법에서는 먼저 필적 문서에서 문자 영역만을 분할하고, 분할된 문자 영역에 대한 특징을 추출한다. 그리고 비선형적인 형태로 추출되는 특징으로부터 동적 타임 워핑(DTW)과 다변량 통계 분석법(PCA) 알고리즘을 이용하여 기준이 되는 특징과의 유사성을 구한다. 본 논문에서 제안된 필적 검증 방법은 효과적인 특징 추출 방법 및 기존의 짧은 패턴에서 효과적으로 수행하던 방법들을 다양한 길이를 가진 특징에 대해서도 효과적으로 필적 검증이 가능하도록 하였다. 본 논문은 실험 결과는 제안된 방법인 기존의 방법보다 우수함을 다양한 실험을 통해서 보여준다. 제안된 필적 검증 방법은 기존에 감정 전문가에 의해 수동적으로 수행되던 필적 검증 작업을 자동화하고, 기존 필적 검증 작업의 객관성을 배가할 수 있을 것으로 기대된다.

Abstract ▼ AI-Helper

In this paper, we propose a new handwriting verification method using pattern analysis in off-line environments. The proposed method first segments character regions in a document and extracts effective features from the segmented regions. It then estimates the similarity between the extracted non-linear features and reference ones by using dynamic time warping and principal component analysis. Our handwriting verification method extracts handwriting features effectively and enables the verification of handwriting with various lengths of features as well as ones of short patterns. The experimental results show that our method outperforms others in terms as accuracy. We expect that the proposed method will automate the manual handwriting verification tasks and provide much objectivity on handwriting identification.

주제어

AI 본문요약
AI-Helper

* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.

문제 정의

획을 이용하여 비교를 하기 위하여 추출되는 특징은 크기와 모양 및 방향이 일치해야 한다는 기준을 가지게 된다. 그러나 크기는 문자열 전체에서 일관성만 있으면 문제가 되지 않으므로 본 방법을 통하여 모양과 방향 정보를 사용하여 지역적인 특징 정보를 산출하고, 문자 크기에 독립적이고 모양과 방향에 따라 다른 평가가 가능한 특징을 추출하고자 한다.
따라서 본 논문에서는 오프라인 환경에서 한글 필적(서명) 에 대한 특징 추출과 분석을 위한 새로운 방법을 제시한다. 본 논문에서는 기존 연구의 문제점인 한글 비교 분석을 가능하도록 하기 위해 한글 필적에 대한 문자 영역 추출 방법을 연구하고, 추출된 문자 영역에서의 효과적인 특징 추출 및 기존에 짧은 패턴 위주로 효과적으로 수행하던 방법들을 다양한 길이를 가진 개인별 특징에 대해 비교 분석하는 방법을 제안한다.
제시한다. 본 논문에서는 기존 연구의 문제점인 한글 비교 분석을 가능하도록 하기 위해 한글 필적에 대한 문자 영역 추출 방법을 연구하고, 추출된 문자 영역에서의 효과적인 특징 추출 및 기존에 짧은 패턴 위주로 효과적으로 수행하던 방법들을 다양한 길이를 가진 개인별 특징에 대해 비교 분석하는 방법을 제안한다.
이러한 연구 분야를 보통 필적 감정이라 하며, 일반적으로 감정 전문가가 이를 수행하지만, 주관적이라는 단점이 있고, 소모 시간과 비용의 문제를 가지게 된다. 본 논문은 이러한 문제점을 해결하기 위해 컴퓨터를 이용한 패턴 인식을 통해 객관적이고 효율적인 판단을 하는 방법을 제시한다.

제안 방법

학습 단계에서는 필적 학습 영상을 받아들인 후 문자영역을 분할하고 분할된 영역에 대한 특징을 추출하여 저장한다. 검증 단계에서는 입력된 필적 실험 영상으로부터 학습 단계와 동일한 과정을 거쳐 특징을 추출한 후 동적 타임 워핑 (DTW)과 다변량 통계분석(PCA) 알고리즘을 이용하여 비선형적인 형태로 추출된 특징들을 정합한 후 이들 사이의 유사도를 검출한다.
오프라인 검증 방식을 이용하여 필적 및 서명에 대하여 스캐너 및 기타 입력장치를 통하여 입력을 받은 후 입력받은 필적에 대하여 최소 포함 사각형을 계산하는 연산을 이용해 문자 영역을 추출한다. 그런 다음 필적의 궤적을 추적하는 방식의 특징 추출 과정을 거치고, 동적 프로그래밍 방법을 이용한 nonlinear-PCA 알고리즘을 통한 학습 방법을 이용하여 개인의 고유한 필적 개성을 분석한다. 그리고 PCA를 통해 도출된 결과를 마할라노비스 거리 알고리즘을 통하여 유사도를 도출하는 방식을 제안한다.
그런 다음 필적의 궤적을 추적하는 방식의 특징 추출 과정을 거치고, 동적 프로그래밍 방법을 이용한 nonlinear-PCA 알고리즘을 통한 학습 방법을 이용하여 개인의 고유한 필적 개성을 분석한다. 그리고 PCA를 통해 도출된 결과를 마할라노비스 거리 알고리즘을 통하여 유사도를 도출하는 방식을 제안한다.
본 논문에서는 A, B, C, D, E의 5개 그룹에 대한 실험결과를 표 1에서 표3까지 정리하였다. 그리고 표 내부의 음영 표시된 영역은 같은 필적을 비교하였을 때를 표시하고, 투영 방법과 제안된 방법에 대한 비교를 수행하기 위하여 2개의 항목으로 따로 결과를 나타내었다.
본 논문에서 제안된 특징 추출 방법 및 다양한 길이를 가진 개인별 특징에 대해 비교 분석하는 실험을 하였다. 실험 결과를 보이기 위해 A, B, C.
본 논문에서 제안하는 문자의 특징 추출 방법은 문서 영상의 각 문자의 획에 대하여 중심점과의 거리 정보를 이용한 방법을 사용한다. 획을 이용하여 비교를 하기 위하여 추출되는 특징은 크기와 모양 및 방향이 일치해야 한다는 기준을 가지게 된다.
그리고, "와 R? 는 Ri 의 가로의 길이 및 세로의 길이를 표현한다. 본 논문에서는 계산된 거리 에 대하여 임계 거리 TH 보다 작은 사각형을 통합하여 문자 영역을 추출하고, 통합된 최소 포함 사각형에 대한 중심점과 가로 및 세로의 길이를 식 (2) 와같이 설정한다.
흑 화소들의 위치를 추적하기 위해 시작점을 검출하고, 한글 및 여러 문자의 필기체 특징상 왼쪽에서 오른쪽으로 쓰이는 점에 착안하여 좌측 상단에 각각 가중치를 주어 시작점을 찾는다〔12〕. 시작점을 선정한 후 추출된 점들을 후보군으로 분류하여 다음 추적 대상을 반복적으로 탐색하여 점들의 다음 시작점을 결정함으로써 전체 획에 대한 추적을 가능하게 한다.
방식은 다음과 같다. 오프라인 검증 방식을 이용하여 필적 및 서명에 대하여 스캐너 및 기타 입력장치를 통하여 입력을 받은 후 입력받은 필적에 대하여 최소 포함 사각형을 계산하는 연산을 이용해 문자 영역을 추출한다. 그런 다음 필적의 궤적을 추적하는 방식의 특징 추출 과정을 거치고, 동적 프로그래밍 방법을 이용한 nonlinear-PCA 알고리즘을 통한 학습 방법을 이용하여 개인의 고유한 필적 개성을 분석한다.
이와 같이 추출된 정규화된 거리 L을 이용하여 추출된 특징을 획별로 관리하여 특징으로 이용한다.
그림 2의 3 단계에서 녹색 사각형은 자소 단위의 영역, 빨간 사각형은 문자 단위의 영역, 파란 사각형은 문단 단위의 영역을 의미한다. 자소 단위로 검출된 영역을 통합하여 문자 단위의 영역을 검출하는 과정에서는 일정한 거리를 기준으로 문자와 단어가 구분된다는 사실을 이용하는데, 이를 위해 각 자소 단위의 영역에 대한 최소 포함 사각형 사이의 거리를 추출해 비교한다. 각 자소에 대응하는 최소 포함 사각형 4와 Az 사이의 거리 & 는 식 (1)과 같이 계산한다.
추출한다. 학습 문자열의 특징에 대한 공분산 C 및 고유 벡터 e를 이용하여 분석할 문자열과의 정합 과정을 거쳐 변위를 측정하고 분석할 문자열의 특징 정보를 F로 저장한다. 분석할 문자열의 특징 F, 학습된 특징의 공분산 C와 학습된 특징 벡터값 φ을 이용하여 산출한 분석된 특징 사이의 거리정보 MD는 식 (12)와 같이 표현할 수 있다.

대상 데이터

따라서 5개 실험군에 대해서는 실험군 1개당 100개씩 총 500 개의 필적을 사용한다. 그리고 각 실험군의 본인 필적 20개 중 5개, 10개, 15개의 입력된 필적을 대상으로 학습하여 실험을 진행하였다. 본 논문에서는 A, B, C, D, E의 5개 그룹에 대한 실험결과를 표 1에서 표3까지 정리하였다.
D, E의 5개 실험군을 선정하고, 각 실험군별로 본인 필적 20개와 나머지 실험군으로부터 받은 대리 필적 80개, 즉 총 100개의 필적을 제공받았다. 따라서 5개 실험군에 대해서는 실험군 1개당 100개씩 총 500 개의 필적을 사용한다. 그리고 각 실험군의 본인 필적 20개 중 5개, 10개, 15개의 입력된 필적을 대상으로 학습하여 실험을 진행하였다.
본 실험을 위하여 사용한 컴퓨터는 인텔 Pentium Core 2 Duo의 CPU와 1GB의 메모리를 사용하였고, 운영체제는 마이크로소프트사의 Windows XP Home edition을 사용하였으며, 컴파일러는 Visual C++ 8.0을사용하여 제작하였다.
실험 결과를 보이기 위해 A, B, C. D, E의 5개 실험군을 선정하고, 각 실험군별로 본인 필적 20개와 나머지 실험군으로부터 받은 대리 필적 80개, 즉 총 100개의 필적을 제공받았다. 따라서 5개 실험군에 대해서는 실험군 1개당 100개씩 총 500 개의 필적을 사용한다.

데이터처리

기존에 연구된 투영을 통한 방법〔8〕과 본 논문에서 제안한 특징 주줄과 비교분석 방법의 두 가지 특징을 비교하여 그 결과를 표 1에서부터 표 3까지 표시 하였으며, 실험결과를 통하여 제안하는 방법의 우수성과 제안하는 분석 방법에 대하여 다른 방법과의 비교를 통하여 그 차이를 보이고 있다. 기존의 연구 방법인 투영을 통한 방법은 입력을 받은 영상에 대해 투영 방법을 이용하여 문자열에 대한 특징을 추출하고, DTW 알고리즘을 이용하여 비교 분석한 방법이다.

이론/모형

본 논문에서는 위와 같은 학습을 수행한 후 최종적인 유사도를 도출하기 위하여 문자열과의 비교를 위해 마할라 노비스 거리 알고리즘을 이용한다. 마할라노비스 거리 알고리즘은 군집 분석에서 가장 많이 사'용되는 거리 개념이다.

성능/효과

그러나 실험결과를 통하여 제안하는 분석 방법의 몇 가지 문제점을 확인하였다. 그 문제점은 표 3에서 확인할 수 있듯이 학습된 문자열의 양이 많을 경우 학습되는 문자열이 상이한 상태를 가지게 되어 여러 학습된 문자열들의 패턴이 모호해져 오히려 비유사도가 증가함을 알 수가 있었다. 실제로 표 3의 C와 D의 학습 패턴에서 이런 현상이 발생하였으며 , 5회의 학습에서 좋은 결과를 보이던 결과들이 10회 이상의 학습 결과에서 가장 비유사도가 높은 문자열로 분류됨을 알 수 있었다.
본 논문에서는 실험결과를 통하여 기존의 방법 보다 제안된 방법이 더 높은 변별력을 가짐을 알 수 있었다. 제안된 특징 추출 방법으로 인하여 기존의 투영 방법으로 시행하던 방법 상의 두께 정보보다 개인의 필순에 따라 유사도 도출이 정확도 있게 문자열 간의 유사도를 도출해 낼 수 있음을 실험을 통해 알 수 있었고, 5회 정도의 짧은 학습을 통하여 좋은 결과를 보였음을 확인할 수 있었다.
그 문제점은 표 3에서 확인할 수 있듯이 학습된 문자열의 양이 많을 경우 학습되는 문자열이 상이한 상태를 가지게 되어 여러 학습된 문자열들의 패턴이 모호해져 오히려 비유사도가 증가함을 알 수가 있었다. 실제로 표 3의 C와 D의 학습 패턴에서 이런 현상이 발생하였으며 , 5회의 학습에서 좋은 결과를 보이던 결과들이 10회 이상의 학습 결과에서 가장 비유사도가 높은 문자열로 분류됨을 알 수 있었다.
방법이 더 높은 변별력을 가짐을 알 수 있었다. 제안된 특징 추출 방법으로 인하여 기존의 투영 방법으로 시행하던 방법 상의 두께 정보보다 개인의 필순에 따라 유사도 도출이 정확도 있게 문자열 간의 유사도를 도출해 낼 수 있음을 실험을 통해 알 수 있었고, 5회 정도의 짧은 학습을 통하여 좋은 결과를 보였음을 확인할 수 있었다.

후속연구

향후 연구는 보다 다양한 학습 및 입력 자료를 기반으로 한 실험과 본 논문에서 사용하는 파라미터를 자동적으로 조율하는 방법에 관한 연구라 사료된다.

참고문헌 (16)

Basabi Chakraborty, Goutam Chakraborty, "A New Feature Extraction

상세보기
Kai Huang, Hong Yan "Off-line Signature Verification using Structural

상세보기
Alan McCabe "Hidden Markov Modeling with Simple Directional Features for Effective and Efficient Handwriting Verification," International Journal of Tuberculosis and Lung Disease, Vol. 5, No. 3, pp. 216-219, 1988.
Edson J. R. Justino, Flavio Bortolozzi, Robert Sabourin, "A Comparison

상세보기
Marc Parizeau, Rejean Plamondon, "A Comparative Analysis of Regional Correlation, Dynamic Time Warping, and Skeletal Tree Matching for Signature Verification," IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 12, No. 7, pp. 710-717, 1990

상세보기
B. Fang, C. H. Leung, Y. Y. Tang, K. W. Tse, P. C. K. Kwork, Y. K. Wong, "Off-line Signature Verification by the Tracking of Feature and Stroke Positions," Pattern Recognition, Vol. 36, No. 1, pp. 91-101, 2003.

상세보기
박희주, 김진호, 오광식, "새로운 자소분리 기법을 이용한 필기체 한글 인식 시스템," 한국퍼지 및 지능시스템학회 논문지, 제 5권, 제 3호, 101-110쪽, 1995년
김세훈, 하정요, 김계영, 최형일, "필적 및 서명에 대한 Off-line 자동 분석 시스템," HCI 학술대회논문집, 제 3권, 189-193쪽, 2007년
김계영, "지역특징과 지역특징을 통한 필기문자열의 품질 평가시스템" 한국인터넷정보학회논문지, 제 5권, 제 6호, 121-128쪽, 2004년 12월

원문보기 상세보기
유대근, 김경환, "한글 필기체의 구조적 특징을 이용한 효과적 기울기 보정,"
조완현, "문자 인식의 소개 및 새로운 인식시스템의 개발." 한국통계학회 춘계학술발표회 논문집, 68-74쪽, 1998년 1월
윤성수, 변혜란, 이일병, "인간의 정보처리 방법에 기반한 특징추출 및 필기체 문자인식에의 응용," 한국인지과학회논문지, 제 9권, 제 1호, 1-11쪽, 1998년
Eamonn J. Keogh, Michael J. Pazzani, "Derivative Dynamic Time Warping." First SIAM International Conference on Data Mining, 2001.
한수영, 김홍렬, 이기희, "에너지 라벨링 그룹화를 이용한 고속 음성인식시스템," 한국컴퓨터정보학회논문지, 제 9권, 제 4호, 77-83쪽, 2004년 9월

원문보기 상세보기
Lindsay I Smith "A Tutorial on Principal Components Analysis," Technical Report, University of Otago, Feb. 2002.
김명훈, 이지근, 소인미, 정성태, "얼굴과 음성 정보를 이용한 바이모달 사용자 인식 시스템 설계 및 구현," 한국컴퓨터정보학회논문지, 제 10권, 제 5호, 353-362쪽, 2005년 11월

원문보기 상세보기

저자의 다른 논문 :

표제어: PCR

동의어: Packet Collision Rate

용어 설명 출처 목록 (6)

용어 설명: PCR은 세균 특이성이 있는 primer를 이용하여 적은 수의 세균이 있을지라도 쉽게 검출할 수 있는 유용한 방법이며, 이를 이용하여 구강 내 치면세균막이나 타액에서 직접 세균을 검출할 수 있게 되었다[8].

내보내기 구분	파일저장 인쇄 메일전송
구성항목	기본정보 상세정보 관리번호, 논문명, 저널/프로시딩명, 저자 , 발행년, 권, 호, 시작페이지, 끝페이지, 발행기관 관리번호, 논문명, 대등논문명, 저자 , 저널/프로시딩명, 발행기관, 발행년, 발행언어, 권, 호, 시작페이지, 끝페이지, ISBN, ISSN, 주제분야, 키워드, 초록(한글), 초록(영문), 저자(소속기관)
저장형식	Text(ASCII format) Excel format RefWorks Direct Export RIS format (for Reference Manager, ProCite, EndNote), Scholar's Aids, Mendeley
메일정보	받는사람 (필수) @ 보내는사람 (선택) @ 제목 내용 KISTI 검색결과 이메일 서비스
안내	총 건의 자료가 검색되었습니다. 다운받으실 자료의 인덱스를 입력하세요. (1-10,000) 검색결과의 순서대로 최대 10,000건 까지 다운로드가 가능합니다. 데이타가 많을 경우 속도가 느려질 수 있습니다.(최대 2~3분 소요) 다운로드 파일은 UTF-8 형태로 저장됩니다. 파일의 내용이 제대로 보이지 않을실 때는 웹브라우저 상단의 보기 -> 인코딩 -> 자동선택 여부를 확인하십시오. ~ Text(ASCII format) Excel format

연합인증