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]

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]

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]

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]

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]

We present the prefix Fréchet similarity as a new measure for similarity of curves which is for instance motivated by evacuation analysis and defined as follows. Given two (polygonal) curves T and T ′ , we ask for two prefix curves of T and T ′ which have a Fréchet distance no larger than a given distance threshold δ ≥ 0 with respect to the L 1 metric such that the sum of the lengths of the prefix curves is maximal. As parameterized Fréchet measures as for example the prefix Fréchet similarity are highly unstable regarding the value of the distance threshold δ , we give an algorithm that computes exactly the profile of the prefix Fréchet similarity which means the complete functional relation between δ and the prefix Fréchet similarity of T and T ′. This is the first efficient algorithm for computing exactly the whole profile of a parametrized Fréchet distance. While the running time of our algorithm for computing the profile of the prefix Fréchet similarity is O (n 3 log ⁡ n) , we provide a lower bound of Ω (n 2) for the running time of any algorithm computing the profile of the prefix Fréchet similarity, where n denotes the number of segments on T and T ′. This implies that our running time is at most a near linear factor away from being optimal. [ABSTRACT FROM AUTHOR]

We define and study the Fréchet distance and the discrete Fréchet distance between two point sets in the plane. One problem based on the well-known Fréchet distance is to find a polygonal curve on a point set with small Fréchet distance or small discrete Fréchet distance to another given polygonal curve. Here, we consider two given point sets and ask if permutations of these point sets exist, such that the Fréchet distance or the discrete Fréchet distance of curves defined by the permutations is small. [ABSTRACT FROM AUTHOR]