Binomial Convolutions and Derivatives Estimation from Noisy Discretizations

We present a new method to estimate derivatives of digitized functions. Even with noisy data, this approach is convergent and can be computed by using only the arithmetic operations. Moreover, higher order derivatives can also be estimated. To deal with p

  • PDF / 529,741 Bytes
  • 10 Pages / 430 x 660 pts Page_size
  • 36 Downloads / 177 Views

DOWNLOAD

REPORT


2

Univ. Clermont 1, LAIC, IUT D´ept Informatique, BP 86, F-63172 Aubi`ere, France [email protected] Univ. Clermont 1, LAIC, IUT D´ept Informatique, BP 86, F-63172 Aubi`ere, France [email protected] 3 GREYC Image – ENSICAEN, 6 bd marchal Juin, 14050 Caen CEDEX, France [email protected]

Abstract. We present a new method to estimate derivatives of digitized functions. Even with noisy data, this approach is convergent and can be computed by using only the arithmetic operations. Moreover, higher order derivatives can also be estimated. To deal with parametrized curves, we introduce a new notion which solves the problem of correspondence between the parametrization of a continuous curve and the pixels numbering of a discrete object.

1

Introduction

In the framework of image and signal processing, as well as shape analysis, a common problem is to estimate derivatives of functions, when only some (possibly noisy) sampling of the function is available from acquisition. This problem has been investigated through finite difference methods ([1]), scale-space ([4,8]) and discrete geometry ([6,7,5]). We present a new approach to estimate derivatives from discretized data. As in scale-space, our method relies on simple computations of convolutions. However, our approach is oriented toward integer-only models and algorithms and is based on a discrete point of view of analysis. Unlike estimators proposed in [6], our method still works on noisy data. Moreover, we are able to estimate higher order derivatives. Regarding the order of convergence, we have proved that our approach is as good as the one proposed in [6], that is, in O(h2/3 ) for first order derivatives. Besides, this order of convergence is uniform. To the best of our knowledge, there is no uniform convergence results for estimation of derivatives from discretizations using scale-space.  The asymptotic computational complexity is worst case O( − ln(h)/h) for first order derivatives which is similar to [6]. To deal with parametrized curves of Z2 , we introduce a new notion, the pixel length parametrization, which solves the problem of correspondence between the pixels numbering of a discrete object and the parametrization of a continuous curve. D. Coeurjolly et al. (Eds.): DGCI 2008, LNCS 4992, pp. 370–379, 2008. c Springer-Verlag Berlin Heidelberg 2008 

Binomial Convolutions and Derivatives Estimation

371

Through this paper, we also present some experimental results showing the behavior of our derivative estimator.

2

Derivatives Estimation for Real Functions

First, we consider the case of the real functions. We call real functions functions for which input and output sets are of dimension 1 without doing any hypothesis on the nature of these sets. We call discrete function a function for which the input set is such that the cardinal of all bounded subset is finite (this is the case, for example, with Z and N). For simplification purposes, we consider in the sequel that a discrete function is a function from Z to Z. 2.1

Pri