KR20030005342A - 화상에서의 객체 탐색 방법 - Google Patents

Abstract

본 발명에 따른, 화상에서 소정의 객체를 탐색하는 방법은 이 객체에 속하며 기지의 스트로크 폭을 갖는 라인을 선택하는 단계, 및 이 스트로크 폭을 포함하는 폭 범위(60)의 양단을 각각 정의하는 최대폭(56)과 최소폭(58)을 정의하는 단계를 포함한다. 상기 화상에서 상기 범위내에 속하는 특징부 폭을 갖는 특징부를 탐색하고, 그 특징부를 처리하여 그 특징부가 상기 객체의 일부분인지 여부를 판정한다.

Description

화상에서의 객체 탐색 방법{FINDING OBJECTS IN AN IMAGE}

많은 화상 처리 응용 분야에서는, 어떤 객체 또는 객체들이 주어진 화상에 존재하는지와, 존재하는 경우 그 화상의 어느 장소에 존재하는지를 탐색한다. 탐색할 객체들의 사전(dictionary)이 주어진다. 그렇지만, 화상에서의 객체들의 외관은 상기 사전에 있는 그들의 외관과 다를 수 있다. 객체들의 외관에 변화가 있는 이유로는 회전, 크기 변환(scaling), 노이즈, 비선형 왜곡, 객체 내부에서의 콘트라스트 변화와 객체와 배경 사이에서의 콘트라스트 변화, 그리고 약간의 토폴로지 변화(topological variation) 등을 들 수 있다. 실용적인 화상 처리 방법은 이러한 변화들이 존재하더라도 대형 화상에 걸쳐 특정 객체를 신속하게 탐색할 수 있어야만 한다.

당업계에 알려진, 화상에서 객체들을 탐색하는 대부분의 방법들에서는 대부분 패턴 정합(pattern matching) 기술이나 토폴로지 검색(topological search) 기술 중 어느 하나를 사용하고 있다. 이들 기술에서는, 기울기(gradient) 또는 경계부(edge)와 같은 원하는 특징부들을 강조시키기 위해, 먼저 화상을 선처리, 즉 필터링해야만 하는 것이 통상적이다. 패턴 정합은 전술한 여러가지 유형의 변화, 특히 비선형 변화에 민감하다. 토폴로지 검색 방법에서는 확대(dilation), 및 윤곽선(outline)과 뼈대(skeleton)의 탐색과 같은 연산을 필요로 하는 데, 이들 연산은 시간이 너무 많이 소요되므로 대형 화상의 고속 처리에는 계산상 비효율적이다.

객체를 검색하기에 앞서 그 화상을 이진화(binarization)시키면, 계산 시간을 줄일 수 있으며, 특히 그 화상이 데시메이션(decimation)까지 되어 있는 경우에 더욱 그렇다. 그렇지만, 이진화에 기반한 방법들은 콘트라스트 변화에 특히 민감하다. 이진화 방법 및 임계값의 선택에 따라, 화상에서의 객체들의 중요한 특징부들 또는 객체들과 배경간의 차이점들은 화상이 이진화될 때 사라져 버릴 수 있다. 화상 내에서의 밝기 및 콘트라스트의 변화로 인해, 화상의 서로 다른 부분에서 각기 다른 임계값이 필요하게 되는 경우가 자주 있다.

한가지 특히 매력적인 객체-탐색 응용 분야로는, 우편 소포의 자동 분류가 있다. 소포 분류 장비는 그 소포에 붙여져 있는 여러가지 마크 및 스티커를 인식하여 위치 확인을 할 수 있어야만 한다. 통상, 대형 화상의 전체 영역을 스캔하는 데 단지 아주 한정된 처리 시간만이 할당될 뿐이다. 화상은 소포 컨베이어 상부에 있는 카메라에 의해 캡처되기 때문에, 소포의 높이가 각기 달라서 크기에 많은 변화가 있을 수 있다. 소포 자체의 물리적인 변형이 소포에 붙여져 있는 스티커에 비선형 왜곡을 일으킨다. 게다가, 동일한 스티커지만 발행판이 다를 경우 그레이-스케일 콘트라스트, 스트로크 폭(stroke width), 글자체 및 특징부 토폴로지가 다를 수 있다.

본 발명은 일반적으로 화상 처리 방법 및 장치에 관한 것으로서, 구체적으로는 화상에서 객체(object)를 고속으로 탐색하는 방법에 관한 것이다.

도 1은 본 발명의 양호한 실시예에 따른 소포 분류 시스템의 개략적인 모식도이다.

도 2는 본 발명의 양호한 실시예에 따른 화상에서 객체를 식별하는 방법을 개략적으로 설명하는 플로우차트이다.

도 3은 본 발명의 양호한 실시예에 따른 도 2의 객체 식별 방법과 연계하여 특히 유용한, 화상에서 관심 영역들을 탐색하는 방법을 개략적으로 설명하는 플로우챠트이다.

도 4는 도 1의 시스템에서 캡처된 화상의 복사본으로서, 관심 영역들은 도 2 및 도 3의 방법들을 사용하여 식별된다.

도 5는 그레이-스케일 값을 도 4의 관심 영역들 중 하나를 통과하는 라인을 따라 있는 픽셀 위치의 함수로서 나타낸 그래프이다.

도 6은 본 발명의 양호한 실시예에 따라 도 5의 그레이-스케일 값으로부터 도출한 차분 함수를 나타낸 그래프이다.

도 7은 본 발명의 양호한 실시예에 따라 도 2의 객체 식별 방법과 연계하여 특히 유용한, 영역 확대 방법을 개략적으로 설명하는 플로우차트이다.

도 8은 본 발명의 양호한 실시예에 따라 도 2 및 도 7의 방법을 도 4의 화상에 적용함으로써 발생된 스테인들의 화상의 복사본을 나타낸 것이다.

본 발명의 목적은 화상에서 객체를 고속으로 탐색하는 방법 및 장치를 제공하는 데 있다.

본 발명의 어떤 특징들의 다른 목적은 초대형 화상에 대해서까지도 고속으로 동작하는, 화상에서 객체를 탐색하는 방법을 제공하는 데 있다.

본 발명의 어떤 특징들의 또다른 목적은 객체의 외관에 여러 변화들이 존재하는 경우까지도 안정되고 정확한, 화상에서 객체를 탐색하는 방법을 제공하는 데 있다.

본 발명의 어떤 특징들의 또다른 목적은 자동화된 소포 분류 응용 분야에 사용하기 적합한, 화상에서 객체를 탐색하는 방법을 제공하는 데 있다.

본 발명의 양호한 실시예들에서, 화상에서 탐색하려는 관심 객체는 그 객체를 구성하고 있는 라인들, 특히 그 라인들의 스트로크 폭에 의해 정의된다. (본 특허 출원 및 청구항들과 관련하여, 용어 "라인"이란 직선이든 곡선이든 관계없이 임의의 가늘고 긴 특징부를 의미하는 것으로 이해해야 한다.) 이들 라인이 화상에 보일 때, 이들 라인은 소정의 범위내에 있는 폭을 갖는 것으로 기대된다. 이 범위는 그 객체에 속하는 라인들의 기지의 스트로크 폭을 포함하지만, 변형, 크기 변환, 콘트라스트 변화 또는 다른 이유들로 인해 화상에 있는 실제 라인들의 폭에 일어날 수 있는 임의의 편차들을 고려하기 위해 확장된다. 객체들을 탐색하기 위해서, 이 범위내에 있는 폭을 갖는 모든 특징부들을 찾아서 화상을 신속하게 검색한다. 이 방법에 의하면, 화상에 있는 픽셀들의 작은 부분 집합만을 스캔한 것에 기초하여 관심 영역들의 작은 집합의 위치를 신속하게 알아낼 수 있고, 관심 객체가 이들 영역 중의 하나에서 발견될 가능성이 높은 것이 일반적이다.

본 발명의 어떤 양호한 실시예들에서는, 일련의 연속적인 단계들에서 관심 객체를 찾아서 그레이-스케일 화상을 검색한다. 각각의 단계에서는 검색 영역을 이전의 영역에 비해 좁혀가면서 탐색 중인 특정 객체에 가까와지게 된다. 제1 단계에서, 소정의 범위내에 있는 폭을 갖는 특징부들에 존재하는 것으로 보이는 픽셀의 클러스터들(clusters)을 탐색함으로써 관심 영역들의 위치를 알아낸다. 그 다음에, 관심 영역들을 스캔하여 콘트라스트 피크(contrast peak), 즉 그 영역들을 통과하는 선택된 스캔 라인들을 따라 일어나는 그레이-스케일의 급격한 변화를 탐색한다. 이러한 피크의 크기가 주어진 임계값을 넘고 또 그의 폭이 상기 범위내에 있는 경우, 그것은 관심 객체를 구성하고 있는 라인들 중 하나의 일부분이 될만한 후보가 된다. 이 후보 피크는 영역 확대 절차에서 형태 확장되어(morphologically expanded), "스테인(stain)" 즉 거의 동일한 그레이-스케일 값을 갖는 픽셀들의 연결 그룹(connected group)을 생성한다. 그 다음에, 당업계에 공지된 고도의 화상 인식 절차를 각각의 스테인에 적용하여, 어느 스테인 또는 스테인들이 관심 객체에 해당하는지를 판정한다. 이 마지막 단계는 객체 자체에 따라 달라지는 유일한 단계로서, 스테인들에 포함되어 있는 모든 픽셀들의 아주 작은 부분 집합에 대해서만 수행된다.

본 명세서에 기술된 방법들은 우편 소포상의 라벨, 심볼 및 스티커를 식별하는 데, 즉 고속 스캐닝 및 분류의 응용 분야에 사용하는 데 특히 적합하다. 그렇지만, 본 발명의 원리들은 또한 대형 화상에서 관심 객체의 위치를 신속하게 알아내면서도 그 화상에서의 변화 및 변형으로 인한 식별 오류를 피할 수 있는 광범위한 다른 상황에도 적용될 수 있다.

따라서, 본 발명의 양호한 실시예에 따르면, 화상에서 소정의 객체를 탐색하는 방법은,

상기 객체에 속하며, 기지의 스트로크 폭을 갖는 라인을 선택하는 단계,

상기 스트로크 폭을 포함하는 폭 범위의 양단을 각각 정의하는 최대폭과 최소폭을 정의하는 단계,

상기 화상에서 상기 범위내의 특징부 폭을 갖는 특징부를 탐색하는 단계, 및

상기 특징부가 상기 객체의 일부분인지 여부를 판정하기 위해, 상기 특징부를 처리하는 단계를 포함한다.

양호하게는, 상기 최대폭 및 최소 폭을 정의하는 단계는 상기 객체가 화상에 보일 때 그 객체 내의 라인의 폭에 일어날 수 있는 여러 변화들을 측정하는 단계를 포함한다.

양호한 실시예에서, 상기 화상에서 특징부를 탐색하는 단계는,

상기 화상에서 상기 최대폭보다 작은 폭을 갖는 하나 이상의 화상 요소들에 속하는 픽셀들의 제1 궤적을 탐색하는 단계,

상기 화상에서 상기 최소폭보다 작은 폭을 갖는 하나 이상의 화상 요소들에 속하는 픽셀들의 제2 궤적을 탐색하는 단계, 및

상기 제1 궤적과 상기 제2 궤적의 논리합(disjunction)을 구하는 단계를 포함한다.

양호하게는, 상기 제1 궤적을 탐색하는 단계는 상기 최대폭과 같은 거리만큼 그로부터 떨어져 있는 다른 픽셀들의 그레이-스케일값과 적어도 미리 정해진 콘트라스트 임계값만큼 차이가 있는 그레이-스케일값을 갖는 픽셀을 탐색하는 단계를 포함한다. 그 대신에 또는 그에 부가하여, 상기 화상에서 특징부를 탐색하는 단계는 상기 궤적들을 탐색하기 이전에 상기 화상을 서브샘플링하는 단계를 포함함으로써, 상기 화상내의 모든 픽셀들의 부분 집합에 대해서만 상기 궤적에 포함되는지 살펴보면 된다. 또한, 그 대신에 또는 그에 부가하여, 상기 화상에서 특징부를 탐색하는 단계는 상기 제1 궤적과 상기 제2 궤적의 논리합에 있는 픽셀들의 클러스터를 상기 화상에서의 관심 영역으로서 식별하는 단계를 포함하며, 상기 관심 영역이 상기 객체를 포함할만한 후보가 된다.

또하나의 양호한 실시예에서, 상기 화상에서 특징부를 탐색하는 단계는,

상기 화상에서 상기 객체를 포함할만한 후보인 관심 영역을 식별하는 단계,

상기 관심 영역을 통과하는 스캔 라인을 선택하는 단계, 및

상기 범위내의 거리만큼 서로 떨어져 있는 한 쌍의 콘트라스트 천이를 탐색하기 위해, 상기 스캔 라인을 따라 배치되어 있는 픽셀들의 그레이-스케일값을 평가하는 단계를 포함한다.

양호하게는, 상기 스캔 라인을 선택하는 단계는 복수의 스캔 라인을 선택하는 단계를 포함하며, 복수의 스캔 라인 사이의 간격은 상기 객체의 치수에 따라 결정된다. 그 대신에 또는 그에 부가하여, 상기 그레이-스케일값을 평가하는 단계는상기 스캔 라인 상의 선택된 한 쌍의 픽셀들의 각각의 그레이-스케일값 사이의 차, 즉 상기 콘트라스트 천이들 중 임의의 주어진 천이의 어느 한 쪽에서의 차가 미리 정해진 임계값을 초과하는 상기 콘트라스트 천이를 탐색하는 단계를 포함한다. 가장 양호하게는, 상기 한쌍의 픽셀은 상기 스트로크 폭의 함수로서 선택되는 거리만큼 서로 떨어져 있다.

양호하게는, 상기 특징부를 처리하는 단계는,

상기 특징부에 속하는 적어도 하나의 최초 픽셀의 궤적을 탐색하는 단계, 및

상기 객체에서의 라인을 재구성하기 위해, 상기 궤적을 확장하는 단계를 포함한다. 상기 궤적을 확장하는 단계는 상기 적어도 하나의 최초 픽셀에 인접하고 또 상기 적어도 하나의 최초 픽셀의 그레이-스케일값에 따라 설정된 임계값을 넘는 그레이-스케일값을 갖는 부가의 픽셀을 상기 궤적에 부가함으로써 행하는 것이 가장 바람직하다.

양호하게는, 상기 부가의 픽셀을 상기 궤적에 부가하는 단계는 제1 부가 픽셀을 부가하는 단계를 포함하며,

상기 궤적을 확장하는 단계는,

상기 궤적에서의 픽셀들에 인접하고 또 상기 임계값을 넘는 그레이-스케일값을 각각 갖는 추가의 부가 픽셀들을 계속하여 부가하는 단계, 및

상기 궤적이 상기 객체의 치수에 따라 결정된 최대 크기에 도달할 때, 상기 추가의 부가 픽셀들의 부가를 중단하는 단계를 더 포함한다.

또한, 양호하게는 상기 특징부를 처리하는 단계는 상기 궤적을 상기 객체에정합시키기 위해 상기 확장된 궤적을 처리하는 단계를 포함한다.

양호한 실시예에서, 상기 객체는 어떤 물품 상에 있는 하나 이상의 마킹을 포함하며, 그 마킹에 따라 상기 물품은 분류 시스템에 의해 분류되고, 상기 특징부를 처리하는 단계는 상기 마킹을 식별하는 단계, 및 상기 식별된 마킹에 따라 상기 물품을 분류하는 단계를 포함한다.

또한, 본 발명의 양호한 실시예에 따르면, 화상에서 미리 정해진 객체를 탐색하는 장치가 제공되며, 이 장치는 미리 정해진 최대폭과 최소폭 사이의 범위내에 있는 특징부 폭을 갖는 특징부를 화상에서 탐색하는 동작과, 상기 특징부를 처리하여 상기 특징부가 상기 객체의 일부분인지를 판정하는 동작을 하는 화상 처리기를 포함하며, 상기 범위는 상기 객체에 속하는 라인의 기지의 스트로크 폭이 상기 범위 내에 속하도록 정의된다.

양호하게는, 상기 장치는 상기 객체를 포함하는 화상을 캡처하여 이 화상의 전자적 표현을 상기 화상 처리기로 전달하도록 구성된 화상 캡처 장치를 포함한다. 양호한 실시예에서, 상기 객체는 어떤 물품 상에 있는 하나 이상의 마킹을 포함하며, 이 마킹에 따라 상기 물품은 분류되고, 상기 객체 탐색 장치는 상기 마킹을 판독하여 그 마킹에 따라 상기 물품을 분류하도록 구성되어 있다.

또한, 본 발명의 양호한 실시예에 따르면, 화상에서 미리 정해진 객체를 탐색하는 컴퓨터 소프트웨어 제품이 제공되며, 이 컴퓨터 소프트웨어 제품은 프로그램 명령어들이 저장되어 있는 컴퓨터 판독가능한 매체를 포함하며, 상기 프로그램 명령어들이 컴퓨터에 의해 판독될 때, 그 컴퓨터는 미리 정해진 최대폭과 최소폭사이의 범위내에 있는 특징부 폭을 갖는 특징부를 상기 화상에서 탐색하고, 또한 상기 특징부를 처리하여 상기 특징부가 상기 객체의 일부분인지를 판정하는 동작을 하게 되며, 상기 범위는 상기 객체에 속하는 라인의 기지의 스트로크 폭이 상기 범위 내에 속하도록 정의된다.

본 발명은 첨부된 도면과 함께 본 발명의 양호한 실시예들에 대한 이하의 상세한 설명으로부터 보다 완벽하게 이해될 것이다.

도 1은 본 발명의 양호한 실시예에 따른 소포 분류 시스템(20)을 개략적으로 나타낸 모식도이다. 라벨(24)이 붙어 있는 소포(22)는 컨베이어(26)에 의해 이송된다. 소포의 그레이-스케일 화상은 카메라(28), 양호하게는 라인 카메라(line camera)에 의하거나 또는 그 대신에 비디오 카메라나 디지털 스틸 카메라에 의해 캡처된다. 카메라에 의해 캡처된 화상은 디지털화되어 처리기(30)로 전달되고, 이 처리기는 이하에서 기술하는 방법들을 적용하여 소포(22)상에 있는 라벨(24) 및/또는 다른 특징부들을 식별한다. 그 대신에, 처리기는 화상을 어떤 다른 소스로부터 수신하거나, 또는 메모리(도시 생략)로부터 검색할 수도 있다. 식별된 라벨은 그 다음에 분류기(32)에 의해 자동적으로 판독되고, 분류기는 그에 따라 소포를 일정 경로로 보낸다.

처리기(30)는 양호하게는 적절한 소프트웨어를 사용하여 본 발명의 방법들을 수행하도록 프로그램된 범용 컴퓨터를 포함한다. 이 소프트웨어는 네트워크를 통해 프로세서로 다운로드되거나, 또는 그 대신에 CD-ROM과 같은 유형 매체상에 제공되어 프로세서에 설치될 수 있다. 이러한 소프트웨어는 다른 화상 처리 응용 분야에도 마찬가지로 적용될 수 있으며, 따라서 마찬가지 방식으로 다른 컴퓨터들에 제공되어 설치될 수 있다. 그 대신에, 본 명세서에 기술하는 방법들은 전용 하드웨어나 프로그램가능 디지털 신호 처리기를 사용하거나, 또는 전용 및/또는 프로그램가능 요소 및/또는 소프트웨어의 조합을 사용하여 구현되어도 좋다. 소포 분류 시스템(20)에 처리기(30)의 사용은 일례로서 본 명세서에 기술한 것에 불과하며, 어떤 한정하는 것은 아니다.

도 2는 본 발명의 양호한 실시예에 따른 화상에서 객체를 탐색하는 방법을 개략적으로 설명하는 플로우차트이다. 이 방법은 특히 소포(22)상의 라벨(24)과 같은 객체들을 탐색하는 데 적용할 수 있다. 간결함을 위해, 이하에서는 화상에서 한개의 객체를 탐색하는 방법에 대해 기술하고 있지만, 이 방법은 다수의 객체들을 동시에 또는 순차적으로 탐색하는 방법으로 용이하게 확장될 수 있다.

커널(kernel) 탐색 단계(40)에서는, 전체 화상에서 픽셀들의 작은 부분 집합을 스캔하여, 소정의 범위내의 폭을 갖는 화상 특징부 상에 존재하는 픽셀들을 탐색한다. 이 목적으로 선택된 범위는 탐색할 객체에 있는 실제 라인들의 폭에 따라 달라진다. 이러한 픽셀들을 커널이라고 한다. 클러스터링(clustering) 단계(42)에서는, 당업계에 공지되어 있는 임의의 적당한 클러스터링 알고리즘을 사용하여 커널들을 클러스터로 그룹화한다. 예를 들어, 화상은 여러개의 타일들(tiles)로 분할될 수 있다. 각각의 타일에서 커널의 수를 카운트하여, 주어진 임계값을 넘는 커널 수를 갖는 타일들은 관심 영역(region of interest, ROI)에 속하는 것으로 식별한다.

도 3은 본 발명의 양호한 실시예에 따른 커널 탐색 단계(40)의 세부를 개략적으로 설명하는 플로우차트이다. 데시메이션 단계(54)에서, 원래의 화상은 수평 방향 및 수직 방향 모두에서 비율 D로 데시메이션되며, 따라서 (nD, mD)(여기서, m, n은 정수임)로 주어지는 (x, y) 좌표를 갖는 픽셀들만을 포함하는 서브샘플링된 화상(sub-sampled image)이 생성된다. 따라서, 이 단계에서 스캔되는 픽셀의 수는 원래의 화상에 비해 D²배만큼 감소된다.

화상에서 찾고 있는 객체에 대해, 어떤 스트로크 폭의 범위는 화상에서 그 객체를 구성하고 있는 라인들이 이 범위내의 스트로크 폭을 가질 확률이 아주 높도록 정의된다. 이 범위의 경계는 최대폭(w₁)과 최소폭(w₂)에 의해 정해진다. 최대폭 검사 단계(56)에서는, 데이메이션된 화상에서 픽셀들의 그레이-스케일값[P(x, y)]을 평가하여, 그 값들이 이하의 복합 조건을 만족하는지 여부를 판정한다.

이들 식에서, T는 그레이-레벨 임계값이고, t는 콘트라스트 임계값이며, 이들 모두는 화상 및 관심 객체의 특성에 기초하여 결정된다. 파라미터 d₁은이다. 부등식 P(x,y) < T은 픽셀의 그레이-스케일 값이 임계값 T보다 더 어두운지 여부를 판정한다. 나머지 부등식들은 픽셀 (x,y)과 이 픽셀을 중심으로 직경 w₁인 원의 서로 마주하는 측에 있는 2 점간의 그레이-스케일 콘트라스트가 t보다 큰지 여부를 판정한다. 픽셀 (x,y)은 데시메이션된 화상에서 선택한 것이지만, 원 상의 점들은 원래의 데이메이션되지 않은 화상에서 선택해도 된다.

상기 조건을 만족하는 픽셀들에는 단계(56)에서 "ON" 표시를 해두어, 그 픽셀들이 최대 스트로크 폭 w₁보다 작은 폭의 라인 상에 존재할 수도 있다는 것을 나타낸다. 최소 폭 검사 단계(58)에서는, 단계(56)에서 "ON" 표시가 된 픽셀들에 대해 동일한 절차를 반복하지만, 이 때에는 최소 스트로크 폭 W₂(및 대응하는 파라미터 d₂)을 사용한다. 따라서, 이 단계에서는, 최소 스트로크 폭보다 작은 폭의 라인 상에 존재할 수 있는 픽셀들에 "ON" 표시를 해둔다. XOR 단계(60)에서는, 단계(56, 58)에서 "ON" 표시가 된 픽셀들의 논리합(disjunction)(배타적 OR)을 구한다. 이 논리합은 최대 스트로크 폭과 최소 스트로크 폭 사이의 폭을 갖는 라인들 상에 존재할 수 있는 픽셀들의 리스트를 반환(return)한다. 이 리스트는 ROI를 탐색하기 위해 단계(42)에 입력된다.

본 발명의 양수인에게 양도된 미국 특허 출원 제09/310,287호에서는 도 3의 단계(56)에서 수행되는 것과 유사한 알고리즘에 대해 기술하고 있으며, 이 미국 출원은 여기에 인용함으로써 그 개시 내용이 본 명세서에 포함된다. 상기 미국 출원에서는, 텍스트 픽셀들을 탐색하기 위해, 즉 광학적 문자 인식 수행의 준비 단계로서 그 화상을 최적으로 이진화하기 위해, 화상에서 소정의 최대값보다 작은 폭을 갖는 라인들이 식별된다. 그렇지만, 상기 미국 출원에서는 더 작은 최소폭 이하의 폭을 갖는 라인들을 제거하는 것에 대해서는 전혀 개시하고 있지 않다.

도 4는 시스템(20)에서 캡처된 소포(22)의 화상의 복사본으로서, 본 발명의 양호한 실시예에 따라 단계(42)에서 탐색한 ROI(66, 68)를 나타내고 있다. 이 예에서는, 화상에서 찾고 있는 객체가 삼각형의 우편 스티커(64)로서, ROI(66) 안에 들어 있다. 단계(40)에서 사용된 최대폭 및 최소폭은 그 삼각형의 변을 이루는 흑색 경계선들의 폭에 기초하여 정의된다. 이 단계에서 탐색된 다른 ROI(68)도 스티커(64)의 경계선 정도의 폭을 갖는 라인들을 포함하고 있다.

이제, 도 2로 돌아가, 콘트라스트 피크 추출 단계(44)에서는, ROI를 통과하는 일단의 선택된 스캔 라인들을 따라가면서 각각의 ROI에서의 그레이-스케일값들을 스캔한다. 스캔 라인들은 수평선, 수직선 또는 대각선일 수 있다. ROI당 하나의 스캔 라인으로 충분할 수 있지만, 그 검색이 보다 안정되도록 ROI당 2개 또는 3개의 스캔 라인을 사용하는 것이 바람직하다. 스캔 라인들 간의 상대적 방향 및 간격은 찾고 있는 객체의 크기 및 형상에 기초하여 선택되는 것이 가장 바람직하다. 어느 경우든, 스캔 라인들은 ROI내의 모든 픽셀들 중 아주 조금만 포함하고 있을 뿐이다.

도 5는 ROI(66)를 통과하는 스캔 라인들 중 하나를 따라가면서 그레이-스케일값 f(x)를 나타낸 그래프이다. 이 도면 및 이하의 설명에서, 그레이-스케일값은 반전되어 있으며, 따라서 255는 흑색을 나타내고 0은 백색을 나타낸다. 그래프에서 피크들은 콘트라스트 변화가 심한 것을 나타내는 것으로서, 이러한 콘트라스트 변화는 그 중에서도 특히 스캔 라인이 삼각형 스티커(64)의 어두운 경계선들 중 하나를 가로지르는 영역들에서 보게 된다. 이들 피크의 폭 및 크기를 평가하기 위해, 이하와 같은 차분 함수 d(x)가 정의된다.

d(x) = f(x) - f(x-L)

여기서, L은 찾고 있는 객체에 있는 라인의 예상되는 스트로크 폭의 절반을 나타낸다.

도 6은 도 5의 픽셀값 f(x)로부터 도출된 차분 함수 d(x)를 나타낸 그래프이다. 화상에서 콘트라스트 피크(CP)는 피크(74, 76)와 같은 d(x)에서의 플러스(+) 피크와 마이너스(-) 피크의 쌍(doublet)이 나타나는 것으로 정의된다. CP의 자격을 갖추기 위해서는, 플러스 피크와 마이너스 피크의 진폭이 그 각각의 소정의 임계값을 넘어서야 하며, 이들 피크간의 이격 거리가 그 객체의 라인들에 대한 소정의 최대 및 최소 폭 한계 내에 있어야만 한다. 이 이격 거리 조건에 기초하여, 피크들(74, 76)은 하나의 CP를 나타낼 수 있고, 피크들(78, 80)은 또다른 CP를 나타낼 수 있지만, 피크들(82, 84)은 너무 멀리 떨어져 있어 CP를 나타내지 못하며 따라서 폐기된다.

진폭 임계값에 관하여는, 피크들(76, 78)은 피크들(74, 78)보다 비교적 약하다는 것을 알 수 있다. 피크들(76, 78)은 스티커(64)에서 삼각형의 경계선들과 그삼각형 내부의 진한 회색 영역간의 천이를 나타낸다. 이들 천이는 경계선들과 삼각형 외부의 연한 회색 영역간의 천이, 즉 피크들(74, 80)로 나타낸 천이보다 콘트라스트가 더 낮은 것이 특징이다. 이러한 차이를 처리하기 위해, 내측 피크들(76, 78)에 적용된 임계값이 외측 피크들(74, 80)에 대한 임계값보다 낮은 값으로 설정되는 것이 바람직하다. 찾고 있는 객체에 대한 예비 지식에 기초한 이들 임계값에 의해 표현된 콘트라스트 특성은 화상에서 그 객체의 방향과는 아무런 관계가 없으며 또 스캔 라인이 좌측에서 우측으로 또는 우측에서 좌측으로 분석되든지간에 아무런 관계가 없다. 콘트라스트 조건 및 피크 이격 거리 조건을 만족하는 임의의 CP에 대해서는 단계(44)에서 후보 CP로서 표시를 한다. CP의 위치는 그에 대응하는 플러스 및 마이너스 피크의 쌍의 중앙에 있는 픽셀로서 표시된다.

반경 검사 단계(46)에서는, 단계(44)에서 탐색된 CP들 각각에 대해 반경을 계산한다. 이 반경은 CP와 이에 가장 가까운 "백색" 픽셀간의 거리로서 정의된다. 이러한 목적의 백색 픽셀은 CP의 중앙에 있는 픽셀의 그레이-스케일값보다 소정의 임계값 이상만큼 더 연한 그레이-스케일 값을 갖는 픽셀로서 정의된다. 단계(44)에서는 콘트라스트가 스캔 라인을 따라서만 측정되었지만, 단계(46)에서는 CP 중앙 픽셀을 중심으로 모든 방향에서 콘트라스트가 측정된다. 중앙 픽셀에서 그에 가장 가까운 백색 픽셀까지의 거리가 폭 범위의 소정의 한계보다 작거나 또는 큰 경우, 대응하는 CP는 폐기된다. 반경 조건을 만족하는 CP만이 스테인 형성 단계(48)로 보내지며, 이 단계에서는 이들 CP에 확장 연산을 수행하여 ROI내의 객체들을 재구성한다.

도 7은 본 발명의 양호한 실시예에 따른 스테인 형성 단계(48)의 세부를 개략적으로 설명하는 플로우차트이다. 씨드(seed) 선택 단계(90)에서는, ROI 각각에 대해, ROI에서 탐색된 CP들 중 하나를 선택하여 스테인으로 확장하기 위한 씨드로서 사용한다. 콘트라스트 임계값도 이 시점에 선택되고, 이 값을 적용하여 ROI내의 다른 어떤 픽셀들을 스테인에 속하는 픽셀들의 리스트에 부가해야하는지를 결정하며, 이에 대해서는 이하에서 기술한다. 임계값은 씨드의 그레이-스케일 값에 기초하여 예를 들면 씨드 그레이-스케일 값(흑색 = 255임)의 미리 정해진 몇분의 1로서, 또는 화상에서 씨드와 그 근처의 배경 픽셀들간의 콘트라스트의 함수로서 선택하는 것이 바람직하다. 이와 같이 하여, 후속하는 스테인 확장 단계들은 화상의 여러 부분에서 일어날 수 있는 콘트라스트 및/또는 밝기 변화에 적응한다. ROI내에 다수의 CP가 있는 경우, 씨드로서 맨처음 가장 밝은 CP를 선택하는 것이 가장 바람직하다. 비교적 낮은 임계값이 이러한 밝은 CP에 대해 선정되면 ROI내의 보다 어두운 CP들도 동일 스테인에 속하는 것으로 선택된다.

스테인의 확장을 시작하기 위해, 포인터는 스테인에서 픽셀들의 리스트에 있는 제1 픽셀, 즉 씨드 자신(이 시점에서 리스트에 있는 유일한 픽셀)을 가리키도록 초기화된다. 이웃 픽셀(neighbor) 검사 단계(92)에서는, 포인터가 현재 나타내고 있는 픽셀의 이웃 픽셀들 모두를 검사한다. 픽셀 검사 단계(94)에서는, 이웃 픽셀들 각각에 대해 우선 이 이웃 픽셀이 스테인에 포함시키기에 적당한 것인지에 대해 이미 판단해보았는지 여부를 판정한다. 그렇지 않은 경우, 그레이-스케일 검사 단계(96)에서 이웃 픽셀의 그레이-스케일 값을 검사하여 그 이웃 픽셀이 단계(90)에서 결정된 임계값보다 더 어두운지 여부를 판정한다. 그러한 경우, 픽셀 부가 단계(98)에서 그 픽셀은 스테인 내의 픽셀들의 리스트에 부가된다. 이웃 픽셀 완료 단계(100)에서는, 검사할 씨드의 이웃 픽셀들이 더 있는지 여부를 판정하고, 더 있는 경우, 그 다음 이웃 픽셀 단계(101)에서 그 다음 이웃 픽셀을 선택한다. 단계(94) 내지 단계(101)는 포인터가 현재 나타내고 있는 픽셀의 이웃 픽셀들 모두가 검사될 때까지 반복된다.

현재 픽셀의 이웃 픽셀들 모두가 검사되었으면, 리스트 검사 단계(102)에서 스테인 내의 픽셀들의 현재 리스트를 조사하여, 그 리스트에 검사되지 않은 이웃 픽셀을 갖는 픽셀들이 더 있는지 여부를 판정한다. 그 리스트에 픽셀들이 더 있는 경우, 스테인이 아직도 소정의 크기 한계를 초과하지 않았다는 것을 확인하기 위해 크기 모니터링 단계(104)에서 스테인의 현재 크기를 검사한다. 이 한계는 화상에서 찾고 있는 객체의 크기에 의해 주어진다. 그 객체에 대응될 수 없는 스테인에 처리 시간을 허비하는 것을 피하기 위해, 스테인 확장은 스테인의 크기가 크기 한계를 초과하면 종료된다. 그렇지만, 크기 한계가 초과되지 않는 한, 그 다음 픽셀 단계(106)에서 포인터는 그 리스트의 다음 픽셀로 증분되고, 이상의 단계들이 반복된다.

단계(102)에서 프로세스가 리스트의 최하단에 도달하였다는 것을 알게 되면, CP 검사 단계(108)에서는 현재의 ROI에 남아 있는 CP를 검사하여, 기존의 리스트에 포함되지 않은 것이 있는지 여부를 판정한다. 있는 경우, 단계(90)에서 이들 CP 중 하나가 새로운 씨드로서 선택되고, 전체 프로세스가 반복된다. 양호하게는, 화상에서 각기 다른 다수의 객체들을 동시에 찾고 있는 경우, 객체들 중 가장 큰 것에 대응될 수 있는 CP가 먼저 확장된다. 이들 CP는 단계(104)에서 더 큰 크기 한계를 가질 것이며, 그 결과 얻어지는 큰 스테인은 보다 작은 객체들에 대응되는 것으로 생각되는 CP를 확장하여 생성되는 보다 작은 스테인들을 포섭할 수 있게 됨으로써 ROI를 마무리하는 데 걸리는 총 처리 시간을 감축시키게 된다.

도 8은 도 4의 화상에서 식별된 ROI(66, 68)에 단계(44, 46, 48)(도 2)를 적용하여 생성된 스테인들의 이진 화상의 복사본이다. 이들 스테인을 생성하기 위해, 먼저 단계(44)에서 삼각형(64)의 높이의 절반만큼 간격을 두고 있는 스캔 라인들을 사용하여 ROI에서 콘트라스트 피크를 탐색하였다. 삼각형의 어두운 경계선들은 대응하는 스테인에서 분명하게 식별된다. 삼각형 경계선들의 폭과 유사한 폭을 갖는 라인들을 마침 포함하고 있는 기타 스테인(110, 112)도 생성된다.

마지막으로, 도 2에 도시되어 있는 객체 인식 단계(50)에서, 스테인 화상들을 분석하여, 관심 객체 및 전체 화상에서의 그 객체의 위치를 식별한다. 당업계에 공지되어 있는 여러가지 화상 인식 알고리즘들이 이 단계에서 적용될 수 있으며, 이 때 이진 스테인 화상만을 사용하거나 또는 원래의 화상에서의 대응하는 그레이-스케일 정보를 사용하거나 한다. 이 단계에서 알고리즘의 최적의 선택은 객체의 구체적인 특성에 따라 다르며, 이는 본 발명의 범위를 벗어나는 것이다. 그렇지만, 전체 화상에 걸쳐 객체 인식 알고리즘을 적용해야만 하는 당업계에 공지된 화상 처리 방법들에 비해, 이러한 알고리즘을 수행하는데 걸리는 시간이 실질적으로 감축되고, 또 객체 식별의 신뢰성이 실질적으로 향상된다는 것은 명백하다.

이상에서 설명한 양호한 실시예는 어떤 유형의 그레이-스케일 화상의 처리에 관한 것이지만, 본 발명의 원리들은 컬러 화상을 포함한 거의 모든 유형의 화상을 처리하는 데 용이하게 적용 실시될 수 있다는 것을 이해할 것이다. 따라서, 이상에서 설명한 양호한 실시예들은 단지 일례로서 인용한 것 일뿐이며, 본 발명은 본 명세서에서 특별히 도시하고 설명한 것에 한정되지 않는다는 것도 잘 알 것이다. 오히려, 본 발명의 범위는 이상에 설명한 여러가지 특징들의 컴비네이션(combination) 및 서브컴비네이션(subcombination) 모두를 포함함은 물론, 이상의 설명을 살펴봄으로써 당업자가 안출할 수 있는 것으로서 종래 기술에서 개시되지 않은 변형예 및 수정예도 포함한다.

Claims (19)

1. 화상에서 소정의 객체를 탐색하는 방법으로서,

   상기 객체에 속하며, 기지의 스트로크 폭을 갖는 라인을 선택하는 단계,

   상기 스트로크 폭을 포함하는 폭 범위의 양단을 각각 정의하는 최대폭과 최소폭을 정의하는 단계,

   상기 화상에서 상기 범위내의 특징부 폭을 갖는 특징부를 탐색하는 단계, 및

   상기 특징부가 상기 객체의 일부분인지 여부를 판정하기 위해, 상기 특징부를 처리하는 단계를 포함하는 화상에서의 객체 탐색 방법.
2. 제1항에 있어서, 상기 최대폭 및 최소폭을 정의하는 단계는 상기 객체가 화상에 보일 때 그 객체내의 라인의 폭에 일어날 수 있는 여러 변화들을 측정하는 단계를 포함하는 것인 화상에서의 객체 탐색 방법.
3. 제1항에 있어서, 상기 화상에서 특징부를 탐색하는 단계는,

   상기 화상에서 상기 최대폭보다 작은 폭을 갖는 하나 이상의 화상 요소들에 속하는 픽셀들의 제1 궤적을 탐색하는 단계,

   상기 화상에서 상기 최소폭보다 작은 폭을 갖는 하나 이상의 화상 요소들에 속하는 픽셀들의 제2 궤적을 탐색하는 단계, 및

   상기 제1 궤적과 상기 제2 궤적의 논리합(disjunction)을 구하는 단계를 포함하는 것인 화상에서의 객체 탐색 방법.
4. 제3항에 있어서, 상기 제1 궤적을 탐색하는 단계는 상기 최대폭과 같은 거리만큼 그로부터 떨어져 있는 다른 픽셀들의 그레이-스케일값과 적어도 미리 정해진 콘트라스트 임계값만큼 차이가 있는 그레이-스케일값을 갖는 픽셀을 탐색하는 단계를 포함하는 것인 화상에서의 객체 탐색 방법.
5. 제3항에 있어서, 상기 화상에서 특징부를 탐색하는 단계는 상기 궤적들을 탐색하기 이전에 상기 화상을 서브샘플링하는 단계를 포함함으로써, 상기 화상내의 모든 픽셀들의 부분 집합에 대해서만 상기 궤적에 포함되는지 살펴보면 되는 것인 화상에서의 객체 탐색 방법.
6. 제3항에 있어서, 상기 화상에서 특징부를 탐색하는 단계는 상기 제1 궤적과 상기 제2 궤적의 논리합에 있는 픽셀들의 클러스터를 상기 화상에서의 관심 영역으로서 식별하는 단계를 포함하며, 상기 관심 영역이 상기 객체를 포함할만한 후보인 것인 화상에서의 객체 탐색 방법.
7. 제1항에 있어서, 상기 화상에서 특징부를 탐색하는 단계는,

   상기 화상에서 상기 객체를 포함할만한 후보인 관심 영역을 식별하는 단계,

   상기 관심 영역을 통과하는 스캔 라인을 선택하는 단계, 및

   상기 범위내의 거리만큼 서로 떨어져 있는 한 쌍의 콘트라스트 천이를 탐색하기 위해, 상기 스캔 라인을 따라 배치되어 있는 픽셀들의 그레이-스케일값을 평가하는 단계를 포함하는 것인 화상에서의 객체 탐색 방법.
8. 제7항에 있어서, 상기 스캔 라인을 선택하는 단계는 복수의 스캔 라인을 선택하는 단계를 포함하며, 복수의 스캔 라인 사이의 간격은 상기 객체의 치수에 따라 결정되는 것인 화상에서의 객체 탐색 방법.
9. 제7항에 있어서, 상기 그레이-스케일값을 평가하는 단계는 상기 스캔 라인 상의 선택된 한 쌍의 픽셀들의 각각의 그레이-스케일값 사이의 차, 즉 상기 콘트라스트 천이들 중 임의의 주어진 천이의 어느 한 쪽에서의 차가 미리 정해진 임계값을 초과하는 상기 콘트라스트 천이를 탐색하는 단계를 포함하는 것인 화상에서의 객체 탐색 방법.
10. 제9항에 있어서, 상기 한쌍의 픽셀은 상기 스트로크 폭의 함수로서 선택되는 거리만큼 서로 떨어져 있는 것인 화상에서의 객체 탐색 방법.
11. 제1항에 있어서, 상기 특징부를 처리하는 단계는,

    상기 특징부에 속하는 적어도 하나의 최초 픽셀의 궤적을 탐색하는 단계, 및

    상기 객체에서의 라인을 재구성하기 위해, 상기 궤적을 확장하는 단계를 포함하는 것인 화상에서의 객체 탐색 방법.
12. 제11항에 있어서, 상기 궤적을 확장하는 단계는 상기 적어도 하나의 최초 픽셀에 인접하고 또 상기 적어도 하나의 최초 픽셀의 그레이-스케일값에 따라 설정된 임계값을 넘는 그레이-스케일값을 갖는 부가의 픽셀을 상기 궤적에 부가하는 단계를 포함하는 것인 화상에서의 객체 탐색 방법.
13. 제12항에 있어서, 상기 부가의 픽셀을 상기 궤적에 부가하는 단계는 제1 부가 픽셀을 부가하는 단계를 포함하며,

    상기 궤적을 확장하는 단계는,

    상기 궤적에서의 픽셀들에 인접하고 또 상기 임계값을 넘는 그레이-스케일값을 각각 갖는 추가의 부가 픽셀들을 계속하여 부가하는 단계, 및

    상기 궤적이 상기 객체의 치수에 따라 결정된 최대 크기에 도달할 때, 상기 추가의 부가 픽셀들의 부가를 중단하는 단계를 더 포함하는 것인 화상에서의 객체 탐색 방법.
14. 제11항에 있어서, 상기 특징부를 처리하는 단계는 상기 궤적을 상기 객체에 정합시키기 위해 상기 확장된 궤적을 처리하는 단계를 포함하는 것인 화상에서의 객체 탐색 방법.
15. 제1항에 있어서, 상기 객체는 어떤 물품 상에 있는 하나 이상의 마킹을 포함하며, 그 마킹에 따라 상기 물품은 분류 시스템에 의해 분류되고,

    상기 특징부를 처리하는 단계는 상기 마킹을 식별하는 단계, 및 상기 식별된 마킹에 따라 상기 물품을 분류하는 단계를 포함하는 것인 화상에서의 객체 탐색 방법.
16. 화상에서 미리 정해진 객체를 탐색하는 장치로서,

    미리 정해진 최대폭과 최소폭 사이의 범위내에 있는 특징부 폭을 갖는 특징부를 화상에서 탐색하는 동작과, 상기 특징부를 처리하여 상기 특징부가 상기 객체의 일부분인지를 판정하는 동작을 하는 화상 처리기를 포함하며,

    상기 범위는 상기 객체에 속하는 라인의 기지의 스트로크 폭이 상기 범위 내에 속하도록 정의되는 것인 화상에서의 객체 탐색 장치.
17. 제16항에 있어서, 상기 객체를 포함하는 화상을 캡처하여 이 화상의 전자적 표현을 상기 화상 처리기로 전달하도록 구성된 화상 캡처 장치를 포함하는 화상에서의 객체 탐색 장치.
18. 제17항에 있어서, 상기 객체는 어떤 물품 상에 있는 하나 이상의 마킹을 포함하며, 이 마킹에 따라 상기 물품은 분류되고,

    상기 객체 탐색 장치는 상기 마킹을 판독하여 그 마킹에 따라 상기 물품을분류하도록 구성되어 있는 것인 화상에서의 객체 탐색 장치.
19. 화상에서 미리 정해진 객체를 탐색하는 컴퓨터 소프트웨어 제품으로서,

    프로그램 명령어들이 저장되어 있는 컴퓨터 판독가능한 매체를 포함하며,

    상기 프로그램 명령어들이 컴퓨터에 의해 판독될 때, 그 컴퓨터는 미리 정해진 최대폭과 최소폭 사이의 범위내에 있는 특징부 폭을 갖는 특징부를 상기 화상에서 탐색하고, 또한 상기 특징부를 처리하여 상기 특징부가 상기 객체의 일부분인지를 판정하는 동작을 하게 되며,

    상기 범위는 상기 객체에 속하는 라인의 기지의 스트로크 폭이 상기 범위 내에 속하도록 정의되는 것인 컴퓨터 소프트웨어 제품.