Abstract-A new graph theoretic approach for data clustering presenteras och dess tillämpning på bildsegmenteringsproblemet demonstreras. De data som ska samlas in representeras av en oriktad adjakenskurva G med bågkapacitet som tilldelas för att återspegla likheten mellan de länkade hörnen. Clustering uppnås genom att ta bort bågar av G för att bilda ömsesidigt uteslutande subgrafer sådan att den största inter-subgraph maximal flöde minimeras. För grafer av måttlig storlek (2000 hörn), den optimala lösningen erhålls genom att dela ett flöde och klippa ekvivalent träd av 6, som kan konstrueras effektivt med hjälp av Gomory-Hu algoritm. Men för större grafer är detta tillvägagångssätt opraktiskt. Nya teorem för subgrafkondensering härleds och används sedan för att utveckla en snabb algoritm som hierarkiskt konstruerar och partitionerar ett delvis likvärdigt träd av mycket reducerad storlek. Denna algoritm resulterar i en optimal lösning som motsvarar den som erhålls genom att partitionera hela motsvarande träd och kan hantera mycket stora grafer med flera hundra tusen hörn. Den nya klusteralgoritmen tillämpas på bildsegmenteringsproblemet. Segmenteringen uppnås genom att man effektivt söker efter slutna konturer av kantelement (motsvarande minsta snitt i G), som till största delen består av starka kanter, medan man stöter bort konturer som innehåller isolerade starka kanter. Denna metod kan exakt lokalisera regiongränser och garanterar samtidigt bildandet av slutna kantkonturer.
Det presenteras av Wu och Leahy REF som en optimal graf teoretisk metod för dataklustring i bildsegmenteringsproblemet.
An optimal graph theoretic approach to data clustering: Theory and its application to image segmentation
{'venue': 'IEEE Transactions on Pattern Analysis and Machine Intelligence', 'journal': None, 'mag_field_of_study': ['Computer Science']}