오쓰의 방법

Otsu 알고리즘을 사용하여 임계값화된 이미지 예제

원본 이미지

컴퓨터 비전과 이미지 처리에서는 오쓰 노부유키(大大大, 오쓰 노부유키)의 이름을 딴 오쓰의 방법이 사용되어 자동 이미지 임계화를 실시한다.^[1]가장 간단한 형태에서 알고리즘은 픽셀을 포그라운드와 배경의 두 클래스로 분리하는 단일 강도 임계값을 반환한다.이 임계값은 클래스 내 강도 분산을 최소화하거나 클래스 간 분산을 최대화하여 동등하게 결정된다.^[2]오쓰의 방법은 피셔의 판별 분석의 1차원 이산형 아날로그로 젠크스 최적화 방법과 관련이 있으며, 강도 히스토그램에 대해 수행되는 전지구적으로 최적의 k-평균에^[3] 해당한다.다단계 임계치로의 확장은 원래 논문에서 설명되었으며,^[2] 이후 연산적으로 효율적인 구현이 제안되었다.^[4][5]

오쓰의 방법

오쓰의 방법 시각화

알고리즘은 두 클래스의 가중된 분산 합으로 정의된 클래스 내 분산을 최소화하는 임계값을 철저히 검색한다.

${\displaystyle \w}^{2}(t)=\omega _{0}(t)\ma_{0}^{0}^{2}(t)+\omega _{1}(t)\{1}^{1}(t)}$

가중치 ${\displaystyle {0\mathrm{}}_{}}$ ${\$$}$ 및 $$${\displaystyle {\Omega \mathrm{}}_{}}$ 1 ${\$ $\$$omega_$${$1$}}{$1}:{1$}{$1}}은(는$)$ $임계값$ t {\$displaystyle$ \$sigma$$$_${0$}^{${\displaystyle 0_{}^{}}$$}}}}}}$과$(와$) ${\displaystyle {\mathrm{}}_{}^{}}$ ${\$는 이 두 클래스의 분산이다$$$$.

클래스 확률 $\Omega {\displaystyle {}_{}}$ ${\displaystyle {0\mathrm{}}_{}}$, ${\displaystyle 1_{}}$( ${\displaystyle t}$) ${\displaystyle \omega _{0,1}(t)}$은(는) $히스토그램$의$$L {\$displaystyle L}$ 빈에서$$ 계산된다$$.

${\displaystyle {\begin}\i1}t(t)&=\sum _{i=0}^{t-1p(i)\[4pt]\omega_{1}(t)&=\sum _{i=t}^{L-1p(i)\ended}}}}}}}}$

2개 클래스의 경우 클래스 내 분산을 최소화하는 것은 클래스 간 분산을 최대화하는 것과 동일하다.^[2]

${\displaystyle {\begin{aligned}\sigma _{b}^{2}(t)&=\sigma ^{2}-\sigma _{w}^{2}(t)=\omega _{0}(t)(\mu _{0}-\mu _{T})^{2}+\omega _{1}(t)(\mu _{1}-\mu _{T})^{2}\\&=\omega _{0}(t)\omega _{1}(t)\left[\mu _{0}(t)-\mu _{1}(t)\right]^{2}\end{aligned}}}$

클래스 확률 $\Omega {\displaystyle }$ ${\displaystyle \omega}$ 및 클래스는$$ ${\displaystyle \mu }$을$($를) 의미하며 여기서 클래스는 $\mu {\displaystyle {}_{}}$ 0(${\displaystyle {t\mathrm{}}_{}}$)${\displaystyle$ $\$$mu _{0$$}($$t)},$$$μt는 다음과$같다$.

${\displaystyle {\begin{aligned}\mu _{0}(t)&={\frac {\sum _{i=0}^{t-1}ip(i)}{\omega _{0}(t)}}\\[4pt]\mu _{1}(t)&={\frac {\sum _{i=t}^{L-1}ip(i)}{\omega _{1}(t)}}\\\mu _{T}&=\sum _{i=0}^{L-1}ip(i)\end{aligned}}}$

다음과 같은 관계를 쉽게 확인할 수 있다.

${\displaystyle {\begin{ligned}\mu _{0}\mu_{0}\mu_{1}\mu_{1}=\mu_{T}\mai_{0}+\omega _{1}&=1\ended}}}}}}}}}"$

클래스 확률과 클래스 평균은 반복적으로 계산할 수 있다.이 아이디어는 효과적인 알고리즘을 산출한다.

알고리즘.

1. 각 강도 수준의 히스토그램 및 확률 계산
2. 초기 $\Omega {\displaystyle {}_{}}$ ${\displaystyle i_{}}$( ${\displaystyle 0}$) ${\displaystyle \omega _{i}(0)$ 및$$ ${\displaystyle {\mu i}_{}}$(${\displaystyle 0}$) ${\displaystyle \mu _{i}(0)$ 설정
3. 가능한 모든 임계값 $t{\displaystyle }$= ${\displaystyle 1}$,${\displaystyle }$… ${\displaystyle t=1,\ldots }$개의$$ 최대 강도를 단계별로 수행하십시오.
   1. 업데이트 $\Omega {\displaystyle {}_{}}$ ${\displaystyle i_{}}$ ${\$ 및$$ $\mu {\displaystyle {}_{}}$ ${\displaystyle i_{}}$ ${\$
   2. 계산 $\sigma {\displaystyle {}_{}^{}}$ ${\displaystyle b_{}^{}}$ ${\displaystyle {}_{}^{}}$( ${\displaystyle t}$) ${\displaystyle \sigma _{b}^{2}(t)}$
4. 원하는 임계값은 최대 $\sigma {\displaystyle {}_{}^{}}$ ${\displaystyle b_{}^{}}$ ${\displaystyle {}_{}^{}}$( ${\displaystyle t}$) ${\displaystyle \sigma _{b}^{2}(t)}$에 해당함

MATLAB 또는 옥타브 구현

histogramCounts는 그레이스케일 영상의 서로 다른 그레이 레벨(일반적으로 8비트 영상의 경우) 256개 요소 히스토그램이다.레벨은 이미지의 임계값(더블)이다.

기능 수준)otsu(histogramCounts)총=sum(histogramCounts), 픽셀의 이미지%%OTSU 자동 경계화 최고=256, sumB=0;wB=0;최대=0.0, sum1)dot(0:top-1, histogramCounts). ii에=1:최고 wF)총-wB;만약wB>0&&wF>0mF)(sum1-sumB)/wF, val)wB*wF*((sumB/wB)-mF%총 수 cm이다.*((sumB/wB) - mF; (val >= 최대 ) 수준 = ii, 최대 = val, 끝 wB = wB + 히스토그램 카운트(ii); sumB = sumB + (i-1) * 히스토그램 카운트(iii); 끝

Matlab에는 기능이 내장되어 있다.graythresh()그리고multithresh()각각 Otsu의 방법과 Multi Otsu의 방법으로 구현되는 이미지 처리 도구 상자.

제한 사항

오쓰의 방법은 히스토그램이 두 봉우리 사이에 깊고 날카로운 계곡과 함께 이원분포일 때 잘 된다.그러나 물체 영역이 배경 영역에 비해 작을 경우 히스토그램은 더 이상 이원성을 나타내지 않는다.^[6]평균 차이에 비해 물체 및 배경 강도의 편차가 크거나 영상이 가법 노이즈에 의해 심하게 손상되면 회색 수준 히스토그램의 날카로운 계곡이 저하된다.그러면 Otsu의 방법에 의해 결정되는 잘못된 임계값은 분할 오류를 초래한다. (여기서 우리는 객체 크기를 전체 이미지 영역에 대한 객체 영역의 비율로 정의하고 평균 차이는 객체와 배경의 평균 강도 차이로 정의한다.

경험적 결과, 객체 분할에 사용되는 글로벌 임계값 기법(오츠 방법 포함)의 성능은 작은 객체 크기, 전경과 배경 픽셀의 작은 평균 차이, 객체에 속하는 픽셀과 배경에 속하는 픽셀의 큰 차이, 큰 양에 의해 제한된다는 것을 알 수 있다.f 소음 ^[7]등

개선사항

오쓰의 방법의 한계를 해결하기 위해 다양한 연장이 개발되었다.대표적인 확장법은 2차원 오츠(Otsu)의 방법으로, 노이즈가 있는 영상에서 객체 분할 작업에 더 좋은 성능을 발휘한다.여기서 주어진 픽셀의 강도 값을 인접 지역의 평균 강도와 비교하여 분할 결과를 개선한다.^[8]

각 픽셀에서 근방의 평균 회색 수준 값이 계산된다.주어진 픽셀의 그레이 레벨을 $L{\displaystyle }$ ${\displaystyle L}$ 이산값으로$$ 나누고 평균 그레이 레벨도 동일한 $L{\displaystyle }$ ${\displaystyle L}$ 값으로$$ 나누도록 한다.그러면 픽셀 그레이 레벨과 주변 평균$({\displaystyle i}$, j $){\displaystyle (i,$$j$$)\}.$ 각 쌍은 L ${\displaystyle \times }$ ${\displaystyle L}$ ${\displaystyle L} 가능$한 $2차원$ 빈 중 하나에 속한다.한 쌍$($${\displaystyle i}$, j ) {\$displaystyle$ ($i,$ j $){$의 총 발생 횟수$($$주파수)$를 이미지 $N{\displaystyle }$ ${\displaystyle N$의 총 픽셀 수로 나눈 값, 2차원 히스토그램에서 공동 확률 질량 함수를 정의한다.

${\displaystyle P_{ij}={\frac {f_{ij}}{{N}}},\qquad \sum _{i=0}^{j=0}^{L-1}P_{ij}=1}{ij}=1}.$

그리고 2차원 오쓰의 방법은 다음과 같이 2차원 히스토그램을 바탕으로 개발된다.

두 등급의 확률은 다음과 같이 나타낼 수 있다.

${\displaystyle {\begin{aligned}\omega _{0}&=\sum _{i=0}^{s-1}\sum _{j=0}^{t-1}P_{ij}\\\omega _{1}&=\sum _{i=s}^{L-1}\sum _{j=t}^{L-1}P_{ij}\end{aligned}}}$

두 클래스의 강도 평균 값 벡터와 총 평균 벡터는 다음과 같이 표현할 수 있다.

${\displaystyle {\signified}\mu _{0}&=[\mu _{0i}\mu _{0j}]^{T}=\left[\sum _{i=0}^{s-1}\sum _{j=0}^{t-1}i{\frac {P_{ij}}{\omega _{0}}},\sum _{i=0}^{s-1}\sum _{j=0}^{t-1}j{\frac {P_{ij}}{\omega _{0}}}\right]^{T}\\\mu _{1}&=[\mu _{1i},\mu _{1j}]^{T}=\left[\sum _{i=s}^{L-1}\sum _{j=t}^{L-1}i{\frac {P_{ij}}{\omega _{1}}},\sum _{i=s}^{L-1}\sum _{j=t}^{L-1}j{\frac {P_{ij}}{\omega _{1}}}\right]^{T}\\\mu _{T}&=[\mu _{Ti}\mu _{Tj}]^{T}=\left[\sum _{i=0}^{L-1}\sum _{j=0}^{L-1}iP_{ij}}\sum _{i=0}^{j-1}jP_{ij}\right]^^{T}\end{aigned}}$

대부분의 경우 대각선 이탈 확률은 무시할 수 있으므로 다음과 같이 쉽게 확인할 수 있다.

${\displaystyle \omega _{0}+\omega _{1}\cong 1}$

${\displaystyle \omega _{0}\mu _{0}+\omega _{1}\mu _{1}\cong \mu _{T}}$

클래스 간 이산 행렬은 다음과 같이 정의된다.

${\displaystyle S_{b}=\sum _{k=0}^{1}\omega_{k}[(\mu_{k}-\mu_{T})(\mu_{k}-\mu_{T})^{T}}}}}}}$

이산 행렬의 추적은 다음과 같이 표현할 수 있다.

${\displaystyle {\begin{aligned}&\operatorname {tr} (S_{b})\\[4pt]={}&\omega _{0}[(\mu _{0i}-\mu _{Ti})^{2}+(\mu _{0j}-\mu _{Tj})^{2}]+\omega _{1}[(\mu _{1i}-\mu _{Ti})^{2}+(\mu _{1j}-\mu _{Tj})^{2}]\\[4pt]={}&{\frac {(\mu _{Ti}\omega _{0}-\mu _{i})^{2}+(\mu _{Tj}\omega _{0}-\mu _{j})^{2}}{\omega _{0}(1-\omega _{0})}}\end{aligned}}}$

어디에

${\displaystyle \mu _{i}=\sum _{i=0}^{s-1}\sum _{j=0}^{t-1}iP_{ij}}}}$

${\displaystyle \mu _{j}=\sum _{i=0}^{s-1}\sum _{j=0}^{t-1}jP_{ij}}}}$

1차원 Otsu의 방법과 마찬가지로 최적의 임계값$({\displaystyle s}$, t )${\displaystyle(s,t)}$은 ${\displaystyle \mathrm{tr}}$ ${\displaystyle (}$S ${\displaystyle b_{}}$) ${\displaystyle \operatorname {tr}(S_{b})$을 최대화하여 얻는다$$$.$

알고리즘.

$s{\displaystyle }$ ${\displaystyle s}$과 $t{\displaystyle }$ ${\displaystyle t}$은 1차원 오쓰의 방법과 유사한 반복적으로 얻어진다$$.$s{\displaystyle }$ ${\displaystyle s}$ 및$$ $t{\displaystyle }$ ${\displaystyle t}$의 값은 ${\displaystyle \mathrm{tr}}$ ${\displaystyle (S_{}}$ b${\displaystyle {}_{}}$) ${\displaysty \operatorname {tr}(S_{b})$의 최대값을 얻을 때까지 변경된다$.$

맥스.,s,t = 0; 을 위해 ss: 0 로 L-1 하다     을 위해 tt: 0 로 L-1 하다         평가하다 tr(S_b);         만일 tr(S_b) > 맥스.             맥스. = tr(S,b);             s = ss;             t = tt;         종지부를 찍다 만일     종지부를 찍다 을 위해 종지부를 찍다 을 위해 돌아오다 s,t; 

${\displaystyle \mathrm{tr}}$ ${\displaystyle }$(${\displaystyle {}_{}}$ ${\displaystyle b_{}}$) ${\displaystyle \operatorname {tr}(S_{b})$을 평가하기 위해 빠른 재귀 동적 프로그래밍 알고리즘을 사용하여 시간 성능을 개선할 수 있다는 점에 유의하십시오$.$^[9]그러나 동적 프로그래밍 접근법에도 불구하고, 2d Otsu의 방법은 여전히 시간 복잡성이 크다.따라서, 계산 비용을 줄이기 위해 많은 연구가 이루어졌다.^[10]

If summed area tables are used to build the 3 tables, sum over ${\displaystyle P_{ij}}$, sum over ${\displaystyle i*P_{ij}}$, and sum over ${\displaystyle j*P_{ij}}$, then the runtime complexity is the maximum of (O(N_pixels), O(N_bins*N_bins)).임계값 측면에서 거친 분해능만 필요한 경우 N_bins를 줄일 수 있다는 점에 유의하십시오.

매트랩 구현

함수 입력 및 출력:

hists는 그레이스케일 값과 근린 평균 그레이스케일 값 쌍의 ${\displaystyle 256}$× ${\displaystyle 256}${\$displaystyle 256\times 256}$ 2D 히스토그램이다$$.

총계는 주어진 image.it에 있는 쌍의 수입니다. 각 방향에서 2D-히스토그램의 빈의 수로 결정된다.

임계값은 얻어진 임계값이다.

함수 임계값 = otsu_2D(hists, total) 최대값 = 0.0, 임계값 = 0, helperVec = 0:255, mu_t0 = sum(repmat(helperVec',1,256)*hists); mu_t1 = sum(repmat(helperVec,256,1)*hists)); p_0 = zeros(256); mu_i = p_0; mu_j = p_0; for ii = 1:256  for jj = 1:256  if jj == 1  if ii == 1  p_0(1,1) = hists(1,1);  else  p_0(ii,1) = p_0(ii-1,1) + hists(ii,1);  mu_i(ii,1) = mu_i(ii-1,1)+(ii-1)*hists(ii,1);  mu_j(ii,1) = mu_j(ii-1,1);  end  else  p_0(ii,jj) = p_0(ii,jj-1)+p_0(ii-1,jj)-p_0(ii-1,jj-1)+hists(ii,jj); % THERE IS A BUG HERE. INDICES IN MATLAB MUST BE HIGHER THAN 0. ii-1 is not valid  mu_i(ii,jj) = mu_i(ii,jj-1)+mu_i(ii-1,jj)-mu_i(ii-1,jj-1)+(ii-1)*hists(ii,jj);  mu_j(ii,jj) = mu_j(ii,jj-1)+mu_j(ii-1,jj)-mu_j(ii-1,jj-1)+(jj-1)*hists(ii,jj);  end  if (p_0(ii,jj) == 0)  continue;  end  if (p_0(ii,jj) == total)  break;  end  tr = ((mu_i(ii,jj)-p_0(ii,jj)*mu_t0)^2 + (mu_j(i,ii)-p_0(i,i)*mu_t1)^2)/(p_0(ii,t1)^2)/(p_0(i-p_0)(i,i)*); (tr >= 최대 임계값 = ii; 최대 = tr; 엔드 엔드 엔드 엔드)

참조

외부 링크

• Script-Fu(Script-Fu)를 이용한 Otsu의 KIMP-plugin 역점화 방법 구현
• 임계값 지정에 대한 강의 노트 – Otsu 방법에 대한 설명
• Otsu의 방법을 사용하여 임계값을 수행하는 ImageJ용 플러그인
• 오쓰의 방법에 대한 전체 설명과 작업 예시 및 자바 구현
• ITK에서의 Otsu 방법의 구현
• C#의 Otsu 임계값 설정 – 설명을 포함한 간단한 C# 구현
• MATLAB를 이용한 Otsu의 방법
• Python에서 Scikit-image로 Otsu 임계값 설정