Experimental Study of Distributions Differential Invariants Based on Spline Image Models

Abstract

The article investigates the distributions of the brightness of pixels for differential invariants based on partial derivatives of the image model, as a linear combination of Bsplines, close to interpolation on the average. For the magnitude of the gradient, Lapsasian, the Hessian determinant and the curvature of the scaling curve, conclusions are presented on the possibility of using digital terrain photographs based on aerial survey data for processing tasks.

Keywords

• 1 Image processing
• image sharpness
• digital stabilization
• B-spalne
• linear filter operators

1. Introduction

Today, the development of unmanned aircraft in Ukraine is due to a number of factors, among which use for reconnaissance missions, including in the combat zone. Among the urgent tasks that are being implemented today for the development subsystems of target load for unmanned aerial vehicles (UAVs) is the ability to perform navigation via an optical channel in the absence of a GPS signal. That is, the processing of terrain images should be carried out directly on board the UAVs, the location of the aircraft should be determined and the flight mission control should be performed. Without considering the whole range of possible options for solving the problem, we note one of the approaches, namely: determining the location based on the analysis of local features of a digital image.

It is assumed that the location of the aircraft (AC) can be determined with acceptable accuracy if one or more terrain objects are hit in the field of vision of the target load cameras, for which their location is known in advance. At the heart of modern effective methods for recognizing objects that are invariant with respect to rotations and changes in scale, the analysis of partial derivatives of the image of the first and second order is laid, in order to determine and describe the singular points an objects of search . In this part, the theoretical substantiation of the article's research is carried on the basics of an image model based on two-dimensional polynomial splines based on B-splines, which close to interpolation on average. [1].

The search and recognition of objects based on the determination of special points in digital photos is a well-known and widespread approach to the processing of data, which are aerial and satellite images. A caveat when using well-known methods in the development of appropriate software for the on-board hardware complex of an aircraft is the relative computational complexity of standard algorithms, which complicates real-time processing and, on the other hand, the patented nature of the search methods (in particular, the SIFT method and its modifications). However, real and of the deadline and the requirement for scientific novelty, is the approach to finding singular points of objects based on differential invariants based on partial derivatives, based on the author's image model in the form of a two-dimensional linear combination of B-splines, to the study of their distribution this work is devoted.

2. Analysis of publications and formulation of the research problem

Determination of local features of digital images (DI) is an integral part of computational procedures for searching and recognizing objects, photogrammetry, orthorectification of air reconnaissance data, target detection on digital video, and the like. Speaking about the features of the DI, we mean local, low-level features that are not related to spatial relationships - the edges of objects, curvature, which is supplied by the rate of change of light intensity in the direction of the edge - those that are invariant with respect to scaling, rotation and, partially , regarding changes in the observation point and the intensity of the image. They are well localized both in the spatial and in the frequency regions, they are resistant to noise, and the individual feature allows the search for relationships between the features of objects presented in different images of the scene [2].

In general, the mathematical basis for the search for features is a broad analysis of partial derivatives of the first and second order, which are obtained from a continuous image model. Convolution of their discrete counterparts with DIs is often used in software, such as the operators Roberts and Previti [3]. Another widely used approach is the analysis of the derivatives of the image model after convolution with the Gaussian function [4-9].

As shown in work [10], an alternative to the Gaussian-based smoothed image model can be a model based on linear combinations of B-splines, which are close to interpolation ones on average. Having actually similar properties in the frequency domain, like the Gaussian function, B-splines are simpler in calculus and allow the construction of an image model, which, due to its analytical form, makes it possible to obtain partial derivatives, on the basis of which it is possible to construct high-speed operators invariant with respect to rotation and scale change search for the features of DI [11-13]. Let in a continuous model of a two-dimensional image p(t, q) as the impulse call function is used the model

Sr,0  p,t, q    pi, j Br,ht t  iht  Br,hq q  jhq , iZ jZ r  2,3, (1) where Br,h   - B-spline of order r, which is determined [1] on a uniform partition of the real axis with step h, for example, for r=2, to within to an argument, we have:  0,   3  2t h2 8, B2,h t    3 4  2t h2 4,   3  2t h2 8, t 3h 2;3h 2, t 3h 2;  h 2, t  h 2; h 2, t h 2;3h 2.

Then, due to the explicit form of model (1), it is not difficult to obtain both an explicit form of its partial derivatives and their discrete analogs, which are suitable for processing digital images. The set of derivatives of model (1) and their analogs in the scale-position space up to the order k at a given point of the image and at a given scale can be called a k -jet, which corresponds to the cropped Taylor expansion for a locally smoothed fragment of the image [9]. These derivatives together describe the basic types of features in scale-position space and compactly represent the local structure of the image. For k  2 , at the selected scale, the 2-jet contains derivatives

 Sr,0  p,t, q t , Sr,0  p,t, q q , Sr,0  p,t, q tt , Sr,0  p,t, q qq , Sr,0  p,t, q tq  , From five components of a 2-jet for each of the models (1) of order r  2,3, four differential invariants with respect to local rotations can be constructed - the magnitude of the gradient Sr,0 , 2  S Laplacian r ,0 , determinant of Hessian det r,0 and the curvature of the scaling curve kr,0 (up to the notation of operators of different orders): S  S2  S2

t q , 2S  S  Sqq ,

tt det   SttSqq  S2

tq , k  S2Sqq  Sq2S  2SS S

t tt t q tq , To obtain specific types of operators (2)-(5) when different r  2,3, corresponding explicit looks of partial derivatives of model (1). To work with the DI when r  2 discrete analogs S2,0  p , t , qt ,

S2,0  p , t , q 

S 2,0,l  i1 j1   l,iii, jj j  pii, jj iii1 ji1 q taking into account ht  hq  1, can be submitted as follows [11]: (6) where pi, j - lightning intensity in i, j  pixel; l  t, q t 

 1 1  16  10 6 0 6 1

 0  1  ; q 

 1 1 

6 16  1 0 1 

 0 6  0 1  .

;

Accordingly, discrete convolutions of second-order differentiation operators based on model (1) when r  2 are [11]: where

S 2,0,l  i1 j1   l,iii, jj j  pii, jj iii1 ji1 (2) (3) (4) (5) (7) l  tt, qq, tq qq 

 1 1  8   1 6

; 2 12 2 1 

 6 

 1  ; tt 

 1 1 

2 8  1 12 6 6 1 

 2  1  ;  1 1  tq  4  0  1 0 0 0 1

 0  1  .

In a similar way, partial derivatives of the first and second order are obtained for the splines of higher orders [12].

Having cited the results of previous studies of the authors regarding to linear operators for determining the features of the DI, we set the goal of this work to investigate the distributions of these invariants, taking into account the possible distortion of the DI in the form of smoothing or a decrease in linear dimensions. Such studies should contribute to the formation of a list of tips on how to determine the "more resistant" to distortion features from the entire list of those that can be determined during DI processing.

3. Presentation of the main material

It should be noted that DI, in particular photographs, can be considered as an implementation of a discretized function of illumination intensity (raster), which has a multimodal form with pronounced both local and global features, and the location of such features on the raster for each individual photo is a random value. Let us also pay attention to the fact that a feature that can be determined at a certain scale of the DI may not be useful in further processing due to the fact that such a feature may not appear on other scales. The degree that determines the "benefit" of a particular feature for further work may be the value of a particular differential invariant (2) - (5). Therefore, in the further presentation, we will consider examples and analysis of the distributions of such invariants when processing aerial photography data (Fig. 1).

To determine the detectors for the reference image (Fig. 1), we apply the linear operator Delta  pi, j  in the form of a discrete convolution of the sequence  pi, j i, jZ :  where d _ pi, j i, jZ - newly formed sequence to search for special points; L - symmetric matrix of dimension (7х7); L  1

Ext  extl ,i _ posl , j _ posl ;l  1, M  or then of volume M , which as extl ,l  1, M contains the value of the invariant calculated at the locations of local minimums and maxima

d _ pi, j i, jZ : if d _ pi, j  max d _ pii, jj ;ii  i 1,i  1, jj  j 1, j  1 d _ pi, j  mind _ pii, jj ;ii  i 1, i  1, jj  j 1, j  1

i _ posl  i , j _ posl  j .

Note that such an approach to determining the location of the DI features (array of indices i _ posl , j _ posl ;l  1, M 

) is not original - the SIFT method [13] and many of its modifications for the same purpose use the difference between DI convolutions with Gaussans (difference of Gaussians – DoG), an analogue of which [14-16] is the expression (8). However, unlike the known approaches, we will focus on the search for “persistent” features not by large-scale transformations of the DI, but by calculating the values of extl ,l  1, M invariants of the type (2) - (5) and selecting from them only those that have advantages. Let us set the goal to investigate the distributions of the invariants calculated at the indicated points and give recommendations on the selection of points-features of digital aerial survey data, which can later be used for aircraft orientation.

Using the obtained locations of local extrema, was calculated extl ,l  1, M - the values (2) - (5) of the singular point detectors taking into account (6), (7) after the drawdown of the masks of the derivatives of splines with d _ pi, j i, jZ . It should be noted that the high saturation of the singular points even for small fragments of images imposes the requirement to select those detector values that correspond to unlikely realizations on the tails of the distributions of operators (2) - (5). Therefore, it was proposed [12] for the final selection of singular points suitable for recognition, to analyze the probability distribution of the array of values that satisfy the conditions: extl ;l  1, M 

of a particular detector and leave those extl  ext1 , l  1, M , and where F 1  by – the inverse function of the probability distribution of the detector for a specific DI ; ext1 , ext12 – quantiles of such a distribution on its tails for some relatively small probabilities 1 and 2 .

When analyzing the distributions of operators (2), (3), and (5), which have a distribution density function close to a symmetric function, which, for definiteness, can, for example, be set 1  0, 01 and 2  0, 01, which should leave for further analysis 2% of the number of singular points. And for the distribution, operator (4) should take values 1 less, and for the right tail 2 – more, for example, 1  0, 005 and 2  0, 015 .

In addition, on the number of singular points in [12], the effect of smoothing and decreasing the linear dimensions of the DI was studied. In particular, convolutions with symmetric masks of size (7x7)

ext1  F 1 1  extl  ext12 , l  1, N , ext12  F 1 1  2  , (11) (12) (6)  obtained on the basis of the spline model (1) at r=6.

The authors have shown experimentally that it is possible to significantly reduce the number of singular points on the DI by smoothing and reducing their linear dimensions. In this case, we obtain a smaller number of singular points with divisions of the detectors, which differ from the distributions on the initial size of the DI only in scale. Therefore, it can be stated that the definition of special points is quite positively affected by both the smoothing of the DI and the decrease in their linear dimensions, because the number of points decreases, however, the value of the detectors correlates with those that were determined for the original image. As for the choice of a specific differential invariant for determining the singular points, it is recommended to pay attention to the curvature of the curve scaling k (5), because it is for this operator that the maximum growth rate of the distribution function detector near zero, and therefore the features that will be highlighted on tails will be more "characteristic" and their number will be relatively smaller.

If the location of the singularity is determined directly from the values of  pi, j i, jZ , that is, formed (9), or an array of indices i _ posl , j _ posl ;l  1, M  , then as a result of the experimental studies it was

Delta  pi, j 

established that the application of operator (8) to the initial DI when finding singular points does not have a priority value comparison with the definition of singularities based on differential invariants (2) - (5) before the approach that was studied in this work, namely, calculation directly over the raster. In both cases, the distributions of all invariants have a similar shape and, despite the different scales along the abscissa, there is a significant correlation of their values.

The thesis received further confirmation that smoothing DI and decreasing linear dimensions significantly affect a smaller number of features, while those features that remain are on the tails of the distributions of differential invariants, which makes it possible to formalize the process of their selection for further analysis and use in the task of finding similar objects in photographs.

So, we will focus our research on the analysis of the percentage of coincidence of the location of the singular point, determined for the reference DI and the control's DI of the same size, but with the introduced changes. That is, let there be an array Ext of detectors (9), which are determined at the singular points of the initial DI according to any of the invariants (2) - (5) and selected according to the criteria (10), (11) in accordance with the distributions of each of the invariants. We introduce some distortions into the DI, for example, smoothing behind the operator with a mask (12) and determine the location of the singular points with the calculation of the corresponding invariant in them, obtaining an array Ext_C, which containing the selected detector values, according to criteria (10) and (11). Next, two arrays are compared Ext and Ext_C in order to establish the number of coincidences of the location of the selected special points, that is, the number of matches of K pairs of point indices i _ posl , j _ posl ;l  1, M 

i _ posg , j _ posg ; g  1, MC and , where М – the number of singular points in the array Ext ; МС – the number of singular points in the array Ext_C. Finally, the analysis will be subject to the percentage V of singular points of the Ext_C, array that have the same location with the feature in the array Ext:

K V 

100%

Delta  pi, j 

Delta  pi, j 

MC .

The authors analyzed the value of the statistics V for each of the types of differential invariants (2)(5), as well as for the native variants of distortions. In addition, the estimate V for the DI was considered separately after the action of the operator and after the action of smoothing the output DI. Such studies will make it possible to finally formulate recommendations for the selection of special points that can be used in the future to solve the problem of aircraft navigation through an optical channel.

For example, tables (Tables 1-6) present the results of coincidence studies after applying the differential curvature invariant (5). Thus, the table (Table 1) shows the values of the statistics V, obtained after the action of the operator for six test images (Fig. 1) after applying smoothing by the operator with a mask (12). The left column of the table contains the percentage of the original number of singular points, which are determined by the criteria (10), (11), that is, in fact, it is

Delta  pi, j  20 a) 35,1

b) 48,47

c) 35,03

d) 27,03

e) (how the above DI will be subject to transformation after the operator ): the array Ext is formed after smoothing by the operator with a mask (12), and Ext_C is formed after double smoothing by the operator with a mask (12).

Delta  pi, j 

The following three tables (Tables 4-6) show the percentage of coincidence of the differential invariant (5) after similar distortions, but without using the operator pass filter with a mask (12) Delta  pi, j  , but simply smoothed by a lowe)

Delta  pi, j 

Delta  pi, j  transformation by the operator ) after the linear dimensions of the image were halved with smoothing, according to the action of the operator with the mask (12), and the invariants that were determined for the DI after a similar reduction with anti-aliasing and already new anti-aliasing of such a reduced image. 4. Conclusions Note that the authors obtained similar tables for other differential invariants (2) - (4).

Having carefully analyzed the results of the last tables (Tables 1-6) and similar tables for other invariants, one can draw the following conclusions.

1. The well-known approach, according to the definition of a detector using partial derivatives of the smoothed DI model for invariants (2) - (5), is indeed more desirable than the calculation of discrete analogs of partial derivatives with respect to DI, which was transformed by the operator

. However, it can be noted that for the Hessians (4) and Laplacian (3) the difference is less noticeable. 2. After the DI is to be smoothed, the percentage of coincidences of the number of positions of the special points is significantly higher than that of the original DI and the smoothed DI. This is generally consistent with the well-known approach of SIFT-like methods to select singular points by conducting large-scale DI analysis, the essence of which is to compare features at different scales and with different degrees of smoothing and leave those that "appear" at all scales. In contrast to the well-known approach, authors propose to select points for invariants corresponding to conditions (10), (11), after one or two smoothing of the output DI by an operator with a mask (12), as such that has the greatest degree of smoothing. This approach is less computationally burdensome, and the percentage of stable features is high enough for operators (3)-(5) - about 60%. 3. DI reduction with anti-aliasing for feature selection should be used only for large-volume images with high detail, because otherwise the percentage of features that coincide after distortion will be quite unstable and variable. A small number of values of one or another invariant selected on the tails of the distribution of values will not always guarantee that most of them are really stable features. 4. An increase in the percentage of the number of values of the invariant sampled on the tails of distributions by more than 8% is not justified, because the number of “features” increases, and their stability does not actually grow, or changes insignificantly. Leaving 1-2% of the calculated invariants is also inappropriate - there is a high variability and not always a high percentage of matches. Quite acceptable and optimal in terms of quality and quantity criteria, the number of points should be considered at the level of 4-6%. 5. The table (Table 2) shows the results indicating that after processing the smoothed DI by the

Delta  pi, j  operator (8) for every 10-12 pixels of the digital image of the terrain, there is a point of local extremum, that is, a point candidate for selection as a feature. It should be borne in mind that a digital image of the terrain, tied to a digital map in the area of the flight mission, can be tens, and possibly hundreds of pixels in size. Therefore, taking into account the proposed selection criteria, even if we select 4% of the points whose location corresponds to the values of the differential invariants (2) - (5) on the distribution tails, their number will reach hundreds of thousands, and this is subject to preliminary smoothing of the digital image. Such a number of points will be a burden on the on-board computing system and a radical solution to the problem of reducing the number of features is inclusively in reducing the linear dimensions of the DI. 6. According to the authors, the preference among the types of differential invariants can be given to the operator (5), built from a digital image after its smoothing. This operator, when selecting 4% of the values on the distribution tails, has a comparable level of coincidence of features with corresponding distortions associated with smoothing. So, on average, the number of matches is as follows: 57.21% for operator (5), 61.05% for (4), 59.34% for (3). But operator (3.5) is more resistant to distortion of the DI when its size decreases - the percentages for 4% matches are as follows: 42.91% for (5), 34.4% for (4) and 36.33% for (3), in addition, the results for both the Hessians and the Lapsasian are more variable, which indicates the instability of the results obtained, in contrast to the curvature of the level (5).

On the question of how many times the linear dimensions of a digital image can be reduced, the answer will depend on the specific resolutions of the fixation systems (photo and video cameras) and the corresponding practical research directly during flight and other tests of the system being developed. In conclusion, it should be noted that all the studies carried out were carried out on the example of a small number of typical examples (Fig. 1), therefore, all figures and conclusions should be considered advisory and those that can be clarified in the course of further practical tests.

5. References

[1] P. Prystavka, Polynomial splines in data processing, Dnipro, NDU, 2004. [2] B. Kukharenko, Image analysis algorithms for determining local features and recognizing objects and panoramas, Informational technologies 7 (2011). [3] J. M. Prewitt, M. L.Mendelson, The analysis of cell images, Annals of the New York Academy of

Science 128 (1966) 1035–1053. [4] I. E. Sobel, Camera Models and Machine Perception, PhD Thesis, Stanford University, CA, 1970. [5] J. Canny, A computational approach to edge detection, IEEE Transactions on Pattern Analysis and

Machine Intelligence 8(6) (1986) 679–698. [6] D. C. Marr, E. Hildreth, Theory of edge detection, Proceedings of the Royal Society of London

B207 (1980) 187–217. [7] C. Schmid, R. Mohr, C. Bauckhage, Evaluation of interest point detectors, International Journal of

Computer Vision 37(2) (2000) 151–172. [8] T. Lindeberg, Scale-space, in: B. Wah (Ed.), Encyclopedia of Computer Science and Engineering,

John Wiley and Sons, Hoboken, New Jersey, 2009, pp. 2495–2504. [9] J. J. Koenderink, A. J. van Dorn, Generic neighborhood operators, IEEE Transactions on Pattern

Analysis and Machine Intelligence 14(6) (1992) 597–605. [10] P. Prystavka, M. Rybiy, Model of realistic images based on two-dimensional splines close to interpolation on average, Science-intensive technologies 3(15) (2012) 67–71. [11] P. Prystavka, Determining the features of images based on combinations of B-splines of the second order, close to the interpolation on average, Current problems of automation and information technology19 (2015) 67–77. [12] P. Prystavka, O. Tyvodar, B. Martyuk, Feature detection for realistic images based on b-splines of 3rd order related to interpolar on average, Proceedings of the National Aviation University 2(71) (2017) 76–83. [13] D. G. Lowe, Object recognition from local scale-invariant features, in: Proceedings of the

International Conference on Computer Vision, Corfu, Greece, 1990, pp. 1150–1157. [14] A. V. Iatsyshyn, V. O. Kovach, Y. O. Romanenko, I. I. Deinega, A. V. Iatsyshyn, O. O. Popov, S.

H. Lytvynova, Application of augmented reality technologies for preparation of specialists of new technological era, CEUR Workshop Proceedings 2643 (2020) 134–160. [14] Z. Pawlak, Rough Sets – Theoretical Aspects of Reasoning about Data, Kluwer Academic

Publishers, Dordrecht, volume 9, 1991. doi: 10.1007/978-94-011-3534-4 [15] Quinlan JR C4.5: Programs for Machine Learning. Morgan Kaufmann Publishers, San Mateo. [16] B. Horn, B. Schunk, Determing Optical Flow MIT Artificial Intelligence Laboratory, 1980.

References