Все выпуски

Рассмотрена задача вложения бесконечного счетного графа в непрерывное метрическое пространство. Введено понятие равномерного вложения, при котором не возникает точек накопления на множестве образов вершин и образы ребер имеют ограниченную длину. Найдены необходимые и достаточные условия в терминах структуры графа для возможности равномерного вложения в пространства с метриками Эвклида и Лоренца. Доказано, что деревья с конечным ветвлением имеют равномерное вложение в пространство с метрикой модуля метрики Минковского.

The task of embedding an infinity countable graph into continuous metric space is considered. The concept of uniform embedding having no accumulation point in a set of vertex images and having all graph edge images of a limited length is introduced. Necessary and sufficient conditions for possibility of uniform embedding into spaces with Euclid and Lorenz metrics are stated in terms of graph structure. It is proved that tree graphs with finite branching have uniform embedding into space with absolute Minkowski metric.

В работе рассматривается эффект поляризации вакуума скалярного поля на группах Ли с биинвариантной метрикой Робертсона–Уокера. При помощи метода орбит найдены выражения для вакуумных средних тензора энергии-импульса скалярного поля, которые определяются характером представления группы. Показана совместность уравнений Эйнштейна с данным тензором энергии-импульса. В качестве примера рассмотрена модель перемешанного мира.

We consider vacuum polarization of a scalar field on the Lie groups with a bi-invariant metric of Robertson-Walker type. Using the method of orbits we found expression for the vacuum expectation values of the energy-momentum tensor of the scalar field which are determined by the representation character of the group. It is shown that Einstein’s equations with the energy-momentum tensor are consistent. As an example, we consider isotropic Bianchi type IX model.

Sensor fusion is one of the important solutions for the perception problem in self-driving cars, where the main aim is to enhance the perception of the system without losing real-time performance. Therefore, it is a trade-off problem and its often observed that most models that have a high environment perception cannot perform in a real-time manner. Our article is concerned with camera and Lidar data fusion for better environment perception in self-driving cars, considering 3 main classes which are cars, cyclists and pedestrians. We fuse output from the 3D detector model that takes its input from Lidar as well as the output from the 2D detector that take its input from the camera, to give better perception output than any of them separately, ensuring that it is able to work in real-time. We addressed our problem using a 3D detector model (Complex-Yolov3) and a 2D detector model (Yolo-v3), wherein we applied the image-based fusion method that could make a fusion between Lidar and camera information with a fast and efficient late fusion technique that is discussed in detail in this article. We used the mean average precision (mAP) metric in order to evaluate our object detection model and to compare the proposed approach with them as well. At the end, we showed the results on the KITTI dataset as well as our real hardware setup, which consists of Lidar velodyne 16 and Leopard USB cameras. We used Python to develop our algorithm and then validated it on the KITTI dataset. We used ros2 along with C++ to verify the algorithm on our dataset obtained from our hardware configurations which proved that our proposed approach could give good results and work efficiently in practical situations in a real-time manner.

Sensor fusion is one of the important solutions for the perception problem in self-driving cars, where the main aim is to enhance the perception of the system without losing real-time performance. Therefore, it is a trade-off problem and its often observed that most models that have a high environment perception cannot perform in a real-time manner. Our article is concerned with camera and Lidar data fusion for better environment perception in self-driving cars, considering 3 main classes which are cars, cyclists and pedestrians. We fuse output from the 3D detector model that takes its input from Lidar as well as the output from the 2D detector that take its input from the camera, to give better perception output than any of them separately, ensuring that it is able to work in real-time. We addressed our problem using a 3D detector model (Complex-Yolov3) and a 2D detector model (Yolo-v3), wherein we applied the image-based fusion method that could make a fusion between Lidar and camera information with a fast and efficient late fusion technique that is discussed in detail in this article. We used the mean average precision (mAP) metric in order to evaluate our object detection model and to compare the proposed approach with them as well. At the end, we showed the results on the KITTI dataset as well as our real hardware setup, which consists of Lidar velodyne 16 and Leopard USB cameras. We used Python to develop our algorithm and then validated it on the KITTI dataset. We used ros2 along with C++ to verify the algorithm on our dataset obtained from our hardware configurations which proved that our proposed approach could give good results and work efficiently in practical situations in a real-time manner.

В данной работе рассматривается задача восстановления матрицы корреспонденций для наблюдений реальных корреспонденций в г. Москве. Следуя общепринятому подходу [Гасников и др., 2013], транспортная сеть рассматривается как ориентированный граф, дуги которого соответствуют участкам дороги, а вершины графа — районы, из которых выезжают / в которые въезжают участники движения. Число жителей города считается постоянным. Задача восстановления матрицы корреспонденций состоит в расчете всех корреспонденций израйона $i$ в район $j$.

Для восстановления матрицы предлагается использовать один из наиболее популярных в урбанистике способов расчета матрицы корреспонценций — энтропийная модель. В работе, в соответствии с работой [Вильсон, 1978], приводится описание эволюционного обоснования энтропийной модели, описывается основная идея перехода к решению задачи энтропийно-линейного программирования (ЭЛП) при расчете матрицы корреспонденций. Для решения полученной задачи ЭЛП предлагается перейти к двойственной задаче и решать задачу относительно двойственных переменных. В работе описывается несколько численных методов оптимизации для решения данной задачи: алгоритм Синхорна и ускоренный алгоритм Синхорна. Далее приводятся численные эксперименты для следующих вариантов функций затрат: линейная функция затрат и сумма степенной и логарифмической функции затрат. В данных функциях затраты представляют из себя некоторую комбинацию среднего времени в пути и расстояния между районами, которая зависит от параметров. Для каждого набора параметров функции затрат рассчитывается матрица корреспонденций и далее оценивается качество восстановленной матрицы относительно известной матрицы корреспонденций. Мы предполагаем, что шум в восстановленной матрице корреспонденций является гауссовским, в результате в качестве метрики качества выступает среднеквадратичное отклонение. Данная задача представляет из себя задачу невыпуклой оптимизации. В статье приводится обзор безградиенных методов оптимизации для решения невыпуклых задач. Так как число параметров функции затрат небольшое, для определения оптимальных параметров функции затрат было выбрано использовать метод перебора по сетке значений. Таким образом, для каждого набора параметров рассчитывается матрица корреспонденций и далее оценивается качество восстановленной матрицы относительно известной матрицы корреспонденций. Далее по минимальному значению невязки для каждой функции затрат определяется, для какой функции затрат и при каких значениях параметров восстановленная матрица наилучшим образом описывает реальные корреспонденции.

In this paper, we consider the problem of restoring the correspondence matrix based on the observations of real correspondences in Moscow. Following the conventional approach [Gasnikov et al., 2013], the transport network is considered as a directed graph whose edges correspond to road sections and the graph vertices correspond to areas that the traffic participants leave or enter. The number of city residents is considered constant. The problem of restoring the correspondence matrix is to calculate all the correspondence from the $i$ area to the $j$ area.

To restore the matrix, we propose to use one of the most popular methods of calculating the correspondence matrix in urban studies — the entropy model. In our work, which is based on the work [Wilson, 1978], we describe the evolutionary justification of the entropy model and the main idea of the transition to solving the problem of entropy-linear programming (ELP) in calculating the correspondence matrix. To solve the ELP problem, it is proposed to pass to the dual problem. In this paper, we describe several numerical optimization methods for solving this problem: the Sinkhorn method and the Accelerated Sinkhorn method. We provide numerical experiments for the following variants of cost functions: a linear cost function and a superposition of the power and logarithmic cost functions. In these functions, the cost is a combination of average time and distance between areas, which depends on the parameters. The correspondence matrix is calculated for multiple sets of parameters and then we calculate the quality of the restored matrix relative to the known correspondence matrix.

We assume that the noise in the restored correspondence matrix is Gaussian, as a result, we use the standard deviation as a quality metric. The article provides an overview of gradient-free optimization methods for solving non-convex problems. Since the number of parameters of the cost function is small, we use the grid search method to find the optimal parameters of the cost function. Thus, the correspondence matrix calculated for each set of parameters and then the quality of the restored matrix is evaluated relative to the known correspondence matrix. Further, according to the minimum residual value for each cost function, we determine for which cost function and at what parameter values the restored matrix best describes real correspondence.

Осуществление передачи сигналов сотовой связи — одна из ключевых задач современного мира. Для улучшения сигнала передаваемой информации необходимо чтобы сигнал не искажался при усилении мощности на базовой станции сотовой связи. Поставленную задачу можно решать самыми различными способами, однако одним из самых простых решений, которое широко используется в индустрии, является добавление нелинейных искажений, позволяющих линеаризовать работу усилителя и устранять интермодуляционные искажения в областях спектра, не используемых для передачи сигнала. В силу большой нагрузки и работы в реальном времени модель, осуществляющая данные искажения, не должна быть громоздкой и иметь большое количество адаптируемых параметров. В данной статье производится анализ современных работ по теме многокритериальной оптимизации и построения моделей для решения задачи предискажения сигнала при помощи данных методов. В статье показывается, что возможно найти структуру (сохранив производительность) и имеющую меньшее количество используемых ресурсов, быстрее, чем полный перебор по всему словарю из заданных параметров.

In this paper, we investigate different alternative ideas for the design of digital predistortion models for radiofrequency power amplifiers. When compared to the greedy search algorithm, these algorithms allow a faster identification of the model parameters combination while still performing reasonably well. For the subsequent implementation, different metrics of model costs and score results in the process of optimization enable us to achieve sparse selections of the model, which balance the model accuracy and model resources (according to the complexity of implementation). The results achieved in the process of simulations show that combinations obtained with explored algorithms show the best performance after a lower number of simulations.

В работе приведены различные модификации алгоритма Frank–Wolfe для задачи поиска равновесного распределения потоков. В качестве модели для экспериментов используется модель Бекмана. В этой статье в первую очередь уделяется внимание выбору направления базового шага алгоритма Frank–Wolfe (FW). Будут представлены алгоритмы: Conjugate Frank–Wolfe (CFW), Bi-conjugate Frank–Wolfe (BFW), Fukushima Frank–Wolfe (FFW). Каждой модификации соответствуют различные подходы к выбору этого направления. Некоторые из этих модификаций описаны в предыдущих работах авторов. В данной статье будут предложены алгоритмы N-conjugate Frank–Wolfe (NFW) и Weighted Fukushima Frank–Wolfe (WFFW). Эти алгоритмы являются некоторым идейным продолжением алгоритмов BFW и FFW. Таким образом, если первый алгоритм использовал на каждой итерации два последних направления предыдущих итераций для выбора следующего направления, сопряженного к ним, то предложенный алгоритм NFW использует $N$ предыдущих направлений. В случае же Fukushima Frank –Wolfe в качестве следующего направления берется среднее от нескольких предыдущих направлений. Соответственно этому алгоритму предложена модификация WFFW, использующая экспоненциальное сглаживание по предыдущим направлениям. Для сравнительного анализа были проведены эксперименты с различными модификациями на нескольких наборах данных, представляющих городские структуры и взятых из общедоступных источников. За метрику качества была взята величина относительного зазора. Результаты экспериментов показали преимущество алгоритмов, использующих предыдущие направления для выбора шага, перед классическим алгоритмом Frank–Wolfe. Кроме того, было выявлено улучшение эффективности при использовании более двух сопряженных направлений. Например, на многих датасетах модификация 3-conjugate FW сходилась наилучшим образом. Кроме того, предложенная модификация WFFW зачастую обгоняла FFW и CFW, хотя и проигрывала модификациям NFW.

The paper presents various modifications of the Frank–Wolfe algorithm in the equilibrium traffic assignment problem. The Beckman model is used as a model for experiments. In this article, first of all, attention is paid to the choice of the direction of the basic step of the Frank–Wolfe algorithm. Algorithms will be presented: Conjugate Frank–Wolfe (CFW), Bi-conjugate Frank–Wolfe (BFW), Fukushima Frank –Wolfe (FFW). Each modification corresponds to different approaches to the choice of this direction. Some of these modifications are described in previous works of the authors. In this article, following algorithms will be proposed: N-conjugate Frank–Wolfe (NFW), Weighted Fukushima Frank–Wolfe (WFFW). These algorithms are some ideological continuation of the BFW and FFW algorithms. Thus, if the first algorithm used at each iteration the last two directions of the previous iterations to select the next direction conjugate to them, then the proposed algorithm NFW is using more than $N$ previous directions. In the case of Fukushima Frank–Wolfe, the average of several previous directions is taken as the next direction. According to this algorithm, a modification WFFW is proposed, which uses a exponential smoothing from previous directions. For comparative analysis, experiments with various modifications were carried out on several data sets representing urban structures and taken from publicly available sources. The relative gap value was taken as the quality metric. The experimental results showed the advantage of algorithms using the previous directions for step selection over the classic Frank–Wolfe algorithm. In addition, an improvement in efficiency was revealed when using more than two conjugate directions. For example, on various datasets, the modification 3FW showed the best convergence. In addition, the proposed modification WFFW often overtook FFW and CFW, although performed worse than NFW.

В работе рассматриваются статистические оценки порога и мощности перколяционных кластеров на квадратных решетках. Порог перколяции p_c и мощность перколяционных кластеров P_∞ на квадратной решетке с (1,π)-окрестностью зависят не только от размерности решетки, но от показателя Минковского π. Для оценки мощности перколяционных кластеров P_∞ предложен новый метод, основанный на усреднении относительных частот целевого подмножества узлов решетки. Реализация предложенного метода основана на библиотеке SPSL, выпущенной под лицензией GNU GPL-3 с использованием свободного языка программирования R.

In this paper we consider statistical estimates of threshold and strength of percolation clusters on square lattices. The percolation threshold p_c and the strength of percolation clusters P_∞ for a square lattice with (1,π)-neighborhood depends not only on the lattice dimension, but also on the Minkowski exponent d. To estimate the strength of percolation clusters P_∞ proposed a new method of averaging the relative frequencies of the target subset of lattice sites. The implementation of this method is based on the SPSL package, released under GNU GPL-3 using the free programming language R.

Оценка надежности программного обеспечения (ПО) — важная составляющая процесса разработки современного программного обеспечения. Многие исследования направлены на улучшение моделей для измерения и прогнозирования надежности программных продуктов. Однако мало внимания уделяется подходам к сопоставлению существующих систем с точки зрения надежности ПО. Несмотря на огромное значение для практики (и для управления разработкой ПО), полной и проверенной методологии сравнения не существует. В этой статье мы предлагаем методологию сравнения надежности программного обеспечения, в которой широко применяются модели роста надежности программного обеспечения. Методология была оценена на примере трех мобильных операционных систем с открытым исходным кодом: Sailfish, Tizen, CyanogenMod.

Побочным продуктом исследования является сравнение трех мобильных операционных систем с открытым исходным кодом. Целью данного исследования является определение того, какая ОС является более надежной. Для этого были определены 3 вопроса и 8 метрик. С учетом сравнения этих метрик оказалось, что Sailfish в большинстве случаев является самой эффективной операционной системой. Напротив, Tizen показывает лучшее в 3 случаях из 8, но оказывается хуже других систем только в одном случае из 8.

Evaluation of software reliability is an important part of the process of developing modern software. Many studies are aimed at improving models for measuring and predicting the reliability of software products. However, little attention is paid to approaches to comparing existing systems in terms of software reliability. Despite the enormous importance for practice (and for managing software development), a complete and proven comparison methodology does not exist. In this article, we propose a software reliability comparison methodology in which software reliability growth models are widely used. The proposed methodology has the following features: it provides certain level of flexibility and abstraction while keeping objectivity, i.e. providing measurable comparison criteria. Also, given the comparison methodology with a set of SRGMs and evaluation criteria it becomes much easier to disseminate information about reliability of wide range of software systems. The methodology was evaluated on the example of three mobile operating systems with open source: Sailfish, Tizen, CyanogenMod.

A byproduct of our study is a comparison of the three analyzed Open Source mobile operating systems. The goal of this research is to determine which OS is stronger in terms of reliability. To this end we have performed a GQM analysis and we have identified 3 questions and 8 metrics. Considering the comparison of metrics, it appears that Sailfish is in most case the best performing OS. However, it is also the OS that performs the worst in most cases. On the contrary, Tizen scores the best in 3 cases out of 8, but the worst only in one case out of 8.

Решение задачи лазерной спектрометрии позволяет определять размеры частиц в растворе по спектру интенсивности рассеянного света. В результате эксперимента методом динамического рассеяния света получается кривая интенсивности рассеяния, по которой необходимо определить, частицы каких размеров представлены в растворе. Экспериментально полученный спектр интенсивности сравнивается с теоретически ожидаемым спектром, который является кривой Лоренца. Основная задача сводится к тому, чтобы на основании этих данных найти относительные концентрации частиц каждого сорта, представленных в растворе. В статье представлен способ построения и использования нейронной сети, обученной на синтетических данных, для определения размера частиц в растворе в диапазоне 1–500 нм. Нейронная сеть имеет полносвязный слой из 60 нейронов с функцией активации RELU на выходе, слой из 45 нейронов и с аналогичной функцией активации, слой dropout и 2 слоя с количеством нейронов 15 и 1 (выход сети). В статье описано, как сеть обучалась и тестировалась на синтетических и экспериментальных данных. На синтетических данных метрика «среднеквадратичное отклонение» (rmse) дала значение 1.3157 нм. Экспериментальные данные были получены для размеров частиц 200 нм, 400 нм и раствора с представителями обоих размеров. Сравниваются результаты работы нейронной сети и классических линейных методов, основанных на применении различных регуляризаций за счет введения дополнительных параметров и применяемых для определения размера частиц. К недостаткам классических методов можно отнести трудность автоматического определения степени регуляризации: слишком сильная регуляризация приводит к тому, что кривые распределения частиц по размерам сильно сглаживаются, а слабая регуляризация дает осциллирующие кривые и низкую надежность результатов. В работе показано, что нейронная сеть дает хорошее предсказание для частиц с большим размером. Для малых размеров предсказание хуже, но ошибка быстро уменьшается с увеличением размера.

Solution of Dynamic Light Scattering problem makes it possible to determine particle size distribution (PSD) from the spectrum of the intensity of scattered light. As a result of experiment, an intensity curve is obtained. The experimentally obtained spectrum of intensity is compared with the theoretically expected spectrum, which is the Lorentzian line. The main task is to determine on the basis of these data the relative concentrations of particles of each class presented in the solution. The article presents a method for constructing and using a neural network trained on synthetic data to determine PSD in a solution in the range of 1–500 nm. The neural network has a fully connected layer of 60 neurons with the RELU activation function at the output, a layer of 45 neurons and the same activation function, a dropout layer and 2 layers with 15 and 1 neurons (network output). The article describes how the network has been trained and tested on synthetic and experimental data. On the synthetic data, the standard deviation metric (rmse) gave a value of 1.3157 nm. Experimental data were obtained for particle sizes of 200 nm, 400 nm and a solution with representatives of both sizes. The results of the neural network and the classical linear methods are compared. The disadvantages of the classical methods are that it is difficult to determine the degree of regularization: too much regularization leads to the particle size distribution curves are much smoothed out, and weak regularization gives oscillating curves and low reliability of the results. The paper shows that the neural network gives a good prediction for particles with a large size. For small sizes, the prediction is worse, but the error quickly decreases as the particle size increases.

При распознавании рабочих на изображениях строительной площадки, получаемых с камер наблюдения, типичной является ситуация, при которой объекты детекции имеют сильно различающийся пространственный масштаб относительно друг друга и других объектов. Повышение точности детекции мелких объектов может быть обеспечено путем использования Feature-Fused модификации детектора SSD (Single Shot Detector). Вместе с применением на инференсе нарезки изображения с перекрытием такая модель хорошо справляется с детекцией мелких объектов. Однако при практическом использовании данного подхода требуется ручная настройка параметров нарезки. При этом снижается точность детекции объектов на сценах, отличающихся от сцен, использованных при обучении, а также крупных объектов. В данной работе предложен алгоритм автоматического выбора оптимальных параметров нарезки изображения в зависимости от соотношений характерных геометрических размеров объектов на изображении. Нами разработан двухпроходной вариант детектора Feature-Fused SSD для автоматического определения параметров нарезки изображения. На первом проходе применяется усеченная версия детектора, позволяющая определять характерные размеры объектов интереса. На втором проходе осуществляется финальная детекция объектов с параметрами нарезки, выбранными после первого прохода. Был собран датасет с изображениями рабочих на строительной площадке. Датасет включает крупные, мелкие и разноплановые изображения рабочих. Для сравнения результатов детекции для однопроходного алгоритма без разбиения входного изображения, однопроходного алгоритма с равномерным разбиением и двухпроходного алгоритма с подбором оптимального разбиения рассматривались тесты по детекции отдельно крупных объектов, очень мелких объектов, с высокой плотностью объектов как на переднем, так и на заднем плане, только на заднем плане. В диапазоне рассмотренных нами случаев наш подход превосходит подходы, взятые в сравнение, позволяет хорошо бороться с проблемой двойных детекций и демонстрирует качество 0,82–0,91 по метрике mAP (mean Average Precision).

When recognizing workers on images of a construction site obtained from surveillance cameras, a situation is typical in which the objects of detection have a very different spatial scale relative to each other and other objects. An increase in the accuracy of detection of small objects can be achieved by using the Feature-Fused modification of the SSD detector. Together with the use of overlapping image slicing on the inference, this model copes well with the detection of small objects. However, the practical use of this approach requires manual adjustment of the slicing parameters. This reduces the accuracy of object detection on scenes that differ from the scenes used in training, as well as large objects. In this paper, we propose an algorithm for automatic selection of image slicing parameters depending on the ratio of the characteristic geometric dimensions of objects in the image. We have developed a two-pass version of the Feature-Fused SSD detector for automatic determination of optimal image slicing parameters. On the first pass, a fast truncated version of the detector is used, which makes it possible to determine the characteristic sizes of objects of interest. On the second pass, the final detection of objects with slicing parameters selected after the first pass is performed. A dataset was collected with images of workers on a construction site. The dataset includes large, small and diverse images of workers. To compare the detection results for a one-pass algorithm without splitting the input image, a one-pass algorithm with uniform splitting, and a two-pass algorithm with the selection of the optimal splitting, we considered tests for the detection of separately large objects, very small objects, with a high density of objects both in the foreground and in the background, only in the background. In the range of cases we have considered, our approach is superior to the approaches taken in comparison, allows us to deal well with the problem of double detections and demonstrates a quality of 0.82–0.91 according to the mAP (mean Average Precision) metric.