Quiet: Faster Belief Propagation for Images and Related Applications

1 Introduction

Markov random fields is one of the popular graphical models in AI and machine learning [Nakatsuji and Fujiwara, 2014; Fujiwara et al., 2014; Shiokawa et al., 2013; Zhu et al., 2008]. Belief propagation is known to be very effective in performing inference on Markov random fields [Choi and Darwiche, 2008]. It was first applied to infer the label of each node by solving the energy minimization problem [Sun et al., 2003; Weiss and Freeman, 2001]. The label of a node represents some property in the real world such as the same object or the disparity in given images, where nodes correspond to pixels. Belief propagation performs inference by iteratively updating messages between nodes for each label. While belief propagation was originally intended for graphical models without loops, for which it is guaranteed to provide the globally optimal solution, it is empirically effective on a number of loopy graphical models including Markov random fields [Cozman and Polastro, 2008].

Due to its effectiveness and solid theoretical foundation, belief propagation is used by many applications. For example, stereo matching is one of the most popular applications [Ogawara, 2010]. It is exploited to extract 3D information from digital images, and is highly important in the fields of telecommunications and robotics since depth information allows for a system to separate occluding image components [P´erez and S´anchez, 2011]. Another popular application is the computation of optical flow [Lipski et al., 2010]; optical flow is the apparent motion of the brightness pattern between images [Szeliski, 2010]. It can be used in image morphing to change an image into another through a seamless transition in the field of computer art [Lipski et al., 2010]. Other than above, belief propagation is used in a variety of applications such as image restoration [Felzenszwalb and Huttenlocher, 2006], computer-assisted colorization [Noma et al., 2009], and image segmentation [Zhao et al., 2014]. We omit detail descriptions due to the space limitations.

Although belief propagation is effective in various applications, one of the most important research concerns is its speed since a naive approach of belief propagation incurs quadratic computation cost in the number of labels [Sun et al., 2003; Weiss and Freeman, 2001]. If N, K, and T are the number of nodes, labels, and iterations, respectively, it needs O(NK2T) time. The proposal by Felzenszwalb et al. can reduce the computation cost from O(NK2T) to O(NKT) [Felzenszwalb and Huttenlocher, 2006; 2004]; it is linear in the number of labels. Their approach is now regarded as the standard approach in implementing belief propagation [P´erez and S´anchez, 2011]. However, current belief propagation applications involve many nodes (pixels); this indicates that N can have large a value. In the early 2000's, when belief propagation was first applied to the inference problem [Sun et al., 2003; Weiss and Freeman, 2001], image size was around 640 × 480 or so. Recently, images of 1280 × 720 pixels must be processed in real-time to realize 3D telepresence systems [P´erez and S´anchez, 2011]. Moreover, recent optical flow-based image morphing systems must process 1920×1080 images [Lipski et al., 2010]. To increase the processing speed, Ogawara proposed to enhance the standard approach by averaging the outgoing messages from the nodes [Ogawara, 2010]. Although it is more efficient than the standard approach by reducing the number of updated messages, the computation cost of their approach is O(NKT ); the same as the standard approach. Furthermore, its inference results are different from those of the standard approach. Sacrificing the inference results makes it difficult to realize truly effective applications [Fujiwara et al., 2013].

This paper proposes Quiet a novel, highly-efficient algorithm for belief propagation that provably guarantees to output the same inference results as the standard approach. In order to reduce the computation cost, we dynamically skip unnecessary updates by identifying converged messages in each iteration. This approach reduces the computation cost from O(NKT) to O(MKT), where M is the average number of message updates in the given image and we have M ≪N. Experiments demonstrate that our approach cuts the processing time by over 80% from the standard approach.

The remainder of this paper is organized as follows. Section 2 briefly reviews the existing approaches. Section 3 details our approach. Section 4 reviews the results of our experiments. Section 5 provides our conclusion.

2 Preliminary

This section briefly reviews the standard approach by Felzenszwalb et al. and the approximate variant by Ogawara. This paper focuses on the pairwise model since the higher-order models are not general to use in applications compared to the pairwise model as described in [Zikic et al., 2010]. However, our approach can be easily applied for other models [Singla et al., 2014; Sato, 2007].

Let P, L, and f be the set of pixels in an image, a set of labels, and a function that assigns label li ∈L to each pixel p∈P, respectively. Inference quality of a labeling is given by energy function E(f):

where N are the neighbor edges in the four-connected image grid. Dp(li) is the matching cost of assigning label li to pixel p which is set to suit the application. For example, in stereo matching, the matching cost is typically set as follows:

In this equation, label li is a non-negative integer, and Il(x, y) are the values of pixel p = (x, y) of the left image, and Ir(x, y) the values of pixel p = (x, y) of the right image [Ogawara, 2010]. τ is a positive constant to suppress the effect of outliers. In addition, Vpq(li, lj) is the smoothness cost of assigning label li and lj to neighboring pixels p and q, respectively. The most widely used smoothness cost is Potts model, which can prevent edge oversmoothing [Chen et al., 2012]. Potts model takes the following form:

In this model, the cost is zero for equal labels and a positive constant, d, for different labels (i.e., d > 0). Finding a labeling with minimum energy corresponds to the inference problem for the graphical model of the given image as described in the previous papers [Felzenszwalb and Huttenlocher, 2006; 2004]. In order to optimize the labeling, belief propagation iteratively passes messages around the graph according to the connectivity given by the edges the same as other approaches in machine learning [Nakatsuji et al., 2014; Fujiwara and Irie, 2014; Farahmand et al., 2010; Chen et al., 2009]. Each message is a vector whose dimension is given by the number of labels, K. In particular, the max-product algorithm is used to find an approximate minimum cost labeling of the energy function [Fujiwara et al., 2011]. If mtpq (lj) is the message of node p to node q for label lj in the t-th iteration, the message is iteratively computed as follows:

where N(p) \ q are the neighbors of node p other than q. In addition, mtpq (lj) is the normalized message of mtpq (lj) which is computed to prevent overflow/underflow [Martin et al., 2011]. Note that mtpq (lj) and mtpq (lj) are initialized to zero. After T iterations, label l∗ q at node q is selected by using the following equation:

The naive implementation of belief propagation requires O(NK2T) time; it is quadratic in the number of labels. Therefore, reducing the computation cost of belief propagation is crucial to enhancing its usefulness.

In order to reduce the computation cost, the proposal of Felzenszwalb et al. exploits three techniques [Felzenszwalb and Huttenlocher, 2006; 2004]. The first technique computes message updates efficiently. They express Equation (4) as follows with the Potts model of Equation (3):

where htp (li) is computed as follows:

In Equation (6), the minimization over label li is performed once independently of the value of lj ; we can update the message in linear time w.r.t. the number of labels. Their second technique updates messages to every other pixel on even iterations and vice versa on odd iterations. This technique eliminates the need to store messages from the previous iteration when updating current messages. Their multi-level technique runs the belief propagation algorithm in a coarseto-fine manner. It efficiently computes messages over longrange distances by progressively increasing the resolutions to get estimates for the messages at the next finer level; the bth level corresponds to a labeling problem where blocks of 2b-1 × 2b-1 pixels are grouped together (b ≥ 1). By using the three techniques, their approach reduces the computation cost fromO(NK2T) to O(NKT), and is now regarded as the standard approach to implementing belief propagation [P´erez and S´anchez, 2011].

Ogawara proposed to use approximate values of messages to enhance the processing speed of the standard approach [Ogawara, 2010]. Specifically, their approach updates messages as follows:

where |N(p)| is the number of nodes included in N(p). In the original algorithm, messages have different values even if they are sent from the same node as shown in Equation (4). However, in the approximate approach, all messages from a node are made identical to each other. Therefore, the number of message updates for a node is reduced to 1 from the |N(p)| of the original algorithm. However, while their approach is more efficient than the standard approach, it does not guarantee the same inference results as the standard approach. In addition, their approach requires O(NKT) time which is the same as the standard approach.

3 Proposed Approach

This section introduces Quiet, our efficient approach for belief propagation; it gives the same inference results as the standard approach. We first give an overview and then a full description. We also give theoretical analyses and extensions of our approach in this section.

3.1 Adaptive Message Update

The second technique of the standard approach updates messages to every other pixel in even iterations and vice versa in odd iterations as described in the previous section. It splits the nodes into two sets by coloring the pixels of the image in a checkerboard pattern. As a result, messages can be divided into two sets based on the nodes that send the messages. Let M, Me, andMo be the set of all the messages, the set of messages updated at even iterations, and the set of messages updated at odd iterations, respectively; we have Me ∪Mo = M andMe ∩Me = ∅. In Equation (4), messages inMe can be computed only by the messages in Mo and vice versa. The standard approach exploits this property to reduce memory cost. However, the standard approach still incurs high computation cost, especially for images of high-resolution since they entail large numbers of nodes and messages.

We reduce the computational cost of the standard approach by skipping unnecessary message updates. This technique is based on the observation that the exactly same values of messages are repeatedly sent for most pairs in the iterations; we call these messages convergence. By exploiting this property, we dynamically update the messages only if values of the messages can be changed by the updates in each iterations. Since we can skip most messages, we can reduce the computational cost of the standard approach.

This section first defines the set of messages whose values are updated in the current iteration. It next shows three properties of converged messages. Finally, it introduces the property of the set of updated messages by utilizing the three properties.

Let l′p be the label that gives the minimum value of ht-2 p (li), i.e., l′p = argminli∈L{ht-2 p (li)}, and mtpq be the set of messages that are sent from node p to node q in the t-th iteration, i.e., mtpq = {mtpq (lj) : lj ∈ L}. The set of messages whose values will be updated in the t-th iteration (t ≥ 1), Ut, is given as follows:

Definition 1 When t ̸= 1, message set mt+1 pq is included in Ut+1 if at least one of the following conditions holds for message mtsp (li);

1. mtsp (li) ̸= mt-2 sp (li) and li = l′p ,

where mtsp (li) ∈ Ut and s ∈ N(p)\q. If t = 1, we have Ut =Mo.

In order to describe the property that defines the set of updated messages Ut, we introduce the three cases of converged messages for label li ∈ L where (1) li = l′p , (2) li ̸= l′p and ht-2 p (li) ≥ ht-2 p (l′p ) + d, and (3) li ̸= l′p and ht-2 p (li) < ht-2 p (l′p ) + d. Note that these three case are mutually exclusive. The three properties on the converged messages are as follows (proofs are shown in Appendix);

Lemma 1 For label l′p , mt+1 pq (l′p ) = mt-1 pq (l′p ) holds if we have (1) mtsp (l′p ) = mt-2 sp (l′p ) for all node s such that s ∈ N(p)\q and (2) htp (li) ≥ ht-2 p (l′p ) for all label li such that li ̸= l′p .

Lemma 2 For label li such that li ̸= l′p and ht-2 p (li) ≥ ht-2 p (l′p )+d, we havemt+1 pq (li) =mt-1 pq (li) if (1) mtsp (l′p ) = mt-2 sp (l′p ) holds for all node s such that s ∈ N(p) \ q and (2) htp (li) ≥ ht-2 p (l′p ) +d holds for all label li such that li ̸= l′p .

Lemma 3 We have mt+1 pq (li) = mt-1 pq (li) for label li such that li ̸= l′p and ht-2 p (li)<ht-2 p (l′p )+d if we have mtsp (li)= mt-2 sp (li) for all node s such that s ∈ N(p) \ q where (1) li = l′p or (2) li ̸= l′p and ht-2 p (li)<ht-2 p (l′p )+d.

Lemma 1, 2, and 3 correspond to the three cases in Definition 1. By exploiting these lemmas, we introduce the property of set of updated messages Ut as follows:

Lemma 4 If message mt+1 pq is not included in the set of updated messages Ut+1, mt+1 pq (lj) = mt-1 pq (lj) holds for all messages such that mt+1 pq (lj) ∈mt+1 pq .

Proof We consider three cases of label li ∈ L for message mt+1 pq (li); (1) li = l′p , (2) li ̸= l′p and ht-2 p (li) ≥ ht-2 p (l′p )+d, and (3) li ̸= l′p and ht-2 p (li) < ht-2 p (l′p )+dwhich correspond to the three lemmas.

In the first case, from Lemma 1, we have mt+1 pq (l′p ) ̸= mt-1 pq (l′p ) if (1) mtsp (l′p)̸=mt-2 sp (l′p) holds where s∈N(p)\q or (2) htp (li)<ht-2 p (l′p ) holds where li ̸= l′p . If htp (li)<ht-2 p (l′p ) holds, htp (li)<ht-2 p (l′p )+d must hold for label li since d>0. Therefore, from the first and second conditions of Definition 1, mt+1 pq must be included inUt+1 if at least onemessage included in mt+1 pq is not converged in the (t+1)-th iteration.

In the second case, we have mt+1 pq (li) ̸= mt-1 pq (li) if (1) mtsp (l′p ) ̸= mt-2 sp (l′p ) where s ∈ N(p)\q or (2) htp (li) < ht-2 p (l′p ) + d holds from Lemma 2. Therefore, if at least one message included in mt+1 pq is not converged in the (t+1)-th iteration, mt+1 pq must be included in Ut+1 from the first and second conditions of Definition 1.

In the third case, mt+1 pq (li) ̸= mt-1 pq (li) holds if we have mtsp (li) ̸= mt-2 sp (li) for node s such that s ∈ N(p)\q where (1) li = l′p or (2) li ̸= l′p and ht-2 p (li) < ht-2 p (l′p )+d from Lemma 3. As a result, from the first and third conditions of Definition 1, mt+1 pq must be included in Ut+1 if at least one message included in mt+1 pq is not converged in the (t+1)-th iteration. ✷

Lemma 4 indicates that, a message can change its value in the (t+1)-th iteration only if the message is included in the set of updated messages Ut+1. As shown in Definition 1, we can compute Ut+1 without messages in the (t+1)-th iteration. Therefore, we can dynamically identify messages whose values are to be updated in the (t+1)-th iteration from the messages of the t-th iteration which makes it possible to improve the efficiency.

Algorithm 1 Quiet

1: for b = B to 1 do 2: for each message do 3: if b = B then 4: initialize the message to zero; 5: else 6: initialize the message by the results of the previous level; 7: U1 =Mo; 8: for t = 1 to T do 9: for each mtsp (li) ∈ Ut do 10: compute mtsp (li) from Equation (4); 11: compute mtsp (li) for mtsp (li); 12: Ut+1 = ∅; 13: for each mtsp (li) such that mtsp (li) ∈ Ut do 14: if mtsp (li) ̸= mt-2 sp (li) and li = l′p then 15: add mt+1 pq toUt+1 where q ∈ N(p)\s; 16: if li ̸= l′p and htp (li) < ht-2 p (l′p ) + d then 17: add mt+1 pq toUt+1 where q ∈ N(p)\s; 18: if mtsp (li)̸=mt-2 sp (li), li̸=l′p , and ht-2 p (li)<ht-2 p (l′p )+d then 19: add mt+1 pq toUt+1 where q ∈ N(p)\s; 20: for each node do 21: determine the label of the node from Equation (5);

3.2 Algorithm

Algorithm 1 gives the full description of our approach, Quiet. Similar to the previous approximate approach [Ogawara, 2010], it is based on the standard approach [Felzenszwalb and Huttenlocher, 2006; 2004] which utilizes the multi-level technique. In Algorithm 1, B is the number of levels. Note that, in the b-th level, blocks of 2b-1 ×2b-1 are grouped together as described in Section 2. Algorithm 1 first initializes the messages to zero if b = B (lines 3-4). Otherwise, it initializes the messages by the results of the previous level (lines 5-6). The details of these processes are shown in the previous papers [Felzenszwalb and Huttenlocher, 2006; 2004]. In the iterations, it updates messages that are included in Ut from Equation (4), and it normalizes messages (lines 9-11). By using the normalized message, it determines the set of updated messages Ut+1. If mtsp (li) ̸= mt-2 sp (li) holds where li = l′p , message set mt+1 pq is included in the set of updated messages Ut+1 from the first condition of Definition 1 (lines 14-15). In addition, if htp (li) < ht-2 p (l′p ) + d holds where li ̸= l′p , mt+1 pq is added to Ut+1 from the second condition of Definition 1 (lines 16-17). Similarly, if we have mtsp (li) ̸=mt-2 sp (li), li ̸=l′p , and ht-2 p (li)<ht-2 p (l′p ) + d, mt+1 pq is added to Ut+1 from the third condition of Definition 1 (lines 18-19). After the iterations, it determines the label of each node (lines 20-21).

3.3 Theoretical Analyses

We introduce the properties of our approach in this section. The first property is the inference results of our approach:

Theorem 1 Algorithm 1 outputs exactly the same results as the standard algorithm of belief propagation.

Proof Prior to proving Theorem 1, we first prove that we have Ut ⊆ Mo in the odd iterations and Ut ⊆ Me in the even iterations by mathematical induction.

Initial step: We have U1 =Mo from Definition 1. As shown in Definition 1 and Lemma 4, a message is included in Ut+1

only if the message can change its value by update in the t-th iteration. In addition, messages included in Me are updated from messages included in Mo by using Equation (4). As a result, since U1 =Mo, it is clear that U2 ⊆Me.

Inductive step: From Lemma 4, if a message is not included in Ut, the message cannot change its value in the t-th iteration. Therefore, we can identify unconverged messages in the (t+ 1)-th iteration fromUt. In addition, messages inMo can be computed only by the messages in Me and vice versa. Thus, it is clear that we have Ut+1 ⊆ Mo and Ut+1 ⊆ Me in the odd and even iterations, respectively, if Ut ⊆ Mo and Ut ⊆Me hold in the odd and even iterations, respectively.

Therefore, from the result of the mathematical induction and from Lemma 4, we can compute messages exactly the same as the standard approach which computes messages included in Mo and Me in even and odd iterations. Consequently, our approach provably guarantees the same inference results as the standard approach. ✷

As described in Section 2, the standard approach needs O(NKT) time. We have the following property for the computation cost of our approach:

Theorem 2 If M is the average number of updated messages in the given image, Algorithm 1 requires O(MKT) time.

Proof As shown in Algorithm 1, our approach iteratively updates and normalizes messages; these processes need O(MKT) time. It then determines the set of updated messages Ut+1. As shown in Algorithm 1, we can compute Ut+1 from the messages included in Ut. Thus, this process also requires O(MKT) time. As a result, our approach needs O(MKT) time. ✷

Theorem 1 and 2 indicate that we can obtain the inference results more efficiently than the standard approach without sacrificing the inference results.

3.4 Extension of Quiet

The previous sections assumed the use of the Potts model and the max-product algorithm for belief propagation. This section briefly describes the extension of our techniques through the use of other models and the sum-product algorithm.

Even though the Potts model is the most popular approach in many applications to the smoothness cost used in Markov random fields [Chen et al., 2012], we can also use the truncated linear model and the truncated quadratic model, both are very well known and are given as follows [Felzenszwalb and Huttenlocher, 2006; 2004]:

where c is the rate of increase in the cost, and d determines when the increase stops. As shown in Equation (10), the truncated linear model increases the cost linearly based on the amount of difference between label li and lj while the truncated quadratic model quadratically increases the cost as shown in Equation (11). For these models, our approach determines the set of updated messages as follows:

where li ∈L. By using this technique, we can obtain the same inference results as the standard approach in O(MKT) time although we omit the proof due to space limitations.

While the max-product algorithm based belief propagation is utilized in many applications [Ogawara, 2010; Noma et al., 2009], the sum-product algorithm can be used for belief propagation. The sum-product based belief propagation computes the posterior probability by selecting the most probable label for each pixel. It updates the messages as follows:

whereΨpq(li,lj)=e-Vpq(li,lj) andΦp(li)=e-Dp(li) . The standard approach updates the message at O(NKT) time in the following manner by using the box sum method as described in the previous paper [Wells, 1986]:

where gt-1 p (li)=Φp(li) ∏s∈N(p)\q mt-1 sp (li). Equation (13) and (14) indicate that the sum-product algorithm updates messages by computing the sums of messages instead of taking the minima of messages as done by the max-product algorithm. Therefore, it is clear that our approach can be directly exploited to enhance the processing speed for sum-product algorithm based belief propagation.

4 Experimental Evaluation

We perform stereo matching to compare our approach to the standard approach [Felzenszwalb and Huttenlocher, 2006; 2004] and the approximate approach [Ogawara, 2010]. We used Art, Moebius, Shopvac, Flowers, and Umbrella images obtained from the Middlebury Stereo Datasets 1 ; their sizes are 1390 × 1110, 1390 × 1110, 2356 × 1996, 2772 × 1980, 2880×1980, and 2960×2016, respectively. The six images are shown in Figure 1. In this section, "Quiet", "Standard", and "Approximate" represent the results of our approach, the standard approach, and the approximate approaches, respectively. In the experiments, we set the number of labels, K = 100, the number of iterations in each level, T = 50, the number of levels, B = 4, and the parameter of the Potts model, d = 20, by following the previous paper [Felzenszwalb and Huttenlocher, 2004]. All experiments were conducted on a Linux 2.70 GHz Intel Xeon server.

4.1 Efficiency

We evaluated the processing time of each approach. Figure 2 shows the results. In addition, Figure 3 shows the numbers updated messages in the iterations for Art dataset and Table 1 details the numbers of messages updated by each approach where b = 1. Since we dynamically skip unnecessary message updates in the iterations, Table 1 shows the average numbers of updated messages for our approach.

Figure 2 shows that our approach is much faster than the previous approaches; our approach cuts the processing time by up to 82% and 75% from the standard and the approximate approaches, respectively. As described in Section 2, the standard approach updates all messages in each iteration. In addition, the approximate approach reduces the number of updated messages by using approximate values for messages to raise inference efficiency. However, the approximate approach incurs the same computation cost as described in Section 2. On the other hand, since most messages reach convergence in a first few iterations, our approach effectively limits the updated messages whereas previous approaches update constant numbers of messages in the iterations as shown in Figure 3. As a result, our approach reduces the number of updated messages in the iteration by detecting the converged messages as shown in Table 1. Thus, our approach has better processing speed than the previous approaches.

1 http://vision.middlebury.edu/stereo/data/

(e) Flowers

(f) Umbrella

Figure 1: Dataset.

4.2 Effectiveness

One major advantage of our approach is that it outputs the same results as the standard approach of belief propagation while the approximate approach yields different results. In this section, we evaluated the precision of the inference results by the proposed approach and the approximate approach against the standard approach. Precision is the fraction of inference results of an approach that match the inference results of the standard approach. Precision takes a value between 0 and 1; precision is 1 if the inference results are identical to those of the standard approach. We show precision of each approach in Figure 4.

Figure 4 shows, as expected, the precision of our approach is 1 under all conditions examined. This is because our approach has the theoretical property that the inference results are same as the standard approach, see Theorem 1. In contrast, the approximate approach has precision under 1; the approximate approach and the standard approach output different inference results. This is because, in the approximate approach, all the messages from the same node are made identical to each other, even though the messages actually have different values in the standard approach.

Figure 4, along with Figure 2, indicates that the approximate approach enhances the processing speed by sacrificing the quality of inference results. On the other hand, our approach achieves higher processing speed than the previous approaches while its inference results replicate those of the standard approach. This indicates that our approach is an attractive option for the research community in performing belief propagation.

5 Conclusions

In this paper, we proposed an efficient algorithm that gives the same inference results as the standard approach to belief propagation. The proposed approach skips unnecessary updates by detecting the converged messages in each iteration to enhance the processing speed. Experiments showed that the proposed approach achieves high efficiency without sacrificing inference quality; our approach outputs the same results as the standard approach unlike the approximate approach. The proposed approach will allow many applications to be processed more efficiently, and help to improve the effectiveness of future applications.

Appendix

In this section, we show proofs of Lemma 1, 2, and 3.

Lemma 1

Proof From Equation (6), we have

since we have minli {ht-2 p (li)} = ht-2 p (l′p ) from the definition of l′p .

In addition, from Equation (7), if we have mtsp (l′p ) = mt-2 sp (l′p ) for all s such that s ∈ N(p)\q,

Therefore, from Equation (6), we have

If htp (li) ≥ ht-2

As a result, mt+1 pq (l′p ) = ht-2 p (l′p ) from Equation (17) and (18). Therefore, from Equation (15), we have mt+1 pq (l′p ) = ht-2 p (l′p ) =mt-1 pq (l′p ). ✷

Lemma 2

Proof From Equation (6) and the definition of l′p , we have

for label li such that li ̸=l′p and ht-2 p (li)≥ht-2 p (l′p )+d. In addition, for all such label li, if htp (li)≥ht-2 p (l′p )+d,

since d > 0 holds. As a result, we have

since htp (l′p ) = ht-2 p (l′p ) holds if mtsp (l′p ) = mt-2 sp (l′p ) for all node s such that s ∈ N(p)\q from Equation (7). Therefore, if we have htp (li) ≥ ht-2 p (l′p ) +d,

from Equation (6). As a result, from Equation (19) and (22), mt+1 pq (l′p ) = ht-2 p (l′p ) +d =mt-1 pq (l′p ) holds. ✷

Lemma 3

Proof If the condition of Lemma 3 holds, for all s such that s ∈ N(p)\q, we have

where (1) li = l′p or (2) li ̸= l′p and ht-2 p (li)<ht-2 p (l′p )+d from Equation (7). Therefore, from Equation (6),

Precision