KR100545477B1

KR100545477B1 - 거리 측정기를 사용한 이미지 검색법

Info

Publication number: KR100545477B1
Application number: KR1020037012332A
Authority: KR
Inventors: 아카리아틴쿠; 바타카리아바르가브; 쿤두말라이; 머르씨씨.; 비시누아리지트
Original assignee: 인텔 코오퍼레이션
Priority date: 2001-03-23
Filing date: 2002-01-25
Publication date: 2006-01-24
Anticipated expiration: 2022-01-25
Also published as: EP1370983A2; KR20040005895A; DE60221109D1; WO2002077870A3; CN1267840C; CN1498381A; TWI223779B; WO2002077870A2; JP2004532458A; HK1060634A1; US6681060B2; EP1370983B1; JP4388095B2; DE60221109T2; JP2007249981A; US20020164075A1; ATE366963T1

Abstract

마할라노비스 거리 측정기는 데이터베이스내의 복수의 이미지 사이에서 문의 이미지를 식별하는데 사용된다. 측정기는 문의 이미지와 하나 이상의 이미지의 유사성의 순위를 매기는데 사용될 수 있다. 분산-공분산 행렬은 데이터베이스내의 모든 이미지에 대하여 계산된다. 분산-공분산 행렬은 데이터베이스내의 하나 이상의 이미지와 문의 이미지 사이의 마할라노비스 거리를 계산하는데 사용된다. 범위 트리는 마할라노비스 거리 측정을 수행하기 위해 유망한 이미지 후보자를 식별하는데 사용될 수 있다.

이미지, 마할라노비스, 특징, 벡터, 행렬, 트리, 명령어

Description

거리 측정기를 사용한 이미지 검색법{IMAGE RETRIEVAL USING DISTANCE MEASURE}

본원발명은 이미지 프로세싱에 관한 것이고, 더 구체적으로는 이미지의 특성화에 관한 것이다.

이미지 프로세싱이란 컴퓨터를 사용하여 이미지를 분석하고 조작하는 것을 말한다. 이러한 분야는 예를 들어 이미지 전송 및 이미지 구성 등 패턴 인식 및 다른 이미지 분석, 압축 및 인코딩을 포함하는 많은 기술을 포함한다. 이미지 프로세싱은 천문학, 의학, 군사작전, 통신, 지질학, 기상학 등과 같은 다양한 분야에서 사용된다.

이미지는, 우리 눈에는 보이더라도, 컴퓨터 또는 다른 프로세서-기반 시스템도 이미지를 "볼 수" 있거나, 예를 들어, 이미지를 다른 이미지와 분간할 수 있도록 특성화될 수 있다. 모멘트, 엔트로피, 질량중심, 오리엔테이션, 또는 다른 히스토그램-기반 특징을 식별하는 것은 이미지 특성화에 대한 하나의 방법이다. 이미지의 구조적 및 구문적 특징은 특성 파라미터로서 역할할 수 있다. 둘레, 면적, 이심률, 또는 오일러 수 등과 같은 기하학적 표시는 수치적으로 이미지를 식별할 수 있다.

이미지는, 예를 들어 전송동안, 섭동되기도 하기 때문에, 이미지의 특성 파라미터는 변환 후에 불변인 것이 이상적이다. 이미지 변환은 번역, 회전, 스케일링, 전단, 압축, 잡음의 포함 등을 포함할 수 있다.

특히, 최신 분야인 인터넷 기술에 있어서, 이미지 탐색은 중요한 툴일 수 있다. 그러나, 이미지 탐색에 사용되는, 이미지의 다른 특성은 매우 변화하는 결과를 가질 수 있다. 이미지 탐색의 이러한 타입은 콘텐트-기반 이미지 검색으로 알려져 있다.

이미지의 데이터베이스로부터 이미지를 검색하는 하나의 기술은 각각의 이미지를 특정 수의 특징과 연관시키는 것이다. 특징벡터를 사용하여, 그 특징값에 의하여 표현되는 각각의 이미지는 식별된 n개의 특징이 존재하는 n차원 특징공간의 일포인트로 맵핑된다. 그때 유사성 문의는 문의 이미지에 근접한 이웃에 있는 이미지를 검색하는데 사용된다.

이들 유사성 문의를 실행함에 있어서, 이미지를 획득하는 정밀도는 유사성 문의에 포함된 다양한 특징을 계산하기 위한 시간 및 이미지 데이터베이스의 사이즈에 의해 오프셋팅될 수 있다.

따라서, 이미지 검색 방법을 최적화하기 위한 요구가 계속되고 있다.

도 1은 본원발명의 일실시예에 따른 2진 이미지의 블록선도,

도 2는 본원발명의 일실시예에 따른 4- 및 8-이웃의 블록선도,

도 3은 본원발명의 일실시예에 따른 그레이-톤 이미지의 블록선도,

도 4A 내지 도 4D는 본원발명의 일실시예에 따른 도 3의 그레이-톤 이미지의 2진 이미지,

도 5A 내지 도 5D는 본원발명의 일실시예에 따른 도 3의 그레이-톤 이미지의 리플렉팅된 그레이 코드 표현,

도 6은 본원발명의 일실시예에 따른 시스템의 블록선도,

도 7은 본원발명의 일실시예에 따른 도 6의 시스템의 복수의 이미지에 대하여 분산-공분산 행렬을 계산하는 순서도, 및

도 8은 본원발명의 일실시예에 따른 도 6의 시스템의 복수의 이미지와 문의 이미지 사이의 마할라노비스 거리를 계산하는 순서도.

오일러(Euler) 수

이미지의 데이터베이스로부터 이미지를 검색하기 위해서, 각각의 이미지는 다른 이미지와 분간되도록 특성화될 수 있다. 예를 들어, 이미지는 수치적으로 특성화될 수 있다.

예를 들어, 2진 이미지의 데이터베이스의 각각의 2진 이미지는 오일러 수에 할당될 수 있다. 2진 이미지의 오일러 수는 이미지내의 홀의 수와 이미지내의 커넥티드 컴포넌트(오브젝트)의 수 사이의 차이다.

오일러 수는 2진 이미지의 토폴로지컬 특징(feature)이다. 오일러 수는 2진 이미지의 번역, 회전, 스케일링, 및 러버-시트 변환하에서 불변으로 남아있는다.

2진 이미지(16)는, 도 1에 도시된 바와 같이, 2진값 1을 나타내기 위해서 오 브젝트 픽셀(12)이 셰이딩되어 있는 한편 2진값 0을 나타내기 위해서 배경 픽셀(12)이 언셰이딩되어 있는 N×M 픽셀 행렬(20)내에 표현될 수 있다. N×M 픽셀 행렬(20)내에, 커넥티드 컴포넌트는 세트내의 임의의 오브젝트 픽셀(12)이 동일 세트의 적어도 하나의 오브젝트 픽셀(12)의 8(또는 4) 이웃(neighborhood)내에 있는 오브젝트 픽셀의 일세트이다. 4-이웃(14) 및 8-이웃(18)이 도 2에 도시되어 있다.

2진 이미지내의 커넥티드 컴포넌트에 더하여, 일실시예에 있어서, 홀은 세트내의 임의의 배경 픽셀이 동일 세트의 적어도 하나의 배경 픽셀의 4(또는 8) 이웃내에 있고 이러한 전체 세트의 배경 픽셀이 커넥티드 컴포넌트에 의해 둘러싸여 있는 배경 픽셀의 일세트로서 정의된다.

픽셀 행렬(20)의 i^th 칼럼(또는 로우)의 런은 i^th 칼럼(또는 로우)내의 연속하는 1의 최대 시퀀스라고 정의된다. 2개의 인접하는 칼럼(로우)에 나타나는 2개의 런은 런의 적어도 하나의 픽셀이 다른 하나의 런의 픽셀의 8(또는 4) 이웃내에 있다면 이웃하고 있다고 각각 말해진다.

I로 알려진 2진 이미지(16)가 단일 로우(칼럼; i)로 이루어져 있다면, 이미지(16)의 오일러의 수 E(I)는, 아래의 공식에 의해 표시되는 바와 같이, 이미지(16)의 런의 수 R(i)와 동일하다.

E(I) = R(i)

그러나, 2진 이미지(16)가 다수의 로우(칼럼)로 이루어진 경우에, 2진 이미 지(I)는 부분이미지(I_i)로 분할될 수 있고, 또한, 전체 이미지의 오일러 수는 아래의 관계식을 사용하여 구할 수 있다.

단, O_i는, 예를 들어 (i-1)^th 와 i^th 로우(칼럼) 사이와 같이, 2개의 연속하는 로우(칼럼) 사이의 이웃하는 런의 수와 같다.

일실시예에 따라, 2진 이미지의 오일러 수는 N×M 픽셀 행렬의 모든 연속하는 로우(칼럼)쌍 사이의 이웃하는 런의 합과 모든 로우(칼럼)에 대한 런의 수의 합 사이의 차로서 정의된다. 수학적으로는 다음과 같다.

단, I_N=I는 전체 이미지를 표시한다. 따라서, 2진 이미지(I)내의 이웃하는 런의 수와 런의 수를 알고 있으면, 오일러 수 E(I)는 계산될 수 있다.

오일러 벡터

2진 이미지의 오일러 수는 그레이-톤 이미지로 확장될 수 있다. 예를 들어, 도 3에 도시된 바와 같이, 그레이-톤 이미지(36)는 각각의 엘리먼트(22)가 상응하는 픽셀의 강도를 나타내는 10진수 0과 255 사이의 정수인 N×M 행렬내에 표현될 수 있다. 각각의 엘리먼트의 강도값은 8-비트 2진 벡터 (b₇, b₆, b₅, b ₄, b₃, b₂, b₁, b₀)에 의해 표현될 수 있다. 따라서, 그레이-톤 이미지(36)는 8개의 비트 평면, 또는 8개의 별개의 2진 이미지로 구성된다.

가상의 그레이-톤 이미지(36)는 3개의 8-비트 픽셀(22a, 22b, 및 22c)을 포함하고, 그 각각은, 도시된 바와 같이, 별개의 강도값을 표현한다.

일실시예에 있어서, 8-비트 2진 벡터의 첫번째의 4개의 가장 중요한 비트 평면(b₇, b₆, b₅, 및 b₄)은 보유된다. 본질적으로, 4개의 2진 이미지는 보유된다. 도 4A 내지 도 4D에는, 4개의 2진 이미지(18a 내지 18d)가 도시되어 있는데, 도 3의 그레이-톤 이미지(36)의 4개의 가장 중요한 비트 평면이 표현되어 있다. 오일러 수는 각각의 2진 이미지(18a 내지 18d)에 대하여 계산될 수 있다.

일실시예에 있어서, 각각의 2진 이미지(18)에 대하여 오일러 수를 계산하기 전에, 4-비트 2진 벡터 (b₇, b₆, b₅, b₄)는, 다음과 같이, 그 상응하는 리플렉팅된 그레이 코드 벡터 (g₇, g₆, g₅, g₄)로 변환된다.

단,

는 XOR(modulo-2)연산을 표시한다. 리플렉팅된 그레이 코드 변환의 결과는, 일실시예에 따라, 도 5A 내지 도 5D의 2진 이미지(28a 내지 28d)에 각각 도시되어 있다. 임의의 2진벡터에 대하여 상응하는 리플렉팅된 그레이 코드는 유 일하고 그 역도 마찬가지라는 것은 잘 알려져 있다.

따라서, 일실시예에 있어서, 본래의 그레이-톤 이미지(K)의 오일러 벡터(

)는 4-튜플 (E₇, E₆, E₅, E₄)인데, 단, E_i는 강도값의 리플렉팅된 그레이 코드 표현에 상응하는, i^th 비트 평면(4≤i≤7)에 의해 형성된, 부분 2진 이미지(g_i)의 오일러 수이다.

따라서, 2진 이미지에 대한 오일러 수를 계산하는 것에 더하여, 그레이-톤 이미지에 대한 오일러 벡터는 이미지의 4개의 가장 중요한 2진 비트 평면을 고려하고, 4-비트 2진 벡터를 그 상응하는 리플렉팅된 그레이 코드로 변환하고, 각각의 리플렉팅된 그레이 코드 표현에 대한 오일러 수를 계산함으로써, 계산될 수 있다.

오일러 벡터를 사용하여 그레이-톤 이미지를 특성화함에 있어서, 오일러 벡터의 엘리먼트는, 어떤 경우에서, 중요도가 감소하는 순서를 갖는다. 즉, 이미지를 특성화함에 있어서 엘리먼트(E₇)가 가장 중요하고, 다음으로는 E₆ 등등이다. 또한, 오일러 벡터의 다양한 엘리먼트의 분산 및 범위는 매우 다르다. 그러한 환경에 있어서, 마할라노비스(Mahalanobis) 거리는 이미지의 일세트의 특징에 대한 속성의 유사성 및 비유사성을 캡처링하는 측정을 제공하도록 채용될 수 있다.

마할라노비스 거리

따라서, 오일러 수(E_i)는 2진 이미지를 특성화할 수 있다. 확장에 의하여, 4개의 오일러 수(E₇, E₆, E₅, 및 E₄)를 포함하는 오일러 벡터(

)는 그레이-톤 이미 지를 특성화할 수 있다. 각각의 오일러 수(E_i)는, 일실시예에 따라, 그레이-톤 이미지의 "특징"으로서 기술될 수 있다. 일실시예에 있어서, 오일러 벡터 특성화는 이미지 검색을 위한 기초를 형성할 수 있다.

오일러 벡터(

)가 이미지 데이터베이스내의 각각의 그레이-톤 이미지(K)에 대한 특징을 기술한다고 가정하자. 오일러 벡터(

)에 의해 정의된 특징을 갖는 새로운 이미지(q)가 이미지 데이터베이스로부터 검색될 것이다. 새롭게 수신된 이미지(q)는 이미지 데이터베이스내의 이미지의 각각과 비교될 수 있다. 매칭이 발견되고 나면, 이미지 검색은 완료된다.

2개의 것을 비교하는 하나의 방법은 그들 사이의 거리를 측정하는 것이다. 거리 측정은 수와 같은 스칼라 사이에서 수행될 수 있지만, 벡터 사이에서 수행될 수도 있다. 이미지가 벡터를 사용하여 기술되는 경우에, 그 자신의 벡터를 갖는 제 2 이미지와 벡터 사이의 거리가 계산될 수 있다. 따라서, 2개의 이미지 사이의 거리가 계산될 수 있다.

문의 이미지(30q)가 이미지 데이터베이스(40)내에서 발견되지 않는다고 가정하자. 일실시예에 있어서, 정확한 매치를 위해 비교하기 보다는, 데이터베이스내의 다른 이미지와 문의 이미지(30q) 사이의 거리 측정이 취해질 수 있다. 하나의 거리 측정은 마할라노비스 거리 측정으로 알려져 있다. 마할라노비스 거리 측정은 데이터베이스내의 다른 이미지와 문의 이미지(30q) 사이의 거리를 계산한 후, 거리 결과의 순위를 매긴다. 최소 거리 결과가 "매치"이다.

마할라노비스 거리 측정 동작은, 일실시예에 따라, 도 6에 도시되어 있다. 시스템(100)은 프로세서(80), 이미지 데이터베이스(40), 및 마할라노비스 거리 측정기(60)를 포함한다. 이미지 데이터베이스(40)는 연관된 오일러 벡터(

)를 각각 갖는 다수의 이미지(30)를 포함한다. 마할라노비스 거리 측정기(60)는 이미지 데이터베이스(40)로부터 이미지(30)의 각각을 수신하고, 그들을 그 자신의 오일러 벡터(

)를 포함하는 문의 이미지(30q)와 비교한다. 일실시예에 있어서, 마할라노비스 거리 측정기(60)는 이미지 데이터베이스(40)로부터의 하나 이상의 이미지(30)와 문의 이미지(30q) 사이의 마할라노비스 거리 측정을 수행하기 위한, 프로세서(80)에 의해 실행가능한, 소프트웨어 프로그램이다.

결과 테이블(50)은, 일실시예에 따라, 이미지 데이터베이스(40)내의 하나 이상의 이미지(30)와 문의 이미지(30q) 사이에서와 같은 거리 계산을 포함한다. 일실시예에 있어서, 거리 결과는 그들 사이즈에 따라 순위가 매겨진다. 따라서, 결과 테이블(50)내의 첫번째(또는 마지막) 엔트리는 거리 계산의 "매치"이다.

이미지 데이터베이스(40)내의 이미지(30)의 각각은 오일러 벡터(

)에 따라 기술되거나 분류될 수 있다. 오일러 벡터의 엘리먼트, 또는 오일러 수(E₇, E₆, E ₅, 및 E₄)는 그들이 분류한 그레이-톤 이미지(30)의 특징을 표현한다. 통상적으로, 2개의 벡터 사이의 거리 측정은 2개의 벡터의 "근접도"를 캡처링하는데 사용될 수 있다. 예를 들어, 벡터(x 및 y) 사이의 유클리디언 거리는 아래의 방정식에 의해 주어진다. 단, x는 4개의 엘리먼트(x₁, x₂, x₃, 및 x₄)를 갖고 마찬가지로 y는 4개 의 엘리먼트(y₁, y₂, y₃, 및 y₄)를 갖는다.

어떠한 현상에 대해서는, 유클리디언 거리가 그다지 우수한 거리 측정을 제공하지 않는다. 오일러 벡터에 의해 그레이-톤 이미지를 특성화할 때 벡터의 엘리먼트는 중요도가 감소하는 레벨을 갖는다는 것을 상기하자. 즉, 그레이-톤 이미지(30)를 특성화함에 있어서 E₇이 E₆보다 더 중요하고, 이미지(30)를 특성화함에 있어서 E₆가 E₅보다 더 중요한 등등이다.

또한, 벡터의 엘리먼트(E₇, E₆, E₅, 및 E₄)의 분산 및 범위는 그 크기가 매우 다르다. 그러한 환경에 있어서, 마할라노비스 거리는 데이터베이스(40)의 이미지(30) 사이의 유사성/비유사성 속성을 캡처링하기 위해 유클리디언 거리보다 더 나은 측정을 제공할 수 있다.

2개의 벡터(x 및 y) 사이의 마할라노비스 거리는 아래의 방정식으로부터 유도될 수 있다.

단, '는 전치행렬을 표현한다. M_VC는 이미지 특징 벡터 x'=(x₁, x₂, . . ., x_N) 및 y'=(y₁, y₂, . . ., y_N)에 의해 형성된 분산-공분산 행렬이다. 여기서, (x - y)'는 (1×n) 행렬이고, M_VC ^-1은 (n×n) 행렬이고, (x - y)는 (n×1) 행렬이므로 그 들의 곱은 스칼라이다.

x의 분산-공분산 행렬은 M_VC로 표시되는 N×N 행렬로서 다음과 같이 주어진다.

M_VC(i,j) = i^th 특징(x_i)의 분산 (i=j 일때);

= i^th변수(x_i) 및 j^th 변수(x_j)의 공분산 (i≠j 일때)

M_VC(i,j) = M_VC(j,i)이다. x의 분산-공분산 행렬은 디스퍼션 행렬이라고도 알려져 있다.

이미지 특징 벡터의 분산-공분산 행렬을 계산하기 위해서, 분산 및 공분산 모두가 계산된다. 특징(x_i)의 분산은 다음과 같이 정의된다.

단, L은 변수(특징; x_i)의 관측의 수이다.

또한 그레이-톤 이미지의 특징은 상관될(correlated) 수 있다. 임의의 2개의 특징 사이의 상관의 측정은 공분산으로 알려져 있다. 공분산은 다음과 같이 정의된다.

분산 및 공분산 값이 결정되고 나면, 분산-공분산 행렬(M_VC)이 계산될 수 있 다. 분산-공분산 행렬(M_VC)은 다음과 같다.

도 7에서는, 이미지(30)의 데이터베이스에 대한 분산-공분산 행렬(M_VC)이 일실시예에 따라 계산된다. 설명을 위해서, 이미지 데이터베이스(40)는 각각의 이미지(30_K)가 연관된 오일러 벡터(

)를 갖는 이미지(30)를 포함한다고 가정하자. 각각의 오일러 벡터(

)는 이미지(30_K)의 "특징"을 구성하는 오일러 수(E_K7, E_K6, E _K5, 및 E_K4)를 포함한다.

분산-공분산 행렬은 데이터베이스(40)의 모든 이미지(30)에 대하여 계산될 수 있다. 다음으로, 문의 이미지(30q)는, 도 6에 도시된 바와 같이, 시스템(100)에 의해 수신될 수 있다. 분산-공분산 행렬(M_VC)이 계산되고 나면, 이미지 문의는 신속하게 소망 이미지를 검색할 수 있다.

일실시예에 있어서, 마할라노비스 거리 측정기(60)은 이미지 데이터베이스(40)의 각각의 특징의 평균을 계산한다(블록 202). 오일러 벡터(

) 가 4개의 특징, 오일러 수(E₇-E₄)를 포함하기 때문에, 다음과 같이 4개의 평균 계산이 계산된다.

단, j는 이미지 데이터베이스(40)내의 이미지의 수이다.

데이터베이스(40)내의 각각의 이미지(30)의 특징은 상관될 수 있다. 임의의 2개의 특징 사이의 상관의 측정은 위에서 정의된 공분산 방정식에 리플렉팅된다. 따라서, 일실시예에 있어서, 이미지(30)의 특징 사이의 공분산은 계산된다(블록 206). 예를 들어, 예시된 데이터베이스(40)에 있어서, 아래의 공분산 방정식이 계산될 수 있다.

오일러 수(E₇와 E₆, E₇와 E₅, E₇와 E₄, E₆와 E₅, E₆와 E₄, 및 E₅와 E₄) 사이에서 와 같이 공분산이 계산된다. 공분산은 연관적이다. 따라서, cov(E₇, E₆)=cov(E₆, E₇) 등등이다.

이미지 데이터베이스(40)의 특징(E7, E6, E5, 및 E4)에 대하여 분산 및 공분산이 알려져 있으면, 분산-공분산 행렬(M_VC)은 일실시예에 따라 계산될 수 있다(블록 208). 오일러 벡터(

)를 사용하여 특성화된 이미지의 데이터베이스에 대하여, 분산-공분산 행렬(M_VC)은 다음과 같다.

따라서, 도 7에 따른 분산-공분산 행렬의 계산은 완료된다.

분산-공분산 행렬(M_VC)이 알려지고 나면, 마할라노비스 거리는 이미지 데이터베이스(40)내의 하나 이상의 이미지(30)와 문의 이미지(30q) 사이에서 측정될 수 있다.

일실시예에 있어서, 마할라노비스 거리는 도 8의 순서도에 따라 계산된다(블록 302). 우선, 2개의 벡터 사이의 차가 계산된다. 각각의 벡터는 주어진 이미지(30)에 대한 특징 정보를 포함한다. 예를 들어, 이미지 데이터베이스(40)의 이미지(30a)와 문의 이미지(30q) 사이에서 마할라노비스 거리가 구해지는 경우에, 오일러 벡터(

와

) 사이의 차가 계산된다.

와

사이의 차는 다음과 같다.

마찬가지로, 전치행렬 (

-

)'은 다음과 같다.

부가적으로, 이미지 데이터베이스(40)내의 이미지(30) 중 임의의 것과 이미지(30_q) 사이의 마할라노비스 거리를 계산하기 위해서, 분산-공분산 행렬(M_VC)의 역행렬(M_VC ^-1)이 계산된다(블록 304). 행렬(M_VC)의 역행렬은 알려진 원리에 따라 계산된다.

이들 연산으로부터, 마할라노비스 거리는 계산될 수 있다(블록 306). 예를 들어, 문의 이미지(30q)를 사용하여, 이미지 데이터베이스(40)내의 이미지(30) 중 하나 이상과 문의 이미지(30q) 사이에서 마할라노비스 거리가 다음과 같이 계산될 수 있다.

일실시예에 있어서, 마할라노비스 거리 측정기(60)는 최소로부터 최대로의 순서로 거리 계산의 순위를 매긴다. 따라서, 결과 테이블(50)로의 첫번째 엔트리는 문의 이미지(30q)에 대하여 가장 근접한 매치이다. 일실시예에 있어서, 대표 이미지 특징으로서 오일러 벡터를 사용하고 근접도 측정으로서 마할라노비스 거리를 사용하여, 소망 이미지가 최소 거리에 있도록 찾아진다. 문의 이미지(30q)의 잡음 및 압축 버전은 결과 테이블(50)내의 다음의 더 높은 순위를 갖는다.

어떤 실시예에 있어서, 이미지(30)를 특성화하는데 사용된 다양한 특징은 검색을 위해 똑같이 중요한 것은 아니다. 그러한 경우에 있어서, 분산-공분산 행렬(M_VC)의 엘리먼트는 상응하는 특징의 중요도에 따라 적합한 가중치만큼 승산될 수 있다.

초대용량 데이터베이스에 대하여, 문의 이미지(30q)로부터 데이터베이스(40)내의 모든 다른 이미지(30)까지의 거리를 계산하는 것은 많은 시간이 걸릴 수 있다. 따라서, 바람직하지 못하게도, 순위매김, 및, 차례로, 검색은 느릴 수 있다. 문제를 방지하기 위해서, 특징 공간내의 문의 이미지(30q)의 이웃에 놓인 이미지의 서브세트를 검색하도록 다차원 탐색 기술이 채용될 수 있다. 그후, 제안된 거리 측정에 따른 순위매김은 이러한 서브세트에 대해서만 수행될 수 있다.

범위 트리

데이터베이스내의 아이템을 찾기 위해 이용할 수 있는 기술이 많이 있다. 예로서, 데이터베이스의 순차 탐색이 일어나고, 해시 테이블이 사용되고, 2진 탐색 기술이 채용될 수 있다. 2진 트리는 데이터 세트내의 아이템의 저장, 제거, 및 탐색에 사용되는 데이터 구조이다. 이미지 데이터베이스(40)내의 이미지(30)에 관하여, 데이터베이스(40)내의 이미지의 모든 j를 탐색함이 없이 문의 이미지(30q)와 유사한 이미지(30)를 찾는 것이 바람직하다.

일실시예에 있어서, 다차원 탐색 트리는 이미지(30)를 저장하는데 그렇게 사용된다. 다차원 탐색 트리는 이미지(30)의 효율적인 검색을 허용한다.

일실시예에 있어서, 이미지는 2진 트리내에 랜덤하게 저장된다. 그러나, 때때로, 데이터는 랜덤한 순서로 2진 트리내로 삽입되지 않는다. 따라서, 2진 탐색의 수행은 최적화보다는 덜 할 수 있다. 2진 트리는 데이터의 각각의 삽입 또는 삭제 후에 "리밸런싱"될 수 있다. 리밸런싱 동작 동안, 2진 트리의 노드는 회전을 사용하여 재배열된다. 전형적으로, 이들 회전은 2진 트리의 높이를 최소화한다.

2진 트리의 일타입은 AVL 트리(그 창시자인 Adelson-Velskii 및 Landis의 이름을 따서 명명됨)로 알려져 있다. 2진 트리의 이러한 특정 형태에 있어서, 리밸런싱은, AVL 트리내의 각각의 노드에 대하여, 밸런스 팩터로 알려진, 그 서브트리 사이의 높이차가 1보다 크지 않은 것을 보장한다.

일실시예에 있어서, 도 6에 도시된 4차원 범위 트리(62)는 데이터베이스(40) 내의 각각의 이미지(30)와 연관된 오일러 벡터(

)를 저장하기 위한 데이터 구조로서 사용된다. 오일러 벡터가 4개의 특징, 오일러 수(E₇, E₆, E₅, 및 E ₄)를 포함하기 때문에 범위 트리(62)는 4차원이다. 문의 이미지(30q)에 대한 오일러 벡터(

)를 사용하여, 범위 트리(62)는 특정 노드를 지정한다. 일실시예에 있어서, 마할라노비스 거리 측정기(60)는, 범위 트리(62)의 모든 이미지(30)보다는, 노드에 있는 이들 이미지만과 문의 이미지(30q) 사이에서 수행된다. 결과는 내림차순으로 순위가 매겨져, 첫번째 거리 값은 매칭된 이미지(30)를 가리킨다.

본원발명이 제한된 수의 실시예에 관하여 설명되었지만, 당업자는 그로부터 수많은 수정예 및 변형예를 인식할 것이다. 첨부된 청구항은 본원발명의 참사상 및 범위내에 있는 모든 그러한 수정예 및 변형예를 망라하는 것으로 의도된다.

Claims

각각이 오일러 수인 하나 이상의 특징에 따라 복수의 이미지를 기술하는 단계;

문의 이미지를 수신하는 단계; 및

복수의 이미지 중 하나와 문의 이미지 사이의 마할라노비스 거리를 계산하는 단계;를 포함하는 것을 특징으로 하는 방법.
제 1 항에 있어서, 복수의 이미지 중 하나와 문의 이미지 사이의 마할라노비스 거리를 계산하는 상기 단계는

복수의 이미지의 하나 이상의 특징을 사용하여 분산-공분산 행렬을 구성하는 단계;

하나 이상의 특징을 포함하는 첫번째 이미지를 복수의 이미지로부터 선택하는 단계; 및

분산-공분산 행렬을 사용하여 문의 이미지와 첫번째 이미지 사이의 마할라노비스 거리를 계산하는 단계;를 더 포함하는 것을 특징으로 하는 방법.
제 2 항에 있어서, 복수의 이미지의 하나 이상의 특징을 사용하여 분산-공분산 행렬을 구성하는 상기 단계는

복수의 이미지의 특징의 평균을 계산하는 단계;

복수의 이미지의 특징의 분산을 계산하는 단계; 및

복수의 이미지의 한쌍의 특징 사이의 공분산을 계산하는 단계;를 더 포함하는 것을 특징으로 하는 방법.
제 3 항에 있어서, 계산된 분산 및 공분산으로부터 분산-공분산 행렬을 구성하는 단계를 더 포함하는 것을 특징으로 하는 방법.
제 2 항에 있어서, 분산-공분산 행렬을 사용하여 문의 이미지와 첫번째 이미지 사이의 마할라노비스 거리를 계산하는 상기 단계는

첫번째 이미지에 대하여 첫번째 이미지의 하나 이상의 특징을 수치적으로 특성화하는 첫번째 벡터를 식별하는 단계;

문의 이미지에 대하여 문의 이미지의 하나 이상의 특징을 수치적으로 특성화하는 문의 벡터를 식별하는 단계; 및

첫번째 벡터와 문의 벡터 사이의 차를 계산하여 차 벡터를 생성하는 단계;를 더 포함하는 것을 특징으로 하는 방법.
제 5 항에 있어서, 분산-공분산 행렬의 역행렬만큼 차 벡터를 승산하여 중간 결과를 생성하는 단계; 및

차 벡터의 역만큼 중간 결과를 승산하는 단계;를 더 포함하는 것을 특징으로 하는 방법.
제 6 항에 있어서, 범위 트리내에 복수의 이미지의 특징을 저장하는 단계를 더 포함하는 것을 특징으로 하는 방법.
프로세서;

각각이 오일러 수인 하나 이상의 특징에 따라 각각 기술된 복수의 이미지를 포함하는 이미지 데이터베이스; 및

프로세서에 의해 실행된다면, 문의 이미지를 수신하여 복수의 이미지 중 하나와 문의 이미지 사이의 마할라노비스 거리를 계산하기에 효과적인 소프트웨어 프로그램을 저장하고 있는 저장매체;를 포함하는 것을 특징으로 하는 시스템.
제 8 항에 있어서, 상기 소프트웨어 프로그램은, 프로세서에 의해 실행된다면, 이미지 데이터베이스내의 복수의 이미지의 하나 이상의 특징을 사용하여 분산-공분산 행렬을 구성하기에 효과적인 것을 특징으로 하는 시스템.
제 9 항에 있어서, 상기 소프트웨어 프로그램은 또한,

복수의 이미지의 하나 이상의 특징의 평균을 계산하고 복수의 이미지의 하나 이상의 특징의 분산을 계산하고 복수의 이미지의 특징쌍 사이의 공분산을 계산함으로써, 마할라노비스 거리를 계산하는 것을 특징으로 하는 시스템.
제 10 항에 있어서, 상기 소프트웨어 프로그램은 또한,

이미지 데이터베이스의 첫번째 이미지를 식별하고 문의 이미지에 대한 문의 벡터를 식별함으로써, 마할라노비스 거리를 계산하고,

상기 첫번째 이미지는 첫번째 이미지의 하나 이상의 특징을 수치적으로 특성화하는 첫번째 벡터를 포함하고, 상기 문의 벡터는 문의 이미지의 하나 이상의 특징을 수치적으로 특성화하는 것을 특징으로 하는 시스템.
제 11 항에 있어서, 상기 소프트웨어 프로그램은 또한,

첫번째 벡터와 문의 벡터 사이의 차를 계산하여 차 벡터를 생성하고 차 벡터의 역을 계산함으로써, 마할라노비스 거리를 계산하는 것을 특징으로 하는 시스템.
제 12 항에 있어서, 상기 소프트웨어 프로그램은 또한,

분산-공분산 행렬의 역행렬과 차 벡터를 승산하여 중간 결과를 생성하고 차 벡터의 역만큼 중간 결과를 승산함으로써, 마할라노비스 거리를 계산하는 것을 특징으로 하는 시스템.
각각이 오일러 수인 하나 이상의 각각의 특징에 따라 복수의 이미지를 기술하고, 문의 이미지를 수신하고, 복수의 이미지 중 하나와 문의 이미지 사이의 마할라노비스 거리를 계산하도록,

프로세서-기반 시스템을 인에이블링하는 명령어를 저장하고 있는 것을 특징으로 하는 저장매체.
제 14 항에 있어서, 복수의 이미지의 하나 이상의 특징을 사용하여 분산-공분산 행렬을 구성하고, 하나 이상의 특징을 포함하는 첫번째 이미지를 복수의 이미지로부터 선택하고, 분산-공분산 행렬을 사용하여 첫번째 이미지와 문의 이미지 사이의 마할라노비스 거리를 계산하도록,

프로세서-기반 시스템을 인에이블링하는 명령어를 더 저장하고 있는 것을 특징으로 하는 저장매체.
제 15 항에 있어서, 복수의 이미지의 특징의 평균을 계산하고, 복수의 이미지의 특징의 분산을 계산하고, 복수의 이미지의 한쌍의 특징 사이의 공분산을 계산하도록,

프로세서-기반 시스템을 인에이블링하는 명령어를 더 저장하고 있는 것을 특징으로 하는 저장매체.
제 16 항에 있어서, 계산된 분산 및 공분산으로부터 분산-공분산 행렬을 구성하도록, 프로세서-기반 시스템을 인에이블링하는 명령어를 더 저장하고 있는 것을 특징으로 하는 저장매체.
제 17 항에 있어서, 첫번째 이미지에 대하여 첫번째 이미지의 하나 이상의 특징을 수치적으로 특성화하는 첫번째 벡터를 식별하고, 문의 이미지에 대하여 문의 이미지의 하나 이상의 특징을 수치적으로 특성화하는 문의 벡터를 식별하고, 첫번째 벡터와 문의 벡터 사이의 차를 계산하여 차 벡터를 생성하도록,

프로세서-기반 시스템을 인에이블링하는 명령어를 더 저장하고 있는 것을 특징으로 하는 저장매체.
제 18 항에 있어서, 분산-공분산 행렬의 역행렬만큼 차 벡터를 승산하여 중간 결과를 생성하고, 차 벡터의 역만큼 중간 결과를 승산하도록,

프로세서-기반 시스템을 인에이블링하는 명령어를 더 저장하고 있는 것을 특징으로 하는 저장매체.
제 19 항에 있어서, 범위 트리내에 복수의 이미지의 특징을 저장하도록, 프로세서-기반 시스템을 인에이블링하는 명령어를 더 저장하고 있는 것을 특징으로 하는 저장매체.