Influence of Noise on the DTW Metric Value in Object Shape Recognition

Full Text

1. Introduction At identification of graphic objects there is a number of problems that need to be investigated first. One of such problems is the influence of noises on the quality of recognition. The use of methodology described in Refs. [1, 2] is oriented on multiple stages of preliminary image processing aimed at extracting primary image features, such as contours, angles, texture, etc. [3, 4]. At the final stage, the object properties are compared with the sample object properties basing on a certain metric that allows the classification of objects. The object contour is known to be one of the most informative features of the object shape [5, 6]. Although the issues of contour receiving and mathematical description attract much attention, a significant role here is played by the recognition methods using signature analysis [7, 8]. It is based on the calculation of one-dimensional contour function from the two-dimensional array of the contour points with the use of the center of gravity of the studied object or, in some cases, without it. The process of identifying such one-dimensional contour function is identical to the analysis and comparison of time series data, since such contour function can be considered as an example of time series. Time series data are widely used in many scientific and practical areas, such as recognition of speech and music, hand-written text, electrocardiograms, stock exchange quotations, in bioinformatics, etc. The use of Euclidean metric (as well as the �� metrics) for their classification often leads to large errors. In the present paper in order to identify the object shape after the preliminary processing of the image we use the algorithm ArcHeight, one of the signature analysis algorithms, by using which one gets a contour function considered further as a time series. We briefly present the principles of the classical algorithm DTW that underlies the comparison of Received 27th October, 2018. time series data. The influence of noises on the value of DTW metric is theoretically analyzed. The results of simulations confirm the theoretical conclusion that the metric value is independent of noise values in a wide range of interval. Examples that show the area of applicability of the present method are presented. In the discussion, the advantages and disadvantage of the presented approach to the identification of contour functions are summarized. In conclusion, the direction of further studies in the field and the perspective of application are outlined. 2. Contour Function Let us define a contour function as the result of a certain transformation of the 2d form (contour) object into a 1d function of the boundary representation. Most methods of constructing such functions are based on the signature analysis that uses the representation of the contour function with respect to the center of gravity [9]. There are also methods that use contours, but do not use the center of gravity, which can be also considered as signature methods, e.g., the algorithms by Chetverikov [10], Rosenfeld [11], Mokhtarian [12] or the arc-chord distance method [13, 14], later referred to as ArcHeight [15]. In the present paper the contour function of the object is obtained using the classical algorithm ArcHeight. This algorithm is based on calculating the length of the perpendicular from the middle of some segment of the curve (the object perimeter) to the chord connecting the end points of the segment. This perpendicular is calculated using the formula 2 √︃ ((�� - ��)(�� - ��) - (�� - ��)(�� - ��)) �� = (�� - ��)2 + (�� (1) - ��)2 and is proportional to the value of curvature of the segment at the considered point [16]. The sequential tracing of the contour yields a certain tabulated function that characterizes the shape of the object. An example of such function for the silhouette of the aircraft JetCommander1121 is shown in Fig. 1. FileN=JetCommander1121.jpg 500 450 400 350 300 250 200 150 100 50 NPoint=2065 0 200 400 600 HordLen=35 S.Golay.Num=31 16 14 12 10 8 6 4 2 0 0 200 400 600 800 1000 1200 1400 1600 1800 2000 800 Figure 1. Silhouette of the aircraft JetCommander1121 with introduced noise at the level of 40 dB, its contour and500its co1n0t0o0 ur f1u20n0 ctio14n00calc1u60l0ated18u0s0 ing20t0h0e 0 200 400 600 450 NPoint=2065 method ArcHeight. The number of c4o00ntour points is 2064, the chord length is 35, the Savitzky-Gola3y50 filter length is 31 point 300 250 200 150 100 50 100 200 300 400 500 600 HordLen=35 S.Golay.Num=31 16 14 12 10 8 6 In the left upper corner of Fig. 1 the silhouette is shown, the right upper corner shows the contour of this, and at the bottom the resulting contour function, obtained using the ArcHeight method is presented. To obtain the contour function we used the following sequence of operations: image loading, filtering, conversion into binary black-and-white image, morphological cleaning of the residual noise, contour receiving, using of the algorithm ArcHeight for the contour function calculation, and its smoothing using Savitzky-Golay method. Since the size of the objects on the image can be different when applying the ArcHeight method, we used the technique of dynamical setting of the curve segment size to eliminate the size influence. Experiments have shown that the optimal value of the chord is � = �/100 + 14, where � is the segment length and � is the total length of the contour in pixels. Remark. To enhance the noise immunity of the method for large objects it is possible to use averaged values of coordinates of a few adjacent points rather than a single point as the end coordinates of the chord. 3. The Idea of DTW Let us denote the contour functions of the object and the sample as the sequences of values � = �1, �2, . . . , ��, . . . , �� and � = �1, �2, . . . , ��, . . . ��, respectively, generally with � ̸= �, and let us consider these functions to be time series data, so that the adjacent values of each series have similar time shifts. For comparing these sequences in the classical DTW method the matrix of distances (deformations) �(�, �) with the dimensions � × � is constructed, where each element (�, �) of the matrix represents a certain distance �(�, �) between two points �� and ��. Commonly this distance is calculated as a Euclidean one, i.e., �(��, ��) = (�2 - �2)1/2, (2) � � but it can be calculated as the norm �(��, ��) = |�� - ��| as well. Each element of the matrix corresponds to the flattened section between the points �� and ��. The purpose of the DTW algorithm is to construct a certain path � = �1, �2, . . . , �� , . . . , �� , such that max(�, �) � � < � + � + 1, obeying the following conditions: § the boundary condition: for the initial and final points of the matrix diagonal �1 = (1, 1) and �� = (�, �); § the continuity condition: for the adjacent points �� = (�, �) and �� = (�′, �′) it is necessary that (� - �′) � 1 and (� - �′) � 1; § the monotonicity condition: for the adjacent points and it is necessary that (�-�′) � 0 and (� - �′) � 0. From the theoretical variety of possible paths, the following one is chosen: ⎛ ⎞ ⎯ ⎸ � ⎸∑︁ �� � (�, �) = min ⎝⎷ �=1 �� /�⎠ . (3) In Eq.(3), the divisor � is used to normalize the metric at different dimensions of the sequences � and �. This path is found basing on dynamical programming by means of the formula �(�, �) = �(��, �� ) + min{�(� - 1, � - 1), �(� - 1, �), �(�, � - 1)}, (4) where �(�, �) is the accumulated path length and �(��, �� ) is the path length from the starting point to the point (�, �). As a result, a certain number is obtained characterizing the distance between the sequences � and �, which will be denoted by ���� . Figure 2 presents three matrices of distance. 50 100 150 200 20 40 60 80 100 120 140 160 180 200 50 100 150 200 50 100 150 200 20 40 60 80 100 120 140 160 180 200 220 0 40 80 120 160 200 Figure 2. Three matrices of distance and the calculated paths for comparison of obje5c0ts: EE (left); EE20with distortion of one of the objects (middle), EN (right) 20 The10l0eft-hand one res4u0lts from the comparison of two identical sequences SS (SampleSample), the middle one is obtained for a certain4v0ariation of one sequence with respect to ano1t5h0 er, and the righ6t0-hand one is obtained fo6r0 different sequences SN (Sample-NonSample). The diagonal top-bottom line corresponds to the optimal path. The smaller is the deviation of this line from the diagonal, the smaller is the difference between the se2q00uences. 80 80 Let us consider the problem of whether the minimal DTW path satisfies the definition of metric. For this aim, let us check the fulfilment of the metric requirements: - the axiom of identit1y00�(�, �) � 0, the equality10t0o zero corresponding to � = �. Since the elements of the matrix of distances are calculated in an Euclidean space, it is obvious that each element of the matrix will be positive and, therefore, the condition is satisfied. When t1h20e sequences coincide, th1e20distance along the principal diagonal will equal 0, since the Euclidean metric, calculated for each element of the diagonal, will be equal to zer1o4;0 140 § the axiom of symmetry �(�, �) = �(�, �). This condition is also obviously valid, since the permutation of positions in the metric means the transposition of the matrix of distances; 160 160 § the triangle inequality �(�, �) � �(�, �) + �(�, �). Automatically follows from 1 and 2 being presented as �(�, �) � �(�, �) + �(�, �). Thus, the use of the 1t8e0rm “DTW metric” is f1u8l0ly justified. Let us define the identification function, based on the DTW method, as 200 {︃1, ���� 2<00, � = 0, ���� � . 220 (5) where ���� is the DTW metric, and is the classification tolerance (CT) for the considered method. 200 Let us analyze some results of DTW metric calculations for realistic data. As an example, consider the contour functions of aircraft silhouettes presented in Fig. 31. 50 100 150 20 40 60 80 100 120 140 160 180 200 is in 1Such objects were chosen on purpose, since the silhouettes of the planes do not differ strongly, so it teresting to classify such objects (i.e., to divide them into classes). Fig. 3. Three matrices of distance and the calculated paths for comparison of objects: EE (left); EE with distortion of one of the objects (middle), EN (right). Figure 3. Silhouettes of aircrafts1 (from top to bottom, from left to right) Grumman TBF-1, Aero L-29, Arado Ar 234B, Curtiss P-40F, Dornier DO-335A, Grumman F4F-3, Arado Ar 240, Avro 668, Bell-X1, Jet Commander 1121, Mitchell-D-25C, Boeing B-47E (strongly reduce) Table 1 presents the values of metrics calculated for all combinations of aircraft silhouettes in Fig. 3. At the principal diagonal, the values of DTW metric calculated for the aircrafts of the same name are located. For combinations of different planes (SN) we get the mean value � = 0.639 and the variance � = 0.045, which allows the conclusion that the mean value for sample-sample combinations is essentially smaller than for sample-non-sample combinations. This is an evidence of DTW metric efficiency in the object shape recognition. One more issue of importance is the type of metric distribution under different distortions of the contour function. The simulation has shown that the distribution of the DTW metric value under the influence of noise occurs in accordance with the normal law. Thus, e.g., Fig. 4 presents a histogram of the metric values and the distribution density function calculated on its base for the Avro668 plane SS combinations. The metric value is different from zero, since in the process of investigation a noise was added on the plane silhouette that distorted the shape of the object and, finally, the contour function. 300 Histogramm distribution Fit Gaussian Law 250 200 Density 150 100 50 0 0.186 0.188 0.19 0.192 0.194 0.196 0.198 0.2 Data Figure 4. Histogram and metric distribution density function for the Avro668 plane SS combinations 0.186 0.188 0.19 0.192 0.194 0.196 0.198 0.2 Data RUDN Journal of MIPh. Vol. 26, No 4, 2018. Pp. 331-342 DTW Metric Values 336 Table 1 - Grumman TBF-1 Aero L-29 Arado Ar234B Arado Ar240 Avro 668 Bell- X1 Boeing B47E Curtiss P-40F Dornier DO335A Grumman F4F-3 JetCommander1121 Mitchell- D-25C Grumman TBF-1 0.000 0.533 1.116 0.927 0.342 0.504 0.480 0.480 0.526 0.509 0.556 0.923 Aero L-29 0.533 0.000 0.804 0.741 0.431 0.531 0.590 0.467 0.488 0.565 0.544 0.727 Arado Ar234B 1.116 0.804 0.000 0.688 0.998 0.794 1.214 0.941 0.777 0.765 0.953 0.559 Arado Ar240 0.927 0.741 0.688 0.000 0.864 0.700 1.026 0.944 0.789 0.780 0.843 0.698 Avro 668 0.342 0.431 0.998 0.864 0.000 0.418 0.361 0.313 0.388 0.321 0.475 0.764 Bell-X1 0.504 0.531 0.794 0.700 0.418 0.000 0.563 0.485 0.429 0.495 0.568 0.641 Boeing B47E 0.480 0.590 1.214 1.026 0.361 0.563 0.000 0.479 0.475 0.507 0.586 0.972 Curtiss P-40F 0.480 0.467 0.941 0.944 0.313 0.485 0.479 0.000 0.344 0.410 0.607 0.778 Dornier DO335A 0.526 0.488 0.777 0.789 0.388 0.429 0.475 0.344 0.000 0.355 0.588 0.655 Grumman F4F-3 0.509 0.565 0.765 0.780 0.321 0.495 0.507 0.410 0.355 0.000 0.569 0.628 Jet Commander 1121 0.556 0.544 0.953 0.843 0.475 0.568 0.586 0.607 0.588 0.569 0.000 0.882 Mitchell-D- 25C 0.923 0.727 0.559 0.698 0.764 0.641 0.972 0.778 0.655 0.628 0.882 0.000 240 0.927 0.741 0.688 0.000 0.864 0.700 1.026 0.944 0.789 0.780 0.843 0.698 Avro668 0.342 0.431 0.998 0.864 0.000 0.418 0.361 0.313 0.388 0.321 0.475 0.764 Bell-X1 0.504 0.531 0.794 0.700 0.418 0.000 0.563 0.485 0.429 0.495 0.568 0.641 BoeingB 47E 0.480 0.590 1.214 1.026 0.361 0.563 0.000 0.479 0.475 0.507 0.586 0.972 CurtissP -40F 0.480 0.467 0.941 0.944 0.313 0.485 0.479 0.000 0.344 0.410 0.607 0.778 Dornier DO335GAo0s.t5e2v6 Iva0n.4M88., S0ev.7a7s7tian0o.v78L9 eon0i.d38A8. In0fl.4u2e9nce 0o.f47N5oise0o.3n44the 0D.0T0W0 Grumma M0.e3t5r5ic . .0..588 03.63575 nF4F-3 0.509 0.565 0.765 0.780 0.321 0.495 0.507 0.410 0.355 0.000 0.569 0.628 of amgarnedeemr1 e0.n5t56wit0h.54t4he 0p.a95r3ame0t.8e4r3s �0.=4750.190.2516827; 0�.58=6 0.00.600174910..58M8 ul0t.i5p6l9e ex0.p00e0rim0e.n88t2s with12o1 ther silhouettes also confirm the normal distribution law for the values of metrics undMeritchtehlle effect of noise. -D-25C 0.923 0.727 0.559 0.698 0.764 0.641 0.972 0.778 0.655 0.628 0.882 0.000 S4p. ecSifpicefceiafitcurFeesaotfuDreTsWomf eDtrTicWapMpliectartiiocnApplication UUnnddeerr pprroocceessssididenetniftiicfiactiaotniorenalroeabjleoctbs,jethcetisr, stizheeiarndsipzoesaitniodn pwoitshitrieosnpewctittohthreesspamecptleto the samaprelenoatreknnoowtn kinnoadwvnanicne.aTdhvearenfcoer.e, Tit hisenreecfoesrsea,ryittoisusneescoemsseaarylgotroithumseicsmometheodalfgoorrithmic method for correct matching of contour functions in the process of recognition. Mcoorrreeocvt emra, tcehvienng ofofrcotnhteourroftuantcitoionnsofinathseinpgroleceossbojef crte,cotghneiticoonn. tour function shifts by a certain number of points corresponding to the rotation angle. An example of such contour Moreover, even for the rotation of a single object, the contour function shifts by a certain number of points func corresponding to the rotation angle. An example of such contour functions with the cyclic shift by nearly 640 ptoiinotns fsorwthiethsilhtohueettceyofcBlioceisnhgBif4t7Ebiys snhoewanrliyn F6ig4.05. points for the silhouette of BoeingB47E is shown in Fig. 5. shift 0 200 400 600 800 1000 1200 Figure 5. BoeingB47E aircraft silhouettes (reduce) with different angle of rotation Fig. 5. BoeingaBn47dE tahirecriarftcsoilnhotuoeuttresf(urendcutceio) wnisthwdiiftfehrecnyt acnligcle sohf riofttation and their contour functions with cyclic shift. Calculating the DTW metric for cyclically shifted contour functions from Fig. 6, we get the Cvaallcuuelartin=g0.t7h17e4D, wThWichmcoertrreiscpofonrdsctyoctlhiceaSllNy csohmifbtiendatcioonntfoorutrhefucnocmtpioanresdfcroonmtouFrig. 6, we get the valdutwe ���� = 0.7174, which corresponds to the SN combination for the compared contfuonucrtiofunns.cStiinocnes.theSionriceenttahtieonoorifetnhteaotbiojenctosfilhthoueetotbe,jie.ce.t, tshielhsohuifettotfeo, nie.ec.,ontthoeursfhuinfcttioofn one contwoiuthrrefuspneccttiotonanwoitthherriessnpoetcktnotownana optrihoerri, sisomneotopkenraotwionnsaareprtoiobrey,pesrofmoremeodpteoraretsioolnvse are to bthee pperorbfolermm.eFdirstto, arsessuomlveethtaht etheprnoubmlbemer .ofFpiorisntt,s oafssthuemsaemtphlaetextcheeednsutmhabt oerf tohef opbojienctts of thetosabme prelceogenxiczeeedd, si.et.,hamt> onf. Otthheerwoisbej, ewcetchtaongbe etheroebcjoecgtnfoirztehde ,saim.ep.le, a�nd v>ice �ve.rsaO. Stehceornwdi,siet, we chanisgneecthesesaorbyjteocatufgomr etnhtethseasmamplpeleafnrdomvitchee rviegrhsteb.yStehceonnudm,bietriosfnpeocinestss,acroyrrteospaoungdmingentot the samtpheleobfrjoecmt, it.he.e, Cri*g=hct,cby,...t,che,cn,cu,m...,bce.rTohfirpdo, iint itss,neceodrerdestpooonrgdainnigzettohethseeqoubenjteicatl , i.e., �* = 1 2 m 1 2 n �1, �2, . . . , ��, �1, �2, . . . , ��. Third, it is needed to organize the sequential comparison of the obje6ct with the fragment of the augmented sample. In other words, we calculate the DTW as a function of the object position on the augmented function �� of the sample in the form � �� � (�, ��(�)) = min (︂√︁∑︀� �-1 �� /� )︂ - , where ��(�) = �*(��, ��+1, . . . , ��+� 1), � = 1, �. Here �� at a certain � determines the value of shift of the window moved along the sample, in which the values of the DTW metric is calculated. The metric value will be calculated as ���� = min (� �� � (�, ��(�))). � 6. Noise Resistance In the development of new methods for identification of the object shape one has to take the influence of different factors into account [17]. One of them is the permanent presence of noises in the real image, which finally distorts the contour function. Let us estimate the influence of noises on the DTW metric value. Let the contour function be presented as � = �1, �2, . . . , ��, . . . , �� for the object and as � = �� + ��, � = 1, � for the sample, where �� is a certain value of the noise component distributed according to the normal law and added to each value of the numerical sequence. Let us substitute the values of � into Eq. (2) and calculate the distance for each value of �: �(�� - ��) = (�� - (�� - ��))2 , � - 1, �. (6) In fact, the result of the calculation means that under the influence of noises the value of metric converges to the �2 law [18]1. According to the central limit theorem, when √2� � converges to infinity for a large number of degrees of freedom �, the distribution of the random variable � → �2(�) can be approximated by the normal distribution, with parameters � = �(�, 2�), with � → ∞ (more exactly, � -� → �(0, 1)). Therefore, the value of metric in the sum of Eq. (6) for a large number point of sequence must tend to zero. Hence, the value of metric should not change under the addition of noises to the contour function in a wide range of the values, determining the shape of objects. Let us verify this statement by simulation using the Matlab software. We impose random noise on the contour function (series), e.g., the one obtained from the silhouette of the AeroL29 aircraft, using the built-in function awgn that allows the addition of noises to an array of points with the level expressed in dB2. Let us calculate the values of metric using Eq. (4) with Eq. (6) taken into account, starting from the signal-to-noise ratio 100 dB and gradually reducing it to 3 dB with the step of 1 dB. The simulation results for three silhouettes of AeroL29, JetCommander1121, and MitchellD25C shown in Fig. 6 demonstrate that the metric remains unchanged practically until the noise level becomes comparable with the signal level. 0.18 0.16 DTW for AeroL29 DTW for JetCommander1121 DTW for MitchellD25C 0.14 Value of DTW 0.12 0.1 0.08 0.06 0.04 0.02 0 0 10 20 30 40 50 60 70 80 90 100 Signal/Noise (dB) FiguFirge. 6.6M. etMricevtarluiecs vvearsluus ethse nvoeisresluevsel tfohr eAenrooLi2s9e(solelidvelinle)f,or AeroL29 (solid line), JJeettCCoommmamndaern1d12e1r(1da1sh2e1d l(inde)a, sahndeMditlcihnelelD)2,5aCn(ddashM-doitttcedhleinlel)D. 25C (dash-dotted line) Basing on the considerations presented above, we conclude that the DTW metric is persistent against the noise in a wide range of values of noise. Basing on the considerations presented above, we conclude that the DTW metric is persistDenitscaugsasiniostntahnednociosne cinlusaiownide range of values of noise. The DTW metric offers wide possibilities of object shape recognition. The disadvatage of the algorithm include high computation complexity of calculating the metric O(mn) and, as a consequence, essential increase of th1eIncomthpiustaptioanpteimr eitfoirssesqhuoewncnes tohf ahitghthdiemeimnsiaognes. noises always lead to the normal law of distribution for metriHc.igh potentialities are related to the application of DTW metric to the recognition of graphical objects 2 shape. The capabilities of DTW allow the identification of objects, for which the description is based on the nonliDneuarevtaoriattihoen onfotrhme caolndtoiusrtrfuibncuttioionnsteopf tthhateonccouirsseinctohme cpaosenoefnotb, jtehcteshaadpde idtiisotonrtoiofn.nIonistheesteoctahsees,contour function istheeqmueitrviacsleonf tthetoLptthypee aardedinitaipopnlicaobflen. Tohiseeantaolystihs eofitmheaDgTeWwmitehtricitssdesmuobnssetrqatuees nitts rpesriostcanecsesianggainastnd generation of ctohnetnoouisre,fwuhnicchtisoingn.ificantly extends the area of its application. Besides the identification of the object shapes, this metric is widely used in speech recognition, in medicine, bioinformatics, and economics in the analysis of trends, where the parasitic noise level can be very high, etc. The work was supported by the Russian Foundation for Basic Research, grant No. 16-07-00556. References 1 Seul M., O'Gorman L., Sammon M. Practical Algorithms for Image Analysis. - 7. Discussion and Conclusion The DTW metric offers wide possibilities of object shape recognition. The disadvantage of the algorithm include high computation complexity of calculating the metric O(mn) and, as a consequence, essential increase of the computation time for sequences of high dimensions. High potentialities are related to the application of DTW metric to the recognition of graphical objects shape. The capabilities of DTW allow the identification of objects, for which the description is based on the nonlinear variation of the contour function step that occurs in the case of object shape distortion. In these cases, the metrics of the Lp type are inapplicable. The analysis of the DTW metrics demonstrates its resistance against the noise, which significantly extends the area of its application. Besides the identification of the object shapes, this metric is widely used in speech recognition, in medicine, bioinformatics, and economics in the analysis of trends, where the parasitic noise level can be very high, etc.

About the authors

Ivan M Gostev

National Research University “Higher School of Economics”

Author for correspondence.
Email: igostev@hse.ru

Doctor of Technical Sciences, professor of Department of Information Systems and Digital Infrastructure Management of National Research University “Higher School of Economics”

20, Myasnickaya str., Moscow, 101000, Russian Federation

Leonid A Sevastianov

Peoples’ Friendship University of Russia (RUDN University)

Email: sevastianov-la@rudn.ru

Professor, Doctor of Physical and Mathematical Sciences, Professor of Department of Applied Probability and Informatics of Peoples’ Friendship University of Russia (RUDN University)

References