METHOD AND DEVICE FOR EFFICIENT PARALLEL MESSAGE COMPUTATION FOR MAP INFERENCE

摘要

The invention concerns a generic message passing scheme for MAP inference on Markov Random Fields (MRFs). The method is based on an efficient message computation using an intermediate input vector I, an output message vector M,an auxiliary seed vector S, all of equal length N, anda pairwise function r = d(x,y), where r,x,y are real numbers. The computation comprising: For each element j of vector S, do S(j) = j. Consider an index distance Δ = 2^floor(log2(N)). Repeat while Δ 0. (step 5349) For each index of vector I, namely i, do in parallel: - consider the set of all indices within distance Δ from a given index i (step 5342), augmented by index i. For every index k (step 5343) belonging to this set, calculate its distance from i using the function: d(i,k) + I(S(k)). Find the minimum distance and call n the index corresponding to this minimum distance. (step 5344) - Do S(i) = S(n). (step 5345) - Δ = floor (Δ/2). (step 5348) For each element j of vector M, do M(j) = I(S(j))+d(j,S(j)).