Linear trace similarity matching based on improved longest common substring

1 Introduction

During the “Thirteenth Five-Year Plan”, China’s high-speed rail operating mileage will reach 30,000 kilometers which can cover more than 80% of large cities and will continue to renovate and complete current airport building, as well as build 74 civil aviation airports and 850 general airports. There are many optical cables, leaky cables, signal cables, cables for rail transit vehicles and links up grounding wire along the railway. In the meanwhile, there are many navigation lights cables and communication optical cables around various airports. Since the inner conductors of various types of cables are mostly copper which has high value, it has gradually become the object of criminals. In recent years, frequent wire-cutting crimes against high-speed rail and airports have caused huge losses of tens of millions of dollars, and frequently interrupt power supply, signal and communication equipment power supply, which potentially cause more serious accidents [1].

Statistics show that these criminals used clamping and cutting tools including bolt cutters, cable cutters and other pliers to destroy the cables which left toolmarks in the crime scene [2]. The linear trace indicates the toolmark morphology of clamping and cutting tool, which is not easy to be destroyed, has a high occurrence rate and high significant on identification. It is of great significance for prosecutor to determine the nature of the case and determine the tools used in the crime so as to find the criminals [3].

Image recognition and three-dimensional scanning techniques have emerged in recent years which provide some new solutions for non-destructive quantitative testing of linear traces compared with traditional methods such as microscopy and manual features [4–6].

Although these methods can automatically match the linear traces to some extent, there are still a few existing problems [7, 8]:

Comparison method based on the image has high requirements for the camera device. Inconsistency reflection, the shooting angle and the focus will directly lead to the distortion of the original data, which may weaken the robustness of the analysis result;

This paper proposes a method in which the single-point laser picks up the toolmark detection signal, and the longest common substring is obtained after noise reduction. In addition, the improved dynamic programming algorithm calculates and generates matching results in order to solve the existing problems in traditional methods. The state matrix generated by the dynamic programming method contains multiple matching results which output the basic longest substring. In addition, all the candidate results can be obtained according to different minimum matching lengths to improve the result when only one calculation is carried out.

2 Longest common substring

Longest Common Substring (LC-Substring) is an algorithm for describing the similarity between two substrings. For a given sample sequence S and a sequence T to be matched, the L -Substring correlation algorithm is used to find the longest common substring between S and T. The longest common substring refers to the longest common part of the sequence S and T that. The longest common substring LC-Substring algorithm is mainly applied to find the exact overlap between sequences.

The algorithms implementing LC-Substring mainly include two types, brute force method and dynamic programming method. The basis of the two types are as follows:

(1) Brute force method

The brute force method is solved by a simple search solution. The brute force method checks whether each substring of S is a substring of T, thereby determining whether it is a common substring of S and T, and selecting the longest common substring. The longest common substrings of S and T can be found after all substrings of S and T have been examined. When the brute force method is used to solve the problem in which S is a string of length n and T is a string of length m, the time complexity is O (2^m+n), and the space complexity is O (n).

The brute force method has the advantages of simple implementation and small space occupation, so it is suitable for problems with small string length which only needs to provide the longest common substring. If the problem needs more outputs, the brute force rule has its limitations.

(2) Dynamic programming design method

The dynamic programming design method is developed for solving the optimization problem, rather than a special algorithm. The constraints and conditions are different for different optimization problems because of the different nature, so the design method of dynamic programming has different problem-solving methods for different problems.

The main idea of dynamic programming is to establish a n * m two-dimensional matrix A according to the length of S and T in the LC-Substring problem. The element of the matrix A (i, j) indicates the matching information at the i position of the S string and the j position of the T string: either matching or not matching or already a continuous match.

LC-Substring dynamic programming transfer equation: A ( i , j ) = { 0 , i = 0 or j = 0 or S ( i ) ≠ T ( j ) A ( i - 1 , j - 1 ) + 1 , S ( i ) = T ( j )(1)

The equation mainly focuses on the local optimal matching data of the current position. The algorithm is suitable for the pattern under strict matching. The LC-Substring has a few applications on:

Finding the match between two trace signals using the dynamic programming method.

The first step is to calculate the matching state of the sequence S and the sequence T by using the motion detection method to perform the similarity matching process. The space and time and complexity in this step are both o (m * n). So when the signal data volume is too large, it will be moderately scaled down and will not have a big impact on the result because the overall signal-to-noise ratio is improved, thereby offsetting the effect of a certain decrease in resolution when the original signal detection signal is improved in the process of zooming down.

The dynamic programming method used in the matching calculation is consistent with the dynamic planning steps of the LC-Substring in the execution steps and the calculation is in the order of rows or columns. And the main improvement of the algorithm is the decision rules of the state transition which uses the method of “local minimum difference”. The basic flow of matching calculations is shown in Fig. 1:

OPEN IN VIEWER

Fig. 1

Matching calculations basic flow.

3.3 Generate results

The position of an optimal solution is recorded in the dynamic programming calculation in the traditional longest common subsequence algorithm. The longest common sequence can be obtained by backtracking and traversing afterward. The state matrix saves the local optimal matching result at any position which can be traced back to obtain the longest result, or the Nth long result. The trace signal cannot be used in strict matching compared with the original numeric string of the LCS application, hence the matching is relatively unstable. It is important to obtain matching results of any positions/lengths in addition to the longest match result required in the trace matching.

Results generation includes the following steps:

Match Filtering: Filter out all possible matching information based on specified criteria.

Results analysis: The results are analyzed including matching results correction, connection or topological sorting based on the generated matching information,

The workflow diagram is shown in Fig. 2:

OPEN IN VIEWER

Fig. 2

Orkflow diagram for result generation.

The output of the Nth long partial matching is usually used for the fast matching process. The Nth long result obtained by the algorithm is accurate and continuous in general. The approximated (most strict) longest common part of the two traces can be achieved under such circumstances. The implementation steps are as follows:

The searching procedure for the Nth largest value position (i, j) is based on the size of the matrix len. The Nth largest value position in the matrix len represents the Nth longest match because the len matrix stores the longest continuous matching size of S and T at the corresponding position.

Firstly, the end position is marked (i, j). And the i position of the S string and the j position of the T string are the matched end positions. Then go to step 3.

It outputs and moves according to the state of Way(x, y) each time when it goes back to the position to find (x, y), { end , Way ( x , y ) = 0 x = x - 1 ; y = y - 1 , Way ( x , y ) = 1 y = y - 1 , Way ( x , y ) = 2 x = x - 1 , Way ( x , y ) = 3 ,

Step 3 will go through Way (x, y) =1 states len (i, j) -1 times and outputs a corresponding sequence of S and T each time, which is compatible with all modes in the comparison algorithm.

The coordinate position at the end of step 3 is marked as the start position. The previous end position and the current start position are returned as well as outputting the sequence corresponding to S and T, which is the longest common sequence of the two sequences.

4.1 Simulation testing

A total of 8 samples, of which data0 is a sample, data1∼100 is overlapped with data0 at different positions, and the overlap percentage is around 30%. The tolerance used in the test is 1, and the test results are as shown in Fig. 3:

OPEN IN VIEWER

Fig. 3

Simulation data matching testing.

4.2 The actual testing

It is difficult to determine the overlap by naked eyes when different cuts of the actual cuts are under testing. The corresponding positions are very different as well. The actual test is performed by the algorithm, and the test tolerance is 4, which is divided into 100 groups. The 100 groups are all repeated tests of the same sample, and the maximum overlap percentage of each group is 30% or 60%. The matching result is shown in Figures 4 and 5, and the matching accuracy is 85%.

OPEN IN VIEWER

Fig. 4

60% overlap actual testing data matching test.

OPEN IN VIEWER

Fig. 5

30% overlap actual testing data matching test.

The test continues with increasing the difficulty of continuous cut. The different cut ends of the actual cut with large randomness and change. The overlapping percentage is 30% ∼60% while other conditions are remaining the same. The matching result is shown in Figure 6 in which the matching accuracy is 80%.

OPEN IN VIEWER

Fig. 6

45% overlap actual testing data matching test.

This paper proposes a similarity matching algorithm for linear traces. The algorithm uses a single-point laser to pick up trace detection signals. The LC-Substring and improved dynamic programming algorithms are used for matching calculation and result generation after noise reduction. The complexity of the algorithm is low which can be directly programmed in Python. The executable can run on a computer with medium configuration. The toolmark detection experts from the Institute of Forensic Science Ministry conducted actual tests and optical comparison to prove that the algorithm can be effectively applied to detect the traceability of the clamping and cutting tool based on the linear trace comparison. It provides a reliable reference for the subsequent identification work. Future works need to improve the computational performance of a large amount of data, complete the cross-regional parallel comparison and traceability source to be able to handle actual case handling environment.