enter image description here I am somewhat new in the field of Digital Signal Processing / Image processing.

As shown in the figure, I have 4 straight lines $f_i(x)$ with $i = 1,\dots, 4$ that pass through $g(x)$. Similiarly there are $4$ sample points $\mathbf{x}_i$ that lie on $g(x)$. The vectors $\mathbf{v}_i$ are the vectors obtained by joining the sample points $\mathbf{x}_i$ and the intersecting points between the lines $f_i(x)$ and $g(x)$.

The values of $\mathbf{x}_i$, $f_i(x)$ and $g(x)$ and hence the vectors $\mathbf{v}_i$ points are known. If so, is it possible to find $g'(x)$ just by exploiting the information (direction and magnitude) contained in $\mathbf{v}_i$ such that the sum of the square of the magnitude of the vectors $\mathbf{v}_i$ is minimized?
My goal is to exploit the 1d-vectorfield and find a transformation matrix that maps $g(x)$ to $g'(x)$.

In the example above since $\mathbf{v}_1$ is pointing downward and $\mathbf{v}_4$ is pointing upwards (see $g(x)$), then intuitively, $g(x)$ must be translated about positive $x-$axis followed by some rotation. What is the best way to solve this problem?

  • $\begingroup$ The diagram needs a bit of clarification because everything depicted is actually 2D, not 1D (as implied by $g(x)$ for example) but what I would like to ask is if $g'(x)$ is a known? $\endgroup$
    – A_A
    Sep 25 '20 at 13:46
  • $\begingroup$ Everything is 2D, only the vector field is 1D in this case since the vectors lie on a line $g(x)$. My goal is to find the unknown $g'(x)$ such that the sum of the error is minimized. $\endgroup$ Sep 25 '20 at 13:57

The issue with considering anything as one dimensional in this problem is that they cannot be manipulated as required by the solution.

This can be solved by the optimsation of a function that modifies the $x_i$s towards the direction that minimises some expression of "error". The error here seems to be the distance of each point from the nearest intersection with the known lines.

The minimisation of that error alone is not enough to produce the required result here, but we will come back to this later.

The key "tool" here is the manipulation of the $x_i$s via modifications to the line they reside upon. This makes it a bit clearer why $g(x)$ is not a useful way of seeing things here.

For example, how are we going to rotate a $g(x)$? How are we going to "move it" towards the left or towards the right? If the answers to these questions are "we will just add some offset" or "send it through some rotation matrix", then $g(x)$ cannot stay as it is because it would be unaware of the space it is moving in.

Instead, suppose that all $x_i$s rest on a line running through and parallel to some vector $\vec{a}$. This, being a vector allows us to move it around (to translate the vector, simply add the required $x,y$ offset) and rotate it (to rotate the vector, simply scale its components by the appropriate coefficients). Consequently, we now cannot leave the description of the points as $x_i$ but instead something like $p_i$ taken from the set of points $P$ with each point being a pair of $(x,y)$ coordinates.

To complete the loop we need a way by which to change this line the points are resting on by some factor that is the result of the minimisation. We can do this by combining a translation and a rotation matrix and use the minimisation to inform us about the final $\text{offset}_x, \text{offset}_y, \theta$ parameters required to make the vector $\vec{a}$ coincide with the right points on the "fan" that is created by the $f_i$s.

In terms of practically doing this, you can establish a very simple function for manipulating the $p_i$s as $\text{mod_points}(P,\text{offset}_x, \text{offset}_y, \theta)=p_{i,n-1} \cdot M_{translate}(\text{offset}_x, \text{offset}_y,) \cdot M_{rotate}(\theta)$ where $P$ is the current position of the points, $p \in P$ and $n \in \mathbb{N}$ is the iteration step. Other platforms (e.g. MATLAB, Scilab, Octave, Julia and others) will have similar optimisation functionality of course.

At each iteration ($n$) use this to derive the error function you are trying to minimise. The error function takes the known lines and the positions of the transformed points and returns how far away from optimal is the solution. For example, $\text{fit_error}(f_i, \text{modified_P})$.

This $\text{fit_error}()$ will then be used in place of fun in scipy.optimise.minimise() and your initial $p_i$s (or $x_i$s as you call them now) will be the initial positions x0.

After a number of iterations, minimise() will have moved the line that the $P$s rest upon on the right intersection point with the "fan" that is defined by the (now known as) $x_i$s.

But, if you try to do this, you will notice that the minimisation of the error is not a sufficient condition because it allows the following solution:

enter image description here

Is this a valid solution according to the criterion of minimal error? Yes it is, this line produces points that rest on the known lines. Is it an acceptable solution?....No.

What else should we do to produce a valid and acceptable solution? Add a constraint to the calculation function so that the $P$ set gets closer to the intersections with the $f_i$ lines while at the same time the distances between the points themselves are also preserved. You can model this as two expressions for the error and add them with weight coefficients so that you can tune what sort of priority you want to give over either of the constraints.

Hope this helps.


You have two options regarding preserving the distance of the points:

  1. Calculate the distance from the points, but infer where should the $\vec{a}$ go next. Then, since you do have the line that the points are on and their "inter-distances" are fixed, you can use the orientation of $\vec{a}$ to calculate where each point should be, knowing just the first one. (Subsequent points will be positioned at known distance $d$ from the previous known point towards the direction of $\vec{a}$).

  2. Literally include all distances that need to be preserved in the expression for the error. In this case it would be distances $d(p_n,p_{n+1}), d(p_n,p_{n+2}), d(p_{n+1}, p_{n+2}), d(p_n,p_{n+3}), d(p_{n+1}, p_{n+3}), d(p_{n+2}, p_{n+3})$ where $d()$ is a function that returns the Euclidean distance and $n = 0$ is the index in $P$.

  • $\begingroup$ Thanks for the clarification!! The distance between the elements $p_{n}$ and $ p_{n-1}$ from the set $P$ must be preserved after the transformation - I admit that the illustration is slightly misleading. The constraint we need is one such that the distance between the points in $P$ are constant throughout the iteration. What is the mathematical way of formulating this constraint; Sth like $\dfrac{dp_{(n, n-1)}}{dt} = 0$, where $dp_{(n, n-1)}$ is the distance between the points $p_n$ and $p_{n-1}$? $\endgroup$ Sep 27 '20 at 8:02
  • $\begingroup$ Glad to hear you found this helpful. Please see updated response. You can upvote or "accept" the answer from the controls next to it and this will stop it from circulating the board as "unanswered". @unfinished_sentenc $\endgroup$
    – A_A
    Sep 28 '20 at 13:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.