랜덤 워커 알고리즘

랜덤 워커 알고리즘은 영상 분할 알고리즘입니다.알고리즘의 ^[1]첫 번째 설명에서 사용자는 소수의 픽셀에 기존의 라벨(시드라고 함)로 인터랙티브하게 라벨을 붙입니다(예: "객체" 및 "배경").라벨이 없는 픽셀은 각각 랜덤 워커를 방출하는 것으로 상상되며, 각 픽셀의 랜덤 워커가 먼저 각 라벨을 가진 시드에 도착할 확률은 계산된다.즉, 사용자가 각각 다른 라벨을 가진 K개의 시드를 배치하면 각 픽셀에 대해 랜덤 워커가 픽셀을 떠날 확률을 계산할 필요가 있다.각각의 씨앗에 도착하지 않는다.이러한 확률은 선형 방정식의 시스템을 풀어서 분석적으로 결정될 수 있다.각 픽셀에 대해 이러한 확률을 계산한 후 랜덤 워커를 보낼 가능성이 가장 높은 라벨에 픽셀이 할당됩니다.이미지는 그래프로 모델링되며, 각 픽셀은 인접한 픽셀에 가장자리로 연결된 노드에 대응하며, 픽셀 간의 유사성을 반영하도록 가장자리에 가중치가 부여됩니다.따라서 랜덤 워크는 가중 그래프에서 발생한다(그래프의 랜덤^[2] 워크에 대한 소개는 도일과 스넬 참조).

초기 알고리즘은 영상 분할을 위한 대화형 방법으로 공식화되었지만 데이터 충실도 조건(예: 강도 이전)^[3]을 고려할 때 완전 자동 알고리즘으로 확장되었다.다른 애플리케이션으로도 확장되었습니다.

이 알고리즘은 처음에는 Leo Grady에 의해 컨퍼런스^[4] 페이퍼로 발표되었고 나중에는 저널 ^[1]페이퍼로 발표되었습니다.

수학

알고리즘은 랜덤 워크의 관점에서 설명되었지만, 각 노드가 시드로 랜덤 워커를 보낼 확률은 그래프 Laplacian 행렬로 희박한 양의 유한 선형 방정식 시스템을 풀어서 분석적으로 계산할 수 있으며, 이는 $변수{\displaystyle }$ L$\displaystyle$L로 나타낼 수 있다. 알고리즘은 sh이었다.임의 개수의 라벨(표시)에 적용할 수 있지만, 여기서 설명하는 것은 두 개의 라벨(설명 단순성)에 관한 것입니다.

이미지가 그래프로 표현되어 있으며, 각 ${\displaystyle {노드}_{}}$vi({$displaystyle v_{$i$$})는 픽셀에 관련되어 있으며, 각 ${\displaystyle {\mathrm{에지}}_{}}$ ei$({displaystyle e_{ij})$는 인접한$$ 픽셀 $({$와 $({$를 접속하고 있다고 가정합니다.엣지 웨이트는 노드 유사성을 인코딩하는 데 사용되며, 이는 이미지 강도, 색상, 텍스처 또는 기타 의미 있는 기능의 차이에서 파생될 수 있습니다.예를 들어 $vi$에서 이미지 $강도{\displaystyle {}_{}}$ $(\$$displaystyle$ $g_$${i$를 사용하는 경우 엣지 가중치 함수를 사용하는 것이 일반적입니다.

$({displaystyle w_{i}=\exp(g_{i}-g_{j})^{2}\오른쪽)}.}$

그런 다음 노드, 가장자리 및 가중치를 사용하여 그래프 라플라시안 행렬을 구성할 수 있습니다.

랜덤 워커 알고리즘은 에너지를 최적화합니다.

${\displaystyle Q(x)=x^{T}Lx=\sum _{e_{ij}w_{ij}\left(x_{i}-x_{j}\right)^{2}$

$여기$서 ${\displaystyle x_{}}$ i$(\$})는$$ 그래프의 각 노드와 관련된 실제 값 변수를 나타내며 최적화는 ${\displaystyle {vi}_{}}$ ${\displaystyle {}_{}}$(\$displaystyle v_{i}\in$ F$$$)$의 경우 $xi$${\displaystyle {}_{}}$$(\displaystyle x_$${$i}=1)과 ${\displaystyle v_{}}$(\$displaystyle$ v_in F$)$의 ${\displaystyle \mathrm{경우}}$ x = 0(\displaystyle $x_{i$}=$0$$)$에 $의해{\displaystyle {}_{}}$ $제한$됩니다${\displaystyle {}_{}}$$여기$서$$F(\$displaystyle$ F$)$와 B$(\displaystyle$ B$)$는 각각 전경 시드 및 배경 시드 세트를 나타냅니다.S$({displaystyle$ S$})$가 시드된 노드 세트($예{\displaystyle }$: S ${\displaystyle =}$ $F$ B {\$displaystyle$S$$= F\$cup$ B$\})$를 $나타내도록{\displaystyle }$ 하고 S$({$를 시드되지 않은 노드 세트(예: $S{\displaystyle }$ ${\displaystyle =}$ $V\cup$ S${\displaystyle \stackrel{}{)}}$를 나타냅니다.es) 그러면 에너지 최소화 문제의 최적성이 다음 솔루션에 의해 주어집니다.

${\displaystyle L_{\overline {S}}, {\overline {S}}x_{\overline {S}=-L_{\overline {S}, S}x_{S}}}$

여기서 첨자는 각 세트에 의해 색인화된 그래프 Laplacian $행렬 L$의 부분을$$ 나타내기 위해 사용됩니다.

알고리즘에 우도(단일) 항을 통합하기 위해 에서 에너지를 최적화할 수 있음을 보여주었다.

${\displaystyle Q(x)=x{T}Lx+\gamma \left(1-x)^{T}F(1-x)+x^{T}Bx\right)=\sum _{e_{ij}w_{ij}\left(x_i}-x_{j}\right}\sum _left(x_{2\sum\sum\sum) \sum$

양의 대각 $행렬{\displaystyle }$ F$${\$displaystyle$ F$}$ 및$$$B{\displaystyle }$ {\$displaystyle$ B$\}$에 대해 이 에너지를 최적화하면 선형 방정식 시스템으로 이어진다.

${\displaystyle \left(L_{\overline {S}}, {\overline {S}}, {\overline {S}}, {\overline {S}}, {\overline {S}}, {\overline {S}}}, {\gamma F_{\gamma F}+\overline {S}}, {\overline {\gamma F}, {S}, {\gamma F}, {S}, {\overline}, {\gamma}, {}$

시드 노드 세트인 $(\displaystyle$ S$)$는 이 경우 비어 있을 수 있지만($즉$, S$$ $=$ ${\displaystyle V}$(\$displaystyle$ {$S}}=V}),$ 양의 대각 행렬이 존재하기 때문에 이 선형 시스템에 고유한 솔루션을 제공할 수 있습니다.

예를 들어, 우도/단일 용어를 사용하여 오브젝트의 색상 모델을 $통합$하는 경우$,$ ${\displaystyle {fi}_{}}$ {\$displaystyle$f_${i$}는 노드$vi$ {\$displaystyle v_{$i$$$$}}의 색상이 오브젝트에 속한다는 신뢰도를 나타냅니다($,$ $fi$ {\$displaystyle$ f_i$$$}$의 값이 클수록, fi {\displaystyle$f_i$}의 신뢰성이 높아집니다).${\displaystyle {}_{}}$${\displaystyle {vi}_{}}$$({$${$$i$$})$는 객체 라벨에 속하며 $bi$({$displaystyle$ b_$$${$$})$는 $노드$ vi({displaystyle$$ $v_i})$의 색상이 배경에 속한다는 확신을 나타냅니다.

알고리즘 해석

랜덤 워커 알고리즘은 처음에 픽셀에 드롭된 랜덤 워커가 먼저 객체(전경) 시드 또는 배경 시드에 도달할 확률에 따라 픽셀을 객체/배경이라고 라벨링함으로써 동기 부여되었습니다.단, 이 같은 알고리즘에 대해서는 에 ^[1]기재되어 있는 다른 해석도 몇 가지 있습니다.

회로 이론 해석

전기 회로 이론과 ^[5]그래프에서 랜덤 워크 사이에는 잘 알려진 연관성이 있습니다.따라서 랜덤 워커 알고리즘은 전기회로의 관점에서 두 가지 해석이 가능하다.두 경우 모두 그래프는 각 가장자리가 수동형 선형 저항으로 대체되는 전기 회로로 간주됩니다.$에지{\displaystyle {}_{}}$ ${\displaystyle {eij}_{}}$와$$된 저항 $({$$displaystyle r_{ij})$는 ${\displaystyle {\mathrm{rij}}_{}}$ $=$ ${\displaystyle 1\frac{\mathrm{}}{}}$ ${\displaystyle \frac{w_{}}{}}$ $({$}=$sqrc {1}{w_{ij}}})$와 같습니다(즉, 에지 무게는 전기 전도도와 같습니다).

첫 번째 해석에서는 백그라운드 시드 ${\displaystyle {vi}_{}}$$$ B$(\displaystyle$ $v_{i}\in$B$)$와 $관련$된 각 노드가 접지와 결합된 단위직류이상전압에 ${\displaystyle {접속}_{}}$되어 있다(i,e).각 ${\displaystyle {vi}_{}}$ †$F$의 ${\displaystyle \mathrm{단위}}$ $전위$(\$displaystyle v_{$i}\in F$)$이 회로 구성에 의해 각 노드에서 확립된 정상 상태의 전기 회로 전위는 랜덤 워커 확률과 정확히 동일합니다.구체적으로는 $노드{\displaystyle {}_{}}$에서의 $(xi)$는 $노드{\displaystyle {}_{}}$ $({$에서 랜덤 워커가 낙하한 경우 백그라운드노드에 도달하기 전에 오브젝트/포그라운드노드에 도달할 확률과 동일합니다.

두 번째 해석에서 랜덤 워커 확률을 0.5로 역치화함으로써 노드를 오브젝트 또는 백그라운드로서 라벨링하는 것은 노드와 오브젝트 또는 백그라운드 시드 사이의 상대적인 유효 컨덕턴스에 근거해 노드를 오브젝트 또는 백그라운드로서 라벨링하는 것과 동등하다.구체적으로는 노드가 백그라운드시드보다 오브젝트시드에 대한 유효 컨덕턴스가 높을 경우(유효저항이 낮을 경우) 노드는 오브젝트로 라벨이 지정됩니다.노드가 오브젝트 시드보다 백그라운드시드에 대한 유효 컨덕턴스가 높을 경우(유효저항이 낮을 경우) 노드는 백그라운드로 라벨이 지정됩니다.

내선번호

위에서 설명한 기존의 랜덤 워커 알고리즘은 다음과 같은 방법으로 확장되었습니다.

• 재시작 시 랜덤^[6] 워크
• 알파^[7] 매팅
• 임계값^[8] 선택
• 소프트^[9] 입력
• 사전 세그먼트^[10] 이미지에서 실행
• 공간^[11] 랜덤 워크 축척
• 오프라인 프리컴퓨팅을^[12][13] 사용한 고속 랜덤 워커
• 범용 랜덤 워크를 통해 유연한 호환성 기능 구현
• 그래프 절단, 랜덤 워커 및 최단 경로를 통합하는 전력 분수계
• 랜덤 워커 유역
• 다변량 가우스 조건부 랜덤 필드

적용들

이미지 분할 외에도 랜덤 워커 알고리즘 또는 그 확장 기능은 컴퓨터 비전 및 그래픽의 여러 문제에 추가로 적용되었습니다.

• 이미지^[18] 컬러화
• 인터랙티브 로토스코프^[19]
• 의료 영상 분할^[20][21][22]
• 여러^[23] 세그먼트화 병합
• 메시^[24][25] 세그멘테이션
• 메시 노이즈^[26] 제거
• 세그멘테이션^[27] 편집
• 그림자^[28] 제거
• 스테레오 매칭(즉, 1차원 이미지 등록)^[29]
• 이미지 융합

레퍼런스

외부 링크

• 원래의 랜덤 워커 알고리즘을 구현하는 Matlab 코드
• 프리컴퓨팅으로 랜덤 워커 알고리즘을 구현하는 Matlab 코드
• 이미지 처리 도구 상자 skikit-image에서 원본 랜덤 워커 알고리즘의 Python 구현