ラスタ図形詰込み問題に対する局所探索法の特徴点抽出を用いた効率化
3 likes6,451 views
ビットマップ（ラスタとも呼ばれる）で描かれた図形を長方形の領域に隙間なく詰込む最適化問題に対して効率的なアルゴリズムの提案する．
![特徴点の抽出による1次元探索の⾼速化
• 図形を1ピクセルずつ動かして重なり度fijが最⼩となる配置を求める探
索⽅法では計算効率が悪い
• ミンコフスキー差にコーナー検出アルゴリズム [Rosten+,2006] を適
⽤し，重なり度fijが最⼩となる可能性の⾼い配置のみ評価することで，
1次元探索の効率化を実現
23
rj－ri
ミンコフスキー差 ⽔平⽅向の重なり度 上⽅向の重なり度 下⽅向の重なり度](https://image.slidesharecdn.com/slide20160916-160908060559/75/-23-2048.jpg)
![特徴点の抽出による1次元探索の⾼速化
• 図形を1ピクセルずつ動かして重なり度fijが最⼩となる配置を求める探
索⽅法では計算効率が悪い
• ミンコフスキー差にコーナー検出アルゴリズム [Rosten+,2006] を適
⽤し，重なり度fijが最⼩となる可能性の⾼い配置のみ評価することで，
1次元探索の効率化を実現
27
rj－ri
ミンコフスキー差 ⽔平⽅向の重なり度 上⽅向の重なり度 下⽅向の重なり度
重なり度が極⼩・極⼤となる可能性が⾼い点FASTによって検出された特徴点](https://image.slidesharecdn.com/slide20160916-160908060559/75/-27-2048.jpg)
![数値実験：他⼿法との⽐較
• 特徴点抽出なし(naive)，特徴点抽出あり(improved)と円弧を含むベ
クタ図形を詰込むアルゴリズム[Burke+,2010]と充填率(%)を⽐較
30
instance naive improved Burke+
Albano 84.7% 87.0% 86.0%
Dagli 83.6% 84.5% 82.2%
Dighe1 82.2% 99.2% 82.1%
Dighe2 99.2% 99.3% 84.3%
Fu 86.5% 88.5% 89.2%
Jakobs1 81.7% 84.4% 82.6%
Jakobs2 75.1% 77.7% 75.1%
Mao 81.0% 82.6% 78.7%
Marques 87.3% 88.4% 86.5%
Shapes0 62.4% 64.4% 65.6%
Shapes1 66.6% 70.4% 71.5%
Shirts 80.6% 83.1% 82.8%
Swim 69.5% 71.0% 67.2%
Trousers 83.0% 86.4% 86.9%
avg. 80.2% 83.4% 80.1%
instance naive improved Burke+
Profiles1 81.2% 85.2% 82.5%
Profiles2 73.6% 74.2% 73.8%
Profiles3 69.4% 70.8% 70.8%
Profiles4 83.2% 84.1% 86.8%
Profiles5 76.3% 80.0% 75.9%
Profiles6 73.5% 75.6% 72.1%
Profiles7 97.4% 98.8% 73.3%
Profiles8 82.9% 83.8% 78.7%
Profiles9 53.1% 53.8% 52.9%
Profiles10 63.5% 66.3% 65.0%
avg. 75.4% 77.3% 73.2%](https://image.slidesharecdn.com/slide20160916-160908060559/75/-30-2048.jpg)
More Related Content
What's hot (20)
Viewers also liked (20)
ラスタ図形詰込み問題に対する局所探索法の特徴点抽出を用いた効率化
- 1. 梅⾕ 俊治，村上 祥平，森⽥ 浩 ⼤阪⼤学 ⼤学院情報科学研究科 2016年9⽉16⽇ ⽇本オペレーションズ・リサーチ学会 秋季研究発表会（⼭形⼤学） ラスタ図形詰込み問題に対する局所探索法の 特徴点検出を⽤いた効率化
- 2. 図形の詰込み問題 • いくつかの図形を互いに重ならないように与えられた容器内に配置する 問題 • 図形や容器の形状により多くのバリエーションを持つ • 服の型紙の配置，鉄鋼・繊維などの素材の切り分け，機械部品の板取り， ⾞両の荷物積み込み，カタログのレイアウトなど多くの応⽤を持つ 2 ⻑⽅形詰込み コンテナ詰込み 多⾓形詰込み
- 3. ベクタ表現とラスタ表現 • ベクタ表現：点と線分で図形を表現 – パラメトリック曲線で描かれた図形の重なりを⾼速に判定することは困難 – 縮退した図形や数値誤差による誤判定の回避に多くの例外処理が必要 • ラスタ表現：ピクセル(pixel)と呼ばれる点の集合で図形を表現 – 任意の形状の図形の重なりをピクセル毎の重なりの有無で判定できる – 計算時間がピクセル数(図形の⾯積)に⽐例する 3ベクタ表現された図形 ラスタ表現された図形
- 4. ストリップパッキング問題 • ⼊⼒：幅W(固定)，⻑さL(可変)の⻑⽅形の容器，n個の図形 P1,P2,...,Pn (各図形は定められた⾓度のみ回転できる) • 条件：全ての図形を互いに重ならないように容器内に配置 • ⽬的：全ての図形を配置するのに必要な容器の⻑さLを最⼩化 4 幅W (固定) ⻑さL(可変) 板取り問題とも呼ばれ，英語でも irregular strip packing problem, nesting problem, marking problemなど多くの呼び名を持つ
- 5. 提案⼿法の概要 • 構築法を適⽤して初期配置を求める • 容器の⻑さL(可変)を⼀時的に固定して重なり度最⼩化問題を解く • 重なりのない配置が得られたら容器の⻑さLを縮める • 重なりのない配置が得られなければ容器の⻑さLを伸ばす 5 容器の⻑さLを 縮める 重なり度を最⼩化
- 6. 重なり度最⼩化問題 • ⼊⼒：幅W(固定)，⻑さLUB(固定)の⻑⽅形の容器，n個の図形 P1,P2,...,Pn (各図形は定められた⾓度のみ回転できる) • 条件：全ての図形を容器内に配置 • ⽬的：図形対Pi, Pjの重なり度fijの総和を最⼩化 6 重なりを持つ図形 重なりを持たない図形 幅W (固定) ⻑さLUB(固定)
- 7. 重なり度の定義 • 重なり部分の⾯積が⼩さくても重なりの解消が困難な場合もある • 重なりの解消に必要な最⼩の移動距離(penetration depth)を考える • 移動⽅向を⽔平 or 垂直のみに制限した移動距離で重なり度を定義 7 Pj Pi 参照点rj 参照点ri
- 8. ミンコフスキー差による重なり度計算 • 図形Pi, Pjの基準となる点を参照点ri, rjとする • Piの参照点を原点に固定し，PiとPjが重なりを持つ参照点rjの配置全体 をミンコフスキー差(Minkowski difference)と呼ぶ • PiとPjが重ならないためには，Pjの参照点rjがミンコフスキー差の外部 となるようにPjを配置すれば良い 8 Pj Pi 参照点rj 参照点ri ミンコフスキー差 NFP(no-fit polygon)，図形の畳込み(convolution)と呼ばれることもある
- 9. スキャンライン表現 • 図形を⾛査してピクセルのある区間の始点と終点の座標を保持 • ⽔平と垂直の2⽅向に⾛査して2種類のスキャンライン表現を作成 → データ量の削減と重なり計算の⾼速化を実現(後述) 9 ラスタ表現 スキャンライン表現
- 10. ミンコフスキー差による重なり度計算 • スキャンライン表現された図形Pi, Pjがあれば，スキャンライン表現さ れたミンコフスキー差が⽣成できる • ミンコフスキー差の上で参照点rjからスキャンラインの端点までの距 離を調べれば⽔平⽅向の重なり度を計算できる 10 Pj Pi 参照点rj 参照点ri
- 11. ミンコフスキー差による重なり度計算 • スキャンライン表現された図形Pi, Pjがあれば，スキャンライン表現さ れたミンコフスキー差が⽣成できる • ミンコフスキー差の上で参照点rjからスキャンラインの端点までの距 離を調べれば垂直⽅向の重なり度を計算できる 11 Pj Pi 参照点rj 参照点ri
- 12. 1次元探索に基づく局所探索法 • 1つの図形を選び⽔平(垂直)⽅向で重なり度が最⼩となる配置を求める • ⽔平・垂直⽅向と交互に1次元探索を繰り返す • 重なりを持つ図形がなくなるか，いずれの図形を動かしても重なり度 が⼩さくなる配置が得られなければ終了 12
- 13. 1次元探索に基づく局所探索法 • 1つの図形を選び⽔平(垂直)⽅向で重なり度が最⼩となる配置を求める • ⽔平・垂直⽅向と交互に1次元探索を繰り返す • 重なりを持つ図形がなくなるか，いずれの図形を動かしても重なり度 が⼩さくなる配置が得られなければ終了 13
- 14. 1次元探索に基づく局所探索法 • 1つの図形を選び⽔平(垂直)⽅向で重なり度が最⼩となる配置を求める • ⽔平・垂直⽅向と交互に1次元探索を繰り返す • 重なりを持つ図形がなくなるか，いずれの図形を動かしても重なり度 が⼩さくなる配置が得られなければ終了 14
- 15. 1次元探索に基づく局所探索法 • 1つの図形を選び⽔平(垂直)⽅向で重なり度が最⼩となる配置を求める • ⽔平・垂直⽅向と交互に1次元探索を繰り返す • 重なりを持つ図形がなくなるか，いずれの図形を動かしても重なり度 が⼩さくなる配置が得られなければ終了 15
- 16. 1次元探索に基づく局所探索法 • 1つの図形を選び⽔平(垂直)⽅向で重なり度が最⼩となる配置を求める • ⽔平・垂直⽅向と交互に1次元探索を繰り返す • 重なりを持つ図形がなくなるか，いずれの図形を動かしても重なり度 が⼩さくなる配置が得られなければ終了 16
- 17. 1次元探索に基づく局所探索法 • 1つの図形を選び⽔平(垂直)⽅向で重なり度が最⼩となる配置を求める • ⽔平・垂直⽅向と交互に1次元探索を繰り返す • 重なりを持つ図形がなくなるか，いずれの図形を動かしても重なり度 が⼩さくなる配置が得られなければ終了 17
- 18. 1次元探索に基づく局所探索法 • 1つの図形を選び⽔平(垂直)⽅向で重なり度が最⼩となる配置を求める • ⽔平・垂直⽅向と交互に1次元探索を繰り返す • 重なりを持つ図形がなくなるか，いずれの図形を動かしても重なり度 が⼩さくなる配置が得られなければ終了 18 各図形の参照点rjのx座標とy座標がそれぞれ1つの変数に対応するので coordinate descent method とみなすこともできる
- 23. 特徴点の抽出による1次元探索の⾼速化 • 図形を1ピクセルずつ動かして重なり度fijが最⼩となる配置を求める探 索⽅法では計算効率が悪い • ミンコフスキー差にコーナー検出アルゴリズム [Rosten+,2006] を適 ⽤し，重なり度fijが最⼩となる可能性の⾼い配置のみ評価することで， 1次元探索の効率化を実現 23 rj－ri ミンコフスキー差 ⽔平⽅向の重なり度 上⽅向の重なり度 下⽅向の重なり度
- 25. コーナー検出アルゴリズム • 注⽬するピクセルと半径rの円周上にあるピクセルの画素値と⽐較 • 円周上のピクセルがm個以下もしくはn個以上連続して明るい場合は 注⽬するピクセルを特徴点として検出 25 輪郭追跡 コーナー 検出 16 1 2 15 14 13 3 4 9 7 8 6 11 5 12 10
- 26. コーナー検出アルゴリズム • 注⽬するピクセルと半径rの円周上にあるピクセルの画素値と⽐較 • 円周上のピクセルがm個以下もしくはn個以上連続して明るい場合は 注⽬するピクセルを特徴点として検出 26 輪郭追跡 コーナー 検出 16 1 2 15 14 13 3 4 9 7 8 6 11 5 12 10
- 27. 特徴点の抽出による1次元探索の⾼速化 • 図形を1ピクセルずつ動かして重なり度fijが最⼩となる配置を求める探 索⽅法では計算効率が悪い • ミンコフスキー差にコーナー検出アルゴリズム [Rosten+,2006] を適 ⽤し，重なり度fijが最⼩となる可能性の⾼い配置のみ評価することで， 1次元探索の効率化を実現 27 rj－ri ミンコフスキー差 ⽔平⽅向の重なり度 上⽅向の重なり度 下⽅向の重なり度 重なり度が極⼩・極⼤となる可能性が⾼い点FASTによって検出された特徴点
- 28. 数値実験：環境とベンチマーク問題例 • ベクタ図形をラスタ図形に変換（容器の幅Wを2048ピクセルに設定） した問題例に提案アルゴリズムを適⽤ • CPU: Intel Core i7(3.1GHz), Memory: 16GBのPCで1200秒実⾏ 28 instance #pieces degrees Albano 24 0,180 Dagli 30 0,180 Dighe1 16 0 Dighe2 10 0 Fu 12 0,90,180,270 Jakobs1 25 0,90,180,270 Jakobs2 25 0,90,180,270 Mao 20 0,90,180,270 Marques 24 0,90,180,270 Shapes0 43 0 Shapes1 43 0,180 Shirts 99 0,180 Swim 48 0,180 Trousers 64 0,180 instance #pieces degrees Profiles1 32 0,90,180,270 Profiles2 50 0,90,180,270 Profiles3 46 0,45,90,...,270,315 Profiles4 54 0,90,180,270 Profiles5 50 0,15,30,...,330,345 Profiles6 69 0,90,180,270 Profiles7 9 0,90,180,270 Profiles8 18 0,90,180,270 Profiles9 57 0,90,180,270 Profiles10 91 0 多⾓形の問題例 円弧を含むベクタ図形の問題例
- 29. 数値実験：計算効率の⽐較 • 特徴点抽出なし(naive)と特徴点抽出あり(improved)の近傍探索(1個 の図形の⽔平・垂直⽅向の繰返し移動)の呼出し回数を⽐較 29 instance naive improved ratio Albano 8941 269803 30.18 Dagli 8050 162750 20.22 Dighe1 20950 411025 19.62 Dighe2 49727 1403485 28.22 Fu 18801 734092 39.05 Jakobs1 7379 151411 20.52 Jakobs2 7187 58200 8.10 Mao 14086 208962 14.83 Marques 9104 172906 18.99 Shapes0 9153 207089 22.63 Shapes1 5085 78823 15.50 Shirts 2358 33117 14.04 Swim 4428 47889 10.82 Trousers 2861 71391 24.95 avg. 20.55 instance naive improved ratio Profiles1 5813 92603 15.93 Profiles2 2415 41696 17.27 Profiles3 601 5332 8.87 Profiles4 622 24292 39.05 Profiles5 616 6036 9.80 Profiles6 2630 21162 8.05 Profiles7 122259 636598 5.21 Profiles8 7110 172526 24.27 Profiles9 2674 19398 7.25 Profiles10 1249 16054 12.85 avg. 14.85
- 30. 数値実験：他⼿法との⽐較 • 特徴点抽出なし(naive)，特徴点抽出あり(improved)と円弧を含むベ クタ図形を詰込むアルゴリズム[Burke+,2010]と充填率(%)を⽐較 30 instance naive improved Burke+ Albano 84.7% 87.0% 86.0% Dagli 83.6% 84.5% 82.2% Dighe1 82.2% 99.2% 82.1% Dighe2 99.2% 99.3% 84.3% Fu 86.5% 88.5% 89.2% Jakobs1 81.7% 84.4% 82.6% Jakobs2 75.1% 77.7% 75.1% Mao 81.0% 82.6% 78.7% Marques 87.3% 88.4% 86.5% Shapes0 62.4% 64.4% 65.6% Shapes1 66.6% 70.4% 71.5% Shirts 80.6% 83.1% 82.8% Swim 69.5% 71.0% 67.2% Trousers 83.0% 86.4% 86.9% avg. 80.2% 83.4% 80.1% instance naive improved Burke+ Profiles1 81.2% 85.2% 82.5% Profiles2 73.6% 74.2% 73.8% Profiles3 69.4% 70.8% 70.8% Profiles4 83.2% 84.1% 86.8% Profiles5 76.3% 80.0% 75.9% Profiles6 73.5% 75.6% 72.1% Profiles7 97.4% 98.8% 73.3% Profiles8 82.9% 83.8% 78.7% Profiles9 53.1% 53.8% 52.9% Profiles10 63.5% 66.3% 65.0% avg. 75.4% 77.3% 73.2%
- 31. 数値実験：実⾏結果(1/4) 31 Albano(87.0%) Dagli(84.5%) Dighe1(99.2%) Dighe2(99.3%) Fu (88.5%) Jakobs1 (84.4%) Jakobs2 (77.7%) Mao (82.6%)
- 32. 数値実験：実⾏結果(2/4) 32 Marques(88.4%) Shapes0(64.4%) Shapes1(70.4%) Shirts(83.1%) Swim(71.0%) Trousers(86.4%)
- 33. 数値実験：実⾏結果(3/4) 33 Profiles1(85.2%) Profiles2(74.2%) Profiles3(70.8%) Profiles4(84.1%) Profiles5(80.0%)
- 34. 数値実験：実⾏結果(4/4) 34 Profiles6(75.6%) Profiles7(98.8%) Profiles8(83.8%) Profiles9(53.8%) Profiles10(66.3%)
- 35. まとめ • ラスタ表現された図形のストリップパッキング問題 • スキャンライン表現とミンコフスキー差を⽤いた⾼速な重なり度計算 • 1次元探索に基づく局所探索法 • 前処理と特徴点の抽出による1次元探索の⾼速化 • ベンチマーク問題例に対する数値実験 35
- 36. 参考⽂献 • S.Umetani, M.Yagiura, S.Imahori, T.Imamichi, K.Nonobe and T.Ibaraki, Solving the irregular strip packing problem via guided local search for overlap minimization, International Transactions of Operational Research, 16 (2009), 661-683. • E.K.Burke, R.S.R.Hellier, G.Kendall and G.Whitwell, Irregular packing using the line and arc no-fit polygon, Operations Research, 58 (2010), 948-970. • E.Rosten and T.Drummond, Machine learning for high-speed corner detection, Computer Vision, 3951 (2006), 430-443. 36