情報可視化における最適化モデルの定式化
会津大学
高橋 成雄

可視化(ビジュアリゼーション)
複雑な対象データの特徴をコンピュータグラフィックス技術を用いて効果的に視覚化する技術
n 「百聞は一見にしかず」n

観察対象
00110101

可視化の要素技術
nScientific Visualization
科学的可視化nn

数値データの可視化技法(空間構造あり)

Information Visualization
情報可視化
n

n

多変量データの可視化

抽象データの可視化技法(空間構造なし)

Visual Analytics
視覚分析論n

可視化と対話処理の融合による知識発見

Scatterplot matrix

Parallel coordinates

1ツリーの可視化

グラフの可視化

平安京ビュー

Cone tree

Treemap

VRC Report

Visualization Discovery Process
ViSCレポート(1987)の後継版
n IEEE Vis. 2005 でドラフト
配布
n 2006.1 最終版
nnVisualization systems are explicitly
designed not to replace the human
but to keep the human in the loop byextending human capabilities.

http://tab.computer.org/vgtc/vrc/

72

Overview

情報可視化の技術的課題
n

最適化問題として定式化
データのクラスタリングや分類
n 視覚表現の図式化およびレイアウト問題
nGradient
methods

個々の解のモデル化は問題ごとに異なる
l 共通の最適化手法が広範囲の問題に適用可能lGradient Method
Cost function

Overview
Gradient
methods

Multivariate analysis

3Subspace Mining from High-Dimensional Data

Analyzing Multivariate Data

〜Asymmetric Biclustering for Finding Data Correlation〜Dataarrangement

Data
analysis

Important features

Dimension

SampleData

MatrixKnowledge

K. Watanabe, H.-Y. Wu, Y. Niibe, S. Takahashi, I. Fujishiro. Biclustering Multivariate Data for
Correlated Subspace Mining, Proc. IEEE Pacific Visualization Symposium 2015, 287-294,
2015.

Biclustering Data Samples andDimensions
Important features

Clusters ofCorrelated
dimensions

Biclustering MethodnBlock model[Hartigan, 1972; van Mechelen et al., 2004]…
Biclustering techniques forcorrelated subspace mining

Clusters ofdata samples
close to each other4K-means ClusteringnBiclustering Method

Minimize the sum of distances from thecorresponding cluster centers

θ1

r5

r4
r6

r1

r3

θ2

n

K-means OK!!
nmin ∑ ri − θκ (i)2

i =1 j =1

i=1

c4

c6

Spherical K-means Clustering

Projected onto a high-dimensional
sphere
c7
c2

c3
c1

R

d

min åå ( xij - n k ( i ), l ( j ) ) 2

NormalizationnSymmetric application of K-means to rows
K-means OK??
and columns
…

r2

r7

[Hartigan, 1972; van Mechelen et al., 2004]

Block model

θ3nheight, BMI,PE class, distance,
literature, English,
math, physics, …

n

c!7

n

c!2

S

n

Inner product represents correlation
c!7

n−1

µ1

d d

2
min å
max
åc~c~j -j ×µµl (lj() j )c!2

j =1j =1

Inner product

c5

c!1

c!6
c!4

c!5

c!3

c!6

µ3

c!4

c!5

c!1
!c3 µ

2

n students

5Spherical K-means Clusteringn

Inner product represents correlation

Asymmetric Biclusteringnc! p ⋅ c!q = c! p c!q cos ϕn∑ (x − x )(x − x )=∑ (x − x ) ∑ (x − x )
i=1

ip

p

n

c! p

ϕ

c!q

i=1

2

ip

p

iq

iq

c2

c6
c4

c5

c1
c3 µ

2

2

q

Pearson product-moment
correlation coefficient

Strongly-correlated

µ1
c7

µ3

q

n

i=1

Iterative algorithm forreducing the objectivefunction monotonically

Block error1å å {~xij - s( j )n k ,l }2
nk d l i: k ( i )=k j: l ( j )=l

Uncorrelated

Type la Supernova Data

Overview
Gradient
methods

Multivariate analysis

Data is provided by courtesy ofProfessor Uemura of Hiroshima Univ.

6

Anchored Maps of Image Feature Space

Bag-of-Features Model〜Projecting High-Dimension through Bipartite Relationships～
Feature space

A

a

n
B

b

Associate each image with a set offeatures

C
ImagesRepresentative features

Representative
features

The bipartite graph
Representative features

Feature space

Anchored Map Representation

a

A

B
b
C
ImagesCoarse level

Representative
features

The bipartite graph

Fine level

Y. Gao, H.-Y. Wu, K. Misue, K. Mizuno, S. Takahashi. Visualizing Bag-of-Feature Image
Categorization Using Anchored Maps, Proc. VINCI 2014, 39-48, 2014.

Anchored Map Representation

Visualizing Bipartite RelatioshipsnVisualize the bipartite graph using
anchored map representations
AanForce-directed algorithm is employed

A

B
b
C
ImagesRepresentative
features

Bipartite graph

B

C
Landmarks

Anchored map

7

Anchored Map Representation

The Force Directed Algorithmn

Avoid excessive visual clutter usingdrawing and repulsive forcesn

Genetic-based optimizationn

improve the visual readability of theanchored map.
1

Fs (vi ) = ∑ kd (| vi − v j | −l0 )(v j − vi )
j∈N i

l0

vi

− ∑

kγ (vk − vi )2k∈V −{i} | vi − vk |Drawing
force
Repulsiveforce

l0 : original length

Gene

Anchored Map Representation

2

0

3

4

0

1

2

3

4

2

4

3

0

4

1

2

3

0

DemonstrationnOriginal layout

1

Discriminate car images from others.

With an optimized circularordering of features8

OverviewLinear Programming (LP)n

Gradient
methodsn

Inequality constraints

Objective function

y

S

x

Linear Programming (LP)contour lines ofthe objective functionnInequality constraints

9x + 25y ≥ 50

Objective function

n

S

x

x≤6

y

3x − 4y ≥ 4x≤63x − 4y ≥ 4

9x + 25y ≥ 50
minimize c = x + 2y

3x − 4y ≥ 4minimize c = x + 2y

Linear Programming (LP)ncontour lines ofthe objective function

9x + 25y ≥ 50

Linearprogramming

3x − 4y ≥ 4x≤6

y3x − 4y ≥ 4x≤6Multivariate analysisnInequality constraints

contour lines ofthe objective function

3x − 4y ≥ 4
9x + 25y ≥ 50

Objective function
minimize c = x + 2y

S

x

x≤6

9

Linear Programming (LP)nInequality constraints

9x + 25y ≥ 50ncontour lines ofthe objective functiony3x − 4y ≥ 4x≤6Overview
Map composition

3x − 4y ≥ 4Multivariate analysis

9x + 25y ≥ 50 c

Objective function
minimize c = x + 2yGradient
methods

Linearprogramming

s*

S

x

x≤6

Disoccluding Routes in Urban Maps
〜Constrained Optimization for 3D Urban Map Layouts～

Hand-Drawn Urban Maps

Synthesized map
D. Hirono, H.-Y. Wu, M. Arikawa, S. Takahashi. Constrained Optimization for Disoccluding
Geographical Landmarks in 3D Urban Maps, Proc. IEEE Pacific Visualization Symposium
2013, 17-14, 2013.

(by)

Hand-drawn map(by ATP Jihlava)

10Hand-Drawn Urban Maps
Roads
occludedRoads
visibleSynthesized map(by)

Hand-drawn map(by ATP Jihlava)

Goal
Deform 3D urban maps to enhance theirreadability

Optimized layout

Original layout

Overview
Input

・Buildings(prisms)
・Roads(polylines)

Keep the consistency in the map layout

Fixedorientation

Relative
position

Scale limits

Minimize occlusion and displacement

Minimum
displacement

Occlusion
avoidance

Output

Hard
Soft

LP

Formulate the problem using the linear programming (LP)11

Overview
Input

・Buildings(prisms)
・Roads(polylines)

Linear optimization problem

Keep the consistency in the map layout

Fixedorientation

Relative
position

OutputSoft

Fixed Orientation

Scale limits

y
x

Hard

Minimize occlusion and displacement

Minimum
displacement

Hard

Soft

P(X p ,Yp )Q(X q ,Yq )Occlusion
avoidance

LP

Formulate the problem using the linear programming (LP)Linear optimization problem
Hard

Linear optimization problem

Soft

Hard

Fixed Orientation

P(X p ,Yp )Q(X q ,Yq )Fixed Orientationyp(x p , y p )yp(x p , y p )xP(X p ,Yp )q(xq , yq )Soft

Q(X q ,Yq )x

1: sq(xq , yq )12OverviewLinear optimization problem
Hard

Soft

Input

Fixed Orientationx・Buildings(prisms)
・Roads(polylines)

1: sQ(X q ,Yq )" x − x = s(X − X )
$ p q
p
q
#
y
−
y
=
s(Y
−Y
$% p qpq)Fixedorientation

Relative
position

Scale limits

Minimize occlusion and displacement

Hard
Soft

q(xq , yq )Minimum
displacementHard

V(X v ,Yv )Soft

Relative PositionyxV(X v ,Yv )Q(X q ,Yq )P(X p ,Yp )LP

Linear optimization problem

Soft

Relative Position

Occlusion
avoidance

Formulate the problem as a constrained optimization problem

Linear optimization problem
Hard

Outputyp(x p , y p )P(X p ,Yp )Keep the consistency in the map layoutyx
Q(X q ,Yq )(A, B)P(X p ,Yp )13

Linear optimization problem
Hard

Linear optimization problem

Soft

Hard

Relative Position

Soft

Relative PositionyxV(X v ,Yv )DP(X p ,Yp )L : Ax + By + C = 0(A 2 + B 2 = 1)

Hard

Hard

V(X v ,Yv )D(A, B)

L : Ax + By + C = 0(A 2 + B 2 = 1)

Linear optimization problem

Soft

Relative Position

Q(X q ,Yq )P(X p ,Yp )(A, B)

Linear optimization problemx

V(X v ,Yv )Q(X q ,Yq )(A, B)

ySoft

Relative PositionyxV(X v ,Yv )D = A(X v − X P ) + B(Yv −YP )D

Q(X q ,Yq )P(X p ,Yp )L : Ax + By + C = 0(A 2 + B 2 = 1)

(A, B)yx
Q(X q ,Yq )P(X p ,Yp )L : Ax + By + C = 0(A 2 + B 2 = 1)

14Linear optimization problem
Hard

Linear optimization problem

Soft

Hard

Relative Position

Soft

Relative PositionyyPositive sidex

V(X v ,Yv )D = A(X v − X P ) + B(Yv −YP )DDQ(X q ,Yq )P(X p ,Yp )(A, B)

Linear optimization problem
Hard

Hard

V(X v ,Yv )D(A, B)

Soft

Relative Positionyv(xv , xv )Positive side

D = A(X v − X P ) + B(Yv −YP ) > 0

Negative side

L : Ax + By + C = 0(A 2 + B 2 = 1)

Linear optimization problem

Soft

Relative Position

Q(X q ,Yq )P(X p ,Yp )(A, B)

L : Ax + By + C = 0(A 2 + B 2 = 1)x

V(X v ,Yv )D = A(X v − X P ) + B(Yv −YP )x
Q(X q ,Yq )P(X p ,Yp )Negative side

L : Ax + By + C = 0(A 2 + B 2 = 1)q(xq , yq )dV(X v ,Yv )D = A(X v − X P ) + B(Yv −YP ) > 0p(x p , y p )(A, B)
D(A, B)yx

Q(X q ,Yq )P(X p ,Yp )L : Ax + By + C = 0

15

Linear optimization problem
Hard

Linear optimization problem

Soft

Hard

Relative Position
Positive sidev(xv , xv )q(xq , yq )dV(X v ,Yv )D = A(X v − X P ) + B(Yv −YP ) > 0p(x p , y p )(A, B)
D(A, B)

Soft

Relative PositionyPositive sidex
Q(X q ,Yq )P(X p ,Yp )Negative sidev(xv , xv )q(xq , yq )dV(X v ,Yv )D = A(X v − X P ) + B(Yv −YP ) > 0p(x p , y p )(A, B)
Dd = A(xv − xP ) + B(yv − yP ) > 0(A, B)

L : Ax + By + C = 0

yx

Q(X q ,Yq )P(X p ,Yp )Negative side

L : Ax + By + C = 0

Results: Sharply Curved Route

Results: All the Routes on the Map

Original Layout

Original Layout

Optimized Layout

Optimized Layout

16Results: Landmark Buildings

Results: Annotating Roads

Original Layout

Original Layout

Optimized Layout

Results: Statistics

Optimized Layout

Overview
Gradient
methods
Map composition

Preprocess

1.2 sec

15.6 sec

6.7 sec

2.4 sec

2.7 sec

Optimization

3.1 sec

53.0 sec

12.7 sec

6.9 sec

8.4 sec

Number ofvariables

12,372

117,724

45,77422,36325,490

Number of
constraints

34,057

322,615

105,690

59,06766,550Elevation
angle

25

20

20

20

30

Multivariate analysis

Linearprogramming

Integer
programming

17

Mixed-Integer Programming(MIP)

Linear Programming (LP)nInequality constraintsy3x − 4y ≥ 4x≤69x + 25y ≥ 50

9x + 25y ≥ 50 c

Objective function
minimize c = x + 2y

Inequality constraints

n

s*

S

x

y

3x − 4y ≥ 4x≤63x − 4y ≥ 4

9x + 25y ≥ 50nn

3x − 4y ≥ 4
9x + 25y ≥ 50 c

Objective function
minimize c = x + 2y

s

s*

S
NP hard

x≤6

x

x≤6

Spatially-Efficient Metro Map Layout

Overview〜Modeling Hand-Drawn Maps as Optimization Problems〜

Gradient
methods
Map composition
Multivariate analysis

2011

2012

Taipei MRT map handkerchief

Network analysis
Linearprogramming

Integer
programming

Octilinear

Orthogonal

H.-Y. Wu, S. Takahashi, D. Hirono, M. Arikawa, C.-C. Lin, H.-C. Yen. Spatially Efficient
Design of Annotated Metro Maps, Computer Graphics Forum, 32(3), 261-270, 2013.

18

Hand-Drawn Schematic Maps

Hand-Drawn Schematic Maps

Taipei MRT map handkerchief 2012
(Courtegy of Milu Design Co., LTD, Taiwan)

London Underground Map

EuroVis 2013, Leipzig, Germany

Map Aesthetic Criteria

The Eurographics Conference on Visualization

Layoutu (LH1) Edge octilinearity
u (LH2) Circular vertex orderu (LH3) Edge spacingu (LS1) Bend minimizationu (LS2) Relative position

minimizationu (LS3) Edge length

minimization
Tube map
1

Chesham9

Chalfont &LatimerAmersham

2

8

Watford

Rickmansworth

3

EdgwareStanmore

Harrow &Wealdstone

Harrowon-the-Hill

KentonQueensbury

PrestonRoad

Kingsbury

Stonebridge Park

Willesden Junction

KensalRise

Queen’s Park

Greenford

KilburnHigh Road

Kilburn Park

Perivale

Maida Vale
Warwick Avenue

North
Acton

South Acton
Acton Town
ChiswickPark

Shepherd’s
Bush

White
City

Wood Lane

Shepherd’s Bush
Market2

West
Kensington

2

Gunnersbury
Hounslow East
Kew Gardens

Hounslow Central

Hatton Cross

Richmond

Heathrow
Terminal 4

South
Hampstead

St. John’s Wood

EdgwareMarylebone
Road

4

5

3

Fulham Broadway
Parsons Green

PimlicoImperial
Wharf

VauxhallClaphamJunction

Wandsworth
Road

Surrey Quays

South Quay
Crossharbour

Kennington

Star Lane
Canning
Town

BlackwallRoyal
Victoria

East
India

3

Queens Road
PeckhamTooting Bec

Tooting Broadway

Colliers Wood

South Wimbledon

2

3

Morden4

Peckham Rye

Emirates
GreenwichPeninsulaRoyal AlbertD

Beckton Park

Pontoon Dock

2

New Cross

BecktonNot served by DLR trains from Bank towards
Lewisham before 1900 on Mondays to Fridays---------------------------------------------------------------------------------King George V

Key to lines

3

Greenwich
Deptford Bridge
Elverson Road
Lewisham

Forest Hill

Woolwich
ArsenalE

4

Jubilee
Metropolitan
Northern
Piccadilly

Anerley

Crystal Palace

F

Norwood Junction

6

5

7

Waterloo & City
London Overground

This diagram is an evolution of the original design conceived in 1931 by Harry Beck
Correct at time of going to print, December 20128

Victoria
DLR

West Croydon

5

Central
CircleHammersmith & City

Penge West

3

Bakerloo

District
District open weekends, public
holidays and some Olympia events

4

SydenhamBrixtonStep-free access for wheelchair users only--------------------------------------------------------------------------------Turnham Green
Served by Piccadilly line trains until 0650
Monday to Saturday, 0745 Sunday and after 2230
every evening. At other times use District line--------------------------------------------------------------------------------Waterloo
Waterloo & City line open 0615-2141 Mondays
to Fridays and 0800-1831 Saturdays.
Closed Sundays and Public Holidays--------------------------------------------------------------------------------West India Quay

Gallions
Reach

LondonCity Airport

Cutty Sark for
Maritime Greenwich

New Cross
Gate
Brockley

Honor Oak Park

Denmark Hill

Clapham North

Prince Regent

Cyprusfor The O2Open until 2100 Mondays to Fridays.
Closed Sundays and most Saturdays--------------------------------------------------------------------------------Emirates Greenwich Peninsula andEmirates Royal Docks
Special fares apply. Open 0700-2000 Mondays
to Fridays, 0800-2000 Saturdays, 0900-2000
Sundays and 0800-2000 Public Holidays.
Closed on Christmas Day.
Opening hours are extended by one hour in theevening after 1 April 2013 and may be extendedon certain events days.
Please check close to the time of travel.
--------------------------------------------------------------------------------Heron Quays
Step-free interchange between Heron Quays
and Canary Wharf Underground station atstreet level--------------------------------------------------------------------------------Hounslow West

4
Custom House for ExCeL

Emirates
Royal DocksWest
Silvertown

North
GreenwichIsland Gardens

StockwellClapham High Street

CWest Ham

Langdon ParkAll Saints

West
India Quay

Heron Quays

Borough

Elephant & Castle

Oval

Upney
Barking
East Ham
Upton Park

Plaistow

Bromleyby-Bow
Devons Road

PoplarCanary Wharf

CanadaWater

Mudchute
Lambeth
North

Becontree

Woodgrange Park
Stratford
High Street2

Westferry

Limehouse

Wapping

Rotherhithe
Bermondsey

Abbey
Road

Bow Road

Stepney GreenWhitechapel
ShadwellTower
Gateway

River ThamesSouthwark

1
2

AldgateEast
Aldgate

Tower
Hill

Fenchurch Street

LondonBridgeElm Park

Dagenham
Heathway

Stratford

Hackney
WickMile End

ShoreditchHigh Street
Bow Church

Monument

Sunday 1300 -1730 open for interchange andexit only--------------------------------------------------------------------------------Canary Wharf

B

Hornchurch
Dagenham
East

Wanstead Park

Pudding
Mill Lane

Bethnal
Green

1

Bank

Blackfriars

Waterloo & City line open 0621-2148 Mondays
to Fridays and 0802-1837 Saturdays.
Closed Sundays and Public Holidays--------------------------------------------------------------------------------Camden Town

Step-free interchange between Underground,
Canary Wharf DLR and Heron Quays DLR
stations at street level--------------------------------------------------------------------------------Cannon Street
UpminsterUpminster Bridge

LeytonstoneHigh Road

Harry Beck, 1933
Wimbledon

Balham1

HoxtonLiverpool
StreetMoorgate

St. Paul’sCannon Street
Mansion House
TempleEmbankment

Waterloo

Clapham Common

Transport for London

Homerton

2

Haggerston

Old Street

BarbicanChancery
Lane
Holborn

Covent Garden

Charing
Cross

Westminster

Clapham SouthF

Dalston Junction

Angel

Farringdon

Russell
SquareLeicester Square

Piccadilly
CircusSt. James’s
Park

Check before you travel
Bank

A

Gants
Hill

LeytonStratford
International

Hackney
CentralFairlop
Barkingside
Newbury Park

Wanstead
Leytonstone

LeytonMidland Road

3

DalstonKingsland

CanonburyKing’s Cross
St. Pancras

EustonSquareGoodgeStreetTottenham
Court Road

Green Park

East Putney
Southfields

Highbury &Islington

Caledonian
Road &
Barnsbury

5

GrangeHill

Chigwell
Hainault

4

Redbridge

Walthamstow
CentralWalthamstow
Queen’s Road

Holloway Road
Caledonian Road

Snaresbrook

BlackhorseRoad
Tottenham
Hale

EustonWarren Street

OxfordCircusVictoria
SloaneSquareSouth
Kensington

Putney Bridge

Wimbledon Park

Mornington
Crescent

Great
PortlandStreetBaker
StreetBond
StreetMarbleArch

1

Hyde Park Corner
Knightsbridge

Earl’sCourt

FinsburyPark

ArsenalCamdenRoad

Camden Town

Regent’s Park

Lancaster
Gate

Queensway
High Street
Kensington

Gloucester
Road

Barons
Court

Hammersmith

Chalk Farm

Bayswater
Notting
Hill Gate

HollandPark

Kensington(Olympia)

Goldhawk Road

Turnham Stamford Ravenscourt
Brook
Park
Green

West Brompton

Heathrow
E Terminals 1, 2, 3

Heathrow Terminal 5

Swiss Cottage

EdgwareRoad
Ladbroke Grove

Latimer Road
East
Acton

West
Acton
Acton Central

Ealing Common

Osterley

HounslowWest

Paddington

Westbourne Park

Park RoyalNorth Ealing

3

South Ealing

Finchley Road

Royal Oak

Hanger Lane

Ealing Broadway

2

West Hampstead

Brondesbury

South Woodford
South Tottenham

Seven
Sisters

Upper Holloway

Kentish Town

KentishTown West

Belsize Park

Kilburn

Brondesbury
Park

Kensal Green

D

Northfields

Finchley Road
& Frognal

Willesden Green

Harlesden

Alperton

9

RodingValleyWoodford
Harringay
Green Lanes

Manor House

Tufnell Park

6

DebdenBuckhurst Hill

Wood Green

Crouch Hill

Archway
GospelOak

Loughton

Oakwood

Arnos Grove
Bounds Green

Turnpike Lane

Highgate

Hampstead
Heath

Hampstead

Dollis Hill

8
EppingCockfosters

SouthgateWest Finchley
Finchley Central
East Finchley

3

Brent Cross
Golders Green

Sudbury Hill

7

Theydon Bois

Mill Hill EastColindale
Hendon Central

NeasdenWembleyPark

Sudbury Town

Boston Manor

Burnt Oak

Canons Park

Northwick
Park
South Kenton

North Wembley
Wembley Central

Woodside Park

4

Hatch End
Headstone Lane

North Harrow

West
HarrowSouth Harrow

Northolt

6 5 4

6High Barnet
Totteridge & Whetstone

Carpenders Park

PinnerEastcote
Rayners Lane

C

5

5

BusheyRuislip Manor

Ruislip
Gardens

8 7 6

Watford Junction
Watford High Street

NorthwoodNorthwood
Hills

Ruislip

IckenhamSouth Ruislip

4Special fares apply

Moor ParkWest Ruislip
Hillingdon
UxbridgeB

7Croxley

Chorleywood

A

Emirates Air Line

9

MAYOR OF LONDON

19

Map Aesthetic Criteria

LayoutSoft Constraints

Annotationu (LH1) Edge octilinearity¨u (LH2) Circular vertex order¨u (LH3) Edge spacingu (LS1) Bend minimizationu (LS2) Relative position

minimizationu (LS3) Edge length

minimization(AH1) Leader octilinearity(AH2) Overlap-free layout¨ (AS1) Leader orientation¨ (AS2) Total leader length¨ (AS3) Leader bends¨ (AS4) Closed regions¨ (AS5) Alternating distributionnC=(AS1) Leader orientation penalty+(AS2) Leader length penalty+(AS3) Leader bend penalty+(AS4) Closed region penalty+(AS5) Label consistency penalty

Tube map
1

Chesham928Chalfont &LatimerAmersham

Watford

Rickmansworth

3

EdgwareStanmore

Harrow &Wealdstone

Harrowon-the-Hill

KentonQueensbury

PrestonRoad

Kingsbury

Northolt

Golders Green

Harlesden

KensalRise

Willesden Junction

Queen’s Park

Westbourne Park

Park Royal

East
Acton

West
Acton

North
Acton

Acton Central
South Acton

South Ealing
Northfields

Acton Town
ChiswickPark

Shepherd’s
Bush

White
City

Wood Lane

Shepherd’s Bush
Market2

Turnham Stamford Ravenscourt
Brook
Park
Green

West
Kensington

2

Gunnersbury
Hounslow East
Kew Gardens

Hounslow Central

Hatton Cross

Richmond

4

Heathrow

E Terminals 1, 2, 3

Heathrow
Terminal 4
Heathrow Terminal 5

St. John’s Wood

Earl’sCourt

5

3

Fulham Broadway
Parsons Green

Victoria

PimlicoVauxhallClaphamJunction

WandsworthRoad

LondonBridgeHeron Quays
South Quay
Crossharbour

Southwark

Mudchute
Lambeth
North

Royal
Victoria

East
India

3

Kennington

Queens Road
PeckhamTooting Broadway

Colliers Wood

South Wimbledon

2

3

Morden4

Royal AlbertD

Beckton Parkfor The O2Emirates
GreenwichPeninsula

Pontoon Dock

Gallions
Reach

LondonCity Airport

2

Beckton

New Cross
Gate

New Cross

Key to lines

Greenwich
Deptford Bridge

Brockley

Elverson Road
Lewisham

Forest Hill

Woolwich
ArsenalE

34Circle57

Metropolitan
Northern
Piccadilly
Victoria
Waterloo & City
DLR
London Overground

This diagram is an evolution of the original design conceived in 1931 by Harry Beck
Correct at time of going to print, December 20128

Spatially efficient annotated map

Hammersmith & City

F

Norwood Junction
West Croydon

6

Bakerloo

JubileeAnerley

5

CentralDistrict
District open weekends, public
holidays and some Olympia events

4

Penge West

Crystal Palace

Step-free access for wheelchair users only--------------------------------------------------------------------------------Turnham Green
Served by Piccadilly line trains until 0650
Monday to Saturday, 0745 Sunday and after 2230
every evening. At other times use District line--------------------------------------------------------------------------------Waterloo

Not served by DLR trains from Bank towards
Lewisham before 1900 on Mondays to Fridays---------------------------------------------------------------------------------King George V

3SydenhamBrixtonSpecial fares apply. Open 0700-2000 Mondays
to Fridays, 0800-2000 Saturdays, 0900-2000
Sundays and 0800-2000 Public Holidays.
Closed on Christmas Day.
Opening hours are extended by one hour in theevening after 1 April 2013 and may be extendedon certain events days.
Please check close to the time of travel.
--------------------------------------------------------------------------------Heron Quays

Waterloo & City line open 0615-2141 Mondays
to Fridays and 0800-1831 Saturdays.
Closed Sundays and Public Holidays--------------------------------------------------------------------------------West India Quay

CyprusNorth
Greenwich

Cutty Sark for
Maritime Greenwich

Honor Oak Park

Denmark Hill

Clapham North

Tooting Bec

Peckham Rye

StockwellClapham High Street

Prince Regent

West
Silvertown

Open until 2100 Mondays to Fridays.
Closed Sundays and most Saturdays--------------------------------------------------------------------------------Emirates Greenwich Peninsula andEmirates Royal Docks

Step-free interchange between Heron Quays
and Canary Wharf Underground station atstreet level--------------------------------------------------------------------------------Hounslow West

4
Custom House for ExCeL

Emirates
Royal Docks

Island Gardens

Borough

Elephant & Castle

Oval

Star Lane

Blackwall

Canary Wharf

CanadaWater

Surrey Quays

1
2

Bermondsey

CWest Ham

Canning
Town

All Saints

West
India Quay

Elm Park

Dagenham
Heathway
Upney
Barking
East Ham
Upton Park
Plaistow

Bromleyby-Bow
Devons Road
Langdon Park

PoplarHarry Beck, 1933
Wimbledon

Balham1

Rotherhithe

Embankment

2

Westferry

Limehouse

Wapping

Becontree

Woodgrange Park
Stratford
High Street
Abbey
Road

Bow Road

Stepney GreenWhitechapel
ShadwellB

Hornchurch
Dagenham
East

Wanstead Park
Stratford

Mile End

Bow Church
AldgateEast

Tower
Gateway

River Thames

Step-free interchange between Underground,
Canary Wharf DLR and Heron Quays DLR
stations at street level--------------------------------------------------------------------------------Cannon Street
UpminsterUpminster Bridge

LeytonHackney
Wick

Pudding
Mill Lane

Bethnal
Green

ShoreditchHigh Street

Aldgate

Tower
Hill

Fenchurch Street

TempleWestminster

Clapham Common

Transport for London

Homerton2

HoxtonMonument

Waterloo & City line open 0621-2148 Mondays
to Fridays and 0802-1837 Saturdays.
Closed Sundays and Public Holidays--------------------------------------------------------------------------------Camden Town
Sunday 1300 -1730 open for interchange andexit only--------------------------------------------------------------------------------Canary Wharf

Gants
Hill

LeytonstoneHigh Road

Stratford
International

Hackney
CentralHaggerston

1

Bank

Blackfriars

A

Fairlop
Barkingside
Newbury Park

Wanstead
Leytonstone

LeytonMidland Road

3

DalstonKingsland

Canonbury

Dalston Junction

Liverpool
StreetMoorgate

St. Paul’sCannon Street
Mansion House

Waterloo

Imperial
Wharf

Check before you travel
Bank

GrangeHill

Chigwell
Hainault

4

Redbridge

Walthamstow
CentralWalthamstow
Queen’s Road

Old Street

BarbicanChancery
Lane
Holborn

Charing
Cross

Clapham SouthF

Caledonian
Road &
Barnsbury

Angel

Farringdon

Russell
SquareCovent Garden

SloaneSquareSouth
Kensington

Highbury &Islington

Caledonian Road

King’s Cross
St. Pancras

EustonSquareLeicester Square

Piccadilly
CircusSt. James’sPark

Snaresbrook

BlackhorseRoad
Tottenham
Hale

EustonGoodgeStreetTottenham
Court Road

Green Park

East Putney
Southfields

Mornington
Crescent

FinsburyPark

ArsenalHolloway Road

CamdenRoad

Camden Town

Warren Street

Regent’s Park

OxfordCircusPutney Bridge

Wimbledon Park

Chalk FarmGreat
PortlandStreetBaker
StreetBond
StreetMarbleArch

1

Hyde Park Corner
Knightsbridge

West Brompton

Osterley

HounslowWest

Swiss Cottage

Lancaster
Gate

Queensway
High Street
Kensington

Gloucester
Road

Barons
Court

Hammersmith

Bayswater
Notting
Hill Gate

HollandPark

Kensington(Olympia)

Goldhawk Road

9RodingValleyWoodfordSouth Woodford
South Tottenham
Seven
Sisters

Upper Holloway

Kentish Town

5

Buckhurst Hill

Harringay
Green Lanes

Manor House

Tufnell Park

6

DebdenLoughton

Oakwood

Wood Green
Turnpike Lane
Crouch Hill

Archway
GospelOak

KentishTown West

Belsize Park

Finchley Road

South
Hampstead

EdgwareMarylebone
Road

EdgwareRoad
Ladbroke Grove

Latimer Road

North Ealing

Ealing Common

Boston Manor

Paddington

Royal Oak

Hanger Lane

3

2West Hampstead

Brondesbury
KilburnHigh Road

Kilburn Park
Maida Vale
Warwick Avenue

Kilburn

Brondesbury
Park

Kensal Green

Alperton

Perivale

Ealing Broadway

8
EppingCockfosters

Arnos Grove
Bounds Green

Finchley Central

Highgate

Hampstead
Heath

Hampstead
Finchley Road
& Frognal

Willesden Green

SouthgateWest Finchley

East Finchley

3

Brent Cross

Dollis Hill

Greenford

D

7

Theydon Bois

Mill Hill EastColindale
Hendon Central

NeasdenWembleyPark

Stonebridge Park

Sudbury Town

Burnt Oak

Canons Park

Northwick
Park
South Kenton

North Wembley
Wembley Central

Woodside Park

4

Hatch End
Headstone Lane

North Harrow

West
HarrowSouth Harrow

Sudbury Hill

6 5 4

6

High Barnet
Totteridge & Whetstone

Carpenders Park

PinnerEastcote
Rayners Lane

C

5

5

BusheyRuislip Manor

Ruislip
Gardens

8 7 6

Watford Junction
Watford High Street

NorthwoodNorthwood
Hills

Ruislip

IckenhamSouth Ruislip

4Special fares apply

Moor ParkWest Ruislip
Hillingdon
UxbridgeB

7Croxley

Chorleywood

A

Emirates Air Line

9(AS4) Closed region penalty (AS5) Label consistency penalty

MAYOR OF LONDON

Label Consistency Penalty

Three-Step Algorithm

cost ( AS 5) = ∑ adj( f j )For each enclosed regionj∈I f( f j (vi ))XOR(f j (vi+1 ))= ( f j (vi )AND f j (vi+1 ))OR( f j (vi )ANDf j (vi+1 ))2ai ≤ 1+ f j (vi ) − f j (vi+1 ) ≤ 1+ aiAND

2bi ≤ 1− f j (vi ) + f j (vi+1 ) ≤ 1+ biAND

1− adji ( f j ) ≤ ai + bi ≤ 2(1− adji ( f j )) ORAND
AND 2x ≤ x1 + x2 ≤ 1+ x
OROR x ≤ x1 + x2 ≤ 2x

fj

fj+1

1

0

(AS5) Label consistency penalty

20

Prague

LisbonTaipei

ViennaDemonstration

Overview
Gradient
methods
Map composition
Multivariate analysis
Network analysis
Linearprogramming

The London metro map

Integer
programming

21

Hierarchical Network Visualization~Partial Orders of Nodes Inference~

Complexrelationship

Fully understood

Dependency

Visualization

Input

Inferred hierarchy

Minimal edge crossing

OutputEdge contraction

Space adjustment

A→I→G
B→E->D
H→F→I->G
C→D→G
H→B→I
B→E→F->C
C→I→H
C→D→A

背景：ネットワーク複雑さ

Paths

Network data

H.-Y. Wu, S. Takahashi, H. N. Miyamura, S. Ohzahata, A. Nakao, Inferring Partial Orders of Nodes
for Hierarchical Network Layout, Journal of Imaging Science and Technology, pp. 60407-1-6040713(13), Vol. 60, No. 6, 2016.

背景：ネットワーク複雑さ

Network data

追跡

背景：ネットワーク複雑さ

Network data

or

追跡

or

視覚的に理解し難しい
分類

分類

22

考察：現実のネットワーク

考察：現実のネットワーク

問題:階層構造の推測と可視化

アイデア: ネットワークパスから推測nn

片道パス：パスがネットワーク階層を順々に登るものを仮定．
往復パス：低階層，高階層，低階層と移動する山形のパスを仮定．[Gao, 2001]
1
2

I

ui+2
C

ui+1

3

G

4

E ui-1

D

B
H

ui

F
A

k-th path

片道パス
往復パス
整数計画法による最適化を用いて類推する

23

手法：片道パス
E→G→C->I
E→C->B
A→G→H->B
A→H→D
A→F→D
入力

1

I

2

ui+2

D

B

C

ui+1

E

ui-1

3
4

手法：往復パス

ui

G

F→E→B->H->C->D->I
I→H→C→D->I
I→H→E->A
F→E→B->GH
F
Ak-th path

階層構造類推と可視化

入力

上りパス

ペナルティー，小さければよい．

p(ui ) − p(ui+1 ) ≥ 1− vi,i+1 階層ID= 2
p(ui ) − p(ui+1 ) ≤ λi,i+1

階層ID = 3

CGp(ui+1 )binary階層構造類推と可視化

binaryp(ui ) − p(ui+1 ) ≥ +α i,i+1 − M βi,i+1 − vi,i+1
p(ui ) − p(ui+1 ) ≤ λi,i+1

階層ID= 2p(ui )

手法：往復パスBEp(ui+1 )階層ID = 3

E

上りパス

下りパス

p(ui )

手法：往復パス
下りパス

p(ui+1 )α = 1, β = 0
階層ID = 3B

α = 1, β = 0

階層IDの差，小さければよい．

階層ID= 2上りパス

p(ui )

C

階層ID= 2p(u j )
α = 0, β = 1DBp(ui+1 )α = 1, β = 0
階層ID = 3

p(u j+1 )Ep(ui )Cp(u j )
α = 0, β = 1Dp(u j+1 )

上りパス

上りパス

p(ui ) − p(ui+1 ) ≥ +α i,i+1 − M βi,i+1 − vi,i+1
p(ui ) − p(ui+1 ) ≤ λi,i+1

p(ui ) − p(ui+1 ) ≥ +α i,i+1 − M βi,i+1 − vi,i+1
p(ui ) − p(ui+1 ) ≤ λi,i+1 上りパスと下りパスは両立はしないため，

下りパス

下りパス

p(u j ) − p(u j+1 ) ≤ −β j, j+1 + M α j, j+1 + v j, j+1
p(u j ) − p(u j+1 ) ≥ −λ j, j+1

p(u j ) − p(u j+1 ) ≤ −β j, j+1 + M α j, j+1 + v j, j+1
p(u j ) − p(u j+1 ) ≥ −λ j, j+1
α j, j+1 + β j, j+1 = 1

大きい整数Mを導入

24

(山形)
手法：往復パスターニングポイントは１つp(u )階層ID= 1H

αi+1,k = 1
階層ID= 2B

E

階層ID= 1p(ui+1 )C

階層ID= 2p(u j )D

上りパス

p(ui+1 )階層ID = 3

p(u j+1 )ECp(u j )
α j, j+1 = 0
Dp(ui )p(u j+1 )上りパス

p(ui ) − p(ui+1 ) ≥ +α i,i+1 − M βi,i+1 − vi,i+1
p(ui ) − p(ui+1 ) ≤ λi,i+1

p(ui ) − p(ui+1 ) ≥ +α i,i+1 − M βi,i+1 − vi,i+1
p(ui ) − p(ui+1 ) ≤ λi,i+1

下りパス

下りパス

p(u j ) − p(u j+1 ) ≤ −β j, j+1 + M α j, j+1 + v j, j+1
p(u j ) − p(u j+1 ) ≥ −λ j, j+1
α j, j+1 + β j, j+1 = 1
αi,i+1 ⊕ αi+1,k + αi+1,k ⊕ α k, j + α k, j ⊕ α j, j+1 = 1Bk

α k, j = 0

αi,i+1 = 1

α j, j+1 = 0

p(ui )

H

αi+1,k = 1

α k, j = 0

αi,i+1 = 1
階層ID = 3(山形)
手法：往復パスターニングポイントは１つ
p(u )

k

p(u j ) − p(u j+1 ) ≤ −β j, j+1 + M α j, j+1 + v j, j+1
p(u j ) − p(u j+1 ) ≥ −λ j, j+1
最小化 minimize w1 × λi,i+1 + w2 × vi,i+1
α j, j+1 + β j, j+1 = 1⊕(XOR)A Short Demonstration

αi,i+1 ⊕ αi+1,k + αi+1,k ⊕ α k, j + α k, j ⊕ α j, j+1 = 1⊕(XOR)

User Intervention

25

Applications 1: One-way PathnCurricula of Univ. of Aizu

Applications 2: Round-trip Pathn

Tokyo metro
255 stationsn 13 metro linesnForce-directed layout

Hierarchical layout

Reverse paths are more penalized

Numbers of credits are equalized at
the respective layers

Accessibility zones inferred fromthe metro network

Visualizing hierarchies among
the metro stations

Overview

Applications 3: Round-trip Pathn

P2P networkn

116 nodes, 306 edges, and 525 paths

Hierarchical structures

Grouped nodes

Gradient
methods
Map composition
Genetic
algorithms Multivariate analysis

Edge contraction

Network analysis
Linearprogramming

Integer
programming
Optimized layout large-sized P2P network

26

Genetic Algorithm

Genetic Algorithm
Crossover

Population
1

2

3

4

5

1

2

5

4

3

Termination

Initialization

Evaluation

Chromosomes
Replacement

Multation

Selection
Loop until
termination
Crossover

Mutation

Dynamic Map Labeling on Continuous Scales

Overview〜Consistent label placement for maps of high readability～

Cartographic design

Gradient
methods

Map composition

Independent
scale

Genetic
algorithms Multivariate analysis

Large

Network analysis
Linearprogramming

Map scale

Small

Continuous
scale

Integer
programming
H.-Y. Wu, S. Takahashi, S.-H. Poon, M. Arikawa. Ongoing project. Intermediate results will
be presented at International Cartographic Conference 2017.

27

デジタルマップの普及
nラベル配置の問題点

異なるスケール(縮尺)による地図表示

nスケールの変化にラベル出現消滅する

109

110

Objectives
Optimize label placement on the map
n Retain the consistency in labeling overthe map scalen

Scale-Aware Label PlacementnSpecific area shrinks as the scale reduces
Scale
1/200

1/150

1/100

Label size is fixedSpecific area28

Scale-Aware Label PlacementnLabels expand/shrink as the scale changes

Scale-Aware Label Placementn

Inverseof the scale
200

150

150

100

100

Scale-Aware Label PlacementnLabels expand/shrink as the scae changes

Inverseof the scale
200

Select labels according to the scale

Inverseof the scale

Overlaps between labels

#1

#2

#3
map space

Scale-Aware Label PlacementnSelect labels according to the scale

Inverseof the scale

#2

#1
1

2

3

#3
map space29

Scale-Aware Label PlacementnSelect labels according to the scale

Inverseof the scale

Scale-Aware Label Placement
n

#2

#1
1

2

3

#3
map space

Select labels according to the scale

Inverseof the scale

#2

#1
1

Scale-Aware Label PlacementnSelect labels according to the scale

Inverseof the scale

2

3

#3
map space

Scale-Aware Label PlacementnSelect labels according to the scale

Inverseof the scale

#2

#1
1

2

3

#3
map space

#2

#1
1

3

2

#3
map space30

Scale-Aware Label PlacementnSelect labels according to the scale

Inverseof the scale

Scale-Aware Label Placement
n

#2

#1
1

3

2

#3
map space

Select labels according to the scale

Inverseof the scale

#2

#1
1

Scale-Aware Label PlacementnSelect labels according to the scale

Inverseof the scale

3

2

#2

1

3

2

#3
map space

map space

Active RangenTotal scale range that contain the labels= 23 intervals

Inverseof the scale

#1

#3

#2

#1
1

3

2

#3
map space

31

Active Rangen

Demonstration

Total scale range that contain the labels= 19 intervals

Inverseof the scale

#2

#1
1

2

3

#3
map space

Topological Surgery for Mesh Unfolding

Overview〜Papercraft Construction from a Single Patch～

Cartographic design

Gradient
methods

Map composition

Entertainment

Genetic
algorithms Multivariate analysis
Network analysis
Linearprogramming

Integer
programming
S. Takahashi, H.-Y. Wu, S. H. Saw, C.-C. Lin, H.-C. Yen. Optimized Topological Surgery for
Unfolding 3D Meshes, Computer Graphics Forum, 30(7), 2077-2086, 2011.

32

Papercraft Models☺ Can retrieve 3D physical shapes☺ For preparing the miniatures of 3D
scenes☺ Fun for both children and adults☹ Still difficult to construct

Key Ideas

Why Difficult?
lPractical issues
Large number of unfolded
patches, including small
fragmentsn Troubles in finding
correspondence between
a pair of cut edgesnPapercraft Construction Example

Employ the topological surgery to
encode the boundary edges of theunfolded patch
l Genetic-based approach to unfolding a
3D mesh into a single connected patchl33

Processing Pipeline

Stitching Unfolded Patches
Encode the order of edges to be
stitched together as a chromosomel Apply a genetic algorithm withimproved crossover and mutation
operationslGenetic-based
optimization
Input 3D mesh

Singleconnected
patch

Patches having a small
number of faces

Mesh Unfolding Process

#4

#2

#5

#3

#6

#7

#1

#0

Results (Bunny; 348 faces)
Conventional
MST-based
approach#{patches}=13

Our proposed
approach#{patches}=134

Results (Horse; 312 faces)

Results (Dragon; 344 faces)

Conventional
MST-based
approach

Conventional
MST-based
approach#{patches}=12#{patches}=13

Our proposed
approach

Our proposed
approach#{patches}=1#{patches}=1

Results (Hand; 336 faces)

Results (Knot; 480 faces)

Conventional
MST-based
approach

Conventional
MST-based
approach#{patches}=18#{patches}=14

Our proposed
approach

Our proposed
approach#{patches}=1#{patches}=135

Results (Cat; 702 faces)

Results (Fish; 950 faces)

Conventional
MST-based
approach

Conventional
MST-based
approach#{patches}=28#{patches}=31

Our proposed
approach

Our proposed
approach#{patches}=1#{patches}=1

Papercraft Construction

Papercraft Construction

36

Results

Bunny (348 faces)
34:01

あかべぇを作ろう

Horse (312 faces)
41:57

Dragon (344 faces)
55:46(min:sec)
Hand (336 faces)
33:55

Knot (480 faces)
46:13

Overview

おわりにCartographic design

Gradient
methods

Map compositionnEntertainment

情報可視化における幅広い技術課題を統一的に最適化問題として定式化
多変量データ視覚解析
n ネットワークデータ可視化
n 地図の図式表現と設計
n おまけ: 娯楽nGenetic
algorithms Multivariate analysis
Network analysis
Linearprogrammingn

個々の問題をどのようにモデル化するかが解決への糸口にInteger
programming

37

おわり

38