On the Beneficial Effect of Noise in Vertex Localization

A theoretical and experimental analysis related to the effect of noise in the task of vertex identification in unknown shapes is presented. Shapes are seen as real functions of their closed boundary. An alternative global perspective of curvature is examined providing insight into the process of noise-enabled vertex localization. The analysis reveals that noise facilitates in the localization of certain vertices. The concept of noising is thus considered and a relevant global method for localizing Global Vertices is investigated in relation to local methods under the presence of increasing noise. Theoretical analysis reveals that induced noise can indeed help localizing certain vertices if combined with global descriptors. Experiments with noise and a comparison to localized methods validate the theoretical results.

1. Supremum of all pair-wise distances between points of \(\varvec{\alpha }\).

2. Directed to the interior of the bounded region defined by \(\varvec{\alpha }\).

3. The fact that remote points are perceptually important has been demonstrated in Raftopoulos and Kollias (2011), where shape matching scores in benchmark datasets where improved by permitting correspondences only to remote points.

Authors and Affiliations

1. CEDRIC-CNAM, 292 Rue St Martin, 75141, Paris Cedex 03, France

   Konstantinos A. Raftopoulos & Marin Ferecatu

2. University of Lincoln, Brayford Pool, Lincoln, Lincolnshire, LN6 7TS, UK

   Stefanos D. Kollias

3. Elais Unilever Hellas SA, A. Legaki 22, 18233, A.I. Rentis, Athens, Greece

   Dionysios D. Sourlas

4. IVML-NTUA, Iroon Polytexneiou 9, 15780, Athens, Greece

   Konstantinos A. Raftopoulos

Corresponding author

Correspondence to Konstantinos A. Raftopoulos.

Communicated by Zhouchen Lin.

Appendix 1: Proof of Proposition 1

Proof

For the clarity of this proof the dot and double dot will denote the vector first and second derivatives with respect to s, whereas the respective scalar derivatives will be denoted by \(\frac{d}{ds}\) and \(\frac{d^2}{ds^2}\). For the meanings of \(\varvec{r}\) and \(\omega \) see Sect. 4.

For the view function \(v_{\xi }(s_*)=\Vert \varvec{\alpha }(s_*)-\varvec{\alpha }(\xi )\Vert \equiv \Vert \varvec{r}\Vert \) it is:

where \(\cdot \) is the inner product. Substituting \(\varvec{r}=\Vert \varvec{r}\Vert (-sin(\omega ), cos(\omega ) )\), \(\dot{\varvec{r}}=(1,0)\) we get:

which is also a proof that the view functions are 1-Lipschitz.

We also have:

and substituting \(\varvec{r}=\Vert \varvec{r}\Vert (-sin(\omega ), cos(\omega ) )\), \(\dot{\varvec{r}}=(1,0)\), \(\ddot{\varvec{r}}=-\kappa (s_*)(0,-1)=(0,\kappa (s_*))\) we get:

and the proof is complete. \(\square \)

Appendix 2: Proof of Theorem 1

For the purpose of the following proofs, we will occasionally consider the view functions as scalars of two parameters, thus we will occasionally use \(v(s,\xi )\) meaning \(v_{s}(\xi )\), to make it explicit that we work with the two parameters in mind. Both parameters s and \(\xi \) are arc lengths measured from the curve’s starting point and \(v(s,\xi )\) is the plane distance between the corresponding points on the curve. Always the dot(s) indicate(s) derivative(s) with respect to s. Every derivative of \(v_{\xi }(s)\) or \(v_{s}(\xi )\) and every partial derivative of \(v(s, \xi )\) is computed under the assumption that \(\xi \ne s\).

Proof

(1)

where we have used the Leibniz integral rule. The step of the derivation, marked with * above, is valid due to the fact that \(v(s,\xi )=v(\xi ,s), \forall s, \xi \in (0, \lambda ]\). The integrals make sense since the set where \(v_{\xi }(s)\) (or \(v_{s}(\xi )\)) is not differentiable has vanishing measure in \(\mathbb {R}\). From Proposition 1, the result in (29) is independent of the variable \(\xi \), given the variable s is fixed at \(s_*\), at the corresponding point of which the Frenet frame is considered (see Sect. 4). This fact permits valid integration over \(\xi \), thus:

which is also a proof that the VAR is \(\lambda \)-Lipschitz.

Angle \(\omega \) is a function of \(\xi \) (given \(s_*\)) and the integral on the right hand side of (33) quantifies a notion of displacement of the curve with respect to the normal to the curve at \(s_*\). To see this, consider a point \(\varvec{\alpha }(\xi )\) and notice that as \(\xi \) traverses the domain of \(\varvec{\alpha }\), angle \(\omega \) measures the angular displacement of this point with respect to the normal at \(s_*\), \(\dot{\phi }_\alpha (s_*)\) can thus be thought of measuring the total angular displacement of the whole curve with respect to the normal at \(s_*\). \(\square \)

Proof

(2), (3) From (33) we get:

From the combination of (29) and (31) we get:

and substituting in (34):

If \(s_*\) is a local maximum point for \(\phi _\alpha (s)\), then there exists a neighborhood U of \(s_*\) such that \(\phi _\alpha (s_*) \ge \phi _\alpha (s)\) for every \(s \in U\). In such a case \(\ddot{\phi }_\alpha (s_*) \le 0\) and since \(\int _0^\lambda \frac{cos^2(\omega )}{\Vert \varvec{r}\Vert }d\xi > 0\) from (36) it follows that:

therefore, \(\kappa (s_*)\ne 0\), \(\left. \int _0^\lambda cos(\omega )d\xi \bigg |\smash {\mathop { }_{s=s_*}}\right. \ne 0\).

From (36), by setting \(A(s)=\int _0^\lambda cos(\omega )d\xi \) and \(B(s)=\int _0^\lambda \frac{cos^2(\omega )}{\Vert r\Vert } d\xi \) and given that \(\kappa (s_*)\ne 0\), we finally have:

and the proof is complete. \(\square \)

Reprints and permissions