非線形最適化によるドットパターンの生成
今道貴司, 沼田英俊, 井手剛
IBM 東京基礎研究所
離散構造と最適化：展開と連携
九州大学 マス・フォア・インダストリ研究所
2012年11月29, 30日© 2012 IBM Corporation

目次
 背景–液晶ディスプレイの構造–ドットパターンの設計

 関連研究–分子動力学による手法–画像の二値化 分子動力学による手法
 最適化による手法–ドットを密度に応じた円に置換して、円の衝突を除去する手法

 計算実験
 まとめ2© 2012 IBM Corporation

液晶ディスプレイの構造
 液晶ディスプレイは映像を表示するが発光はしない液晶セルをバックライトが背面から照明する構造になっている
 バックライトの明るさを一様にするために、導光板や光拡散フィルムのドットパターンを発光表示装置に応じて調節する

バックライトの典型的構造
3© 2012 IBM Corporation

ドットパターンの設計の流れの例
1. 発光表示装置の輝度分布を測定する
2. 輝度分布をもとにドットの充填率を決定する
3. 充填率にもとにドットの分布を計算する
従来手法では計算時間がかかっていた

4. 結果のドットの分布の中から、異常接近のドット対や、空白に逃げたドットをCADで手作業で調整する
手作業なので時間がかかる

5. ドットパターンのデータをもとに光拡散フィルムなどを製造する

提案手法：3と4の過程を改善するアルゴリズム
4© 2012 IBM Corporation

ドットパターンの生成の条件 (井手, 平 2003)
 ドット間に重なりがないこと–その部分が輝点ないし暗点として目視される

 不規則であること–規則的なドットパターンはモアレ縞を発生させる

 一様であること–ドットの配置が偏ると見た目にムラが発生する

 任意の連続的充填率に応じたドットパターンを生成できること

モアレ縞
5

見た目のムラ© 2012 IBM Corporation

目次
 背景
–液晶ディスプレイの構造–ドットパターンの設計

 関連研究–分子動力学による手法–画像の二値化 分子動力学による手法
 最適化による手法–ドットを密度に応じた円に置換して、円の衝突を除去する手法

 計算実験
 まとめ6© 2012 IBM Corporation

LCDのためのドットパターンに関する関連研究 乱数による手法（谷口ら 1998）–格子点上に配置したドットを疑似乱数で摂動を加える

 分子動力学による手法–ドットの形状を固定し位置を最適化する–ドット間に斥力を設定して、適当な時間ドットを移動させて、ドット間の距離を一様にする• Idéら (2003) (詳細を後ほど紹介)• Chang and Lee (2007)• Chang, Fang, and Ju (2009)

 最適化による手法 (Chang and Fang 2007)–ドットの位置を格子点上に固定する–ドットの半径を反復的に最適化する
7© 2012 IBM Corporation

画像の二値化の関連研究
 不規則なドットパターンに用いて見た目をよくする研究として、濃淡画像の二値化と関連がある–ただし、濃淡画像の二値化の場合ピクセルの位置が固定されていて、ピクセルごとの色を決定する（LCDの場合はドットの位置を最適化）

 濃淡画像の二値化では、青色ノイズマスク法などが提案されているが、LCDの場合では疑似模様が発生することが知られている（井手, 平, 2003）8© 2012 IBM Corporation

目次
 背景–液晶ディスプレイの構造–ドットパターンの設計

 関連研究–分子動力学による手法–画像の二値化 分子動力学による手法
 最適化による手法–ドットを密度に応じた円に置換して、円の衝突を除去する手法

 計算実験
 まとめ9© 2012 IBM Corporation

問題設定
 入力
–長方形のバックライト: C• 容器は縦・横とも等間隔で分割：i番目の分割領域Ri (i ∈[1, M])–ドットの半径 r0–Ri内の密度 ρi = (Ri内のドットの面積の総和) / (Riの面積)

 出力–ドットの配置• ドットの密度が入力に合う• ドット同士が重ならないCC
R1
10R2・・・ ・・・© 2012 IBM Corporation

分子動力学による手法 – ドットパターンの初期配置
 ドットの初期配置を密度に応じてランダムに生成する–ドット1個に対して(U0, U1, U2) ∈[0,1]3の乱数を生成–U0から以下の式を満たすkを見つけドットを領域Rkに配置することを決定–(U1, U2)からドットのRk内の位置(x, y)を決定

ただし、(xk, yk)はRkの左下の座標、(lxk, lyk)はRkの辺の長さとする
11© 2012 IBM Corporation

分子動力学による手法 – ドットパターンの初期配置
 Idéら(2003) は乱数として、疑似乱数の代わりに超一様分布列(low-discrepancy sequences, LDS) (Tezuka 1993)を用いた–LDSは準モンテカルロ法で用いられる数列

 LDSによるドットの初期配置の方が、擬似乱数によるドットの初期配置よりもムラが少ないことが報告されている

Idéら(2003)

疑似乱数
12

超一様分布列(LDS)© 2012 IBM Corporation

分子動力学による手法 – 初期配置の改善
 LDSによるドットパターンは高い一様性を持っているが、ドットに大きさがあるためドットの間に重なりや非常に近接する場合がある ドットの間に斥力を定義して、斥力的に相互作用する粒子系とみなす

 動力学的にある程度時間を進めた状態を求めることで、ドットパターンを改善する

13© 2012 IBM Corporation

分子動力学による手法 – 初期配置の改善
 運動方程式
 差分方程式
 ドットiとjの間の斥力–LとDはに比例 差分方程式を解く計算量はfijの計算に依存するが、ドットの密度が低い領域ではDが大きくなるため計算量が大きくなる
14© 2012 IBM Corporation

分子動力学による手法の効果
 それ以前の格子点上にドットを配置した後にランダムな摂動を加える手法(PRP)ではモアレ縞が発生した
 Idéら (2003)の手法(DLDS)は実機を作った実験でモアレ縞が発生しないドットパターンが生成できることを示した
 IBM ThinkPad A30/A30pで用いられた

PRP
15

DLDS

Idéら(2003)

PRPDLDS© 2012 IBM Corporation

分子動力学による手法の欠点
 差分方程式を解くのに時間がかかる いくつかのドットが初期配置の位置から大きく離れてしまう–設計の工程では人手で修正する必要が発生する

入力のドット密度が0だが、いくつかのドットが最終的に逃げてきてしまう16© 2012 IBM Corporation

目次
 背景–液晶ディスプレイの構造–ドットパターンの設計

 関連研究–分子動力学による手法–画像の二値化 分子動力学による手法
 最適化による手法–ドットを密度に応じた円に置換して、円の衝突を除去する手法

 計算実験
 まとめ17© 2012 IBM Corporation

最適化による提案手法のアイデアと概要
 分子動力学による手法では固定のステップ幅Δtで差分方程式を解くが、最終的な配置以外は必要ではない→ 適切な大きさの図形充填の最適化問題に定式化することで、最終的な配置に相当する局所最適解を高速に求められるかもしれない

提案手法の概要
 Idéら (2003)の手法の初期配置はそのまま利用して、配置の改善部分に対して最適化による手法を提案する
 ドットを元のドットよりも大きい円に置換して円の充填問題を解くことでドットパターンの一様性を向上させる

18© 2012 IBM Corporation

最適化による提案手法の流れ
OptDot
1. LDSによるドットの初期配置の生成 (Idéら 2003 と同様)
2. ドット密度に応じた半径の円でドットを置換
3. 円の間の重なりを最小化

New

4. 円を元のドットに戻す

19

1234

© 2012 IBM Corporation

円を用いたドットの置換
 円の衝突を除去した結果、各ドットのペアの間の距離を一様にする
 円の半径はドット密度に応じて設定する–ドットが密な領域 ⇒ 円の半径を小さくして、領域内の円を多くする–ドットが疎な領域 ⇒ 円の半径を大きくして、領域内の円を少なくする

 置換した後の円の重なりを除去すると、円の最密充填になるような半径に設定することで元のドットの間の距離を一様にする

20© 2012 IBM Corporation

円の最密充填の際の半径と密度の関係 表記: r0 = ドットの半径, ρi = ドット密度–Ri内の密度 ρi = (Ri内のドットの面積の総和) / (Riの面積)

 円は右図の六方充填配置が最密になる–密度は

 Ri内に円を六方充填配置した際の半径をr’とするとr’

 距離を一様にする効果を大きくするために少しだけ大きめの半径raを設定する

21© 2012 IBM Corporation

円の衝突除去 円の位置をドットパターンとして望ましいものにするために、以下のペナルティの総和を最小化する–円の間の衝突のペナルティ• ドット間の距離を一様にする–円の容器からの突出のペナルティ• 全てのドットをバックライトの中に収める– 個々の円に制限領域を設定して、制限領域からの突出のペナルティ• 円が初期配置から大きく外れないようにする

22© 2012 IBM Corporation

円の重なりのペナルティ
 貫通深度 (Dobkinら 1993)–二つの図形の衝突を除去するのに必要な最小の平行移動の距離–図形が両方とも円の場合は用意に計算可能

 貫通深度の二乗を円の重なりのペナルティとする

23© 2012 IBM Corporation

円の容器からの突出のペナルティ 容器の外部領域に対する貫通深度の二乗を、円の突出のペナルティとして採用

24© 2012 IBM Corporation

個々の円の制限領域とペナルティ 個々の円Siに対して、正方形の制限領域Qiを設定–制限領域の中心は、ドットの初期配置の位置（固定）–制限領域の大きさは、一辺の長さが直径の2倍 制限領域Qiの外部領域に対する貫通深度の二乗をペナルティとして採用

25© 2012 IBM Corporation

円の衝突除去の定式化
 入力–容器: , 容器の外部領域–円:–個々の円の制限領域:

 決定変数–円の中心の位置(= ドットの中心の位置):

 定式化

円の衝突

円の容器からの突出

26

円の制限領域からの突出© 2012 IBM Corporation

局所最適解の計算
 先の定式化は制約なし非線形最適化問題–目的関数は微分可能

 Limited memory BFGS (L-BFGS)法を適用(Liu, Nocedal 1989)–ドットパターンの最適化の問題は、ドットの数が数十万になることもあり、記憶計算量がO(n)のL-BFGSが望ましい• BFGS法はO(n2)の記憶計算量なので全部をメモリに乗せるのは難しい–実験では、L-BFGS法で高速に局所最適解を求めることができ、十分実用的だった

27© 2012 IBM Corporation

目的関数と微分の計算量
 アルゴリズムのボトルネックは目的関数と微分の計算–円の間の衝突のペナルティ• 領域分割と平面操作法の組合せた手法を利用(Imamichi andNagamochi 2008)• Kを衝突している円の組の数とすると、時間計算量はO(n log n + K)
(円の半径は、円同士が少しずつ重なるように設定するので、Kは通常O(n)になることが期待できる)–円の容器からの突出と、制限領域からの突出のペナルティ• O(n) 時間28© 2012 IBM Corporation

最適化モデルと分子動力学モデルの関係 類似点–個々のドットに注目して円の衝突のペナルティや斥力を設定して、全体としてドット間の距離を一様にする点は似ている• 円の間の衝突のペナルティは、ドットの間の斥力に相当する

 相違点–分子動力学モデル• ドットの初期配置からのズレを小さくする仕組みがない• 運動方程式を解いて、適当な時間を経過させてドットを散らせる• 勾配の計算で遠くのドット間の斥力を計算する必要となる場合があった–最適化モデル• ドットの初期配置からのズレを小さくする仕組みを入れた• 局所最適解がドット間の距離を一様になるように設計した• 局所最適解に高速に収束する手法を適用• 目的関数の計算が重くならないように円の半径は必要以上に大きくしない（衝突する円の組が少ない）
29© 2012 IBM Corporation

目次
 背景–液晶ディスプレイの構造–ドットパターンの設計

 関連研究–分子動力学による手法–画像の二値化 分子動力学による手法
 最適化による手法–ドットを密度に応じた円に置換して、円の衝突を除去する手法

 計算実験
 まとめ30© 2012 IBM Corporation

分子動力学による手法との比較 － 計算時間の比較
 3つの問題例 (ドットの直径 = 46 µm)–角–直下–LED: 111211 dots
: 287080 dots
: 117088 dots

 計算環境–Intel Core 2 Duo T9300 CPU 2.5GHz–Idéら(2003)は200回の反復を行っている–OptDot はIdéら(2003)の結果に比べて10倍近く高速Time (min) 計算時間の比較

403530252015
1050

OptDotIde et al.

LED31

ChokkaTsuno© 2012 IBM Corporationドットパターンの質の比較
 結果のドットパターンに含まれる衝突するドットの組や、接近しすぎるドットの組の数を比較
 OptDotはいずれの場合でも既存手法と同等以上の質を達成
衝突するドットの組の数（ドットの中心間の距離 < 46µm）
Pattern

Initial layout

Idé et al.

OptDot# dots# dot pairs

Tsuno

24339

10111211

6183887655

Chokka36827

00287080

41207319660

LED57949

1315

01170886854741328

近接するドットの組の数（ドットの中心間の距離 < 60µm）
Pattern

Initial layout

Idé et al.

OptDot# dots

# dot pairs

Tsuno

45523

66

16111211

6183887655

Chokka73055

20287080

41207319660

LED

104530

37844

32644

1170886854741328

32© 2012 IBM Corporation

結果 (ＬＥＤ, #dots = 110k）
・OptDot 1.8min ・Idé et al 38min

33© 2012 IBM Corporation

結果 (ＬＥＤ, #dots = 110k）, 拡大図34© 2012 IBM Corporation

結果 (Chokka, #dots = 280k)
・OptDot 4.7min ・Idé et al. 38min

35© 2012 IBM Corporation

結果 (Chokka, #dots = 280k), 拡大図36© 2012 IBM Corporation

結果 (Tsuno, #dots = 110k)
・OptDot 1.9min ・Idé et al. 15min

37© 2012 IBM Corporation

結果 (Tsuno, #dots = 110k), 拡大図

Idé et al.
38

ドットがいくつか逃げている

OptDot© 2012 IBM Corporation

まとめ LCDの導光板や光拡散フィルムのための、最適化によるドットパターンの生成手法を提案–ドットを密度に応じた大きさの円に置換して、円の衝突や初期配置からのズレを最小化–L-BFGS法で局所最適解に高速に収束–分子動力学による既存手法よりも大幅に高速で同等以上の質の結果を得ることに成功 課題–長方形や楕円といった円以外のドットパターンに適用するための拡張–提案手法によるドットパターンをもとに実際の部品を作成して、実際の物理的な性質の測定

39© 2012 IBM Corporation

参考文献• 金光 昭佳, 坂本 隆, 井山 浩暢, 液晶TV用光拡散板の開発, 住友化学 技術誌 2007 –I, pp. 4-12, 2007.
 井手 剛, 平洋一, ドットパターン生成技術と光学系,月刊ディスプレイ, vol.9, No.1,2003.
 谷口 斉, 日良 康夫, 森 祐二, 液晶表示装置, 日本国特許, 特開平10-153779
 Idé, T., Mizuta, H., Numata, H., Taira, Y., Suzuki, M., Noguchi, M. and Katsu, Y.:
Dot pattern generation technique using molecular dynamics, Journal of the OpticalSociety of America A, Vol. 20, No. 2, pp. 248–255 (2003).
 Chang, J.-G. and Lee, C.-T.: Random-dot pattern design of a light guide in anedge-lit backlight: integration of optical design and dot generation scheme by themolecular-dynamics method, Journal of the Optical Society of America A, Vol. 24,No. 3, pp. 839–849 (2007).
 Chang, J.-G., Fang, Y.-B. and Ju, S.-P.: Using a generalized molecular dynamics
force model for random microstructure generation of different aspect-ratios andorientation for use in the optical design of an LED edge-lit backlight, Computer
Physics Communications, Vol. 180, No. 8, pp. 1259–1270 (2009).
40© 2012 IBM Corporation

参考文献
 Tezuka, S.: Polynomial arithmetic analogue of Halton sequences, ACM
Transactions on Modeling and Computer Simulation, Vol. 3, pp. 99–107 (1993).
 D. Dobkin, J. Hershberger, D. Kirkpatrick, and S. Suri, Computing the intersectiondepth of polyhedra, Algorithmica, vol. 9, no. 6, pp. 518-533, 1993.
 Liu, D. C. and Nocedal, J.: On the limited memory BFGS method for large scale
optimization, Mathematical Programming, Vol. 45, No. 1, pp. 503–528 (1989).
 Imamichi, T. and Nagamochi, H.: Performance Analysis of a Collision Detection
Algorithm of Spheres Based on Slab Partitioning, IEICE Transactions on
Fundamentals of Electronics, Communications and Computer Sciences, Vol. E91A, No. 9, pp. 2308–2313 (2008).

41© 2012 IBM Corporation