Homework 7b
Since Problems 1 and 3 of Homework 7 have taken on their own identity as another homework, here is a post to parent discussion for this part. I’ll start with some questions and answers to get the ball rolling:
In the setup file, I first wanted to make sure I am understanding each component correctly. Matrix A is some matrix that when multiplied with x will yield the deformation, b, for each vertex.
Yes, this is true in the absence of pinned vertices. The basic starting point is a matrix A that is set up so that ||Ax|| is the deformation you want to minimize. (Note that this means that, without pins, x = 0 is a perfect solution!)
Vector x is composed of the coordinates of each vertex such that x = [x11,x12,x21,x22,x31,x32,...]‘. At the end of this part b = 0 because we haven’t computed the deformation yet (since we don’t have the new coordinates).
Right, b will have nonzero entries once there are some pins.
I am a little confused as to how to set up the matrix A. The definition of the deformation of an individual triangle, Ej(v1′,v2′,v3′), is easy to understand on paper but I don’t really see how to put that formula into A. I can write the formula in terms of individual coordinates and R, however I don’t see how you can put that into A so that when multiplied by x you get the deformation.
I think if you write out the deformation for a point in terms of the individual components of the three vertices involved, you will see that the two components of the deformation are linear combinations of the variables. (Expand it out all the way including expanding R.)
Also, I know we are supposed to minimize ||Ax|| in this problem, but how do we minimize this quantity? The new and old points are going to be fixed…
The pinned points play a role very much like the boundary pixels in the previous homework. They fit into the equations just like the variables do, except that they are constants, so you need to pull the appropriate terms out and put them on the right hand side.
Or are we minimizing it somehow because each vertex is a part of more than one triangle?
It is important that the vertices are part of multiple triangles. The vertices correspond to columns of A, and each column will have entries on rows that correspond to triangles that its vertex is involved in.
If so what part of the calculation are we minimizing?
One way to say it is that you are minimizing ||Ax||, but not all the entries of x are variables, because some are specified by the user. Instead the system we solve is ||A1 x1 – b|| where x1 consists of all the entries of x that are *not* pinned, and A1 is missing the columns that correspond to those no-longer-variable variables. If you like, you could rearrange the vector x to put all the pinned points at the end — then you are minimizing something that looks like:
||[A1 A2] [x1;x2]||
where x2 contains the known points and x1 has the unknown ones. (This rearrangement is mainly for on paper—in code you’d just use indexing to pull out the columns you want.)
Am I supposed to represent E^2, which I want to minimize, as a measure of the magnitude of some Ax-b?
Yes.
Is the matrix X’ (containing all of the new locations of the vertices) what I am solving for?
Yes, except that you’ll find you need to treat it as one long 2n-vector, not an n-by-2 matrix, in the system. This problem doesn’t separate into decoupled problems for the components, the way some previous problems did.
That would mean that b is a two column matrix, correct?
No, it has to be a 2n-vector.
The constrained linear least squares work done in problem 2 isn’t necessary for this problem, right?
Not for problem 1, but yes for problem 3.
I’m having trouble seeing what the equations that I need to work with here—am I even on the right track?!
You are on the right track! I’d suggest starting with a single triangle, writing out the deformation of a single vertex in terms of the triangle’s three vertices so that you can see how the two components of the deformation are linear combinations of the vertices’ coordinates. Once you see how this works, make yourself a 6-by-6 matrix that computes the deformation of a single triangle from just the coordinates of its three vertices. Once that is working, you can use a bunch of these one-triangle matrices to assemble the matrix for the whole mesh.
Does the output argument ‘b’ from deformation_setup have to match A (size-wise), or can it just be a bunch of numbers that I want access to in deformation_solve?
This writeup implies that b needs to be consistent with an “Ax = b” system, but since solve, not setup, makes and solves the relevant, do you care what setup returns in b?
I’ve read the Q & A, but I’m still having trouble expressing the deformation for a point in terms of the variables. Clearly, given the formula in the assignment, you can change e12′ into v2′ – v1′, but if you expand out R (by multiplying v2′ and v1′ by R), I can’t see how to express the result as a linear combination of v1′ and v2′. I must either be overthinking this or missing something.
A followup to the previous post…when you say x = [x11,x12,x21,x22,x31,x32,...]‘, do you mean that each component of each vertex is a variable? If this is the case, then disregard the previous post.
Yes, each component of each vertex is a variable. The ‘X’ variable in the writeup has n rows (one for each vertex) and two columns (the ‘x’/horizontal coordinate column and the ‘y’/vertical coordinate column). It’s confusing because they named the entire thing ‘X’.
When you’re solving a system like “Ax = b”, however, you only get one column in ‘x’ and one in ‘b’, so the x and y coordinates of the vertices have to be listed sequentially like [x1, y1, x2, y2, x3, y3...], where vertex one (row 1 from capital ‘X’) is [x1 y1], and so on.
Hope that helps.
Is there a typo in the formula for deformation?
It reads: E_j(v_1′,v_2′;v_3′) = ||v1′ + ae_12′ + BRe_12′ -v_3′ ||
Should the last term in the formula be -v_3 instead of -v_3′ ?
@ad488: Yes, you can think of A and B as just some variables that you will get handed back to you in the solution phase. There are some reasonable ways of doing the setup that don’t actually need both of them, in which case you could just return zero for whatever you don’t need.
@sqk: yes, your second post is correct: they are linear combinations of the components, but not of the vectors if you leave them together. This corresponds to the system being a single column system with 2n variables, rather than a 2-column system with n variables. The key difference between the two is that when you have equations that involve x and y components together (which we do) then you have one system, not two separate ones.
@fk: no, the v_3′ is correct. The first three terms inside the norm compute the undeformed position of the third vertex, and we are comparing that to the position where we want to put it. Having v_3 wouldn’t make sense — for instance, imagine a translation of the whole shape one unit to the right. e_12 would be the same as e_12, but v_1′ would be one unit to the right. If you subtract the original v_3 you would conclude that you have a deformation of one unit, when in fact a simple translation of the whole triangle ought to count as zero deformation.
I am a little confused as to how you are supposed to calculate the values of the b-vector. I understand the parallel between this and the poisson image editing in the sense that if a vertex is fixed, you treat its components as constants in the deformation equations (and thus move the constants to the right hand side of the equation), but you don’t know the values of these constants during the setup stage (namely, you don’t know Y), so what are you supposed to do?
If you construct it in the solving stage instead, I don’t see an easy way to do this without being given the triangles.
Every time you ADD a pin or REMOVE a pin, do you have to call setup again? This is what I interpreted, but I just want to make sure I’m thinking correctly.
Thanks.
@sac76: The b that you return from the setup stage does not necessarily have to be the b that will be used to solve the system Ax=b (and in fact it can’t be because as you said you don’t know Y). However, since you get to choose how to parse that b in your solve stage, you can store something useful (such as the columns of A corresponding to the pinned vertices) and then perform the final adjustments on b before you actually solve the system.
@fk: You don’t have to worry about calling setup since the framework will do that automatically for you. You are right though that changing the vector of pinned vertices f would necessitate a new call to deformation_setup().
@Manolis
I’m confused what you mean by “…you can store something useful (such as the columns of A corresponding to the pinned vertices)”. From my understanding, A has (numberVertices – numberPinnedVertices) columns in it, so how would you have a column in A corresponding to pinned vertices?
Let’s say that given a triangle with vertices (v1′, v2′, v3′), you have the deformation for v1x’ given by (1-alpha)*v1x’ + beta*v2x’ – v3x’ (obviously this is not a correct formula, but just for demonstrative purposes), but v2x’ is a fixed point. Therefore, you need to move the quantity beta*v2x’ to the rhs in b because it is a constant. There can be multiple fixed points per deformation equation too. I’m confused as how to encode this.
for setup stage for problem 3, does b equal to 0? Because no vertex is pinned, every x and y will be a free variable. Thanks!
What exactly is abg? It’s not a parameter is the provided code but it is in the writeup. I’m guessing alpha beta gamma, but if that is so then do we not need to solve for these, they are given?
For part1, my program manages to calculate the A and b vectors, and it solves for x using these… but then it runs into a problem in lindeformer.m
My A matrix is 6m*2n and my X matrix is 2n*1.
This is what the error states:
————————————-
??? Error using ==> set
Vertices array must have at least 2 and at most 3 columns (or be empty)
Error in ==> lindeformer>figure1_WindowButtonMotionFcn at 209
set(handles.image.gfx1, ‘vertices’, deformation_solve(handles.A, handles.b, handles.cvIdx, handles.cv));
———————————–
I’m pretty sure my code is correct, and I don’t know what to do about this error. Could someone post a correct value of what x = A\b is for the given inputs T.mat and X.mat? That way I can check if the part of the code that I wrote has a bug.
Thanks.
We are having trouble setting up A. For each E_j, we cannot figure out how to multiply R by an individual x or y component (in the BRe’ term). We are also unsure about how to handle the fact that each E_j is a norm. We can’t figure out how to incorporate this into each individual coefficient in A. Thanks
Are the alpha and beta in the deformation equation based on the previous values of v1, v2, and v3, not v1′, v2′, and v3′?
@fk: Although the vector you use in the least squares system is 2n by 1, the matrices X and X_new through which you communicate with the framework are 2 by n. You’ll need to reshape() or otherwise reorganize your solution vector back into the 2 by n format.
@Kevin: Sorry, abg is a duplicate of G. You can ignore it.
@jmd: Yes, the values for alpha and beta in the deformation equation are computed from the original positions (unprimed variables).
@sac76: If you write down the 6m by 2n matrix A_full that you’d use to compute deformation without considering the constraints, the 6m by 2(n-p) matrix A that you use in your system differs from A_full by the removal of some columns; Manolis means that one reasonable plan would be to pass these columns in b. These columns contain the information about which rows of the system interact with the pinned vertices.
@cjl: You can’t multiply R by an individual component, but each component of the product of R and the 2-vector e_{ij} depends on the individual components of v_i and v_j. The norm in the definition of E naturally fits into the least squares problem definition: your A just produces the components of the vectors inside the norm signs, and then when you take the norm of Ax-b, that’s where the norms come from.
@ky: There are a few different ways to set this up, some of which don’t need to return a second value in b, and letting b be zero in that case makes sense.
e12=v2-v1 when you are trying to find location of v3′. What about when you are trying to find the deformation for the other two vertices? are you still using e12=v2-v1 in your formula? And what about the formula for alpha and beta. Are you substituting them into the equation for error? alpha= (v3-v1)*e12/||e12||^2… are you using this exact equation? v3 and v1? and e12? I don’t know if I made myself clear…
I understand that A is the matrix for the whole mesh and it has 6t columns where t is the number of triangles, but isn’t it possible that some triangles are untouched, its vertices not modified? In that case, are the six rows in A for that triangle full of zeros?
The way our code runs right now, the fixed points move correctly, but every other point seems to go crazy and move by some crazy amount (as in dragging a fixed point every so slightly causes the rest of the points to move by a large amount). If we re-check “Add pins”, everything goes back to the way it started. Any ideas why this might be happening?
Thanks
so the handout says Ej(v1′, v2′, v3′) = ||v1′ + alpha*e12′ + beta*R*e12′ -v3′|| is the deformation of a vertex. Is minimizing this deformation the same as encoding the equation into a row of A and b?
@student: The handout defines a measure called E_j(v1′, v2′; v3′) that measures the deformation of v3′ in terms of the positions of v1′ and v2′. Then in the equation starting E^2 that adds up the whole system, it uses E_j(v1′, v2′; v3′) (same as before) but then E(v2′, v3′; v1′) (which is the deformation of v1′ relative to the edge from v2′ to v3′) and E(v3′, v1′; v2′) (which is v2′ relative to v3′->v1′). So each vertex is measured relative to the opposite edge.
Regarding the triangles that are not directly involved in any constraints: because they are connected to the rest of the shape, which is ultimately connected to the pins, they are indeed relevant to the solution.
@fml: Your symptom is what will happen if there’s something substantially wrong with the system that you solve: the pins will go where they are supposed to, but all the rest of the vertices will go somewhere insane.
@fmlAsWell: Yes, you minimize this by encoding what’s inside the norm signs into some rows of the system. Then once all the rows are stacked up, solving the least-squares system results in minimizing the sum of squares of all the deformations of all the triangles.
@fml: One small mistake I made that caused my system to behave badly as yours seems to was that I forgot to include the minus sign when I brought the columns of the fixed points onto the b side, so all my results were the negative of what they should have been. Try to add a negative to your Ax = b solution to all the points except the fixed ones and see if this helps.
I am not sure how to get alpha and beta.. the formula for that changes depending on which vertex you are looking at. Do we write a function for alpha/beta?
Hey, I am wondering what use is g in the solve_deformation2 function?
is X_new n by 1 or (n – p) by 1?
Also, Is there an easy way to remove columns from a Matlab matrix?
@student: You are right that there is a change when you consider each vertex but the formula itself doesn’t have to be modified. One simple thing to do is to just relabel your current vertex so that it is always v3 and the other two vertices are v1 and v2 (i.e. use the same mental model as the diagram in the handout).
@hiThere: g is a vector of length p containing the triangle indices for each pinned point (this tells you what triangle each pinned point lies in).
@dhg57: Given that your A matrix will only contain columns for non-pinned points, the vector for which you solve is 2*(n-p) by 1. However, X_new should contain the pinned points as well and ends up being a 2 by n matrix (two rows for the two dimensions). This means you will need to splice together your results and known values in matrix Y to form the final X_new.
Removing columns can be done by indexing into a matrix. For example if I wanted to remove column 3 from A, I can form a logical vector to index into A:
f = true(1,n); f(3) = false;
A_reduced = A(:,f);
how do we test our code to see if it works.. I called lindeformer and clicked around but nothing happens… Am I supposed to edit lindeformer? Because it behaves as if I have not made any changes to deformation_setup or solve..
@student: After you select the vertices you want to drag, uncheck the Add Pins box in the File menu. You can then drag the vertices.
After I choose my pins, and begin to move one, the image gets completely jumbled, but dragging vertices around seems to have the desired effect. Is this likely a result of setup being incorrect but solve being correct?
@student2: If you mean that the unpinned vertices fly off to infinity when you say that the image is completely jumbled then that probably means that the matrix A and vector b that you created are not entirely correct. The pinned vertices will never behave erratically because their positions are enforced.
@student2: You may need to sort your Y. You can tell if this is the case when the pins switch their locations as soon as you move one.