Search

The mutual identification of spatial objects is a fundamental issue when updating geographic data with other data sets. Representations of spatial objects in different sources may not have the same identifiers, which would unambiguously assign them to each other. Intersections of spatial objects can be used for this purpose, but this does not allow for the detection of possible changes and their quantification. The aim of this paper is to propose a simple, applicable procedure for calculating the shape similarity measure, which should be able to efficiently identify different representations of spatial objects in two data sources, even though they may be changed or generalised. The main result is the aggregated index of shape similarity and instructions for its calculation and implementation. The shape similarity index is based on the calculation of the set similarity, the distance of the boundaries, and the differences in the area, perimeter, and number of the vertices of areal spatial objects. In the case study, the footprints of the building complexes in Dúbravka (part of the city of Bratislava, the capital of Slovakia) are compared using data from OpenStreetMap and INSPIRE (Infrastructure for Spatial Information in Europe) Buildings. A contribution to the quality check of the OpenStreetMap data is then a secondary result. The proposed method can be effectively used in the semi-automatic integration of heterogeneous data sources, updating the data source with other spatial data, or in their quality control. [ABSTRACT FROM AUTHOR]

We instrument Group Diagrams (GDs) to reduce clutter in sets of eye-tracking scanpaths. Group Diagrams consist of trajectory subsets that cover, or represent, the whole set of trajectories with respect to some distance measure and an adjustable distance threshold. The original GDs allow for an application of various distance measures. We implement the GD framework and evaluate it on scanpaths that were collected by a former user study on public transit maps. We find that the Fréchet distance is the most appropriate measure to get meaningful results, yet it is flexible enough to cover outliers. We discuss several implementation-specific challenges and improve the scalability of the algorithm. To evaluate our results, we conducted a qualitative study with a group of eye-tracking experts. Finally, we note that our enhancements are also beneficial within the original problem setting, suggesting that our approach might be applicable to various types of input data. Eye tracking on a public transit map of Warsaw. Input scanpaths (left), and simplified Group Diagram (right). [ABSTRACT FROM AUTHOR]

Lane cracks are one of the biggest threats to pavement conditions. The automatic detection of lane cracks can not only assist the evaluation of road quality and quantity but can also be used to develop the best crack repair plan, so as to keep the road level and ensure driving safety. Although cracks can be extracted from pavement images because the gray intensity of crack pixels is lower than the background gray intensity, it is still a challenge to extract continuous and complete cracks from the three-lane images with complex texture, high noise, and uneven illumination. Different from threshold segmentation and edge detection, this study designed a crack detection algorithm with dual positioning. An image-enhancement method based on crack saliency is proposed for the first time. Based on Bayesian probability, the saliency of each pixel judged as a crack is calculated. Then, the Fréchet distance improvement triangle relationship is introduced to determine whether the key point extracted is the fracture endpoint and whether the fast-moving method should be terminated. In addition, a complete remote-sensing process was developed to calculate the length and width of cracks by inverting the squint images collected by mobile phones. A large number of images with different types, noise, illumination, and interference conditions were tested. The average crack extraction accuracy of 89.3%, recall rate of 87.1%, and F1 value of 88.2% showed that the method could detect cracks in pavement well. [ABSTRACT FROM AUTHOR]

The research community considers handwritten word recognition (HWR) as an open research problem to date. The reasons behind this are variations in intra-/interpersonal writing style, overlapping and/or touching characters in a word, degraded scanned document images, etc. Two major approaches, namely holistic and analytical, are followed by the researchers while designing an HWR system. In this work, we have followed the holistic approach as it works well on limited and pre-defined lexicon as compared to the analytical approach. As observed in the literature related to handwritten word recognition, irrespective of the approaches, researchers generally extract various local features from hypothetically partitioned segments of a word image while dealing with the said problem. However, no such work has been found which has considered inter-segment similarity that might carry some distinct information about different patterns (here, word segments). To this end, in the present work, we have used Hausdorff and Fréchet distances to quantize the similarity among all possible word segments taking two at a time. Along with this, conventional chain code histogram (a shape-based feature descriptor) and modified negative refraction-based shape transformation features have been used. Finally, a majority voting schema is used to combine outputs from six different classifiers. The model has been evaluated on two standard databases, namely IAM and IFN/ENIT, and the results obtained are promising in comparison with state-of-the-art holistic word recognition methods. Moreover, a performance comparison of the present method with some deep learning models confirms the usefulness of the proposed method. [ABSTRACT FROM AUTHOR]

Breast cancer is among the most common cancers diagnosed in women globally. To help the breast cancer diagnosis, an important step is to accurately segment the breast lesion. To support clinicians in this important step, we analyze the performance of a semi-automated segmentation method based on the Local Graph Cut technique in the Image Segmenter application. Local graph cuts algorithm has the ability to segment more complicated shape by converting the image into a graph representation. It employs seed points set by the user and a cost function. The user identifies certain pixels as foreground and background. The region properties are identified from these pixels and they allow to specify the probability of a pixel belonging to the background or foreground. The graph cut formulation assigns each pixel to a node in the graph and incorrectly segmented pixels are re-assigned until the desired segmentation is completed. To evaluate the segmentation results, the Dice similarity coefficient and Fréchet distance were calculated between the ground truth images and the segmented images. Results show a Dice score of 0.7754 for malignant lesions and 0.8842 for benign lesions. The average Fréchet distance values were 303.28 for malignant and 290.80 for benign lesions, respectively. The experimental results show that the method achieves the best performance and gets the higher Dice score and Fréchet distance for breast benign lesions against malignant lesions. [ABSTRACT FROM AUTHOR]

In the (1 + ε , r) -approximate near-neighbor problem for curves (ANNC) under some similarity measure δ , the goal is to construct a data structure for a given set C of curves that supports approximate near-neighbor queries: Given a query curve Q, if there exists a curve C ∈ C such that δ (Q , C) ≤ r , then return a curve C ′ ∈ C with δ (Q , C ′) ≤ (1 + ε) r . There exists an efficient reduction from the (1 + ε) -approximate nearest-neighbor problem to ANNC, where in the former problem the answer to a query is a curve C ∈ C with δ (Q , C) ≤ (1 + ε) · δ (Q , C ∗) , where C ∗ is the curve of C most similar to Q. Given a set C of n curves, each consisting of m points in d dimensions, we construct a data structure for ANNC that uses n · O (1 ε) md storage space and has O(md) query time (for a query curve of length m), where the similarity measure between two curves is their discrete Fréchet or dynamic time warping distance. Our method is simple to implement, deterministic, and results in an exponential improvement in both query time and storage space compared to all previous bounds. Further, we also consider the asymmetric version of ANNC, where the length of the query curves is k ≪ m , and obtain essentially the same storage and query bounds as above, except that m is replaced by k. Finally, we apply our method to a version of approximate range counting for curves and achieve similar bounds. [ABSTRACT FROM AUTHOR]

Most of the current trajectory privacy protection methods does not consider the shape similarity of trajectory sufficiently, and it is easy to ignore the timing correlation of each point on the trajectory, which results in the low availability of the generated interference tracks. To solve these problems, a differential privacy trajectory protection mechanism based on density clustering algorithm was proposed. Firstly, density based spatial clustering of application with noise (DBSCAN) algorithm was used for clustering analysis of data to reduce the influence of noise points in data set on clustering effect. Secondly, the position transition probability matrix was generated according to the time sequence relationship of user's activity locus points, and the differential privacy method was used to ensure that the generated interference locus points have similar position transfer probability to the real locus points. Finally, considering the influence of differential privacy budget and Fréchet distance on trajectory similarity to select the location interference point. The simulation results show that the proposed scheme has advantages in efficiency obviously, and the generated interference trajectory has higher shape similarity compared with the real position trajectory. [ABSTRACT FROM AUTHOR]

Isomanifolds are the generalization of isosurfaces to arbitrary dimension and codimension, i.e. manifolds defined as the zero set of some multivariate multivalued smooth function f : R d → R d - n . A natural (and efficient) way to approximate an isomanifold is to consider its piecewise-linear (PL) approximation based on a triangulation T of the ambient space R d . In this paper, we give conditions under which the PL approximation of an isomanifold is topologically equivalent to the isomanifold. The conditions are easy to satisfy in the sense that they can always be met by taking a sufficiently fine and thick triangulation T . This contrasts with previous results on the triangulation of manifolds where, in arbitrary dimensions, delicate perturbations are needed to guarantee topological correctness, which leads to strong limitations in practice. We further give a bound on the Fréchet distance between the original isomanifold and its PL approximation. Finally, we show analogous results for the PL approximation of an isomanifold with boundary. [ABSTRACT FROM AUTHOR]

We show that the closure of the set of orientation-preserving automorphisms of the unit square is computable in the bit-model of real computation. As an application we obtain a conditional result on the computability of the Fréchet-distance of continuous surfaces. [ABSTRACT FROM AUTHOR]

A novel biaxial finite-element (FE) model is proposed and validated by a total of 32 reinforced concrete (RC) shear walls with aspect ratio below 1.5. First, a biaxial concrete model package, which was previously developed in ABAQUS software for RC panel tests, is adopted to evaluate its accuracy of simulating RC shear walls. The FE modeling scheme, the biaxial FE model of concrete before and after initial cracking, and the uniaxial FE model of concrete are illustrated. The developed model considers the following five significant features including the concrete compressive softening, tension softening, concrete shear softening, pinching effect, and strength reduction because of lateral cracking. Second, the traditional rebar model without buckling and the longitudinal rebar model considering buckling are also illustrated. Third, the discrete Fréchet distance is adopted to quantify the relative error between FE simulation results and test results. Subsequently, the constitutive model in ABAQUS simulates a total of 32 RC shear walls under axial and lateral forces. The simulated RC shear walls cover a wide range of parameters, including aspect ratio, rebar orientation, reinforcement, and section shape. The FE simulation results are compared with test results including the force versus lateral deformation curves, load-shear displacement curves, and failure modes. According to the comparison, the developed constitutive model shows high accuracy for RC shear walls with aspect ratio below 1.5, including the replication of pinching effect and residual capacity. The developed model overestimated the initial stiffness of some test specimens, which may be attributed to the omission of concrete cracking induced by shrinkage. In general, the overall accuracy of the developed constitutive model is validated. [ABSTRACT FROM AUTHOR]

The Vapnik–Chervonenkis dimension provides a notion of complexity for systems of sets. If the VC dimension is small, then knowing this can drastically simplify fundamental computational tasks such as classification, range counting, and density estimation through the use of sampling bounds. We analyze set systems where the ground set X is a set of polygonal curves in R d and the sets R are metric balls defined by curve similarity metrics, such as the Fréchet distance and the Hausdorff distance, as well as their discrete counterparts. We derive upper and lower bounds on the VC dimension that imply useful sampling bounds in the setting that the number of curves is large, but the complexity of the individual curves is small. Our upper and lower bounds are either near-quadratic or near-linear in the complexity of the curves that define the ranges and they are logarithmic in the complexity of the curves that define the ground set. [ABSTRACT FROM AUTHOR]

The Fréchet distance is a popular similarity measure between curves. For some applications, it is desirable to match the curves under translation before computing the Fréchet distance between them. This variant is called the Translation Invariant Fréchet distance, and algorithms to compute it are well studied. The query version, finding an optimal placement in the plane for a query segment where the Fréchet distance becomes minimized, is much less well understood. We study Translation Invariant Fréchet distance queries in a restricted setting of horizontal query segments. More specifically, we preprocess a trajectory in O (n 2 log 2 n) time and O (n 3 / 2) space, such that for any subtrajectory and any horizontal query segment we can compute their Translation Invariant Fréchet distance in O (polylog n) time. We hope this will be a step towards answering Translation Invariant Fréchet queries between arbitrary trajectories. [ABSTRACT FROM AUTHOR]

The prevalence of asthma has been growing among working age people over the last decades. In this study, we examine the development of Work Ability Score (WAS) among middle-aged asthmatics in a longitudinal setting, in order to find risk factors for poor development. We followed the development of WAS trends during 10 years in a cohort of 529 middle-aged asthmatics, who were active in working life. Follow-up questionnaires were mailed in years 1, 2, 4, 6, 8, and 10. To study the development of WAS over time, we computed the discrete Frechet distance, which describes the similarity between the shapes of WAS curves. Sixty-eight percent of the patients' WAS remained good or excellent throughout the follow-up period, while 24% of the patients WAS trend remained moderate. However, in 8%, the WAS was poor already in baseline and decreased further throughout the study. Using logistic regression, the moderate/poor development was associated significantly with high body mass index (BMI), pack years, adult onset asthma, physically strenuous work, number of co-morbidities, especially in psychiatric conditions, hypertension, and gastroesophageal reflux disease(GERD). When the model was adjusted for age and gender, adulthood onset of asthma and pack years lost their significance. Based on medication (high dose of inhaled corticosteroids (ICS) and second controller in use), 8% of the patients had severe asthma. In the great majority of middle-aged asthma patients WAS remained stable throughout the follow-up period. However, 8% of the patients, who had more severe asthma and multiple co-morbidities, showed significantly poorer outcomes. [ABSTRACT FROM AUTHOR]

The string matching problem on a node-labeled graph G = (V , E) asks whether a given pattern string P equals the concatenation of node labels of some path in G. This is a basic primitive in various problems in bioinformatics, graph databases, or networks, and it was recently proven that solving it in time O (| E | 1 − ϵ | P |) or O (| E | | P | 1 − ϵ) is hard under OVH , the Orthogonal Vectors Hypothesis, and thus under SETH , the Strong Exponential Time Hypothesis (Equi et al., 2019 [11]). We consider its indexed version, where the graph is indexed to support string queries. We show that, under OVH , no polynomial-time index of the graph performed in time O (| E | α) can support querying P in time O (| P | + | E | δ | P | β) , with either δ < 1 or β < 1. We present our techniques as a general framework, introducing the notion of linear independent-components (lic) reduction , from which we derive our result. This allows us to also translate the quadratic conditional lower bound of Backurs and Indyk (2015) [48] for the problem of matching a query string inside a text, under edit distance, into an analogous tight quadratic lower bound for its indexed version. This improves the recent result of Cohen-Addad, Feuilloley and Starikovskaya (2019) [49] , with a slightly different boundary condition. We also apply our technique to obtain the first quadratic indexing lower bounds for Fréchet distance and rooted unlabeled subtree-isomorphism queries. [ABSTRACT FROM AUTHOR]

Given the trajectories of one or several moving groups, we propose a new framework, the group diagram (GD) for representing these. Specifically, we seek a minimal GD as a concise representation of the groups maintaining the spatio-temporal structure of the groups' movement. A GD is specified by three input values, namely a distance threshold, a similarity measure and a minimality criterion. For several variants of the GD, we give a comprehensive analysis of their computational complexity and present efficient approximation algorithms for their computation. Furthermore, we experimentally evaluate our algorithms on GPS data of migrating geese. Applying the proposed methods on these data sets reveals how the GD concisely represents the movement of the groups. This representation can be used for further analysis and for the formulation of new hypotheses for further ecological research, such as differences in movement patterns of groups on different surfaces or the shift of migration routes over several years. We use different similarity measures to summarize the migration routes of (i) a goose family for one migration period and to summarize (ii) the migration routes of one individual for several migration periods or (iii) the migration routes of several independent individuals for one migration period. [ABSTRACT FROM AUTHOR]

Understanding deficits in motor control through the analysis of pedaling biomechanics plays a key role in the treatment of stroke patients. A thorough study of the impact of different exercise patterns and workloads on the change between pre- and post-treatment movement patterns in the patients is therefore of utmost importance to the clinicians. The objective of this study was to analyze the difference between pre- and post-treatment pedaling torques when the patients are subject to different exercise groups with varying workloads. The effects of affected vs unaffected side along with the covariates age and BMI have also been accounted for in this work. Two different three-way ANOVA-based approaches have been implemented here. In the first approach, a random projection-based ANOVA technique has been performed treating the pedaling torques as functional response, whereas the second approach utilizes distance measures to summarize the difference between pre- and post-treatment torques and perform nonparametric tests on it. Bayesian bootstrap has been used here to perform tests on the median distance. A group of stroke patients have been studied in the Cleveland Clinic categorizing them into different exercise groups and workload patterns. The data obtained have been analyzed with the aforementioned techniques, and the results have been reported here. These techniques turn out to be promising and will help clinicians recommend personalized treatment to stroke patients for optimal results. [ABSTRACT FROM AUTHOR]

Map matching is the process which work for location measurement and also find out appropriate route for smooth traveling on the road network, but map matching accuracy fully depends on GPS trajectory data and electronic map of the road network. Unfortunately, GPS data is not accurate because, it's through weak GPS signaling and low quality GPS devices. So, it is difficult to calculate accurate location of movements.This work provides, a map mapping algorithm for simplifying appropriate path, including curves on road network and also, we proposed Frechet distance computing algorithm with road Preliminaries for network simplification. [ABSTRACT FROM AUTHOR]

The minimum backward Fréchet distance (MBFD) problem is a natural optimization problem for the weak Fréchet distance, a variant of the well-known Fréchet distance. In this problem, a threshold ε and two polygonal curves, T 1 and T 2 , are given. The objective is to find a pair of walks on T 1 and T 2 , which minimizes the union of the portions of backward movements (backtracking) while maintaining, at any time, a distance between the moving entities of at most ε. In this paper, we generalize this model to capture scenarios when the cost of backtracking on the input polygonal curves is not homogeneous. More specifically, each edge of T 1 and T 2 has an associated non-negative weight. The cost of backtracking on an edge is the Euclidean length of backward movement on that edge multiplied by the corresponding weight. The objective is to find a pair of walks that minimizes the sum of the costs on the edges of the curves, while guaranteeing that the weak traversal of the curves maintains a weak Fréchet distance of at most ε. We propose two exact algorithms, a simple algorithm with O (n 4) time and space complexities and an improved algorithm whose time and space complexities are O (n 2 log 3 / 2 ⁡ n) , where n is the maximum number of the edges of T 1 and T 2. A solution to weighted MBFD also implies a solution to the more general optimization problem in which both backward and forward movements have associated costs. [ABSTRACT FROM AUTHOR]

An accurate tensor estimation function is a guarantee for acquiring a reliable underground electrical structure model. The past studies regarding transmission functions aim at obtaining smooth and continuous sounding curves through the time domain by data screening means such as least square, robust and remote reference processing methods as well as digital filtering techniques such as wavelet denoising, empirical mode decomposition and Hilbert–Huang transform denoising. As SNRs in different field measurement sites are different, if different data processing algorithms like single-site processing, remote reference processing, magnetic field correlation-based remote reference processing and magnetic channel sharing are used for data processing at the same measuring site, 3N-2 groups of sounding curves with different qualities will be obtained. Manual screening method has been mainly used in the past for screening of the abovementioned 3N-2 groups of sounding curves. If the quantity of sounding site is large, this manual screening method is of low efficiency without quantitative screening indexes. In this paper, discrete Fréchet distance is mainly utilized to carry out quantitative screening of 3N-2 groups of sounding curves processed through the abovementioned four processing methods in order to obtain smooth, continuous and reliable sounding curves, thus avoiding subjectivity and low efficiency problems in the past manual screening. A quantitative sorting of all kinds of data processing results can be conducted, and the optimal sounding curve is finally picked out for data inversion. The above sounding curve selection result has improved processing accuracy of magnetotelluric data. [ABSTRACT FROM AUTHOR]

Keeping the digital road maps up-to-date is of critical importance, because the quality of many road-dependent services relies on it, but traditional measurement methods are still time-consuming and expensive. With the GPS technology and wireless communication technology maturing, the positioning data from floating car become a new data source for updating road maps. The paper presents a novel incremental clustering algorithm for automatically extracting the topology of the road network employing the floating car data. A trajectory is selected as a road Link and then the remaining trajectories are added in turn until all tracks are processed. Further, the algorithm determines whether to merge the trajectory or divide it into a new Link by judging the relations of the space position between the newly added trajectory and the existing Link. A partial curve matching method based on Fréchet distance is employed to measure the partial similarity between a Trajectory and a Link and the time complexity of the proposed algorithm is reduced. Experiments show that the algorithm can quickly extract the geometric shape and topology of the road network with lightweight floating car data. [ABSTRACT FROM AUTHOR]

Knowing the number of clusters a priori is one of the most challenging aspects of unsupervised learning. Clustering Internal Validity Indices (CIVIs) evaluate partitions in unsupervised algorithms based on metrics like compactness, separation, and density. However, specialized CIVIs for specific applications have been designed, and there is no general CIVI that works in all scenarios. The absence of CIVIs based on crisp uncertainty metrics is especially critical in decision-making processes that involve ambiguity, non-convex distributions, outliers, and overlapping data. To address this problem, we propose a novel Uncertainty Fréchet (UF) CIVI that assesses the certainty of a well-defined partition. UF leverages uncertainty fingerprints based on Type-2 fuzzy Gaussian Mixture Models (T2FGMM) and the Fréchet distance between clusters to introduce a metric that evaluates partition quality. We integrate UF into a merging methodology that combines similar clusters within a partition, allowing us to determine the number of clusters without the need to run the clustering algorithms iteratively as other CIVIs require. We undertake a comprehensive evaluation of our proposal on 5,250 convex, 36 non-convex synthetic datasets, and five benchmark real datasets. In addition, we apply UF in a real-world scenario that involves high uncertainty: Passive Acoustic Monitoring (PAM) of ecosystems, which aims to study ecological transformations through acoustic recordings. The results show that UF exhibits notable performance in synthetic and real-world scenarios, obtaining an Adjusted Mutual Information (AMI) score higher than 0.88 for normal, uniform, gamma, and triangular distribution datasets. In the PAM application, UF identifies the transformation of ecosystems through sound using clustering algorithms and UF, achieving an F1 score of 0.84. Therefore, results show that the UF index is a suitable tool for researchers and practitioners working with highly uncertain data. • Evaluating Clustering Quality in Unsupervised Learning. • Quantifying uncertainty in clustering validation processes. • Clustering validation Indices applied to Ecoacoustics. • Convex and no-convex clustering validation. [ABSTRACT FROM AUTHOR]

Abstract Single particle breakage characterisation at fine sizes for use in mill modelling has been addressed by only a few researchers and is not utilised in engineering design. This is mainly due to the challenge of accurately imparting a range of impact energies to sub-millimetre particles and then measuring the progeny size distribution for the tiny resultant mass. In order to fill this gap, a dispersed monolayer multi-particle breakage method was applied with a mini JK Drop weight tester in this work to extend the single particle breakage test from 16 mm down to 425 μm, covering a specific energy (Ecs) range of 0.1–2.5 kWh/t to provide a wide range of test conditions. A challenge that had to be addressed was switching from single particle to dispersed mono-layer due to the physical constraints of drop-height and drop mass in maintaining accuracy in input energy over the orders of magnitude required to apply the required specific range of energy input. As only a limited size range could be subjected to both single particle and mono-layer bed breakage, it was necessary to establish if the two testing techniques provide the same breakage results. A novel application of the Fréchet distance was successfully applied to quantitatively evaluate the discrepancy of progeny size distribution between single particle breakage and monolayer multiple particle breakage. Extrapolation of an empirical Fréchet distance model indicated that the application of dispersed mono-layer breakage below 2 mm provides an acceptable comparison with the single particle breakage applied to coarser sizes, thus facilitating the fitting of a single appearance function across this wide range of sizes and applied breakage energies. Graphical abstract Unlabelled Image Highlights • Breakage tests with both single particle and monolayer multi-particles were conducted. • The Fréchet distance is applied to evaluate the difference between the two test methods. • Multi-particle breakage is equivalent to single particle breakage for <2 mm particles • A potential simpler and viable fine breakage characterisation technique is developed. [ABSTRACT FROM AUTHOR]

Abstract The Fréchet distance is a metric to compare two curves, which is based on monotone matchings between these curves. We call a matching that results in the Fréchet distance a Fréchet matching. There are often many different Fréchet matchings and not all of these capture the similarity between the curves well. We propose to restrict the set of Fréchet matchings to "natural" matchings and to this end introduce locally correct Fréchet matchings. We prove that at least one such matching exists for two polygonal curves and give an O (N 3 log ⁡ N) algorithm to compute it, where N is the number of edges in both curves. We also present an O (N 2) algorithm to compute a locally correct discrete Fréchet matching. [ABSTRACT FROM AUTHOR]

Aiming at the problem of elevator braking failure caused by the uneven wear of the elevator brake, the reasons for the uneven wear and the influence of the elevator brake were summarized. The internal energy change of the elevator brake system was analyzed and studied.The change of the heat flux on the surface of the elevator brake was obtained, and a kind of elevator brake based on the thermal image analysis was put forward. The uneven wear test method was used to collect the infrared thermal image of the brake skin on the elevator brake, the mixed noise in the collection process was filtered out, the isotherm feature vector and the gate edge feature vector was extracted, and the uneven wear degree of the elevator brake skin was characterized by calculating the frying distance between the characteristic vector of the isothermal line and the edge eigenvector of the elevator brake. The results indicate that this method can detect the uneven wear of the elevator brake, and figure out the problem that the elevator can not detect the uneven wear of the brake under the condition of undisintegration. [ABSTRACT FROM AUTHOR]

Frèchet distance is an important geometric measure that captures the distance between two curves or more generally point sets. In this paper, we consider a natural variant of Fréchet distance problem with multiple choice, provide an approximation algorithm and address its parameterized and kernelization complexity. A multiple choice problem consists of a set of color classes Q={Q1,Q2,…,Qn}, where each class Qi consists of a pair of points Qi={qi,qi¯}. We call a subset A⊂{qi,qi¯:1≤i≤n} conflict-free if A contains at most one point from each color class. The standard objective in multiple choice problem is to select a conflict-free subset that optimizes a given function. Given a line-segment ℓ and a set Q of a pair of points in R2, our objective is to find a conflict-free subset that minimizes the Fréchet distance between ℓ and the point set, where the minimum is taken over all possible conflict-free subsets. We first show that this problem is NP-hard, and provide a 3-approximation algorithm. Then we develop a simple randomized FPT algorithm for the problem when parametrized by the solution size, which is later derandomized using universal family of sets. We believe that our derandomization technique can be of independent interest, and can be used to solve other parameterized multiple choice problems. The randomized algorithm runs in O(2knlog2n) time, and the derandomized deterministic algorithm runs in 2kkO(logk)nlog2n time, where k, the parameter, is the number of elements in the conflict-free subset solution. Finally we present a simple branching algorithm for the problem running in O(2knlogn) time. We also show that the problem does not have a polynomial sized kernel under standard complexity theoretic assumptions. [ABSTRACT FROM AUTHOR]

Existing methods for calibrating link fundamental diagrams (FDs) often focus on a limited number of links and use grouping strategies that are largely dependent on roadway physical attributes alone. In this study, we propose a big data-driven two-stage clustering framework to calibrate link FDs for freeway networks. The first stage captures, under normal traffic state, the variations of link FDs over multiple days based on which links are clustered in the second stage. Two methods, i.e. the standard k-means algorithm combined with hierarchical clustering and a modified hierarchical clustering based on the Fréchet distance, are applied in the first stage to obtain the FD parameter matrix for each link. The calibrated matrices are input into the second stage where the modified hierarchical clustering is re-employed as a static approach resulting in multiple clusters of links. To further consider the variations of link FDs, the static approach is extended by modifying the similarity measure through the principle component analysis (PCA). The resulting multivariate time-series clustering models the distributions of the FD parameters as a dynamic approach. The proposed framework is applied on the Melbourne freeway network using one-year worth of loop detector data. Results have shown that (a) similar roadway physical attributes do not necessarily result in similar link FDs, (b) the connectivity-based approach performs better in clustering link FDs as compared with the centroid-based approach, and (c) the proposed framework helps achieving a better understanding of the spatial distribution of links with similar FDs and the associated variations and distributions of the FD parameters. [ABSTRACT FROM AUTHOR]

In this paper we study similarity measures for moving curves which can, for example, model changing coastlines or retreating glacier termini. Points on a moving curve have two parameters, namely the position along the curve as well as time. We therefore focus on similarity measures for surfaces, specifically the Fréchet distance between surfaces. While the Fréchet distance between surfaces is generally NP-hard, we show for variants arising in the context of moving curves that they are polynomial-time solvable or NP-complete depending on the restrictions imposed on how the moving curves are matched. We achieve the polynomial-time solutions by a novel approach for computing a surface in the so-called free-space diagram based on a relation between obstacles. [ABSTRACT FROM AUTHOR]

The paper presents a discrete variation of the Fréchet distance between closed curves, which can be seen as an approximation of the continuous measure. A rather straightforward approach to compute the discrete Fréchet distance between two closed sequences of m and n points using binary search takes O (m n log ⁡ m n) time. We present an algorithm that takes O (m n log ⁎ ⁡ m n) time, where log ⁎ is the iterated logarithm. [ABSTRACT FROM AUTHOR]

Abstract: Outlier detection and clustering are important to analyze trajectory. While many algorithms have been developed to tackle these issues, they lack the combination with visualization to enable the involvement of human intelligence during the analyzing process. We propose a visual framework called M3, which combines data mining algorithms with visualization technique through three coordinated views: Map, MST, and FSDMatrix. Map view displays the spatial information of trajectories. MST is a minimum spanning tree, which presents the relationships between trajectories. In MST, each node represents a trajectory; edges between nodes denote the Fréchet distance between trajectories. FSDMatrix shows a matrix of pairwise Free Space Diagram to assist in detecting outliers and clustering trajectories. The three views are interacted with each other. Through case studies, we discuss the applicability of our framework and demonstrate the convenience brought by it.Graphical abstract: [ABSTRACT FROM AUTHOR]

To solve the problem that underwater submarine target signal are corruped by the strong magnetic background noise and interrupter in the aeromagnetic anomaly detection, a joint estimation detection method is proposed. A signal model of target measured by optical pump magnetometer is established for submarine target based on magnetic dipole. The target signal model is determined by 7 unknown parameters： position vector a:,y ,2 , magnetic moment vector Mx,My,M： 9 and course angle 〇. According to the observation sample, the unknown parameters are searched by genetic algorithm and the prior information of submarine target, and the fitness function is constructed by Frechet distance. Then the test statistic of mean correlation is proposed based on the target estimated signal, and the correlation detector using target estimated signal is designed. The performance analysis using measurement data shows that the detector is still with good detection performance in the low signal-to-noise ratio condition. Compared with the traditional detection based on decomposition of orthonormal basis and the aeromagnetic anomaly detection for moving target, the performance of the joint estimator and detector using target estimated signal is better, and it can improve the signal-to-noise ratio and reduce the false alarm probability. [ABSTRACT FROM AUTHOR]

In different spatial data set, corresponding enties have different space pattern of manifestation, while identification of multi-source heterogeneous data sets of the same entity is the fundamental problem in spatial data integration and various kinds of its applications. Integrating geospatial data from different sources is the most important way to improve the quality of GIS data, while identification of the same object is the prerequisite for integration and analysis of spatial data. In this paper, on the basis of the shape characters, we classify the complex linear features into the simple and the complex linear features, In terms of matching of curve features, there are still some shortcomings in existing methods, this is the reason that the paper puts forward complex curve features of the Fréchet distance matching method. Based on geometry and topology characteristics of curve features, the method first obtains the matching candidates, and then realizes the simplification of features on the basis of Fréchet distance and simplified method. Finally, by introducing triads of simplified features to store the attribute information of the complex linear element, the paper proposed an improved method based on the Fréchet distance and the triads information of the complex linear feature to accomplish the detection of different types of corresponding pairs and to realize complex curve features matching. The test results show that the proposed method not only can efficiently solve the matching problems of curve features, but also can effectively identify 1:0,1:N and M:N matching pairs. [ABSTRACT FROM AUTHOR]

We present a pseudo-polynomial time ( 1 + ε ) -approximation algorithm for computing the integral Fréchet distance between two given polygonal curves T 1 and T 2 . The running time is in O ( ζ 4 n 4 ε 2 log ⁡ ζ n ε ) where n is the complexity of T 1 and T 2 and ζ is the maximal ratio of the lengths of any pair of segments from T 1 and T 2 . This leads to a polynomial running time w.r.t. n and 1 ε for ζ ∈ O ( 1 ) . Furthermore, we relate weighted shortest paths inside a parameter cell C to the monotone free space axis of C . As a result we present a simple construction of weighted shortest paths inside a parameter cell. Additionally, such a shortest path provides an optimal solution for the partial Fréchet similarity of segments for all leash lengths. These two aspects are related to each other and are of independent interest. [ABSTRACT FROM AUTHOR]

The processing and analysis of trajectories are the core of many location-based applications and services, while trajectory similarity is an essential concept regularly used. To address the time-consuming problem of similarity query, an efficient algorithm based on Fréchet distance called Ordered Coverage Judge (OCJ) is proposed, which could realize the filtering query with a given Fréchet distance threshold on large-scale trajectory datasets. The OCJ algorithm can obtain the result set quickly by a two-step operation containing morphological characteristic filtering and ordered coverage judgment. The algorithm is expedient to be implemented in parallel for further increases of speed. Demonstrated by experiments over real trajectory data in a multi-core hardware environment, the new algorithm shows favorable stability and scalability besides its higher efficiency in comparison with traditional serial algorithms and other Fréchet distance algorithms. [ABSTRACT FROM AUTHOR]

Given two polygonal curves in the plane, there are many ways to define a notion of similarity between them. One popular measure is the Fréchet distance. Since it was proposed by Alt and Godau in 1992, many variants and extensions have been studied. Nonetheless, even more than 20 years later, the original $$O(n^2 \log n)$$ algorithm by Alt and Godau for computing the Fréchet distance remains the state of the art (here, n denotes the number of edges on each curve). This has led Helmut Alt to conjecture that the associated decision problem is 3SUM-hard. In recent work, Agarwal et al. show how to break the quadratic barrier for the discrete version of the Fréchet distance, where one considers sequences of points instead of polygonal curves. Building on their work, we give a randomized algorithm to compute the Fréchet distance between two polygonal curves in time $$O(n^2 \sqrt{\log n}(\log \log n)^{3/2})$$ on a pointer machine and in time $$O(n^2(\log \log n)^2)$$ on a word RAM. Furthermore, we show that there exists an algebraic decision tree for the decision problem of depth $$O(n^{2-\varepsilon })$$ , for some $$\varepsilon > 0$$ . We believe that this reveals an intriguing new aspect of this well-studied problem. Finally, we show how to obtain the first subquadratic algorithm for computing the weak Fréchet distance on a word RAM. [ABSTRACT FROM AUTHOR]

We consider the problem of computing the Fréchet distance between two curves for which the exact locations of the vertices are unknown. Each vertex may be placed in a given uncertainty region for that vertex, and the objective is to place vertices so as to minimise the Fréchet distance. This problem was recently shown to be NP-hard in 2D, and it is unclear how to compute an optimal vertex placement at all. We present the first general algorithmic framework for this problem. We prove that it results in a polynomial-time algorithm for curves in 1D with intervals as uncertainty regions. In contrast, we show that the problem is NP-hard in 1D in the case that vertices are placed to maximise the Fréchet distance. We also study the weak Fréchet distance between uncertain curves. While finding the optimal placement of vertices seems more difficult than the regular Fréchet distance—and indeed we can easily prove that the problem is NP-hard in 2D—the optimal placement of vertices in 1D can be computed in polynomial time. Finally, we investigate the discrete weak Fréchet distance, for which, somewhat surprisingly, the problem is NP-hard already in 1D. [ABSTRACT FROM AUTHOR]

The Fréchet distance is a well studied and very popular measure of similarity of two curves. The best known algorithms have quadratic time complexity, which has recently been shown to be optimal assuming the Strong Exponential Time Hypothesis (SETH) [Bringmann, FOCS'14]. To overcome the worst-case quadratic time barrier, restricted classes of curves have been studied that attempt to capture realistic input curves. The most popular such class are -packed curves, for which the Fréchet distance has a -approximation in time [Driemel et al., DCG'12]. In dimension this cannot be improved to for any unless SETH fails [Bringmann, FOCS'14]. In this paper, exploiting properties that prevent stronger lower bounds, we present an improved algorithm with time complexity . This improves upon the algorithm by Driemel et al. for any . Moreover, our algorithm's dependence on , and is optimal in high dimensions apart from lower order factors, unless SETH fails. Our main new ingredients are as follows: For filling the classical free-space diagram we project short subcurves onto a line, which yields one-dimensional separated curves with roughly the same pairwise distances between vertices. Then we tackle this special case in near-linear time by carefully extending a greedy algorithm for the Fréchet distance of one-dimensional separated curves. [ABSTRACT FROM AUTHOR]

Accuracy in roads geometry is an objective to be achieved by surveyors and cartographers when they obtain their data by GPS, Lidar, or photogrammetry. Nevertheless, those capture methods are expensive. Nowadays, cheap and collaborative methods can produce big datasets, which need to be processed in order to get accuracy axis from not accurate original data. Because a roads network is composed of several points, the resulting dataset could become a large-sized file, difficult to manage, and slow in consultancy for the users. In this paper, we expose our previous solutions for estimating a representative axis and propose a novel B-spline least square method governed by a genetic algorithm. The genetic algorithm minimizes the number of knots necessary to define the B-spline representative axis while keeping the axis' original shape. We know the original shape because we have computed it using a large number of knots by an iterative and convergent method developed in a well-contrasted previous study. This paper shows that our approaches are suitable to be deployed in a web-based application in order to support collaborative digital cartography. Copyright © 2015 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

Locomotion recovery after a spinal cord injury (SCI) includes axon regeneration, myelin preservation and increased plasticity in propriospinal and descending spinal circuitries. The combined effects of tamoxifen and exercise after a SCI were analyzed in this study to determine whether the combination of both treatments induces the best outcome in locomotion recovery. In this study, the penetrating injury was provoked by a sharp projectile that penetrates through right dorsal and ventral portions of the T13-L1 spinal segments, affecting propriospinal and descending/ascending tracts. Intraperitoneal application of Tamoxifen and a treadmill exercise protocol, as rehabilitation therapies, separately or combined, were used. To evaluate the functional recovery, angular patterns of the hip, knee and ankle joints as well as the leg pendulum-like movement (PLM) were measured during the unrestricted gait of treated and untreated (UT) animals, previously and after the traumatic injury (15 and 30 days post-injury (dpi)). A pattern (curve) comparison analysis was made by using a locally designed Matlab script that determines the Frechet dissimilarity. The SCI magnitude was assessed by qualitative and quantitative histological analysis of the injury site 30 days after SCI. Our results showed that all treated groups had an improvement in hindlimbs kinematics compared to the UT group, which showed a poor gait locomotion recovery throughout the rehabilitation period. The group with the combined treatment (tamoxifen + exercise (TE)) presented the best outcome. In conclusion, tamoxifen and treadmill exercise treatments are complementary therapies for the functional recovery of gait locomotion in hemi-spinalized rats. [ABSTRACT FROM AUTHOR]

Wearable and smartphone technology innovations have propelled the growth of Pedestrian Navigation Services (PNS). PNS need a map-matching process to project a user's locations onto maps. Many map-matching techniques have been developed for vehicle navigation services. These techniques are inappropriate for PNS because pedestrians move, stop, and turn in different ways compared to vehicles. In addition, the base map data for pedestrians are more complicated than for vehicles. This article proposes a new map-matching method for locating Global Positioning System (GPS) trajectories of pedestrians onto road network datasets. The theory underlying this approach is based on the Fréchet distance, one of the measures of geometric similarity between two curves. The Fréchet distance approach can provide reasonable matching results because two linear trajectories are parameterized with the time variable. Then we improved the method to be adaptive to the positional error of the GPS signal. We used an adaptation coefficient to adjust the search range for every input signal, based on the assumption of auto-correlation between consecutive GPS points. To reduce errors in matching, the reliability index was evaluated in real time for each match. To test the proposed map-matching method, we applied it to GPS trajectories of pedestrians and the road network data. We then assessed the performance by comparing the results with reference datasets. Our proposed method performed better with test data when compared to a conventional map-matching technique for vehicles. [ABSTRACT FROM AUTHOR]

All known algorithms for the Fréchet distance between curves proceed in two steps: first, they construct an efficient oracle for the decision version; second, they use this oracle to find the optimum from a finite set of critical values. We present a novel approach that avoids the detour through the decision version. This gives the first quadratic time algorithm for the Fréchet distance between polygonal curves in $$\mathbb {R}^d$$ under polyhedral distance functions (e.g., $$L_1$$ and $$L_\infty $$ ). We also get a $$(1+\varepsilon )$$ -approximation of the Fréchet distance under the Euclidean metric, in quadratic time for any fixed $$\varepsilon > 0$$ . For the exact Euclidean case, our framework currently yields an algorithm with running time $$O(n^2 \log ^2 n)$$ . However, we conjecture that it may eventually lead to a faster exact algorithm. [ABSTRACT FROM AUTHOR]

Nowadays, an abundance of sensors are used to collect very large datasets of moving objects. The movement of these objects can be analysed by identifying common routes. For this, a cluster of trajectories must be defined and the pattern of each cluster discovered. In this article, we introduce a new pattern, called the Trajectory Box Plot (TBP), to summarize a set of trajectories following the same route. The TBP is an extension of the well-known descriptive statistics Box Plot concept. Each TBP is described by a median trajectory, a 3D box and a 3D fence. The median trajectory depicts the typical movement of mobile objects. The box and the fences (whiskers) describe the spatial and temporal spreading around the central tendency. TBPs are useful to summarize and analyse trajectory streams, understand their spatio-temporal density and detect outliers. In this article, visual analysis highlights how the TBP pattern effectively describes how the density of trajectory clusters change over time. [ABSTRACT FROM AUTHOR]

ABSTRACT Traditionally, spaghetti charts and track ellipses are used in track-based meteorological applications to illustrate the spatial uncertainty of a set of paths on a map. However, the spatial spread of the set is often evaluated by the eye, and as a result, the decisions made can be highly subjective. A unit-less metric based on the Fréchet distance is developed and proposed as a consistent way of quantifying spatial uncertainty in track-based applications. The methodology described is generic and can be configured for use in applications where a measure of the spatial similarity among a set of tracks is required, such as tropical storm track forecasts and flight/ship routing. [ABSTRACT FROM AUTHOR]

The article analyzes similarity of closed polygonal curves with respect to the Fréchet metric, which is stronger than the well-known Hausdorff metric and therefore is more appropriate in some applications. An algorithm is described that determines whether the Fréchet distance between two closed polygonal curves with and vertices is less than a given number . The algorithm takes time whereas the previously known algorithms take time. [ABSTRACT FROM AUTHOR]

We study a modified version of the partial Fréchet similarity that is motivated by real world applications, e.g. the analysis of spectroscopic data in the context of astroinformatics and the analysis of birds' migration trajectories. In those practical applications of curve matching it is often necessary to ignore outliers while dissimilarities regarding individual directions should be weighted by individual costs. We enable both by computing the partial Fréchet similarity between polygonal curves w.r.t. a non-uniform metric. In particular, we measure distances by a function that is induced by a set of weighted vectors. We discuss the approximation quality of regarding any metric and present a polynomial time algorithm for computing an exact solution of the resulting modified partial Fréchet similarity. [ABSTRACT FROM AUTHOR]

We describe a $$O(\log n )$$ -approximation algorithm for computing the homotopic Fréchet distance between two polygonal curves that lie on the boundary of a triangulated topological disk. Prior to this work, algorithms were known only for curves on the Euclidean plane with polygonal obstacles. A key technical ingredient in our analysis is a $$O(\log n)$$ -approximation algorithm for computing the minimum height of a homotopy between two curves. No algorithms were previously known for approximating this parameter. Surprisingly, it is not even known if computing either the homotopic Fréchet distance, or the minimum height of a homotopy, is in NP. [ABSTRACT FROM AUTHOR]

Computing the Fréchet distance for surfaces is a surprisingly hard problem and the only known polynomial-time algorithm is limited to computing it between flat surfaces. We study the problem of computing the Fréchet distance for a class of non-flat surfaces called folded polygons. We present a fixed-parameter tractable algorithm for this problem. Next, we present a polynomial-time approximation algorithm. Finally, we present a restricted class of folded polygons for which we can compute the Fréchet distance for L ∞ in polynomial time. [ABSTRACT FROM AUTHOR]

Geometric similarity measurement of linear features is the key to matching map data, fusion, and clustering. This paper presents a new method for geometric similarity measurement of digital map linear features based on the traditional discrete Frechet distance. We derived a formula for computing discrete curves Frechet distance based on recurrence and presents curves similarity measurement model based on average Frechet distance. The average Frechet distance is obtained by recognizing and computing minimal path between points in two curves, which can avoid biggish error of traditional Frechet distance. Meanwhile, this paper demonstrates that the average Frechet distance delivers higher accuracy, theoretically. In order to measure the partial and overall similarity between two curves, we also present a partial-overall discrete Frechet distance based on the average Frechet distance. Finally, this Frechet distance was applied to matching map data, fusion and contour interpolation. Experiments were performed to show the feasibility and superiority of the method. [ABSTRACT FROM AUTHOR]

Let T be a tree in R d and let Δ > 0 be a real number. The aim is to preprocess T into a data structure, such that for any polygonal query path Q , we can decide if T contains a path P whose Fréchet distance δ F ( Q , P ) to Q is at most Δ. For any real number ε > 0 , we present an efficient data structure that solves an approximate version of this problem for the case when T is c -packed and each of the edges of T and Q has length Ω ( Δ ) : If the query algorithm returns NO, then there is no such path P . If the query algorithm returns YES, then T contains a path P for which δ F ( Q , P ) ≤ ( 1 + ε ) Δ if Q is a line segment, and δ F ( Q , P ) ≤ 3 ( 1 + ε ) Δ otherwise. [ABSTRACT FROM AUTHOR]

We introduce a counterpart of the Frechet distance for the rooted trees in a metric space. Some properties and possible generalizations of this distance are discussed. [ABSTRACT FROM AUTHOR]

This paper develops a new integrated ball (pseudo)metric which provides an intermediary between a chosen starting (pseudo)metric d and the L p distance in general function spaces. Selecting d as the Hausdorff or Fréchet distances, we introduce integrated shape-sensitive versions of these supremum-based metrics. The new metrics allow for finer analyses in functional settings, not attainable applying the non-integrated versions directly. Moreover, convergent discrete approximations make computations feasible in practice. [ABSTRACT FROM AUTHOR]