KR101687941B1 - 온라인 필기 데이터 라인 분할 방법 및 이를 이용하는 장치 - Google Patents

Abstract

본 발명의 일 실시예에 따른 온라인 필기 데이터 라인 분할 방법이 제공된다. 온라인 필기 데이터 라인 분할 방법은 복수의 획을 복수의 그룹으로 그룹화하는 단계, 복수의 그룹 중 연속하는 그룹으로 이루어진 그룹 세트의 클래스를 추정하는 단계, 추정된 그룹 세트의 클래스를 비교하여, 그룹 세트의 그룹 각각이 동일 라인에 있는지 여부를 결정하는 단계를 포함하는 것을 특징으로 한다. 본 발명의 일 실시예에 따르면, 분류기의 분류 결과에 대한 검증 과정을 통해 분류기의 신뢰성을 향상시키고, 나아가 라인 분할에 대한 정확성을 향상시킨 온라인 필기 데이터 라인 분할 방법 및 이를 이용하는 장치를 제공할 수 있다.

Description

온라인 필기 데이터 라인 분할 방법 및 이를 이용하는 장치{METHOD FOR ONLINE HANDWRITTEN TEXT DATA LINE SEGMENTATION AND APPARATUS USING THE SAME}

본 발명은 온라인 필기 데이터 라인 분할 방법 및 이를 이용하는 장치에 관한 것으로서, 보다 상세하게는 분류기를 이용한 온라인 필기 데이터 라인 분할 방법 및 이를 이용하는 장치에 관한 것이다.

전자 디바이스에 문자를 입력하기 위해서 키보드, 키 패드, 음성 등 다양한 매체가 이용되고 있다. 키보드 또는 키 패드를 이용한 문자 입력은 이진화된 문자를 입력하는 것으로서, 기존까지 가장 대중적인 문자 입력 방식이었다. 그러나, 터치 스크린 입력 방식이 대중화되면서, 손가락이나 스타일러스(stylus) 팬에 의해 문자를 필기하는 방법이 점차 확산되고 있다.

터치 스크린 입력 방식이 확산됨에 따라, 전자 디바이스 상에서 필기된 문자가 인식되어, 이진수의 문자열로 변환되는 온라인 필기 데이터 인식 기능이 도입되었다. 이러한 온라인 필기 데이터 인식 기능에서는 전처리 단계에서 온라인 필기 데이터를 라인별로 분할하는 것이 선행된다.

즉, 전자 디바이스 상에 필기된 문자들 중 어디까지가 하나의 라인을 형성하는지를 검출해낼 필요가 있다. 관련하여, 온라인 필기 데이터의 라인 분할을 검출하기 위한 다양한 방법들이 도입되었으나, 충분히 높은 정확도를 갖는 온라인 필기 데이터 라인 분할 방식이 지속적으로 요구되고 있다.

본 발명이 해결하고자 하는 과제는, 보다 정확한 온라인 필기 데이터 라인 분할 방법을 제공하여, 전자 디바이스에서의 보다 정확한 온라인 필기 데이터 인식을 제공하는 것이다.

본 발명이 해결하고자 하는 과제는, 분류기의 분류 결과에 대한 검증 과정을 통해 분류기의 신뢰성이 향상되고, 나아가 라인 분할에 대한 정확성이 향상된 온라인 필기 데이터 라인 분할 방법 및 이를 이용하는 장치를 제공하는 것이다.

본 발명의 과제들은 이상에서 언급한 과제들로 제한되지 않으며, 언급되지 않은 또 다른 과제들은 아래의 기재로부터 당업자에게 명확하게 이해될 수 있을 것이다.

전술한 바와 같은 과제를 해결하기 위하여 본 발명의 일 실시예에 따른 온라인 필기 데이터 라인 분할 방법은 복수의 획(stroke)을 복수의 그룹으로 그룹화하는 단계, 복수의 그룹 중 연속하는 그룹으로 이루어진 그룹 세트의 클래스를 추정하는 단계, 추정된 그룹 세트의 클래스를 비교하여, 그룹 세트의 그룹 각각이 동일 라인에 있는지 여부를 결정하는 단계를 포함하는 것을 특징으로 한다.

본 발명의 다른 특징에 따르면, 복수의 획을 복수의 그룹으로 그룹화하는 단계는, 복수의 획 중 y축 또는 x축에 대하여 적어도 일부 중첩하는지 여부 등의 공간적 특성에 기초하여, 동일 라인에 있다고 확실하게 판단되는 복수의 획을 하나의 그룹으로 그룹화하는 단계를 포함하는 것을 특징으로 한다.

본 발명의 또 다른 특징에 따르면, 복수의 획을 하나의 그룹으로 그룹화하는 단계는 복수의 획 각각의 시간 특성에 또한 기초하여, 동일 라인에 있다고 확실하게 판단되는 복수의 획을 하나의 그룹으로 그룹화하는 단계를 포함하는 것을 특징으로 한다.

본 발명의 또 다른 특징에 따르면, 그룹 세트를 구성하는 단계는 연속된 앞과 뒤의 그룹 세트가 중복된 서브 그룹 세트를 갖도록 구성하는 것을 특징으로 한다.

본 발명의 또 다른 특징에 따르면, 그룹 세트의 클래스를 추정하는 단계는 연속하는 2개의 그룹이 동일한 라인에 있는지를 추정하는 단계를 포함하는 것을 특징으로 한다.

본 발명의 또 다른 특징에 따르면, 연속하는 2개의 그룹이 동일한 라인에 있는지를 추정하는 단계는, 2개의 그룹 사이의 x축 거리, 그룹의 전체 데이터를 바탕으로 한 y축 중심 높이 차와 y축 중첩 거리, y축 히스토그램을 바탕으로 한 y축 중심 높이 차와 y축 중첩 거리 또는 2개의 그룹이 하나의 라인에 있다고 가정 시 하나의 라인의 폭과 높이 중 적어도 하나에 기초하여 추정하는 단계인 것을 특징으로 한다.

본 발명의 또 다른 특징에 따르면, 그룹 세트의 클래스를 추정하는 단계는 기계학습을 기반으로 하는 분류기를 이용하여 수행되는 것을 특징으로 한다.

본 발명의 또 다른 특징에 따르면, 분류기는 랜덤 포레스트(random forest) 인 것을 특징으로 한다.

본 발명의 또 다른 특징에 따르면, 온라인 필기 데이터 라인 분할 방법은 그룹 세트의 그룹 각각이 동일 라인에 있는지 여부를 기초로 라인 세트를 생성하는 단계를 더 포함하는 것을 특징으로 한다.

본 발명의 또 다른 특징에 따르면, 그룹 세트의 그룹 각각이 동일 라인에 있는지 여부를 결정하는 단계는, 추정된 그룹 세트의 클래스가 서로 모순된 경우, 모순되는 그룹 세트의 그룹이 동일 라인에 있는지 여부를 결정하는 단계를 포함하는 것을 특징으로 한다.

본 발명의 또 다른 특징에 따르면, 그룹 세트의 그룹 각각이 동일 라인에 있는지 여부를 결정하는 단계는, 추정된 그룹 세트의 클래스가 서로 모순된 경우, 그룹 세트의 클래스를 재추정하는 단계 및 재추정된 그룹 세트의 클래스를 비교하는 단계를 포함하는 것을 특징으로 한다.

본 발명의 또 다른 특징에 따르면, 그룹 세트의 클래스를 재추정하는 단계는 그룹 세트의 클래스를 추정하는 단계에서 사용된 방식과는 상이한 분류기를 이용하여 수행되는 것을 특징으로 한다.

본 발명의 또 다른 특징에 따르면, 온라인 필기 데이터 라인 분할 방법은 복수의 그룹 앞 또는 뒤에 위치하는 더미 그룹을 생성하는 단계를 더 포함하고, 연속하는 그룹은 복수의 그룹 앞 또는 뒤에 위치하는 더미 그룹을 포함하는 것을 특징으로 한다.

본 발명의 또 다른 특징에 따르면, 온라인 필기 데이터 라인 분할 방법은 그룹화하는 단계 이전에 복수의 획의 기울어짐(skew)을 정규화하는 단계를 더 포함하는 것을 특징으로 한다.

전술한 바와 같은 과제를 해결하기 위하여 본 발명의 일 실시예에 따른 온라인 필기 데이터 라인 분할 장치는 프로세서 및 프로세서와 연결되고, 복수의 획에 대한 입력을 감지하도록 구성된 입력 감지부를 포함하고, 프로세서는, 입력 감지부로부터의 복수의 획을 복수의 그룹으로 그룹화하고, 복수의 그룹 중 연속하는 그룹으로 이루어진 그룹 세트의 클래스를 추정하고, 추정된 그룹 세트의 클래스를 비교하여, 그룹 세트의 그룹 각각이 동일 라인에 있는지 여부를 결정하도록 구성된 것을 특징으로 한다.

본 발명의 또 다른 특징에 따르면, 프로세서는 기계학습을 기반으로 하는 랜덤 포레스트 분류기를 이용하여 그룹 세트의 클래스를 추정하도록 구성된 것을 특징으로 한다.

본 발명의 또 다른 특징에 따르면, 프로세서는, 추정된 그룹 세트의 클래스가 서로 모순된 경우, 모순되는 그룹 세트의 그룹이 동일 라인에 있는지 여부를 추가로 수행하도록 구성된 것을 특징으로 한다.

본 발명의 또 다른 특징에 따르면, 프로세서는, 복수의 그룹 앞 또는 뒤에 위치하는 더미 그룹을 생성하도록 더 구성되고, 연속하는 그룹은 복수의 그룹 앞 또는 뒤에 위치하는 위치하는 더미 그룹을 포함하는 것을 특징으로 한다.

기타 실시예의 구체적인 사항들은 상세한 설명 및 도면들에 포함되어 있다.

본 발명은 보다 정확한 온라인 필기 데이터의 라인 분할 방법을 제공하여, 전자 디바이스에서의 보다 정확한 온라인 필기 데이터 인식을 제공할 수 있다.

또한 본 발명은, 분류기의 분류 결과에 대한 검증 과정을 통해 분류기의 신뢰성을 향상시키고, 나아가 라인 분할에 대한 정확성을 향상시킨 온라인 필기 데이터 라인 분할 방법 및 이를 이용하는 장치를 제공할 수 있다.

본 발명에 따른 효과는 이상에서 예시된 내용에 의해 제한되지 않으며, 더욱 다양한 효과들이 본 명세서 내에 포함되어 있다.

도 1은 본 발명의 일 실시예에 따른 온라인 필기 데이터 라인 분할 장치의 블록도이다.
도 2는 본 발명의 일 실시예에 따른 온라인 필기 데이터 라인 분할 방법을 설명하기 위한 개략적인 흐름도이다.
도 3은 본 발명의 일 실시예에 따른 온라인 필기 데이터 라인 분할 방법의 구체적인 동작을 설명하기 위한 흐름도이다.
도 4 내지 도 7은 본 발명의 일 실시예에 따른 온라인 필기 데이터 라인 분할 방법을 설명하기 위한 개략도들이다.
도 8은 본 발명의 다양한 실시예에 따른 온라인 필기 데이터 라인 분할 방법을 설명하기 위한 개략도이다.

본 발명의 이점 및 특징, 그리고 그것들을 달성하는 방법은 첨부되는 도면과 함께 상세하게 후술되어 있는 실시예들을 참조하면 명확해질 것이다. 그러나 본 발명은 이하에서 개시되는 실시예들에 한정되는 것이 아니라 서로 다른 다양한 형태로 구현될 것이며, 단지 본 실시예들은 본 발명의 개시가 완전하도록 하며, 본 발명이 속하는 기술분야에서 통상의 지식을 가진 자에게 발명의 범주를 완전하게 알려주기 위해 제공되는 것이며, 본 발명은 청구항의 범주에 의해 정의될 뿐이다.

비록 제1, 제2 등이 다양한 구성요소들을 서술하기 위해서 사용되나, 이들 구성요소들은 이들 용어에 의해 제한되지 않음은 물론이다. 이들 용어들은 단지 하나의 구성요소를 다른 구성요소와 구별하기 위하여 사용하는 것이다. 따라서, 이하에서 언급되는 제1 구성요소는 본 발명의 기술적 사상 내에서 제2 구성요소일 수도 있음은 물론이다.

명세서 전체에 걸쳐 동일 참조 부호는 동일 구성 요소를 지칭한다. 본 발명의 여러 실시예들의 각각 단계들이 순차적으로 또는 연관하여 실행 가능하며, 당업자가 충분히 이해할 수 있듯이 기술적으로 다양한 순서 변형이 가능하며, 각 실시예들이 서로에 대하여 독립적으로 실시 가능할 수 있고 연관 관계로 함께 실시 가능할 수도 있다.

이하, 첨부된 도면을 참조하여 본 발명의 다양한 실시예들을 상세히 설명한다.

도 1은 본 발명의 일 실시예에 따른 온라인 필기 데이터 라인 분할 장치의 블록도이다. 온라인 필기 데이터 라인 분할 장치(100)는 입력 감지부(110), 표시부(120), 저장부(130), 및 프로세서(140)를 포함한다.

온라인 필기 데이터 라인 분할 장치(100)는 입력 감지부(110)를 통해 입력된 복수의 획에 대한 데이터를 처리하여, 입력된 온라인 필기 데이터 라인을 분할시키도록 구성된다. 온라인 필기 데이터 라인 분할 장치(100)는 다양한 디바이스로 구현될 수 있다. 예를 들어 온라인 필기 데이터 라인 분할 장치(100)는 휴대폰, 스마트폰, 노트북 컴퓨터, 태블릿(tablet) 컴퓨터, 패블릿(phablet), 디지털 방송용 단말기, PDA (Personal Digital Assistants), PMP (Portable Multimedia Player), 네비게이션 등이거나 이들과 결합하여 사용하는 디바이스일 수 있다.

입력 감지부(110)는 사용자로부터의 온라인 필기 데이터 입력을 감지한다. 입력 감지부(110)는 예를 들어 터치 패널일 수 있으며, 또는 스타일러스(stylus) 팬과 같은 별도의 입력 장치가 요구되는 입력 감지부(110)일 수도 있다. 온라인 필기 데이터 입력은 문자를 구성하는 복수의 획(stroke)로 이루어질 수 있다. 복수의 획은 입력 감지부(110)에 의해 감지되는 온라인 필기 데이터 입력에 의한 획뿐만 아니라, 미리 입력되어 저장된 전자문서에 포함된 획을 포함한다. 즉, 복수의 획은 전자 디바이스에 실시간 입력되는 온라인 필기 데이터 입력에 의한 것일 수 있으나, 기 저장된 획일 수도 있다. 획 데이터란 순서를 가진 좌표들의 정보를 의미하며, 획의 시작 좌표, 끝 좌표, 시작 좌표와 끝 좌표 사이의 일련의 좌표들, 좌표 간 타이밍 등을 포함할 수 있다.

표시부(120)는 감지된 온라인 필기 데이터 입력에 의한 복수의 획을 시각적으로 출력한다. 표시부(120)는 디스플레이 장치를 포함할 수 있다. 또한, 표시부(120)는 온라인 필기 데이터 라인 분할 장치(100)와 관련한 각종 정보를 표시할 수 있다. 예컨대, 표시부(120)는 획과 함께, 온라인 필기 데이터 인식을 하기 위한 선택창을 표시할 수 있다. 사용자는 표시부(120)를 통해 온라인 필기 데이터를 시인할 수 있으며, 온라인 필기 데이터 인식과 연관된 정보를 시인할 수 있다. 입력 감지부(110)와 표시부(120)는 별도로 구성될 수 있으나, 이에 제한되지 않고, 입력 감지부(110)와 표시부(120)가 하나의 패널로 제작될 수도 있다.

저장부(130)는 획 및 라인 등에 대한 데이터를 저장한다. 획에 대한 데이터는 전자문서의 일부분으로 포함될 수 있다. 저장부(130)는 후술될 획의 그룹들, 그룹의 세트들, 그룹 세트의 클래스, 라인 정보 등을 저장할 수 있다. 또한, 저장부(130)는 본 발명의 일 실시예에 따른 온라인 필기 데이터 라인 분할 방법에서 사용되는 분류기 및 분류기에 이용되는 데이터베이스를 저장할 수 있다.

프로세서(140)는 입력 감지부(110), 표시부(120) 및 저장부(130)와 연결되고, 온라인 필기 데이터 라인 분할 장치(100)에서 다양한 연산을 수행한다. 프로세서(140)는 획 데이터 정보를 처리하도록 구성된다. 예컨대, 프로세서(140)는 획의 좌표 (x, y) 중 y가 가장 낮은 좌표를 획의 최저점으로 지정할 수 있고, 유사한 방법으로 y 좌표들을 이용하여 최고점과 x 좌표들을 이용하여 가장 왼쪽 점과 가장 오른쪽 점을 지정할 수 있다. 또한, 프로세서(140)는 이렇게 정의된 4개의 점을 이용하여 획들의 모든 점들을 포함하는 직사각형 영역을 정의할 수 있으며, 이러한 영역들이 y축 및 x축으로 중첩하는지를 결정할 수 있다. 또한, 프로세서(140)는 획 각각의 최저점의 기울기를 구함으로써, 필기 방향을 결정할 수도 있다.

프로세서(140)는 획과 연관된 다양한 연산을 수행함으로써, 온라인 필기 데이터 라인 분할 장치(100)의 기능들을 구현할 수 있다. 본 발명의 일 실시예에 따른 온라인 필기 데이터 라인 분할 장치(100)에서, 프로세서(140)는 복수의 획을 복수의 그룹으로 그룹화하고, 복수의 그룹 중 연속하는 그룹으로 이루어진 그룹 세트의 클래스를 추정하고, 추정된 그룹 세트의 클래스를 비교하여, 그룹 세트의 그룹 각각이 동일 라인에 있는지 여부를 결정하도록 구성된다. 프로세서(140)가 온라인 필기 데이터 라인 분할을 하기 위한 구체적인 동작들에 대해서는 도 2를 참조하여 후술한다.

도 1에는 설명의 편의를 위해, 입력 감지부(110), 표시부(120), 저장부(130), 및 프로세서(140)가 별도의 구성으로 도시되었으나, 발명의 구현에 있어 해당 구성들은 상호 결합 또는 분리되어 구현될 수 있다.

도 2는 본 발명의 일 실시예에 따른 온라인 필기 데이터 라인 분할 방법을 설명하기 위한 개략적인 흐름도이다. 온라인 필기 데이터 라인 분할 방법은 도 1에 도시된 프로세서를 포함하는 온라인 필기 데이터 라인 분할 장치에 의해 수행된다.

먼저, 입력된 복수의 획은 복수의 그룹으로 그룹화된다(S10). 복수의 획 중 y축 또는 x축에 대하여 적어도 일부 중첩하는지 여부가 먼저 결정된다. x축 또는 y축에 대하여, 겹치는 부분이 상당하여, 동일 라인에 있다고 추정되는 획들이 하나의 그룹으로 그룹화된다. 즉, 하나의 그룹은 동일한 라인에 있다고 결정된 복수의 획의 집합이다. 또한, 그룹들은 간격에 의해 서로 구분될 수 있다. 예를 들어, 복수의 그룹들은 띄어쓰기 또는 라인 바꿈에 의해 구분될 수 있다.

나아가, 복수의 획을 하나의 그룹으로 그룹화하는 것은 복수의 획 각각의 시간 특성에 또한 기초하여, 동일 라인에 있다고 결정될 수 있다. 즉, 시간 특성이 그룹화를 위한 인자로 사용될 수도 있다.

또한, 복수의 획들이 그룹들로 그룹화되기 전에 복수의 획의 기울어짐(skew)이 먼저 정규화될 수 있다. 정규화를 통해 온라인 필기 데이터 라인 분할의 정확성이 보다 향상될 수 있다.

이어서, 복수의 그룹 중 연속하는 그룹으로 이루어진 그룹 세트의 클래스가 추정된다(S20). 여기서 연속하는 그룹이란 필기 순서에 따른 그룹일 수 있으며, x축을 따라 연속하여 배치된 그룹들일 수도 있다. 소정의 수의 연속하는 그룹은 하나의 세트로 결정될 수 있다. 연속하는 그룹으로 이루어진 하나의 그룹 세트는 예를 들어, 3개의 연속하는 그룹으로 이루어질 수 있다. 또한, 연속된 앞과 뒤의 그룹 세트는 중복된 서브 그룹 세트를 갖도록 구성될 수 있다.

그룹 세트들에 대해서 클래스가 추정된다. 그룹 세트의 클래스는 연속하는 그룹이 동일한 라인에 있는지 동일한 라인에 없는지를 판단하기 위한 식별자로서, 클래스에 대한 구체적인 설명 및 추정 방법은 도 3 및 도 5를 참조하여 후술한다.

다음으로, 추정된 그룹 세트의 클래스를 비교하여, 그룹 세트의 그룹 각각이 동일 라인에 있는지 여부가 결정된다(S30). 그룹 세트들의 클래스가 비교되는 경우, 클래스 간 모순이 발생할 수 있다. 본 발명의 일 실시예에 따른 온라인 필기 데이터 라인 분할 방법에서는 클래스 간 모순이 발생한 경우, 재차 그룹들이 동일한 라인에 있는지를 판단할 수 있어, 라인 분할의 정확도가 향상될 수 있다.

도 3은 본 발명의 일 실시예에 따른 온라인 필기 데이터 라인 분할 방법의 구체적인 동작을 설명하기 위한 흐름도이다. 도 4 내지 도 7은 본 발명의 일 실시예에 따른 온라인 필기 데이터 라인 분할 방법을 설명하기 위한 개략도들이다.

먼저, 복수의 획이 복수의 그룹으로 그룹화된다(S110). 단계 S110은 도 2에서의 단계 S10과 실질적으로 동일한 단계이다. 이에 대해 도 4를 참조하여, 보다 구체적으로 살펴본다. 도 4의 (a)를 참조하면, “My email address is abc123@ (라인 변동) infraware. com”를 나타내는 복수의 획들이 도시된다. 복수의 획들 각각에는 획 번호가 부여된다. 예를 들어, 도 4의 (a)에서 M은 2개의 획으로 이루어져 있으며 각각 획 번호 1, 2가 부여된다. 이러한 획 번호 1 내지 10이 도 4의 (b)에 나타내어진다. 각각의 획에 대한 데이터는, 획 번호에 대응하며, 전술한 바와 같이 좌표 정보 및 필기 속도 등의 데이터를 포함할 수 있다.

도 4의 (c)에서는 획 쌍이 도시된다. 하나의 획 쌍은 동일한 라인에 있다고 결정된 두 개의 획의 집합이다. 또한, 획 쌍들은 간격에 의해 구분될 수 있다. 도 4의 (c)에서는 복수의 획 중 시간적 특징인 획 순서가 인접한 두 획이, y축에 대하여 겹치는 부분이 상당하고 x축에 대하여 일부 겹치거나 인접하여 하나의 획 쌍으로 결정되는 경우가 도시된다. 예를 들어, 획 1, 2는 서로 중첩되어 형성되므로, 획 번호 1, 2는 하나의 획 쌍을 이룰 수 있다. 또한 획 번호 7과 같이 최 좌측 x좌표와 획 번호 6의 최 우측 x좌표 사이의 간격은 미리 결정된 간격 이상일 수 있고, 최 우측 x좌표와 획 번호 8의 최 좌측 x좌표 사이의 간격은 미리 결정된 간격 이상일 수 있다. 이에 따라 하나의 획 번호가 하나의 획 쌍을 이룰 수도 있다.

또한, 획 쌍들은 하나의 그룹을 구성한다. 하나의 그룹은 동일한 라인에 있다고 결정된 복수의 획의 집합이다. 획 쌍들 중 (1,2) (2,3)과 같이 앞과 뒤의 쌍이 서로 중복한 획을 포함하고 있을 때, 하나의 그룹으로 구성될 수 있다. 이에 따라 획 번호 1 내지 4의 획들이 하나의 그룹으로 결정되고 유사한 방법으로 도4의 (d)와 같이 획 쌍들이 그룹으로 결정된다. 도 4의 (e)를 참조하면, 복수의 획들이 복수의 그룹으로 그룹화된 개략도가 도시된다. 각각의 그룹은 G1 내지 G7으로 도시된다.

본 발명의 일 실시예에 따른 온라인 필기 데이터 라인 분할 방법에서는 연속하는 2개의 그룹이 동일한 라인에 있는지를 랜덤 포레스트 분류기를 이용하여 추정함으로써, 복수의 그룹 중 연속하는 그룹으로 이루어진 그룹 세트의 클래스를 추정한다(S120).

먼저, 그룹 세트란 연속하는 그룹으로 이루어진다. 도 5를 참조하면, 하나의 그룹 세트가 도시된다. 예를 들어, 그룹 세트는 3개의 연속하는 그룹으로 이루어진다. 예를 들어, G1, G2 및 G3이 하나의 그룹을 이룰 수 있다. 또한, 그룹 세트는 도 6의 (a)와 같이 연속된 앞과 뒤의 그룹 세트가 중복된 서브 그룹 세트를 갖도록 이루어진다. 그룹 세트는, 그룹들이 동일한 라인에 있는지를 판단하기 위한 최소단위일 수 있다. 이하에서는 설명의 편의를 위해 그룹 세트가 3개의 연속하는 그룹인 것으로 상정하여 설명하나, 그룹 세트는 3개의 그룹에 제한되지 않고, 3개 이상의 연속하는 그룹을 포함할 수 있다. 이와 같이 3개 이상의 연속하는 그룹을 앞과 뒤의 그룹세트가 중복된 서브 그룹 세트를 갖도록 그룹세트를 구성하는 이유는 분류 과정 후의 검증 과정을 진행하기 위함이다.

그룹 세트 각각은 클래스를 가진다. 클래스란 3개의 연속하는 그룹이 동일한 라인에 있는지를 판단하기 위한 식별자이다. 도 5를 참조하면, G1과 G2가 상이한 라인에 있으며, G2와 G3이 상이한 라인에 있는 경우가 클래스 C0으로 도시된다. G1과 G2가 동일한 라인, G3은 G1 및 G2와 상이한 라인에 있는 경우는 클래스 C1으로 도시되며, G2와 G3이 동일한 라인, G1이 G2 및 G3이 상이한 라인에 있는 경우는 클래스 C2로 도시된다. 3개의 그룹이 동일한 라인에 있는 경우는 클래스 C3이다. 각각의 그룹 세트의 클래스의 정의는 예시적이며, 본 발명을 제한하도록 의도되지 않는다. 클래스의 정의는 다양한 방식으로 결정될 수 있다.

그룹 세트 각각의 클래스는, 즉 그룹들이 하나의 그룹 세트 내에서 동일한 라인에 있는지는 다양한 방식에 의해 추정될 수 있다. 예를 들어, 그룹 세트의 클래스는 분류기에 의해 추정될 수 있다. 본 발명의 일 실시예에 따른 온라인 필기 데이터 라인 분할 방법에서는 기계학습을 기반으로 하는 랜덤 포레스트 분류기를 이용하여 그룹 세트의 클래스가 추정될 수 있다.

랜덤 포레스트 분류기는 다수의 랜덤 결정 트리(Random Decision Tree)를 앙상블 형태로 결합한 것으로, 각 결정 트리에서는 랜덤한 방법으로 트리들을 성장시킬 수 있다. 생성된 N개의 결정 트리들은 앙상블로 결합되어 패턴 분류의 일반화(generalization)율을 높이는 역할을 한다. 분류시, 입력 벡터가 각 트리에 적용이 되고 각 트리에서 생성된 클래스별 확률값은 분류 클래스의 수만큼의 빈(bin)을 갖는 히스토그램에 누적되어 누적 확률 히스토그램을 생성한다. 최종적으로 각 빈의 최대 확률값이 추정되고 가장 높은 빈에 해당하는 클래스로 입력벡터가 분류된다.

여기서, 입력 벡터는 그룹 세트이다. 트리는 다양할 특징들로 구성될 수 있으며, 특징들은 예를 들어, 그룹 세트 내 그룹들 사이의 거리, 그룹들의 y축의 히스토그램의 중심 높이 차, 그룹들의 y축 중심 높이 차, 그룹들이 한 라인이라고 가정했을 때의 그 라인의 너비와 높이 및 그룹들의 y축이 중첩하는 길이 등을 포함할 수 있다.

이러한 트리에서 그룹 세트가 클래스 C0 내지 C3 중 어느 클래스에 속하는지에 대한 확률 값이 존재할 수 있으며, 누적된 확률 히스토그램에 따라 클래스가 추정될 수 있다. 도 6의 (a)를 참조하면, 도 4의 (e)에서의 그룹들을 포함하는 그룹 세트들 및 그룹 세트들에 대한 클래스가 도시된다. 도 6에서 G1, G2, G3의 그룹 세트 S1 내지 S3은 클래스 C3을 갖는 것으로 추정되고 결정되며, G4, G5, G6의 그룹 세트 S4는 클래스 C1을 갖는 것으로, G5, G6, G7의 그룹 세트 S5는 클래스 C2를 갖는 것으로 추정된다.

다음으로, 추정된 그룹 세트의 클래스가 비교되며(S130), 추정된 그룹 세트의 클래스가 서로 모순되는지가 결정된다(S140). 추정된 그룹 세트의 클래스가 모순되지 않는다고 결정되는 경우, 그룹 세트의 그룹 각각이 동일 라인에 있는지 여부가 결정되고(S160), 추정된 그룹 세트의 클래스가 서로 모순된다고 결정되는 경우, 모순되는 그룹 세트의 그룹이 동일 라인에 있는지 여부가 다시 결정된다(S150).

도 6을 참조하면, 예를 들어, 클래스 C3을 갖는 그룹 세트 S1와 클래스 C3을 갖는 그룹 세트 S2의 클래스가 비교된다. 클래스 C3은 3개의 연속하는 그룹이 동일한 라인에 있는 경우의 클래스이므로, 그룹 세트의 클래스들 C3과 C3은 서로 모순되지 않는다. 또한, 그룹 세트 S1 및 S2에 속하는 그룹 G1 내지 G4는 동일한 라인에 있는 것으로 결정된다. 마찬가지로 그룹 세트 S2와 S3가 비교되어, 그룹 G1 내지 G5가 동일한 라인에 있는 것으로 결정된다.

또한, 그룹 세트 S3과 S4의 클래스가 비교된다. 그룹 세트 S3의 클래스는 C3이며, 그룹 세트 S4의 클래스는 C1이다. 클래스 C3인 경우 3개의 그룹이 동일한 라인에 있으며, 클래스 C1인 경우 앞의 2개의 그룹이 동일한 라인, 나머지 한 개의 그룹이 앞의 2개의 그룹과 상이한 라인에 있으므로, 클래스 C1 및 G3은 서로 모순되지 않으며, G4 및 G5가 동일한 라인에 있다는 것이 결정된다.

다음으로, 그룹 세트 S4와 그룹 세트 S5의 클래스가 비교된다. 그룹 세트 S4는 클래스 C1을 가지며, 그룹 세트 S5는 클래스 C2를 가진다. 클래스 C1인 경우, 앞의 2개의 그룹이 동일한 라인, 나머지 한 개의 그룹이 앞의 2개의 그룹과 상이한 라인에 있다. 반면, 클래스 C2인 경우, 뒤의 2개의 그룹이 동일한 라인, 앞의 한 개의 그룹이 뒤의 2개의 그룹과 상이한 라인에 있다. 따라서, 그룹 G5 및 G6은 서로 상이한 라인에 있다는 것이 라인 세트들의 클래스 비교로 결정될 수 있다.

다음으로, 그룹 세트의 그룹 각각이 동일 라인에 있는지 여부를 기초로 라인 세트가 생성된다(S170). 도 6의 (b)를 참조하면, 그룹 G1 내지 G5이 라인 L1로 결정되고, 그룹 G6 및 G7이 라인 L2로 결정된다. 라인 L1 및 라인 L2가 라인 세트를 구성할 수 있다.

한편, 추정된 그룹 세트의 클래스가 서로 모순되는 경우, 모순되는 그룹 세트의 그룹들이 동일 라인에 있는지 여부가 다시 결정된다. 도 7을 참조하면, 그룹 세트의 클래스가 서로 모순되는 경우가 도시된다. 예를 들어, 도 7의 (a)에서 클래스 C1의 그룹 세트에서는 그룹 G3이 그룹 G1 및 그룹 G2와 상이한 라인에 있으며, 클래스 C3의 그룹 세트에서는 그룹 G2 내지 G4가 동일한 라인에 있다. 클래스 C1에서는 그룹 G2와 그룹 G3이 서로 상이한 라인이나, 클래스 C2에서는 그룹 G2와 그룹 G3이 동일한 라인에 있으므로, 비교되는 클래스가 서로 모순된다. 마찬가지로, 도 7의 (b)를 참조하면, 클래스 C1과 클래스 C2는 서로 모순된다.

추정된 그룹 세트의 클래스가 서로 모순된 경우, 모순되는 그룹 세트의 그룹이 동일 라인에 있는지 여부가 다시 결정된다. 또는, 모순되는 그룹 세트의 클래스가 재추정되고, 재추정된 그룹 세트의 클래스가 다시 비교될 수 있다. 그룹 세트의 클래스가 재추정되는 경우, 그룹 세트의 클래스를 추정하는 단계에서 사용된 방식과는 상이한 분류기를 이용하여 수행될 수 있다. 예를 들어, SVM 분류기 등이 이용될 수도 있다.

본 발명의 일 실시예에 따른 온라인 필기 데이터 라인 분할 방법에서는 모순되는 그룹 세트가 발견되는 경우, 다시 그룹 세트 내의 그룹들이 동일한 라인에 있는지를 판별하므로, 라인 분할의 정확성이 향상될 수 있다.

도 8은 본 발명의 다양한 실시예에 따른 온라인 필기 데이터 라인 분할 방법을 설명하기 위한 개략도이다.

도 3의 복수의 획을 복수의 그룹으로 그룹화한 후, 복수의 그룹 앞 또는 뒤에 위치하는 더미 그룹이 생성될 수 있다. 따라서, 연속하는 그룹은 복수의 그룹 앞 또는 뒤에 위치하는 더미 그룹을 포함한다. 도 8을 참조하면, 그룹 G1 앞에 더미 그룹 GD1 그리고 그룹 G7 뒤에 더미 그룹 GD2가 배치된다. 더미 그룹은 랜덤 포레스트 분류기를 이용하는 경우, 특징들에 대해 이상적인 값들을 갖도록 구성된다. 더미 그룹이 그룹들의 맨 앞과 맨 뒤에 배치됨으로써, 맨 앞의 그룹 G1 과 맨 뒤의 그룹 G7이 한번 더 검증될 수 있으며, 이에 따라, 온라인 필기 데이터 라인 분할 분할의 정확도가 더욱 향상될 수 있다.

첨부된 블록도의 각 블록과 흐름도의 각 단계의 조합들은 펌웨어 (firmware), 소프트웨어 (software) 또는 하드웨어 (hardware) 로 구성된, 알고리즘 또는 컴퓨터 프로그램 인스트럭션들에 의해 수행될 수도 있다. 이들 알고리즘 또는 컴퓨터 프로그램 인스트럭션들은 범용 컴퓨터, 특수용 컴퓨터 또는 기타 프로그램 가능한 디지털 신호 처리 디바이스 (Digital Signal Processing Device) 의 프로세서에 탑재될 수 있으므로, 컴퓨터 또는 기타 프로그램 가능한 데이터 프로세싱 장비의 프로세서를 통해 수행되는 그 인스트럭션들이 블록도의 각 블록 또는 흐름도의 각 단계에서 설명된 기능들을 수행하는 수단을 생성하게 된다.

또한, 각 블록 또는 각 단계는 특정된 논리적 기능 (들) 을 실행하기 위한 하나 이상의 실행 가능한 인스트럭션들을 포함하는 모듈, 세그먼트 또는 코드의 일부를 나타낼 수 있다. 이러한 블록들 또는 단계들은 그 기능의 목적과 효과로써 이해되어야 할 것이고 이들 구성요소들은 하나의 블록 또는 모듈 내에 하드웨어 또는 소프트웨어 또는 펌웨어 (firmware) 의 형태로 분할 또는 통합되어 구성 될 수 있음은 물론이다.

본 명세서에 개시된 실시예들과 관련하여 설명된 방법 또는 알고리즘의 단계는 프로세서에 의해 실행되는 하드웨어, 소프트웨어 모듈 또는 그 2 개의 결합으로 직접 구현될 수도 있다. 소프트웨어 모듈은 RAM 메모리, 플래시 메모리, ROM 메모리, EPROM 메모리, EEPROM 메모리, 레지스터, 하드 디스크, 착탈형 디스크, CD-ROM 또는 당업계에 알려진 임의의 다른 형태의 저장 매체에 상주할 수도 있다. 예시적인 저장 매체는 프로세서에 커플링되며, 그 프로세서는 저장 매체로부터 정보를 판독할 수 있고 저장 매체에 정보를 기입할 수 있다. 다른 방법으로, 저장 매체는 프로세서와 일체형일 수도 있다. 프로세서 및 저장 매체는 주문형 집적회로 (ASIC) 내에 상주할 수도 있다. ASIC는 사용자 단말기 내에 상주할 수도 있다. 다른 방법으로, 프로세서 및 저장 매체는 사용자 단말기 내에 개별 컴포넌트로서 상주할 수도 있다.

100 : 온라인 필기 데이터 라인 분할 장치
110 : 입력 감지부
120 : 표시부
130 : 저장부
140 : 프로세서

Claims (17)

1. 복수의 획을 복수의 그룹으로 그룹화하는 단계;
   상기 복수의 그룹 중 연속하는 그룹으로 이루어진 그룹 세트의 클래스를 추정하는 단계로서, 상기 그룹 세트의 클래스는 상기 그룹 세트 내의 상기 그룹 각각이 동일 라인에 있는지 없는지를 판단하기 위한 식별자이며, 상기 그룹 세트의 클래스는 다수의 랜덤 결정 트리(Random Decision Tree)가 앙상블 형태로 결합된 랜덤 포레스트 분류기를 통해 추정되는, 상기 그룹 세트의 클래스를 추정하는 단계;
   추정된 상기 그룹 세트의 클래스를 비교하여, 상기 그룹 세트의 그룹 각각이 동일 라인에 있는지 여부를 결정하는 단계를 포함하는 것을 특징으로 하는, 온라인 필기 데이터 라인 분할 방법.
2. 제1항에 있어서,
   상기 복수의 획을 복수의 그룹으로 그룹화하는 단계는, 상기 복수의 획 중 y축 또는 x축에 대하여 적어도 일부 중첩하는지 여부에 기초하여, 동일 라인에 있다고 결정되는 복수의 획을 하나의 그룹으로 그룹화하는 단계를 포함하는 것을 특징으로 하는, 온라인 필기 데이터 라인 분할 방법.
3. 제2항에 있어서,
   상기 복수의 획을 하나의 그룹으로 그룹화하는 단계는 상기 복수의 획 각각의 시간 특성에 또한 기초하여, 동일 라인에 있다고 결정되는 복수의 획을 하나의 그룹으로 그룹화하는 단계를 포함하는 것을 특징으로 하는, 온라인 필기 데이터 라인 분할 방법.
4. 제1항에 있어서,
   상기 그룹 세트의 클래스를 추정하는 단계는 연속하는 2개의 그룹이 동일한 라인에 있는지를 추정하는 단계를 포함하는 것을 특징으로 하는, 온라인 필기 데이터 라인 분할 방법.
5. 제4항에 있어서,
   상기 연속하는 2개의 그룹이 동일한 라인에 있는지를 추정하는 단계는, 상기 2개의 그룹 사이의 x축 거리, y축 중심 높이 차, y축 중첩 거리, y축 히스토그램을 기초로 한 y축 중심 높이 차, y축 중첩 거리 또는 상기 2개의 그룹이 하나의 라인에 있다고 가정 시 상기 하나의 라인의 폭과 높이 중 적어도 하나에 기초하여 추정하는 단계인 것을 특징으로 하는, 온라인 필기 데이터 라인 분할 방법.
6. 삭제
7. 삭제
8. 제1항에 있어서,
   상기 그룹 세트의 그룹 각각이 동일 라인에 있는지 여부를 기초로 라인 세트를 생성하는 단계를 더 포함하는 것을 특징으로 하는, 온라인 필기 데이터 라인 분할 방법.
9. 제1항에 있어서,
   상기 그룹 세트의 그룹 각각이 동일 라인에 있는지 여부를 결정하는 단계는, 추정된 상기 그룹 세트의 클래스가 서로 모순된 경우, 모순되는 상기 그룹 세트의 그룹이 상기 동일 라인에 있는지 여부를 결정하는 단계를 포함하는 것을 특징으로 하는, 온라인 필기 데이터 라인 분할 방법.
10. 제1항에 있어서,
    상기 그룹 세트의 그룹 각각이 동일 라인에 있는지 여부를 결정하는 단계는, 추정된 상기 그룹 세트의 클래스가 서로 모순된 경우, 상기 그룹 세트의 클래스를 재추정하는 단계 및 재추정된 상기 그룹 세트의 클래스를 비교하는 단계를 포함하는 것을 특징으로 하는, 온라인 필기 데이터 라인 분할 방법.
11. 제10항에 있어서,
    상기 그룹 세트의 클래스를 재추정하는 단계는 상기 그룹 세트의 클래스를 추정하는 단계에서 사용된 방식과는 상이한 분류기를 이용하여 수행되는 것을 특징으로 하는, 온라인 필기 데이터 라인 분할 방법.
12. 제1항에 있어서,
    상기 복수의 그룹 앞 또는 뒤에 위치하는 더미 그룹을 생성하는 단계를 더 포함하고,
    상기 연속하는 그룹은 상기 복수의 그룹 앞 또는 뒤에 위치하는 더미 그룹을 포함하는 것을 특징으로 하는, 온라인 필기 데이터 라인 분할 방법.
13. 제1항에 있어서,
    상기 그룹화하는 단계 이전에 상기 복수의 획의 기울어짐(skew)을 정규화하는 단계를 더 포함하는 것을 특징으로 하는, 온라인 필기 데이터 라인 분할 방법.
14. 프로세서; 및
    상기 프로세서와 연결되고, 복수의 획에 대한 입력을 감지하도록 구성된 입력 감지부를 포함하고,
    상기 프로세서는,
    상기 입력 감지부로부터의 상기 복수의 획을 복수의 그룹으로 그룹화하고,
    상기 복수의 그룹 중 연속하는 그룹으로 이루어진 그룹 세트의 클래스를 추정하되, 상기 그룹 세트의 클래스는 상기 그룹 세트 내의 상기 그룹 각각이 동일 라인에 있는지 없는지를 판단하기 위한 식별자이며, 상기 그룹 세트의 클래스는 다수의 랜덤 결정 트리(Random Decision Tree)가 앙상블 형태로 결합된 랜덤 포레스트 분류기를 통해 추정되고,
    추정된 상기 그룹 세트의 클래스를 비교하여, 상기 그룹 세트의 그룹 각각이 동일 라인에 있는지 여부를 결정하도록 구성된 것을 특징으로 하는, 온라인 필기 데이터 라인 분할 장치.
15. 삭제
16. 제14항에 있어서,
    상기 프로세서는, 추정된 상기 그룹 세트의 클래스가 서로 모순된 경우, 모순되는 상기 그룹 세트의 그룹이 상기 동일 라인에 있는지 여부를 추가로 수행하도록 구성된 것을 특징으로 하는, 온라인 필기 데이터 라인 분할 장치.
17. 제14항에 있어서,
    상기 프로세서는, 상기 복수의 그룹 앞 또는 뒤에 위치하는 더미 그룹을 생성하도록 더 구성되고,
    상기 연속하는 그룹은 상기 복수의 그룹 앞 또는 뒤에 위치하는 더미 그룹을 포함하는 것을 특징으로 하는, 온라인 필기 데이터 라인 분할 장치.

Images