Multi-target detection using convex sparsity prior
Provided is a method for detecting the trajectories of one or more targets in the field of view of one or more sensors, the method comprising: receiving one or more sensor frames corresponding to the one or more sensors; defining a space of allowable target states for the one or more sensor frames; specifying a set of potential target trajectories, each comprising one allowable target state for each of the one or more sensor frames; specifying target signal parameters for each of the allowable target states, such that the target signal parameters predict the expected target signal contribution corresponding to the one or more sensor frames; specifying a data fidelity objective to quantify how well the target signal parameters match the one or more sensor frames; specifying a sequence of one or more sparsity objectives to penalize a number of detected targets; determine the trajectories of one or more targets as follows: obtain values for all the target signal parameters in all the sensor frames, the obtained values being initialized values or previously optimized values, for each sparsity objective of the sequence, starting with the obtained target signal parameters, determine new target signal parameters to optimize the sum of the data fidelity objective and the sparsity objective; and storing the final trajectories in memory.
1. A non-transitory machine-readable medium storing instructions that when executed by one or more processors effectuate operations comprising:
receiving one or more sensor frames corresponding to the one or more sensors;
defining a space of allowable target states for the one or more sensor frames;
specifying a set of potential target trajectories, each comprising one allowable target state for each of the one or more sensor frames;
specifying target signal parameters for each of the allowable target states, such that the target signal parameters predict an expected target signal contribution corresponding to the one or more sensor frames;
specifying a data fidelity objective to quantify how well the target signal parameters match the one or more sensor frames;
specifying a sequence of one or more sparsity objectives to penalize a number of detected targets;
determining trajectories of one or more targets as follows:
obtaining values for all the target signal parameters in all the one or more sensor frames, the obtained values being initialized values or previously optimized values,
for each sparsity objective of the sequence, starting with the obtained values for the target signal parameters, determining new values for target signal parameters to optimize a sum of the data fidelity objective and the given sparsity objective; and
storing final determined trajectories in memory.
2. The non-transitory machine-readable medium of claim 1 wherein the one or more sparsity objectives of the sequence become increasingly non-convex.
3. The non-transitory machine-readable medium of claim 2 wherein the sequence of one or more sparsity objectives begins with a convex objective.
4. The non-transitory machine-readable medium of claim 1 wherein the data fidelity objective is convex.
5. The non-transitory machine-readable medium of claim 1 wherein the one or more sparsity objectives are each a mixture of a convex sparsity objective and a non-convex sparsity objective, with a weight of the non-convex sparsity objective being increased in the sequence.
6. The non-transitory machine-readable medium of claim 5 wherein the convex sparsity objective is a weighted group sparsity prior, corresponding to a sum over all potential target trajectories of a norm of weighted target parameters of each trajectory.
7. The non-transitory machine-readable medium of claim 5 wherein the non-convex sparsity objective is a number of target trajectories with one or more non-zero target signal parameters.
8. The non-transitory machine-readable medium of claim 4 wherein the convex data fidelity objective is a squared norm of a difference between data of the one or more sensor frames and a sum of all target signal contributions predicted by the target signal parameters.
9. The non-transitory machine-readable medium of claim 1 wherein the optimization of the sum of the data fidelity objective and the given sparsity objective is obtained by performing a sequence of optimizations over subspaces of the target signal parameters associated to a subset of all potential target trajectories, until one or more termination conditions are met.
10. The non-transitory machine-readable medium of claim 9 wherein the subset of all potential target trajectories being optimized is incrementally grown by selecting a next best trajectory to include by solving a maximum-weight path problem in a graph of allowable state transitions.
11. The non-transitory machine-readable medium of claim 10 wherein a trajectory from the subset of all potential target trajectories being optimized is updated as follows:
remove the trajectory from the subset and set the target signal parameters of the trajectory to zero;
reoptimize the target signal parameters of remaining trajectories of the subset in the absence of the removed trajectory; and
select the next best trajectory to include by solving the maximum-weight path problem in the graph of allowable state transitions.
12. The non-transitory machine-readable medium of claim 11 wherein the maximum-weight path problem is solved via a Viterbi algorithm.
13. The non-transitory machine-readable medium of claim 10 wherein the termination condition is that a weight of the next best trajectory to add is below a threshold.
14. The non-transitory machine-readable medium of claim 9 wherein the optimization over the subspace of associated target signal parameters is performed by iterative group coordinate descent, where at each iteration the set of all target signal parameters associated to a given target trajectory are jointly optimized while holding all other target signal parameters fixed.
15. The non-transitory machine-readable medium of claim 14 wherein the group coordinate descent is computed using a group shrinkage operation.
16. The non-transitory machine-readable medium of claim 1 , wherein:
the data fidelity objective is a squared norm of a difference between data of the one or more sensor frames and a sum of all target signal contributions predicted by the target signal parameters; and
the one or more sparsity objectives are each a mixture of a weighted group sparsity prior, corresponding to a sum over all potential target trajectories of a norm of weighted target parameters of each trajectory, and a number of target trajectories with one or more non-zero target signal parameters, with the weight on the number of target trajectories being increased in the sequence.
17. The non-transitory machine-readable medium of claim 1 , wherein the instructions, when executed by one or more processors, effectuate further operations comprising steps for displaying the final trajectories to a user.
18. A system comprising:
one or more sensors;
memory; and
one or more processors coupled to the one or more sensors, the one or more processors being configured to:
receive one or more sensor frames corresponding to the one or more sensors;
define a space of allowable target states for the one or more sensor frames;
specify a set of potential target trajectories, each comprising one allowable target state for each of the one or more sensor frames;
specify target signal parameters for each of the allowable target states, such that the target signal parameters predict an expected target signal contribution corresponding to the one or more sensor frames;
specify a data fidelity objective to quantify how well the target signal parameters match the one or more sensor frames;
specify a sequence of one or more sparsity objectives to penalize a number of detected targets;
determine trajectories of one or more targets as follows:
obtain values for all the target signal parameters in all the one or more sensor frames, the obtained values being initialized values or previously optimized values,
for each sparsity objective of the sequence, starting with the obtained target signal parameters, determine values for new target signal parameters to optimize a sum of the data fidelity objective and the given sparsity objective; and
store final determined trajectories in the memory.
19. The system of claim 18 , wherein the one or more sensors are electro-optical/infrared cameras.
20. The system of claim 18 , wherein the one or more sensors are radar sensors.
21. A non-transitory machine-readable medium storing instructions that when executed by one or more processors effectuate operations comprising:
receiving one or more sensor frames corresponding to the one or more sensors;
defining a space of allowable target states for the one or more sensor frames;
specifying a set of potential target trajectories, each comprising one allowable target state for each of the one or more sensor frames;
specifying target signal parameters for each of the allowable target states, such that the target signal parameters predict an expected target signal contribution corresponding to the one or more sensor frames;
specifying a data fidelity objective to quantify how well the target signal parameters match the one or more sensor frames;
specifying a sequence of one or more sparsity objectives to penalize a number of detected targets, wherein at least part of some of the one or more sparsity objectives are convex;
determining trajectories of one or more targets as follows:
obtaining values for all the target signal parameters in all the one or more sensor frames, the obtained values being initialized values or previously optimized values,
for each sparsity objective of the sequence, starting with the obtained values for the target signal parameters, determining new values for target signal parameters to optimize a sum of the data fidelity objective and the given sparsity objective; and
storing final determined trajectories in memory.