---
title: 屋内ナビゲーション手法：SCAN #mixleap
tags:  #mixleap  
author: [Yahoo!デベロッパーネットワーク](https://www.docswell.com/user/ydnjp)
site: [Docswell](https://www.docswell.com/)
thumbnail: https://bcdn.docswell.com/page/2VENR4P978.jpg?width=480
description: 2020年1月30日（木）に、ヤフー大阪オフィスで「Mix Leap Study #57 - iOS ＆ Android勉強会」を開催しました。  「PayPayフリマ」「Yahoo!天気」のAndroidアプリ、そして社内の研究開発から生まれたGPS不要の屋内ナビゲーション手法「SCAN」のiOSアプリを開発する3組のエンジニア・デザイナーが、その開発ノウハウを語りました。  イベントの詳細については、下記connpassページをご覧ください。 https://yahoo-osaka.connpass.com/event/159924/
published: February 28, 20
canonical: https://www.docswell.com/s/ydnjp/KEJJQZ-2020-02-28-150543
---
# Page. 1

![Page Image](https://bcdn.docswell.com/page/2VENR4P978.jpg)

Mix Leap Study #57 - iOS &amp; Android勉強会
屋内ナビゲーション手法：SCAN
ヤフー株式会社
鈴木 健司
Conﬁdential
西 紗記子


# Page. 2

![Page Image](https://bcdn.docswell.com/page/GY79MQ33E3.jpg)

SCANとは？
Conﬁdential


# Page. 3

![Page Image](https://bcdn.docswell.com/page/5G78LGMLED.jpg)

屋内位置測位技術の課題
GPSが届きにくい
屋内ではGPS電波が届きにくく
屋内で位置を特定させるには異なるアプローチが必要
Conﬁdential
事業者側の準備コスト
QR/地磁気/Wiﬁなど既存設備への追加や
専用の地図を用意する必要


# Page. 4

![Page Image](https://bcdn.docswell.com/page/ML7LLG3Q7R.jpg)

SCANのアプローチ
1
設置されている構内図を
Conﬁdential
2
SCANで撮影すると
3
撮影画像に現在地を表示/追跡


# Page. 5

![Page Image](https://bcdn.docswell.com/page/54EMMQMKEW.jpg)

SCANの特徴
Camera
IMU
スマホ単体で完結
専用の装置や地図が不要
現在地測位に用いるのはスマホ内蔵カメラとIMUだけ
既存設備をそのまま活用可能で導入コストが低い
Conﬁdential


# Page. 6

![Page Image](https://bcdn.docswell.com/page/ZPERV8V679.jpg)

Conﬁdential


# Page. 7

![Page Image](https://bcdn.docswell.com/page/NP7XZ8ZDEX.jpg)

R&amp;Dしたので
SCANは世界最高峰の国際学会に採択されました
コンピュータ科学分野の国際学会ACM（Association for Computing Machinery）が主催する
MobileHCI 2019 DemosにてSCANは査読スコア満点で採択され、その研究内容に高い関心が寄せられています
Conﬁdential


# Page. 8

![Page Image](https://bcdn.docswell.com/page/637K8K8DED.jpg)

Conﬁdential


# Page. 9

![Page Image](https://bcdn.docswell.com/page/4LJ32Z2P75.jpg)

BEST DEMO - Peopleʼs Choice を受賞しました！
Conﬁdential


# Page. 10

![Page Image](https://bcdn.docswell.com/page/V8JDZRZ3EG.jpg)

SCANのしくみ
Conﬁdential


# Page. 11

![Page Image](https://bcdn.docswell.com/page/4VEPDWDPE8.jpg)

全体の流れ
- ユーザの操作時 -
Conﬁdential


# Page. 12

![Page Image](https://bcdn.docswell.com/page/L27V181VEQ.jpg)

屋内地図を撮影
Conﬁdential


# Page. 13

![Page Image](https://bcdn.docswell.com/page/Z5JG2521JL.jpg)

屋内地図を撮影
matching feature points
reference
user scanned
撮影画像と参照画像のマッチング
Conﬁdential


# Page. 14

![Page Image](https://bcdn.docswell.com/page/V47QPZPNEP.jpg)

(Camera Calibration)
屋内地図を撮影
2枚の画像から回転/移動量を求め現在地XYを算出
target
u
user
matching feature points
reference
user scanned
撮影画像と参照画像のマッチング
Conﬁdential
a2
a1
reference
θ
u= (
cosθ -sinθ
sinθ cosθ
)a
2


# Page. 15

![Page Image](https://bcdn.docswell.com/page/DKE4Y3Y371.jpg)

(Camera Calibration)
屋内地図を撮影
2枚の画像から回転/移動量を求め現在地XYを算出
target
u
user
a2
a1
reference
θ
u= (
cosθ -sinθ
sinθ cosθ
)a
2
matching feature points
reference
user scanned
撮影画像と参照画像のマッチング
Conﬁdential
user scanned
front-view
正面図に補正し現在地XYを画像上にマッピング


# Page. 16

![Page Image](https://bcdn.docswell.com/page/PL71616ZEG.jpg)

(Camera Calibration)
屋内地図を撮影
2枚の画像から回転/移動量を求め現在地XYを算出
target
u
user
a2
a1
IMUで相対的移動量を取得し位置更新
reference
IMU
θ
u= (
cosθ -sinθ
sinθ cosθ
)a
2
matching feature points
reference
user scanned
撮影画像と参照画像のマッチング
Conﬁdential
user scanned
front-view
正面図に補正し現在地XYを画像上にマッピング
3d axis


# Page. 17

![Page Image](https://bcdn.docswell.com/page/8G7WW8W672.jpg)

SCANの実装を少し詳しく
Conﬁdential


# Page. 18

![Page Image](https://bcdn.docswell.com/page/W4JZ585R73.jpg)

(Camera Calibration)
屋内地図を撮影
2枚の画像から回転/移動量を求め現在地XYを算出
target
u
user
a2
a1
IMUで相対的移動量を取得し位置更新
reference
3d axis
IMU
θ
u= (
cosθ -sinθ
sinθ cosθ
)a
2
matching feature points
←これ
reference
user scanned
撮影画像と参照画像のマッチング
Conﬁdential
user scanned
front-view
正面図に補正し現在地XYを画像上にマッピング


# Page. 19

![Page Image](https://bcdn.docswell.com/page/KYE69P91EV.jpg)

の前にちょっと
行列演算について
Conﬁdential


# Page. 20

![Page Image](https://bcdn.docswell.com/page/5GE5NKNL74.jpg)

Conﬁdential
参照：https://ja.wikipedia.org/wiki/レナ_(画像データ)


# Page. 21

![Page Image](https://bcdn.docswell.com/page/V9725W537R.jpg)

Conﬁdential


# Page. 22

![Page Image](https://bcdn.docswell.com/page/5DJYKLK8EM.jpg)

問
Conﬁdential
画像を右上100ピクセル移動しなさい


# Page. 23

![Page Image](https://bcdn.docswell.com/page/2V7NR4R9J8.jpg)

Conﬁdential


# Page. 24

![Page Image](https://bcdn.docswell.com/page/GYJ9MQM373.jpg)

Conﬁdential


# Page. 25

![Page Image](https://bcdn.docswell.com/page/5GJ8LGLL7D.jpg)

Conﬁdential


# Page. 26

![Page Image](https://bcdn.docswell.com/page/MLJLLGLQJR.jpg)

Conﬁdential


# Page. 27

![Page Image](https://bcdn.docswell.com/page/547MMQ1K7W.jpg)

Conﬁdential


# Page. 28

![Page Image](https://bcdn.docswell.com/page/ZP7RV8L6J9.jpg)

問
Conﬁdential
画像を原点から45度回転させなさい


# Page. 29

![Page Image](https://bcdn.docswell.com/page/NPJXZ8WD7X.jpg)

Conﬁdential


# Page. 30

![Page Image](https://bcdn.docswell.com/page/63JK8KVD7D.jpg)

Conﬁdential


# Page. 31

![Page Image](https://bcdn.docswell.com/page/4LE32ZMPJ5.jpg)

Conﬁdential


# Page. 32

![Page Image](https://bcdn.docswell.com/page/V8EDZR637G.jpg)

Conﬁdential


# Page. 33

![Page Image](https://bcdn.docswell.com/page/4V7PDWYP78.jpg)

45
Conﬁdential


# Page. 34

![Page Image](https://bcdn.docswell.com/page/L2JV18GV7Q.jpg)

Conﬁdential


# Page. 35

![Page Image](https://bcdn.docswell.com/page/Z5EG2581EL.jpg)

Conﬁdential


# Page. 36

![Page Image](https://bcdn.docswell.com/page/V4JQPZ9N7P.jpg)

これを行列演算でやってみる
Conﬁdential


# Page. 37

![Page Image](https://bcdn.docswell.com/page/DK74Y3X3J1.jpg)

1
0
0
Conﬁdential
0
1
0
0
0
1
参照：https://developer.apple.com/documentation/accelerate


# Page. 38

![Page Image](https://bcdn.docswell.com/page/PLJ161NZ7G.jpg)

1
0
0
0
1
0
0
0
1
複数の計算式を一行で出来る！
Conﬁdential
参照：https://developer.apple.com/documentation/accelerate


# Page. 39

![Page Image](https://bcdn.docswell.com/page/8GJWW846J2.jpg)

平行移動行列
!&quot;
1
#&quot; = 0
0
1
0
1
0
100 !
100 #
1
1
&quot; + 100
= &amp; + 100
1
回転行列
45
cos
&quot;
!
180
#&quot; =
45
sin
1
180
0
45
− sin
180
45
cos
180
0
0 !
#
0 1
1
45
45
cos
* ∗ , − sin
*∗0
180
180
=
45
45
sin
* ∗ , + cos
*∗0
180
180
1
回転と平行移動のアフィン変換行列
&quot;
!
1
#&quot; = 0
0
1
Conﬁdential
0
1
0
45
cos
100
180
100
45
sin
1
180
0
45
− sin
180
45
cos
180
0
0 !
#
0 1
1
参照：https://developer.apple.com/documentation/accelerate


# Page. 40

![Page Image](https://bcdn.docswell.com/page/W4EZ582RJ3.jpg)

Swiftでどう書くの？
Conﬁdential


# Page. 41

![Page Image](https://bcdn.docswell.com/page/KY769PV17V.jpg)

Conﬁdential
参照：https://developer.apple.com/documentation/accelerate


# Page. 42

![Page Image](https://bcdn.docswell.com/page/5G75NKDLJ4.jpg)

1
0
0
0
1
0
100
100
1
simd_float3x3(simd_float3(1, 0, 100),
simd_float3(0, 1, 100),
simd_float3(0, 0, 1))
Conﬁdential


# Page. 43

![Page Image](https://bcdn.docswell.com/page/V9J25W83JR.jpg)

&quot;
!
1
&quot;
# = 0
0
1
0
1
0
100 !
100 #
1
1
let p = simd_float3(x, y, 1) * simd_float3x3(simd_float3(1, 0, 100),
simd_float3(0, 1, 100),
simd_float3(0, 0, 1)) .
Conﬁdential


# Page. 44

![Page Image](https://bcdn.docswell.com/page/5DEYKL687M.jpg)

一般的な数学
&quot;
!
1
&quot;
# = 0
0
1
0
1
0
100 !
100 #
1
1
&quot; + 100
= &amp; + 100
1
simdではこう書かなくてはならない！
! 1
&quot; = # 0
#
1 0
1
&quot;
!
Conﬁdential
0
1
0
100
100
1
&quot; + 100
= &amp; + 100
1


# Page. 45

![Page Image](https://bcdn.docswell.com/page/2VJNR4Z9E8.jpg)

Conﬁdential


# Page. 46

![Page Image](https://bcdn.docswell.com/page/GYE9MQZ3J3.jpg)

Conﬁdential


# Page. 47

![Page Image](https://bcdn.docswell.com/page/5GE8LG1LJD.jpg)

Conﬁdential


# Page. 48

![Page Image](https://bcdn.docswell.com/page/MLELLGQQER.jpg)

これをシェーダーでやってみる
Conﬁdential


# Page. 49

![Page Image](https://bcdn.docswell.com/page/54JMMLKKJW.jpg)

forで1pxづつやる
||
画素数多いと時間がかかる
Conﬁdential


# Page. 50

![Page Image](https://bcdn.docswell.com/page/ZPJRVKX6E9.jpg)

Conﬁdential
forで1pxづつやる
shaderで同時並列でやる
||
||
画素数多いと時間がかかる
処理が早い！


# Page. 51

![Page Image](https://bcdn.docswell.com/page/NPEXZL6DJX.jpg)

Conﬁdential


# Page. 52

![Page Image](https://bcdn.docswell.com/page/63EK8L1DJD.jpg)

Conﬁdential


# Page. 53

![Page Image](https://bcdn.docswell.com/page/4L7323QPE5.jpg)

forで1pxづつやる
⏱
Conﬁdential
0.241829秒
shaderで同時並列でやる


# Page. 54

![Page Image](https://bcdn.docswell.com/page/V87DZ493JG.jpg)

forで1pxづつやる
⏱
Conﬁdential
0.241829秒
shaderで同時並列でやる
⏱
0.000584秒


# Page. 55

![Page Image](https://bcdn.docswell.com/page/4VJPDMZPJ8.jpg)

400倍
高速
forで1pxづつやる
⏱
Conﬁdential
0.241829秒
shaderで同時並列でやる
⏱
0.000584秒


# Page. 56

![Page Image](https://bcdn.docswell.com/page/L2EV19WVJQ.jpg)

※実際はこうなります。興味のある方は是非調べてみて下さい！
Conﬁdential


# Page. 57

![Page Image](https://bcdn.docswell.com/page/Z57G2ZD17L.jpg)

ここまで前提知識
Conﬁdential


# Page. 58

![Page Image](https://bcdn.docswell.com/page/V4EQPL1NJP.jpg)

(Camera Calibration)
屋内地図を撮影
2枚の画像から回転/移動量を求め現在地XYを算出
target
u
user
a2
a1
IMUで相対的移動量を取得し位置更新
reference
3d axis
IMU
θ
u= (
cosθ -sinθ
sinθ cosθ
)a
2
matching feature points
←これ
reference
user scanned
撮影画像と参照画像の特徴量マッチング
Conﬁdential
user scanned
front-view
正面図に補正し現在地XYを画像上にマッピング


# Page. 59

![Page Image](https://bcdn.docswell.com/page/DKJ4YDR3E1.jpg)

!&quot;
cos )
# &quot; = sin )
0
1
− sin )
cos )
0
0 !
0 #
1 1
行列を用いることで画像の変換が行えることを説明しました
Conﬁdential


# Page. 60

![Page Image](https://bcdn.docswell.com/page/PLE16ZQZJG.jpg)

ここに2枚の画像があります
Conﬁdential


# Page. 61

![Page Image](https://bcdn.docswell.com/page/8GEWW9M6E2.jpg)

?
?
?
?
?
?
?
?
?
左画像を右画像と完全に変換できる未知の行列が存在します！
Conﬁdential


# Page. 62

![Page Image](https://bcdn.docswell.com/page/W47Z59QRE3.jpg)

どう求めるのか？
Conﬁdential


# Page. 63

![Page Image](https://bcdn.docswell.com/page/KYJ69K61JV.jpg)

⚙
ℎ$$
! = ℎ%$
ℎ&amp;$
ℎ$%
ℎ%%
ℎ&amp;%
computer vision
Computer Visionの技術を用いると未知の行列が得られます
この未知の行列のことを「ホモグラフィー行列」と呼びます
Conﬁdential
ℎ$&amp;
ℎ%&amp;
ℎ&amp;&amp;


# Page. 64

![Page Image](https://bcdn.docswell.com/page/5GJ5NP6LE4.jpg)

ℎ$$
! = ℎ%$
ℎ&amp;$
ℎ$%
ℎ%%
ℎ&amp;%
ℎ$&amp;
ℎ%&amp;
ℎ&amp;&amp;
左の画像の任意のXYが、右の画像のどこかがHを用い計算できる
Conﬁdential


# Page. 65

![Page Image](https://bcdn.docswell.com/page/4LE323QDJ5.jpg)

&quot;#
!
(H.inverse)
右の画像の任意のXYが左の画像のどこかがHの逆行列で計算できます
Conﬁdential


# Page. 66

![Page Image](https://bcdn.docswell.com/page/V8EDZ4927G.jpg)

user scanned
front-view
すなわち、ユーザが撮った写真を正面図に変換できます！
Conﬁdential


# Page. 67

![Page Image](https://bcdn.docswell.com/page/4V7PDMZL78.jpg)

ありがとうございました
Conﬁdential


