Livewire 세그멘테이션 기법
Livewire Segmentation Technique |
Livewire는 사용자가 간단한 마우스 [1]클릭으로 빠르고 정확하게 추출할 관심 영역을 선택할 수 있는 분할 기법입니다.이는 Edsger W. Dijkstra의 최저 비용 경로 알고리즘을 기반으로 합니다.먼저 가장자리를 추출하기 위해 Sobel(소벨) 필터로 영상을 접습니다.결과 이미지의 각 픽셀은 그래프의 꼭지점이며, 위, 아래, 왼쪽, 오른쪽과 같이 주변의 4개 픽셀로 가는 가장자리를 가집니다.에지 비용은 비용 함수를 기반으로 정의됩니다.1995년 에릭 N.모텐슨과 윌리엄 A.Barrett은 인텔리전트 [2]시저로 알려진 라이브와이어 분할 도구에서 확장 작업을 수행했습니다.
라이브와이어 세그멘테이션
사용자는 앵커라고 하는 영상의 픽셀을 클릭하여 시작점을 설정합니다.그런 다음 마우스를 다른 점으로 이동하기 시작하면 가장 작은 비용 경로가 앵커에서 마우스가 오버된 픽셀로 그려지고 사용자가 마우스를 이동하면 자동으로 변경됩니다.표시되는 경로를 선택하려면 이미지를 다시 클릭하기만 하면 됩니다.
오른쪽 이미지에서 사용자가 원하는 관심 영역을 표시하기 위해 클릭한 위치가 작은 정사각형으로 표시되어 있는 것을 쉽게 볼 수 있습니다.또한 이미지의 테두리에서 라이브 와이어가 끊어졌음을 쉽게 확인할 수 있습니다.
라이브와이어 알고리즘
Sobel(소벨) 필터로 이미지를 컨볼루션하여 가장자리를 추출합니다.이 필터링된 이미지를 사용하여 픽셀을 네 방향(위, 아래, 왼쪽)[1]의 가장자리가 있는 노드로 그래프를 만듭니다.가장자리에 Sobel 필터에서 수집된 피쳐로 가중치가 부여되므로 가장자리를 유지하는 데 비용이 적게 듭니다.여러 가지 다른 비용 방법이 가능하지만 가장 중요한 것은 구배[1] 크기이다.
의사 코드의 Live-Wire 2-D DP 그래프 검색 알고리즘 [2]
알고리즘 Livewire가 입력됩니다: s {Start(또는 시드) 픽셀.} l(q, r) {픽셀 q와 r.} 데이터 구조 간의 링크에 대한 로컬 비용 함수: L {총 비용(초기 빈)에 따라 정렬된 활성 픽셀 목록입니다.} N(q) {q의 인접 집합(픽셀의 인접 8개 포함).} e(q) {q가 확장/처리되었는지 여부를 나타내는 부울 함수입니다.} g(q) {시드 포인트에서 q.} 출력까지의 총 비용 함수: p {최소 비용 경로를 나타내는 각 픽셀의 포인트.} g(s) ← 0, L ← s, {비용이 들지 않는 시드 픽셀을 사용하여 활성 목록을 초기화합니다.}이(가) L을(가) 시작하는 동안 {확장할 지점을 가리킵니다.} q ← 최소(L); {활성 목록에서 최소 비용 픽셀 q를 제거합니다.} e(q) ← TRUE, {q를 확장(예: 처리됨)으로 표시합니다.e(r)가 gtmp ←g(q) + l(q, r)을 시작하지 않도록 각 rµN(q)에 대해 }. {네이버에 대한 총 비용을 계산합니다.} rlL 및 gtmp < g(r)인 경우 {목록에서 고비용 네이버 삭제.} r ← L. r l L이면 {If neighbor not list, } g(r) ← gtmp; {neighbor's total cost, } p(r) ← q; {set(또는 reset) 백 포인터, } L ← r; {및 활성 목록으로 전환(또는 복귀)을 시작합니다.} 엔드 엔드 엔드
3D로의 확장
2010년에 Leo Grady는 Livewire 알고리즘을 3D로 [3]확장했습니다.이 확장에서는 2D Livewire 알고리즘을 사용자가 0차원 경계(2개 점)를 지정할 수 있도록 하고 이러한 점을 연결하는 최소 1차원 공경계(곡선)를 찾는 것으로 처리했습니다. 여기서 최소값은 영상 속성으로 정의됩니다.알고리즘을 3D로 확장하기 위해 사용자는 대신 하나 이상의 1차원 경계(폐쇄 곡선)를 지정하도록 요구되며, 알고리즘은 최소 표면이 이미지 특성에 따라 정의되는 1차원 곡선에 의해 경계가 되는 최소 2차원 공경계(표면)를 구한다.이 Livewire의 3D 확장은 이산 외부 미적분 개념에 크게 의존하여 경계/공계 연산자의 관점에서 2D Livewire 알고리즘을 재해석한 후 이러한 개념을 3D로 적용합니다.그래디 페이퍼에는 3D 최소 표면을 계산하는 효율적인 알고리즘도 나와 있습니다.
「 」를 참조해 주세요.
레퍼런스
- ^ a b c 바지오, 다니엘 엘리스GPGPU 기반 이미지 세그멘테이션 라이브와이어 알고리즘 구현.2007년, 108f.Saao Jos'e dos Campos, 항공공대 석사 논문.http://gpuwire.googlecode.com/files/Master%20Thesis%20-%20Updated%20February%2015th.pdf Wayback Machine 2010-12-17 아카이브 완료
- ^ a b Mortensen, E. N.; Barrett, W. A. 이미지 합성용 지능형 가위.인: SIGGRAPH '95: 제22회 컴퓨터 그래픽스 및 인터랙티브 기술에 관한 연례 회의의 속행.뉴욕, 뉴욕, 미국: ACM Press, 1995. 페이지 191-198. ISBN0-89791-701-4.
- ^ Leo Grady, "최소 표면은 최단 경로 분할 방법을 3D로 확장한다", 패턴 분석 및 기계 지능에 관한 IEEE 트랜잭션, Vol. 32, No. 2, 페이지 321-334, 2010년 2월.
