sub-voxel-precise estimation of the extremum of a tabulated function

06/03/2012 - 09:38 von Hannes Fassold | Report spam
I have a regular 3D voxel grid (spacing 1) and a arbitrary (real)
function evaluated at a 3x3x3 window in ('voxel grid') around a
'center' position (xc, yc, zc). So I have 27 function values at the
postions (xc +{-1|0|1}, yc +(-1|0|1}, zc + (-1|0|1})).

Now i want to interpolate a quadratical 'taylor' polynom into the
function and find the position (xc_0, yc_0, zc_0) where the
quadratical polynom has an extremum. How to do ?
For the 1D case, i know how to do - see fn. 'P3Interpolate_Extremum_1'
from http://www.ebyte.it/library/codesni...tion.html.
But how to 'generalize' this function to 3 dimensions ??
Furthermore, I'd like to know whether these 27 grid points and
function values define my an unique quadratical polynom, or whether I
have to fit a 'best-fitting' quadratical polynom into these points.

By the way the problem comes from implementing section 2 in paper
http://citeseerx.ist.psu.edu/viewdo...C07DA9?doi.1.1.1.8475&rep=rep1&type=pdf

Many thx for any suggestions.
 

Lesen sie die antworten

#1 Christian Gollwitzer
06/03/2012 - 22:05 | Warnen spam
Hallo Hannes,

vorweg: dies ist eine deutsche Newsgroup.

Am 06.03.12 09:38, schrieb Hannes Fassold:
I have a regular 3D voxel grid (spacing 1) and a arbitrary (real)
function evaluated at a 3x3x3 window in ('voxel grid') around a
'center' position (xc, yc, zc). So I have 27 function values at the
postions (xc +{-1|0|1}, yc +(-1|0|1}, zc + (-1|0|1})).

Now i want to interpolate a quadratical 'taylor' polynom into the
function and find the position (xc_0, yc_0, zc_0) where the
quadratical polynom has an extremum. How to do ?
For the 1D case, i know how to do - see fn. 'P3Interpolate_Extremum_1'
from http://www.ebyte.it/library/codesni...tion.html.
But how to 'generalize' this function to 3 dimensions ??
Furthermore, I'd like to know whether these 27 grid points and
function values define my an unique quadratical polynom, or whether I
have to fit a 'best-fitting' quadratical polynom into these points.



Also zuerst muss man einen Ansatz für die Funktion machen, dann die
Stützstellen einsetzen und das Gleichungssystem für die Werte an den
Stützstellen lösen. Du hast vorgeschlagen, ein quadratisches Polynom zu
benutzen. Im allgemeinen Fall über drei Dimensionen enthàlt das dann
folgende Basisfunktionen:

x^2, y^2, z^2, x*y, x*z, y*z, x, y, z, 1

Damit hast Du 10 Dimensionen und 27 Stützpunkte, was bedeutet, dass es
im Allgemeinen keine Lösung gibt. Du kannst natürlich trotzdem eine
Approximation über die Pseudoinverse berechnen, doch ich rate davon eher ab:

Das quadratische Polynom muss nàmlich mitnichten ein eindeutiges
Extremum haben. Im 1D-Fall kann ja auch der Koeffizient vor dem
Quadratterm 0 sein, was aber ein singulàrer Fall ist. Im
höherdimensionalen Fall kann das Polynom stattdessen auch Sattelpunkte
haben. Um das festzustellen, müsstest Du das Polynom folgendermaßen
umschreiben:

1/2 r Q r + c*r

mit r=(x,y,z) als Vektor, Q einer symmetrischen Matrix und c als Vektor.
Dann ist es eine Parabel, falls Q positiv definit ist. Das ist aber
recht fragil. Du musst dann nàmlich das Gleichungssystem
Q r_c = - c
lösen, um auf den Ort des Extremums r_c zu kommen und die positive
Definitheit überprüfen (z.B. Cholesky-Faktorisierung).

Du könntest den Ansatz auch weiter reduzieren und die gemischten Terme
herausnehmen, so dass folgende Basisfunktionen übrigbleiben:

x^2, x, y^2, y, z^2, z, 1

Damit ergibt sich der globale kritische Punkt als

x_c = - a_x/a_x2
y_c = - a_y/a_y2
z_c = - a_z/a_z2

und Du hast ein Extremum falls alle a_x2,a_y2,a_z2 das gleiche
Vorzeichen haben.

By the way the problem comes from implementing section 2 in paper
http://citeseerx.ist.psu.edu/viewdo...C07DA9?doi.1.1.1.8475&rep=rep1&type=pdf



OK, die scheinen wirklich das volle System zu lösen. Ich hab das aber
nicht genau gelesen.

Christian

Ähnliche fragen