最適化技法を用いたレーザスキャン計画の立案〜ピラミッドを覆い尽くせ！〜
檀 寛成（関西大学 環境都市工学部）
NTT データ数理システム 数理最適化交流会 2021
【アカデミックコンファレンス FY2021 用 ダイジェスト版】

2021/10/29

檀寛成 (関西大学)

最適化技法を用いたレーザスキャン計画

2021/10/29

1 / 40自己紹介
2001/3: 京都大学大学院 情報学研究科 修士課程修了
2001/4 – 2006/3: (株) 数理システム 研究員
2004/9: 博士（情報学）
指導教員: 福島雅夫先生（現: 京都情報大学院大学）
2006/4 – : 関西大学
2006/4 – 2007/3: 工学部 システムマネジメント工学科
2007/4 – : 環境都市工学部 都市システム工学科
2020/10 – : 大阪大学 招へい教員
梅谷先生の「数理最適化寄付講座」のお手伝いをしています

興味を持っている研究対象
非線形最適化
自動微分とか内点法とか実装してます
最適化技法の実問題への応用
最近は土木分野での応用が多いです（所属が土木系学科）
檀寛成 (関西大学)最適化技法を用いたレーザスキャン計画

2021/10/29

2 / 40

発表概要
3D スキャナとは問題定義: 3D スキャンプランの立案
提案手法
最適化手法を用いた 3D スキャンプランの立案
現場のデータをどのように作成するか？

提案手法の適用例
梅田地下街の計測
ピラミッド (Abusir, Egypt) の計測

まとめ
本発表は，
「ピラミッドの最適計測プランの作成」（オペレーションズ・リサーチ 61 p.648-649）に基づきます．
http://www.orsj.or.jp/archive2/or61-10/or61_10_648.pdf
檀寛成 (関西大学)

最適化技法を用いたレーザスキャン計画

2021/10/29

3 / 40

3D スキャナとは

檀

寛成 (関西大学)

最適化技法を用いたレーザスキャン計画

2021/10/29

4 / 40

3D スキャナとは (4/4)

地上レーザスキャナの特徴
対象物（の表面）の点群データを取得できる構造物の現状 (as-is / as-built) を記録できる地上レーザスキャナの使用例
建設現場の進捗管理・完成形の記録
被災状況の記録
流出した土砂量の推定等に利用できる

歴史的建造物・遺跡の記録

地上レーザスキャナによる測量方法も整備されつつある
国土地理院「地上レーザスキャナを用いた公共測量マニュアル（案）」檀寛成 (関西大学)

最適化技法を用いたレーザスキャン計画

2021/10/29

8 / 40問題定義

檀寛成 (関西大学)

最適化技法を用いたレーザスキャン計画

2021/10/29

9 / 40

3D スキャン時の困難
3D スキャナからの可視性物体間の遮蔽関係を調べる必要がある
対象物全体を計測するのは困難

檀

寛成 (関西大学)

最適化技法を用いたレーザスキャン計画

2021/10/29

10 / 40

3D スキャン時の困難
3D スキャナからの可視性物体間の遮蔽関係を調べる必要がある
対象物全体を計測するのは困難

檀寛成 (関西大学)

最適化技法を用いたレーザスキャン計画

2021/10/29

10 / 40

問題定義
どう計測したら対象物全体を計測できるか？
遮蔽を避ける必要性
複数箇所からの計測が必要

トレードオフ: 計測の質と時間的コスト
計測回数を増やせば計測の質は上がる
計測の質：得られた点群の密度
同じ場所を重ねて計測すれば密度はあがるものと仮定（=同じ場所にパルスレーザーがあたることはないと仮定）

計測回数を増やすと時間的コストも増える
約 1 時間/回（※スキャナにもよります）

問題: 最適な 3D スキャンプランの作成
対象物全体を計測するための最小の計測回数は？
計測点の最適な配置は？
檀寛成 (関西大学)

最適化技法を用いたレーザスキャン計画

2021/10/29

11 / 40

提案手法

檀寛成 (関西大学)

最適化技法を用いたレーザスキャン計画

2021/10/29

12 / 40

提案手法の概要
最適化問題として定式化し，ソルバで求解する
モデル 1: 対象物全体を計測するのに必要な計測回数の最小化
モデル 2: 定められた計測回数の下で得られるデータ量（= 点群データの点数）の最大化

仮定
計測対象と周辺環境がメッシュ（三角形）で表現されている
計測候補点が与えられている現場データをどのように作成するか？
（後述）
檀寛成 (関西大学)

最適化技法を用いたレーザスキャン計画

2021/10/29

13 / 40

定式化 (1/6)[集合/添字]i ∈ I: 計測候補点,j ∈ J : 計測対象表面のメッシュ.
[変数](xi :=[パラメータ](di j :=
(ai j :=

1, i を計測点として採用する,0, i を計測点として採用しない.

1, i から j は計測できる,
0, i から j は計測できない,
i から j を計測して得られるデータ量, di j = 1,0,
di j = 0,

r := 計測可能回数の上限.
檀寛成 (関西大学)

最適化技法を用いたレーザスキャン計画

2021/10/29

14 / 40

定式化 (2/6)
計測候補点 i からの j の可視性（遮蔽）檀

寛成 (関西大学)

最適化技法を用いたレーザスキャン計画

2021/10/29

15 / 40

定式化 (3/6)

計測候補点 i からの j の可視性（スキャナの視野）

Ver!cal scanangle

Ver!cal scanangle

3D Scanner

檀寛成 (関西大学)

最適化技法を用いたレーザスキャン計画

3D Scanner

2021/10/29

16 / 40

定式化 (4/6)

ai j : i から j を計測したときのデータ量
ai j は i から j を見たときの立体角に比例する
立体角: 対象物を単位球の中心に向けて射影したときの「影」の大きさ

檀寛成 (関西大学)

最適化技法を用いたレーザスキャン計画

2021/10/29

17 / 40

定式化 (5/6)
モデル 1
対象物全体を計測しつつ，計測回数を最小にする

X
minimizei∈IX

subject toxi
di j xi ≥ 1 (∀ j ∈ J),i∈Ixi ∈ {0, 1} (∀i ∈ I).
目的関数: 採用する計測点の数を最小にする
制約条件: 対象物表面のメッシュを少なくとも1 回は計測する『集合被覆問題』に他ならない！
檀寛成 (関西大学)

最適化技法を用いたレーザスキャン計画

2021/10/29

18 / 40

定式化 (6/6)
モデル 2
計測点の最適な配置を求める

Xmaximize

ai j xii∈I, j∈J

X
subject toX

di j xi ≥ 1 (∀ j ∈ J),i∈Ixi ≤ r,i∈Ixi ∈ {0, 1} (∀i ∈ I).
目的関数: 得られるデータ量を最大にする

r: 計測可能回数 (≥ モデル 1 での最適目的関数値)
檀

寛成 (関西大学)

最適化技法を用いたレーザスキャン計画

2021/10/29

19 / 40データの準備檀寛成 (関西大学)

最適化技法を用いたレーザスキャン計画

2021/10/29

20 / 40

現場のデータをどのように準備するか？ (1/3)
一般論として…
最適化問題を解くためにはデータが必要不可欠！
本研究でのデータ準備方法
3D モデル（メッシュ）の作成
パターン 1（図面等がある場合）: 3D モデラー等で作成パターン 2（図面等がない場合）: 事前調査で写真撮影し，SfM/MVS で粗い 3D モデルを作成
SfM: Structure from Motion, MVS: Multi-view Stereo

3D モデルから di j , ai j を計算（最適解の算出 → 現場での実測）

檀寛成 (関西大学)

最適化技法を用いたレーザスキャン計画

2021/10/29

21 / 40

現場のデータをどのように準備するか？ (2/3)
図面からメッシュを作成した実例（大学構内）

檀寛成 (関西大学)

最適化技法を用いたレーザスキャン計画

2021/10/29

22 / 40

現場のデータをどのように準備するか？ (3/3)
SfM/MVS の実例（バルバル神殿 (バーレーン)）(メッシュ数: 2710，計測候補点: 1262)
檀寛成 (関西大学)

最適化技法を用いたレーザスキャン計画

2021/10/29

23 / 40

適用例

檀寛成 (関西大学)

最適化技法を用いたレーザスキャン計画

2021/10/29

24 / 40

適用例 1: 梅田地下街
梅田地下街の記録（協力：大阪地下街株式会社様）

檀寛成 (関西大学)

最適化技法を用いたレーザスキャン計画

2021/10/29

25 / 40

適用例 1: 梅田地下街
メッシュ分割したモデルとスキャナ設置候補位置
メッシュ数：約 4000，スキャナ設置候補位置：333 箇所

全体を網羅しつつ，約 1 平方 cm あたりに 1 点のレーザが当たるように計画 ⇒ 20 点で計測可能！
モデル 2 の制約条件を少し変更

檀寛成 (関西大学)

最適化技法を用いたレーザスキャン計画

2021/10/29

27 / 40

適用例 1: 梅田地下街
スキャン結果
記録した点群に，写真で撮影した画像の色を乗せたもの

檀寛成 (関西大学)

最適化技法を用いたレーザスキャン計画

2021/10/29

28 / 40

適用例 1: 梅田地下街
スキャン結果
記録した点群に，写真で撮影した画像の色を乗せたもの

檀寛成 (関西大学)

最適化技法を用いたレーザスキャン計画

2021/10/29

28 / 40

適用例 2: ピラミッド (Abusir, Egypt)
事前調査 (2014/9)

檀寛成 (関西大学)

最適化技法を用いたレーザスキャン計画

2021/10/29

31 / 40

適用例 2: ピラミッド (Abusir, Egypt)
Structure from Motion (SfM)
写真 624 枚（写真，動画からの切り出し）檀寛成 (関西大学)

最適化技法を用いたレーザスキャン計画

2021/10/29

32 / 40

適用例 2: ピラミッド (Abusir, Egypt)
MVS によるメッシュ化
節点数 1,658,906, 面数 3,316,972

檀

寛成 (関西大学)

最適化技法を用いたレーザスキャン計画

2021/10/29

33 / 40

適用例 2: ピラミッド (Abusir, Egypt)
入力データ

檀

寛成 (関西大学)

最適化技法を用いたレーザスキャン計画

2021/10/29

34 / 40

適用例 2: ピラミッド (Abusir, Egypt)
最適な計測点（7 点）

檀寛成 (関西大学)

最適化技法を用いたレーザスキャン計画

2021/10/29

35 / 40

適用例 2: ピラミッド (Abusir, Egypt)
現場での計測 (2015/3)

檀寛成 (関西大学)

最適化技法を用いたレーザスキャン計画

2021/10/29

37 / 40

まとめ
最適化手法を用いた 3D 計測プランニング全体を計測できる最小の計測点数の算出
定められた個数の計測点の最適配置

データの準備，現場への適用
今後の課題
計算の高速化（可視性のチェックが遅い）
現場でのニーズに応えられるシステムの作成

本研究を通じて感じたこと
最適化は極めて横断的な学問
まさか考古学に貢献できるとは…

比較的単純な定式化でも面白いことができる！
Special thanks to:
安室 喜弘 教授（関西大学），河江 肖剰 准教授（名古屋大学），
金屋 一郎 教授（長崎県立大学），市川 泰雅 氏（CG artist），廣瀬 詢 氏（関西大学），松下 亮介 氏（関西大学），北田 祐平 氏（関西大学）
檀寛成 (関西大学)

最適化技法を用いたレーザスキャン計画

2021/10/29

40 / 40