An Improved Algorithm of Congruent Matching Cells (CMC) Method for Firearm Evidence Identifications.
In forensic investigations involving firearms, toolmarks on bullets and cartridge cases fired from a firearm are important clues and evidence. Comparisons of these toolmarks have more than a hundred years of history through the use of manual comparison microscopes . In recent years, automated identification technologies and systems have been developed [2, 3]. For correlations of the cartridge case, most identification systems correlate the whole region without taking into account the fact that not all regions on the primer are well-marked by the impression of the breech face of the gun slide during firing. Some regions of the primer that make poor contact with the breech face may generate "invalid" areas of poor correlation which may affect the capability of identification. In 2012, the Congruent Matching Cells (CMC) method was invented at the National Institute of Standards and Technology (NIST) to provide objective and high-accuracy ballistics identification and evidence searches . The CMC method divides the measured image into small correlation cells so that "invalid" areas can be isolated from "valid" areas that contain unique identifying marks in order to improve correlation accuracy. The method uses four identification parameters to determine the number of valid congruent matching cell pairs (CMC) contained in a pair of images. A numerical identification criterion, C = 6, was suggested as a criterion for identifying images of matching cartridge cases which are fired from the same firearm . Pairs of images with CMC greater than 6 are identified as matches, and pairs of images with CMC less than 6 are concluded to be nonmatches.
The CMC method was initially tested using both three-dimensional (3D) topography images and optical grayscale intensity images of primers from a set of 40 test fires from 10 consecutively manufactured pistol slides. These measurements allowed for 780 pairwise correlations for both the 3D topography images and optical images. The test results showed that all image pairs are correctly identified without any false identification (false positive) or false exclusion (false negative) [5, 6]. However, the separation between the known-matching (KM) and known-non-matching (KNM) distributions of the number of CMCs for the optical images pair is not significant  (see also Fig. 8a). In order to increase the correlation accuracy, this paper examines the processing of the CMC method. An improved algorithm is proposed that takes advantage of the cell correlations at a common initial phase angle and includes a forward and backward correlations strategy (i.e. A vs. B and B vs. A) to significantly improve the capability of identification. The improved algorithm is tested using both 3D topography images and optical images captured from breech face impressions from the same set of 40 cartridge cases.
2. Congruent Matching Cells (CMC) Method
2.1. Basic Concepts
Depending on the contact conditions with the gun parts, the surfaces of the bullets and cartridge cases fired from a firearm include both "valid" and "invalid" correlation regions . A valid correlation region contains "individual characteristics"  of the ballistics signature that can be used effectively for identification. An invalid correlation region does not contain individual characteristics of the firearm's ballistics signature and should be eliminated from identification. If the correlation is performed on the whole region of two correlated images, a quantitative measure of correlation may be relatively low, because large invalid correlation areas may be involved in the correlation. If instead, the correlation region is divided into cells for correlation, the valid correlation cells can be identified and the invalid correlation cells can be eliminated from correlations. This procedure can enhance the quantitative measure of correlation .
When images A and B originating from a pair of cartridge cases fired from the same firearm are compared, the cell pairs located in their common valid correlation area can be characterized by four identification parameters:
1) High correlation values quantified by the cross correlation function maximum, CC[F.sub.max] ;
2) Similar registration angles [theta];
3) Similar x-y spatial distribution.
Four corresponding "thresholds" are used to identify the Congruent Matching Cells: [T.sub.CCF], [T.sub.[theta]], [T.sub.x], and [T.sub.y]. If the registered cell pairs come from valid correlation areas of A and B originating from the same firearm, their correlation value CC[F.sub.max] should exceed [T.sub.CCF], and their deviations in rotation angle 8 and lateral translation x and y at the matched position should all fall within ranges given respectively by [T.sub.[theta]], [T.sub.x], and [T.sub.y], then those cell pairs are regarded as a congruent, matching set of cell pairs. Inspired by the numerical identification criterion of the Consecutively Matching Striae (CMS) method proposed by Biasotti and Murdock for identification of bullet striation signatures , the numerical identification criterion for the CMC method is suggested as C = 6 , i.e. When the CMC number is equal to or greater than 6, images A and B are concluded to be a match.
2.2. Original Algorithm of CMC Method
In the original algorithm of the CMC method, the images are divided into a cell array. For a pair of compared images A and B, after eliminating void cells that contain zero or very few data points, each cell in the reference image A scans the correlated image B at each of its rotational positions. Then the [theta], x, and y parameters of each cell are registered at the position of the maximum correlation value, CC[F.sub.max] (see Fig. 1 which shows only a simplified 4 x 4 cells array), and are compared with the thresholds of [T.sub.CCF], [T.sub.[theta]], [T.sub.x], and [T.sub.y] to determine whether or not they are Congruent Matching Cells (CMC) . To reduce the computation time, the median values of [theta], x, and y are selected as virtual references for identification of the correlated cell pairs .
3. Improved Algorithm of CMC Method
As stated before, if two compared images originate from the same firearm, the cell pairs located in their common valid correlation area must have similar registration angles 6, which are close to the initial phase angle &0, where the two correlated images can be correctly matched . In the beginning of the correlation, however, the initial phase angle is uncertain as the correlation is not performed and the orientation of cartridge case setup is unknown when images are captured. As a result, in the previous optical image validation tests, each cell in the reference image A must scan the correlated image B at each of its rotated positions and be registered only at the CC[F.sub.max] position  without taking account of the initial phase angle. Ideally, for the pairwise cell correlations of matching image pairs, the maximum correlation value CC[F.sub.max] should always be located at the angular position around the initial phase angle [[THETA].sub.0]; and the CCF values obtained at other rotation angles should be smaller and should be ignored . However, after extensive case studies, instances can be observed where some cell pairs from matching images are registered at an angle other than [[THETA].sub.0], leading to an incorrect correlation conclusion. This is most common when the CCF distribution patterns of the matching and non-matching cell correlations show large overlapping regions .
As an example, Table 1 shows the correlation results represented by the values of CC[F.sub.max], [theta] and x, y of a KM pair of optical images. The nominal cell number is 49 (a 7 x 7 array of cells); after eliminating void cells, the effective cell number is N = 30; the rotation range is [+ or - ]30[degrees] with 3[degrees] increments. The missing indexes in Table 1 and 2 represent the void cells . Each row in the tables represents a pairwise cell correlation. Each row marked in red represents a CMC. For the 12 CMCs shown in Table 1, their registration angles [theta] are distributed from 12[degrees] to 18[degrees] with the thresholds set as [T.sub.CCF] = 25%, [T.sub.[theta]] = [+ or -] 3[degrees] and [T.sub.x] = [T.sub.y] = [+ or -]25 pixel with 5.06 [micro]m pixel spacing . The initial phase angle for this image pair taken as a whole is estimated to be [[THETA].sub.0] = 15[degrees]. The other 18 pairwise cells are not congruent matching cells, since the rotation angle associated with their maximum CCF value did not fall within the threshold range of the registration phase angle from 12[degrees] to 18[degrees].
However, due to the fact that CCF distribution patterns of matching and non- matching cell correlations show large overlapping regions , some of the valid cell pairs may be mistakenly excluded from the CMC count because by chance their correlation yields a higher CCF value at a rotation angle outside the threshold range [T.sub.[theta]] = [+ or -]3[degrees] than the CCF value found within the range. In order to avoid the elimination of these valid cell pairs, we use the initial phase angle [[THETA].sub.0] = 15[degrees] as a fixed registration angle. With the fixed registration angle, the CMC number will be determined only by three parameters (CC[F.sub.max], x, and y). As the blue rows in Table 2 indicate, the CMC number increases from 12 to 15. It can be seen that the CCF values of the additional CMCs are just a little lower than the CCF values of the corresponding cells in Table 1. In addition, (two cells are considered as CMCs in Table 1, but not in Table 2. These cells will be included in the refined analysis discussed below. Based on these correlation results, a new algorithm using CMCs located at the initial phase angle, instead of the original algorithm using CMCs located in the full angular registration range, is proposed to improve correlation accuracy. The key question is how the initial phase angle [[THETA].sub.0] is determined.
Figure 2a shows the CMC-[theta] distribution for the above KM image pair at each registration angle 6 between +30[degrees] and -30[degrees] with 3[degrees] increments. It shows a distribution which exhibits a single peak concentrated at 12[degrees]. If two images are truly matching, the CMC-[theta] distribution of matching image pairs should have a prominent peak located near the initial phase angle &0, while non- matching image pairs may have a relatively flat and random CMC-[theta] distribution pattern (Fig. 3 a).
An additional criterion is now introduced to distinguish the matching from the non-matching distributions, such as those shown in Figs. 2 and 3. It can be seen that for the CMC-[theta] distribution of the KM correlation (Fig. 2a), the second highest CMC number is close to the maximum CMC number relative to its phase angle. While for the KNM correlation (Fig. 3a), the second highest CMC number could appear anywhere in the angle range. Thus, the first step for the improved algorithm is using an additional "high CMC number" along with the "maximum CMC number" to determine the angular position of the initial phase. If we define the "high CMC number" as (CM[C.sub.max] - [tau]), where t is an empirical constant (in this paper, we specify t =1), and let the angular range of the "high CMCs" be the maximum angular interval with the corresponding CMC number is greater than or equal to the "high CMC number", then the angular range of "high CMCs" in Fig. 2a is only the histogram bar centered around 12[degrees]. Therefore, the initial phase angle can be considered as 12[degrees]. However, for the KNM case as shown in Fig. 3a, the "high CMC number" is (CM[C.sub.max] - 1 = 5), and the corresponding angular range of the "high CMCs" extends from -15[degrees] to - 3[degrees]. The wide distribution range between the angles of the maximum and the high CMC number suggests that the KNM image pairs have no common initial phase angle for their angular registration.
The CMCs in the KM image pairs result primarily from the individual characteristics which represent the similarity of their ballistics signatures. On the other hand, the CMCs in the KNM image pairs usually result from random factors, mainly because KNM surfaces are not expected to be correlated at all. For example, Fig. 4 shows a typical CCF map of a known congruent matching cell of a correlated KM image scanned by the corresponding correlation cell of the pairwise matched reference image. It can be seen that there is only one CCF peak above the threshold [T.sub.CCF] = 25 %, indicated by the arrow. Figure 5 shows a typical CCF map for a KNM situation, a single cell of one image correlated with a cell of a non-matching reference image. It can be seen that there are at least three peaks with similar CCF values above the threshold. This example suggests that the CCF peak in the KM images is relatively systematic and stable. Its position and CCF value do not significantly change with the change of correlation conditions (cell size, cell incision angle, cell shift direction, etc.). Conversely, the CCF peaks in the KNM images are randomly oriented and are not stable. These KNM peak positions and CCF values may significantly change with correlation conditions, which may help distinguish the non-matching correlations.
Based on the above observation that the KM distributions are less sensitive to correlation conditions than KNM distributions, the second proposed step is to combine the forward and backward correlations (i.e., A vs. B and B vs. A, see Fig. 6) and utilize the different features of CMC-[theta] distributions in KM and KNM images to detect and exclude random CMC peaks for non-matching correlations from the CMC-[theta] distributions. Figures 2b and 3b show the CMC-[theta] distributions of the backward correlations of the KM and KNM. The forward correlations are shown in Fig. 2a and Fig. 3 a. It can be seen that the forward and backward CMC-[theta] distributions of the KM correlation are very similar. On the contrary, the CMC-[theta] distributions in the two KNM figures are significantly different because there is no common initial phase angle for the KNM image pairs. This suggests a method for improving the CMC algorithm by combining the angular ranges between the lines of high CMCs found for the forward and backward CMC-[theta] distributions. For example, in the KM correlation (Fig. 2), the angular range of the "high CMCs" for both the forward and backward distributions is from 12[degrees] to 15[degrees] which is close to that of the forward correlations 12[degrees]. However, for the KNM correlation in Fig. 3, the angular range of the "high CMCs" for the forward and backward distributions is expanded from (-15[degrees] to -3[degrees], forward) to (-24[degrees] to 21[degrees], backward). The wide distribution range suggests that there is not a common initial phase angle between these two KNM image pairs.
The optical images and 3D topography images from the same set of 40 cartridge cases discussed in references [5, 6] are tested using the improved algorithm of the CMC method. Each set includes 63 KM and the 717 KNM image pairs for a total of 780 correlations. The first set includes 40 optical images captured using a microscope with a ring light; the second set of images includes 40 topography images captured using a confocal microscope.
Each set of images is processed using the following procedure:
1) Conduct both forward and backward correlations at each rotation and record the registration based on CC[F.sub.max], x, and y for each cell at each rotation. These data will be used in the next two steps separately.
2) At every rotation angle, each cell in the reference image finds a registration position in the compared image with a maximum CCF value. By selecting the registration with the maximum CCF value for each cell, the two CMC numbers determined by the four thresholds can be obtained based on the original algorithm . The lower CMC number is used as the initial result. An example of the results is shown in Tablet.
3) Build CMC-[theta] distributions using the data generated in step 1, by counting the number of cells that have congruent positions at each individual rotation angle. Calculate the angular range of "high CMCs" using both the forward and backward CMC-[theta] distributions, as illustrated in Figs. 2 and 3.
4) If the angular range of the "high CMCs" is within the range T0, identify the CMCs for each rotation angle in this range and combine them to give the number of CMCs for this comparison in place of the original CMC number. In this step, if the range is narrower than T0, the nearby angles are included to make the range equal to T0; CMCs with same index in each rotation are only counted once.
5) If the angular range of the "High CMCs" is larger than the range T0, keep the CMC value obtained from step 2 as the final CMC for this comparison.
Table 3 and Fig. 7 show the final CMCs of the image pair used in section 3. Nine additional CMCs marked in blue are identified by the improved algorithm. Figures 8 and 9 show the results obtained from the original and improved algorithm. For the optical image set, the minimum CMC number of the KM correlations increases from 6 to 11. All of the 780 image correlations are identified correctly as matching or non-matching by the criterion C = 6 used in the improved algorithm. Similarly, for the topography image set, the minimum CMC number of the KM correlations increases from 8 to 12. In all of these results, the CMC values for KNM image correlations are consistently low in number. In summary, these experiments demonstrate that the improved algorithm can enhance the identification capability of the CMC method for both optical intensity and topographical breech face representations.
5. Discussion and Conclusion
The improved algorithm of the CMC method keeps account of the CC[F.sub.max] values of cell correlation at each registration angle, rather than only the CC[F.sub.max] value at a single registration angle, which may fall outside the accepted range of T0. By using these additional values, the revised algorithm builds the CMC-[theta] distribution which represents the important features of the matching image pair and the non-matching image pair. For the matching image pair, correlation positions of cells are highly concentrated around a particular initial phase angle, mostly caused by the similarity of the individual characteristics of the KM image pairs. For the non-matching image pairs, the distribution of the correlation values seems random, irregular, and relatively flat. As the experimental results show, the improved algorithm of the CMC method can identify the matching cells with lower CCF values which may be otherwise ignored by the original algorithm, and therefore improves the capability of the CMC method to distinguish matching images from non-matching images.
In our future work, we will test different sample sets to test and optimize the stability and capability of the improved CMC method further.
The funding for this work is provided by NIST's Forensic Measurement Challenge Project (FMC2012). The authors are grateful to T. Fadul of the Miami-Dade Crime Lab. for providing test samples and to X. Zheng of NIST for providing the topographic images.
 J. E. Hamby and J. W. Thorpe, The History of Firearm and Toolmark Identification, AFTE Journal 31 (3), 266-284 (1999).
 R. Nennstiel and J. Rahm, An Experience Report Regarding the Performance of the IBIS[TM] Correlator, J. Forensic Sci. 51 (1), 24-30 (2006). http://dx.doi.org/10.1111/j.1556-4029.2005.00003.x
 P. Thumwarin, C. Prasit, and T. Matsuura, Firearm Identification Based on Rotation Invariant Feature of Cartridge Case, SICE Annual Conference 2008, 45-49 (2008).
 J. Song, Proposed NIST Ballistics Identification System (NBIS) Using 3D Topography Measurements on Correlation Cells, AFTE Journal 45 (2), 184-194 (2013).
 W. Chu, M. Tong, and J. Song, Validation Tests for the Congruent Matching Cells (CMC) Method Using Cartridge Cases Fired with Consecutively Manufactured Pistol Slides, AFTE Journal 45 (4), 361-366 (2013).
 M. Tong, J. Song, W. Chu, and R. M. Thompson, Fired Cartridge Case Identification Using Optical Images and Congruent Matching Cells (CMC) Method, J. Res. Natl. Inst. Stand. Technol. 119, 575-582 (2014). http://dx.doi.org/10.6028/jres.119.023
 AFTE Criteria for Identification Committee, The Theory of Identification, Range of Striae Comparison Reports and Modified Glossary Definitions - An AFTE Criteria for Identification Committee Report, AFTE Journal 24 (3), 336-340 (1992).
 J. Song and T. V. Vorburger, Proposed Bullet Signature Comparisons Using Autocorrelation Functions, Proc. 2000 NCSL, NCSL--International, Toronto, July 2000.
 A. Biasotti and J. Murdock, Firearms and Toolmark Identification: Legal Issues and Scientific Status in D. Faigman, D. Kaye, M. Saks, and J. Sanders, eds., Modern Scientific Evidence: The Law and Science of Expert Testimony, West Publishing Co., St. Paul, 124-151 (1997).
Mingsi Tong and Wei Chu are guest researchers of the Surface & Nanostructure Metrology Group of the Semiconductor and Dimensional Metrology Division (SDMD) of the Physical Measurement Laboratory(PML) at NIST. John Song is a project leader of the Surface & Nanostructure Metrology Group of SDMD of PML at NIST. The National Institute of Standards and Technology is an agency of the U.S. Department of Commerce.
Mingsi Tong (1,2), John Song (2), and Wei Chu (2)
(1) School of Mechatronics Engineering, Harbin Institute of Technology, Harbin 150001, China
(2) National Institute of Standards and Technology, Gaithersburg, MD 20899 USA
Caption: Fig. 1. Correlation scheme using the fast CMC method: [A.sub.2] and [B.sub.2] represent the matched cell pair. During the correlation process, cell [A.sub.2] only scans the red dotted window in each rotated position of the correlated image B .
Caption: Fig. 2. CMC-[theta] distribution of a typical correlation for a pair of KM optical images. Red lines indicate the angular range of "high CMCs".
Caption: Fig. 3. CMC-[theta] distribution of a typical correlation for a pair of KNM optical images. Red lines indicate the angular range of "high CMCs".
Caption: Fig. 4. A typical CCF map on a known congruent matching cell of correlated KM optical image scanned by the corresponding correlation cell of the pairwise matched reference image.
Caption: Fig. 5. A typical CCF map on a cell of correlated KNM optical image scanned by a correlation cell of a non- matched reference image.
Caption: Fig. 6. Depiction of the forward and backward correlations. For both directions a cell-size area in one image is scanned over a larger region of interest in the other image.
Caption: Fig. 7. Shows the KM image pair. Red cells represent CMCs identified by the original algorithm; blue cells represent additional CMCs identified using the improved algorithm.
Caption: Fig. 8. CMC distribution of the optical image set.
Caption: Fig. 9. CMC distribution of the topography image set.
Table 1. A typical correlation for a pair of KM optical images (Angular registration from -30[degrees] to 30[degrees]). Cell index CC[F.sub.max] [theta] [x y] (pixel) (Col., Row) (degree) (C1, R2) 0.34707 -30 [3,-2] (C1, R3) 0.29071 12 [18,-7] (C1, R4) 0.30964 -12 [19,-24] (C1, R5) 0.26825 -30 [30,15] (C1, R6) 0.41703 12 [1,0] (C2, R1) 0.38082 -3 [-7,6] (C2, R2) 0.44403 15 [9,6] (C2, R7) 0.44394 18 [-117,88] (C3, R1) 0.33065 15 [6,1] (C3, R2) 0.30452 -9 [-25,-27] (C3, R7) 0.56988 15 [23,1] (C4, R1) 0.38804 15 [4,0] (C4, R2) 0.44964 24 [26,9] (C4, R7) 0.35934 15 [24,-3] (C5, R1) 0.36111 12 [19,1] (C5, R2) 0.35324 12 [-98,-130] (C5, R6) 0.50059 12 [8,4] (C5, R7) 0.29452 -15 [-98,-130] (C6, R1) 0.43035 9 [25,14] (C6, R2) 0.44577 18 [-3,-14] (C6, R3) 0.32158 0 [27,-124] (C6, R4) 0.26124 18 [9,-19] (C6, R5) 0.45302 15 [17,-6] (C6, R6) 0.33633 18 [90,-166] (C6, R7) 0.55679 -6 [119,84] (C7, R2) 0.37795 -3 [-7,-13] (C7, R3) 0.39892 -15 [-3,-3] (C7, R4) 0.37137 -12 [-13,-144] (C7, R5) 0.29614 21 [-127,181] (C7, R6) 0.42114 -15 [-3,2] Table 2. A typical correlation for a pair of KM optical images (Angular registration based on 15[degrees]). Cell index CC[F.sub.max] [theta] [x, y] (pixel) (Col., Row) (degree) (C1, R2) 0.27635 15 [42,-65] (C1, R3) 0.26147 15 [13,8] (C1, R4) 0.25001 15 [-4,101] (C1, R5) 0.26463 15 [19,11] (C1, R6) 0.40851 15 [11,14] (C2, R1) 0.29890 15 [-2,4] (C2, R2) 0.44403 15 [9,6] (C2, R7) 0.44390 15 [-119,81] (C3, R1) 0.33065 15 [6,1] (C3, R2) 0.28137 15 [10,-3] (C3, R7) 0.56988 15 [23,1] (C4, R1) 0.38804 15 [4,0] (C4, R2) 0.36664 15 [13,-2] (C4, R7) 0.35934 15 [24,-3] (C5, R1) 0.29101 15 [-144,71] (C5, R2) 0.33398 15 [17,-4] (C5, R6) 0.45089 15 [19,-2] (C5, R7) 0.25491 15 [100,-79] (C6, R1) 0.38182 15 [53,38] (C6, R2) 0.44428 15 [7,-4] (C6, R3) 0.26104 15 [102,-123] (C6, R4) 0.24524 15 [10,-8] (C6, R5) 0.45302 15 [17,-6] (C6, R6) 0.33438 15 [87,-154] (C6, R7) 0.55393 15 [119,84] (C7, R2) 0.31479 15 [-57,-81] (C7, R3) 0.35473 15 [-168,-80] (C7, R4) 0.31181 15 [7,-152] (C7, R5) 0.24747 15 [-130,183] (C7, R6) 0.41028 15 [52,134] Table 3. Final CMCs in the KM correlation. Cell index CC[F.sub.max] [theta] [x, y] (pixel) (Col., Row) (degree) (C1, R2) 0.29604 12 [20,-7] (C1, R3) 0.29071 12 [18,-7] (C1, R4) 0.27868 12 [16,-5] (C1, R5) 0.26463 15 [19,11] (C1, R6) 0.41703 12 [1,0] (C2, R1) 0.29890 15 [-2,4] (C2, R2) 0.44403 15 [9,6] (C3, R1) 0.33065 15 [6,1] (C3, R2) 0.28138 15 [10,-3] (C3, R7) 0.56988 15 [23,1] (C4, R1) 0.38804 15 [4,0] (C4, R2) 0.36664 15 [13,-2] (C4, R7) 0.35934 15 [24,-3] (C5, R1) 0.36111 12 [19,1] (C5, R2) 0.33398 15 [17,-4] (C5, R6) 0.50059 12 [8,4] (C5, R7) 0.27228 12 [6,5] (C6, R1) 0.42877 12 [11,3] (C6, R2) 0.44577 18 [-3,-14] (C6, R4) 0.26124 18 [9,-19] (C6, R5) 0.45302 15 [17,-6]
|Printer friendly Cite/link Email Feedback|
|Author:||Tong, Mingsi; Song, John; Chu, Wei|
|Publication:||Journal of Research of the National Institute of Standards and Technology|
|Date:||Jan 1, 2015|
|Previous Article:||On the Stability of Rotating Drops.|
|Next Article:||SAGRAD: A Program for Neural Network Training with Simulated Annealing and the Conjugate Gradient Method.|