유역(이미지 처리)

Watershed (image processing)

이미지 처리에 관한 연구에서 분수령은 그레이스케일 이미지에 정의된 변환이다.그 이름은 은유적으로 인접한 배수 분지를 분리하는 지질학적 분수령, 즉 배수 분열을 가리킨다.유역 변환은 각 점의 밝기가 높이를 나타내는 지형도처럼 작용하는 이미지를 처리하고 능선 상단을 따라 흐르는 선을 찾아낸다.

분수령에는 여러 가지 기술적 정의가 있다.그래프에서 유역 선은 노드, 에지 또는 두 노드와 에지의 하이브리드 선에 정의될 수 있다.유역은 연속 도메인에서도 정의될 수 있다.[1]분수령을 계산하는 알고리즘도 다양하다.유역 알고리즘은 주로 객체 분할, 즉 이미지에서 서로 다른 객체를 분리하기 위해 이미지 처리에 사용된다.이것은 물체를 세거나 분리된 물체의 추가 분석을 가능하게 한다.

  • 경사로 크기 완화

  • 그라데이션 크기 이미지

  • 그라데이션의 유역

  • 경사로의 유역(완화)

정의들

지질학에서 분수령은 인접한 유역 분지를 분리하는 분열이다.

범람에 의한 유역

이 아이디어는 1979년 S에 의해 소개되었다.Beucher와 C.란투에줄.[2]기본적인 아이디어는 각 지역 최소의 수원을 구호물에 배치하고, 전체 구호물을 원천으로부터 범람시키고, 서로 다른 수원지가 만날 때 장벽을 쌓는 것으로 구성되었다.결과적으로 발생한 장벽 세트는 홍수에 의한 분수령이 된다.Priority-Flud라고 통칭되는 많은 개선사항이 그 이후로 이 알고리즘에 적용되었다.[3]

지형적 거리별 유역

직관적으로 지형학적 구조물에 떨어지는 물방울은 "가장 필요한" 최소치를 향해 흐른다."가장 필요한" 최소값은 가장 가파른 내리막길 끝에 있는 최소값이다.지형에 있어서는 그 지점이 그 최소의 유역 유역에 놓여 있으면 이런 현상이 일어난다.이전의 정의는 이 조건을 검증하지 않는다.

물방울 원리에 의한 유역

직관적으로 유역은 물방울이 뚜렷한 미니마를 향해 흐를 수 있는 지역 미니마의 분리다.가장자리 가중 그래프의 분수령을 정의하기 위해 이 직관적인 아이디어의 공식화가 에 제공되었다.

픽셀간 유역

S. Beucher와 F.마이어는 다음과 같은 절차를 고려하여 유역법의 알고리즘 간 픽셀 구현을 도입했다.[5]

  1. 각 최소값에 구별되는 레이블로 레이블을 지정하십시오.세트 초기화S레이블이 지정된 노드.
  2. 추출 위치S최소 고도 F의 노드 x, 즉 F(x) = 최소{F(y) y ∈ S}.x의 라벨을 x에 인접한 각 비 라벨 노드 y에 귀속시키고 y를 S에 삽입한다.
  3. 2단계를 끝까지 반복하십시오.S비어 있다.

위상유역

이전의 개념은 유역 기반에 초점을 맞추지만 생산되는 분리 선에는 초점을 맞추지 않는다.위상학적 분수령은 M에 의해 도입되었다.1997년 쿠프리와 G. 베르트랑, 다음과 같은 기본적 재산의 혜택을 누렸다.[6]함수 W는 W ≤ F와 W가 F의 지역 미니마 사이의 대비를 유지하는 경우에만 F 함수의 분수령이다. 여기서 두 지역 미니마 M과1 M의2 대조는 M에서 M으로2 가기 위해1 상승해야 하는 최소 고도로 정의된다.[7]효율적인 알고리즘이 논문에 자세히 설명되어 있다.[8]

유역 알고리즘

영상 분할에 유역 원리를 사용하기 위해 다른 접근법을 사용할 수 있다.

  • 이미지의 그라데이션의 국소 최소값을 마커로 선택할 수 있으며, 이 경우 과분할이 생성되고 두 번째 단계는 지역 합병을 수반한다.
  • 마커 기반 유역 변환은 사용자가 명시적으로 정의했거나 형태론적 연산자 또는 다른 방법으로 자동으로 결정된 특정 마커 위치를 사용한다.

마이어의 홍수 알고리즘

가장 일반적인 유역 알고리즘 중 하나는 F에 의해 도입되었다.1990년대 초 Meyer는 Priority-Flud라고 통칭되는 많은 개선사항들이 수조 개의 픽셀로 구성된 데이터 세트에 적합한 변형을 [9]포함하여 이후 이 알고리즘에 적용되었다.[10]

알고리즘은 그레이 스케일 영상에서 작동한다.회색 값 완화의 연속적인 범람 시 인접 유역 분지가 건설된다.이 플러딩 프로세스는 경사 영상에서 수행된다. 즉, 가장자리를 따라 분진이 나타나야 한다.일반적으로 이것은 특히 의료 CT 데이터와 같은 노이즈가 많은 영상 소재의 경우 영상의 과도한 세분화로 이어질 것이다.영상을 미리 처리하거나 유사성 기준에 기초하여 해당 지역을 병합해야 한다.

  1. 홍수가 시작되어야 하는 픽셀인 일련의 마커가 선택된다.각각 다른 라벨이 주어진다.
  2. 표시된 각 영역의 인접 픽셀은 픽셀의 그라데이션 크기에 해당하는 우선순위 수준의 우선순위 대기열에 삽입된다.
  3. 우선 순위 수준이 가장 높은 픽셀은 우선 순위 대기열에서 추출된다.이미 라벨이 붙어 있는 추출된 픽셀의 이웃에 모두 동일한 라벨이 붙어 있는 경우, 해당 픽셀에 라벨이 붙어 있는 것이다.우선 순위 대기열에 아직 포함되지 않은 모든 비표시 인접 항목이 우선 순위 대기열에 배치된다.
  4. 우선 순위 대기열이 비워질 때까지 3단계를 다시 실행하십시오.

라벨이 부착되지 않은 픽셀이 분수령이다.

제약 펠릿 모집단에 대한 표식기 지원 유역 변환 예제.유역 선은 CT 영상 스택에 검은색으로 중첩된다.[11]

최적의 스패닝 포리스트 알고리즘(워터쉬드 컷)

최적의 스패닝 숲으로서의 유역은 Jean Cousty 외 연구진에 의해 도입되었다.[12]그들은 이러한 유역의 일관성을 확립한다: 그것들은 (가장 가파른 강하 특성을 통해) 그들의 "교정 분지" 또는 (물방울 원리를 통해) 유역 분지를 분리하는 "분할선"에 의해 동등하게 정의될 수 있다.그리고 그들은 동등성 정리를 통해 최소 스패닝 숲의 측면에서 그들의 최적성을 증명한다.그 후에, 그들은 그것들을 계산하기 위해 선형 시간 알고리즘을 도입한다.다른 프레임워크에서는 유사한 특성이 검증되지 않으며 제안된 알고리즘이 이론과 실제 모두에서 가장 효율적인 기존 알고리즘이라는 점에 유의할 필요가 있다.

  • 두 개의 마커(녹색)가 있는 영상과 이미지의 그라데이션에서 계산된 최소 스패닝 포리스트.

  • 최소 스패닝 포리스트에 의한 분할 결과

컴퓨터 비전에 있는 다른 알고리즘과의 링크

그래프 자르기

2007년 C.알렌 외는 최적의 스패닝 포리스트에 대한 그래프 잘라내기 관련 링크를 설정했다.[13]더 정확히 말하면, 그들은 그래프의 무게의 힘이 일정 수 이상일 때, 그래프가 에너지를 최소화하는 컷은 최대 스패닝 포리스트에 의한 컷이라는 것을 보여준다.

최단길숲

팔카오 외 [14]연구소의 이미지 포리스트링 변환(IFT)은 최단 경로 포리스트를 계산하는 절차다.IFT의 마커가 중량 함수의 극단치에 해당할 때 숲에 의해 유도된 절단이 분수령 절단이라는 것이 J. Cousty 외 연구진에 의해 증명되었다.[15]

랜덤 워커

랜덤 워커 알고리즘은 조합 디리클레 문제를 해결하는 분할 알고리즘으로, 2006년 L. Grady에 의해 영상 분할에 적응했다.[16]2011년 C.쿠프리 외 연구진은 그래프의 무게의 힘이 무한대로 수렴할 때 무작위 보행자 에너지를 최소화하는 컷이 최대 스패닝 포리스트에 의한 컷이라는 것을 증명했다.[17]

계층

계층적 유역 변환은 결과를 그래프 표시로 변환하고(즉, 분할된 영역의 인접 관계가 결정됨) 추가적인 유역 변환을 반복적으로 적용한다.자세한 내용은 을 참조하십시오.분수령과 계층적 분열을 연결하는 이론은 다음에서[19] 개발되었다.

메모들

  1. ^ L. Najman과 M.슈미트연속 함수의 분수령.신호 처리(수학적 형태학에 관한 특별호), Vol. 38(1994), 페이지 99–112
  2. ^ 이미지 처리, 실시간 에지 및 동작 감지에 관한 Serge Beucher와 Christian Lantuéj 워크샵(1979) http://cmm.ensmp.fr/~beucher/publi/pb.pdf
  3. ^ 반스, R, 리먼, C, 물라, D, 2014.우선 순위 플러드: 디지털 고도 모델을 위한 최적의 저압 채우기 및 유역 라벨링 알고리즘.컴퓨터 & 지리학 62, 117–127. doi:10.1016/j.cageo.2013.04.024
  4. ^ J. Cousty, G. Bertrand, L. Najman, M.쿠프리유역 절단: 최소 스패닝 숲과 물방울 원리, 패턴 분석 및 기계 인텔리전스 31(8) 페이지 1362-1374, 2009,
  5. ^ 세르게이 뷰처와 페르난드 마이어.분할에 대한 형태론적 접근방식: 유역 변환.이미지 처리의 수학적 형태학(Ed)에서.E. R. Dougherty), 페이지 433–481(1993).
  6. ^ M. Couprie, G. Bertrand.위상학적 그레이 스케일 유역 변환.SPIE 비전 지오메트리 V의 Proc., 3168, 페이지 136–146(1997).http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.3.7654&rep=rep1&type=pdf
  7. ^ G. 베르트랑위상학적 유역이야Journal of Mathemical Imaging and Vision, 22(2–3), 217–230페이지(2005년)
  8. ^ 미셸 쿠프리, 로랑 나즈만, 길레스 베르트랑위상학적 유역에 대한 준선형 알고리즘.Journal of Mathemical Imaging and Vision, Springer Verlag, 2005, 22 (2-3), pp.231-249.
  9. ^ 반스, R, 리먼, C, 물라, D, 2014.우선 순위 플러드: 디지털 고도 모델을 위한 최적의 저압 채우기 및 유역 라벨링 알고리즘.컴퓨터 & 지리학 62, 117–127. doi:10.1016/j.cageo.2013.04.024
  10. ^ 반스, R, 2016.데스크톱 또는 클러스터의 수조 개의 셀 디지털 고도 모델에 대해 채워지는 병렬 우선 순위-홍수 우울증컴퓨터 & 지리학.doi:10.1016/j.cageo.2016.07.001
  11. ^ 도어, F. J. S. & 플로렌스, A. J. (2020)다분해 캡슐 형상의 특성화를 위한 마이크로-XRT 이미지 분석 및 머신러닝 방법론국제 제약 저널: X, 2, 100041.https://doi.org/10.1016/j.ijpx.2020.100041
  12. ^ 장 쿠스티, 길레스 베르트랑, 로랑 나즈만, 미셸 쿠프리.유역 절단: 최소 스패닝 숲과 물방울 원리.패턴 분석 및 머신 인텔리전스에 관한 IEEE 거래. 31(8)2009년 8월. 페이지 1362–1374.
  13. ^ Cédric Allene, Jean-Yves Audibert, Michel Couprie 및 Renaud Keriven : "최적 스패닝 숲과 유역의 일부 링크", Image and Vision Computing, 2009.
  14. ^ A.X. Stolfi, J. de Alencar Lotufo, R. : "이미지 포리스트링 변환: 이론, 알고리즘 및 응용 프로그램", PAMI, 2004
  15. ^ 장 쿠스티, 길레스 베르트랑, 로랑 나즈만, 미셸 쿠프리.유역 절단: 희석, 최단 경로 숲 및 위상학적 유역.패턴 분석과 기계 인텔리전스에 관한 IEEE 거래. 32 (5). 2010. 페이지 925–939.
  16. ^ Grady, L.: "Random walk for image segmentation"(영상 분할을 위해 무작위로 걷는다)PAMI, 2006
  17. ^ Camille Couprie, Leo Grady, Laurent Najman 및 Hugues Talbot, "파워 유역: 통합 그래프 기반 최적화 프레임워크", IEEE 패턴 분석 및 머신 인텔리전스에 관한 거래, 제33권, 제1384-1399권, 2011년 7월
  18. ^ 로랑 나즈만, 미셸 슈미트유역 등고선의 지오데틱 절약과 계층적 세분화.패턴 분석 및 기계 인텔리전스에 관한 IEEE 거래, 1996, 18 (12), 페이지 1163-1173.
  19. ^ 로랑 나즈만계층적 세그먼트와 초경량 유역 사이의 동등성.Springer Verlag, 2011, 40(3), 페이지 231-247의 수학적 이미징 및 비전 저널.

참조

외부 링크