KR19990062829A - 문자열 추출 장치 및 패턴 추출 장치 - Google Patents

Abstract

복잡한 화상으로부터 문자열을 추출하는 것을 가능하게 하고, 문자색을 잘못 보는 일이 없이, 또한 선폭이 가는 선분을 빠뜨리지 않는 문자열 추출 장치를 제공한다.

입력 화상의 연결 성분을 구하고, 연결 성분의 상대적 위치 및 굵기의 유사성에 기초하여 그룹으로 나누고, 문자 인식 처리를 행하여 그룹의 문자 인식도를 구하고, 구형 영역의 면적에 의해 웨이트한 것의 총합을 그룹의 평가치로 하고, 모든 그룹의 조합에 대해 평가치를 구하고, 조합의 평가치가 가장 높은 그룹의 조합을 문자열로서 추출한다.

Description

문자열 추출 장치 및 패턴 추출 장치

본 발명은 문서나 도면 등을 판독하는 화상 인식 기술에 관한 것으로, 특히, 화상으로부터 헤드라인 등의 문자열을 추출하는 경우에 적용하기에 바람직한 것이다.

문서를 전자적으로 파일링하는 경우, 키워드를 문서에 부여해 놓는 것이 불가결하지만, 이 작업은 작업자에게 있어서 매우 번거로운 것으로, 이 작업을 자동화하는 것은 전자 파일링의 유용성을 높이는데에 있어서 매우 중요한 과제이다.

신문이나 잡지에 있어서는, 헤드라인 부분을 자동적으로 추출하고, 문자 인식하여 키워드로 하는 것이 가장 효율적이다. 왜냐하면, 헤드라인은 문서의 내용의 특징을 풍부하게 포함하며, 또한 문서 중에서 특정하기 쉽기 때문이다.

이 때문에, 키워드를 추출하는 시간을 단축하고, 키워드를 정확하게 추출하는 기술(예를 들면 특개평4-287168호 파일링의 자동 키워드 추출 방법)이 고안되어 있다.

이 방법은, 도면이나 사진이나 표의 설명문이, 도면이나 사진이나 표의 구형부분의 상부 혹은 하부에 있는 것에 주목하여, 거기에 있는 문자열 혹은 문자열 영역을 추출하여 문자 인식을 행하고, 키워드로서 등록한다고 하는 것이다.

또한, 화상으로부터 문자열을 추출하는 기술(예를 들면, 특개평8-293003호 문자열 추출 방법 및 그 방법을 이용한 문자열 추출 장치, 및 그 장치를 이용한 문자열 인식 처리 장치 및 문자열 인식 처리 시스템)이 고안되어 있다.

여기서는, 화상 내의 모든 문자를 추출하고, 연속성을 갖는 문자열마다 그룹으로 나누어, 각 그룹의 특징량과 등록된 문자열의 특징량의 모델과 비교·판별하고, 문자열로서 추출하는 것이다. 여기서, 연속성이란 문자열의 배열이고, 특징량이란 한자나 숫자 등의 문자의 종류와 크기이다.

이와 같이, 전자 파일링의 대상이 되는 문서나 도면이 여러가지이고, 화상 인식 기술도 다양하지만, 화상으로부터 추출하는 문자열의 예로서, 신문에서 잘 보여지는 배경 모양이 있는 헤드라인을 대상으로 하는 다음에 나타내는 방법이 일반적으로 잘 알려져 있다.

우선, 입력 화상을 세로 쓰기인지, 가로 쓰기인지를 판정하고, 입력 화상과 그 반전 화상에 라벨링 처리를 행하고, 동일한 색의 화소가 연속해 있는 연결 성분을 구한다.

다음에, 각 연결 성분의 크기, 굵기, 및 상대적 위치로부터 문자 후보를 찾아 내기 시작한다.

여기서, 입력 화상의 연결 성분으로부터 얻어지는 문자 후보를 흑문자 후보, 반전 화상의 연결 성분으로부터 얻어지는 문자 후보를 백문자 후보라고 부른다. 이 흑문자 후보와 백문자 후보의 갯수로부터 문자의 색을 결정하여, 문자색을 흑으로 한 경우에는 입력 화상의 연결 성분만을 그 이후의 처리 대상으로 하고, 문자색을 백으로 한 경우에는 반전 화상의 연결 성분만을 그 이후의 처리 대상으로 한다.

다음에, 처리 대상의 연결 성분을 머지(merge)하여 문자열 영역을 구하고, 이 문자열 영역에 포함되는 연결 성분으로, 임계치 이상의 굵기의 연결 성분을 문자 성분으로서 추출한다. 이 임계치는, 연결 성분의 굵기의 최대치에 대한 일정한 비율의 값이다. 마지막으로, 문자 성분으로서 추출한 연결 성분을 화상으로서 생성하고, 문자 인식 처리에 의해 문자열로 한다.

또한, 헤드라인 부분을 정확하게 추출하기 위해서, 동일 문자열에 속하는 흑화소 영역의 정확한 통합 기술이 필요하게 된다.

이 기술에 관한 종래 방법으로서는, 다음의 방법이 있다.

우선, 기울기 보정이나 테두리선 제거 등의 전 처리를 하고 나서, 화상 전체를 라벨링하고, 얻어진 흑화소 연결 영역의 중첩 네스트 통합을 행한다. 다음에, 얻어진 흑화소 연결 영역으로부터 문서 전체의 본문 문자 크기를 판단하고, 그 값을 기초로 각 연결 영역의 속성 판별을 행한다. 그리고, 속성이 문자라고 판단된 구형에 대해서는, 세로 또는 가로의 통합을 반복하여, 문자열을 확정한다.

그러나, 종래의 기술에서는, 문자 추출 처리의 도중의 단계에서 문자색을 결정하고, 일률적인 표준 문자선 폭을 이용하고 있고, 또한, 문자열 영역을 설정할 때는 1행(혹은 1열)을 전제로 하고 있었다. 그 때문에, 배경 모양의 흑백 혼재, 복수종류의 폰트 혼재, 컬러 문서, 복수행, 종횡 혼재, 및 이들의 복합체로 구성되는 복잡한 화상으로부터 문자열을 추출하는 것이 곤란하게 된다고 하는 문제가 있었다.

또한, 흑문자 후보와 백문자 후보의 갯수의 관계는, 문자색을 결정하기 위한 판단 기준으로서 신뢰성이 높다고는 말할 수 없고, 또한, 문자 추출 처리의 도중의 단계에서 문자색을 결정하고 있지만, 여기서 판단을 잘못하면, 그 이후에는 수복 불가능하며, 마지막으로 처리하는 문자 인식이 불가능하게 된다고 하는 문제가 있었다.

또한, 일률적인 표준 문자선 폭을 이용하는 것은 비교적 선폭이 가는 문자 성분이 소실하기 쉬운 경향에 있는 것을 의미하며, 마지막으로 처리하는 문자 인식에 영향을 미치게 된다고 하는 문제가 있었다.

또한, 종래 수법에서는, 흑화소 연결 영역의 중첩 네스트 통합을 행하기 위해서, 원래 통합되어서는 안 되는 부분이 차례차례로 통합되어, 결국 문서 전체가 통합된다고 하는 심각한 실패에 빠질 가능성이 있었다.

예를 들면, 문서 전체의 기울기가 보정되지 않은 경우, 또한 테두리선이 완전히 제거되지 않는 경우, 중첩 네스트 통합에 의해, 문서 전체가 통합되는 경우가 있다.

도 30은, 종래의 중첩 네스트 통합에 의해, 문서 전체가 통합되는 예를 나타낸 도면이다.

도 30의 (a)에 있어서, 연결 성분의 외접 구형 K61∼K65가 입력 화상으로부터 얻어진 것으로 한다. 이 연결 성분의 외접 구형 K61∼K65에 대해, 중첩 네스트 통합을 행하면, 외접 구형 K61과 외접 구형 K62가 중첩되어 있기 때문에, 외접 구형K61과 외접 구형 K62와는 통합되고, 도 30의 (b)에 도시한 바와 같이, 외접 구형 K61과 외접 구형 K62를 둘러싸는 외접 구형 K66이 생성된다. 외접 구형 K66이 생성되면, 이 외접 구형 K66과 외접 구형 K63이 중첩되기 때문에, 외접 구형 K66과 외접 구형 K63이 통합되고, 도 30의 (c)에 도시한 바와 같이, 외접 구형 K66과 외접 구형 K63을 둘러싸는 외접 구형 K67이 생성된다. 외접 구형 K67이 생성되면, 이 외접 구형 K67과 외접 구형 K64가 중첩되기 때문에, 외접 구형 K67과 외접 구형 K64가 통합된다. 마찬가지로 하여, 도 30의 (a)의 외접 구형 K61∼K65의 전부가 통합되어, 도 30의 (d)에 도시한 바와 같이, 외접 구형 K61∼K65를 둘러싸는 외접 구형 K68이 생성된다.

또한, 사진이나 도면, 무늬가 있는 헤드라인이 있는 경우에는, 중첩 네스트 통합 처리의 시간이 많이 걸린다고 하는 문제도 있다.

그래서, 본 발명의 제1의 목적은, 문서나 도면 등을 판독하는 화상 인식 기술에 관한 것으로, 특히, 복잡한 화상으로부터 문자열을 추출하는 것을 가능하게 하여, 문자색을 잘못 보는 일이 없고, 또한 선폭이 가는 선분을 빠뜨리는 일이 없는 문자열 추출 장치를 제공하는 것이다.

또한, 본 발명의 제2의 목적은, 부분적으로 중첩 네스트 통합을 행하는 것이 가능한 패턴 추출 장치를 제공하는 것이다.

본 발명의 문자열 추출 장치는, 화상으로부터 문자열을 추출하는 장치에 있어서, 입력한 화상으로부터 화소의 색에 기초하여, 화소의 색이 연속해 있는 연결 성분을 추출하는 연결 성분 추출 수단과, 연결 성분의 상대적 위치, 및 연결 성분의 전 화소수에 대한 경계 화소수의 비에 기초하여, 연결 성분을 공통의 문자열 또는 문자열군을 구성하는 가능성이 높은 그룹으로 나누는 그룹핑 수단과, 그룹마다 문자 인식 처리를 행하고, 그 결과의 각 문자의 제1위 인식 후보의 거리치의 역수의 합을 그룹의 문자 인식도로 하는 문자 인식 수단과, 그룹의 문자 인식도에 그룹이 차지하는 구형 영역의 면적에 의해 웨이트한 것을 그룹의 평가치로 하고, 모든 그룹의 조합에 대해 그룹의 평가치의 합을 조합의 평가치로 하는 조합 평가 수단과, 조합의 평가치가 가장 높은 그룹의 조합을 문자열로서 추출하는 문자열 추출 수단을 구비하는 것을 특징으로 한다.

또한, 본 발명의 문자열 추출 장치는, 입력한 화상이 흑백 2치 화상인 경우에는 입력 화상과, 흑백 2치를 반전시킨 반전 화상에 대해, 흑화소가 연속해 있는 연결 성분을 추출하는 것을 특징으로 한다.

또한, 본 발명의 문자열 추출 장치는, 그룹이 차지하는 구형 영역에 중첩이 없는 그룹만을 관련짓고, 그룹이 차지하는 구형 영역에 중첩이 없는 그룹의 조합을 전부 구하는 것을 특징으로 한다.

또한, 본 발명의 기록 매체는 프로그램을 기록한 컴퓨터 판독 가능한 기록 매체로서, 컴퓨터를, 입력한 화상으로부터 화소의 색에 기초하여 화소의 색이 연속해 있는 연결 성분을 추출하는 연결 성분 추출 수단과, 연결 성분의 상대적 위치, 및 연결 성분의 전 화소수에 대한 경계 화소수의 비에 기초하여, 연결 성분을 공통의 문자열 또는 문자열군을 구성하는 가능성이 높은 그룹으로 나누는 그룹핑 수단과, 그룹마다 문자 인식 처리를 행하고, 그 결과의 각 문자의 제1위 인식 후보의 거리치의 역수의 합을 그룹의 문자 인식도로 하는 문자 인식 수단과, 그룹의 문자 인식도에 그룹이 차지하는 구형 영역의 면적에 의해 웨이트한 것을 그룹의 평가치로 하고, 모든 그룹의 조합에 대해 그룹의 평가치의 합을 조합의 평가치로 하는 조합 평가 수단과, 조합의 평가치가 가장 높은 그룹의 조합을 문자열로서 추출하는 문자열 추출 수단을 구비하며, 화상으로부터 문자열을 추출하는 문자열 추출 장치로서 기능시키는 것을 특징으로 한다.

또한, 본 발명의 한 형태에 따르면, 입력 화상 및 상기 입력 화상의 흑백 반전 화상의 각각으로부터 얻어지는 패턴의 인식 결과 중, 상호 영역이 중첩하지 않은 부분을 조합시킨 것을, 상기 입력 화상으로부터의 패턴의 추출 결과로 하도록 하고 있다.

이에 따라, 신문 등의 헤드라인 문자 중에, 흑화소로 구성된 문자와 외곽선 문자가 혼재하고 있는 경우에 있어서도, 흑문자 후보와 백문자 후보의 갯수로부터 문자의 색이 결정되었기 때문에, 문자색이 흑으로 된 경우에는 입력 화상의 연결 성분만이 그 이후의 처리 대상으로 되어, 흑문자는 정확하게 인식할 수 있지만, 외곽선 문자는 인식 불능으로 되거나, 문자색이 백으로 된 경우에는 흑백 반전 화상의 연결 성분만이 문자 인식의 처리 대상으로 되어, 외곽선 문자는 정확하게 인식할 수 있지만, 흑문자는 인식 불능으로 되거나 하는 것을 방지하는 것이 가능해져서, 배경 모양의 흑백 혼재, 복수 종류의 폰트 혼재, 컬러 문서, 복수행, 종횡 혼재, 및 이들의 복합체로 구성되는 복잡한 화상으로부터 문자열을 정밀도 좋게 추출하는 것이 가능해진다.

또한, 본 발명의 한 형태에 따르면, 입력 화상의 연결 성분을 추출하는 연결 성분 추출 수단과, 상기 연결 성분의 외접 구형을 생성하는 외접 구형 생성 수단과, 상기 외접 구형이 상기 입력 화상에 존재하는 빈도를 상기 외접 구형의 면적으로 웨이트된 막대 그래프를 생성하는 막대 그래프 생성 수단과, 상기 막대 그래프의 최대치를 나타낸 외접 구형의 크기를 상기 입력 화상의 문자 크기로 추정하는 문자 크기 추정 수단을 구비하고 있다.

이에 따라, 1개의 문자가 상호 분리한 복수의 스트로크로 구성되고, 중첩 네스트 통합 처리를 행하지 않았기 때문에, 각 스트로크마다 생성되는 외접 구형이 그대로 남겨질 경우에 있어서도, 1개의 문자의 일부로 구성되는 외접 구형은, 1개의 문자 전체로부터의 구성되는 외접 구형보다도, 크기가 작아지기 때문에, 1개의 문자의 일부로 구성되는 외접 구형의 빈도의 평가를 낮게 하는 것이 가능해져서, 문자 크기를 추정할 때에, 문자가 부분적인 크기가 문자 크기의 추정에 영향받는 것을 작게 하는 것이 가능해지기 때문에, 중첩 네스트 통합 처리를 행하지 않는 경우에 있어서도, 문자 크기를 정밀도 좋게 추정하는 것이 가능해진다.

또한, 본 발명의 한 형태에 따르면, 상기 외접 구형 생성 수단으로 생성된 외접 구형의 그룹핑을 행하는 그룹핑 수단과, 상기 문자 크기 추정 수단으로 추정된 문자 크기를 갖는 제1 외접 구형을 소정의 갯수 이상 포함하는 제2 외접 구형을 추출하는 박스형 추출 수단과, 상기 제2 외접 구형을 상기 그룹핑의 대상으로부터 제외하는 박스형 제외 수단을 구비하고 있다.

이에 따라, 신문 등으로부터 헤드라인 문자를 추출하는 경우에 있어서, 헤드라인 문자의 근처에 본문 문자를 둘러싸는 박스형이 존재하는 경우에 있어서도, 이 박스형만을 추출하는 것이 가능해져서, 헤드라인 문자의 외접 구형과 구별하는 것이 가능해지기 때문에, 헤드라인 문자만을 정밀도 좋게 추출하는 것이 가능해진다.

또한, 본 발명의 한 형태에 따르면, 상기 외접 구형에 부여된 구형 번호를 상기 입력 화상에 설정된 각 좌표에 사영하는 사영 수단을 구비하고, 상기 박스형 추출 수단은 상기 각 좌표에 포함되는 구형 번호를 상기 제2 외접 구형의 좌표의 범위 내에서 탐색함으로써, 제1 외접 구형을 추출하도록 하고 있다.

이에 따라, 외접 구형 내에 존재하는 다른 외접 구형을 용이하게 추출하는 것이 가능해져서, 본문 문자를 둘러싸는 박스형과 헤드라인 문자가 혼재하고 있는 경우에 있어서도, 박스형만을 고속으로 추출하는 것이 가능해진다.

또한, 본 발명의 한 형태에 따르면, 입력 화상의 연결 성분을 추출하는 연결 성분 추출 수단과, 상기 연결 성분의 외접 구형을 생성하는 외접 구형 생성 수단과, 상기 외접 구형이 상호 중첩되어 있는 다른 외접 구형의 갯수를 산출하는 중첩도 평가 수단과, 상기 중첩도 평가 수단의 산출 결과에 기초하여, 중첩 네스트 통합 처리를 행하는 중첩 네스트 통합 처리 수단을 구비하고 있다.

이에 따라, 중첩도가 큰 외접 구형만을 대상으로 중첩 네스트 통합 처리를 행하고, 중첩도가 작은 외접 구형의 중첩 네스트 통합 처리를 행하지 않도록 하는 것이 가능해지기 때문에, 외접 구형이 화면 전체에서 통합되어, 헤드라인 문자의 외접 구형이 소실되는 것을 방지하는 것이 가능해짐과 동시에, 중첩도가 큰 도면이나 사진의 일부를 보다 큰 구형에 흡수 통합해 놓는 것이 가능해져서, 도면이나 사진의 일부의 외접 구형이 그대로 남고, 헤드라인 문자로서 잘못 추출되거나, 헤드라인 문자를 구성하는 것으로서 잘못하여 구형 통합되거나 하는 것을 방지하는 것이 가능해져서, 헤드라인 문자와 도면이나 사진 등이 혼재하고 있는 경우에 있어서도, 헤드라인 문자의 추출을 정밀도 좋게 행하는 것이 가능해진다.

또한, 본 발명의 한 형태에 따르면, 상기 외접 구형에 부여된 구형 번호를 상기 입력 화상에 설정된 각 좌표에 사영하는 사영 수단과, 상기 각 좌표에 포함되는 구형 번호를 소정의 외접 구형의 좌표의 범위 내에서 탐색함으로써, 상기 소정의 외접 구형에 중첩되어 있는 다른 외접 구형을 추출하는 중첩 구형 추출 수단을 구비하고 있다.

이에 따라, 상호 중첩되어 있는 외접 구형을 용이하게 추출하는 것이 가능 해지고, 외접 구형의 중첩도를 고속으로 산출하는 것이 가능해진다.

도 1은 본 발명의 제1 실시예에 따른 패턴 추출 장치의 구성을 나타내는 블럭도.

도 2는 본 발명의 제2 실시예에 따른 패턴 추출 장치의 구성을 나타내는 블럭도.

도 3은 본 발명의 일 실시예에 따른 패턴 추출 장치의 시스템 구성을 나타내는 블럭도.

도 4a 내지 도 4c는 본 발명의 제3 실시예에 따른 문자열 추출 장치의 동작을 설명하는 도면.

도 5는 본 발명의 제3 실시예에 따른 문자열 추출 장치의 구성을 나타내는 블럭도.

도 6은 본 발명의 제3 실시예에 따른 문자열 추출 장치의 동작을 나타내는 플로우차트.

도 7은 본 발명의 일 실시예에 따른 라벨링 처리를 설명하는 도면.

도 8은 본 발명의 일 실시예에 따른 그룹핑 처리를 나타내는 플로우차트.

도 9는 본 발명의 일 실시예에 따른 연결 성분과 외접 구형의 예를 나타내는 도면.

도 10은 본 발명의 일 실시예에 따른 대상 연결 성분의 제한 방법을 나타내는 플로우차트.

도 11은 본 발명의 일 실시예에 따른 연결 성분 근방을 설명하는 도면.

도 12는 본 발명의 일 실시예에 따른 연결 성분의 가족적 유사성을 설명하는 도면.

도 13은 본 발명의 일 실시예에 따른 그룹의 문자 인식도의 산출 방법을 설명하는 도면.

도 14는 본 발명의 일 실시예에 따른 연합 그래프와 클리크를 나타내는 도면.

도 15는 본 발명의 일 실시예에 따른 연결 성분의 중첩이 없는 그룹의 추출 방법을 나타내는 플로우차트.

도 16a 내지 도 16d는 본 발명의 일 실시예에 따른 연결 성분끼리의 링크 부착 방법을 설명하는 도면.

도 17a 내지 도 17d는 본 발명의 일 실시예에 따른 클리크가 되는 그룹과 클리크가 되지 않는 그룹의 예를 나타내는 도면.

도 18은 본 발명의 일 실시예에 따른 조합의 평가치 산출 방법을 나타내는 도면.

도 19는 본 발명의 제4 실시예에 따른 패턴 추출 장치의 동작을 나타내는 플로우차트.

도 20a 내지 도 20b는 본 발명의 일 실시예에 따른 외접 구형의 크기를 구하기 위한 막대 그래프의 일례를 나타내는 도면.

도 21은 본 발명의 일 실시예에 따른 구형 번호의 사영 테이블의 일례를 나타내는 도면.

도 22는 본 발명의 일 실시예에 따른 헤드라인 구형 후보의 선택 방법을 나타내는 플로우차트.

도 23은 본 발명의 일 실시예에 따른 박스형의 체크 방법을 설명하는 도면.

도 24는 본 발명의 일 실시예에 따른 중첩 네스트 통합을 설명하는 도면.

도 25a 내지 도 25b는 본 발명의 일 실시예에 따른 부분적 중첩 네스트 통합을 설명하는 도면.

도 26은 본 발명의 일 실시예에 따른 근방 구형의 예를 나타내는 도면.

도 27은 본 발명의 일 실시예에 따른 근방 통합 처리를 나타내는 플로우차트.

도 28은 본 발명의 일 실시예에 따른 중첩 구형의 일례를 나타내는 도면.

도 29는 본 발명의 일 실시예에 따른 헤드라인 구형의 마킹 방법을 설명하는 도면.

도 30은 종래의 중첩 네스트 통합에 의해 문서 전체의 구형이 통합되는 예를 나타내는 도면.

도면의 주요 부분에 대한 부호의 설명

1 : 반전 화상 생성 수단

2 : 인식 수단

3 : 출력 수단

11 : 연결 성분 추출 수단

12 : 외접 구형 생성 수단

13 : 중첩도 평가 수단

14 : 중첩 네스트 처리 수단

21 : CPU

22 : ROM

23 : RAM

24 : 통신 인터페이스

25 : 통신 네트워크

26 : 버스

27 : 입출력 인터페이스

28 : 디스플레이

29 : 프린터

30 : 메모리

31 : 스캐너

32 : 키보드

33 : 드라이버

34 : 하드디스크

35 : IC 메모리 카드

36 : 자기 테이프

37 : 플로피 디스크

38 : 광 디스크

41 : 문자열 추출 장치

42 : 연결 성분 추출 수단

43 : 그룹핑 수단

44 : 문자 인식 수단

45 : 조합 평가 수단

46 : 문자열 추출 수단

이하, 본 발명의 한 실시예에 따른 패턴 추출 장치에 대해, 도면을 참조하면서 설명한다.

도 1은, 본 발명의 제1 실시예에 따른 패턴 추출 장치의 구성을 나타낸 블럭도이다.

도 1에 있어서, 반전 화상 생성 수단(1)은 입력 화상의 라벨을 반전한 반전 화상을 생성한다. 인식 수단(2)은 입력 화상으로부터 추출된 패턴 및 반전 화상 생성 수단(1)으로 생성된 반전 화상으로부터 추출된 패턴의 인식 처리를 행한다. 출력 수단(3)은, 인식 수단(2)으로 인식된 인식 결과 중, 입력 화상으로부터 추출된 패턴의 영역과 반전 화상 생성 수단(1)으로 생성된 반전 화상으로부터 추출된 패턴의 영역과의 중첩이 없는 조합을, 정합성이 있는 조합으로서 출력한다.

이에 따라, 신문 등의 헤드라인 문자 중에, 흑화소로 구성된 문자와 외곽선 문자가 혼재하고 있는 경우에 있어서도, 흑화소로 구성된 문자와 외곽선 문자와의 양쪽에 대해 인식 처리를 행하고, 흑화소로 구성된 문자의 인식 결과 및 외곽선 문자의 인식 결과를 조합시켜 출력하는 것이 가능해진다.

이 때문에, 흑문자 후보와 백문자 후보의 갯수로부터 문자의 색이 결정되어, 문자색이 흑으로 된 경우에는 입력 화상의 연결 성분만이 그 이후의 처리 대상으로 되고, 흑문자는 정확하게 인식할 수 있지만, 외곽선 문자는 인식 불능으로 되거나, 문자색이 백으로 된 경우에는 흑백 반전 화상의 연결 성분만이 문자 인식의 처리 대상으로 되어, 외곽선 문자는 정확하게 인식할 수 있지만, 흑문자는 인식 불능이 되거나 하는 것을 방지하는 것이 가능해지고, 배경 모양의 흑백 혼재, 복수 종류의 폰트 혼재, 컬러 문서, 복수행, 종횡 혼재, 및 이들의 복합체로 구성되는 복잡한 화상으로부터 문자열을 정밀도 좋게 추출하는 것이 가능해진다.

도 2는, 본 발명의 제2 실시예에 따른 패턴 추출 장치의 구성을 나타낸 블럭도이다.

도 2에 있어서, 연결 성분 추출 수단(11)은, 입력 화상의 라벨링을 행함으로써, 입력 화상의 연결 성분을 추출한다. 외접 구형 생성 수단(12)은 연결 성분 추출수단(11)으로 추출된 연결 성분의 외접 구형을 생성한다. 중첩도 평가 수단(13)은, 외접 구형 생성 수단(12)으로 생성된 외접 구형이 상호 중첩되어 있는 다른 외접 구형의 갯수를 산출한다. 중첩 네스트 통합 처리 수단(14)은, 중첩도 평가 수단(13)의 산출 결과에 기초하여, 중첩 네스트 통합 처리를 행한다.

이에 따라, 중첩 네스트 통합을 부분적으로 행하는 것이 가능해져서, 중첩도가 큰 외접 구형만을 대상으로 중첩 네스트 통합 처리를 행하고, 중첩도가 작은 외접 구형의 중첩 네스트 통합 처리를 행하지 않도록 하는 것이 가능해지기 때문에, 외접 구형이 화면 전체로 통합되어, 헤드라인 문자의 외접 구형이 소실하는 것을 방지하는 것이 가능해진다.

또한, 중첩도가 큰 도면이나 사진의 일부를 보다 큰 구형에 흡수 통합하여 놓는 것이 가능해져서, 도면이나 사진의 일부의 외접 구형이 그대로 남고, 헤드라인문자로서 잘못 추출되거나, 헤드라인 문자를 구성함으로써 잘못 구형 통합되거나 하는 것을 방지하는 것이 가능해져서, 헤드라인 문자와 도면이나 사진 등이 혼재하고있는 경우에 있어서도, 헤드라인 문자의 추출을 정밀도 좋게 행하는 것이 가능해진다.

도 3은 본 발명의 한 실시예에 따른 정보 검색 장치의 시스템 구성을 나타낸 블럭도이다.

도 3에 있어서, 참조 번호(21)는 전체적인 처리를 행하는 중앙 연산 처리 유닛(CPU), 참조 번호(22)는 판독 전용 메모리(ROM), 참조 번호(23)는 랜덤 억세스메모리(RAM), 참조 번호(24)는 통신 인터페이스, 참조 번호(25)는 통신 네트워크, 참조 번호(26)는 버스, 참조 번호(27)는 입출력 인터페이스, 참조 번호(28)는 헤드라인 문자 등의 인식 결과 등을 표시하는 디스플레이, 참조 번호(29)는 헤드라인 문자등의 인식 결과 등을 인쇄하는 프린터, 참조 번호(30)는 스캐너(31)에 의해 판독된 데이타를 일시적으로 저장하는 메모리, 참조 번호(31)는 입력 화상 등을 판독하는 스캐너, 참조 번호(32)는 키보드, 참조 번호(33)는 기억 매체를 구동하는 드라이버, 참조 번호(34)는 하드디스크, 참조 번호(35)는 IC 메모리 카드, 참조 번호(36)는 자기테이프, 참조 번호(37)는 플로피 디스크, 참조 번호(38)는 CD-ROM이나 DVD-ROM 등의 광 디스크이다.

패턴 추출 처리를 행하는 프로그램 등은, 하드디스크(34), IC 메모리 카드(35), 자기 테이프(36), 플로피 디스크(37), 광 디스크(38) 등의 기억 매체에 저장된다. 그리고, 패턴 추출 처리를 행하는 프로그램 등을, 이들 기억 매체로부터 RAM(23)에 판독함으로써, 신문이나 잡지 등의 문서 화상으로부터 헤드라인 문자 등의 추출을 행할 수 있다. 또한, 패턴 추출 처리를 행하는 프로그램 등을, ROM(22)에 저장해 놓는 것도 가능하다.

또한, 패턴 추출 처리를 행하는 프로그램 등을, 통신 인터페이스(24)를 통해 통신 네트워크(25)로부터 추출하는 것도 가능하다. 통신 인터페이스(24)에 접속되는 통신 네트워크(25)로서, 예를 들면, LAN(Local Area Network), WAN(Wide Area Network), 인터넷, 아날로그 전화망, 디지탈 전화망(ISDN: Integral Service Digital Network), PHS(Personal Handy System)나 위성 통신 등의 무선 통신망을 이용할 수 있다.

CPU(21)는 패턴 추출 처리를 행하는 프로그램이 기동되면, 스캐너(31)에 의해 판독된 입력 화상에 라벨링을 행하고, 동일 라벨이 부착된 연결 성분마다 외접 구형을 생성한다. 그리고, 각 외접 구형의 중첩도를 조사하고, 중첩도가 큰 외접 구형끼리에 대해, 중첩 호스트 통합을 행한다. 다음에, 중첩 네스트 통합이 행해진 외접 구형의 그룹핑을 행하고, 그 그룹핑 결과 중에서 헤드라인 문자를 추출하고, 그 추출 결과를 디스플레이(28)나 프린터(29)에 출력한다.

도 4a 내지 도 4c는 본 발명의 제3 실시예에 따른 문자열 추출 장치의 동작을 설명하는 도면이다. 도 4a에 있어서, 흑테두리 중에「」이라고 2행에 걸쳐 쓰여진 흑화소 문자와, 「調査グ」라고 세로 쓰기로 쓰여진 외곽선 문자가 입력 화상으로서 입력된 것으로 하고, 이 입력 화상으로부터, 「」이라는 문자열과 「調査グ」라는 문자열을 추출하도록 한다.

우선, 입력한 화상으로부터 화소의 색에 기초하여, 화소의 색이 연속해 있는 연결 성분을 추출한다.

입력 화상이 컬러 화상인 경우에는, 각 색에 대해 연결 성분을 추출한다. 도4a의 입력 화상은 흑백 2치 화상으로, 흑백 2치를 반전시킨 반전 화상에 대해서도, 흑화소 및 백화소가 연속해 있는 연결 성분을 추출한다. 반전 화상은 도 4a에 도시한 바와 같이, 입력 화상의 배경 영역의 색과 문자 부분의 색이 반전한다.

이 연결 성분의 추출 처리에 의해, 입력 화상의 흑화소의 각 연결 성분마다, 다른 라벨이 부착됨과 동시에, 반전 화상의 흑화소의 각 연결 성분마다, 다른 라벨이 부착된다.

다음에, 입력 화상과 반전 화상의 각각에 대해, 연결 성분과 연결 성분의 위치 관계 및 연결 성분과 연결 성분의 굵기의 유사성으로부터, 공통의 문자열 또는 문자열군을 구성하는 가능성이 높은 연결 성분을 그룹으로 나눈다.

여기서, 연결 성분의 굵기의 유사성이란, 연결 성분의 전 화소수에 대한 경계화소수의 비의 것이고, 공통의 문자열 또는 문자열군이란, 의미적으로 공동하여 동일한 것을 표현하는 문자열의 집합의 것이다.

그 결과, 도 4a에 도시한 바와 같이, 입력 화상의 「」이라는 문자는, 굵기가 상호 동일하고, 각각 근접하여 배치되어 있으므로, 그룹 a에 그룹핑된다. 또한, 입력 화상의 「」이라는 문자를 둘러싸는 테두리 및「調査グ」라는 외곽선 문자의 배경 부분에 대응하는 흑화소 영역은, 흑화소로 하나로 연결하고 있으므로, 그룹 b에 그룹핑된다.

또한, 반전 화상의 「」이라는 외곽선 문자의 배경 부분에 대응하는 흑화소 영역 및「調査グ」라는 문자를 둘러싸는 테두리는, 흑화소로 하나로 연결하고 있으므로, 그룹 a1에 그룹핑된다. 또한, 반전 화상의 「調査グ」라는 문자는, 굵기가 상호 동일하고, 각각 근접하여 배치되어 있으므로, 그룹 b1에 그룹핑된다.

여기서, 그룹 a는 배경 영역이 백으로 비교적 작은 문자의 그룹이고, 그룹 b는 배경 영역이 흑으로 비교적 큰 외곽선 문자이지만, 이 시점에서는 그룹 b는 외곽선 문자로는 인식할 수 없다. 그룹 a에는 백을 배경으로 문자가 있을 것 같은 것, 그룹 b는 전체가 거무스름한 것을 알 수 있을 정도이다. 이 때문에, 그룹 b의 흑화소로 구성되는 배경 영역에 대한 문자 인식 처리를 행하더라도, 「調査グ」라는 문자를 인식하는 것은 불가능하다.

또한, 그룹 a1은 배경 영역이 흑으로 비교적 작은 외곽선 문자이고, 그룹 b1은 배경 영역이 백으로 비교적 큰 문자의 그룹이지만, 이 시점에서는 그룹 b1은 외곽선 문자로는 인식되어 있지 않다. 그룹 a1은 전체가 흑의 것, 그룹 b1에는 백을 배경으로 문자가 있을 것 같은 것을 알 수 있을 정도이다. 이 때문에, 그룹 a1의 흑화소로 구성되는 배경 영역에 대한 문자 인식 처리를 행하더라도, 「」이라는 문자를 인식하는 것은 불가능하다.

이와 같이 그룹으로 나누면, 그룹마다 문자 인식 처리를 행한다. 그 결과의 각 문자의 제1위 인식 후보의 거리치의 역수의 합을 그룹의 문자 인식도로 한다. 따라서, 그룹의 문자 인식도의 값이 높으면, 추출하여야 할 문자열일 가능성이 높게 된다. 그룹의 문자 인식도에 그룹이 차지하는 구형 영역의 면적에 의해 웨이트한 것을 그룹의 평가치로 한다.

다음에, 모든 그룹의 조합에 대해 평가치를 구하여, 조합의 평가치로 한다. 그룹을 조합할 때에는, 그룹이 차지하는 구형 영역에 중첩이 없는 그룹만을 관련짓고, 그룹이 차지하는 구형 영역에 중첩이 없는 그룹의 조합을 전부 구한다.

도 4b의 조합은 그룹이 차지하는 구형 영역에 중첩이 없는 그룹을 조합시키는 것을 설명하기 위한 도면이다.

도 4b에 도시한 바와 같이, 도 4a의 그룹 a는, 그룹 b1이 차지하는 구형 영역과 중첩되지 않기 때문에, 그룹 b1과 조합될 가능성이 있지만, 그룹 b 및 그룹 a1은, 그룹이 차지하는 구형 영역이 중첩되기 때문에, 그룹 b 및 그룹 a1과 조합되는 경우가 없다.

한편, 그룹 b는, 그룹 a, 그룹 a1, 혹은 그룹 b1 중 어떤 그룹과 조합하더라도, 그룹이 차지하는 구형 영역이 중첩되기 때문에, 그룹 a, 그룹 a1, 혹은 그룹 b1 중 어느 한쪽의 그룹과도 조합될 가능성이 없다.

따라서, 모든 조합으로부터, 그룹 a와 그룹 b의 조합, 그룹 a와 그룹 a1의 조합, 그룹 b와 그룹 a1의 조합, 그룹 b와 그룹 b1의 조합 및, 그룹 a1과 그룹 b1의 조합이 제외되고, 그룹 a와 그룹 b1의 조합만이 남는다. 도 4b에 제외되는 조합을 점선으로 나타낸다. 실선으로 접속되는 그룹의 조합의 전부에 대해 평가치가 계산된다. 그 결과, 조합의 평가치가 가장 높은 그룹의 조합을 문자열로서 추출한다.

도 4c는 추출 결과를 나타낸다.

도 4c에 있어서, 그룹 a와 그룹 b1의 조합이 선택되고, 그룹 a로부터 추출되는 패턴의 문자 인식을 행한 결과, 「」이라는 문자열이 출력되고, 그룹 b1으로부터 추출되는 패턴의 문자 인식을 행한 결과, 「調査グ」라는 문자열이 출력된다.

여기서, 혹시, 그룹 b에 대한 문자 인식을 행한 경우에는, 그룹 b는 입력 화상의 「」이라는 문자를 둘러싸는 테두리 및「調査グ」라는 외곽선 문자의 배경 부분에 대응하는 흑화소 영역에 구성되어 있기 때문에, 「調査グ」라는 문자열을 정확하게 인식할 수 없다.

이 때문에, 도 4a의 입력 화상으로부터 추출되는 패턴만을 이용하여, 인식 처리를 행하면 「」이라는 문자열은 추출할 수 있지만, 「調査グ」라는 문자열은 추출할 수 없게 된다.

한편, 그룹 a1에 대한 문자 인식을 행한 경우에는, 그룹 a1은 반전 화상의 「」이라는 외곽선 문자의 배경 부분에 대응하는 흑화소 영역 및「調査グ」라는 문자를 둘러싸는 테두리로 구성되어 있기 때문에, 「調査グ」라는 문자열을 정확하게 인식할 수 없다.

이 때문에, 도 4a의 반전 화상으로부터 추출되는 패턴만을 이용하여, 인식 처리를 행하면, 「調査グ」라는 문자열은 추출할 수 있지만, 「」이라는 문자열은 추출할 수 없게 된다.

이것에 대해, 도 4a 내지 도 4c의 실시예에서는, 입력 화상으로부터 추출되는 패턴 및 반전 화상으로부터 추출되는 패턴의 양쪽을 이용하여 문자 인식을 행하고, 「」이라는 문자열은 입력 화상으로부터 추출하고, 「調査グ」라는 문자열은 반전 화상으로부터 추출할 수 있으므로, 「」이라는 문자열 및「調査グ」라는 문자열의 양쪽 모두 정확하게 추출하는 것이 가능하다.

도 5는 본 발명의 제3 실시예에 따른 문자열 추출 장치의 구성을 나타낸 블럭도이다.

도 5에 있어서, 문자열 추출 장치(41)는 연결 성분 추출 수단(42)과 그룹핑 수단(43)과 문자 인식 수단(44)과 조합 평가 수단(45)과 문자열 추출 수단(46)을 구비하고 있다.

연결 성분 추출 수단(42)에서는, 입력한 화상으로부터 화소의 색에 기초하여화소의 색이 연속해 있는 연결 성분을 추출한다. 입력 화상이 컬러 화상인 경우에는 각색에 대해 연결 성분을 추출하고, 입력 화상이 흑백 2치 화상인 경우에는 반전 화상에 대해서도 흑화소 및 백화소가 연속해 있는 연결 성분을 추출한다.

그룹핑 수단(43)에서는, 연결 성분과 연결 성분의 위치 관계 및 연결 성분과 연결 성분의 굵기의 유사성으로부터 공통의 문자열 또는 문자열군을 구성하는 가능성이 높은 연결 성분을 그룹으로 나눈다.

문자 인식 수단(44)에서는, 그룹마다 문자 인식 처리를 행하고, 그룹의 문자 인식도를 구한다. 조합 평가 수단(45)에서는, 그룹의 평가치를 구하고, 또한 조합의 평가치를 구한다. 문자열 추출 수단(46)에서는, 조합의 평가치가 가장 높은 그룹의 조합을 문자열로서 추출한다.

이와 같이, 도 5의 문자열 추출 장치(41)에서는, 연결 성분의 유사성으로부터 그룹으로 나누고, 그룹마다 문자 인식 처리를 실시하여 문자열다움을 부여하고, 정합성이 있는 조합의 그룹을 추출하므로, 흑백 혼재의 배경 모양, 컬러 문서 등이 복잡한 화상으로부터 문자열을 추출하는 것이 가능하게 된다.

또한, 도 5의 문자열 추출 장치(41) 및 기록 매체에서는, 추출 처리의 도중에는 색의 결정을 행하지 않고, 문자열 영역의 가정도 행하지 않고, 또한, 추출 처리의 과정에서 일률적으로 표준 문자의 선폭을 결정하지 않으므로, 문자열 추출의 정밀도가 향상된다.

이하, 본 발명의 제3 실시예에 따른 문자열 추출 장치(41)에 대해 도면을 이용하여 상세히 설명한다. 이 문자열 추출 장치(41)의 실시예로서, 신문의 헤드라인 등의 흑백 2치의 화상으로부터 문자열을 추출하는 경우를 예로 든다.

도 6은, 본 발명의 제3 실시예에 따른 문자열 추출 장치의 동작을 나타낸 플로우차트이다.

도 6에 있어서, 우선, 스텝 S1에 있어서, 화상이 입력되고, 스텝 S2로 진행한다. 스텝 S2에서는, 입력된 화상에 대해 흑백 반전의 화상을 생성한다. 계속해서, 입력 화상과 반전 화상의 처리를 병행하여 행하지만, 입력 화상의 처리를 하는 경우에는 스텝 S3으로, 반전 화상의 처리를 하는 경우에는 스텝 S6으로 진행한다.

입력 화상과 반전 화상이 얻어지면, 계속해서 각각의 연결 성분을 구하기 위해서 라벨링 처리를 행한다. 스텝 S3에서는 입력 화상의 라벨링 처리를, 스텝 S6에서는 반전 화상의 라벨링 처리를 행한다.

입력 화상과 반전 화상의 라벨링을 계속해서, 각각의 연결 성분을 그룹핑(그룹 나눔)한다. 도 6의 스텝 S4에서는, 입력 화상의 그룹핑을, 스텝 S7에서는, 반전 화상의 그룹핑을 행한다.

입력 화상과 반전 화상의 그룹핑을 계속해서, 각각의 그룹의 문자 인식 처리를 행한다. 스텝 S5에서는, 입력 화상의 그룹의 문자 인식 처리를, 스텝 S8에서는, 반전 화상의 그룹의 문자 인식 처리를 행한다.

입력 화상과 반전 화상의 그룹의 문자 인식 처리에 계속해서, 스텝 S9로 진행한다. 스텝 S9에서는, 그룹이 차지하는 구형 영역에 중첩이 있는 그룹을 그룹의 조합으로부터 제외하고, 정합성이 있는 조합을 전부 열거한다.

스텝 S10에서는, 후보에 오른 조합의 각각에 대해, 평가치에 기초하여 평가한다. 각 그룹의 평가치는, 그룹의 문자 인식도와 각 그룹이 차지하는 구형 영역의 면적과의 함수이고, 조합의 평가치는 정합성이 있는 조합에 대해 그룹의 평가치를 조합시켜 구한다.

계속해서, 스텝 S11로 진행하고, 스텝 S10에 있어서, 조합의 평가치가 최고의 조합의 그룹에 대응하는 문자열을 추출하여 처리를 종료한다.

도 7은, 본 발명의 한 실시예에 따른 라벨링 처리를 설명하는 도면이다.

도 7에 있어서, 외곽선 문자의 「祭」의 1문자가 1에서 4까지의 번호를 붙인 4개의 연결 성분 R1∼R4로 구성되어 있는 것이 도시된다. 이와 같이, 동일한 색의 화소(도 4a 내지 도 4c에서는 백화소)가 연속해 있는 연결 성분을 번호 등에 의해서 식별하여 가는 것을 라벨링이라고 한다.

도 8은, 본 발명의 한 실시예에 따른 그룹핑 처리를 나타낸 플로우차트이다.

도 8에 있어서, 우선, 스텝 S21에 있어서, 문자 성분 후보를 선택한다. 스텝 S21에서는, 대상 연결 성분의 압축을 행한다. 여기서는, 연결 성분의 외접 구형의 크기가 있는 기준 이하의 것을 제거하고, 명백하게 문자 성분 후보가 될 수 없는 것을 금후의 처리의 대상 밖으로 한다. 계속해서, 스텝 S22로 진행한다.

스텝 S22에서는, 연결 성분에 대하여 근방을 설정한다. 근방은, 연결 성분의 외접 구형의 주위를 일정한 크기로 둘러싼 때에 가능한 영역으로 한다. 연결 성분의 근방에 일부가 포함되는 연결 성분을 근방 연결 성분이라고 부른다. 계속해서, 스텝 S23으로 진행한다.

스텝 S23에서는, 연결 성분과 그 근방 연결 성분을 링크시킨다. 여기서 링크란, 연결 성분 및 근방 연결 성분의 각각이 동일한 문자열 혹은 동일한 문자열군에 속하는지를 판단하고, 연결 성분과 그 근방 연결 성분을 관계짓는 것이다.

연결 성분의 링크는, 연결 성분의 상대적 위치 및 굵기의 유사성에 기초하여 행해진다. 연결 성분 사이의 상대적 위치와 굵기의 유사성의 것을 연결 성분의 가족적 유사성이라고 부른다. 스텝 S23에서는, 모든 연결 성분 및 모든 근방 연결 성분과의 가족적 유사성이 판단되고, 스텝 S24로 진행한다.

스텝 S24에서는, 링크로 연결된 연결 성분 및 근방 연결 성분을 그룹으로서 추출한다. 연결 성분의 링크의 방법은 여러가지이고, 예를 들면, 연결 성분 A와 연결 성분 B와 연결 성분 C가 링크로 연결되어 있지만, 연결 성분 A와 연결 성분 C는 직접 연결되지 않는 경우가 있다. 또한, 연결 성분 A로부터 연결 성분 B에 링크하고 있지만, 연결 성분 B로부터 연결 성분 A에는 링크되어 있지 않는 경우도 있다.

이와 같은 링크를 형성하는 연결 성분을 호상(弧狀) 연결의 연결 성분이라고 부른다. 스텝 S24에서는, 링크로 연결된 호상 연결의 연결 성분의 집합을 추출하여 하나의 그룹으로 한다.

도 9는 본 발명의 한 실시예에 따른 연결 성분과 외접 구형의 예를 나타낸 도면이다.

도 9에 있어서, 가타카나의 「タ」라는 문자가 하나의 연결 성분이고, 그 외접 구형의 x방향의 길이가 dx, y방향의 길이가 dy이다.

도 10은 본 발명의 한 실시예에 따른 대상 연결 성분의 제한 방법을 나타낸 플로우차트이다.

도 10에 있어서, 연결 성분의 외접 구형을 나타내는 x방향의 길이 dx의 임계치와 y방향의 길이 dy의 임계치를, 각각 th1 내지 th2로 미리 결정해 놓는다. 도 10의 스텝 S31에 있어서, x방향의 길이 dx와 y방향의 길이 dy가 입력되면, 스텝 S32에 있어서, y방향의 길이 dy가 임계치 th2보다 작은지의 여부가 판정된다.

스텝 S32에 있어서, y방향의 길이 dy가 임계치 th2보다 작으면 스텝 S33으로 진행하고, y방향의 길이 dy가 임계치 th2보다 작지 않으면 스텝 S36으로 진행한다. 스텝 S33에 있어서, x 방향의 길이 dx가 임계치 th1보다 크고, 임계치 th2보다 작으면 스텝 S35로 진행하고, x방향의 길이 dx가 임계치 th1 이하이거나, 임계치 th2 이상이면 스텝 S34로 진행한다.

스텝 S34에 있어서, y방향의 길이 dy가 임계치 th1보다 크면, 스텝 S35로 진행하고, y방향의 길이 dy가 임계치 th1보다 크지 않으면 스텝 S36으로 진행한다.

스텝 S35에 있어서는, 상기 연결 성분을 문자 성분 후보가 될 수 있도록 하여, 스텝 S36에 있어서는, 상기 연결 성분을 금후의 처리의 대상 밖으로 하여 처리를 종료한다.

도 11은, 본 발명의 일 실시예에 따른 연결 성분 근방을 설명하는 도면이다.

도 11에서, 근방은 연결 성분의 외접 구형의 주위를 일정한 크기로 둘러쌌을 때에 형성되는 영역이다.

여기서, 일정한 크기란 도 11에 도시된 바와 같이 세로쓰기인 경우에는 가로 방향의 양측에 각각 가로 방향 크기×(1/6), 세로 방향의 상하에 세로 방향 크기×(3/4)의 영역으로 한다. 가로쓰기의 경우에도 근방의 정의는 동일하다.

도 11에서는, 「京」이라는 문자에 주목하여, 「京」의 근방을 설정한 경우, 「京」의 근방에는, 「東」이라는 문자와 「に」라는 문자가 걸려 있으므로, 「京」이라는 문자의 근방 연결 성분이 「東」이라는 문자와 「に」라는 문자인 것을 알 수 있다. 도 11의 「東京に今秋」의 배경 영역의 절반에는 대소의 네트 패턴이 배치되어 있고, 「京」의 문자는 ○ 표시를 한 부분에서 접촉한 것처럼 나타내기 때문에, 「京」의 1문자가 하나의 연결 성분이라고 간주된다.

또한, 도 11에서 「京」의 문자가 ○ 표시를 한 부분에서 접촉하지 않는다고 하면, 「京」은 「상부 성분」과 그 이외의 2개의 연결 성분으로 이루어지고, 각각의 연결 성분의 근방에 대해, 각각의 크기에 대해 근방 연결 성분이 조사된다.

도 12는, 본 발명의 일 실시예에 따른 연결 성분의 가족적 유사성을 설명하는 도면이다.

도 12에서, 연결 성분의 가족적 유사성은 연결 성분간의 상대적인 위치 관계와 연결 성분의 평균적 굵기의 차에 따라 정해진다. 여기서, 평균적 굵기는, 연결 성분의 전 화소수에 대한 경계 화소수의 비, 즉 (경계 화소수/전화소수)로 표시된다.

도 12에 도시된 연결 성분 A와 연결 성분 A의 근방 연결 성분 B의 위치 관계를 d 및 nx, 연결 성분 A와 근방 연결 성분 B의 평균적 굵기를 각각 ta와 tb로 하면, 연결 성분 A에 대한 근방 연결 성분 B의 가족적 유사성은, 이하의 수학식 1로 표시된다.

연결 성분 A에 대한 근방 연결 성분 B의 가족적 유사성

=d/nx+0.1×max(ta, tb)/min(ta, tb)

여기서, d는, 근방 연결 성분 B의 x 방향의 성분 nx가 연결 성분 A로부터 삐져나온 부분의 길이를 나타낸다.

도 12에 도시된 연결 성분 A에 대한 근방 연결 성분 B의 가족적 유사성도, 연결 성분 B에 대한 연결 성분 C의 가족적 유사성도 동일한 정도로 높으므로, 각각의 연결 성분 A, B, C는 동일한 문자열에 속한다고 판단된다. 여기서는, 연결 성분 B에 대한 연결 성분 C의 가족적 유사성은 굵기의 성분에 대해서만 고려되어진다.

도 13은 본 발명의 일 실시예에 따른 그룹의 문자 인식도의 산출 방법을 설명하는 도면이다.

도 13에서, 그룹의 문자 인식도는 그룹마다 문자 인식 처리를 행하고, 그 결과의 각 문자의 제1위 인식 후보의 거리치의 역수의 합으로 나타낸다. 문자의 거리치가 작은 것은 문자의 인식도가 높은 것을 의미한다.

도 13에 도시된 바와 같이, 예를 들면 「東京に今秋」이라는 문자열을 그룹 A, 그룹 A의 각 문자「東」, 「京」, 「に」, 「今」, 「秋」의 제1위 인식 후보의 거리치를 각각 d1, d2, d3, d4, d5로 하면, 그룹 A의 문자 인식도 Ra는, 다음 수학식 2로 나타낸다.

Ra=1/d1+1/d2+1/d3+1/d4+1/d5

또한, 도 13의 「東京に今秋」라는 문자열의 배경 영역에 있는 「네트 패턴」은 완전하게 「점」이면, 대상 연결 성분의 제한으로 대상밖이 될 가능성이 높지만, 만약 점과 점이 접속된 「네트워크 패턴」이라고 하면, 그룹 B로서 분류되고, 그룹 B도, 「네트워크 패턴」의 반전 화상의 그룹도, 문자 인식도는 0인 것이 예상된다. 또한, 이 그룹 B의 「네트워크 패턴」은, 「東京に今秋」이라는 문자열로 이루어지는 그룹 A와 중첩되기 때문에, 그룹 B가 그룹 A와 조합되어 출력되는 일은 없다.

도 14는, 본 발명의 일 실시예에 따른 연합 그래프와 클리크를 도시하는 도면이다.

도 14에서, 그룹이 차지하는 구형 영역에 중첩이 없는 그룹만을 관련화하고, 그룹이 차지하는 구형 영역에 중첩이 없는 그룹의 조합을 전부 구하기 위해, 연합 그래프와 클리크의 개념을 이용하고 있다.

즉, 정합성이 있는 조합을 카운트하기 위해 연합 그래프를 작성하고, 완전 그래프인 클리크를 전부 요구함으로써, 그룹이 차지하는 구형 영역에 중첩이 있는 그룹을 그룹의 조합으로부터 제외시킬 수 있다.

도 14의 연합 그래프는, 그룹을 노드로서 그룹이 차지하는 구형 영역이 상호 중첩되지 않은 그룹에 상당하는 노드끼리, 패스(실선)로 접속하여 작성한 것이다. 연합 그래프에서, 구형 영역에 중첩이 있는 그룹에 상당하는 노드끼리는 패스로 접속되지 않는다.

클리크는 정합성이 있는 노드의 조합을 나타낸다. 클리크는 연합 그래프로부터 복수 작성되고, 각각의 클리크는 모든 노드가 패스로 연결되는 완전 그래프이다. 연합 그래프로부터 클리크를 구함으로써 정합성이 있는 그룹의 조합을 전부 셀 수 있다.

도 13에서 임시로 설정한 그룹 B의 「네트워크 패턴」과 그룹 A의 「東京に今秋」에 대해 그룹 A와 그룹 B가 개별로 인식되어도, 그룹 A와 그룹 B의 조합으로서 성립하지 않는 것은 이 때문이다.

이렇게 함으로써 정합성이 있는 그룹에 대한 조합의 평가치를 구하는 것이 가능해지고, 평가의 결과, 예를 들면 배경 영역에 있는 네트워크 패턴이나, 오물등이 제외되게 된다.

예를 들면, 도 14에서 노드 N1 ∼ N8로 이루어지는 연합 그래프가 작성된 것으로 하면, 각 노드로부터 다른 모든 노드에 패스가 형성되는 완전 그래프를 구한다. 예를 들면, 노드 N1은 노드 N1로부터 다른 모든 노드 N2 ∼ N8에 패스가 형성되기 때문에, 노드 N1은 클리크의 노드가 되고, 노드 N2는 노드 N2로부터 노드 N8에 패스가 형성되지 않기 때문에, 노드 N2는 클리크의 노드로부터 제외되고, 노드 N3은, 노드 N3으로부터 다른 모든 노드 N1, N2, N4 ∼ N8에 패스가 형성되기 때문에, 노드 N3은 클리크의 노드가 되고, 노드 N4는 노드 N4로부터 다른 모든 노드 N1 ∼ N3, N5 ∼ N8에 패스가 형성되기 때문에, 노드 N4는, 클리크의 노드가 되고, 노드 N5는 노드 N5로부터 다른 모든 노드 N1 ∼ N4, N6 ∼ N8에 패스가 형성되기 때문에, 노드 N5는 클리크의 노드가 되고, 노드 N6은 노드 N6으로부터 노드 N8에 패스가 형성되지 않기 때문에, 노드 N6은 클리크의 노드로부터 제외되고, 노드 N7은 노드 N7로부터 다른 모든 노드 N1 ∼ N6, N8에 패스가 형성되기 때문에, 노드 N7은 클리크의 노드가 되고, 노드 N8은 노드 N8로부터 다른 모든 노드 N1 ∼ N7에 패스가 형성되기 때문에, 노드 N8은 클리크의 노드가 된다.

이 결과, 노드 N1, N3, N4, N5, N7, N8로 이루어지는 클리크를 추출할 수 있다. 연합 그래프로부터 클리크를 추출함으로써, 구형 영역이 상호 중첩되지 않은 그룹만을 효율적으로 추출할 수 있다.

도 15는, 본 발명의 일 실시예에 따른 연결 성분의 중첩이 없는 그룹의 추출 방법을 나타내는 플로우차트이다.

도 15에서, 각 그룹에 대해 다른 모든 그룹에 대해 관련되어 있는지의 여부의 판단을 행하고(스텝 S41), 연합 그래프를 생성한다(스텝 S42). 이어서, 연합 그래프로부터 클리크를 추출하고(스텝 S43), 입력 화상으로부터 추출되는 그룹과 반전 화상으로부터 추출되는 그룹의 조합 중, 정합성이 있는 조합을 확정한다(스텝 S44).

도 16a 내지 도 16d는, 본 발명의 일 실시예에 따른 연결 성분끼리의 링크 부착의 방법을 설명하는 도면이다.

도 16a에서, 「水道 メ-タ-」라는 배경이 흑색인 외곽선 문자와 「談合解明」이라는 흑화소 문자가 입력된 것으로 하고, 「談」이라는 문자의 일부의 연결 성분 R11과 링크된 연결 성분을 추출하는 것으로 한다.

이 경우, 도 16b에 도시된 바와 같이 연결 성분 R11의 외접 구형 G1이 생성되고, 이 외접 구형 G1의 주위에 연결 성분의 근방 B1이 설정된다. 연결 성분의 근방 B1이 설정되면, 도 16c에 도시된 바와 같이 연결 성분의 근방 B1에 따른 근방연결 성분 R12 ∼ R20이 추출된다. 근방 연결 성분 R12 ∼ R20이 추출되면, 도 16 d에 도시된 바와 같이, 연결 성분 R11과 근방 연결 성분 R12 ∼ R20의 가족적 유사성이 조사된다. 여기서, 근방 연결 성분 R12는 연결 성분 R11과 굵기가 크게 다르므로, 근방 연결 성분 R12는 연결 성분 R11의 링크 부착의 대상으로부터 제외되고, 근방 연결 성분 R12를 제외한 근방 연결 성분 R13 ∼ R20이 연결 성분 R11과 링크 부착된다.

도 17a 내지 도 17d는, 본 발명의 일 실시예에 따른 클리크가 되는 그룹과 클리크가 되지 않은 그룹의 예를 나타내는 도면이다.

도 17a에서, 원화상의 「水道 メ-タ-」라는 문자는, 굵기가 상호 동일하고, 각각 근접하여 배치되어 있으므로, 그룹 1에 그룹핑된다. 또한, 원화상의 「談合解明」이라는 외곽선 문자의 배경 부분에 대응하는 흑화소 영역은, 흑화소에서 하나로 연결하고 있으므로, 그룹 2에 그룹핑된다.

또한, 반전 화상의 「水道 メ-タ-」라는 외곽선 문자의 배경 부분에 대응하는 흑화소 영역은, 흑화소에서 하나로 연결하고 있으므로, 그룹 a로 그룹핑된다. 또한, 반전 화상의 「談合解明」이라는 문자는, 굵기가 상호 동일하고, 각각 근접하여 배치되어 있으므로, 그룹 b로 그룹핑된다.

이어서, 도 17c에 도시된 바와 같이, 그룹 1과 그룹 b는, 그룹 1이 차지하는 구형 영역과 그룹 b가 차지하는 구형 영역이 상호 중첩되지 않기 때문에, 클리크라고 간주되고, 그룹 1과 그룹 b는 정합성이 있는 조합으로 취급된다. 또한, 도 17d에 도시된 바와 같이, 그룹 1과 그룹 a는, 그룹 1이 차지하는 구형 영역과 그룹 a가 차지하는 구형 영역이 상호 중첩되고, 클리크가 아니라고 간주되기 때문에, 그룹 1과 그룹 a는 정합성이 없는 조합으로 취급된다.

이와 같이 함으로써, 도 17b에 도시된 바와 같이 그룹 1은, 그룹 b 및 그룹 2와는 정합성이 있는 조합이 되지만, 그룹 a와는 정합성이 있는 조합이 되지 않는다. 또한, 그룹 2는 그룹 1 및 그룹 a와는 정합성이 있는 조합으로 되지만, 그룹 b와는 정합성이 있는 조합으로 되지 않는다. 또한, 그룹 a는 그룹 2 및 그룹 b와는 정합성이 있는 조합으로 되지만, 그룹 1과는 정합성이 있는 조합으로 되지 않는다. 또한, 그룹 b는 그룹 1 및 그룹 a와는 정합성이 있는 조합으로 되지만, 그룹 2와는 정합성이 있는 조합으로 되지 않는다.

도 18은, 본 발명중 일 실시예에 따른 조합 평가치의 산출 방법을 나타내는 도면이다.

도 18에서, 조합의 평가치는 정합성이 있는 조합에 대해, 그룹의 문자 인식도와 각 그룹이 차지하는 구형 영역의 면적과의 함수인 그룹의 평가치를 조합하여 구한다.

예를 들면, 도 18의 입력 화상으로부터 정합성이 있는 그룹의 조합으로서, 그룹 A와 그룹 B의 조합을 얻었다고 한다. 그룹 A가 차지하는 구형 영역의 면적을 Sa, 그룹의 문자 인식도를 Ra, 그룹 B가 차지하는 구형 영역의 면적을 Sb, 그룹의 문자 인식도를 Rb로 하면, 그룹 A와 그룹 B의 조합의 평가치는, 아래의 수학식 3으로 구할 수 있다.

조합(A, B)의 평가치=aSa×Ra×Ra+Sb×Rb×Rb

또한, 본 실시예에서는 흑백 화상에 대해 설명했지만, 본 실시예는 흑백 화상에 한정되지 않고, 흑백 화소를 색의 채도, 명도, 농도로 대체함에 따라, 널리 컬러 문자나 컬러의 배경에 적용할 수 있는 것은 물론이다.

또한, 본 실시예에서는 세로쓰기 문자를 예로 하여 설명했지만, 세로쓰기 문자에도 종횡 혼재의 문자열에도 적용할 수 있는 것은 물론이다.

이어서, 본 발명의 제4 실시예에 따른 패턴 추출 장치에 대해 설명한다.

본 발명의 제4 실시예에서는 연결 성분의 중첩 네스트 통합을 생략함으로써, 화상 전체가 통합되는 것을 방지함과 동시에, 헤드라인 영역을 추출할 때에 악영향의 근원이 되는 도면이나 사진의 일부는, 보다 큰 구형으로 흡수 통합해 두도록 함으로써, 그 영향을 경감시킨다. 일반적으로, 도면이나 사진의 일부로 이루어지는 구형은, 상호 중첩되는 경우가 많고, 이들을 분별하는 목표가 된다. 그래서, 헤드라인 구형의 상호 중첩도를 계산하고, 어느 한 임계치를 넘는 것을 도면이나 사진의 일부로 이루어지는 구형이라고 판단하고, 그 구형에 한하여 중첩 네스트 통합을 행한다.

또한, 중첩 네스트 통합을 생략했을 때에, 정확한 본문 문자 크기를 추정하기위해, 연결 성분의 외접 구형의 크기에 관한 막대 그래프이고, 빈도 및 구형의 면적에 따라 웨이트된 것을 이용한다. 이에 따라, 문자의 일부분이 그대로 카운트되고, 실제의 본문 문자 크기보다도 작은 크기의 구형의 수가 최대가 되어도, 면적의 가중이 있으므로, 새로운 막대 그래프에서는 최대가 되지 않는다. 따라서, 실제의 본문 문자 크기보다도 작은 크기의 구형이 추정 문자 크기로는 되지 않는다. 반대로, 큰 연결 성분이 있었다고 해도, 면적은 크지만 빈도가 작으므로, 실제의 본문 문자 크기보다도 큰 크기의 구형도 추정 문자 크기는 되지 않는다.

이하, 본 발명의 제4 실시예에 대해 흑백 2치의 화상의 경우를 예로 들어 설명한다.

도 19는, 본 발명의 제4 실시예에 따른 패턴 추출 장치의 동작을 나타내는 플로우차트이다.

도 19에서, 우선 입력된 화상에 대해 라벨링 처리를 실시한다(스텝 S51). 이 라벨링 처리에 따라, 각 연결 성분의 외접 구형의 좌표 정보를 얻을 수 있다.

이어서, 본문 문자 크기의 추정을 행한다(스텝 S52). 이 본문 문자 크기의 추정에서는, 우선 연결 성분의 외접 구형의 크기에 관한 막대 그래프를 작성한다. 단, 이 막대 그래프는, 빈도 및 구형의 면적에 따라 웨이트된 것으로 한다. 구체적으로는, 우선 임의의 연결 성분의 가로폭을 dx, 세로폭을 dy로 했을 때, 그 큰 쪽의 막대 그래프를 취한다. 또한, 얻어진 막대 그래프의 각 값 H(i)에 대해 H′(i)=H(i)×H(i)×i×i (단, i는 구형의 크기를 나타냄.) 라고 하는 변환을 실시하여, 새로운 막대 그래프 H′를 작성한다. 이 새로운 막대 그래프 H′에 대해, 막대 그래프 값의 최대를 제공하는 곳을 본문 문자 크기로 한다.

도 20a 내지 도 20b는, 본 발명의 일 실시예에 따른 외접 구형의 크기를 구하기 위한 막대 그래프의 일례를 나타내는 도면이다.

도 20a에서, 중첩 네스트 통합을 행하지 않고, 외접 구형의 크기의 빈도 H를 나타내는 막대 그래프를 생성하면, 본문 문자의 크기에 대응하는 피크 P2가 발생됨과 동시에, 통합되기 전의 문자의 일부의 외접 구형의 크기에 대응하는 피크 P1이 발생하는 경우가 있다.

이 때문에, 이 막대 그래프를 이용하여 본문 문자 크기를 추정하면, 피크 P1에 대응하는 외접 구형의 크기가 본문 문자 크기라고 추정되고, 본문 문자 크기의 크기가 잘못 추정되는 경우가 있다.

한편, 도 20b에서, 도 20a의 막대 그래프를 외접 구형의 크기로 부가하면, 외접 구형의 크기가 큰 피크 P2의 막대 그래프값 H에 비교하여, 외접 구형의 크기가 작은 피크 P1의 막대 그래프 값 H는 작아진다. 이 결과, 도 20b의 막대 그래프에서는, 통합되기 전의 문자의 일부 외접 구형의 크기에 대응하는 피크 P1′의 값에 비교하여, 본문 문자의 크기에 대응하는 피크 P2′의 값을 크게 평가하는 것이 가능 해지고, 피크 P1′에 대응하는 외접 구형의 크기가 본문 문자 크기라고 잘못 추정되는 것을 방지하여 본문 문자 크기의 크기를 정확하게 추정하는 것이 가능해진다.

이어서, 본문 문자 구형 후보의 사영 테이블의 작성을 행한다(스텝 S53).

이 사영 테이블의 작성에서는, 우선 모든 구형 중에서 본문 문자 구형 후보를 선출한다. 구체적으로는, 연결 성분의 가로폭을 dx, 세로폭을 dy, 본문 문자 크기를 c, 임계치를 α로 하면, ｜max (dx, dy)-c｜α를 만족하는 구형을 본문 문자 구형 후보로 한다.

이어서, 전화상의 x 좌표 축, 및 y 좌표 축에 대해 본문 문자 구형 후보의 사영을 취한다. 즉, 어떤 본문 문자 구형 후보의 번호를 n, 그 구형의 좌측 상점의 좌표를 (x1, y1), 우측 하점의 좌표를 (x2, y2) 로 했을 때, x 좌표 축 상에서 x1 ∼ x2까지인 곳에, 또한 y 좌표 축 상에서 y1 ∼ y2까지인 곳에, 번호 n을 기록한다. 이와 같이 함으로써 본문 문자 구형 후보의 사영 테이블을 작성한다.

도 21은, 본 발명의 일 실시예에 따른 구형 번호의 사영 방법의 일례를 도시하는 도면이다.

도 21에서, 구형 번호 1 ∼ 6의 외접 구형이 생성된 것으로 하면, 각 구형 번호 1 ∼ 6을 xy 좌표 축에 사영한다. 예를 들면, x 좌표가 4 ∼ 6의 점에는, 구형번호 1, 6의 외접 구형이 걸려 있으므로, x 좌표가 4 ∼ 6의 점에는 구형 번호 1, 6이 사영된다. 또한, x 좌표가 7, 8, 10의 점에는, 구형 번호 6의 외접 구형이 걸려 있으므로, x 좌표가 7, 8, 10인 점에는 구형 번호 6이 사영된다. 또한, x 좌표가 9인 점에는, 구형 번호 2, 4, 6의 외접 구형이 걸려 있으므로, x 좌표가 9인 점에는 구형 번호 2, 4, 6이 사영된다. 또한, x 좌표가 11인 점에는, 구형 번호 3, 5의 외접 구형이 걸려 있으므로, x 좌표가 11인 점에는 구형 번호 3, 5가 사영된다. y 좌표에 대해서도 동일하다.

이어서, 헤드라인 구형 후보의 선택을 행한다(스텝 S54). 이 헤드라인 구형 후보의 선택에서는, 헤드라인 및 헤드라인를 구성하는 문자를 선택한다. 기본적으로는, 본문 문자의 어느 일정배의 크기 이상인 것을, 헤드라인 구형 후보로 한다.

도 22는, 본 발명의 일 실시예에 따른 헤드라인 구형 후보의 선택 방법을 나타내는 플로우차트이다.

도 22에서, 우선 구형의 좌측 상점의 좌표를 (x1, y1), 구형의 우측 하점의 좌표를 (x2, y2), 구형의 우측 하점의 x 좌표 x2와 구형의 좌측 상점의 x 좌표 x1과의 차를 dx, 구형의 우측 하점의 y 좌표 y2와 구형의 좌측 상점의 y 좌표 y1의 차를 dy, 본문 문자 크기를 moji로 한다(스텝 S71).

이어서, 이하의 수학식 4를 만족하는지의 여부를 판단하고(스텝 S72), 이 조건을 만족하지 않는 경우에는, 헤드라인 구형 후보가 아니라고 해도 처리를 종료하고, 이 조건을 만족하는 경우에는 스텝 S73으로 진행시킨다.

(dxmoji×16 또는 dymoji×2) 및 (dxmoji×2 또는 dymoji×16)

이어서, 이하의 수학식 5를 만족하는지의 여부를 판단하고(스텝 S73), 이 조건을 만족하지 않은 경우에는 헤드라인 구형 후보가 아니라고 해도 처리를 종료하고, 이 조건을 만족하는 경우에는, 헤드라인 구형 후보로서 등록한다(스텝 S74).

(dxmoji×3/2 또는 dymoji×3/2) 및 (dxmoji/3 또는 dymoji/3)

이어서, 박스형의 체크를 행한다(스텝 S55).

테두리의 전체, 혹은 그 일부로 이루어지는 연결 성분의 외접 구형을 박스형이라고 하기로 하면, 박스형은 헤드라인으로는 될 수 없지만, 크기 및 형상으로부터 볼때는, 박스형과 헤드라인 구형과의 판별을 할 수 없다. 그래서, 미리 구형 전체로부터 박스형을 제외해야한다. 일반적으로, 테두리 중에는 본문 문자가 많이 포함되고, 헤드라인 구형 중에는 본문 문자가 거의 포함되지 않기 때문에, 구형 중 본문 문자 구형 후보의 수를 조사하고, 박스형인지의 여부의 판단을 한다. 즉, 주목하는 영역의 외접 구형 내에 포함되는 본문 문자 구형 후보의 수를 세고, 어떤 일정한 수보다도 많을 때, 테두리, 혹은 테두리의 일부로 둘러싸인 영역이라고 판단한다. 여기서, 본문 문자 구형 후보는 외접 구형이 본문 문자 크기인 연결 흑화소 영역을 가리킨다. 또, 테두리 중 본문 문자의 수는, 문자 구형 후보의 사영 테이블을 이용하여, 효율적으로 계산할 수 있다.

도 23은, 본 발명의 일 실시예에 따른 박스형의 체크 방법을 설명하는 도면이다.

도 23에서, 외접 구형 K1 ∼ K6이 추출되고, 외접 구형 K1 ∼ K5가 헤드라인 문자의 구형 후보로서 선택된 것으로 한다. 여기서, 외접 구형 K1 ∼ K4는 헤드라인 문자의 외접 구형이고, 외접 구형 K5는 본문 문자를 둘러싼 테두리의 외접 구형인 것으로 한다. 이 경우, 외접 구형 K1 ∼ K5가 동일한 그룹으로 그룹핑되면, 헤드라인 문자의 외접 구형의 그룹 중에 헤드라인 문자이외의 외접 구형이 속하기 때문에, 헤드라인 문자의 추출을 정확히 할 수 없게 되므로, 외접 구형 K5를 헤드라인 문자의 구형 후보로부터 제거할 필요가 있다.

그래서, 본문 문자를 둘러싼 테두리 중에는, 본문 문자가 다수 포함되어 있다는 것에 주목하여, 헤드라인 문자의 구형 후보로서 선택된 외접 구형 K1 ∼ K5 중에 포함되는 본문 문자 크기의 외접 구형 K6의 갯수를 센다.

이 결과, 외접 구형 K5 중에는, 본문 문자 크기의 외접 구형 K6이 다수 포함되어 있고, 외접 구형 K1 ∼ K4 중에는, 본문 문자 크기의 외접 구형이 포함되지 않으므로, 본문 문자 크기의 외접 구형 K6이 다수 포함되어 있는 외접 구형 K5를 헤드라인 문자의 구형 후보로부터 제거함으로써, 헤드라인 문자의 구형 후보로서 외접 구형 K1 ∼ K4만을 정확하게 선택하는 것이 가능해진다.

이어서, 부분적 중첩 네스트 통합을 행한다(스텝 S56).

헤드라인 구형 후보 중에는, 도면이나 사진의 일부로 이루어지는 연결 성분의 외접 구형이 포함되는 경우가 있고, 이들 외접 구형은 다른 정확한 헤드라인 구형과 통합됨으로써, 악영향의 근원이 된다. 그래서, 이들 도면이나 사진의 일부로 이루어지는 외접 구형은, 보다 큰 구형에 흡수 통합해 둠으로써, 헤드라인 구형의 추출에의 악영향을 경감시켜야 한다. 일반적으로, 도면이나 사진의 일부로 이루어지는 구형은, 상호 중첩되는 경우가 많고, 이들을 분별하는 기준이 된다. 그래서, 외접 구형의 상호 중첩도를 계산하고, 어느 한 임계치를 넘는 것을 도면이나 사진의 일부로부터 얻을 수 있는 외접 구형이라고 판단하고, 그 구형에 한하여 중첩 네스트 통합을 행한다. 여기서, 외접 구형의 중첩도는, 외접 구형이 다른 외접 구형과 몇겹으로 중첩되어 있는지를 나타내는 수이다.

도 24는, 본 발명의 일 실시예에 따른 중첩 네스트 통합을 설명하는 도면이다.

도 24에서, 「」라는 문자의 연결 성분을 추출한 결과, 2개의 연결 성분 R1, R2가 추출되고, 연결 성분 R1의 외접 구형 K11 및 연결 성분 R2의 외접 구형 K12가 생성된 것으로 한다. 이 외접 구형 K11, K12에 중첩 네스트 통합을 행하면, 외접 구형 K11, K12를 둘러싼 외접 구형 K13이 생성된다.

이 결과, 복수의 스트로크로 구성되는 문자에 대해, 각 스트로크마다 다른 라벨이 부여된 경우에도, 하나의 문자를 구성하는 각 스트로크를 하나로 통합할 수 있다.

도 25a 내지 도 25b는, 본 발명의 일 실시예에 따른 부분적 중첩 네스트 통합을 설명하는 도면이다.

도 25a에서, 외접 구형 K21 ∼ K26이 생성된 것으로 한다. 여기서, 예를 들면, 외접 구형 K22에 대해서는, 외접 구형 K22는 외접 구형 K21 및 외접 구형 K23의 2개의 외접 구형과 중첩되어 있으므로, 중첩도가 2가 된다. 또한, 외접 구형 K23 에 대해서는 외접 구형 K23은 외접 구형 K22, 외접 구형 K24 ∼ K26의 4개의 외접 구형과 중첩되어 있으므로, 중첩도가 4가 된다.

여기서, 예를 들면 중첩도가 4이상인 외접 구형에 대해, 중첩 네스트 통합을 행하는 것으로 하면, 도 25b에 도시된 바와 같이 외접 구형 K22 ∼ K26을 포함하는 외접 구형 K27이 생성되고, 외접 구형 K21과 외접 구형 K27은 통합되지 않는다.

여기서, 예를 들면 외접 구형 K21은 헤드라인 문자의 외접 구형이고, 외접 구형 K22 ∼ K26은 배경 무늬의 외접 구형인 것으로 하고, 중첩도를 고려하지 않고 중첩 네스트 통합을 행하면, 외접 구형 K21 ∼ K26은 전부 통합되고, 헤드라인 문자의 외접 구형이 소실하여, 헤드라인 문자의 영역을 추출할 수 없게 된다.

한편, 중첩 네스트 통합을 전혀 행하지 않도록 하면, 외접 구형 K21 ∼ K26은 각각 별개로 존재하고, 헤드라인 문자의 배경의 무늬의 외접 구형 K22 ∼ K26이 헤드라인 구형 후보로서 선택되는 경우가 발생하고, 헤드라인 문자의 배경의 무늬의 외접 구형 K22 ∼ K26이 헤드라인 구형 후보로서 선택되는 경우에는, 헤드라인 문자가 정확한 추출을 할 수 없게 된다.

그래서, 중첩 네스트 통합의 대상이 되는 외접 구형 K21 ∼ K26을 중첩도를 이용하여 선별하고, 외접 구형 K22 ∼ K26만을 대상으로 하여 중첩 네스트 통합을 행함에 따라, 헤드라인 문자의 배경 무늬의 외접 구형 K22 ∼ K26을 외접 구형 K27에 흡수하여 외접 구형 K22 ∼ K26이 헤드라인 구형 후보로서 선택되는 것을 방지하는 것이 가능해짐과 동시에, 헤드라인 문자의 외접 구형 K21을 그대로 남겨 두는 것이 가능해지고, 헤드라인 문자의 추출 정밀도를 향상시키는 것이 가능해진다.

중첩도의 구체적인 계산은, 아래와 같이 함으로써 행할 수 있다.

우선, 도 21에 도시된 방법에 따라 헤드라인 구형 후보의 사영 테이블을 작성한다. 이어서, 헤드라인 구형 후보에 대해 1화소씩, x 좌표축의 사영 테이블과 y 좌표 축의 사영 테이블로부터 헤드라인 구형의 번호를 참조함에 따라, 중첩도를 계산한다.

이어서, 구형 통합을 행한다(스텝 S57).

이 구형 통합에서는 헤드라인 구형끼리의 통합이 행해진다. 우선, 주목하는 헤드라인 구형에 대해 근방 영역을 취하고, 다른 헤드라인 구형 중에서 일부가 그 근방 영역에 포함되는 헤드라인 구형을 다 조사한다. 그리고, 주목하고 있는 헤드라인 구형이 그 근방 영역 내의 헤드라인 구형과 통합할 수 있는지의 여부를 판단한다. 이 때, 근방 영역을 취하는 방법 및 통합 조건은, 세로쓰기용과 가로쓰기용의 2개의 케이스에 의거한 방법 및 조건으로 행한다.

도 26은 본 발명의 일 실시예에 따른 근방 구형의 예를 나타내는 도면이다.

도 26에서, 외접 구형 K31 ∼ K36이 생성되는 것으로 하고, 외접 구형 K31을 주목 구형으로 하여, 근방 영역을 설정하게 하면, 외접 구형 K31 주위의 소정의 범위 내에 근방 영역 H1이 설정된다. 외접 구형 K31과 구형 통합되는 외접 구형의 후보로서, 근방 영역 H1에 대한 외접 구형 K32 ∼ K34가 선택되고, 외접 구형 K35, K36은, 외접 구형 K31과 구형 통합되는 외접 구형의 후보로부터 제외된다.

도 27은 본 발명의 일 실시예에 따른 근방 통합 처리를 나타내는 플로우차트이다.

도 27에서, 우선 구형 집합을 입력하고(스텝 S81), 구형사이의 링크의 설치를 행한다(스텝 S82). 구형사이의 링크 설치에서는, 우선 주목 구형의 근방을 설정하고(스텝 S91), 주목 구형의 근방에 대한 외접 구형을 추출함으로써, 주목 구형의 근방 구형을 결정하고(스텝 S92), 주목 구형과 근방 구형과의 위치 관계, 문자선 굵기, 또는 각 구형 내의 흑화소 밀도 등을 고려함으로써, 주목 구형과 근방 구형과의 통합 여부의 결정을 행한다. 그리고, 주목 구형과 근방 구형이 통합 가능하게 된 것에 대해 링크를 설치한다.

이어서, 링크로 이어지는 극대 구형 집합의 추출을 행하고(스텝 S83), 극대 구형 집합에 속하는 구형을, 스텝 S81에서 입력된 구형의 집합으로부터 삭제하고, 극대 구형 집합의 외접 구형을 구형 집합에 추가시킨다(스텝 S84).

이어서, 중첩 구형 제거를 행한다(스텝 S58).

이 중첩 구형 제거에서는, 통합된 헤드라인 구형 중에서 중첩을 피하기 위해, 동일한 구형의 한쪽을 기각한다.

도 28은, 본 발명의 일 실시예에 따른 중첩 구형의 일례를 나타내는 도면이다.

도 28에서, 외접 구형 K41, K42가 추출되고, 외접 구형 K41을 주목 구형으로서 세로 통합을 행하는 경우, 외접 구형 K41의 주위에 근방 영역 H11이 설정된다. 그리고, 근방 영역 H11에 관한 외접 구형 K42가 추출되고, 외접 구형 K41과 외접 구형 K42의 통합이 가능하다고 판정되면, 외접 구형 K41, K42를 포함하는 외접 구형 K43이 생성된다.

한편, 외접 구형 K41을 주목 구형으로서 가로 통합을 행하는 경우, 외접 구형 K41 주위에 근방 영역 H12가 설정된다. 그리고, 근방 영역 H12에 관한 외접 구형 K42가 추출되고, 외접 구형 K41과 외접 구형 K42과의 통합이 가능하다고 판정되면, 외접 구형 K41, K42를 포함하는 외접 구형 K43이 생성된다.

이 결과, 완전히 동일한 외접 구형 K43이 중첩하여 생성되기 때문에, 한쪽 외접 구형 K43을 기각한다.

이어서, 박스형의 체크를 행한다(스텝 S59).

이 박스형의 체크에서는, 얻어진 헤드라인 구형에 대해 다시 그것이 박스형인지의 여부의 판단을 사영 테이블을 이용하여 행하고, 헤드라인 구형 중에서 박스형을 제외시킨다.

이어서, 헤드라인 구형이 표시된다(스텝 S60). 이 헤드라인 구형의 마킹에서는, 이렇게 해서 얻어진 헤드라인 구형에 대해 그 크기 및 형상으로부터 마킹을 부여한다.

도 29는, 본 발명의 일 실시예에 따른 헤드라인 구형의 마킹 방법을 설명하는 도면이다.

도 29에서 외접 구형 K51이 생성되고, 그 외접 구형 K51의 가로 방향의 길이를 dx, 세로 방향의 길이를 dy로 하면, 이 외접 구형 K51에 대한 마킹은, 아래식으로 부여된다.

마크 = (1+α × ratio) × (dx × dy)

ratio = max (dx, dy)/min(dx, dy)

여기서, α는 파라미터이다.

이 마킹을 산출함으로써, 헤드라인 문자로 구성되는 타이틀이, 하나의 문서 화상으로부터 복수개 얻어진 경우, 이들의 타이틀에 우선 순위를 붙여 출력할 수 있다.

이상 설명된 바와 같이, 본 발명에 따르면 연결 성분의 가족적 유사성으로부터 그룹으로 나뉘고, 그룹마다 문자 인식 처리를 실시하여 문자열다움을 부여하고, 정합성이 있는 조합의 그룹을 추출하므로, 흑백 혼재의 배경 모양, 복수의 폰트 혼재, 컬러 문서, 복수행, 종횡 혼재, 및 이들의 복합체로 구성되는 복잡한 화상으로부터 문자열을 추출하는 것이 가능해진다고 하는 효과가 있다.

또한, 본 발명의 일 형태에 따르면, 추출 처리의 도중에서는 색의 결정이나 문자열 영역의 가정을 행하지 않고, 또한 추출 처리의 과정에서 일률적으로 표준 문자의 선폭을 결정해 버리는 일이 없으므로, 문자색을 잘못 보는 일이 없고, 또한 비교적 가는 선분을 빠뜨리는 일이 없어지고, 문자열 추출의 정밀도가 향상한다고 하는 효과가 있다.

또한, 본 발명의 일 형태에 따르면, 입력 화상 및 상기 입력 화상의 흑백 반전 화상의 각각으로부터 얻어지는 패턴의 인식 결과 중, 상호 영역이 중첩하지 않은 부분을 조합한 것을, 상기 입력 화상으로부터의 패턴의 추출 결과로 함에 따라, 신문등의 헤드라인 문자 중에, 흑화소로 구성된 문자와 외곽선 문자가 혼재하는 경우에도, 흑문자 후보와 백문자 후보의 갯수로부터 문자의 색을 결정하고, 문자색이 흑이라고 된 경우에는 입력 화상의 연결 성분만이 그 이후의 처리 대상이 되고, 흑문자는 정확히 인식할 수 있지만, 외곽선 문자는 인식 불능이 되거나, 문자색이 백이 된 경우에는 흑백 반전 화상의 연결 성분만이 문자 인식의 처리 대상이 되고, 외곽선 문자는 정확히 인식할 수 있지만, 흑문자는 인식 불능이 되거나 하는 것을 방지하는 것이 가능해지고, 배경 모양의 흑백 혼재, 복수 종류의 폰트 혼재, 컬러 문서, 복수행, 종횡 혼재, 및 이들의 복합체로 구성되는 복잡한 화상으로부터 문자열을 정밀도 좋게 추출하는 것이 가능해진다.

또한, 본 발명의 일 형태에 따르면, 외접 구형의 빈도를 그 외접 구형의 면적에서 웨이트함에 따라, 하나의 문자가 상호 분리된 복수의 스트로크로 구성되고, 중첩 네스트 처리를 행하지 않았기 때문에, 각 스트로크마다 생성되는 외접 구형이 그대로 남는 경우에도, 하나의 문자의 일부로 구성되는 외접 구형은, 하나의 문자 전체로 구성되는 외접 구형보다도, 크기가 작아지기 때문에 하나의 문자 일부로 구성되는 외접 구형의 빈도를 작게 하는 것이 가능해지고, 문자 크기를 추정할 때에, 문자가 부분적인 크기가 문자 크기의 추정에 영향을 주는 것을 작게 하는 것이 가능해지고, 중첩 네스트 처리를 행하지 않은 경우에도, 문자 크기를 정밀도 좋게 추정하는 것이 가능해진다.

또한, 본 발명의 일 형태에 따르면, 테두리 중에 포함되어 있는 본문 문자의 갯수를 카운트함에 따라, 신문 등으로부터 헤드라인 문자를 추출하는 경우에, 헤드라인 문자의 근처에 본문 문자를 둘러싼 박스형이 존재하는 경우에도 이 박스형만을 추출하는 것이 가능해지고, 헤드라인 문자의 외접 구형과 구별하는 것이 가능해지기 때문에, 헤드라인 문자만을 정밀도 좋게 추출하는 것이 가능해진다.

또한, 본 발명의 일 형태에 따르면, 외접 구형에 부여된 구형 번호를 입력 화상에 설정된 각 좌표에 사영함으로써, 외접 구형 내에 존재하는 다른 외접 구형을 용이하게 추출하는 것이 가능해지고, 본문 문자를 둘러싼 박스형과 헤드라인 문자가 혼재하는 경우에도, 박스형만을 고속으로 추출하는 것이 가능해진다.

또한, 본 발명의 일 형태에 따르면, 중첩 네스트 통합을 부분적으로 행함에 따라, 중첩도가 큰 외접 구형만을 대상으로 중첩 네스트 처리를 행하고, 중첩도가 작은 외접 구형의 중첩 네스트 통합 처리를 행하지 않도록 하는 것이 가능해지기 때문에, 외접 구형이 화면 전체에서 통합되어, 헤드라인 문자의 외접 구형이 소실하는 것을 방지하는 것이 가능해짐과 동시에, 중첩도가 큰 도면이나 사진의 일부를 보다 큰 구형으로 흡수 통합해 두는 것이 가능해지고, 도면이나 사진의 일부의 외접 구형이 그대로 남고, 헤드라인 문자로서 잘못 추출되거나, 헤드라인 문자를 구성함으로써 잘못하여 구형 통합되거나 하는 것을 방지하는 것이 가능해지고, 헤드라인 문자와 도면이나 사진 등이 혼재하는 경우에도, 헤드라인 문자의 추출을 정밀도 좋게 행하는 것이 가능해진다.

또한, 본 발명의 일 형태에 따르면, 외접 구형에 부여된 구형 번호를 입력 화상에 설정된 각 좌표에 사영함으로써, 상호 중첩되는 외접 구형을 용이하게 추출하는 것이 가능해지고, 외접 구형의 중첩도를 고속으로 산출하는 것이 가능해진다.

Claims (14)

1. 화상으로부터 문자열을 추출하는 문자열 추출 장치에 있어서,

   입력한 화상으로부터 화소의 색에 기초하여, 화소의 색이 연속해 있는 연결 성분을 추출하는 연결 성분 추출 수단과,

   연결 성분의 상대적 위치, 및, 연결 성분의 굵기에 기초하여, 연결 성분을 공통의 문자열 또는 문자열군을 구성하는 가능성이 높은 그룹으로 나누는 그룹핑 수단과,

   그룹마다 문자 인식 처리를 행하고, 그 결과의 각 문자의 제1위 인식 후보의 거리치에 기초하여 그룹의 문자 인식도를 결정하는 문자 인식 수단과,

   그룹의 문자 인식도에 그룹이 차지하는 구형 영역의 면적에 의해 부가한 것을 그룹의 평가치로 하고, 모든 그룹의 조합에 대해 그룹의 평가치의 합을 조합의 평가치로 하는 조합 평가 수단과,

   조합의 평가치가 가장 높은 그룹의 조합을 문자열로서 추출하는 문자열 추출수단

   을 구비하는 것을 특징으로 하는 문자열 추출 장치.
2. 제1항에 있어서,

   상기 연결 성분의 굵기는, 상기 연결 성분의 전 화소수에 대한 경계 화소수의 비인 것을 특징으로 하는 문자열 추출 장치.
3. 제1항 또는 제2항에 있어서,

   입력한 화상이 흑백 2치 화상인 경우에는, 입력 화상과, 흑백 2치를 반전시킨 반전 화상에 대해, 흑화소가 연속해 있는 연결 성분을 추출하는 것을 특징으로 하는 문자열 추출 장치.
4. 제1항 또는 제2항에 있어서,

   그룹이 차지하는 구형 영역에 중첩이 없는 그룹만을 관련짓고, 그룹이 차지하는 구형 영역에 중첩이 없는 그룹의 조합을 전부 구하는 것을 특징으로 하는 문자열 추출 장치.
5. 입력 화상의 라벨을 반전한 반전 화상을 생성하는 반전 화상 생성 수단과,

   상기 입력 화상으로부터 추출된 패턴 및 상기 반전 화상으로부터 추출된 패턴의 인식 처리를 행하는 인식 수단과,

   상기 인식 결과 중, 상기 입력 화상으로부터 추출된 패턴의 영역과 상기 반전 화상으로부터 추출된 패턴의 영역과의 중첩이 없는 조합을 출력하는 출력 수단을 구비하는 것을 특징으로 하는 패턴 추출 장치.
6. 입력 화상의 연결 성분을 추출하는 연결 성분 추출 수단과,

   상기 연결 성분의 외접 구형을 생성하는 외접 구형 생성 수단과,

   상기 외접 구형의 빈도를 상기 외접 구형의 면적으로 웨이트한 막대 그래프를 생성하는 막대 그래프 생성 수단과,

   상기 막대 그래프의 최대치를 나타낸 외접 구형의 크기를, 상기 입력 화상의 문자 크기와 추정하는 문자 크기 추정 수단을 구비하는 것을 특징으로 하는 패턴 추출 장치.
7. 제6항에 있어서,

   상기 외접 구형 생성 수단으로 생성된 외접 구형의 그룹핑을 행하는 그룹핑 수단과,

   상기 문자 크기 추정 수단으로 추정된 문자 크기를 갖는 제1 외접 구형을 소정의 갯수 이상 포함하는 제2 외접 구형을 추출하는 박스형 추출 수단과,

   상기 제2 외접 구형을 상기 그룹핑의 대상으로부터 제외하는 박스형 제외 수단을 구비하는 것을 특징으로 하는 패턴 추출 장치.
8. 제7항에 있어서,

   상기 외접 구형에 부여된 구형 번호를 상기 입력 화상에 설정된 각 좌표에 사영하는 사영 수단을 구비하고,

   상기 박스형 추출 수단은, 상기 각 좌표에 포함되는 구형 번호를 상기 제2 외접 구형의 좌표의 범위 내에서 탐색함으로써, 제1 외접 구형을 추출하는 것을 특징으로 하는 패턴 추출 장치.
9. 입력 화상의 연결 성분을 추출하는 연결 성분 추출 수단과,

   상기 연결 성분의 외접 구형을 생성하는 외접 구형 생성 수단과,

   상기 외접 구형이 상호 중첩되어 있는 다른 외접 구형의 갯수를 산출하는 중첩도 평가 수단과,

   상기 중첩도 평가 수단의 산출 결과에 기초하여, 중첩 네스트 통합 처리를 행하는 중첩 네스트 통합 처리 수단을 구비하는 것을 특징으로 하는 패턴 추출 장치.
10. 제9항에 있어서,

    상기 외접 구형에 부여된 구형 번호를, 상기 입력 화상에 설정된 각 좌표에 사영하는 사영 수단과,

    상기 각 좌표에 포함되는 구형 번호를 소정의 외접 구형의 좌표의 범위 내에서 탐색함으로써, 상기 소정의 외접 구형에 중첩되어 있는 다른 외접 구형을 추출하는 중첩 구형 추출 수단을 구비하는 것을 특징으로 하는 패턴 추출 장치.
11. 입력 화상 및 상기 입력 화상의 흑백 반전 화상의 각각으로부터 얻어지는 패턴의 인식 결과 중, 상호 영역이 중첩하지 않은 부분을 조합시킨 것을, 상기 입력 화상으로부터의 패턴의 추출 결과로 하는 것을 특징으로 하는 패턴 추출 방법.
12. 입력 화상의 연결 성분의 외접 구형의 중첩도에 기초하여, 중첩 네스트 통합 처리를 부분적으로 행하는 것을 특징으로 하는 패턴 추출 방법.
13. 컴퓨터를,

    입력한 화상으로부터 화소의 색에 기초하여, 화소의 색이 연속해 있는 연결 성분을 추출하는 연결 성분 추출 수단과,

    연결 성분의 상대적 위치, 및 연결 성분의 굵기에 기초하여, 연결 성분을 공통의 문자열 또는 문자열군을 구성하는 가능성이 높은 그룹으로 나누는 그룹핑 수단과,

    그룹마다 문자 인식 처리를 행하고, 그 결과의 각 문자의 제1위 인식 후보의 거리치에 기초하여 그룹의 문자 인식도를 결정하는 문자 인식 수단과,

    그룹의 문자 인식도에 그룹이 차지하는 구형 영역의 면적에 의해서 웨이트한 것을 그룹의 평가치로 하고, 모든 그룹의 조합에 대해 그룹의 평가치의 합을 조합의 평가치로 하는 조합 평가 수단과,

    조합의 평가치가 가장 높은 그룹의 조합을 문자열로서 추출하는 문자열 추출수단을 구비하고, 화상으로부터 문자열을 추출하는 문자열 추출 장치로서 기능시키는 것을 특징으로 하는 프로그램을 기록한 컴퓨터 판독 가능한 기록 매체.
14. 입력 화상의 연결 성분을 추출하는 기능과,

    상기 연결 성분의 외접 구형을 생성하는 기능과,

    상기 외접 구형이 상호 중첩되어 있는 다른 외접 구형의 갯수를 산출하는 기능과,

    상기 산출된 갯수에 기초하여, 중첩 네스트 통합 처리를 행하는 기능을 컴퓨터에 실행시키는 프로그램을 저장한 컴퓨터 판독 가능한 기억 매체.