Dec. 23 情報系 Winter FESTA at 一橋講堂

Dec. 23 情報系 Winter FESTA at 一橋講堂
Outline
1. Background and Purpose
2. Project Initiatives
3. Major Results
2
1. Background and Purpose
20th cent.
21st cent.
Computer
One of the Greatest Scientific Inventions
Big Data Era
Revolution
Data Volume
Revolution
Computational
Speed
Computer Science
The paradigm in 20th cent. Is obsolete!
ex) polynomial time ≠ fast
PARADIGM
Polynomial Time Algorithms
Computer Science
Urgent Task!
Sublinear Time Algorithms
3
2. Project Initiatives
Foundations of Algorithm Theory for BIG DATA
1. Foundations of Sublinear Time Algorithm (Katoh group)
2. Foundations of Sublinear Data Structures (Shibuya group)
3. Foundations of Sublinear Modeling (Tanaka group)
4
Research Groups
Katoh group
(Sublinear Time Algorithms)
Ito
Katoh
Takizawa
Makino Okamoto Yoshida
Kamiyama
Saito
Shibuya group
(Sublinear Data Structures)
Shibuya
Nakano
Yada
Sakamoto Yamagiwa Sadakane Takeda
Tanigawa Onodera
Kida
Tanaka group
(Sublinear Modeling)
Tanaka
Yasuda
Shioura
Shinohara
Ito
Group 1. Sublinear Time Algorithms
Base Theories
Breakthrough [Yoshida, Ito and
others]
maximum matching, vertexconnectivity, sparsity matroid,
knapsack problem, etc:
constant-time randomized
approx. algorithm
Maximum Matching for
Bipartite Graphs
Practically efficient algorithm
6
Group 2. Sublinear Data Structures
Base Theories
Information Theory-based Approach
Big Data
of Size n
Enumeration-based Approach
Description for
enumeration
O(I)
compression
(I: information
quantity)
Enumerated outputs of
"big-data size"
New
paradigm
o(n) -size
Indexing
How to index?
How to compress?
o(I) indexing /
computation?
Applications
How to enumerate?
How to represent?
Sublinear-size
representation?
New sublinear data structure
paradigms for Big Data
 FPGA Compression
 Management Information Data
 Protein 3-D Structure DB
Big Data with
"Well-structured Data"
ATTCAGCGTAAGGCCATTGCGATAG
CCTTAAGCGCTAAAGTCGTGGCGCC
TATCGATCTTGGACATTAACGCTCT
GTAACTACAGGTAGCGGTATCGATC
ATCGTATTCTGATTCTTCTATCTTC
ATGGTGCTGCTGGTATACTCTACCC
TCTGGTGCATCAATAATCTCCGTGC
TATCCAATAGGCTTTGCGCACTGAT
Group 3. Sublinear Modeling from statistical mechanics
Statistical mechanics involves rich techniques for coarse graining of information.
low-dimensional data
BIG DATA
New Paradigm of Sublinear modeling
using
Statistical Mechanics
and
Machine Learning
Finding hierarchical structures of BIG DATA
(Hierarchical) Markov Random Field for Big Data
Structure inference of (hierarchical) MRFs generating Big Data
using statistical mechanical and machine learning techniques
Our recent theoretical developments:
• mean-field theory for hierarchical probabilistic models (PRE, 2013; J. Phys., 2013; ICPR, 2014)
• statistical machine learning theory for MRFs (Neur. Comput, 2009; ICPR, 2012)
etc.
8
3. Major Results
A1. Constant-Time Algorithms for Complex Networks
A2. Modeling and Simulation of Umeda Underground
Mall toward Algorithmic Evacuation Planning
Poster
D1. Sublinear-Space Compression and Its Application
D2. Extraction of Characteristic Subgraphs from LargeScale Assembly Graphs
関連発表
Poster
M1. Information Coarse Graining using Renormalization
Group Theory with Application to Image Processing
M2. Detection of Sparse Structure in Big Data with
Application to Detection of Cheating Students
関連発表
Poster
加藤CREST関連ポスターは他にも２件、計５件あります。
Major results of Katoh group
A1. Constant-Time Algorithms for Complex Networks
A2. Modeling and Simulation of Umeda Underground Mall
toward Algorithmic Evacuation Planning
Poster
A1. Constant-Time Algorithms for Complex Networks
Past Important Results
Target: Complex Networks
Dense-Graph Model:
• Every hereditary property is
testable. [Alon et al. FOCS05]
Degree-Bounded Model:
• Every minor-closed property is
testable. [Benjamini et al. STOC08]
• For hyperfinite graphs, every
property is testable. [Newman & Sohler
• Typical & important big graph data
• Includes web-graphs, social
networks, etc.
• Characteristics:
• small world
• high cluster
• power-law degree distribution
STOC11]
• → “sparse” and “degree
unbounded”
These algorithms cannot be applied.
We need new algorithms!
How to Model Complex Networks
CLUE
Isolated cliques [Ito & Iwama
05,09]:
<k
k vertices
Highly related with “high cluster.”
[Uno & Oguri 11] [Shigezumi, Uno, Watanabe
11] observed the following facts: In typical realworld networks G,
1.G includes many isolated cliques,
2.G’ that is obtained by contracting all isolated
cliques of G has a similar structure, and
3.The above operation can be applied
recursively several times.
We introduce a new graph class HSF (Hierarchically Scale-Free Multigraphs)
If G is in HSF, then
i.G obeys power-law degree distribution,
ii.G includes at least one isolated clique,
iii.G’ that is obtained by contracting all isolated cliques of G also has the
above property (i) and (ii) if |G|≥c, which is a given constant.
Our New Results
Theorem [Ito 15]
HSF is hyperfinite*.
For this class, every property is testable in constant-time.
*Hyperfinite: A graph can be decomposed into constant-sized components by removing at
most εn edges (n is # of vertices).
Importance of this theorem:
a)The first result on universal testers on the general (=sparse & degree unbounded)
graph model.
b)By using this result (algorithm), whether a big complex network has any specified
property can be tested in constant-time.
Future work:
• Practical usefulness: computer experiments by using actual data.
practical side
• Which property is easy to test in practice?
• Extending the theorem, e.g., cliques → dense subgraphs.
theoretical side
• Theoretical characterization of properties that are easy to test.
A2. Modeling and Simulation of Umeda Underground
Mall toward Algorithmic Evacuation Planning
• Background
• Frequent occurrence in recent years of
flood and tsunami.
• Disasters become bigger and wider
areas are affected.
• Congestion and limited time for
evacuation.
• Need of the support for local
governments.
Prediction of flooding
area from Yodogawa
• Purpose
• Development of algorithmic
evacuation planning systems with big
spatial data and efficient algorithms.
• Agenda
• Model big and precise spatial data.
• Perform general multi-agent
simulations.
• Development of efficient evacuation
planning algorithms.
• Unify and validate the data and
methods.
3D Model of Umeda Underground Mall by
Taniguchi Lab. at OCU
Data acquisition, modeling and
multi-agent based evacuation simulation
• Characteristics of Umeda Underground
Mall
• About 1.1km length of east and west side, north
and south side, respectively.
• Composed of multiple malls and five stations.
• About 50 connected buildings and 150 entrances.
• More than 1 million passengers per a day.
• Difficulty on the data acquisition
• Base 3D data has been developed by Prof.
Yoshiya Taniguchi at OCU.
• However, other spatial data are stored in a lot of
private sectors and difficult to get them.
• We could get them from flooding measure
consociation.
• Pedestrian data were partially available and we
did a field study for getting the remaining data.
• Performed as a benchmark with general method.
• Simulator: Simtread DXF version (A&A)
• About 20000 evacuees evacuate to the nearest
connected buildings at 18:00 on a weekday.
• We can roughly grasp the evacuation time and
congested places.
Evacuees
• Multi-agent based evacuation simulation
25000
20000
15000
10000
5000
0
0
5
10
15
Minutes
20
25
Current achievements and future plans
• Achievements (ongoing)
• Modeled big and precise spatial
data.
• Performed general multi-agent
simulations.
• PR of the current simulation
result.
• Flooding measure consociation of
Osaka City Umeda Underground
Mall
• Osaka Prefecture Police
• NHK, News Terrace Kansai
• NHK, Ohayo Nippon
• MBS, Chichinpuipui
• Yomiuri newspaper
• Sankei newspaper
• Mainichi newspaper
• Nikkei newspaper
MBS Chichinpuipui, Sep. 1, 2015
• Future plans
• Development of efficient
evacuation planning algorithms.
• Unify and validate the data and
methods.
Map evacuation exercise on March 6, 2015
Major results of Shibuya group
D1. Sublinear-Space Compression and Its Application
D2. Extraction of Characteristic Subgraphs from Large-Scale
Assembly Graphs
関連発表
Poster
D1. Sublinear-Space Compression and Its Application
Sakamoto & Yamagiwa
• High performance compression with
compressed space
• Wide applications: index, pattern discovery,
hardware implementation, etc.
• First online self-index
• online construction
• supports search and partial extraction
100~1000 times
scalability
output/input(%)
• Hardware implementation
memory/input
• FPGA (patent application)
• Embedded Technology 2015 特別賞
• VLDB BPOE workshop best-paper award
Background and Goal
• Rapid increase of stream
data
• social media
• demand for rapid printing of
large digital data
• rapid communication of
sensing data
• rapid processing of image data
Platform of stream
computing
• Progress of online
compression
• not requiring whole data
• output linear workspace (not
input linear)
• simple algorithm: scalable and
fast
Basic technology: algorithm
• Grammar compression
• Naïve method: parsing tree, pruning, and
encoding
• advantage：online friendly because of its
principle
• dis-：compression ratio
• Online and optimal encoding of
grammar compression
(sakamoto@presto, et al.)
Basic technology: hardware
• High-performance stream computing
environment (yamagiwa@presto)
• Grammar comp. on FPGA
(sakamoto&yamagiwa, before crest)
• advantage over previous methods
• small circuit size
• 1CPU time compression
• Prototype
• fast communication by fixed
symbol table
• speeding up by compression>transmission->decompression
After the beginning of CREST
• First Online self-index
first online self-index
small workspace
real-time detection of frequent pattern
Google code release
• dynamic data structure
• several times speeding-up
(depending on memory size)
• JST innovation Japan 2015
• patent application
• VLDB2015 BPOE workshop
best paper award
offline
• Embedded Technology 2015
特別賞
memory
•
•
•
•
• Hardware implementation
online
input-size
D2. Extraction of Characteristic Subgraphs
from Large-Scale Assembly Graphs
[1] Wing-Kin Sung, Kunihiko Sadakane, Tetsuo Shibuya, Abha Belorkar and Iana Pyrogova,
An O(m log m)-time algorithm for detecting superbubbles, IEEE/ACM Transactions on
Computational Biology and Bioinformatcs, 12(4), July/August 2015.
[2] Taku Onodera, Kunihiko Sadakane and Tetsuo Shibuya, Detecting Superbubbles in Assembly Graphs,
The 13th Workshop on Bioinformatics (WABI 2013), LNCS 8126, pp. 338-348, 2013.
[3] Alexander Bowe, Taku Onodera, Kunihiko Sadakane and Tetsuo Shibuya, Succinct de Bruijn Graphs,
The 12th Workshop on Algorithms in Bioinformatics (WABI 2012), LNCS 7534, pp. 225-235, 2012.
de Bruijn graph and the SDBG (Succinct de Bruijn Graph)
[Bowe, Onodera, Sadakane, Shibuya 2012]
• DNA Assembly: Reconstruction of genome from NGS reads
1E+16
• NP-hard problem / Input size: 300 Gbp
1E+15
• de Bruijn graph: Large graph needed for DNA Assembly
#bases
1E+14
• SDBG: Our new data structure that stores de Bruijn graph
in very small memory
1E+13
1E+12
Moore's Law
（2x in 18 months）
1E+11
• O(kn) → O(n), 300 bits/edge → 5 bits/edge
Single Reads
Size of the SRA database
（10x in 18 months）
2013
2012
2011
2010
2009
2008
2007
1E+10
TAG
$$$
CGT
$$$T
$$T
Paired Reads
TAGT
$TAG
GTCG
AGTC
$$TA
AGT
TCGT
CGTC
GTC
TCG
$TA
AGTT
TCGA
GAGT
Assemble
GTT
GAG
CGAG
GTT$
Genome
(contigs / scaffolds)
TT$
De Bruijn graph for
$$$TAGTCGTCGAGTT$
CGA
Knowledge Extraction from de Bruijn graphs
• Subgraphs related to:
• Multiploids, repeats, somatic variations, sequencing errors
• O(m2) needed to detect naively
34
• Intractable
gcag t
c
cta
tagatgcaagtgtagatacacag ta
3
tagatgcaagtgtagatacacag ta
28
2
6
cagtttgtattttttgttgagtgaatgt
ct
ccag t
28
cggcacaaaaa
18
tatgaggaaaaacaggg
17
aggatatg
att
3
tagtttgtattttttgttgagtgaatgt
tggcacaaaaa
28
28
ttt
gagatgcaagtgtagatacacag
c
1
1
ata
28
cc ata
gagatgcaagtgtagatacacag
17
28
25
ctg gggaaaaaacaggg aggatatg
ata
t
a tgttttttgtt gagtgaatgtctccag
11
c
23
aaa agtt
tatgaggaaaaacaggg
agttcagttt
g ggttttttgtt
gagtgaatgtctccagt
11
ggttttttgtt
att
ata
3
3
25
4
cggaaaaaacagggaggatatgatt
28
10
g
1
tgttttttgtt gagtgaatgtctccag
27
Superbubble
gggaaaaaacagggaggatatgatt
attg
agttcagttt
ata
aga
25
5
ta aga
Efficient Algorithms
[WABI2013, GIW2014]
• Average-case O(m) algorithm
• Utilize the statistical property of the graph
• Practically very fast
• Around 12 min./1 CPU for human-size genome
• Worst-case: O(m2)
• Worst-case O(m log m) algorithm
• Novel techniques that transform de Bruijn graphs to
tractable graphs
Keys to "Sublinear Big-Data Algorithms"
• Utilization of statistical behaviors of the data
• Transformation of data to tractable data
Major results of Tanaka group
関連発表
Poster
M1. Information Coarse Graining using Renormalization Group Theory
with Application to Image Processing
M2. Detection of Sparse Structure in Big Data with Application to
Detection of Cheating Students
M1. Sublinear Modeling:
from statistical-mechanical point of view
Statistical mechanics involves rich techniques for coarse graining of information.
low-dimensional data
BIG DATA
New Paradigm of Sublinear modeling
using
Statistical Mechanics
and
Machine Learning
Finding hierarchical structures of BIG DATA
(Hierarchical) Markov Random Field for Big Data
Structure inference of (hierarchical) MRFs generating Big Data
using statistical mechanical and machine learning techniques
Probability + Approximation + Algorithm
 Create a new scheme of sublinear-time algorithms for Big Data
Information Coarse Graining using Renormalization Group Theory
P ( r ) (a) ∝
1
Step 1
1
K(r-1)
 1 (r )

exp
,
K
δ
a
a
(
)
∏( r )  2
i
j 

{i , j }∈E
2
K(r)
K(r-1)
3
3
Step 2
1
K(r-1)
4
K(r-1)
K(r)
5
5
K(r+1)
K(r-1)
K(r-1)
6
K(r)
7
7
2


K ( r −1)
 q −1+ e

(r )
= 4 ln
K
( r −1)
/ 2 
 q − 2 + 2e K


y
 q −1+ ex 

y = 4 ln
x
/
2
 q − 2 + 2e



q=8
y=x
K
Inverse Renormalization Method
K(1)
K(2)
x
Application to Bayesian Image Segmentation
•
•
K. Tanaka, S. Kataoka, M. Yasuda, Y. Waizumi and C.-T. Hsu: Bayesian image segmentations by Potts prior
and loopy belief propagation, JPSJ, 2014.
K. Tanaka, S. Kataoka, M. Yasuda and M. Ohzeki: Inverse renormalization group transformation
in Bayesian image segmentations, JPSJ, 2015.
1728 Sec
Conventional Method
481 x 321
Segmentation by
Belief Propagation
for Original Image
30 x 20
Coarse Graining
Procedures
30 x 20 Labeled
Image
The new coarse graining method is
at least 10 times faster than
the conventional method
101 Sec
Grand Truth
M2. Detection of Sparse Structure in BIG DATA
Finding sparse structures in BIG DATA is important topic for an analysis of BIG DATA
e.g.) graph mining, data decomposition etc.
Find Sparse structure using
Extended Item Response Theory and Decimation Algorithm
Extended Item Response Theory (EIRT)
can detect characters of nodes and structure among nodes
Decimation Algorithm (DA)
can detect Sparse structure among nodes
The method without DA (EIRT + L1 regularization)
cannot detect a clear structure from data
optimal point of DA
detection error
Decimated pairs
The new algorithm can detect
the character of each node
and
the sparse structure
among nodes
The new algorithm
succeeded to detect
sparse structure in data
Application to detection of cheating students
S. Yamanaka, M. Ohzeki, A. Decelle: Detection of Cheating by Decimation Algorithm, JPSJ, 2015.
Newton 26th Feb. 2015
newspapers:
財経新聞, Jan. 2015
人民日報, Jan. 2015
朝日新聞, Jan. 2015
TV news coverage:
NHK, おはよう日本, Mar. 2015
Application to detection of cheating students
S. Yamanaka, M. Ohzeki, A. Decelle: Detection of Cheating by Decimation Algorithm, JPSJ, 2015.
• 27th March Broad casting from NHK「おはよう日本」
4. Summary
A1. Constant-Time Algorithms for Complex Networks
A2. Modeling and Simulation of Umeda Underground
Mall toward Algorithmic Evacuation Planning
D1. Sublinear-Space Compression and Its Application
D2. Extraction of Characteristic Subgraphs from LargeScale Assembly Graphs
M1. Information Coarse Graining using Renormalization
Group Theory with Application to Image Processing
M2. Detection of Sparse Structure in Big Data with
Application to Detection of Cheating Students
Steady Progress
Poster Presentations
複雑ネットワークに対する定数時間アルゴリズム
伊藤大雄
Online self-indexed grammar compression
高畠嘉将, 田部井靖生, 坂本比呂志
Direct Access to Variable-to-Fixed Length Codes
with a Succinct Index
喜田拓也
On Demand Calibrationを用いた広域歩行者追跡
和泉勇治
超事前分布を用いた確率的領域分割モデ
ルのパラメータ推定
古市智大，片岡駿，田中和之
Poster Presentations
複雑ネットワークに対する定数時間アルゴリズム
伊藤大雄
Online self-indexed grammar compression
高畠嘉将, 田部井靖生, 坂本比呂志
Direct Access to Variable-to-Fixed Length Codes
with a Succinct Index
喜田拓也
On Demand Calibrationを用いた広域歩行者追跡
和泉勇治
超事前分布を用いた確率的領域分割モデ
ルのパラメータ推定
古市智大，片岡駿，田中和之
複雑ネットワークに対する
定数時間アルゴリズム
「ビッグデータ時代に向けた
革新的アルゴリズム基盤」
ABD14 --- Team A
伊藤大雄
電気通信大学大学院情報理工学研究科
JST CREST
2016/3/7
ABD14全体会議
2
Back Ground and Our Target on Constant-Time Algorithms
Past Important Results
Target: Complex Networks
Dense-Graph Model:
• Every hereditary property is testable.
• Typical & important big graph data
• Includes web-graphs, social
networks, etc.
• Characteristics:
• small world
• high cluster
• power-law degree distribution
[Alon et al. FOCS05]
Degree-Bounded Model:
• Every minor-closed property is
testable. [Benjamini et al. STOC08]
• For hyperfinite graphs, every
property is testable. [Newman & Sohler
STOC11]
• → “sparse” and “degree
unbounded”
These algorithms cannot be applied.
We need new algorithms!
How to Model Complex Networks
CLUE
Isolated cliques [Ito & Iwama 05,09]:
<k
k vertices
Highly related with “high cluster.”
[Uno & Oguri 11] [Shigezumi, Uno, Watanabe 11]
observed that if a graph G is a complex network,
then:
1.G includes many isolated cliques,
2.G’ that is obtained by contracting all isolated
cliques of G has a similar structure, and
3.The above operation can be applied recursively
several times.
We introduce a new graph class HSF (Hierarchically Scale-Free Multigraphs)
If G is in HSF, then
i.G obeys power-law degree distribution,
ii.G includes at least one isolated clique,
iii.G’ that is obtained by contracting all isolated cliques of G also has the
above property (i) and (ii) if |G|≥c, which is a given constant.
Our New Results
Theorem [Ito 15]
HSF is hyperfinite*.
For this class, every property is testable in constant-time.
*Hyperfinite: A graph can be decomposed into constant-sized components by removing at most εn edges
(n is # of vertices).
Importance of this theorem:
a) First results on universal testers on the general (=sparse & degree un-bounded)
graph model.
b) By using this result (algorithm), whether a big complex network have any specified
property can be tested in constant-time.
Future work:
• Practical usefulness: computer examination by using actual data.
practical side
• Which property is easy to test in practice?
• Extending the theorem, e.g., cliques → dense subgraphs.
theoretical side
• Theoretical characterization of properties that are easy to test.
Online self-indexed grammar
compression
高畠嘉将, 田部井靖生, 坂本比呂志
Online self-indexed grammar compression
高畠嘉将 (九工大), 田部井靖生 (JST PRESTO), 坂本比呂志 (九工大)
SPIRE2015 で発表済み
• 繰り返しの多いテキストのための部分文字列の出現位置・回数
を検索可能な索引
• 例) 個人のゲノム、バージョン管理された文書やソースコード
• 文法圧縮索引 = 繰り返しの多いテキストに有効
• 通常の索引は入力テキストと索引が必要だが、文法圧縮索引は繰り返し
の多いテキストを高圧縮率で圧縮したデータのみで省領域に検索可能
• 既存の文法圧縮索引の構築はオフライン
• 入力テキストが全てないと構築不可
• 新たな文字を末尾追加する場合、一度データを解凍して、作り直すので
入力長に依存した計算時間及び領域が必要
• 圧縮データサイズに依存した領域かつ高速に新たな文字を末尾
追加可能なオンライン文法圧縮索引を提案
オフライン圧縮索引との
比較実験 (english text 446MB)
• 圧縮領域で構築可能
• 構築時間および検索時間
は低下
構築領域（ＭＢ）
入力長
• オンライン化のために
遅いデータ構造を用いた
ため
構築時間（sec）
検索時間（msec）
Direct Access to Variable-to-Fixed
Length Codes with a Succinct Index
喜田拓也
Direct Access to Variable-to-Fixed Length Codes with a Succinct Index
発表者：喜田拓也（北海道大学）加藤CREST劣線形データ構造チームメンバー（チームリーダー：渋谷哲朗）
・気象衛星データ
・航空写真データ
リモートセンシングデータ
Remote sensing data
GPS
Internet SNS
・GPSログ
・ライフログ
・市民からの情報提供
・市民への道路情報の提供
ビッグデータ
GPSログ・ライフログデータ
GPS logs, Life logs
UGCデータ
User Generated Content data
20120101000000,3,5.0,1,120,644132,00008,168933376,555574333,09853,168933408, ・・・
20120101000000,3,5.0,1,110,644132,00008,168933376,555574333,09853,168933408, ・・・
20120101000000,3,5.0,1,120,644132,00009,168989212,555755788,00036,168990785, ・・・
・・・
Repair-VF：データ検索やデータ解析時に再利用しやすいデータ圧縮方式
高速なデータ展開
Repair-VF
圧縮したまま検索可能
優れた圧縮性能
Fully Indexable Dictionary (FID;完備辞書)
高速な部分文字列抽出を実現！
実験結果：部分文字列抽出の速度比較
抽出位置 𝑝𝑜𝑠 を変化させたときの抽出時間（CPU時間）をプロット
FOLCA
既存手法（FOLCA）と比較して，
１０倍以上高速に部分文字列
を取り出すことができる
FIDを含めても圧縮率は同等
method
RVF+RRR
RVF+DA
RVF+SDA
dna
proteins
english
RVF w/o index
28.43
46.27
30.53
RVF+DA
47.83
63.78
47.62
RVF+SDA
60.86
62.39
45.54
RVF+RRR
41.05
54.17
38.60
FOLCA
40.69
50.34
47.25
(% of the compressed size / the original size)
On Demand Calibrationを用
いた広域歩行者追跡
和泉勇治
On Demand Calibrationを用いた広域歩行者追跡
加藤CREST 劣線形モデリンググループ
東北大学大学院情報科学研究科和泉勇治
• 避難シミュレーションにおける歩行者の初期位置の取得
• 歩行者の初期位置と歩行の向きを取得
• 歩行者検知＋追跡
• より広域に歩行者を追跡し，
高精度なシミュレーションの実現
• 複数のカメラ画像に跨る歩行者追跡
• カメラ画像間の共通領域が無い撮影状況での歩行者追跡
• Non-Overlapping Fields of View
参照：合田祥子「大都市地下街の津波避難計画に関する研究」
On Demand Calibrationを用いた広域歩行者追跡
加藤CREST 劣線形モデリンググループ
東北大学大学院情報科学研究科和泉勇治
•
カメラ毎の撮影状況が異なる
–
共通色物体を利用した色の補正
,
•
W : Calibration Matrix
: RGB values of Sampling Point
IoT/M2Mからのアプローチ
–
自律的な情報交換
•
•
追跡精度
53.03% → 71.12%
•
トラヒック量
–
–
提案方式： 480kBps
中央方式： 14400kBps
超事前分布を用いた確率的領
域分割モデルのパラメータ推定
古市智大，片岡駿，田中和之
超事前分布を用いた確率的領域分割モデルの
東北大学大学院情報科学研究科
パラメータの推定
古市智大，片岡駿，田中和之
• 確率的領域分割[1]
Pr A|α
PottsPrior
Pr A|F
Pr F|A
分割画像 A
• くりこみによる高速化[2]
観測画像 F
2713[sec]
481×321
64×41
α ＝3.171
600[sec]
α ＝3.213
• 問題点
• くりこみにより平滑化パラメータの画像ごとの差異がなく
なってしまう
⇨平滑化パラメータの分布をモデルに導入
超事前分布
αf i x ＝3.229
64×41
α ＝2.489
α ＝3.213
α ＝3.461
超事前分布
α ＝18.931
[1]K. Tanaka, S. Kataoka, M. Yasuda, Y. Waizumi and C.‐T. Hsu: Bayesian image segmentations by Potts prior and loopy belief
propagation, JPSJ, 2014.
[2] K. Tanaka, S. Kataoka, M. Yasuda and M. Ohzeki: Inverse renormalization group transformation in Bayesian image
segmentations, JPSJ, 2015.

Download Report