Editor’s note: In this issue, data recovery experts from SalvationDATA will introduce a vital process of video retrieval, target tracking. Target tracking is a technique that can help connect the messy dots coming from different frames and then form a motion track of certain targets. Once the track is ready, investigators will be able to know clearly about the whereabouts of targets of interest, thus saving much trouble of manual inspection.
1 Background
Target tracking nowadays is very popular in such fields as military, visual navigation, intelligent robot, intelligent transportation, public security etc.. Take a few cases for example, vehicle tracking is indispensable for photographing system of traffic violation detection; motion tracking is vital for detection of human, animal or vehicle intrusion; plus, motion tracking is also a very vital sub-branch of computer vision technology.
Figure 1
2 Tracking Procedure
Target tracking requires that target of interest, either it is human or object, should be found first in every frame of a continuous video sequence. However, most target tracking follows the steps shown below:
2.1 Accurate Target Description
For target tracking to be possible, accurate description of certain targets is essential, which indicates that features extracted from the target must be accurate. A rule of thumb would be to describe the target by its shape, pattern, moment feature, transformation coefficient etc..
2.2 Similarity Calculation
Commonly used methods for similarity calculation include Euclidean distance, Mahalanobis distance, Chessboard distance, Weighted distance, Similarity coefficient, Correlation index etc..
2.3 Search & Match of Target Zone
It would be too time-consuming and too much burden on a computing system if we are to conduct similarity calculation of every object in a scene. Hence, a target zone, usually, will be determined first in order to improve efficiency. Commonly used methods used for finding a target zone include Kalman Filtering, Particle Filter, Mean Shite etc..
3 Tracking Algorithm
Retrieval speed matters for efficient video retrieval. So, a good tracking algorithm should be simple and efficient.
Figure 2
As shown in Figure 2, the job of target tracking is to discern if the 2 marked objects are the same.
To find out, an accurate description of the 1st object needs to be obtained first. Then, get an accurate description of the 2nd object. When the descriptions of the above 2 are available, conduct similarity calculation, the 2 objects are considered the same if the value is above the threshold value, say 0.75.
The situation is much more complicated in real cases than what’s shown here. In real cases, it is quite common that investigators have to compare several objects simultaneously. And investigators also have to handle such cases as merging or separating of targets.
4 Efficient Target Tracking
Every step of target tracking needs to be optimized if investigators are to conduct efficient target tracking.
4.1 Target Description
Clearly, algorithms(shape & pattern comparison etc.) that take too much time and calculation need to be abandoned first.
After rounds of comparison, it is found that Color histogram comes at the top since it doesn’t require much calculation. Unlike the other methods mentioned above, Color Histogram calculates the ratio of each color in a whole scene, but not its spatial position. But it is possible that two objects are deemed the same if they have the same ratio of a certain color, so histogram after the 2 scenes are split into several different blocks respectively, is needed for confirmation. Then, it can be concluded that the 2 objects are the same if each block of the 2 scenes has a similar histogram.
4.2 Similarity Calculation
What introduced above is how we can determine if 2 objects are similar. But, as mentioned earlier, the process is much more complicated in real cases. In real cases, such scenarios as merging and separating of objects often occur. And this couldn’t be done by simply repeating methods mentioned above.
Figure 3
As shown in Figure 3, the 2 objects in video frame one switched their positions in video frame 2. But the histogram shows that the similarity value is still 0.5, which is definitely not accurate. So, other methods are needed for second confirmation.
Distance: the objects in the 2 video frames are considered to be of high similarity if the distance value is small. Distance and similarity are in inverse proportion(1-migration distance/diagonal length of the video frame )in a Euclidean distance, we can get the result by calculating the logarithmic value of its member and denominator.
Length-width ratio: It is possible that extra parameter like length-width ratio is needed for further confirmation if we cannot get an accurate result with distance.
Orientation: orientation parameter is needed if the 2 extra parameters are not enough for an accurate result.
4.3 Search & Match of Target Zone
As shown in Figure 3, when the 2 objects in video frame 1 both match those 2 in video frame 2, then the object 1 in video frame 2 is the combination of the 2 objects in video frame 1. The 2 objects in video frame 2 should be marked separately if we were to track these 2 objects in video frame 1. And that requires area searching and matching, which is viable with a commonly used method or self-defined algorithm.
5 Tracking Result
The tracked objects will be marked with frames, and its motion track can be obtained through connecting them in all video frames. Then suspected objects can be singled out with various filters like orientation, trip thread etc integrated into DVR forensics software.
Conclusion:
In this issue, data experts from SalvationDATA explained the definition, procedure, algorithm, and result of target tracking. Apart from that, they also underlined the importance of optimization of each step in order to improve video retrieval efficiency. The technique introduced here in this issue has already been integrated into our DVR forensics solution VIP, which is having summer giveaway promotion now, contact us for more information!
SalvationDATA Blog 