大規模な制約付き線形最小二乗法、ソルバーベース

この例では、大規模な範囲制約付き線形最小二乗最適化問題を解いて、不鮮明なイメージを修正する方法を説明します。この例では、ソルバーベースのアプローチを使用します。問題ベースのアプローチについては、大規模な制約付き線形最小二乗法、問題ベースを参照してください。

問題

興味深いナンバー プレートの自動車に乗っている人物の写真があります。

load optdeblur
[m,n] = size(P);
mn = m*n;
imshow(P)
title(sprintf('Original Image, size %d-by-%d, %d pixels',m,n,mn))

問題は、この写真にブレを追加してからブレを除去しようとすることです。最初のイメージは白黒であり、m 行 n 列の行列 P 内の 0 から 1 の範囲にあるピクセル値から構成されています。

動きの追加

各ピクセルと上下 5 ピクセルの平均をとることによって、垂直方向の動きのブレの影響をシミュレートします。単一の行列乗算でブレを追加するためのスパース行列 D を作成します。

blur = 5;  mindex = 1:mn;  nindex = 1:mn;
for i = 1:blur
  mindex=[mindex i+1:mn 1:mn-i];
  nindex=[nindex 1:mn-i i+1:mn];
end
D = sparse(mindex,nindex,1/(2*blur+1));

D の図を描画します。

cla
axis off ij
xs = 31;
ys = 15;
xlim([0,xs+1]);
ylim([0,ys+1]);
[ix,iy] = meshgrid(1:(xs-1),1:(ys-1));
l = abs(ix-iy)<=5;
text(ix(l),iy(l),'x')
text(ix(~l),iy(~l),'0')
text(xs*ones(ys,1),1:ys,'...');
text(1:xs,ys*ones(xs,1),'...');
title('Blurring Operator D (x = 1/11)')

イメージ P に行列 D を乗算して、ブレを追加したイメージ G を作成します。

G = D*(P(:));
figure
imshow(reshape(G,m,n));
title('Blurred Image')

イメージは判別が困難になり、ナンバー プレートを読むことができなくなりました。

ブレを除去したイメージ

ブレを除去するため、ブレを追加する演算子 D が既知であると仮定します。どの程度、ブレを除去して、元のイメージ P を復元できるでしょうか。

最も簡単な方法は、次の最小二乗問題を x について解くことです。

$$0\le x\le 1$$ という条件で $$\min (\Vert Dx-G{\Vert }^2)$$

この問題では、与えられたブレ追加行列 D を使用して、Dx が G = DP に最も近くなる x を求めようとします。解が妥当なピクセル値を表すように、解を 0 から 1 に制限します。

lb = zeros(mn,1);
ub = 1 + lb;
sol = lsqlin(D,G,[],[],[],[],lb,ub);

Minimum found that satisfies the constraints.

Optimization completed because the objective function is non-decreasing in 
feasible directions, to within the value of the optimality tolerance,
and constraints are satisfied to within the value of the constraint tolerance.

xpic = reshape(sol,m,n);
figure
imshow(xpic)
title('Deblurred Image')

ブレを除去したイメージは、ブレを追加したイメージよりはるかに鮮明になっています。再び、ナンバー プレートを読むことができるようになりました。しかし、ブレを除去したイメージには、右下の舗道の部分にある水平の帯のような不自然さがあります。おそらく、これらの不自然さは、正則化によって除去できます。

正則化

正則化は、解を平滑化する方法です。正則化の方法は多数あります。簡単なアプローチとして、次のように目的関数に項を追加します。

$$0\le x\le 1$$ という条件で $$\min (\Vert (D+\epsilon I)x-G{\Vert }^2)$$

$$\epsilon I$$ という項は、生成される二次問題をより安定させます。$$\epsilon =0.02$$ を使用して、再び問題を解きます。

addI = speye(mn);
sol2 = lsqlin(D+0.02*addI,G,[],[],[],[],lb,ub);

Minimum found that satisfies the constraints.

Optimization completed because the objective function is non-decreasing in 
feasible directions, to within the value of the optimality tolerance,
and constraints are satisfied to within the value of the constraint tolerance.

xpic2 = reshape(sol2,m,n);
figure
imshow(xpic2)
title('Deblurred Regularized Image')

この簡単な正則化では、不自然さが除去されないようです。

関連するトピック

• 大規模な制約付き線形最小二乗法、問題ベース