Ranking on Cross
Cross-Domain
Domain Manifold for
Sketch-based 3D model Retrieval

Takahiko Furuya，Ryutarou Ohbuchi
University of Yamanashi

Introduction
 3D models are widely used
used.

– Mechanical CAD, Games,…
– 3D range scanners, 3D printers,…
i t– User generated.
• Trimble
T i bl 3D warehouse，...
h 3D model retrieval is essential.

– High retrieval accuracy.
– Efficiency.
– Ease of use.
2013/11/25

2Introduction
 3D models are widely used
used.

– Mechanical CAD, Games,…
– 3D range scanners, 3D printers,…
i t– User generated.
• Trimble
T i bl 3D warehouse，...
h 3D model retrieval is essential.

– High retrieval accuracy.
– Efficiency.
– Ease of use.
2013/11/25

accurate
tandeasy to use
3Why sketch
sketch-based
based ?
Keywords
 Accessible for most people.
× 3D models lack textual tags.

humansearch

3D model Sufficiently
S ffi i tl accuratet for
f certaint i applications.
li ti
× 3D models often unavailable.

2D sketch Accessible for most people.
 Intuitively specify 2D shape.
× Inaccurate.
• Even the best method yields MAP = 11%
using SHREC 2013 benchmark.

2013/11/25

4

Cross-domain
Crossdomain matching problem
 How do we compare a 2D sketch and a 3D model?

Can’t be compared directly
directly.

2D sketch
2013/11/25

3D model5

Cross-domain
Crossdomain matching problem
 Approach 1 : Image featurefeature-based
based comparison
comparison.

– Renders 3D models into lines.
• e.g., Suggestive
Sti contourt[DeCarlo03], …
– Adopted by most.

Can be compared.

2D sketch
2013/11/25

2D sketch-likesketch like image
6

Cross-domain
Crossdomain matching problem
 Approach 1 : Image featurefeature-based
based comparison
comparison.

Can’t handle abstraction,,semantic influence and noise.

2D sketch
2013/11/25

2D sketch-likesketch like image
7

Cross-domain
Crossdomain matching problem
 Approach 1 : Image featurefeature-based
based comparison
comparison.

Can’t handle abstraction,,semantic influence and noise.

2D sketch
2013/11/25

2D sketch-likesketch like image
8

Cross-domain
Crossdomain matching problem
 Approach 2 ： Semantic label-basedlabel based comparison
comparison.

“human”“human”
Can be retrieved.

2D sketch
2013/11/25

3D model9

Cross-domain
Crossdomain matching problem
 Approach 2 ： Semantic label-basedlabel based comparison
comparison.

Learning sparse labels is difficult.
“human”“human”“chair”“chair”

2D sketches
2013/11/25

3D models10

Our approach Combination of features and labels
labels.

 Matching by image features.

 Matching by semantic labels.
“human”

2013/11/25“human”

11Outline

Related work– BF-GALIF [Eitz12]• Algorithm
go tforo sketch-baseds etc based 3
3D modelode retrieval
et e a– Manifold Ranking [Zhou03]• Algorithm for distance metric learningProposed methodExperiments and resultsConclusion and future work

2013/11/25

12Related work : Sketch-to-3D model matching algorithm

BF GALIF [Eitz12]
BF-GALIF
 Efficiently compares sets of local featuresfeatures.

1. Densely extracts Gabor filter-based local features.
2 Integrates
2.
I t
t localll featuresf tintoi t a vector
t byb Bag-of-Features.
B
fF t
about 1,000,features
per image＊local feature

2D sketchk t h
2013/11/25

gaborb filter
filt bbankk(4 orientations)

responseimages

a sett off
GALIF features13

Related work : Sketch-to-3D model matching algorithm

BF GALIF [Eitz12]
BF-GALIF
 Efficiently compares sets of local featuresfeatures.

1. Densely extracts Gabor filter-based local features.
2 Integrates
2.
I t
t localll featuresf tintoi t a vector
t byb Bag-of-Features.
BfF t 4 11 

2D sketch…

view 1

3D modelview 200multi-view
rendering
2013/11/25

local feature
extraction…

 3
  21
 

sketch-3D
k t h 3D modeld lfeature distance…

 2  0  4

distancecomputation

BF
integration
14

Related work : Sketch-to-3D model matching algorithm

BF GALIF [Eitz12]
BF-GALIF
 Efficiently compares sets of local featuresfeatures.

Robust against articulation of 2D shape
shape.
Amongg the most accurate methods.
Yet, insufficient …
Our approach
Oh・ better feature comparison.
・ semantic labels
labels.
2013/11/25

15

Improving single
single-domain
domain feature comparison
 Learns featurefeature-adaptive
adaptive distance metric on manifold
manifold.

Euclidean distancefeature-adaptivepdistancefeature spacepof 3D modelfeature spacepof 3D model

2013/11/25

16

Related work : Distance metric learning
M if ld R
ManifoldRanking
ki [Zhou03][Zh 03]
 Diffusion distance on a feature manifold graph
graph.

generatea manifold graphquery

diffuse relevanceon a graphqueryfeature space

Our approachpp
・ extends Manifold Ranking to cross-domain.
2013/11/25

17

Improving cross
cross-domain
domain feature comparison BF-GALIFBF GALIF [Eitz12][Eit 12]– Structure of feature manifold is ignored.
sketch-3D modelfeature similarity
query

2D sketch domain
2013/11/25

3D model domain
18Outline

Related workP
Proposedd method
th d– Cross-Domain Manifold Ranking (CDMR) algorithmExperiments and resultsConclusion and future work

2013/11/25

19

Improving cross
cross-domain
domain feature comparison
 Ranking by diffusion distance on a Cross
Cross-Domain
DomainManifold (CDM).
sketch-sketchfeature similarity

sketch-3D modelfeature similarity

3D model-3Dmodelfeature similarity

query

2D sketch domain
2013/11/25

3D model domain
20Improving cross
cross-domain
domain feature comparison
 Ranking by diffusion distance on a Cross
Cross-Domain
DomainManifold (CDM).
sketch-sketchfeature similarity

3D model-3Dmodelfeature similarity

query

semantic label
similarity
2D sketch domain
2013/11/25

3D model domain
21

Improving cross
cross-domain
domain feature comparison
 Ranking by diffusion distance on a Cross
Cross-Domain
DomainManifold (CDM).
sketch-sketchfeature similarity

sketch-3D modelfeature similarity

3D model-3Dmodelfeature similarity

query

semantic label
similarity
2D sketch domain
2013/11/25

3D model domain
22Proposed method

C
Cross-Domain
Di M
Manifold
if ld RRankingki (CDMR)
 Ranking by diffusion distance on the CDM
CDM.

1. Generates a feature manifold on each domain.
2 Links
2.
Li k theth twot
manifolds
if ld bby ffeaturet
andd llabelb l similarity.
i il it
3. Diffuses relevance from the query.

2013/11/25ffeature similarity
i il i( weight [0, 1] )ffeaturetsimilarity
i il it( weight [0, 1] )2D sketch domain

3D model domain
23Proposed method

CCross-Domain
Di M
Manifold
if ld R
Rankingki (CDMR)
 Ranking by diffusion distance on the CDM
CDM.

1. Generates a feature manifold on each domain.
2 Links
2.
Li k theth twot
manifolds
if ld bby ffeaturet
andd llabelb l similarity.
i il it
3. Diffuses relevance from the query.
ffeaturetsimilarity
i il it( weight [0, 1] )2D sketch domain
2013/11/25

3D model domain
24Proposed methodC
Cross-Domain
Di M
Manifold
if ld RRankingki (CDMR)
 Ranking by diffusion distance on the CDM
CDM.

1. Generates a feature manifold on each domain.
2 Links
2.
Li k theth twot
manifolds
if ld bby ffeaturetandd llabelb l similarity.
i il it
3. Diffuses relevance from the query.
ffeaturetsimilarity
i il it( weight [0, 1] )2D sketch domain
2013/11/25

label similarity( weight 1 )3D model domain
25Proposed method

C
Cross-Domain
Di M
Manifold
if ld R
Rankingki (CDMR)
 Ranking by diffusion distance on the CDM
CDM.

1. Generates a feature manifold on each domain.
2 Links
2.
Li k theth twot
manifolds
if ld bby ffeaturet
andd llabelb l similarity.
i il it
3. Diffuses relevance from the query.
query

2D sketch domain
2013/11/25

3D model domain
26

Proposed method

C
Cross-Domain
Di M
Manifold
if ld R
Rankingki (CDMR) Feature comparison methods
methods.

sketch to sketch
sketch-to-sketch

sketch to 3D model
sketch-to-3D

3D modelmodel-to-3D
to 3D model

BF-fGALIFBF-fGALIFBF-DSIFT(based on [Eitz12])(based on [Eitz12])[Furuya09]

2D sketch domain
2013/11/25

3D model domain
27

Outline

Related work
– BF-GALIF [Eitz12]• Algorithm
go tforo sketch-baseds etc based 3
3D modelode retrieval
et e a– Manifold Ranking [Zhou03]• Algorithm for distance metric learningProposed method– Cross-Domain Manifold Ranking (CDMR) algorithmExperiments and resultsConclusion and future work

2013/11/25

28

Experiments
 Evaluate retrieval accuracy.
accuracy– BF-fGALIF (≒[Eitz12])• No distance metric learninglearning.
• Baseline– CDMR-BF-fGALIF (F)• Unsupervised learning.

– CDMR-BF-fGALIF (L)• Supervised
plearning.
g– CDMR-BF-fGALIF (F+L)()• Semi-supervised learning.
2013/11/25

29

Experiments

B
Benchmarkhkddatabasest b S-PSB [Eitz12]

・Test set (90 categories)
907 sketches

907 models

Difficult to learnlabels.
・21 shared categories
categories.
・As few as 4 labels

・Training set (92 categories)
907 sketches“human”
2013/11/25“pig”

907 models“human”

per category.

“pig”
30

Experiments

B
Benchmarkhkd
databasest b S-PSB [Eitz12]

・Test set (90 categories)
Difficult 907
to learnlabels.
907 sketchesmodelslabels
f tfeaturesimilarity
i il it・21 shared categories
categories.
・As few as 4 labels

・Training set (92 categories)
907 sketches
2D sketch domain“human”
2013/11/25“pig”

Learning labels
is difficult.

907 models
label similarity“human”

per category.
3D model domain

“pig”
31

Experiments

BBenchmark
hkd
databasest b
SHREC2013 sketch-based 3D shape retrieval (SH13) [Li13]

・Test set (90 categories)
2,700 sketches

1,258 models

Easyy to learnlabels.
“ant”“duck”“ant”“duck”

・Training set (90 categories)

・share all categories
categories.
・50 labels per category.

4,500 sketches“ant”
2013/11/25“duck”
32

Experiments

B
Benchmarkhkd
databasest b
SHREC2013 sketch-based 3D shape retrieval (SH13) [Li13]

・Test set (90 categories)
Easy tolearnlabels.
labels2,700 sketches
1,258
modelsf t
featuresimilarity
i il it“ant”“duck”

・Training set (90 categories)

g labels
Learning
is relatively easy.
・share all categories
categories.
・50 labels per category.

4,500 sketches
2D sketch domain“ant”
2013/11/25

label similarity“ant”“duck”

3D model domain“duck”
33

Experimental results

Eff tiEffectivenessoff CDMR forf S-PSBS PSB
 CDMR is effective.
effective0BF-fGALIF

102030405060 [%]MAP

all classes
全カテゴリ

17.5

27.5

CDMR-BF-fGALIF (F)CDMR-BF-fGALIF (L)CDMR-BF-fGALIF ((F+L))
2013/11/25

27.7

31.9

34

Experimental results

Eff tiEffectivenessoff CDMR forf S-PSBS PSB
 CDMR is effective.
effective
0

BF-fGALIF

102030405060 [%]MAP

all classes
全カテゴリ

17.5

27.5

CDMR-BF-fGALIF (F)CDMR-BF-fGALIF (L)CDMR-BF-fGALIF ((F+L))
2013/11/25

+ 10%
27.7

31.9+ 14%35

Experimental results

Eff tiEffectivenessoff CDMR forf S-PSBS PSB
 CDMR (F+L) effectively learns sparse labelinglabeling.
010

2013/11/25

405060 [%]
MAP

全カテゴリ
allclasses
unlabeledclasses
ラベルなしカテゴリ
labeledclasses
ラベルありカテゴリ

23.1

20.0

CDMR-BF-fGALIF (F)CDMR-BF-fGALIF ((F+L))

30

17.5
13.6

BF-fGALIF

CDMR-BF-fGALIF (L)

20

27.5
38 5
38.5
27.7

6.6

58 4
58.4
20.6

31.9
48.3
36

Experimental results

Eff tiEffectivenessoff CDMR forf S-PSBS PSB
 CDMR (F+L) effectively learns sparse labelinglabeling.
01020
17.5
13.6

BF-fGALIF

CDMR-BF-fGALIF ((F+L))
2013/11/25

6.6

- 7%

405060 [%]
MAP

全カテゴリ
allclasses
unlabeledclasses
ラベルなしカテゴリ
labeledclasses
ラベルありカテゴリ

23.1

20.0

CDMR-BF-fGALIF (F)CDMR-BF-fGALIF (L)

30

27.5
38 5
38.5

over-fits
to labels.
27.7
58 4
58.4
20.6

31.9

+ 35%

48.3
37

Experimental results

Eff tiEffectivenessoff CDMR forf S-PSBS PSB
 CDMR (F+L) effectively learns sparse labelinglabeling.
010

2013/11/25

6.6405060 [%]
MAP

全カテゴリ
allclasses
unlabeledclasses
ラベルなしカテゴリ
labeledclasses
ラベルありカテゴリ

23.1

20.0

CDMR-BF-fGALIF (F)CDMR-BF-fGALIF ((F+L))

30

17.5
13.6

BF-fGALIF

CDMR-BF-fGALIF (L)2027.538 5
38.5

avoids27.7over-fitting.
+7%
20.6

+25%

58 4
58.4

31.9
48.3
38

Experimental results

Eff tiEffectivenessoff CDMR ffor SH13
 Large improvement of MAP due to dense labelinglabeling.
0

BF-fGALIF

CDMR-BF-fGALIF (F)

1020

30

40

50

60

70 [%]
MAPall全カテゴリ
classes

11.3

19.4

CDMR-BF-fGALIF (L)66.1

CDMR-BF-fGALIF ((F+L))

65.7

2013/11/25

39

Experimental results

Eff tiEffectivenessoff CDMR ffor SH13
 Large improvement of MAP due to dense labelinglabeling.
0

BF-fGALIF

CDMR-BF-fGALIF (F)1020304050

6070 [%]
MAP

all
全カテゴリ
classes

11.3

19.4

+ 55%
CDMR-BF-fGALIF (L)

66.1

+ 54%
CDMR-BF-fGALIF ((F+L))
2013/11/25

65.7

40

Conclusion and Future work Conclusion– More accurate sketch-based 3D model retrieval.
• Cross-Domain
C
Di M
Manifoldif ld RRankingki (CDMR)– Combines feature similarity and semantic similarity.
– Outperforms previous methods
methods.
 Future work

– Faster computation (e.g., approximation of diffusion).
– MoreM
accuratet featuref tcomparison.
i2013/11/25

41