NCUT算法是一種聚類算法，它可以分為兩個主要部分：Flood Fill和Normalized Cut。Flood Fill是一種2維連通域聚類方法，具有計算複雜度小和速度快的特點。它通過將點雲映射到2維的柵格中並聚類連通的格線來簡化數據量。Normalized Cut則用於更精確地分割聚類，通過計算連通組件之間的權重來實現，這些權重考慮了歐氏距離和高度特徵距離。
Flood Fill：
構造格線：將點雲映射到2維柵格中，通過降維和量化減少數據量。
獲得連通組件：將含有點雲的連通格線聚類為單個連通組件。
分割點雲：從連通組件中獲得對應的原始點雲，進行分割。
Normalized Cut：
構造高度特徵圖：用於計算連通組件之間的權重。
計算權重：結合高度特徵和歐氏距離來計算連通組件之間的權重。
分割組件：根據權重矩陣聚合Skeletons，實現將所有組件分成兩部分的分割。
NCUT算法在圖像處理和數據挖掘中有廣泛套用，特別是在圖像分割中，它可以將圖像分割成具有相似特徵的區域。此外，NCUT算法可以視為最小割的最佳化，旨在最大化關聯度（association）並最小化不關聯度（disassociation）。
需要注意的是，NCUT算法在某些情況下可能存在過分割或欠分割的問題，這些問題可以通過Normalized Cut來解決。Normalized Cut的數學定義是最大化關聯度（association）和最小化不關聯度（disassociation），從而實現更精準的分割。