Efficient algorithms for finding the K best paths througha trellis

A set of algorithms is presented for finding the best set of K mutually exclusive paths through a trellis of N nodes, with worst-case computation time bounded by N³log n for a fixed-precision computation. The algorithms are based on a transformation of the K-path trellis problem into an equivalent minimum-cost network flow (MCNF) problem. The approach allows the application of efficient MCNF algorithms, which can obtain optimal solutions orders of magnitude faster than the algorithm proposed by J.K. Wolf et al. (1989). The resulting algorithms extend the practicality of the trellis formulation (in terms of required computations) to multiobject tracking problems with much larger numbers of targets and false alarms. A response by Wolf et al. is included     

Feature enhancement and ATR performance using nonquadratic optimization-based SAR imaging

We present an evaluation of the impact of a recently proposed synthetic aperture radar (SAR) imaging technique on feature enhancement and automatic target recognition (ATR) performance. This image formation technique is based on nonquadratic optimization, and the images it produces appear to exhibit enhanced features. We quantify such feature enhancement through a number of criteria. The findings of our analysis indicate that the new feature-enhanced SAR image formation method provides images with higher resolution of scatterers, and better separability of different regions as compared with conventional SAR images. We also provide an ATR-based evaluation. We run recognition experiments using conventional and feature-enhanced SAR images of military targets, with three different classifiers. The first classifier is template based. The second classifier makes a decision through a likelihood test, based on Gaussian models for reflectivities. The third classifier is based on extracted locations of the dominant target scatterers. The experimental results demonstrate that the new feature-enhanced SAR imaging method can improve the recognition performance, especially in scenarios involving reduced data quality or quantity.