The Mutex Watershed and its Objective: Efficient, Parameter-Free Graph Partitioning
원문 초록
Image partitioning, or segmentation without semantics, is the task of decomposing an image into distinct segments, or equivalently to detect closed contours. Most prior work either requires seeds, one per segment; or a threshold; or formulates the task as multicut / correlation clustering, an NP-hard problem. Here, we propose an efficient algorithm for graph partitioning, the "Mutex Watershed''. Unlike seeded watershed, the algorithm can accommodate not only attractive but also repulsive cues, allowing it to find a previously unspecified number of segments without the need for explicit seeds or a tunable threshold. We also prove that this simple algorithm solves to global optimality an objective function that is intimately related to the multicut / correlation clustering integer linear programming formulation. The algorithm is deterministic, very simple to implement, and has empirically linearithmic complexity. When presented with short-range attractive and long-range repulsive cues from a deep neural network, the Mutex Watershed gives the best results currently known for the competitive ISBI 2012 EM segmentation benchmark.
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
수요가 있는 그래프 분할: 일반화된 컨던턴스와 그 응용
Graph Partitioning with Demands: Generalized Conductance and its Applications
본 논문에서는 일반적인 수요 모델 하에서 다양한 그래프 분할 문제를 연구한다. 각 문제에서 용량 함수 $c\colon E\to \mathbb{N}$와 수요 함수 $w\colon V\times V\to \mathbb{N}$가 주어진 그래프 $G=(V,E,c,w)$가 주어진다. 우리의 주요 관심사는 컷 $(S, \bar{S})$를 찾아 다음 양을 최소화하는 문제이다. \[ ψ_w( S ) = \frac{c( S, \bar{S} )}{w( S, V )\cdot w( \bar{S}, V )}. \] 여기서 $c( S, \bar{S} )$는 $S$와 $S$의 여집합 $\bar{S}$ 사이의 간선 비용이며, $w( S, V )=w( S )+w( S, \bar{S} )$는 $S$ 내부의 내부 수요 $w( S )$와 $S$의 꼭짓점과 $\bar{S}$의 꼭짓점 사이의 수요 $w( S, \bar{S} )$의 합이다. $ψ_w( S )$를 컷 $(S, \bar{S})$의 \emph{generalized conductance}(일반화된 컨던턴스)라 하고, $ψ_w( S )$를 최소화하는 과제를 Generalized Conductance Problem(일반화된 컨던턴스 문제)라 부른다. 주요 기여는 이 목적함수에 대해 $\mathcal{O}(\log n)$-근사 보장을 갖는 알고리즘을 제시하는 것이다. 이 결과는 양방향 환원을 통해 달성된다. 먼저 잘 알려진 Generalized $k$-Multicut Problem으로 환원하고, 이어서 잘릴 수 있는 수요량에 대한 추가 상한 제약이 있는 고전 Sparsest-Cut Problem의 제약 변형으로 환원한다. 더 나아가, 위 절차가 수요가 있는 그래프 분할(Graph Partitioning with Demands)에 대해 $\mathcal{O}(\log n)$-이기준 근사를 얻는 데 사용될 수 있음을 보인다. 여기서 목표는 $G\setminus C$의 모든 연결 성분 $H$에 대해 $w( H )\leq ρ\cdot w( V )$를 만족하는 최소 비용의 간선 부분집합 $C$를 찾는 것이다. 이는 차례로 수요가 있는 계층적 클러스터링(Hierarchical Clustering with Demands)—그래프를 점점 더 세분화된 클러스터로 분할하는 컷의 계층을 찾는 문제—에 대한 $\mathcal{O}(\log n)$-근사를 제공한다. 곱셈형 수요 함수(multiplicative demand functions)의 경우 이러한 보장을 $\mathcal{O}(\sqrt{\log n})$로 개선하며, 트리(tree)의 경우 모든 목적함수에 대해 $\mathcal{O}(1)$-근사를 얻는다.
원자적 움직임 기반 음악-춤 생성
Music-to-Dance Generation via Atomic Movements
음악 기반 춤 생성은 음악과 리듬적으로 동기화되고 의미적으로 일관된 인간 움직임을 생성하는 것을 목표로 한다. 최근 신경망 기반 접근법들은 인상적인 시각적 사실성을 달성했지만, 일반적으로 움직임을 연속 신호로 모델링하고 그 구성적 특성을 간과하여 생성된 춤이 구조적으로 비일관적이고 제어하기 어렵게 만든다. 본 연구에서는 안무를 원자적 움직임(atomic movements)의 시퀀스로 모델링하는 구조 인식 프레임워크를 제안한다. 원자적 움직임은 춤의 구성 요소로 작용하는 의미적으로 해석 가능한 동작 이벤트이다. 이 원자적 움직임 어휘를 구축하기 위해, 먼저 대규모 춤 데이터를 분할하고 이를 원자적 움직임 그룹으로 클러스터링한다. 그다음 대규모 언어 모델(LLM)을 사용해 클러스터에 의미적 재라벨링과 정제를 수행하여, 해석 가능하고 재사용 가능한 원자적 움직임 집합을 얻는다. 이러한 원자적 움직임 주석을 바탕으로, 인간의 안무 과정을 반영하는 2단계 생성 프레임워크를 설계한다. 원자적 움직임 계획 단계에서는, 모델이 입력 음악을 조건으로 원자적 움직임의 유형, 지속 시간, 타이밍을 예측하여 상징적 춤 배치를 형성한다. 완성 단계에서는, 전환 인식(transition-aware) 생성기가 계획된 구조를 조건으로 매끄럽고 스타일적으로 일관된 움직임을 합성한다. 광범위한 실험을 통해, 본 방법이 기존 베이스라인 대비 구조적 일관성, 리듬 정렬, 지각적 자연스러움에서 유의미하게 향상된 춤을 생성함을 보였으며, 명시적 구조 표현을 통해 해석 가능성과 제어 가능한 편집을 향상시킨다.
제2회 MLC-SLM 챌린지를 위한 Omnilingual-ASR 기반 Speech-LLM 시스템
An Omnilingual-ASR-Based Speech-LLM System for the 2nd MLC-SLM Challenge
제2회 MLCSLM 챌린지 Task 1에 대한 우리의 제출을 설명한다. DiariZen-Large-s80(WavLM-Large) 분할(segmentation), CAM++ 임베딩 기반 2화자 클러스터링, LoRA 적응 omniASR LLM 7B v2 인식기를 결합한 계단식 화자 분리(diarization)-후-인식 시스템이며, 테스트 시점에는 oracle 분할이나 화자 레이블을 사용하지 않는다. 공식 Development set(150개 대화, 21개 언어/억양 카테고리)에서 이 시스템은 macro tcpMER 29.27%를 달성했으며, 공식 기준선의 79.15%에 비해 낮다. Evaluation set에서는 50.23%를 기록했다. 또한 tcpMER에 실질적으로 영향을 미치는 두 가지 엔지니어링 선택을 분석한다. 첫째, 임베딩 기반 화자 클러스터링은 ASR <sc> 턴 마커만으로 화자를 할당하는 end-to-end 스타일 대안보다 우수하다. 둘째, 화자 분리 재현율을 높이려는 의도로 도입된 overlap-aware 분할은 겹치는 발화가 두 번 전사되기 때문에 tcpMER를 증가시킨다.
Cross-Domain Few-Shot Semantic Segmentation
Image Segmentation Based on Watershed and Edge Detection Techniques
Solving non-uniqueness in agglomerative hierarchical clustering using multidendrograms
토론
이 논문과 연결된 포럼 글이 아직 없습니다.