逆向复杂的二维查找表 [英] Reverse complex 2D lookup table

问题描述

我有一些函数 (a,b)"> 映射了一些输入 到输出 .输出是一个复数.我真正感兴趣的是反函数 (x,y)">.但由于这种反演不能以分析的方式完成，我需要用数值近似来完成.

I have some function which maps some input to the output . The output is a complex number. What I'm actually interested in is the inverse function . But since this inversion can't be done in a analytical way I need to do it with a numerical approximation.

由于 在计算上很昂贵，我的想法是使用查找表方法.我可以生成一个尺寸为 (正向查找表)的 2D 查找表，但是我实际需要的是这个查找表的逆——基于给定的 "https://i.stack.imgur.com/MN3m4.png" alt="(a,b)">.

Since is computationally expensive my idea was to use a lookup table approach. I can generate a 2D lookup table with the dimensions (forward lookup table), but what I actually need is the inverse of this lookup table—yielding based on a given .

对于查找表的反转，我能想到的最简单的方法是使用正向查找表的条目作为顶点，并在它们之间在规则网格中进行插值，从而生成逆向查找表.如果逆查找表对于所需的精度来说太大，我将生成粗表并将这些值用作优化算法的起始值.有没有我遗漏的更简单的方法?

For the inversion of the lookup table the simplest approach I can think of is using the entries of the forward lookup table as vertices and interpolate between them in a regular grid yielding the inverse lookup table. In case the inverse lookup table would be to large for the required precision, I would generate coarse table and use the values as starting values for an optimization algorithm. Are there any easier approaches I'm missing?

哪里 , 是常量，, 是 .

Where , are constant and , are .

推荐答案

1. 对于 f(x,y) 你可以使用 f(x,y)->(a,b) 2D LUT (查表)

1. for f(x,y) you can use f(x,y)->(a,b) 2D LUT (Look Up Table)

但是存储的网格点必须选择得非常密集，以便每个网格矩形最多有一个凹凸，否则插值将无法正常工作.

But the stored grid points must be selected so dense so that there is max one bump per grid rectangle, otherwise interpolation would not work correctly.

如果你想使用线性插值，那么局部最小值/最大值必须是 LUT 内的点，对于更高阶的多项式插值，这并不总是需要的.我会使用 4 点三次插值

If you want to use linear interpolation then the local min/max must be points inside LUT, for polynomial interpolation of higher order is this not always needed. I would use 4 point cubic interpolation

如何计算g(a,b)->(x,y)

• 首先可以进行反向映射吗?
• 那么有多少 (x,y) 点返回相同的 (a,b)=f(x,y) ?
• 与问题相同:f 是否具有功能?

• first is reverse mapping possible?
• so how many (x,y) points return the same (a,b)=f(x,y) ?
• it is the same as question: Is f function or not?

如果 f 不是函数，那么你遇到了问题，你无法解决这个问题，除非以某种方式将范围细分为 f 函数的子范围，然后你会必须根据一些规则选择合适的范围，这取决于您要做什么.所以让我们假设 f 是函数

if f is not function then you got a problem and you can not solve this, unless somehow subdivide the range to sub ranges where f is function and then you will have to select the proper range according to some rules dependent on what are you trying to do. So let assume that f is function

那么如何计算 (x,y)=g(a,b) 那个 f(x,y)=(a,b)?

So how to compute (x,y)=g(a,b) that f(x,y)=(a,b)?

1. 我将从结果的近似值开始.所以在整个范围内尝试足够多的 (x,y) 值并存储最接近所需输出的点，以便 |f(x,y)-(a,b)|是最小的.

1. I would start with approximation of the result. So try enough (x,y) values along the whole range and store the closest point to the desired output so that |f(x,y)-(a,b)| is minimal.

然后重新开始，但不是全范围而是在这一点附近

Then start this again but not on full range but around this point instead

• 递归地将准确度提高到您需要的程度.
• 看这里提高超越方程解的精度那里我正在计算类似的问题，具有二维点的一维 LUT (a(t),y(t)) 并且需要逆 3D 点 (a0,y0,z0) 你可以在那里使用我的近似类

• recursively increasing accuracy up to a point you need.
• look here Increasing accuracy of solution of transcendental equation there I am computing similar problem have 1D LUT of 2D points (a(t),y(t)) and need the inverse 3D point (a0,y0,z0) You can use my approximation class there

近似的嵌套是这样完成的:

int n=5;  // recursions
double e; // Error Of Solution Variable
approx ax,ay;
//            min    max   step   
for (ax.init(-100.0,+100.0,10.0,n,&e);!ax.done;ax.step())
for (ay.init(-100.0,+100.0,10.0,n,&e);!ay.done;ay.step())
    {
    e=|f(ax.a,ay.a)-(a,b)|;
    }
// here (ax.a,ay.a) should hold your solution for input point `(a,b)`

• 初始步骤应该尽可能小，以免错过任何凹凸
• 如果您的 g(a,b) 形状太复杂，那么这可能无法正常工作
• initial step should be as small so there is no bump missed
• if your g(a,b) shape is too complex then this will probably not work properly

由此您可以计算逆 LUT 表...

From this you can compute the inverse LUT table ...

• 每个递归都将步骤除以 10，因此请明智地选择 n.
• Each recursion divides the step by 10 so choose n wisely.

对于 2D 和奇异点来说，这个性能还不错O((log(N))^2).我在 3D O((log(N))^3) 上执行此操作，每个 e 计算具有 100 点，这非常缓慢(大约 35 秒)

For 2D and singular point is the performance of this not that bad O((log(N))^2). I am doing this on 3D O((log(N))^3) with 100 points per e computation and that is painfully slow (about 35 seconds)

• 其中N=(10^n)*(max-min)/step，n为递归次数
• 精度是step/(10^n)
• 不要忘记将最小值、最大值更改为您使用的范围......

这篇关于逆向复杂的二维查找表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！