I have the energy function that I would like to minimize as: $$\sum_{\{i, j\}}((h_i - h_j) - q_{ij})^2$$ This is applied over a 2D grid, where $q_{ij}$ is the relative height between two cells $i$ $j$, and $h_i$ is the absolute height of the cell that I am trying to find. Note that $q_{ij}$ is only non-zero for the 4-neighborhood of each cell i.e. directly adjacent ones. I was given a hint that this can be formulated as a Poisson problem but I've not been able to get there.

This is my current attempt:

We can expand this given energy to get: $$\sum_{\{i, j\}} (h_i^2 -2h_i h_j -2h_i q_{ij} + h_j^2 +2h_j q_{ij} + q_{ij}^2)$$

Which is then equivalent to the individual sums: $$\sum_{\{i, j\}}(h_i^2) -2\sum_{\{i, j\}}(h_i h_j) -2\sum_{\{i, j\}}(h_i q_{ij}) + \sum_{\{i, j\}}(h_j^2) +2\sum_{\{i, j\}}(h_j q_{ij}) + \sum_{\{i, j\}}(q_{ij}^2)$$

I then define the column vector $H$ as the vector with all values of $h_i$ stacked on top of each other. I also define $M$ as the adjacency matrix between cells, which in this case would be a grid yielding the 4-neighborhood. Finally I define $Q$ as the matrix with the same sparsity pattern as $M$, but with values representing the relative height between $i$ and $j$.

With $H$, $M$ and $Q$ I can write these sums in matrix form:

$$4H^TH -2H^T(MH) -2(QH)^TO + (MH)^T(MH) + 2(QMH)^TO + O^TQ^2O$$ Where $O$ is a vector of ones. My reasoning for the $1^{st}$ coefficient is that each $h_i$ will appear on the left of the sum 4 times.

From this point I can group similar terms:

$$H^T(4I -2M + M^2)H + H^T(2QM -2Q)O + O^TQ^2O$$

Which I write as: $$H^TAH + H^T(2QM -2Q)O + O^TQ^2O$$

I then use the reasoning from this question (which I admit to not fully understanding), to get my final system:

$$AH = (QM - Q)O,\quad A = 4I -2M + M^2$$

W̶e̶ ̶c̶a̶n̶ ̶w̶o̶r̶k̶o̶u̶t̶ ̶t̶h̶a̶t̶ ̶$̶A̶$̶ ̶i̶s̶ ̶a̶c̶t̶u̶a̶l̶l̶y̶ ̶$̶4̶I̶ ̶-̶ ̶L̶$̶ ̶w̶h̶e̶r̶e̶ ̶$̶L̶$̶ ̶i̶s̶ ̶t̶h̶e̶ ̶l̶a̶p̶l̶a̶c̶i̶a̶n̶ ̶m̶a̶t̶r̶i̶x̶. This to me doesn't look like a poisson problem, so I would like to know where I went wrong in the above workings? My understanding of what a poisson problem looks like is from the wiki page, so perhaps I've misunderstood?

Any hints or advice would be great, thank you.


My mistake was in the conversion to vectors and matrices. $(MH)^T(MH)$ should instead be: $4H^TH$

The reason being, that each cell shall be present as a neighbor to 4 other cells. This gives us: $$8H^TH -2H^T(MH) -2(QH)^TO + 2(QMH)^TO + O^TQ^2O$$ And when we work through with this equation, a standard Poisson problem does emerge. I also had a mistake on the final line, $QM - Q$ should instead be $Q - QM$. $$AH = \frac{1}{2}(Q - QM)O, \quad A = 4I - M$$


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.