Probabilistic matching of planar regions
type: Item
instance of: scholarly article
title: Probabilistic matching of planar regions
zbMATH Open document ID: 1182.65031
author: Helmut Alt
author: Ludmila Scharf
author: Daria Schymura
published in: Computational Geometry
publication date: 2009-11-16T00:00:00Z
review text: Given two shapes \(A\) and \(B\), a set of transformations \(T\) and a distance measure \(d\), the matching problem is to find the transformation \(t\in T\) such that \(t(A)\) and \(B\) match optimally with respect to \(d\). The authors consider the problem of matching 2D shapes modeled by sets of polygons, using as sets of allowed transformations the set of translations or the set of planar rigid motions, and as similarity measure, the area of overlap. The probabilistic matching algorithm for translations works as follows: Given two shapes \(A\) and \(B\), in one random experiment a point \(a\in A\) and another point \(b\in B\) are selected. The vector \(b-a\in{\mathbb R}^2\) defines a translation \(t\). After repetition of this procedure, a point cloud in \({\mathbb R}^2\) is obtained. The center of the resulting point cloud is a translation that maps a large part of \(A\) onto \(B\). For rigid motions, two different approaches using analogous ideas are given. In the first, besides the translation vector defined as before, a rotation angle is randomly selected. In the second approach, the rigid motion is determined by selecting two points \(a_1,a_2\in A\) and one point \(b_1\in B\). Then another point \(b_2\in B\) is selected such that the distances between the points \(a_1\) and \(a_2\) and \(b_1\) and \(b_2\) are the same. The translation vector is \(b_1-a_1\) and the two vectors \(a_2-a_1\) and \(b_2-b_1\) define the rotation angle. It is shown that the algorithm approximates the maximal area of overlap. A time bound is given that does not depend significantly on the number of vertices, but on perimeter and area of the shapes and, in the case of rigid motions, also on the diameter.
reviewed by: Juan Monterde
Mathematics Subject Classification ID: 65D18
zbMATH DE Number: 5633794
zbMATH Keywords: shape matching
zbMATH Keywords: probabilistic algorithm
zbMATH Keywords: approximation algorithms
zbMATH Keywords: computational geometry
MaRDI profile type: Publication
full work available at URL: j.comgeo.2009.04.006
OpenAlex ID: W2044648518
cites work: Maximum Overlap of Convex Polytopes under Translation
cites work: Matching convex shapes with respect to the symmetric difference
cites work: Q4945503
cites work: Shape Matching by Random Sampling
cites work: On approximating the depth and related problems
cites work: Finding a guard that sees most and a shop that sells most
cites work: Computing the maximum overlap of two convex polygons under translations
cites work: Q4323630
cites work: Q4940106
DOI: 10.1016/J.COMGEO.2009.04.006
description: scientific article; zbMATH DE number 5633794