|
1 ###################################################################### |
|
2 # Predictive online PDPS for optical flow with unknown velocity field |
|
3 ###################################################################### |
|
4 |
|
5 __precompile__() |
|
6 |
|
7 module AlgorithmBothMulti |
|
8 |
|
9 using Printf |
|
10 |
|
11 using AlgTools.Util |
|
12 import AlgTools.Iterate |
|
13 using ImageTools.Gradient |
|
14 using ImageTools.ImFilter |
|
15 |
|
16 using ..OpticalFlow: Image, |
|
17 ImageSize, |
|
18 DisplacementConstant, |
|
19 pdflow!, |
|
20 horn_schunck_reg_prox!, |
|
21 pointwise_gradiprod_2d!, |
|
22 horn_schunck_reg_prox_op!, |
|
23 mldivide_step_plus_sym2x2!, |
|
24 ConstantDisplacementHornSchunckData, |
|
25 filter_hs |
|
26 |
|
27 using ..Algorithm: step_lengths |
|
28 |
|
29 ######################### |
|
30 # Iterate initialisation |
|
31 ######################### |
|
32 |
|
33 function init_displ(xinit::Image, ::Type{DisplacementConstant}, n::Integer) |
|
34 return xinit, zeros(n, 2) |
|
35 end |
|
36 |
|
37 # function init_displ(xinit::Image, ::Type{DisplacementFull}, n::Integer) |
|
38 # return xinit, zeros(n, 2, size(xinit)...) |
|
39 # end |
|
40 |
|
41 function init_rest(x::Image, u::DisplacementT) where DisplacementT |
|
42 imdim=size(x) |
|
43 |
|
44 y = zeros(2, imdim...) |
|
45 Δx = copy(x) |
|
46 Δy = copy(y) |
|
47 x̄ = copy(x) |
|
48 |
|
49 return x, y, Δx, Δy, x̄, u |
|
50 end |
|
51 |
|
52 function init_iterates( :: Type{DisplacementT}, |
|
53 xinit::Image, |
|
54 n::Integer) where DisplacementT |
|
55 return init_rest(init_displ(copy(xinit), DisplacementT, n)...) |
|
56 end |
|
57 |
|
58 function init_iterates( :: Type{DisplacementT}, |
|
59 dim::ImageSize, |
|
60 n::Integer) where DisplacementT |
|
61 return init_rest(init_displ(zeros(dim...), DisplacementT, n)...) |
|
62 end |
|
63 |
|
64 ############ |
|
65 # Algorithm |
|
66 ############ |
|
67 |
|
68 function solve( :: Type{DisplacementT}; |
|
69 dim :: ImageSize, |
|
70 iterate = AlgTools.simple_iterate, |
|
71 params::NamedTuple) where DisplacementT |
|
72 |
|
73 ###################### |
|
74 # Initialise iterates |
|
75 ###################### |
|
76 |
|
77 n = params.displacement_count |
|
78 k = 0 # number of displacements we have already |
|
79 |
|
80 x, y, Δx, Δy, x̄, u = init_iterates(DisplacementT, dim, n) |
|
81 init_data = (params.init == :data) |
|
82 hs = [ConstantDisplacementHornSchunckData() for i=1:n] |
|
83 #hs = Array{ConstantDisplacementHornSchunckData}(undef, n) |
|
84 A = Array{Float64,3}(undef, n, 2, 2) |
|
85 d = Array{Float64,2}(undef, n, 2) |
|
86 |
|
87 # … for tracking cumulative movement |
|
88 ucumulbase = [0.0, 0.0] |
|
89 |
|
90 ############################################# |
|
91 # Extract parameters and set up step lengths |
|
92 ############################################# |
|
93 |
|
94 α, ρ, λ, θ = params.α, params.ρ, params.λ, params.θ |
|
95 R_K² = ∇₂_norm₂₂_est² |
|
96 γ = 1 |
|
97 τ, σ, σ̃, ρ̃ = step_lengths(params, γ, R_K²) |
|
98 |
|
99 kernel = params.kernel |
|
100 T = params.timestep |
|
101 |
|
102 #################### |
|
103 # Run the algorithm |
|
104 #################### |
|
105 |
|
106 b_next_filt = nothing |
|
107 diffu = similar(u[1, :]) |
|
108 |
|
109 v = iterate(params) do verbose :: Function, |
|
110 b :: Image, |
|
111 🚫unused_v_known :: DisplacementT, |
|
112 b_next :: Image |
|
113 |
|
114 #################################### |
|
115 # Smooth data for Horn–Schunck term |
|
116 #################################### |
|
117 |
|
118 b_filt, b_next_filt = filter_hs(b, b_next, b_next_filt, kernel) |
|
119 |
|
120 ################################################ |
|
121 # Prediction step |
|
122 ################################################ |
|
123 |
|
124 # Predict x and y |
|
125 if k==0 |
|
126 if init_data |
|
127 x .= b |
|
128 init_data = false |
|
129 end |
|
130 else |
|
131 # Displacement from previous to this image is estimated as |
|
132 # the difference of their displacements from beginning of window. |
|
133 if k>1 |
|
134 @. @views diffu = u[k, :] - u[k-1, :] |
|
135 else |
|
136 @. @views diffu = u[k, :] |
|
137 end |
|
138 |
|
139 pdflow!(x, Δx, y, Δy, diffu, params.dual_flow) |
|
140 end |
|
141 |
|
142 # Shift stored prox matrices |
|
143 if k==n |
|
144 tmp = copy(u[1, :]) |
|
145 ucumulbase .+= tmp |
|
146 for j=1:(n-1) |
|
147 @. @views u[j, :] = u[j+1, :] - tmp |
|
148 hs[j] = hs[j+1] |
|
149 end |
|
150 # Create new struct as original contains references to objects that |
|
151 # have been moved to index n-1. |
|
152 hs[n]=ConstantDisplacementHornSchunckData() |
|
153 else |
|
154 k += 1 |
|
155 end |
|
156 |
|
157 # Predict u: zero displacement from current to next image, i.e., |
|
158 # same displacement to beginning of window. |
|
159 if k==1 |
|
160 @. @views u[k, :] = 0.0 |
|
161 else |
|
162 @. @views u[k, :] = u[k-1, :] |
|
163 end |
|
164 |
|
165 # Predictor proximals tep |
|
166 if params.prox_predict |
|
167 ∇₂!(Δy, x) |
|
168 @. y = (y + σ̃*Δy)/(1 + σ̃*(ρ̃+ρ/α)) |
|
169 proj_norm₂₁ball!(y, α) |
|
170 end |
|
171 |
|
172 ################################################################################# |
|
173 # PDPS step |
|
174 # |
|
175 # For the displacements, with τ̃=τ/k, we need to solve for 2≤j<k, |
|
176 # |
|
177 # (1) (I/τ̃+M₀^j+M₀^{j+1})u^j = M₀^ju^{j-1} + M₀^{j+1}u^{j+1} |
|
178 # + ũ^j/τ̃ - z^j + z^{j+1}, |
|
179 # |
|
180 # as well as |
|
181 # |
|
182 # (2) (I/τ̃+M₀^k)u^k = M₀^k u^{k-1} + ũ^k/τ̃ - z^k |
|
183 # |
|
184 # and |
|
185 # |
|
186 # (3) (I/τ̃+M₀^1+M₀^2)u^1 = 0 + M₀^{2}u^{2} + ũ^1/τ̃ - z^1 + z^{2} |
|
187 # |
|
188 # We first construct from (2) that |
|
189 # |
|
190 # u^k = A^k u^{k-1} + d^k |
|
191 # |
|
192 # for |
|
193 # |
|
194 # A^k := (I/τ̃+M₀^k)^{-1} M₀^k |
|
195 # d_k := (I/τ̃+M₀^k)^{-1} (ũ^k/τ̃ - z^k). |
|
196 # |
|
197 # Inserting this into (1) we need |
|
198 # |
|
199 # (4) (I/τ̃+M₀^j+M₀^{j+1}(I-A^{j+1}))u^j = M₀^ju^{j-1} + M₀^{j+1}d^{j+1} |
|
200 # + ũ^j/τ̃ - z^j + z^{j+1}. |
|
201 # |
|
202 # This is well-defined because A^{j+1} < I. It also has the same form as (1), so |
|
203 # we continue with |
|
204 # |
|
205 # (5) u^j = A^j u^{j-1} + d^j |
|
206 # |
|
207 # for |
|
208 # |
|
209 # A^j := (I/τ̃+M₀^j+M₀^{j+1}(I-A^{j+1}))^{-1} M₀^j |
|
210 # d^j := (I/τ̃+M₀^j+M₀^{j+1}(I-A^{j+1}))^{-1} |
|
211 # (M₀^{j+1}d^{j+1} + ũ^j/τ̃ - z^j + z^{j+1}) |
|
212 # |
|
213 # Finally from (3) with these we need |
|
214 # |
|
215 # (I/τ̃+M₀^1+M₀^2(I-A^2))u^1 = M₀^2d^2 + ũ^1/τ̃ - z^1 + z^2, |
|
216 # |
|
217 # which is of the same form as (4) with u^0=0, so by (5) u^1=d^1. |
|
218 # |
|
219 ################################################################################# |
|
220 |
|
221 ∇₂ᵀ!(Δx, y) # primal step: |
|
222 @. x̄ = x # | save old x for over-relax |
|
223 @. x = (x-τ*(Δx-b))/(1+τ) # | prox |
|
224 # | | for displacement |
|
225 # Calculate matrices for latest data; rest is stored. |
|
226 @views begin |
|
227 horn_schunck_reg_prox_op!(hs[k], b_next_filt, b_filt, θ, λ, T) |
|
228 |
|
229 τ̃=τ/k |
|
230 |
|
231 B = hs[k].M₀ |
|
232 c = u[k, :]./τ̃-hs[k].z |
|
233 mldivide_step_plus_sym2x2!(A[k, :, :], B, B, τ̃) |
|
234 mldivide_step_plus_sym2x2!(d[k, :], B, c, τ̃) |
|
235 |
|
236 for j=(k-1):-1:1 |
|
237 B = hs[j].M₀+hs[j+1].M₀*([1 0; 0 1]-A[j+1, :, :]) |
|
238 c = hs[j+1].M₀*d[j+1, :]+u[j, :]./τ̃-hs[j].z+hs[j+1].z |
|
239 mldivide_step_plus_sym2x2!(A[j, :, :], B, hs[j].M₀, τ̃) |
|
240 mldivide_step_plus_sym2x2!(d[j, :], B, c, τ̃) |
|
241 end |
|
242 |
|
243 u[1, :] .= d[1, :] |
|
244 for j=2:k |
|
245 u[j, :] .= A[j, :, :]*u[j-1, :] + d[j, :] |
|
246 end |
|
247 end |
|
248 |
|
249 @. x̄ = 2x - x̄ # over-relax: x̄ = 2x-x_old |
|
250 ∇₂!(Δy, x̄) # dual step: y |
|
251 @. y = (y + σ*Δy)/(1 + σ*ρ/α) # | |
|
252 proj_norm₂₁ball!(y, α) # | prox |
|
253 |
|
254 ######################################################## |
|
255 # Give function value and cumulative movement if needed |
|
256 ######################################################## |
|
257 v = verbose() do |
|
258 ∇₂!(Δy, x) |
|
259 hs_plus_reg=0 |
|
260 for j=1:k |
|
261 v=(j==1 ? u[j, :] : u[j, :]-u[j-1, :]) |
|
262 hs_plus_reg += hs[j].cv/2 + dot(hs[j].Mv*v, v)/2+dot(hs[j].av, v) |
|
263 end |
|
264 value = (norm₂²(b-x)/2 + hs_plus_reg/k + α*γnorm₂₁(Δy, ρ)) |
|
265 |
|
266 value, x, u[k, :]+ucumulbase, u[1:k,:].+ucumulbase' |
|
267 end |
|
268 |
|
269 return v |
|
270 end |
|
271 |
|
272 return x, y, v |
|
273 end |
|
274 |
|
275 end # Module |
|
276 |
|
277 |