You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
50 lines
1.7 KiB
50 lines
1.7 KiB
function clusterIdx = recursiveNCuts(anAffinityMat)
|
|
%Implementation of the recursive N-cuts algorithm
|
|
% Usage clusters = recursiveNCuts (anAffinityMat), where:
|
|
% Inputs
|
|
% - anAffinityMat is a rectangular, symmetrical affinity matrix
|
|
% representation of an image
|
|
% Output
|
|
% - clusterIdx is a vector storing the cluster Id of each node
|
|
|
|
% Makes sure preconditions are met
|
|
if ~issymmetric(anAffinityMat)
|
|
error('The affinity matrix provided is not symmetric.');
|
|
end
|
|
|
|
% Executes clustering using N-Cuts algorithm
|
|
clusterIdx = myNCuts(anAffinityMat, 2);
|
|
|
|
% Checks stop conditions
|
|
if (nnz(clusterIdx == 1) < 5 || nnz(clusterIdx == 2) < 5)
|
|
clusterIdx = [];
|
|
return;
|
|
end
|
|
NCut = calculateNcut(anAffinityMat, clusterIdx);
|
|
if (NCut > 0.2)
|
|
clusterIdx = [];
|
|
return;
|
|
end
|
|
|
|
% Finds indices of each cluster
|
|
clusterOneIndices = (clusterIdx == 1);
|
|
clusterTwoIndices = (clusterIdx == 2);
|
|
|
|
% Recursively calls itself for each part of the matrix
|
|
firstSubClusters = recursiveNCuts(anAffinityMat(clusterOneIndices, ...
|
|
clusterOneIndices));
|
|
secondSubClusters = recursiveNCuts(anAffinityMat(clusterTwoIndices, ...
|
|
clusterTwoIndices));
|
|
|
|
% Re-merges the sub-cluster arrays
|
|
if ~isempty(firstSubClusters)
|
|
clusterIdx(clusterOneIndices) = firstSubClusters;
|
|
end
|
|
if ~isempty(secondSubClusters)
|
|
clusterIdx(clusterTwoIndices) = secondSubClusters;
|
|
end
|
|
|
|
% Makes sure the IDs of the clusters of each half are unique
|
|
clusterIdx(clusterTwoIndices) = clusterIdx(clusterTwoIndices) + ...
|
|
size(unique(clusterIdx(clusterOneIndices)), 1);
|
|
end
|
|
|