시작점이없는 그래프 검색 알고리즘

Question

나는 장면의 가장자리지도를 가지고 있으며 하늘과 지형을 가장 잘 구분하는 가장자리를 추출하고 싶습니다. 이것은 그래프 트래버 설 (graph traversal) 문제로 잘 짜여진 것 같습니다. 그러나 A *와 같은 인기있는 검색 알고리즘은 시작과 끝 지점 (처음과 마지막 열은 각각 제외 함)을 사용하는 데 의존합니다. 이러한 매개 변수를 필요로하지 않는 그래프 검색 알고리즘이 있습니까? 나는 부드러움과 같이 추출 된 가장자리의 일부 전역 특징을 최대화하고 싶다. 참고 : 속도가 중요한 문제이므로 실시간으로 처리해야합니다.

Answer 1

컴퓨터 비전 연구원은 minimum cuts으로 이러한 유형의 문제를 공격했습니다. 위키피디아의 전체 내용은 article about graph cuts in computer vision입니다. Greig, Porteous 및 Seheult가 제안한 알고리즘을 처음으로 개괄적으로 살펴 보겠습니다.

픽셀 색상에서 하늘 대 지형의 확률에 대한 로그 가능성까지의 함수가 있다고 가정합니다. 소스 버텍스, 싱크 버텍스 및 각 픽셀에 대한 버텍스가있는 그래프를 준비합니다. 하늘 인 픽셀의 로그 가능성과 동일한 용량으로 각 픽셀에 소스를 연결합니다. 해당 픽셀의 지형 가능성에 해당하는 용량으로 각 픽셀을 싱크에 연결합니다. 인접 픽셀의 각 쌍에 대해 서로 다른 분류를 갖는 로그 가능성과 동일한 용량으로 연결합니다. 최소 컷을 계산하십시오. 컷의 소스 측에있는 모든 정점은 하늘로 분류되고 컷의 싱크 측에있는 모든 정점은 지형으로 분류됩니다.

지형이 이미지 하단에 있고 하늘이 상단에있는 것으로 알려진 경우 소스를 각각의 상단 픽셀에 연결하고 하단 픽셀을 싱크에 연결하십시오. 무한한 수용력. 그런 다음 인접 픽셀 색상의 유사성에 따라 가장자리 용량을 변경하지 않고 색상을 기반으로 픽셀을 분류하는 로그 가능성을 제거 할 수 있습니다.