KR20010036671A - 블록기반 영상 히스토그램 생성방법 - Google Patents

Abstract

본 발명은 블록 단위의 선형 양자화를 이용하여 색상, 밝기, 그리고 에지 성분을 갖는 히스토그램을 생성하는 방법에 관한 것이다.

이러한 블록기반 영상 히스토그램 생성방법은, 변수 k를 초기화하고 상기 영상의 픽셀들을 하나의 그룹으로 묶어서 레벨 k의 블록 크기를 설정하는 제 1 단계와, 상기 레벨 k의 모든 블록에 대해 블록 단위로 영상의 특징정보를 추출하여 해당 히스토그램을 갱신하는 제 2 단계와, 상기 레벨 k의 블록들을 묶어서 레벨 k+1의 블록을 만들고, 상기 레벨 k의 영상 특징정보들을 병합하면서 상기 레벨 k+1의 모든 블록에 대해 블록 단위로 영상의 특징정보를 생성하여 해당 히스토그램을 갱신하는 제 3 단계, 상기 k를 1씩 증가시키면서 모든 레벨에 대해 상기 제 3 단계를 반복 수행하는 제 4 단계를 포함한 것을 특징으로 한다.

Description

블록기반 영상 히스토그램 생성방법 { Block-based Image Histogram Generation Method }

본 발명은 JPEG, MPEG-1, 2의 표준을 따르는 압축된 데이터 비트열 또는 비압축 영상 데이터로부터 정규화된 히스토그램을 생성하는 방법에 관한 것으로서, 특히 블록 단위 선형 양자화를 이용하여 색상, 밝기, 그리고 에지 성분을 갖는 히스토그램을 생성하는 방법에 관한 것이다.

JPEG은 정지 영상에서, MPEG-1, 2는 동영상에서 저장 및 전송에 관한 국제 표준안으로 그 활용도가 매우 높다. 이러한 압축된 영상 정보에 대하여 대표 영상(Key Frame) 추출이나 영상 검색, 브라우징과 같은 응용을 위하여 각각의 영상마다 특징 정보를 추출할 필요가 있다.

이와 같이 영상에서 특징 정보를 추출하기 위해서, 영상 내 밝기 혹은 색상(빨강, 녹색, 파랑)의 상대적 발생 빈도를 나타내는 밝기 혹은 색상 히스토그램(Histogram)이 많이 사용된다. 특히 최근에 디지털화되어 저장된 정지영상 혹은 디지털 비디오의 검색을 위해 히스토그램을 비교하는 방법이 제안되고 있다. 이와 같이 히스토그램이 영상의 검색 및 장면전환 검출에 많이 활용되면서 히스토그램에 대한 개선이 요구되고 있다. 즉, 기존의 이산 양자화와 색상만의 단일 성분 히스토그램을 발전시켜 선형 갱신(linear update) 혹은 연성판정(soft decision)을 채택한 색상, 에지, 밝기의 복합 히스토그램(composite histogram)을 채택하여 영상의 내용을 보다 효율적이고 충실하게 나타낼 필요성이 대두되고 있다.

종래의 히스토그램 생성방법에 관한 기술을 살펴보면 다음과 같다.

'Katherine 외 2인'이 권리자인 미국 특허(No. 5,805,733) 'Method and system for detecting scenes and summarizing video sequences' 에는, 색상 히스토그램과 에지 맵을 사용하여 장면 전환을 검출하는 내용이 기술되어 있다. 이는 인간 시각을 고려한 색상 정보를 추출한다는 효과가 있으나, 밝기를 이용하지 않는다는 문제점이 있다. 'M.J.Swain 외 1인'이 'Int. J. of Computer Vision'에 게재한 논문 'Color Indexing' 에서는 색상 정보를 입력받아 히스토그램 인터섹션(Histogram Intersection) 기법을 이용하여 영상의 유사도를 측정하여 인덱싱을 수행하는 내용이 기술되어 있다. 그러나, 이 역시 밝기 및 에지 정보를 사용하지 않아 정확성이 떨어진다는 문제점이 있다. 또한, 이들 기존의 기법들에서는 이산 양자화기법을 이용하여 히스토그램을 생성하므로 같은 성능을 내기 위해 상대적으로 많은 히스토그램 빈(bin)이 필요하며, 따라서 저장과 유사도 측정이 비효율적이라는 문제점이 있었다.

그리고, 종래에는 히스토그램 생성시, 픽셀 단위로 특징 추출을 수행하기 때문에 제한적인 특징 정보만을 생성할 수밖에 없는 문제점이 있었다.

따라서, 본 발명은 상기와 같은 종래기술의 문제점을 해결하기 위하여 안출된 것으로서, 여러 개의 픽셀로 구성된 블록을 히스토그램 생성의 기본 단위로 사용하여, 이 블록 단위의 픽셀 집합에서 다양한 분해능의 밝기, 색상, 에지 등의 특징 정보를 추출하는 블록 기반 영상 히스토그램 생성방법을 제공하기 위한 것이다.

또한, 본 발명은, 영상 히스토그램에서 히스토그램의 각 빈이 가지는 의미를 구분하여, 영상의 내용을 좀 더 효과적으로 반영하는 히스토그램을 생성하기 위한 것이기도 하다.

도 1은 본 발명의 한 실시예에 따른 블록기반 영상 히스토그램 생성방법을 도시한 전체 흐름도,

도 2는 본 발명의 한 실시예에 따른 블록기반 영상 히스토그램 빈 갱신방법을 도시한 흐름도,

도 3은 블록내 서브블록들의 밝기 대표값과 에지의 종류를 도시한 도면,

도 4는 에지 검출을 위한 블록 필터를 도시한 도면,

도 5는 에지 검출방법을 도시한 흐름도,

도 6은 하위레벨의 다수개의 블록들을 병합하여 상위레벨의 블록을 생성하는 과정을 도시한 도면,

도 7은 히스토그램 시멘틱의 일 예를 도시한 도면,

도 8은 선형 가중치를 고려하지 않은 종래의 히스토그램 갱신방법을 도시한 도면,

도 9는 선형 가중치를 고려한 본 발명의 한 실시예에 따른 히스토그램 갱신방법을 도시한 도면,

도 10은 유채색 빈과 빈 사이의 선형 가중치와 유채색과 무채색 사이의 선형 가중치를 설명하기 위하여 도시한 도면,

도 11은 밝기 특징정보와 에지 특징정보를 사용하여 구성한 복합 히스토그램의 일 예를 도시한 도면,

도 12는 전체 영역(global)에서의 특징정보와, 부분적 전체영역(semi-global)에서의 특징정보, 국부영역(local)에서의 특징정보를 사용하여 구성한 복합 히스토그램,

도 13은 도 12의 복합 히스토그램의 일 예를 설명하기 위하여 도시한 도면이다.

상기한 목적을 달성하기 위한 본 발명에 따르면, 영상 데이터의 색정보와 밝기정보를 이용하여 영상 히스토그램을 생성하는 방법에 있어서, 상기 영상의 픽셀들을 하나의 그룹으로 묶은 블록 단위로 영상의 특징정보를 추출하여 히스토그램을 생성하고, 상기 블록의 크기를 변화시키고 상기 크기 변화된 블록 단위로 영상의 특징정보를 추출하여 히스토그램을 생성하는 것을 특징으로 한다.

양호하게는, 변수 k를 초기화하고 상기 영상의 픽셀들을 하나의 그룹으로 묶어서 레벨 k의 블록 크기를 설정하는 제 1 단계와, 상기 레벨 k의 모든 블록에 대해 블록 단위로 영상의 특징정보를 추출하여 해당 히스토그램을 갱신하는 제 2 단계와, 상기 레벨 k의 블록들을 묶어서 레벨 k+1의 블록을 만들고, 상기 레벨 k의 영상 특징정보들을 병합하면서 상기 레벨 k+1의 모든 블록에 대해 블록 단위로 영상의 특징정보를 생성하여 해당 히스토그램을 갱신하는 제 3 단계, 상기 k를 1씩 증가시키면서 모든 레벨에 대해 상기 제 3 단계를 반복 수행하는 제 4 단계를 포함한다.

여기서, 상기 영상의 특징정보는 밝기, 에지, 및 색상 정보를 포함한다.

보다 상세하게는, 상기 제 2 단계에서 영상의 에지 특징정보를 추출하는 단계는, 상기 블록을 가로 및 세로로 2등분하여 4개의 서브블록을 나누는 제 1 서브단계와, 상기 각각의 서브블록들의 밝기 대표값들을 구하는 제 2 서브단계, 및 상기 인접한 서브블록 사이의 밝기차가 임계값(Te)을 넘으면 해당 서브블록들 사이에 에지가 존재하는 것으로 판단하고, 에지의 종류(수평에지, 수직에지, 혼합에지)를 검출하는 제 3 서브단계를 포함한다. 모든 서브블록들 사이의 밝기차가 임계값(Te)을 넘지 않으면, 상기 블록은 에지가 존재하지 않는 모노톤 블록으로 판정하는 제 4 서브단계를 더 포함하는 것이 더욱 양호하다.

보다 양호하게는, 상기 제 2 단계에서 영상의 에지 특징정보를 추출하는 단계는, 상기 블록을 가로 및 세로로 2등분하여 4개의 서브블록을 나누는 제 1 서브단계와, 상기 각각의 서브블록들의 밝기 대표값들을 구하는 제 2 서브단계, 및 상기 서브블록들의 밝기 대표값들과 필터 계수값들을 컨볼루션(convolution)하여 0도 에지값(edge0)과, 45도 에지값(edge45)과, 90도 에지값(edge90)과, 135도 에지값(edge135)과, 혼합 에지값(complex_edge)을 각각 구하는 제 3 서브단계, 상기 0도 에지값(edge0)과, 45도 에지값(edge45)과, 90도 에지값(edge90)과, 135도 에지값(edge135)과, 혼합 에지값(complex_edge) 중 최대 에지값과 임계값(Th_sub_differece)을 비교하는 제 4 서브단계, 및 상기 제 4 서브단계에서 최대 에지값이 임계값보다 크면 상기 최대값의 에지를 상기 블록의 대표 에지로 판정하는 제 5 서브단계를 포함한다. 상기 제 4 서브단계에서 최대 에지값이 임계값보다 작으면 상기 블록을 단일톤 블록으로 판정하는 제 6 서브단계를 더 포함하는 것이 더욱 양호하다.

보다 더 양호하게는, 상기 제 3 서브단계는, 상기 서브블록의 밝기 대표값들과 필터 계수값들을 수학식 1에 적용하여 0도 에지값(edge0)과, 45도 에지값(edge45)과, 90도 에지값(edge90)과, 135도 에지값(edge135)과, 혼합 에지값(complex_edge)을 구하는 단계이다.

여기서, 상기 서브블록의 밝기 대표값은 픽셀들의 평균값 또는 픽셀들의 중앙값을 사용한다.

더욱 양호하게는, 상기 제 2 단계에서 영상의 색상, 밝기 특징정보를 추출하는 단계는, 블록의 색차 정보를 이용하여 의사 색조(ph)와 의사 색농도(ps)를 구하는 제 1 서브단계와, 상기 의사 색조와 의사 색농도를 이용하여 유채색의 빈과 빈 사이의 선형 가중치(α)와, 유채색과 무채색 사이의 선형 가중치(β)를 구하는 제 2 서브단계, 상기 의사 색농도값을 이용하여 상기 블록의 색상이 순수 색상인지 혹은 무채색을 포함한 어두운 유채색인 지를 판별하는 제 3 서브단계, 상기 블록의 색상이 순수 색상이면, 상기 선형 가중치(α)를 이용하여 해당 색상 히스토그램 빈의 증가분을 계산하여 해당 색상 히스토그램을 갱신하는 제 4 서브단계, 및 상기 블록의 색상이 어두운 유채색이면, 상기 선형 가중치(α)와 선형 가중치(β)를 이용하여, 해당 색상 히스토그램 빈의 증가분과 밝기 히스토그램 빈의 증가분을 계산하여 해당 색상 히스토그램과 밝기 히스토그램을 갱신하는 제 5 서브단계를 포함한다.

양호하게는, 영상의 적어도 2개 이상의 특징정보를 하나의 복합 히스토그램에 표현한다.

또한, 본 발명에 따르면 상술하였던 블록기반 영상 히스토그램 생성방법을 실현하기 위한 프로그램을 기록한 컴퓨터로 읽을 수 있는 기록매체가 제공된다.

이하, 첨부된 도면을 참조하면서 본 발명의 한 실시예에 따른 ″블록기반 영상 히스토그램 생성방법″을 보다 상세하게 설명하면 다음과 같다.

본 발명의 특징은 크게 5가지로 볼 수 있다. 첫째, 다수개의 픽셀들을 하나의 블록으로 묶어서 이를 기본 단위로 이용하여 특징 정보를 추출하는 것이다. 둘째, 블록 단위로 추출되는 특징 정보에 에지 및 질감 정보가 포함되도록 하는 것이다. 셋째, 블록의 크기는 영상의 크기에 따라 변형 가능하여 영상 전체의 크기에 상관없이 정량적인 특징 정보의 추출이 가능하도록 한다. 넷째, 히스토그램의 증가치를 계산할 때 선형 가중치를 적용하여 양자화오차를 줄인다. 다섯째, 하나의 영상에 대해 전체 영역, 부분적 전체 영역, 국부 영역에 대해 각각의 히스토그램을 생성한다.

도 1은 본 발명의 한 실시예에 따른 블록기반 영상 히스토그램 생성방법을 도시한 전체 흐름도이다.

도 1을 참조하면, 먼저, 변수 k를 0으로 초기화하고 상기 영상의 픽셀들을 하나의 그룹으로 묶어서 레벨 0의 블록 크기를 설정한다(S101). 상기 레벨 0의 모든 블록에 대해 블록 단위로 영상의 특징정보를 추출하여 해당 히스토그램을 갱신한다(S102, S103, S104, S105). 즉, 첫 번째 블록부터 블록 내 특징정보를 추출하고(S102), 해당 히스토그램을 갱신하는(S103) 동작을 모든 블록에 대해 수행한다(S104, S105). 블록 내 특징정보로는 밝기, 색상, 에지 정보가 포함되며, 정보를 추출하는 자세한 설명은 후술하기로 한다.

다음, 레벨 0의 모든 블록들에 대해 특징정보를 추출한 후, 레벨을 나타내는 변수 k를 1 증가시킨(S106) 다음, 레벨 0의 특징정보를 병합하여 레벨 1의 특징정보를 생성하고(S107), 해당 히스토그램을 갱신한다(S108). 이때, 레벨 1의 블록은 레벨 0의 블록들을 묶어서 만들 수 있으며, 레벨 1의 특징정보들도 레벨 0의 특징정보를 병합하여 생성할 수 있다. 레벨 1의 모든 블록들에 대해 특징정보를 추출하고 해당 히스토그램을 갱신하는 동작을 반복 수행한다(S109, S110).

다음, 모든 레벨에 대한 특징정보 생성이 끝나지 않았으면(S111), 레벨을 나타내는 변수를 1 증가시키는 단계 S106으로 진행하고, 모든 레벨에 대한 특징정보 생성이 끝나면 종료한다.

1, 먼저, 첫 번째 특징인 히스토그램의 기본 단위에 대해 설명한다.

기존의 히스토그램 생성방법에서는 영상 내 각 픽셀별로 추출된 밝기 혹은 색상 특징 정보를 해당 히스토그램 빈에 대해서만 갱신하였다. 그러나, 본 발명에서는 도 2에 도시된 바와 같이 여러 픽셀들 즉, N×M 픽셀 그룹을 하나의 블록으로 묶어서 마치 하나의 큰 픽셀(블록) 단위로 히스토그램 빈을 갱신한다. 즉, 히스토그램 빈의 갱신을 블록 단위로 정의함으로써 영상의 밝기, 색상 특징 뿐만 아니라 다양한 분해능을 갖는 에지 특징 정보도 추출한다. 또한, 영상의 크기에 비례하여 블록의 크기를 변형하여, 영상 전체의 크기에 상관없이(scale invariant) 정량적인 특징 정보의 추출이 가능하도록 한다.

도 2는 영상의 각 블록 단위별 히스토그램 갱신의 예를 도시한 도면이다. 각 블록마다 추출된 특징정보들은 블록 단위로 히스토그램 빈 갱신에 사용된다.

2, 두 번째 특징인 블록에서 추출된 특징 정보에 대해 설명한다.

상기와 같이 N×M 픽셀들을 블록 단위로 묶어서 하나의 블록으로 구성하고 블록 단위로 특징 정보를 추출하기 때문에 밝기 및 색상 정보 뿐만 아니라 블록 내 발생되는 에지, 질감(texture) 등 다양한 특징 정보를 획득할 수 있다.

그리고 이 블록 단위로 추출된 특징 정보는 복합(composite) 히스토그램 갱신에 반영할 수 있다. 하나의 블록은 도 3에 도시된 바와 같이 4개의 서브 블록(sub-block)들로 이루어진다. 각 서브 블록들은 내부 픽셀들의 밝기 대표값으로 표현된다. 서브 블록의 대표값으로는 서브 블록 내 픽셀들의 평균값(average value) 또는 중앙값(median value)을 사용한다. 이러한 서브 블록으로 이루어진 블록의 에지는 다음과 같은 방법으로 검출할 수 있다.

블록의 에지 존재 여부를 검출하는 방법의 제1실시예는 다음과 같다.

도 3의 (a)에 도시된 바와 같이 블록은 4개의 서브 블록들로 이루어지며, 각 서브 블록들의 밝기 대표값은 각각 DC1, DC2, DC3, DC4라 한다. 블록간 에지 구별을 위한 밝기차의 임계값을 Te라 하면, 각 블록간 밝기값의 차이가 Te를 넘는 경우 해당 블록간에 에지가 존재하는 것이며 이를 굵은 실선으로 표현한다. 블록 내에 에지가 존재하는 경우 도 3의 (b), (c), (d)의 3가지 종류 중의 한가지 에지에 해당된다. 즉, (b)와 같은 수직 에지이거나, (c)와 같은 수평 에지이거나, (d)와 같은 혼합에지 중 한가지 에지이다. 이와 같이 에지가 판정되면 해당 히스토그램 빈을 1 증가시킨다.

블록의 에지 존재 여부를 검출하는 방법의 제2실시예는 다음과 같다.

도 4는 본 실시예에 따른 블록의 에지 존재 여부를 검출할 때 사용하는 5가지 필터들을 도시한 도면이다. 도 4의 (a)는 edgd 90의 필터 계수값, (b)는 edge 0의 필터 계수값, (c)는 edge 45의 필터 계수값, (d)는 edge 135의 필터 계수값, 및 (e)는 complex_edge의 필터 계수값이다. 도 5는 본 발명의 제2실시예에 따른 블록의 에지 존재 여부 검출방법을 도시한 흐름도이다.

도 5를 참조하면, 0도 에지값(edge0), 45도 에지값(edge45), 90도 에지값(edge90), 135도 에지값(edge135), 혼합 에지값(complex_edge)을 각각 구한다(S501). 이때, 상기한 에지값들은 상기한 도 4에 도시된 5가지의 필터와 각 서브 블록들의 대표값들을 컨볼루션(convolution)하여 구할 수 있는 바, 이는 수학식 1과 같다.

여기서, mean_sub_block(0)는 도 3 (a)의 DC1, mean_sub_block(1)는 DC2, mean_sub_block(2)는 DC3, mean_sub_block(3)는 DC4를 각각 의미한다. 또한, edge90_filter(i) 내지 complex_edge_filter(i)는 도 4에 도시된 필터 계수값들을 의미한다. 예를 들어, edge45_filter(0)은, edge45_filter(1)과 edge45_filter(2)는 0, edge45_filter(3)은이다.

상기와 같이 0도 에지값(edge0)과, 45도 에지값(edge45), 90도 에지값(edge90), 135도 에지값(edge135), 및 혼합 에지값(complex_edge)들을 계산한 다음, 이들 중 가장 큰 값이 임계값(Th_sub_differece)을 넘는지 판별하여(S502) 단일톤 블록과 에지블록을 구분한다. 즉, 최대 에지값이 임계값보다 크면 상기 최대값 에지를 그 블록의 대표 에지로 판별한다(S503). 그러나, 최대 에지값이 임계값보다 작으면 그 블록을 단일톤 블록으로 판별한다(S504). 상기와 같이 해당 블록의 에지 종류가 판별되면 해당 히스토그램 빈을 1 증가시킨다.

3. 블록에서 추출된 특징정보의 가변크기 블록(variable size block)화

이제까지는 영상 전체의 밝기, 색상, 에지 등의 분포 등을 일정한 해상도로 추출하였으나, 영상을 보다 효과적으로 표현하려면 다양한 해상도를 갖는 특징 정보의 추출이 필요하다. 본 발명에서는 도 6에 도시된 바와 같이 여러 개의 기본 블록(level 0)들로 이루어진 상위 블록(level 1)을 정의한다. 즉, 하위레벨 k의 블록들을 모아서 상위레벨 k+1의 블록으로 정의한다. 도면에서, 레벨 k의 블록들은 (0,0) 에서 (5,5) 까지이다. 하위레벨 k의 블록들을 9개씩 묶으면, (0,0)에서 (2,2) 까지의 블록들은 상위레벨 k+1의 B00 블록이 되고, (0,3) 에서 (2,5) 까지의 블록들은 상위레벨 k+1의 B01 블록이 되며, (3,0) 에서 (5,2) 까지의 블록들은 상위레벨 k+1의 B10 블록이 되고, (3,3) 에서 (5,5) 까지의 블록들은 상위레벨 k+1의 B11 블록이 된다.

영상을 보다 효과적으로 표현하려면, 각 레벨별로 에지 성분을 추출하여 해당 히스토그램의 빈을 발생한다. 상위레벨 블록의 특징정보는 하위레벨 블록들의 특징정보를 사용하여 간단한 연산으로 구할 수 있다. 그리고 영상 내 위치정보를 추가한 상위블록 특징정보는 영상내 위치별, 해상도별 특징 정보를 반영한 시멘틱(semantic)의 히스토그램을 도 7과 같이 구성할 수 있다. 즉, 각 레벨별로 수직 에지 히스토그램 빈과 수평 에지 히스토그램 빈, 및 혼합 에지 히스토그램 빈을 별도 발생할 수 있다.

4. 선형 갱신(linear update)

색상에 있어서, 기존의 히스토그램 빈 갱신방법은 도 8에 도시된 바와 같이 주어진 구역내의 데이터 존재 유무를 가지고 해당 히스토그램의 빈을 1씩 증가시키는 바이너리(binary) 결정방법을 사용한다. 이 경우 빈과 빈 사이의 경계 부근에 존재하는 데이터의 경우 유사한 색상 특징을 반영하지만 2개의 빈에 각각 다르게 할당됨으로써 서로 다른 특징 정보로 표현되는 심각한 오차를 발생시킨다. 이러한 오차를 해소하기 위하여 종래에는 결과 히스토그램을 평탄화시키는 작업 즉, 저역통과 필터링을 행하였다. 그러나, 이러한 평탄화 작업으로 인하여 특징 정보의 손실이 많으므로 영상의 정확한 특징 정보를 반영할 수 없는 문제점이 있었다.

이러한 종래기술의 문제점을 보다 명확하게 살펴보기 위하여 도 8을 참조하면서 설명하면 다음과 같다.

도 8의 (a)와 (c)의 ″A″부분은 모두 오렌지색이지만, (a)는 빨강에 가까운 오렌지색이고 (c)는 노랑에 가까운 오렌지색이다. 이 두 색은 비슷한 오렌지색이지만, (a)의 오렌지색은 (c)에 도시된 바와 같이 빨강 히스토그램 빈에 카운트되고, (c)의 오렌지색은 (d)에 도시된 바와 같이 노랑 히스토그램 빈에 카운트된다. 이와 같이 종래에는 빈과 빈 사이의 경계 부근에 존재하는 정보는 유사한 특징을 가지지만 각각 다른 빈에 할당되기 때문에 다른 특징 정보로 표현되는 심각한 오차를 발생시키는 문제점이 있었다.

이러한 문제를 해결하기 위하여, 본 발명에서는 각 빈과 빈 사이의 거리에 따른 선형적인 가중치를 적용함으로써 빈과 빈 사이에서 발생되는 양자화 오차를 줄인다.

즉, 도 9를 참조하면, (a)에 도시된 ″A″부분과 (c)에 도시된 ″A″부분은 모두 오렌지색이며, 빨강(R)과 노랑(Y)의 경계부근에 위치한다. 이때, 빨강(R)에 가까운 오렌지색은 (b)에 도시된 바와 같이 빨강(R)에 더 많은 가중치가 부여되어 히스토그램 카운팅되고, 노랑(Y)에 가까운 오렌지색은 (d)에 도시된 바와 같이 노랑(Y)에 더 많은 가중치가 부여되어 히스토그램 카운팅된다. 각 빈과 빈 사이의 거리에 따른 선형적인 가중치의 적용에 따라 빈과 빈 사이에서 발생하는 양자화 오차를 줄인다. 따라서, 적은 수의 빈을 갖는 히스토그램이라도 특징 정보를 정확하게 반영할 수 있는 잇점이 있다.

이와 같은 선형 갱신의 적용예를 설명하면 다음과 같다.

도 10은 유채색영역을 마젠타(M), 청색(B), 사이안(C), 녹색(G), 노랑(Y)의 6가지로 구분하고, 무채색을 밝기에 따라 5가지로 구분하여 히스토그램의 빈을 카운트하는 예를 설명하기 위하여 도시한 도면이다. 이 경우, 히스토그램 빈 h(0)부터 h(5)는 색상 히스토그램이고, h(6)부터 h(10)은 밝기 히스토그램이다.

본 발명에서는 YCbCr 색공간으로부터 의사 색조(pseudo hue)와 의사 색농도(pseudo saturation)를 계산하여 사용한다. 그러나, 색조(Hue)와 색농도(Saturation)로 표현되는 색공간을 사용하는 경우에는 의사 색조(pseudo hue)와 의사 색농도(pseudo saturation) 대신에 색조와 색농도를 그대로 사용할 수도 있다.

YCbCr 색공간에서, Cb, Cr값에 의하여 의사 색조(Psuedo Hue)와 의사 색농도(Psuedo Saturation)은 수학식 2와 같이 정의된다.

색상 빈과 빈 사이의 선형 가중치(α)와 무채색과 유채색 빈 사이의 선형 가중치(β)는 수학식 3과 같이 구할 수 있다.

이때, 색차 성분을 이용한 색정보는 영상의 밝기에 무관한 색 특징 정보로서만 사용된다. 색공간에서 중심인 원점부근에서는 Cr과 Cb가 '0'근처의 값을 가지므로 무채색에 가까운 색이다. 일반적으로 이 색차값과 원점과의 거리를 임계치로 하여 무채색과 유채색을 구분하게 되는데, 자연 영상의 경우 이 경계에 존재하는 경우가 많이 발생하고, 이 경계에서 발생하는 오차가 매우 심각하게 발생한다. 즉, 밝기가 좀 더 밝은 색상은 유채색의 히스토그램 빈에 갱신되고, 밝기가 좀 더 어두운 색상은 무채색 히스토그램 빈에 갱신되는 등과 같이, 비슷한 어두운 밝기의 색상이더라도 서로 다른 히스토그램 빈에 갱신되는 등의 문제가 발생한다.

본 발명에서는 이와 같은 무채색과 유채색의 경계부근에서도 선형 가중치를 고려한 갱신방법을 사용한다.

무채색 빈의 시작 임계치를 Ts라 한다면, 의사 색농도(ps)가 Ts를 넘으면 순수 색상이기 때문에 도 10의 (a)에 도시된 바와 같이 색상 히스토그램의 카운트는 빈과 빈 사이의 선형 가중치(α)만으로 각 빈(h(i))을 실수 값의 증가분으로 증가시킨다. 이는 수학식 4와 같이 표현된다.

여기서, i=0,1,2,3,4,5

한편, 의사 색농도(ps)가 Ts를 넘지 않으면 즉, 색공간에서 원점 부근에 위치한 무채색에 가까운 색상인 경우에는, 도 10의 (b)에 도시된 바와 같이 색상 히스토그램은 빈과 빈 사이의 선형 가중치(α)와 무채색 빈의 선형 가중치(β)를 포함하여 증가시킨다. 이는 수학식 5와 같이 표현된다.

여기서, i=0,1,2,3,4,5

또한, 상기와 같이 밝기가 어두운 색상인 경우, 밝기 히스토그램을 5개의 빈들로 구분하고, 밝기 히스토그램 빈들을 선형 가중치(β)를 이용하여 수학식 6과 같은 조건에 따라 증가시킨다.

다음은, 에지와 밝기로 구성된 복합 히스토그램의 갱신 예를 설명하기로 한다. 도 11은 0 레벨의 블록들이 가지는 밝기 정보와, 0, 1, 2 레벨들의 블록들이 가지는 에지 정보들을 히스토그램 빈 갱신에 적용한 예를 설명하기 위하여 도시한 도면이다.

우선, 0 레벨에서, 블록의 대표 밝기값 L 에 대하여 밝기 히스토그램 빈은 Q개로 구분하는 바, 그 구분 조건은 수학식 7과 같다.

그리고, 각 레벨에서의 블록에서 구하여진 방향성 에지의 강도를 각각 수직에지의 강도(α_v(k)), 수평 에지의 강도(α_h(k)), 혼합 에지의 강도(α_misc(k))라고 하면, 해당 히스토그램 빈의 갱신은 수학식 8과 같다.

상기와 같은 복합 히스토그램의 경우, 0 레벨의 밝기 히스토그램 빈은 h(0) 내지 h(Q-1)을 마련하고, 0 레벨 내지 2 레벨의 에지 히스토그램 빈은 h(Q) 내지 h(Q+8)을 마련한다.

여기에 1 레벨, 2 레벨, .. , k 레벨의 밝기 히스토그램을 추가하여, 밝기에 대한 다해상도(multi-resolution) 표현을 추가할 수도 있다.

5. 영역별 히스토그램 생성

도 12와 같이 블록 단위로 생성된 히스토그램을 이용하여, 영상의 전체 영역(global region), 부분적 전체영역(semi-global region), 국부 영역(local region)에 대하여 각각의 히스토그램을 생성한다. 이렇게 생성된 각 영역별 히스토그램은 영상의 전체적인 특징와 국부적인 위치정보를 잘 반영할 수 있는 특징정보로 이용할 수 있다.

전체 영역(global region)에 대하여 6개의 밝기 빈과 5개의 에지 빈을 사용하면 도 13에 도시된 바와 같이 11개의 히스토그램 빈을 생성할 수 있다. 이 11개의 히스토그램 빈을 이용하여 영상의 전체적인 특징정보를 표현한다.

이 전체 영역을 가로 및 세로를 4등분하여 16개의 국부영역들을 만들고, 각각 국부영역별로 5개의 에지 빈을 생성하면 도 13에 도시된 바와 같이 80개의 히스토그램 빈이 생성된다.

마지막으로, 각 국부영역에 대하여 가로, 세로별로 각각 에지의 종류별로 누적을 하여 가로에 대하여 4개의 부분적 전체영역을 만들고, 세로에 대해 4개의 부분적 전체영역을 만든다. 각 부분적 전체영역에 대해 5가지 에지 빈이 존재하면, 도 13에 도시된 바와 같이 40개의 에지 빈이 생성된다.

즉, 도 13에 도시된 바와 같은 복합 히스토그램에는 전체 영역에 대한 밝기 정보가 h(0)부터 h(5)까지 갱신되고, 전체 영역에 대한 에지 정보가 h(6)부터 h(10)까지 갱신되며, 국부 영역에 대한 에지 정보가 그 위치별로 5개씩 h(11)부터 h(90)까지 갱신되고, 부분적 전체영역에 대한 에지 정보가 그 위치별로 5개씩 h(91)부터 h(130)까지 갱신된다.

이와 같이 히스토그램 빈의 순서가 정해지면, 부분적 전체영역이나 국부영역의 히스토그램에는 위치정보와 에지 특징정보가 동시에 표현된다.

이때, 이 복합 히스토그램은 각 영역별 정규화되는데, 그 방법은 아래와 같다.

첫 번째, 전체 영역 히스토그램 빈(global_histogram_value[i])은 영상내 존재하는 전체영역의 블록의 개수(global_number_block)로 나누어 수학식 9와 같이 정규화한다.

두 번째, 국부 영역의 80개의 히스토그램 빈은 각 국부영역의 영상에 대하여 각각 국부영역 내 블록의 갯수(local_global_number_block)로 나누어 수학식 10과 같이 정규화한다.

마지막으로, 부분적 전체 영역의 40개의 빈은 각 부분적 전체 영역의 영상에 대해, 가로 또는 세로로 연속된 부분 영상 내 블록 수(semi_global_number_block)로 나누어 수학식 11과 같이 정규화한다.

이렇게 정규화된 nomalize_histogram[i]는 도 13과 같이 표현된다.

위에서 양호한 실시예에 근거하여 이 발명을 설명하였지만, 이러한 실시예는 이 발명을 제한하려는 것이 아니라 예시하려는 것이다. 이 발명이 속하는 분야의 숙련자에게는 이 발명의 기술사상을 벗어남이 없이 위 실시예에 대한 다양한 변화나 변경 또는 조절이 가능함이 자명할 것이다. 그러므로, 이 발명의 보호범위는 첨부된 청구범위에 의해서만 한정될 것이며, 위와 같은 변화예나 변경예 또는 조절예를 모두 포함하는 것으로 해석되어야 할 것이다.

이상과 같이 본 발명에 따른 히스토그램 생성방법은, 여러 개의 픽셀로 이루어진 블록 단위로 특징정보를 추출하기 때문에 종래에는 추출하지 못했던 에지 정보를 추출할 수 있다. 또한, 다양한 해상도의 밝기, 색상, 에지 등의 특징정보를 추출하기 때문에 영상의 내용을 반영하는 특징정보를 보다 자세하게 추출할 수 있고, 유사도 측정이나 거리 측정에서 정확한 비교가 가능해지는 효과가 있다.

또한, 선형 갱신방법을 이용함으로써, 빈과 빈 사이의 경계에서 발생하는 양자화 오차를 상당히 감소시킬 수 있는 효과가 있다. 또한, 히스토그램 빈을 정규화하여 사용하기 때문에 영상의 크기에 관계없이 유사한 영상을 검색해 낼 수 있는 효과가 있다.

Claims (13)

1. 영상 데이터의 색정보와 밝기정보를 이용하여 영상 히스토그램을 생성하는 방법에 있어서,

   상기 영상의 픽셀들을 하나의 그룹으로 묶은 블록 단위로 영상의 특징정보를 추출하여 각 특징별로 전체 히스토그램 빈들을 갱신하고, 상기 블록의 크기를 변화시키고 상기 크기 변화된 블록 단위로 영상의 특징정보를 추출하여 각 블록별 부분 히스토그램 빈들을 갱신하여, 상기 전체 히스토그램 빈들과 부분 히스토그램 빈들을 결합하여 영상 히스토그램을 생성한 것을 특징으로 하는 블록기반 영상 히스토그램 생성방법.
2. 제 1 항에 있어서, 변수 k를 초기화하고 상기 영상의 픽셀들을 하나의 그룹으로 묶어서 레벨 k의 블록 크기를 설정하는 제 1 단계와,

   상기 레벨 k의 모든 블록에 대해 블록 단위로 영상의 특징정보를 추출하여 해당 히스토그램을 갱신하는 제 2 단계와,

   상기 레벨 k의 블록들을 묶어서 레벨 k+1의 블록을 만들고, 상기 레벨 k의 영상 특징정보들을 병합하면서 상기 레벨 k+1의 모든 블록에 대해 블록 단위로 영상의 특징정보를 생성하여 해당 히스토그램을 갱신하는 제 3 단계,

   상기 k를 1씩 증가시키면서 모든 레벨에 대해 상기 제 3 단계를 반복 수행하는 제 4 단계를 포함한 것을 특징으로 하는 블록기반 영상 히스토그램 생성방법.
3. 제 2 항에 있어서, 상기 영상의 특징정보는 밝기, 에지, 및 색상 정보를 포함한 것을 특징으로 하는 블록기반 영상 히스토그램 생성방법.
4. 제 3 항에 있어서, 상기 제 2 단계에서 영상의 에지 특징정보를 추출하는 단계는,

   상기 블록을 가로 및 세로로 2등분하여 4개의 서브블록을 나누는 제 1 서브단계와,

   상기 각각의 서브블록들의 밝기 대표값들을 구하는 제 2 서브단계, 및

   상기 인접한 서브블록 사이의 밝기차가 임계값(Te)을 넘으면 해당 서브블록들 사이에 에지가 존재하는 것으로 판단하고, 에지의 종류(수평에지, 수직에지, 혼합에지)를 검출하는 제 3 서브단계를 포함한 것을 특징으로 하는 블록기반 영상 히스토그램 생성방법.
5. 제 4 항에 있어서, 모든 서브블록들 사이의 밝기차가 임계값(Te)을 넘지 않으면, 상기 블록은 에지가 존재하지 않는 모노톤 블록으로 판정하는 제 4 서브단계를 더 포함한 것을 특징으로 하는 블록기반 영상 히스토그램 생성방법.
6. 제 3 항에 있어서, 상기 제 2 단계에서 영상의 에지 특징정보를 추출하는 단계는,

   상기 블록을 가로 및 세로로 2등분하여 4개의 서브블록을 나누는 제 1 서브단계와,

   상기 각각의 서브블록들의 밝기 대표값들을 구하는 제 2 서브단계, 및

   상기 서브블록들의 밝기 대표값들과 필터 계수값들을 컨볼루션(convolution)하여 0도 에지값(edge0)과, 45도 에지값(edge45)과, 90도 에지값(edge90)과, 135도 에지값(edge135)과, 혼합 에지값(complex_edge)을 각각 구하는 제 3 서브단계,

   상기 0도 에지값(edge0)과, 45도 에지값(edge45)과, 90도 에지값(edge90)과, 135도 에지값(edge135)과, 혼합 에지값(complex_edge) 중 최대 에지값과 임계값(Th_sub_differece)을 비교하는 제 4 서브단계, 및

   상기 제 4 서브단계에서 최대 에지값이 임계값보다 크면 상기 최대값의 에지를 상기 블록의 대표 에지로 판정하는 제 5 서브단계를 포함한 것을 특징으로 하는 블록기반 영상 히스토그램 생성방법.
7. 제 6 항에 있어서,

   상기 제 4 서브단계에서 최대 에지값이 임계값보다 작으면 상기 블록을 단일톤 블록으로 판정하는 제 6 서브단계를 포함한 것을 특징으로 하는 블록기반 영상 히스토그램 생성방법.
8. 제 6 항에 있어서, 상기 제 3 서브단계는,

   상기 서브블록의 밝기 대표값들과 필터 계수값들을 아래의 식에 적용하여 0도 에지값(edge0)과, 45도 에지값(edge45)과, 90도 에지값(edge90)과, 135도 에지값(edge135)과, 혼합 에지값(complex_edge)을 구하는 단계인 것을 특징으로 하는 블록기반 영상 히스토그램 생성방법.

   [식]

   여기서, edge90_filter(i) 내지 complex_egde_filter(i)는 해당 필터의 계수값이다.
9. 제 4 항 내지 제 8 항 중 어느 한 항에 있어서, 상기 서브블록의 밝기 대표값은 픽셀들의 평균값인 것을 특징으로 하는 블록기반 영상 히스토그램 생성방법.
10. 제 4 항 내지 제 8 항 중 어느 한 항에 있어서, 상기 서브블록의 밝기 대표값은 픽셀들의 중앙값인 것을 특징으로 하는 블록기반 영상 히스토그램 생성방법.
11. 제 3 항에 있어서, 상기 제 2 단계에서 영상의 색상, 밝기 특징정보를 추출하는 단계는,

    블록의 색차 정보를 이용하여 의사 색조(ph)와 의사 색농도(ps)를 구하는 제 1 서브단계와,

    상기 의사 색조와 의사 색농도를 이용하여 유채색의 빈과 빈 사이의 선형 가중치(α)와, 유채색과 무채색 사이의 선형 가중치(β)를 구하는 제 2 서브단계,

    상기 의사 색농도값을 이용하여 상기 블록의 색상이 순수 색상인지 혹은 무채색을 포함한 어두운 유채색인 지를 판별하는 제 3 서브단계,

    상기 블록의 색상이 순수 색상이면, 상기 선형 가중치(α)를 이용하여 해당 색상 히스토그램 빈의 증가분을 계산하여 해당 색상 히스토그램을 갱신하는 제 4 서브단계, 및

    상기 블록의 색상이 어두운 유채색이면, 상기 선형 가중치(α)와 선형 가중치(β)를 이용하여, 해당 색상 히스토그램 빈의 증가분과 밝기 히스토그램 빈의 증가분을 계산하여 해당 색상 히스토그램과 밝기 히스토그램을 갱신하는 제 5 서브단계를 포함한 것을 특징으로 하는 블록기반 영상 히스토그램 생성방법.
12. 제 1 항 또는 제 2 항에 있어서, 영상의 적어도 2개 이상의 특징정보를 하나의 복합 히스토그램에 표현하는 것을 특징으로 하는 블록기반 영상 히스토그램 생성방법.
13. 컴퓨터에,

    변수 k를 초기화하고 상기 영상의 픽셀들을 하나의 그룹으로 묶어서 레벨 k의 블록 크기를 설정하는 제 1 단계와,

    상기 레벨 k의 모든 블록에 대해 블록 단위로 영상의 밝기, 색상, 에지 특징정보를 추출하여 해당 히스토그램을 갱신하는 제 2 단계와,

    상기 레벨 k의 블록들을 묶어서 레벨 k+1의 블록을 만들고, 상기 레벨 k의 영상 특징정보들을 병합하면서 상기 레벨 k+1의 모든 블록에 대해 블록 단위로 영상의 특징정보를 생성하여 해당 히스토그램을 갱신하는 제 3 단계,

    상기 k를 1씩 증가시키면서 모든 레벨에 대해 상기 제 3 단계를 반복 수행하는 제 4 단계를 포함하여, 영상 데이터의 색정보와 밝기 정보를 이용하여 영상 히스토그램을 생성하는 방법을 실현하기 위한 프로그램을 기록한 컴퓨터로 읽을 수 있는 기록매체.