n枚の画像を1枚のキャンバスに最適なサイズで描画するには?(javascript.canvas)

どうも( ´_ゝ`)
タイトルの通り,n枚の画像を1枚のキャンバスに最適なサイズで描画するにはどうしたら良いか考えました. 最適化問題として定式化したいと思います.結論を言うと,まだ解けていません.

考え方としては,i番目の画像に拡大率x_iをかけることにより,画像のサイズを調整する. まず,オリジナルの画像をo^{(1)}, \ldots, o^{(n)}とする. そしてi番目の画像o^{(i)}のwidth, heightをそれぞれo^{(i)}_w, o^{(i)}_hとする. 同様に,リサイズされた画像をz^{(1)}, \ldots, z^{(n)}とし, i番目のリサイズされた画像のwidth, heightをz^{(i)}_w, z^{(i)}_hとする. 元の画像とリサイズされた画像のwidth,heightの関係は以下のように定義する.

\displaystyle  z^{(i)}_w = \sqrt{x_i} o^{(i)}_w\\ z^{(i)}_h = \sqrt{x_i} o^{(i)}_h

こうすると,各画像の面積の関係は以下のようになる.

\displaystyle  z^{(i)}_w z^{(i)}_h = x_i o^{(i)}_w o^{(i)}_h = x_i y_i

ここで,y_iは元の画像の面積である.

次に,評価関数f({\bf x}), {\bf x} = [x_1, \ldots, x_n]を作る. 元の画像の面積に近ければ近いほど良い と考え,各画像サイズの二乗誤差を用いて以下のように定義することにした.

\displaystyle  f({\bf x}) = \sum_i (y_i - x_i y_i)^2 = \sum_i y^2_i (1 - xi)^2

これを最小化する{\bf x}を見つければよいが,このままだとx_i=1 \forall i=1,\ldots,n,つまり元のサイズで出せば良いじゃん?と言われてしまう. そこで,リサイズされた画像の面積の合計が,canvasの面積Sを超えないように,という条件を加える. これらを統合すると,以下の最適化問題を解くことになる.

\displaystyle  \min_{{\bf x}} \sum_i y^2_i (1 - xi)^2 \\ s.t. \sum_i x_i y_i \leq S \\  0 \leq x_i \leq 1 \forall i=1,\ldots,n

これを解くにはKKT条件を使うことになりそうだが,まだ解けていないので解けたら載せたいと思います.

コメントを残す

以下に詳細を記入するか、アイコンをクリックしてログインしてください。

WordPress.com ロゴ

WordPress.com アカウントを使ってコメントしています。 ログアウト / 変更 )

Twitter 画像

Twitter アカウントを使ってコメントしています。 ログアウト / 変更 )

Facebook の写真

Facebook アカウントを使ってコメントしています。 ログアウト / 変更 )

Google+ フォト

Google+ アカウントを使ってコメントしています。 ログアウト / 変更 )

%s と連携中