Application of an Efficient Graph-Based Partitioning Algorithm for Extended Target Tracking Using GM-PHD Filter

One of the main tasks involving the extended target tracking is how to partition the measurement set accurately and efficiently. In this article, an efficient graph-based partitioning algorithm is introduced for extended target tracking. To reduce the computational load and the interference of clutter on the measurement set partition, a measurement set preprocessing method based on density-based clustering algorithm is presented. An intuitive directed $k$-nearest neighbor ($k$NN) graph model based on graph theory is established to represent the relationship between different measurements in the measurement set that needs to be segmented. In the framework of directed $k$NN graph, a novel similarity metric based on shared nearest neighbor (SNN) is used, and a pairwise similarity that integrates the number of elements in the set of SNN and the closeness of data points is constructed. The spectral clustering algorithm is used to process the multiway cut in the directed $k$NN graph. The graph-based partitioning algorithm is applied to the extended target Gaussian mixture probability hypothesis density filter. Simulation results illustrate the advantages of our proposed graph-based partitioning algorithm in performance and computational efficiency.