Quality-Guided Path-Following Algorithm

Source: Two-Dimensional Phase Unwrapping: Theory, Algorithms, and Software, D. C. Ghiglia and M. D. Pritt (1998).

The unwrapping integration path uses a quality map to unwrap high-quality pixels first and low-quality pixels last.

The quality map defines the quality or goodness of each phase value (e.g., pseudocorrelation, variance of phase derivatives, maximum phase gradients, magnitude image, etc.).

“A starting pixel with a high-quality value is selected and its four neighbors are examined.  These neighbors are unwrapped and stored in a list called the ‘adjoin list.’  The algorithm then proceeds iteratively as follows: The list pixel with the highest-quality value is removed from the list, and its four neighbors are unwrapped and placed in the list.  (The pixels are sorted and stored in the list in the order of their quality values.)  If a neighbor has already been unwrapped, it is not placed in the list.  This iterative process of removing the highest-quality pixel from the list, unwrapping its four neighbors and inserting them in the list continues until all the pixels have been unwrapped.”

Figure 1: (A) The red pixels represent those that have been unwrapped.  (B) The adjoin list consists of the green pixels.  (C) If the pixel in the third row and the second column is selected from the list and unwrapped, then the adjoin list is updated as shown.

Flynn’s Minimum Discontinuity algorithm:

Source: Two-Dimensional Phase Unwrapping: Theory, Algorithms, and Software, D. C. Ghiglia and M. D. Pritt (1998).

The “fringe lines” created by phase wrap discontinuities separate the image into regions that are off by factors of 2p from each other.

The unwrapped pixel value jm,n equals the wrapped phase value ym,n plus an integer multiple (the “wrap count”) cm,n of 2p.

A discontinuity is defined to be a pair of (vertically or horizontally) adjoining pixels whose difference exceeds p in magnitude.

The vertical and horizontal jump counts are defined respectively by the equations:

vm,n = round( (jm,n - jm+1,n) / (2p ) ),
zm,n = round( (jm,n - jm,n+1) / (2p ) ).

The sum of the magnitudes of all the jump counts,

E = sum( |vm,n| ) + sum( |zm,n| )

is a measure of the overall severity of the discontinuities, and it is this measure that the algorithm is designed to minimize.

Figure 2: Close Relationship between the wrap counts and the jump counts. (a) The wrapped phase data of a pyramid. The dots indicate the pixels, the numbers indicate the phase values (scaled to the range 0-1), and the dashed lines indicate the fringe lines. This phase can be unwrapped by incrementing the wrap counts of the region enclosed by the dashed lines. (b) The jump counts are nonzero at the fringe lines, and the numbers indicate the jump count values. Incrementing the wrap counts as explained in (a) is equivalent to incrementing and decrementing the jump counts in the manner described in the text so that the jump counts all become zero, which indicates that the phase has been unwrapped.

Changes in wrap counts are represented by changes in jump counts and are accounted for using “nodes” and “edges”. An array of points, called nodes, is envisioned that is offset by 0.5 pixels horizontally and vertically from the phase data.

An edge is defined to be an arrow that connects a node to one of its four neighbors and defines a change in the jump count of the pair of pixels it separates.

By convention, a leftward/rightward edge is an increment/decrement of a vertical jump count.  Similarly, a downward/upward edge is an increment/decrement of a horizontal jump count.

The “value” of an edge from node (i,j) to (m,n), denoted dV(i,j,m,n), is defined to be 1 if the edge induces a decrease in the magnitude of the jump count and –1 if it induces an increase.

Figure 3: Nodes and edges that correspond to the phase unwrapping example of figure 2. The Squares represent the nodes, which are offset by ½ pixel horizontally and vertically from the pixels (represented by the dots). The arrows represent the edges, and their labels indicate the edge values. These edges represent the jump count changes that unwrap the phase, as explained in Figure 2. Notice that the edges define a loop that coincides with the dashed fringe lines of Figure 2.

An operation that has more positive edges than negative ones is called an “improving operation” or an “improving loop” and Flynn’s algorithm tries to find and apply these operations.

Improving loops are found by creating trees of nodes with the edges as links.  If an edge leads from one node to another, the first node is the “parent” and the second is the “child”.

Every node is either isolated, the root of a tree, or can be reached from the root of its tree by a unique path

Associated with each node (m,n) is its value, which is defined to be the sum of the values of the edges that lead to this node from its root (roots and isolated nodes have the value 0):
value(m,n) = sum( dV(mk,nk,mk+1,nk+1), k=0 to k=L-1).

The trees are created as follows:  Each pair of adjoining nodes is tested for the addition of an edge, unless an edge between the two nodes already exists.

The addition of an edge from node (i,j) to (m,n) results in value(m,n) being increased by
dval = value(i,j) + dV(i,j,m,n) – value(m,n).

if dval is negative, then the edge would result in the value of the node becoming negative or less than its old value and the edge is not added.

If dval is positive, the edge is added and value(m,n) is increased by dval.  Also, dval is added to all nodes in any subtrees branching from node (m,n) and any existing edge to (m,n) is removed.

Figure 4: An example of a set of trees. The yellow numbers are the nodes, and the arrows are the edges. The numbers indicate the values of the nodes and the edges. The two large arrows are new edges that can be added.

Figure 5: Trees that result from the addition of the two new edges indicated by the two new edges indicated by the large arrows of figure 4.

Flynn’s algorithm summary:

The horizontal and vertical jump counts are calculated.

The array of node values is initialized to zeros.

The nodes are repeatedly scanned and an edge is added if its value dval is positive.

If a loop is found, its jump counts are all updated, its edges removed, and the values of its nodes and subtrees are updated accordingly

The wrap counts are calculated from the jump counts and added to the input phase data to get the unwrapped solution.

The process ends what a complete scan adds no new edges and removes no loops.

Note: Given a quality map, weights can be applied to the jump counts to achieve a minimum weighted discontinuity solution.