JP5084598B2 - Tracking processing apparatus and program - Google Patents

Description

  The present invention relates to a tracking processing apparatus that processes a multi-target tracking algorithm that simultaneously tracks a plurality of targets (hereinafter also referred to as targets), and more particularly, to a tracking processing apparatus that processes an MHT (Multiple Hyperthesis Tracking) algorithm. .

  The MHT algorithm is applied to the target multi-target tracking algorithm detected by the sensor, and it is indispensable to reduce the calculation load of the MHT algorithm in order to operate as a tracking processing device.

Currently, as a measure for reducing the calculation load of the MHT algorithm, there is an adoption of an algorithm that solves an n-Best solution search that is one of the processes constituting the MHT algorithm at high speed.
The processing for solving the n-Best solution search is a processing that is a heavy load among the MHT algorithms, and since this processing has conventionally been a bottleneck for MHT, a technique for speeding up the algorithm is considered (for example, Patent Document 1).
JP 2004-219299 A

However, due to the diversification of sensors, it is required to apply the MHT algorithm to the target multi-target tracking algorithm detected by a plurality of sensors. In the conventional tracking processing device, the number of tracks processed by the MHT algorithm becomes enormous, The calculation load of the wake state update has also come to show a high ratio in the entire calculation as with the n-Best solution search.
In particular, in multi-target tracking processing under high clutter, processing may not be completed within a required time.
In addition, if the targets are dense, the cluster processing effect of the MHT algorithm may be lost.

  In order to prevent this, it is necessary to distribute the calculation load of the part other than the n-Best solution search in the MHT algorithm, but it has not been realized so far.

The speedup of the conventional tracking processing device is mainly for speeding up the n-Best solution search, and the one corresponding to the speedup of the wake update processing has not been realized.
In the future, when processing detection data from diversifying sensors, it is not sufficient to perform the tracking process only by speeding up the n-Best solution search.

  The main object of the present invention is to solve such problems, and it is a main object of the present invention to improve the processing efficiency when the multi-target tracking algorithm is implemented and to shorten the processing time.

The tracking processing device according to the present invention is
A tracking processing device for tracking a target,
A multi-target tracking algorithm processing unit for performing a multi-target tracking algorithm by performing an n-Best solution search process for a hypothesis that is a combination of wakes representing a motion specification of a target;
While the multi-target tracking algorithm processing unit is performing the n-Best solution search process, the parent track that is an existing track is updated to generate a child track, and a new track that is independent from the parent track And a wake management unit that generates a wake as a new wake.

  According to the present invention, a multi-target tracking algorithm processing unit and a wake management unit are provided, and while the multi-target tracking algorithm processing unit performs n-Best solution search processing that takes processing time, the wake management unit performs child wakes. Since the new wake is generated, the child wake and the new wake can be generated without waiting for the end of the n-Best solution search process, and the processing time can be shortened.

Embodiment 1 FIG.
The first embodiment of the present invention will be described below with reference to the drawings.
In the present embodiment, a parallel tracking processing device (tracking processing device) that performs parallel processing separately for track management and other functions will be described.
FIG. 1 shows the configuration of a parallel tracking processing apparatus according to the first embodiment.

  The parallel tracking processing device 1 is connected to the sensor 2 and the external device 3, and includes a MHT processing unit 4 and a plurality of track management units 5, and is a multi-target tracking algorithm using detection data received from the sensor 2. This is a device that executes the MHT algorithm, generates wake information composed of a target estimated position, a target estimated speed, and the like, and outputs the wake information to the external device 3.

  The sensor 2 is a device that detects a target such as a radar or an infrared sensor at a constant cycle, and is connected to the parallel tracking processing device 1 and is configured by a detection time and a detection position obtained by detecting the target. Data is output to the parallel tracking processor 1.

  The external device 3 is connected to the parallel tracking processing device 1 and is a device that processes the wake information received from the parallel tracking processing device 1 such as a display and each sensor controller.

The MHT processing unit 4 is connected to each sensor 2, the external device 3, and the plurality of track management units 5, and controls the plurality of track management units 5 while detecting the MHT using detection data received at regular intervals from each sensor. The algorithm is executed, wake information is generated and output to the external device 3.
The MHT processing unit 4 is an example of a multi-target tracking algorithm processing unit.

The wake management unit 5 is connected to the MHT processing unit 4 and performs tracking filter processing for predicting a target position, a target speed, and the like from the data received from the MHT processing unit 4 to create, update, and manage the wake.
Each track management unit 5 may be connected to another track management unit 5.

The MHT processing unit 4 has the configuration shown in FIG. 2, and each track management unit 5 has the configuration shown in FIG.
Details of each element shown in FIGS. 2 and 6 will be described later.

Before describing in detail the configuration and operation of the parallel tracking processing device 1 according to the present embodiment, first, the main features of the parallel tracking processing device 1 will be outlined.
FIG. 8 shows a processing procedure of the MHT processing unit 4 and the wake management unit 5 of the parallel tracking processing device 1 according to the present embodiment.
Note that “to process” shown in FIG. 8 is a process performed by “to part” shown in FIG. 2 and FIG.
Specifically, the data reception process (S101) in FIG. 8 is performed by the detection data reception unit 6 in FIG. 2, and the detection data pack generation process (S102) in FIG. 8 is performed by the detection data pack generation unit 7 in FIG.
Further, the wake prediction process (S104) in FIG. 8 is performed by the wake prediction unit 21 in FIG. 6, and the wake correlation process (S105) in FIG. 8 is performed by the wake correlation unit 22 in FIG.
The same applies to other processes.

FIG. 9 shows the procedure of a conventional MHT process.
In FIG. 9, the processing corresponding to the processing of FIG.
That is, S201 is attached to the detection data reception process corresponding to the detection data reception process (S101) of FIG. 8, and S204 is attached to the wake prediction process corresponding to the wake prediction process (S104) of FIG.
The same applies to other processes.

With reference to FIG. 8 and FIG. 9, main features of the parallel tracking processing apparatus 1 according to the present embodiment will be described in comparison with the conventional MHT processing procedure.
Here, focusing on the processes before and after the n-Best solution search process (S108, S208), the difference between the conventional MHT process and the process of the parallel tracking processing apparatus 1 according to the present embodiment will be described.

As shown in FIG. 9, in the conventional MHT process, after the likelihood matrix is generated in the likelihood matrix generation process in S207, the n-Best solution search process in S208 is performed, and the n-Best solution search process ends. After that, the wake update / generation process of S206 is performed.
That is, the child track and the new track are generated based on the search result of the n-Best solution search process (S208).
Further, after the wake update / generation process, a hypothesis generation process (S209), a semi-optimization process (S210), and the like are performed.

On the other hand, in the parallel tracking processing device 1 according to the present embodiment, as shown in FIG. 8, after the likelihood matrix is generated in the likelihood matrix generation process of S107, the n-Best solution search process of S108 is performed. However, the wake update / generation process (S106) is started and completed before the n-Best solution search process (S108) ends.
That is, the wake update / generation process (S106) is performed while the n-best solution search process (S108) is being performed in the MHT processing unit 4.
The n-Best solution search process is for selecting n (n ≧ 2) hypotheses that are combinations of wakes representing the motion specifications (position, velocity, acceleration, etc.) of the target in descending order of reliability. It is processing.
In the hypothesis generation process (S109), the hypothesis is updated by combining the existing hypothesis (the hypothesis one cycle before) with the detection data (observation vector) of the current cycle to generate a child hypothesis. Since a hypothesis is a combination of wakes, if all of the existing hypotheses (one hypothesis before) are used to generate a child hypothesis, the amount of calculation processing becomes enormous, so the reliability is high before generating the child hypothesis. It is necessary to select a predetermined number of hypotheses from those. For this reason, a calculation for selecting a hypothesis is performed in the n-Best solution search process (S108).
Since this n-Best solution search process (S108) requires a long time process, in this embodiment, while the MHT processing unit 4 is performing the n-Best solution search process (S108), each track When the management unit 5 performs a track update / generation process (S106) to generate a child track and a new track, and the n-Best solution search process is completed, the MHT processing unit 4 performs a search result in the n-Best solution search process. Is transmitted to each wake management unit 5 (search processing result data).
The child wake is a wake after updating the previous wake (parent wake) using the detection data of the current cycle. The new wake is a new wake that is generated from the detection data of the current cycle and is independent of the parent wake.
Then, each wake management unit 5 selects a specific child wake and new wake from the generated child wake and new wake based on the search result in the wake selection process (S113).
As described above, in the present embodiment, the child wake and the new wake are generated during the time-consuming n-Best solution search process to shorten the processing time.

Further, as described above, in the conventional MHT process of FIG. 9, after the n-Best solution search process (S208) ends, the wake update / generation process (S206) ends, and then the hypothesis generation process (S209), Although the optimization process (S210) and the like are performed, the parallel tracking processing apparatus 1 according to the present embodiment is independent from the wake update / generation process (S109) after the n-Best solution end search process (S108) ends. Then, hypothesis generation processing (S109), semi-optimization processing (S110), and the like are performed.
For this reason, also in this point, the processing time is shortened.
Details of each process shown in FIG. 8 will be described later.

  Hereinafter, each element of the MHT processing unit 4 and the track management unit 5 will be described, but prior to that, terms used in the following description will be described.

About Wake and Proxy Wake A conventional wake is data composed of tracking filter data for predicting a target position, a target speed, etc., a main wake flag, and a detection data ID list.
This wake flag is a flag indicating whether or not the wake is confirmed as a true target.
The detection data ID list is a set of detection data (or a set of IDs of detection data) that would have been obtained from the same target.
A wake in this embodiment (hereinafter simply referred to as a wake) is a wake having tracking filter data for a conventional wake.
The proxy wake is obtained by removing the tracking filter data, which requires a processing load, from the conventional wake. In simple terms,
Conventional wake = proxy wake + wake.
The proxy wake and the wake correspond one-on-one. For this reason, the wake ID of a wake corresponding to the proxy wake is included in the proxy wake.
That is, the proxy wake is composed of a main wake flag, a detection data ID list, and a wake ID corresponding to the wake. In this way, the proxy track represents the attributes required for the MHT algorithm from the track.
In order to generate and update a wake, tracking filter processing is required. In this embodiment, as described above, wake generation / update processing (S106 in FIG. 8) is performed in each wake management unit 5. Therefore, the tracking filter process is performed by each track management unit 5 and is not performed by the MHT processing unit 4. Instead, the MHT processing unit 4 uses a detection data ID list, which is a set of detection data (or a set of detection data IDs), as a proxy wake, and performs hypothesis generation processing (FIG. 8) without tracking filter processing. S109), semi-optimization processing (S110), etc. are performed.
The tracking filter process is a process (algorithm) for estimating the true value of the motion specification of the target, and is realized by a Kalman filter or an α-β filter.
Since the tracking filter process is a function like a collection of matrix operations, the total number of times for updating the tracking filter for each track increases as the number of conventional tracks increases. Since it was assumed that the conventional MHT processing was performed by one CPU (Central Processing Unit), if the number of conventional tracks increased, the entire processing time was directly affected. Therefore, in the present embodiment, the conventional wake is divided into a tracking filter and other functions, each tracking filter process is distributed to a plurality of CPUs (a plurality of wake management units), and a process other than the tracking filter process is performed. Is performed by another CPU (MHT processing unit) to reduce the overall processing time. In the present embodiment, tracking filter data distributed to a plurality of CPUs is defined as a wake, and data for other functions is defined as a proxy wake.
Further, as will be described later, in the MHT processing unit 4, once the likelihood matrix is generated, only the information included in the proxy wake is used, so that communication with the wake management unit 5 is not performed, and n-Best It is possible to perform a series of processing from solution search processing (S108 in FIG. 8), hypothesis generation processing (S109), semi-optimization processing (S110), wake establishment processing (S111), and wake arrangement processing (S112). Become. That is, each track management unit 5 can update the tracking filter, and the MHT processing unit 4 can perform other processing.

About the child track The child track in the present embodiment uses the detection data of the current cycle (hereinafter referred to as detection data k) to track the track of the previous cycle (hereinafter referred to as track k-1). This is the wake after updating the filter status.
The child wake is registered in the wake DB 30 (FIG. 8) as a wake of the current cycle (hereinafter referred to as wake k).

Sub-substitute wake The sub-substitute wake according to the present embodiment is a proxy wake obtained by adding detection data k to the one-cycle previous proxy wake (hereinafter referred to as a proxy wake k-1).
That is, if the detection data ID list of the proxy wake k-1 is composed of the detection data D1, D2, and D3, and the detection data ID of the detection data k is D4, the detection of the child proxy wake of the proxy wake k-1 The data ID list is (D1, D2, D3, D4).
The child proxy track is registered in the proxy track DB as a proxy track of the current cycle (hereinafter referred to as proxy track k).

About the Hypothesis The hypothesis in the present embodiment describes which of the plurality of proxy wakes is to be adopted. There are a plurality of hypotheses, and the number thereof is the number output by the n-Best solution search unit 10 (FIG. 2).

Child Hypothesis The child hypothesis in the present embodiment is the current hypothesis (hereinafter referred to as hypothesis k) from which the hypothesis k-1 is derived using the detection data k.
The child hypothesis is registered in the hypothesis DB 18 (FIG. 2) as the hypothesis k.

About semi-optimization Semi-optimization is aimed at extracting important child hypotheses from all generated child hypotheses and deleting useless child hypotheses.
As a semi-optimization technique, there are n-ScanLimit, cumulative reliability limit, and the like.

A flow for generating a child proxy track and a child hypothesis from the proxy track k-1, the hypothesis k-1, and the detection data k is shown below.
Assume that the following three surrogate wakes k-1 exist.
T1 = {D11, D23} The proxy track T1 includes detection data D11, D23.
T2 = {D11, D22} The proxy track T2 includes detection data D11, D22.
T3 = {D13, D24} The proxy wake T3 includes detection data D13, D24.
It is assumed that the following two hypotheses k-1 exist.
H1 = {T1, T2} Hypothesis 1 adopts proxy wakes T1, T2.
H2 = {T2, T3} Hypothesis 2 adopts proxy wakes T2, T3.
Assume that three detection data k, D31, D32, and D33, are input.
Assuming that the n-Best solution search unit generates a child hypothesis 1 in which hypothesis 1 to D31 is connected to T2 and D33 is connected to T1, and hypothesis 2 to D32 is a child hypothesis 2 to be connected to T3 and D33 is connected to T2. A child proxy wake is generated as follows.
Child proxy track 1 = {D11, D23, D33} T1 and D33 are connected Child proxy track 2 = {D11, D22, D31} T2 and D31 are connected Child proxy track 3 = {D13, D24, D32} Child surrogate track 4 where T3 and D32 are connected = {D11, D22, D33} The child hypothesis where T2 and D33 are connected is as follows.
Child hypothesis 1 = {Sub-substitute wake 1, Sub-substitute wake 2}
Child Hypothesis 2 = {Child Proxy Track 2, Child Proxy Track 3}

Next, the function of the MHT processing unit 4 will be described with reference to FIG.
FIG. 2 shows a configuration of the MHT processing unit 4 according to the first embodiment.

  The detection data receiving unit 6 is connected to each sensor 2 and the detection data pack generation unit 7, receives detection data from each sensor 2, and outputs the detection data to the detection data pack generation unit 7.

The detection data pack generation unit 7 is connected to the detection data reception unit 6, the likelihood matrix generation preparation unit 8, and the communication unit 20, and is obtained from the same sensor from the detection data received from the detection data reception unit 6. A detection data pack that is a set of detection data having the same detection time is generated, the detection data pack is output to the likelihood matrix generation preparation unit 8, and the detection data pack is transmitted to each track management unit 5. The same detection data pack is transmitted to each track management unit 5.
At this time, a unique detection data ID is assigned to each detection data of the detection data pack.
When a plurality of detection data packs are generated, the detection data packs are output to the likelihood matrix generation preparation unit 8 and each track management unit 5 for each detection data pack.
The detection data pack includes detection data and detection sensor information.

The likelihood matrix generation preparation unit 8 is connected to the detection data pack generation unit 7 and the likelihood matrix generation unit 9, and based on the detection data pack received from the detection data pack generation unit 7, the unnecessary signal density and the new target The density is calculated, an unnecessary signal part likelihood matrix and a new wake part likelihood matrix are generated, and output to the likelihood matrix generation unit 9.
FIG. 3 shows configurations of the unnecessary signal portion likelihood matrix and the new wake portion likelihood matrix.

The likelihood matrix generation unit 9 is connected to the likelihood matrix generation preparation unit 8, the communication unit 20, and the n-Best solution search unit 10, and includes an unnecessary signal portion likelihood matrix input from the likelihood matrix generation preparation unit 8 and The new wake part likelihood matrix is combined with the existing wake part likelihood matrix received from each wake management part 5 to create a likelihood matrix and output it to the n-Best solution search part 10.
In FIG. 4, the structure of the existing wake part likelihood matrix and likelihood matrix is shown.

The hypothesis DB 18 is connected to the n-Best solution search unit 10 and the track arrangement unit 14, and when accessed from the n-Best solution search unit 10, the hypothesis one cycle before (hereinafter referred to as hypothesis k-1). .) Further, from the wake organizing unit 14, the hypothesis k-1 is updated with the current hypothesis (hereinafter referred to as hypothesis k).
The hypothesis is composed of a set of track IDs of the adopted proxy track and the hypothesis reliability.

The n-Best solution search unit 10 is connected to the likelihood matrix generation unit 9, the hypothesis DB 18, the hypothesis generation unit 11, and the communication unit 20, and is acquired from the likelihood matrix input from the likelihood matrix generation unit 9 and the hypothesis DB 18. From the hypothesis k-1, an n-Best solution search is performed to generate a correlation matrix, and the correlation matrix is output to the hypothesis generation unit 11.
Further, the existing wake part correlation matrix corresponding to the wake managed by each wake management part 5 is transmitted to each wake management part 5. Here, when the n-Best solution search is performed, a plurality of correlation matrices are generated. Therefore, each time the correlation matrix is generated, the existing wake part correlation matrix may be transmitted to each wake management part 5, The logical sum of the correlation matrix may be taken and the existing wake part correlation matrix may be transmitted to each wake management part 5.
Further, the new wake part of the correlation matrix is transmitted to each wake management part 5. Here, the new target part correlation matrix is transmitted to one wake management unit 5 for one detection target so that wakes are not managed redundantly by each wake management unit 5. A new wake ID corresponding to the destination wake management unit 5 is assigned to the new target part correlation matrix.
FIG. 5 shows the structure of the correlation matrix.

The proxy wake DB 19 is connected to the hypothesis generator 11 and the wake organizer 14, and when accessed from the hypothesis generator 11, the proxy wake one cycle before (hereinafter referred to as proxy wake k−1). keeping. Further, from the wake organizing unit 14, the proxy wake k-1 is updated with the current proxy wake (hereinafter referred to as the proxy wake k).
The proxy track includes a track ID corresponding to the track held by each track management unit 5, a main track flag, and a list of the latest detection data IDs corresponding to the number of n-ScanLimits.

  The hypothesis generation unit 11 is connected to the n-Best solution search unit 10, the proxy track DB 19, and the semi-optimization unit 12, and the proxy matrix acquired from the correlation matrix and the proxy track DB 19 input from the n-Best solution search unit 10. A child hypothesis and a child proxy track are generated from k−1 and output to the semi-optimization unit 12.

The semi-optimization unit 12 is connected to the hypothesis generation unit 11, the track establishment unit 13, and the communication unit 20, and extracts and extracts important child hypotheses from the child hypotheses and child proxy tracks input from the hypothesis generation unit 11. The child hypothesis is transmitted to the wake establishment unit 13.
There are several quasi-optimization methods. Here, the following two will be described.
(1) n-ScanLimit
(2) Cumulative reliability limit In n-ScanLimit, the list of detection data IDs included in the child proxy track input from the hypothesis generation unit 11 is considered to be the same as the child proxy track that is the same as the number of the latest n-ScanLimit. And the track IDs included in those child proxy tracks are transmitted as the integration target track IDs to the track management unit 5 that manages the tracks having the track IDs included in these child proxy tracks.
Further, the child hypotheses whose child hypotheses are the same in n-ScanLimit are integrated.
In the cumulative reliability restriction, the hypotheses included in the child hypothesis input from the hypothesis generation unit 11 are added in order from the highest hypothesis reliability, leaving the child hypotheses until a certain value is reached, and deleting other child hypotheses. . Then, the reliability of the remaining child hypotheses is normalized.

The wake establishment unit 13 is connected to the quasi-optimization unit 12, the wake arrangement unit 14, and the communication unit 20. Among the sub-optimized child hypotheses input from the quasi-optimization unit 12, a certain quasi When the number of elements in the detection data ID list included in the child proxy wake input from the sub-optimization unit 12 adopted in the child hypothesis after optimization exceeds a certain number, the child proxy wake is set as the main wake, The child proxy wake input from the semi-optimizing unit 12 is output to the wake organizing unit 14.
Further, among the sub-optimized child hypotheses input from the sub-optimization unit 12, the sub-optimized child hypotheses not including this wake are deleted, and the remaining hypothesis reliability of the sub-optimized child hypotheses is determined. Normalization is performed and the result is output to the wake organizing unit 14.
In addition, among the sub-optimized child hypotheses received from the sub-optimizing unit 12, the track ID included in the main track adopted in the sub-optimized child hypothesis having the highest hypothesis reliability is transmitted. The wake ID is transmitted to the wake management unit 5.

The wake organizing unit 14 is connected to the wake establishing unit 13, the hypothesis DB 18, the proxy wake DB 19, the wake distributing unit 15, and the communication unit 20, and among the child proxy wakes after the wake establishment established from the wake establishing unit 13, the wake The track ID of the child proxy track after the establishment of the track that has not been adopted from any of the child hypotheses after the establishment of the track input from the establishment unit 13 is transmitted to the track management unit 5 as the deletion target track ID, and the child proxy track is deleted. To do.
Further, the track ID of the child proxy track after establishment of the remaining track is transmitted to each track management unit 5 as a transfer target track ID according to the following conditions.
By transmitting the transfer target track ID, it is possible to notify the transfer source track management unit 5 of the transfer target track.
The conditions are as follows. In the following, they are listed in order of priority.
(1) The number of transfers shall be within the maximum number of transfers.
(2) Tracks in which the elements of the detection data ID list included in each proxy track match (n-ScanLimit number-1) from the latest elements are managed by the same track management unit 5. .
(3) Transfer from the wake management unit 5 having a large number of wakes to the small wake management unit 5.
Further, the track ID of the child proxy track after the establishment of the track determined to be transferred is changed to the track ID corresponding to the track management unit 5 of the transfer destination, and is output to the track distribution unit 15 together with the transfer destination as a transfer table. .
The transfer table includes a transfer target track ID, a post-transfer track ID, and a transfer destination (transfer destination track management unit 5).

  The wake distribution unit 15 is connected to the wake management unit 14 and the communication unit 20, receives the child track to be transferred from the wake management unit 5 of the transfer source, and based on the transfer table input from the wake management unit 14. The transfer destination track management unit 5 is determined, the track ID of the transfer target child track is changed to the post-transfer track ID, and the received transfer target child track is transmitted to the transfer destination track management unit 5 as the transfer track.

  The wake information generation unit 16 is connected to the wake information transmission unit 17 and the communication unit 20, creates wake information to be transmitted to the external device 3 from the wake information received from each wake management unit 5, and the wake information transmission unit. 17 output.

  The wake information transmission unit 17 is connected to the wake information generation unit 16 and the external device 3, and transmits the wake information input from the wake information generation unit 16 to the external device 3.

Hereinafter, the function of the wake management unit 5 will be described with reference to FIG.
FIG. 6 shows a configuration of the wake management unit 5 according to the first embodiment.

The wake DB 30 is connected to the wake prediction unit 21 and the wake DB update unit 28. When accessed from the wake prediction unit 21, the wake DB 30 holds a wake one cycle before (hereinafter referred to as a wake k-1). ing. Further, the wake k-1 is updated from the wake DB update unit 28 with the current wake (hereinafter referred to as wake k).
The wake includes a wake ID, tracking filter data, various flags, and the like.

The wake prediction unit 21 is connected to the communication unit 31, the wake DB 30, the wake correlation unit 22, and the wake update / generation unit 23, and the wake k−1 acquired from the wake DB 30 is received from the MHT processing unit 4. The predicted track (hereinafter referred to as predicted track k) is transmitted to the track correlation unit 22 and the track update / generation unit 23. Prediction is performed by predicting the tracking filter data included in the wake.
Further, the detection data included in the detection data pack received from the MHT processing unit 4 is output to the wake correlation unit 22.

The wake correlation unit 22 is connected to the wake prediction unit 21, the wake update / generation unit 23, and the communication unit 31, and performs correlation determination based on detection data input from the wake prediction unit 21 and predicted wake k input from the wake prediction unit 21. If there is a correlation, the gate internal / external determination matrix is generated as inside the gate, and if there is no correlation, the gate internal / external determination matrix and the detection data input from the wake prediction unit 21 are output to the wake update / generation unit 23. To do.
Further, the likelihood is calculated from the detection data input from the wake prediction unit 21 and the predicted wake k input from the wake prediction unit 21 to generate an existing wake part likelihood matrix of each wake management unit 5, and the MHT processing unit 4. Send to.
FIG. 7 shows the configuration of the gate internal / external determination matrix.

  The wake update / generation unit 23 is connected to the wake correlation unit 22, the wake prediction unit 21, and the wake selection unit 24. The in-gate determination matrix and detection data input from the wake correlation unit 22, and input from the wake prediction unit 21. A child track (including a memory track) and a new track are generated based on the predicted track k, and are output to the track selection unit 24. At this time, the child track (including the memory track) inherits the track ID of the corresponding predicted track k, but the track ID of the new track is not set.

  The wake selection unit 24 is connected to the wake update / generation unit 23, the communication unit 31, and the wake integration unit 25. Among the child wakes (including memory tracks) and the new wakes input from the wake update / generation unit 23, the MHT is selected. The child tracks (including memory tracks) and new tracks that have no correlation in the existing track portion correlation matrix and the new track portion correlation matrix received from the processing unit 4 are deleted, and the remaining child tracks (including memory tracks) and new tracks are deleted. Is output to the track integration unit 25 as a child track after selection of the track. Here, the track ID added to the new track portion correlation matrix is set to the track ID of the new track that is correlated in the new track portion correlation matrix received from the MHT processing unit 4.

  The track integration unit 25 is connected to the track selection unit 24, the communication unit 31, and the transmission target track setting unit 26, and received from the MHT processing unit 4 among the child tracks after the track selection input from the track selection unit 24. The child tracks corresponding to the integration target track ID are integrated and output to the transmission target track setting unit 26 as a child track after integration of the tracks.

  The transmission target track setting unit 26 is connected to the track integration unit 25, the communication unit 31, and the track transfer unit 27, and is received from the MHT processing unit 4 among the child tracks after the track integration input from the track integration unit 25. The transmission flag of the child track having the track ID corresponding to the transmission target track ID is turned on, the transmission flags of the other child tracks are turned off, and the child track after the transmission flag is set is output to the track transfer unit 27.

The wake transfer unit 27 is connected to the transmission target track setting unit 26, the communication unit 31, and the wake DB update unit 28. Among the child wakes after the transmission flag is set input from the transmission target track setting unit 26, the MHT processing unit 4 deletes the child wake having the track ID corresponding to the deletion coping track ID received from 4 and transmits the child wake corresponding to the transfer target track ID received from the MHT processing unit 4 to the MHT processing unit 4 as the transfer target child wake. To do.
In addition, the child wake that is not the transfer target in the above process is output to the wake DB update unit 28 as the non-transfer target child wake.

The wake DB update unit 28 is connected to the wake transfer unit 27, the communication unit 31, the transmission target track information generation unit 29, and the wake DB 30, and from the non-transfer target child track and MHT processing unit 4 input from the wake transfer unit 27. The received transfer wake is set as the wake k, and the wake k-1 in the wake DB 30 is updated with the wake k.
Further, the wake k whose transmission flag is ON among the wakes k is output to the transmission target track information generation unit 29 as the transmission target track k.

  The transmission target track information generation unit 29 is connected to the track DB update unit 28 and the communication unit 31, and generates transmission target track information based on the filter information of the transmission target track k input from the track DB update unit 28. Transmit to the MHT processing unit 4.

Next, an operation procedure of the parallel tracking processing apparatus 1 according to the present embodiment will be described with reference to FIG.
In addition, since the operation | movement of the parallel tracking processing apparatus 1 which concerns on this Embodiment is a parallel process, the process flow of the MHT process part 4 and the wake management part 5 is described alternately.

Processing of MHT Processing Unit 4 In step S <b> 101, the detection data receiving unit 6 receives detection data from the sensor 2.
Next, in S102, the detection data pack generation unit 7 generates a detection data pack from all the detection data k, and the communication unit 20 transmits the detection data pack to all the track management units 5. In addition, the process of S104 mentioned later of each wake management part 5 is also started here.
Next, in S103, the likelihood matrix generation preparation unit 8 generates an unnecessary signal part likelihood matrix and a new wake part likelihood matrix from the detection data pack.
From this point onward, if the existing wake part likelihood matrix is not received from the wake management part 5, the process cannot proceed.

Process of Each Track Management Unit 5 First, in S104, the communication unit 31 receives the detection data pack, and the track prediction unit 21 performs a tracking filter prediction process from the received detection data pack and the track k−1. A predicted wake k is generated.
Next, in S105, the wake correlation unit 22 generates a gate internal / external determination matrix that determines the correlation between all the detection data included in the detection data pack and the predicted wake, and the communication unit 31 transmits the matrix to the MHT processing unit 4. .
Next, in S106, the wake update / generation unit 23 generates a child wake and a new wake from the predicted wake k, the gate inside / outside determination matrix, and all the detection data k.
In addition, after this, unless the existing wake part correlation matrix and the new wake part correlation matrix are received from the MHT processing part 4, the process cannot proceed.

In the processing S107 of the MHT processing unit 4, the communication unit 20 receives the existing track part likelihood matrix, and the likelihood matrix generation unit 9 generates an unnecessary signal part likelihood matrix generated by the likelihood matrix generation preparation unit 8, A likelihood matrix is generated from the new wake part likelihood matrix and the received existing wake part likelihood matrix.
Next, in S108, the n-Best solution search unit 10 generates a correlation matrix from the likelihood matrix and all hypotheses k-1, and the existing wake part correlation matrix which is a matrix of all existing wake parts of the correlation matrix and Then, a new wake part correlation matrix which is a matrix of the new wake part of the correlation matrix is generated, and the communication unit 20 transmits the existing wake part correlation matrix and the new wake part correlation matrix to all the wake management parts 5. In addition, S113 mentioned later of each wake management part 5 is also started here.
Next, in S109, the hypothesis generation unit 11 generates a child hypothesis and a child proxy track from the correlation matrix and the proxy track k-1 by the n-Best solution search unit 10.
Next, in S110, the quasi-optimization unit 12 generates a quasi-optimized child hypothesis and a quasi-optimized child proxy wake from the child hypothesis and the child proxy wake, and sets the track ID of the integrated proxy wake as the integration target track. The communication unit 20 transmits the integration target track ID to the track management unit 5.
Next, in S111, the wake establishment unit 13 generates the wake-established child hypothesis and the wake-established child proxy wake from the quasi-optimized child hypothesis and the quasi-optimized child proxy wake, and is the main wake. The track ID of the confirmed proxy track is set as a transmission target track ID, and the communication unit 20 transmits the transmission target track ID to the track management unit 5.
Next, in S112, the wake organizing unit 14 generates a transfer table from the post-established child hypothesis and the wake-established child proxy wake, and the wake ID of the wake that needs to be transferred needs to be deleted. The wake ID of a certain wake is set as a deletion target wake ID, and the communication unit 20 transmits the transfer target wake ID and the deletion wake ID to the wake management unit 5. Further, the child hypothesis after the wake establishment is registered in the hypothesis DB 18 as the hypothesis k, and the child proxy wake after the wake establishment is registered in the proxy wake DB 19 as the proxy wake k.
From this point onward, it is not possible to proceed to the previous processing without receiving the transfer target child track from the track management unit 5.

Processing in each track management unit 5 In S113, the communication unit 30 receives the existing track unit correlation matrix and the new track unit correlation matrix transmitted from the MHT processing unit 4, and the track selection unit 24 uses the track update / generation unit 23. A specific child wake and a new wake are selected from the child wake and the new wake generated by, and the existing wake part correlation matrix and the new wake part correlation matrix received from the MHT processing unit 4, and set as the child wake after the wake selection.
Here, the wake selection procedure will be described.
All the wake management units 5 receive the existing wake unit correlation matrix and the new wake unit correlation matrix transmitted from the MHT processing unit 4 (n-Best solution search unit 10), and correspond to the wake of the wake management unit 5 The track selection is performed referring to the item to be performed.
The wake management unit 5 generates child wakes for all combinations, and the existing wake part correlation matrix describes the combination of which wake is connected to which detection data, so it is described in the existing wake part correlation matrix. The child wake corresponding to the combination that has been made is left, and the child wake not corresponding is deleted. In addition, all new tracks corresponding to all detection data are also generated, and the new track part correlation matrix describes which detection data becomes the new track, so it is described in the new track part correlation matrix. A new track is left, and a new track not described is deleted.
That is, the n-Best solution search unit 10 outputs a solution (existing wake part correlation matrix and new wake part correlation matrix) as to which proxy wake k-1 and which detection data k are connected, and this solution is used for each wake management. Transmitted to the unit 5. The existing wake part correlation matrix is a matrix of all existing wake parts of the correlation matrix output from the n-Best solution search part 10, the row indicates each detection data k, the column indicates each proxy wake k-1, and the value. Represents the correlation between the detection data k of the row and the wake k-1 of the column. The new wake part correlation matrix is a matrix of the new wake part of the correlation matrix output from the n-Best solution search part 10, the row and column are the respective detection data k, and the values are the detection data k is new. Indicates whether it is a goal or not. Here, when there is a new target, a proxy track ID without duplication is allocated.
For example, there are three detection data k, D1, D2, and D3, two proxy wakes k-1 exist, T1 and T2, D1 is correlated with T1, D2 is correlated with T2, and D3 is new. If it is a target, the existing wake part correlation matrix is as follows.

  The new wake part correlation matrix is as follows.

  These existing wake part correlation matrices and new wake part correlation matrices are created by the number of solutions output by the n-Best solution search unit 10. Then, all existing wake part correlation matrices and new wake part correlation matrices are transmitted to all wake management parts 5. Each wake management unit 5 has already generated a child wake and a new wake using all the detection data k and the wake k-1 of the wake management unit by the wake update / generation unit. When the matrix and the new wake part correlation matrix are received, only the child wake and the new wake corresponding to the correlated or new target combination are left, and the other wakes are deleted.

Processing of Each Track Management Unit 5 In S114, the communication unit 31 receives the integration target track ID from the MHT processing unit 4, and the track integration unit 25 selects the track selection post-track selected by the track selection unit 24 and From the integration target track ID, the child tracks after the wake selection are integrated to form the child track after the wake integration.
In S115, the communication unit 31 receives the transmission target track ID from the MHT processing unit 4, and the transmission target track setting unit 26 uses the track integrated child track integrated with the track integration unit 25 and the transmission target track ID. After the transmission flag is set, a child wake is generated.
Further, in S116, the communication unit 31 receives the transfer target track ID and the deletion target track ID from the MHT processing unit 4, and the wake transfer unit 27 transmits the transmission corresponding to the deletion target track ID after the transmission flag is set. Delete child track after setting flag. In addition, after the transmission flag is set, a track corresponding to the transfer target track ID is set as the transfer target child track, and the communication unit 31 transmits the transfer target child track to the MHT processing unit 4.
In addition, after that, unless the transfer wake is received from the MHT processing unit 4, the process cannot proceed.

Processing of MHT Processing Unit 4 Next, in S117, the wake distribution unit 15 generates a transfer wake from the transfer table and the transfer target child track, and the communication unit 20 transmits the transfer wake to the wake management unit 5.
Thereafter, unless the transmission target track information is received from the track management unit 5, the process cannot proceed.

Processing in each track management unit 5 In S118, the communication unit 31 receives the transfer track from the MHT processing unit 4, and the track DB update unit 28 registers the transfer target child track and the transfer track as the track k in the track DB. . Further, a wake k whose transmission flag is ON is set as a transmission target wake k.
Next, in S119, the transmission target track information generation unit 29 generates transmission target track information from the transmission target track k, and the communication unit 31 transmits the transmission target track information to the MHT processing unit 4.
And each wake management part 5 returns a process to S104.

Processing of MHT Processing Unit 4 In S120, the communication unit 20 receives transmission target track information from each track management unit 5, and the track information generation unit 16 generates track information from all transmission target track information.
Next, in S <b> 121, the wake information transmission unit 17 transmits the wake information to the external device 3. Then, the MHT processing unit 4 returns the processing to S101.

As described above, in the conventional MHT processing, the n-Best solution search is performed, and then the child track and the new track that have been adopted in the hypothesis are generated. During the best solution search, the wake management unit generates child wakes and new wakes for all combinations in advance, and selects only the child wakes and new wakes adopted as hypotheses by the n-best solution search. , Reducing processing time.
In the present embodiment, since the wake is distributed and managed by each wake management unit, the processing time at the time of wake correlation can be reduced.

In the above description, in the transfer of the wake, the transfer target wake management unit 5 transmits the transfer target wake to the MHT processing unit 4, and the MHT processing unit 4 receives the transfer target received from the transfer wake management unit 5. In the above example, the wake track is transmitted to the wake management unit 5. However, when each wake management unit 5 is connected, between the wake management unit 5 of the transfer source and the wake management unit 5 of the transfer destination, The wake to be transferred may be transmitted and received directly (without going through the MHT processing unit 4).
In this case, for example, the MHT processing unit 4 outputs a transfer notification for notifying the transfer source track management unit 5 of the transfer destination track management unit 5 and the transfer target track, and each track management unit 5 When a transfer notification is input from the processing unit 4, the wake to be transferred is output to the wake management unit 5 of the transfer destination notified in the transfer notification.

  As described above, in the present embodiment, a parallel tracking processing apparatus including an MHT processing unit that generates and manages a proxy wake that is an alternative to a wake processed by the MHT algorithm, which is a multi-target tracking algorithm, and that implements the MHT algorithm is described. did.

  In the present embodiment, the parallel tracking processing apparatus including the track management unit that manages the tracks processed by the MHT algorithm has been described.

  In the present embodiment, the parallel tracking processing apparatus having the function of distributing the detection data pack, which is the processing unit of the MHT algorithm, to the wake management unit has been described.

  Further, in the present embodiment, it has been described that the MHT processing unit omits the cluster processing of the MHT algorithm.

  Further, in the present embodiment, the parallel tracking processing device has been described as having a wake distribution function that distributes the calculation load of the wake management unit.

  Further, in the present embodiment, the parallel tracking processing apparatus having a function of transferring a wake through each MHT processing unit or directly between each wake management unit has been described.

  Further, in the present embodiment, while the MHT processing unit is performing the n-Best solution search that is a part of the MHT algorithm processing, the wake management unit generates a child track and a new track, and the MHT processing unit A parallel tracking processing device having a function of performing wake-up sorting when an n-Best solution search solution is calculated has been described.

Finally, a hardware configuration example of the parallel tracking processing device 1 shown in the first embodiment will be described.
FIG. 10 is a diagram illustrating an example of hardware resources of the parallel tracking processing device 1 illustrated in the first embodiment.
10 is merely an example of the hardware configuration of the parallel tracking processing device 1, and the hardware configuration of the parallel tracking processing device 1 is not limited to the configuration described in FIG. There may be.

In FIG. 10, the parallel tracking processing device 1 includes a CPU 911 (also referred to as a central processing unit, a central processing unit, a processing unit, an arithmetic unit, a microprocessor, a microcomputer, and a processor) that executes a program.
As described above, the parallel tracking processing device 1 according to the first embodiment includes a plurality of CPUs 911.
The CPU 911 is connected to, for example, a ROM (Read Only Memory) 913, a RAM (Random Access Memory) 914, a communication board 915, a display device 901, a keyboard 902, a mouse 903, and a magnetic disk device 920 via a bus 912. Control hardware devices.
Further, the CPU 911 may be connected to an FDD 904 (Flexible Disk Drive) or a compact disk device 905 (CDD).
Further, it may be connected to a printer device or a scanner device (not shown).
Further, instead of the magnetic disk device 920, a storage device such as an optical disk device or a memory card (registered trademark) read / write device may be used.
The RAM 914 is an example of a volatile memory. The storage media of the ROM 913, the FDD 904, the CDD 905, and the magnetic disk device 920 are an example of a nonvolatile memory. These are examples of the storage device.
A communication board 915, a keyboard 902, a mouse 903, a scanner device, an FDD 904, and the like are examples of input devices.
Further, the communication board 915, the display device 901, the printer device, and the like are examples of an output device.

  The communication board 915 is connected to the network. For example, the communication board 915 is connected to a LAN (Local Area Network), the Internet, a WAN (Wide Area Network), or the like.

The magnetic disk device 920 stores an operating system 921 (OS) program group 923 and a file group 924. Further, a window system 922 may be stored.
The programs in the program group 923 are executed by the CPU 911 using the operating system 921. The CPU 911 can use the window system 922 if necessary.

The RAM 914 temporarily stores at least part of the operating system 921 program and application programs to be executed by the CPU 911.
The RAM 914 stores various data necessary for processing by the CPU 911.

The ROM 913 stores a BIOS (Basic Input Output System) program, and the magnetic disk device 920 stores a boot program.
When the parallel tracking processing device 1 is activated, the BIOS program in the ROM 913 and the boot program in the magnetic disk device 920 are executed, and the operating system 921 is activated by the BIOS program and the boot program.

  The program group 923 stores a program for executing the function described as “˜unit” in the description of the first embodiment. The program is read and executed by the CPU 911.

In the file group 924, in the description of the first embodiment, “determination of”, “calculation of”, “comparison of”, “prediction of”, “search for”, “generation of”, Information, data, signal values, variable values, and parameters indicating the results of the processing described as “updating”, “setting of”, “registration of”, “selection of”, etc. And “˜database”.
The “˜file” and “˜database” are stored in a recording medium such as a disk or a memory. Information, data, signal values, variable values, and parameters stored in a storage medium such as a disk or memory are read out to the main memory or cache memory by the CPU 911 via a read / write circuit, and extracted, searched, referenced, compared, and calculated. Used for CPU operations such as calculation, processing, editing, output, printing, and display.
Information, data, signal values, variable values, and parameters are stored in the main memory, registers, cache memory, and buffers during the CPU operations of extraction, search, reference, comparison, calculation, processing, editing, output, printing, and display. It is temporarily stored in a memory or the like.
In addition, the arrows in the flowchart described in the first embodiment mainly indicate input and output of data and signals. The data and signal values are the RAM 914 memory, the FDD 904 flexible disk, the CDD 905 compact disk, and the magnetic disk device. It is recorded on a recording medium such as a 920 magnetic disk, other optical disks, minidisks, and DVDs. Data and signals are transmitted online via a bus 912, signal lines, cables, or other transmission media.

  In addition, what is described as “˜unit” in the description of Embodiment 1 may be “˜circuit”, “˜device”, “˜device”, and “˜step”, “˜”. “Procedure” and “˜Process” may be used. That is, what is described as “˜unit” may be realized by firmware stored in the ROM 913. Alternatively, it may be implemented only by software, or only by hardware such as elements, devices, substrates, and wirings, by a combination of software and hardware, or by a combination of firmware. Firmware and software are stored as programs in a recording medium such as a magnetic disk, a flexible disk, an optical disk, a compact disk, a mini disk, and a DVD. The program is read by the CPU 911 and executed by the CPU 911. That is, the program causes the computer to function as the “˜unit” in the first embodiment. Alternatively, the computer executes the procedure and method of “˜unit” in the first embodiment.

  As described above, the parallel tracking processing device 1 shown in the first embodiment includes a CPU as a processing device, a memory as a storage device, a magnetic disk, a keyboard as an input device, a mouse, a communication board, etc., a display device as an output device, and a communication board. As described above, the function indicated as “to part” is realized by using these processing device, storage device, input device, and output device.

It is a figure for demonstrating the parallel tracking processing apparatus by Embodiment 1 of this invention. It is a figure for demonstrating the MHT process part by Embodiment 1 of this invention. It is a figure for demonstrating the unnecessary signal part likelihood matrix and new wake part likelihood matrix by Embodiment 1 of this invention. It is a figure for demonstrating the existing wake part likelihood matrix and likelihood matrix by Embodiment 1 of this invention. It is a figure for demonstrating the correlation matrix by Embodiment 1 of this invention. It is a figure for demonstrating the wake management part by Embodiment 1 of this invention. It is a figure for demonstrating the gate inside / outside determination matrix by Embodiment 1 of this invention. It is a figure for demonstrating the operation | movement procedure of the parallel tracking processing apparatus by Embodiment 1 of this invention. It is a figure for demonstrating the operation | movement procedure of the conventional MHT process. It is a figure for demonstrating the hardware structural example of the parallel tracking processing apparatus by Embodiment 1 of this invention.

Explanation of symbols

  DESCRIPTION OF SYMBOLS 1 Parallel tracking processing apparatus, 2 sensors, 3 External apparatus, 4 MHT processing part, 5 Track management part, 6 Detection data reception part, 7 Detection data pack generation part, 8 Likelihood matrix generation preparation part, 9 Likelihood matrix generation part 10 n-Best solution search unit, 11 hypothesis generation unit, 12 semi-optimization unit, 13 track establishment unit, 14 track arrangement unit, 15 track distribution unit, 16 track information generation unit, 17 track information transmission unit, 18 hypothesis DB , 19 Proxy track DB, 20 communication unit (MHT processing unit 4 side), 21 track prediction unit, 22 track correlation unit, 23 track update / generation unit, 24 track selection unit, 25 track integration unit, 26 transmission target track setting unit 27 Track transfer unit, 28 Track DB update unit, 29 Track information generation unit to be transmitted, 30 Track DB, 31 Communication unit (track management unit 5 side).

Claims (9)

A tracking processing device for tracking a target,
A multi-target tracking algorithm processing unit for performing a multi-target tracking algorithm by performing an n-Best solution search process for a hypothesis that is a combination of wakes representing a motion specification of a target;
While the multi-target tracking algorithm processing unit is performing the n-Best solution search process, the parent track that is an existing track is updated to generate a child track, and a new track that is independent from the parent track And a track management unit for generating a track as a new track. The wake management unit
From the target tracking algorithm processing unit, search process result data indicating the result of the n-Best solution search process is input,
The tracking processing apparatus according to claim 1, wherein either one of the generated child tracks and the new track is selected based on the content of the input search processing result data. The multi-target tracking algorithm processing unit
Of the processes included in the multi-target tracking algorithm, at least a hypothesis generation process for generating a child hypothesis by updating an existing hypothesis based on the result of the n-Best solution search process, and a child generated by the hypothesis generation process The tracking processing apparatus according to claim 1, wherein the semi-optimization process for integrating hypotheses is performed without a tracking filter process for estimating a true value of a motion specification of a target. The tracking processing device includes:
Connected to multiple sensors that detect the target,
The multi-target tracking algorithm processing unit
From the plurality of sensors, input detection data indicating a detection result in each sensor,
4. The tracking process according to claim 3, wherein at least the hypothesis generation process and the semi-optimization process are performed without the tracking filter process, using the input detection data as a proxy wake representing a wake. apparatus. The tracking processing device includes:
Connected to multiple sensors that detect the target,
As the wake management unit, it has a plurality of wake management units that manage different parent wakes,
The multi-target tracking algorithm processing unit
Detection data indicating detection results in each sensor is input from the plurality of sensors, and detection is performed by collecting two or more detection data for the same detection time obtained from the same sensor among the plurality of input detection data. As a data pack, output a detection data pack to each of the plurality of track management units,
Each track management department
The detection data pack output from the multi-target tracking algorithm processing unit is input, and based on the detection data included in the detection data pack, the managed parent wake is updated to generate a child wake, and the detection data pack The tracking processing device according to claim 1, wherein a new track is generated using the detection data included in the tracking data. Each track management department
From the target tracking algorithm processing unit, search process result data indicating the result of the n-Best solution search process is input,
Based on the contents of the input search processing result data, select either wake from the generated child wake and new wake,
The multi-target tracking algorithm processing unit
Decide to transfer the wake selected by one of the wake management units to the other wake management unit, input the wake of the transfer target from the wake management unit of the transfer source, and input the transferred wake of the transfer target The tracking processing apparatus according to claim 5, wherein the tracking processing apparatus outputs to a wake management unit. Each track management department
From the multi-target tracking algorithm processing unit, search process result data indicating the result of the n-Best solution search process is input,
Based on the contents of the input search processing result data, select either wake from the generated child wake and new wake,
The multi-target tracking algorithm processing unit
Decide to transfer the wake selected by one of the wake management units to another wake management unit, and notify the transfer source wake management unit of the transfer destination wake management unit and the transfer target wake. Output,
Each track management department
The wake of the transfer object is output to the wake management unit of the transfer destination notified in the transfer notification when the transfer notification is input from the multi-target tracking algorithm processing unit. The tracking processing device described. The multi-target tracking algorithm processing unit
The tracking processing apparatus according to claim 1, wherein an MHT (Multiple Hyperthesis Tracking) algorithm is implemented as the multi-target tracking algorithm. To the computer that tracks the target,
A multi-target tracking algorithm processing procedure for performing a multi-target tracking algorithm by performing an n-Best solution search process for a hypothesis that is a combination of wakes representing a motion specification of a target;
While the n-Best solution search process is being performed, the parent track that is an existing track is updated to generate a child track, and a new track that is independent from the parent track is generated as a new track A program characterized by causing management procedures to be executed.

Images