------------------------------------------------------------------------- This file gives pseudo code for the PNN algorithm presented in: "Fast and memory efficient implementation of the exact PNN" IEEE Trans. on Image Processing, Vol.9, No. (5), May 2000. Pasi Fränti, Timo Kaukoranta, Day-Fann Shen and Kuo-Shu Chang Updated: 30.3.2000 Pasi Franti franti@cs.uef.fi ------------------------------------------------------------------------- Preface: ------------------------------------------------------------------------- The following pseudo code gives a sketch of the implementation. It is not complete, not very exact, and several less relevant lower level routines are left out. The pseudo code aims at readability and therefore few less relevant optimizations are left out. Questions and comments by email are always welcome. ------------------------------------------------------------------------- Data structures: ------------------------------------------------------------------------- X[N] = Training set of N vectors. P[N] = Partition of the training set, described as N pointers from X to C. C[k] = Codebook of M vectors. C[j].vector = Code vector C[j].size = Cluster size ------------------------------------------------------------------------- Algorithm: ------------------------------------------------------------------------- PerformPNN(C,P) { Q[BookSize(C)]: Nearest Neighbor Pointers; Q[j].nearest = Index of the nearest neighbor cluster. Q[j].distance = Cost of merging the two clusters. Q[j].recalculate = Flag indicating if the pointer must be updated. FOR j=1 TO BookSize(C) DO { Q[j] <- FindNearestNeighbor(C,j); } WHILE BookSize(C) > k DO { a <- FindMinimumDistance(C,Q); b <- Q[a].nearest; MergeVectors(C,P,Q,a,b); UpdatePointers(C,Q); } } FindNearestNeighbor(C,a) { q: Nearest Neighbor Pointer structure; q.nearest <- 1; q.distance <- Infinite; q.recalculate <- NO; FOR j=1 TO BookSize(C) DO { d <- MergeDistortion(C[a],C[j]); IF a<>j AND db THEN Swap(a,b); /* So that a is smaller index. */ last = BookSize(C); MarkClustersForRecalculation(C,Q,a,b); C[a].vector <- Centroid(C[a].vector,C[b].vector); JoinPartitions(P,C,a,b); FillEmptyPosition(C,Q,b,last); DecreaseBookSize(C); } MarkClustersForRecalculation(C,Q,a,b) { FOR j=1 TO jlast THEN { C[b] <- C[last]; Q[b] <- Q[last]; FOR j=1 TO j