평균 이동

평균 이동은 밀도 함수의 최대값을 찾기 위한 비모수 특성 공간 수학적 분석 기술, 이른바 모드 탐색 ^[1]알고리즘입니다.애플리케이션 도메인에는 컴퓨터 비전 및 이미지 ^[2]처리에서의 클러스터 분석이 포함됩니다.

역사

평균 교대 절차는 보통 1975년에 ^[3]후쿠나가와 호스테틀러가 작업한 것으로 알려져 있다.그러나 이는 1964년 ^[4]Schnell의 이전 작업을 연상시킨다.

개요

평균 이동은 해당 ^[1]함수에서 추출한 이산 데이터가 주어진 밀도 함수의 최대값(모드)을 찾기 위한 절차이다.이것은 반복적인 방법으로, $초기$ 추정치x(\ $displaystyle$ x $x$ 부터 시작합니다. 커널 $K(x_{i}-x)$ K $K(x_{i}-x)$ i - $K(x_{i}-x)$ $)(\displaystyle$ K $(x_{i}-x)}$ 를 지정합니다 $K(x_{i}-x)$ .이 함수는 평균의 재추정을 위한 인근 점의 무게를 결정합니다.일반적으로 현재 추정치까지의 거리에 있는 가우스 커널 K $K(x_{i}-x)=e^{-c||x_{i}-x||^{2}}$ i - $K(x_{i}-x)=e^{-c||x_{i}-x||^{2}}$ ) $=$ - $K(x_{i}-x)=e^{-c||x_{i}-x||^{2}}$ x $K(x_{i}-x)=e^{-c||x_{i}-x||^{2}}$ - $K(x_{i}-x)=e^{-c||x_{i}-x||^{2}}$ ({ $displaystyle$ K $(x_{i}-x ^{2$ 가 사용됩니다.K $(\displaystyle$ K $)$ 에 $K$ $의해$ 결정된 창 밀도의 가중 평균은 다음과 같습니다.

({displaystyle m(x)=sum frac {x_{i}\in N(x)}K(x_{i}-x)x_{i}{\in N(x)}K(x_{i}-x}}}})

$N(x)$ 서 N $x)$ { $displaystyle$ N $(x)}$ 은 $N(x)$ K $($ i - $K(x_{i}-x)\neq 0$ x) $K(x_{i}-x)\neq 0$ 0 $(x_{i}-neq$ 0 $K(x_{i}-x)\neq 0$ 의 포인트 세트인 x ${$ $displaystyle$ x $x$ 의 근방입니다.

m $m(x)-x$ - $m(x)-x$ (\ $displaystyle$ ^[3]m $(x)-x)$ 의 $m(x)-x$ $m(x)-x$ 를 Fukunaga 및 Hostetler에서는 평균 이동이라고 합니다.이제 평균 이동 알고리즘이 x $x\leftarrow m(x)$ ( $x\leftarrow m(x)$ ) { $displaystyle$ x $\left 화살표$ m $(x$ 을(를) 설정하고 m $)$ { $displaystyle$ m $(x)}$ 이 $m(x)$ (가) 수렴될 $m(x)$ 까지 추정을 반복합니다.

평균 이동 알고리즘은 많은 애플리케이션에서 널리 사용되어 왔지만, 고차원 공간에서 일반 커널을 사용하는 알고리즘의 수렴에 대한 확실한 증거는 아직 알려지지 ^[5]않았습니다.Aliyari Ghassabeh는 미분 가능하고 볼록하며 엄격하게 감소하는 프로파일 ^[6]함수를 사용하여 평균 이동 알고리즘의 수렴을 1차원으로 보여주었다.그러나 1차원 케이스는 실제 적용 범위가 한정되어 있습니다.또, 한정된 수의 정지점(또는 고립점)을 가지는 고차원의 알고리즘의 수렴이 ^[5]^[7]증명되었다.그러나, 일반적인 커널 함수가 유한한 정지점(또는 격리점)을 가지기에 충분한 조건은 제공되지 않았다.

가우스 평균 시프트는 기대-최대화 ^[8]알고리즘입니다.

세부 사항

데이터는n $(\$ $displaystyle$ n) $차원$ 유클리드 $공간$ X $(\displaystyle$ X $X$ 에 $n$ 포함된 유한 $집합$ S(\ $displaystyle$ S $)$ 로 $S$ 하고K(\ $displaystyle$ K $)$ 는 $K$ X(\ $displaystyle$ $X$ $X$ 에서 $\lambda$ 볼의 특성 함수인 플랫 커널로 $합니다$ .

$K(x)=begin{cases}1&{\text{if}}\x\leq \seconda \\0&{\text{if}}\x\>\seconda \\\end{cases}}$

알고리즘의 각 반복에서 s $s\leftarrow m(s)$ $s\leftarrow m(s)$ ( s $s\leftarrow m(s)$ ) \ $displaystyle$ s \ $left 화살표 m$ ( s )는 $s\leftarrow m(s)$ $s\in S$ $†$ S \ $displaystyle s$ \ $in$ S 에 대해 동시에 $s\in S$ 실행된다.첫 번째 질문은 희박한 표본 집합이 주어진 밀도 함수를 어떻게 추정하느냐이다.가장 간단한 접근법 중 하나는 데이터를 평활화하는 것입니다. 예를 들어 $너비$ h $(\displaystyle$ h $h$ 의 고정 커널을 사용하여 데이터를 정리하는 것입니다.

$f(x)=\sum _{i}K(x-x_{i})=\sum _{i}k\leftfrac {x_{i}\^{2}}\right$

$x_{i}$ 서 x i $(\$ })는 $x_{i}$ 입력 샘플이고 k $)$ { $displaystyle$ k $(r)}$ 는 $k(r)$ 커널 함수(또는 파르젠 창)입니다. $\displaystyle$ h는 $h$ 알고리즘의 유일한 파라미터로 대역폭이라고 불립니다.이 방법은 커널 밀도 추정 또는 파르젠 창 기술로 알려져 있습니다.위의 방정식에서 f $)$ { $style$ f $(x)}$ 를 $f(x)$ $f(x)$ 하면 경사 상승 또는 기타 최적화 기법을 사용하여 국소 최대값을 구할 수 있습니다.이 "brute force" 접근법의 문제는 고차원의 경우 전체 검색 공간에 대해 $f(x)$ f $x)\displaystyle f($ x)를 $f(x)$ 평가하는 것이 계산적으로 불가능해진다는 것이다.대신, 평균 시프트는 다중 재시작 구배 강하로 최적화 문헌에 알려진 바리안트를 사용합니다.로컬 최대값 $y_{k}$ $y_{k}$ 입력 $x_{1}$ $x_{1}$ 1 $x_{1}$ ({ $displaystyle x_{1$ 부터 시작하여 평균 시프트는 y $y_{k}$ ({ $displaystyle y_{$ $k$ $y_{k}$ $y_{k}$ 에서의 밀도 $f(x)$ (x $)$ 의 구배를 계산하고 그 방향으로 ^[9]오르막길을 걷습니다.

커널의 종류

커널 정의:X $(\displaystyle$ X $)$ 를 $X$ n $(\displaystyle$ n $)$ 차원 $n$ 유클리드 공간, $\mathbb {R} ^{n}$ n(\ $displaystyle \mathbb {R} ^{n$ 으로 $합니다$ .x $({$ $displaystyle$ x})의 $x$ 노름은 음수가 아닌 $\|x\|^{2}=x^{\top }x\geq 0$ 입니다 $\|x\|^{2}=x^{\top }x\geq 0$ $K:X\rightarrow \mathbb {R}$ kernel이 존재한다면 x $\|x\|^{2}=x^{\top }x\geq 0$ $K:X\rightarrow \mathbb {R}$ $\|x\|^{2}=x^{\top }x\geq 0$ $K:X\rightarrow \mathbb {R}$ $x$ x $\|x\|^{2}=x^{\top }x\geq 0$ 0 { $\|x\|^{2}=x^{\top }x\geq 0$ $displaystyle$ \ $x$ \ $K:X\rightarrow \mathbb {R}$ $^$ \ ^ { \ $top$ }x $\$ $geq$ $K:X\rightarrow \mathbb {R}$ $0$ $\|x\|^{2}=x^{\top }x\geq 0$ $} 입니다.$ }, $k:[0,\infty ]\rightarrow \mathbb {R}$ 다음과 같이 합니다 $.$

$K(x)=k(\|x\|^{2})$ ( $K(x)=k(\|x\|^{2})$ ) $K(x)=k(\|x\|^{2})$ ( $K(x)=k(\|x\|^{2})$ x $K(x)=k(\|x\|^{2})$ 2) $K(x)=k(\|x\|^{2})$ { $displaystyle$ K ( x ) = $k$ ( \ $x \^{2$ } $)$ } 、

k는 음이 아닙니다.
k는 증가하지 않습니다 $k(a)\geq k(b)$ $a<b$ ( $k(a)\geq k(b)$ ) $k(a)\geq k(b)$ k $k(a)\geq k(b)$ ( $k(a)\geq k(b)$ ) \ $displaystyle$ k ( $a$ ) \ $geq$ k ( b $k(a)\geq k(b)$ ) ( $a<b$ $a<b$ $displaystyle$ a < b ) $a<b$
k는 분할적으로 연속적이며 $\int _{0}^{\infty }k(r)\,dr<\infty \$ k ( $\int _{0}^{\infty }k(r)\,dr<\infty \$ ) $\int _{0}^{\infty }k(r)\,dr<\infty \$ r < $\int _{0}^{\infty }k(r)\,dr<\infty \$ \ $displaystyle \int$ _ { $0}^{\infty }k(r),dr$ <\ $infty$ \ $}$

평균 이동에 가장 자주 사용되는 커널 프로파일은 다음과 같습니다.

플랫 커널

$\displaystyle k(x)=cases{case}1&{\text{if}}\leq \casesda \\0&{\text{if}}\x>\caseda \\\end{cases}}$

가우스 커널

$k(x)=e^{-{\frac {x}{2\flac ^{2}}}}$

여기서 표준 편차 $\sigma$ $"\displaystyle\display$ "는 $\sigma$ 대역폭 $파라미터$ h $\displaystyle$ h로 $동작$ 합니다 $h$

적용들

클러스터링

2차원 공간의 점 집합을 고려합니다.C $\style$ C\displaystyle $C$ R을 $C$ 으로 $r$ 하여 $반지름$ r $\displaystyle$ r을 커널로 하는 원형 창을 가정합니다.평균 이동은 수렴될 때까지 이 커널을 고밀도 영역으로 반복적으로 이동시키는 언덕 오르기 알고리즘입니다.모든 이동은 평균 이동 벡터에 의해 정의됩니다.평균 이동 벡터는 항상 밀도의 최대 증가 방향을 가리킵니다.반복할 때마다 커널은 중심 또는 그 안에 있는 점의 평균으로 이동한다.이 평균을 계산하는 방법은 커널 선택에 따라 달라집니다.이 경우 평평한 커널 대신 가우스 커널이 선택되면 모든 포인트에 우선 커널 중심으로부터의 거리가 증가함에 따라 기하급수적으로 감소하는 가중치가 할당됩니다.컨버전스에서는, 시프트가 커널내에 더 많은 포인트를 수용할 수 있는 방향은 없습니다.

추적

평균 이동 알고리즘은 시각적 추적에 사용할 수 있습니다.가장 간단한 알고리즘은 이전 영상에서 객체의 색상 히스토그램을 기반으로 새 영상에서 신뢰 맵을 생성하고 평균 이동을 사용하여 객체의 이전 위치 근처에서 신뢰 맵의 피크를 찾습니다.신뢰도 맵은 새 영상의 확률 밀도 함수이며, 새 영상의 각 픽셀을 이전 영상의 개체에서 발생하는 픽셀 색상의 확률인 확률로 할당합니다.커널 기반 객체 추적,^[10] 앙상블 추적,^[11] CAMshift와 같은 몇 가지 알고리즘이 이 아이디어를 확장합니다.

스무딩

$x_{i}$ i $(\$ }) $z_{i},i=1,...,n,$ z $z_{i},i=1,...,n,$ $z_{i},i=1,...,n,$ $z_{i},i=1,...,n,$ , $z_{i},i=1,...,n,$ $z_{i},i=1,...,n,$ ${\displaystyle z_{i$ }, $i=1,$ ..., $n,}$ 을 $z_{i},i=1,...,n,$ (를) $공동$ 공간 범위 도메인의 d $(\displaystyle$ d $)$ 차원 $d$ 입력 및 필터링된 이미지 픽셀로 $x_{i}$ .각 픽셀에 대해

$j=1$ j $j=1$ { $displaystyle$ j $=1$ } $j=1$ 및 $y_{i,1}=x_{i}$ $y_{i,1}=x_{i}$ $=$ $y_{i,1}=x_{i}$ i $y_{i,1}=x_{i}$ { $displaystyle y_{i,1$ }= $x_{i}$
y $y_{i,j+1}$ $=$ $y=y_{i,c}$ $y_{i,j+1}$ i , $y=y_{i,c}$ c \ $display$ y $y=y_{i,c}$ $y_{i,j+1}$ { $i$ $y_{i,j+1}$ , $cdot$ $m(\cdot )$ } 까지의 m $m(\cdot )$ ( $m(\cdot )$ ){ $display$ m ( \ $cdot$ )에 $m(\cdot )$ $m(\cdot )$ $y_{i,j+1}$ i $y=y_{i,c}$ , $+$ ( \ $display$ y $_$ { $i$ , c $y=y_{i,c}$ } )를 $y_{{i,j+1}}$ $y=y_{i,c}$ 합니다.
$z_{i}=(x_{i}^{s},y_{i,c}^{r})$ i $=$ ( $z_{i}=(x_{i}^{s},y_{i,c}^{r})$ $z_{i}=(x_{i}^{s},y_{i,c}^{r})$ , $z_{i}=(x_{i}^{s},y_{i,c}^{r})$ i , $z_{i}=(x_{i}^{s},y_{i,c}^{r})$ r $){displaystyle z_{i$ }=( $x_{i}^{s}, y_{i,c$ }^r $z_{i}=(x_{i}^{s},y_{i,c}^{r})$ 을 $z_{i}=(x_{i}^{s},y_{i,c}^{r})$ 합니다.위 첨자 s와 r은 각각 벡터의 공간 및 범위 성분을 나타냅니다.이 할당은 공간 위치 축의 필터링된 데이터에 y $y_{i,c}^{r}$ $y_{i,c}^{r}$ \ $displaystyle y_{i,c}^{r$ 의 $y_{i,c}^{r}$ 포인트의 범위 구성요소가 포함되도록 지정합니다.

힘

평균 이동은 실제 데이터 분석에 적합한 애플리케이션 독립적인 도구입니다.
데이터 클러스터에서 미리 정의된 모양을 가정하지 않습니다.
임의의 피쳐 공간을 처리할 수 있습니다.
이 순서는 대역폭이라는 단일 파라미터의 선택에 의존합니다.
대역폭/창 크기 'h'는 k-평균과 달리 물리적 의미를 가집니다.

약점

창 크기 선택은 단순하지 않습니다.
창 크기가 적절하지 않으면 모드가 병합되거나 추가 "shallow" 모드가 생성될 수 있습니다.
적응형 창 크기를 사용해야 하는 경우가 많습니다.

유용성

알고리즘의 바리안트는 머신 러닝 및 이미지 처리 패키지에 포함되어 있습니다.

ELKI. 클러스터링 알고리즘이 많은 Java 데이터 마이닝 도구.
ImageJ. 평균 시프트 필터를 사용한 이미지 필터링.
mlpack. 듀얼 트리 알고리즘 기반의 효율적인 구현.
OpenCV에는 cvMeanShift 메서드를 통한 평균 이동 구현이 포함되어 있습니다.
Orfeo 툴박스C++ 실장
Scikit-learn Numpy/Python 구현에서는 볼 트리를 사용하여 효율적인 인접 포인트 검색

「」를 참조해 주세요.

레퍼런스

^ ^a ^b Cheng, Yizong (August 1995). "Mean Shift, Mode Seeking, and Clustering". IEEE Transactions on Pattern Analysis and Machine Intelligence. 17 (8): 790–799. CiteSeerX 10.1.1.510.1222. doi:10.1109/34.400568.
^ Comaniciu, Dorin; Peter Meer (May 2002). "Mean Shift: A Robust Approach Toward Feature Space Analysis". IEEE Transactions on Pattern Analysis and Machine Intelligence. 24 (5): 603–619. CiteSeerX 10.1.1.160.3832. doi:10.1109/34.1000236.
^ ^a ^b Fukunaga, Keinosuke; Larry D. Hostetler (January 1975). "The Estimation of the Gradient of a Density Function, with Applications in Pattern Recognition". IEEE Transactions on Information Theory. 21 (1): 32–40. doi:10.1109/TIT.1975.1055330.
^ Schnell, P. (1964). "Eine Methode zur Auffindung von Gruppen". Biometrische Zeitschrift (in German). 6 (1): 47–48. doi:10.1002/bimj.19640060105.
^ ^a ^b Aliyari Ghassabeh, Youness (2015-03-01). "A sufficient condition for the convergence of the mean shift algorithm with Gaussian kernel". Journal of Multivariate Analysis. 135: 1–10. doi:10.1016/j.jmva.2014.11.009.
^ Aliyari Ghassabeh, Youness (2013-09-01). "On the convergence of the mean shift algorithm in the one-dimensional space". Pattern Recognition Letters. 34 (12): 1423–1427. arXiv:1407.2961. doi:10.1016/j.patrec.2013.05.004. S2CID 10233475.
^ Li, Xiangru; Hu, Zhanyi; Wu, Fuchao (2007-06-01). "A note on the convergence of the mean shift". Pattern Recognition. 40 (6): 1756–1762. doi:10.1016/j.patcog.2006.10.016.
^ Carreira-Perpinan, Miguel A. (May 2007). "Gaussian Mean-Shift Is an EM Algorithm". IEEE Transactions on Pattern Analysis and Machine Intelligence. 29 (5): 767–776. doi:10.1109/tpami.2007.1057. ISSN 0162-8828. PMID 17356198. S2CID 6694308.
^ Richard Szeliski, 컴퓨터 비전, 알고리즘 및 애플리케이션, Springer, 2011
^ Comaniciu, Dorin; Visvanathan Ramesh; Peter Meer (May 2003). "Kernel-based Object Tracking". IEEE Transactions on Pattern Analysis and Machine Intelligence. 25 (5): 564–575. CiteSeerX 10.1.1.8.7474. doi:10.1109/tpami.2003.1195991.
^ Avidan, Shai (2005). Ensemble tracking. 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR'05). Vol. 2. San Diego, California: IEEE. pp. 494–501. doi:10.1109/CVPR.2005.144. ISBN 978-0-7695-2372-9. PMID 17170479. S2CID 1638397.
^ Gary Bradski(1998) 지각 사용자 인터페이스에서 사용하는 컴퓨터 비전 얼굴 추적 2012-04-17년 인텔 테크놀로지 저널 No.2에서 아카이브되었습니다.
^ Emami, Ebrahim (2013). "Online failure detection and correction for CAMShift tracking algorithm". 2013 8th Iranian Conference on Machine Vision and Image Processing (MVIP). 2013 Iranian Conference on Machine Vision and Image Processing (MVIP). Vol. 2. IEEE. pp. 180–183. doi:10.1109/IranianMVIP.2013.6779974. ISBN 978-1-4673-6184-2. S2CID 15864761.

[PAMI95-1] Cheng, Yizong (August 1995). "Mean Shift, Mode Seeking, and Clustering". IEEE Transactions on Pattern Analysis and Machine Intelligence. 17 (8): 790–799. CiteSeerX 10.1.1.510.1222. doi:10.1109/34.400568.

[PAMI02-2] Comaniciu, Dorin; Peter Meer (May 2002). "Mean Shift: A Robust Approach Toward Feature Space Analysis". IEEE Transactions on Pattern Analysis and Machine Intelligence. 24 (5): 603–619. CiteSeerX 10.1.1.160.3832. doi:10.1109/34.1000236.

[Fukunaga-3] Fukunaga, Keinosuke; Larry D. Hostetler (January 1975). "The Estimation of the Gradient of a Density Function, with Applications in Pattern Recognition". IEEE Transactions on Information Theory. 21 (1): 32–40. doi:10.1109/TIT.1975.1055330.

[4] Schnell, P. (1964). "Eine Methode zur Auffindung von Gruppen". Biometrische Zeitschrift (in German). 6 (1): 47–48. doi:10.1002/bimj.19640060105.

[:0-5] Aliyari Ghassabeh, Youness (2015-03-01). "A sufficient condition for the convergence of the mean shift algorithm with Gaussian kernel". Journal of Multivariate Analysis. 135: 1–10. doi:10.1016/j.jmva.2014.11.009.

[6] Aliyari Ghassabeh, Youness (2013-09-01). "On the convergence of the mean shift algorithm in the one-dimensional space". Pattern Recognition Letters. 34 (12): 1423–1427. arXiv:1407.2961. doi:10.1016/j.patrec.2013.05.004. S2CID 10233475.

[7] Li, Xiangru; Hu, Zhanyi; Wu, Fuchao (2007-06-01). "A note on the convergence of the mean shift". Pattern Recognition. 40 (6): 1756–1762. doi:10.1016/j.patcog.2006.10.016.

[8] Carreira-Perpinan, Miguel A. (May 2007). "Gaussian Mean-Shift Is an EM Algorithm". IEEE Transactions on Pattern Analysis and Machine Intelligence. 29 (5): 767–776. doi:10.1109/tpami.2007.1057. ISSN 0162-8828. PMID 17356198. S2CID 6694308.

[9] Richard Szeliski, 컴퓨터 비전, 알고리즘 및 애플리케이션, Springer, 2011

[PAMI03-10] Comaniciu, Dorin; Visvanathan Ramesh; Peter Meer (May 2003). "Kernel-based Object Tracking". IEEE Transactions on Pattern Analysis and Machine Intelligence. 25 (5): 564–575. CiteSeerX 10.1.1.8.7474. doi:10.1109/tpami.2003.1195991.

[avidan2001-11] Avidan, Shai (2005). Ensemble tracking. 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR'05). Vol. 2. San Diego, California: IEEE. pp. 494–501. doi:10.1109/CVPR.2005.144. ISBN 978-0-7695-2372-9. PMID 17170479. S2CID 1638397.

[12] Gary Bradski(1998) 지각 사용자 인터페이스에서 사용하는 컴퓨터 비전 얼굴 추적 2012-04-17년 인텔 테크놀로지 저널 No.2에서 아카이브되었습니다.

[Emami2001-13] Emami, Ebrahim (2013). "Online failure detection and correction for CAMShift tracking algorithm". 2013 8th Iranian Conference on Machine Vision and Image Processing (MVIP). 2013 Iranian Conference on Machine Vision and Image Processing (MVIP). Vol. 2. IEEE. pp. 180–183. doi:10.1109/IranianMVIP.2013.6779974. ISBN 978-1-4673-6184-2. S2CID 15864761.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

Search

평균 이동

네임스페이스

더

목차

역사

개요

세부 사항

커널의 종류

적용들

클러스터링

추적

스무딩

힘

약점

유용성

「」를 참조해 주세요.

레퍼런스

Search

평균 이동

역사

개요

세부 사항

커널의 종류

적용들

클러스터링

추적

스무딩

힘

약점

유용성

「 」를 참조해 주세요.

레퍼런스

「」를 참조해 주세요.