Questions about the computing time and `unwrap_arbitrary` inputs

[kanglcn]

Thank you a lot for creating this open phase-unwrapping package! This is indeed what I am searching hard.

I have some questions about the implementation of

1. I think you implement the edgelist algorithm. As far as I know, this algorithm minimizes L1 as the mcf method. Why this algorithm is NP-hard while mcf is not? Does it mean the edgelist is much slower than mcf?
2. How should I generate the edges and simplices in unwrap_arbitrary?

Thanks!

[yoyololicon]

Hi @kanglcn, I'm glad you're interested in this tool!

1. I think you implement the edgelist algorithm. As far as I know, this algorithm minimizes L1 as the mcf method. Why this algorithm is NP-hard while mcf is not? Does it mean the edgelist is much slower than mcf?

Yeah, you're right; the edgelist method is equivalent to MCF (just a different formulation). Thus, it shouldn't be NP-hard. I guess it means they belong to a subset of ILP problems that can be solved in polynomial time (correct me if I'm wrong). I'll have a look at this and revise the README if needed. In practice, assuming using the same solver for MCF and edgelist, I found sometimes edgelist has a slightly smaller equation matrix $\mathbf{A}$ and thus is faster to compute.

2. How should I generate the edges and simplices in unwrap_arbitrary?

I assume you have $N$ wrapped phase and their coordinates in an $M$-dimensional space ($\mathbf{\theta} \in \mathbb{R}^{\mathbf{N} \times \mathbf{M}}$). You can use the Delaunay or Convex Hull algorithm in SciPy to connect the points into a graph. They'll also compute the simplices for you. https://docs.scipy.org/doc/scipy/reference/generated/scipy.spatial.Delaunay.html#scipy.spatial.Delaunay

I hope this helps.

[kanglcn]

Thanks @yoyololicon for your reply!

2. How should I generate the edges and simplices in unwrap_arbitrary?

I assume you have N wrapped phase and their coordinates in an M-dimensional space (θ∈RN×M). You can use the Delaunay or Convex Hull algorithm in SciPy to connect the points into a graph. They'll also compute the simplices for you. https://docs.scipy.org/doc/scipy/reference/generated/scipy.spatial.Delaunay.html#scipy.spatial.Delaunay

How can I get the edges from simplices? For given simplices, is edges uniquely determined? If so, I think there is no need to use it as an input to unwrap_arbitrary. If not, will it affect the final phase unwrapping result?

Another question, what is the meaning of $A$ in the README? And what does $Ak = -A\frac{x}{2\pi}$ mean? It does not show in the edgelist paper.

[yoyololicon]

Hi @kanglcn ,

From simplices to edges:

edges = np.unique(np.stack((simplices, np.roll(simplices, 1, 1)), 2).reshape(-1, 2), 0)

unwrap_arbitrary requires edges to be always presented, while simplices is optional because some graphs are not simply compositions of simplices. If no simplices are given, the edgelist method is used. And yes, if the simplices are given, then it should be composed of the given edges.

$\mathbf{A}$ and the equation directly relate to Figure 1 in the edgelist paper. Depending on which method you're using, each row in $\mathbf{A}$ represents an elementary cycle (i.e., a, b, and c nodes in the figure) or an edge (ab, ac, or bc).

[kanglcn]

Thanks for the explanation!