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 usedused.

– Mechanical CAD, Games,…
– 3D range scanners, 3D printers,…
i t– User generated.
• Trimble
T i bl 3D warehouse，...
h 3D model retrieval is essential.
Focuses of this research– High retrieval accuracy.
– Efficiency.
– Ease of use.

2013/11/25

accuratetandeasy to use2

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 hand-drawn sketch Accessible for most people.
 Intuitively specify 2D shape.
× Inaccurate.
• Even the best method yields MAP = 11%
using SHREC 2013 benchmark.

2013/11/25

3

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/253D model4

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
5

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

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

wobbly2D sketch
2013/11/25

2D sketch-likesketch like image6

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

“human”“human”
Can be retrieved.

2D sketch
2013/11/25

3D model7

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 models8

Our approach Combination of features and labels
labels.

 Matching by image features.

 Matching by semantic labels.
“human”

2013/11/25“human”

9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

10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 tt local
ll featuresf t
intoi 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 features11

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 200
multi-viewrendering
2013/11/25

local featureextraction…

 3
  21
 sketch-3D
k t h 3D modeld lfeature distance

…

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

distancecomputation

BF
integration
12

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

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

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

13

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

Euclidean distancefeature-adaptive
pdistancefeature spacepof 3D modelfeature spacepof 3D model

2013/11/25

14

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

generatea manifold graphdiffuse relevanceon a graphqueryquery

queryfeature space

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

15

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
16Outline

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

2013/11/25

17

Improving cross
cross-domain
domain feature comparison
 Ranking by diffusion distance on a Cross
Cross-Domain
DomainManifold (CDM).
–St t
Structure
off eachh featuref t
manifold
if ld isi kept.
k t
sketch-sketchfeature similarity

sketch-3D modelfeature similarity

3D model-3Dmodelfeature similarity

query

2D sketch domain
2013/11/25

3D model domain
18

Improving cross
cross-domain
domain feature comparison
 Ranking by diffusion distance on a Cross
Cross-Domain
DomainManifold (CDM).
–St t
Structure
off eachh featuref tmanifold
if ld isi kept.
k t
sketch-sketchfeature similarity3D model-3Dmodelfeature similarity

query

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

3D model domain
19Improving cross
cross-domain
domain feature comparison
 Ranking by diffusion distance on a Cross
Cross-Domain
DomainManifold (CDM).
–St t
Structure
off eachh featuref tmanifold
if ld isi kept.
k t
sketch-sketchfeature similarity

sketch-3D modelfeature similarity

3D model-3Dmodelfeature similarity

query

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

3D model domain
20Proposed methodCCross-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/25

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

3D model domain
21Proposed methodCCross-Domain
Di M
Manifoldif 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 twotmanifolds
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
22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 twotmanifolds
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
23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 Links2.
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
24Proposed method

C
Cross-Domain
Di M
Manifold
if ld R
Rankingki (CDMR)Example 1 : Ranking by label similarity
similarity.
query

2013/11/25

25

Proposed method

C
Cross-Domain
Di M
Manifold
if ld R
Rankingki (CDMR)Example 1 : Ranking by label similarity
similarity.

Incorrect results.

query

2013/11/25

26

Proposed method

CCross-Domain
Di M
Manifold
if ld R
Rankingki (CDMR)Example 1 : Ranking by label similarity.
similarity
query

2013/11/25“human”“human”27Proposed method

C
Cross-Domain
Di M
Manifold
if ld R
Rankingki (CDMR)Example 1 : Ranking by label similarity
similarity.
query“human”“human”

Correct results thanks tosemantic labels.
2013/11/25

28

Proposed method

C
Cross-Domain
Di M
Manifold
if ld R
Rankingki (CDMR)Example 2 : Ranking by feature similarity.
similarity
query

2013/11/25

29

Proposed method

C
Cross-Domain
Di M
Manifold
if ld R
Rankingki (CDMR)Example 2 : Ranking by feature similarity
similarity.

Correct results.

query

2013/11/25

30

Proposed method

C
Cross-Domain
Di M
Manifold
if ld R
Rankingki (CDMR)
 CDMR embodies an automatic query expansion
expansion.
original
query

expandedqueryqy

expanded
query

expandedquery

2013/11/25

31

Proposed method

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

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
32

3D model-to-3D model comparison
BF DSIFT [Furuya09]
BF-DSIFT
Dense and random extraction of local visual featuresfeatures.
 Per-model BF integration.
SIFT [Lowe04]
・invariant for rotation.
・robust against affine transformation.
・multi-scale.
view 1 5
  3  4

…
3D modelmulti-viewrendering
2013/11/25

SIFTviewi42
local feature
extraction

distancecomputation

 4
 1
1 

BF integration
33

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

34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

35

Experiments

BBenchmark
hkd
databasest b
 S-PSB [Eitz12]

・Test set (90 categories)
907 sketches

907 models

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

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

907 models“human”

per category.

“pig”
36Experiments

BBenchmark
hkddatabasest 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”
37

Experiments

B
Benchmarkhkd
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”
38

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 tfeaturesimilarity
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”
39

Experimental results

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

BF-fGALIF

1020

30

40

5060 [%]MAP

all classes
全カテゴリ

17.5

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

27.7

31.9

40

Experimental results

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

BF-fGALIF

1020

30

405060 [%]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%
41

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
42

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
43

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))

3017.5
13.6

BF-fGALIF

CDMR-BF-fGALIF (L)

20

27.5
38 5
38.5

avoidsover-fitting.
27.7
+7%
20.6

+25%

58 4
58.4

31.9
48.3
44

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

CDMR-BF-fGALIF (L)66.1

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

65.7

2013/11/25

45

Experimental results

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

BF-fGALIF

CDMR-BF-fGALIF (F)10203040506070 [%]MAPall全カテゴリ
classes

11.3

19.4

+ 55%
CDMR-BF-fGALIF (L)

66.1

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

65.7

46

Experimental results

CComparisoniwithith otherth algorithms
l ith
SH13

109
0.9
0.8
0.7
0.6
0.5
0.4
0.3
0.2
0.1
0

Proposed

002
0.2

04
0.4

06
0.6

08
0.8

Precisioon

Precisioon

S-PSB

11090.9
0.8
0.7
0.6
0.5
0.4
0.3
0.2
0.1
0

Proposed

002
0.204
0.4

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

CDMR-BF-fGALIF(L)BF-fGALIF

06
0.6

08
0.8

1Recall
CDMR-BF-GALIF(F+L)
CDMR-BF-fGALIF(F+L)
CDMR-BF-GALIF (F)CDMR-BF-fGALIF(F)VC+SC NUM 100
VC+SC_NUM_100
SBR-2D-3D_NUM_50
EFSD

CDMR-BF-GALIF(L)
CDMR-BF-fGALIF(L)BF-fGALIFBF-GALIF
VC+SC NUM 50
VC+SC_NUM_50
FDC

47Experimental results

R ti
Retrievall resultslt (S-PSB)(S PSB) “human”
human (labeled category)

BF-GALIF [Eitz12]
Query
CDMR-BF-GALIF (L) ≒ CMCP [Zhai12]

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

2013/11/25

48

Experimental results

R ti
Retrievall resultslt (S-PSB)(S PSB) “glassglass_with_stemwith stem” (unlabeled category)

BF-GALIF [Eitz12]
Query
CDMR-BF-GALIF (L) ≒ CMCP [Zhai12]

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

2013/11/25

49

Experimental results
CComputationi timeiper query
Computation time per query for S-PSB [s]methods

extract
BF-GALIF

computedistance

BF-GALIF

0.11

1.59

CDMR BF GALIF
CDMR-BF-GALIF

0 11
0.11

1 59
1.59

CDMR
(matrix size :3,628 x 3,628)

total
1.70

36 86
36.86

38 56
38.56

Computation time per query for SH13 [s]methods

extract
BF-GALIF

computeDistance

BF-GALIF

0.11

1.13

CDMR-BF-GALIF

0.11

1.17

CDMR
(matrix size :
8,458,x 8,458)
,)

total
1.24

659.93661.21

measured by using: Intel Xeon E3-1245 @ 3.30 GHz，32 GB of memory
2013/11/25

50

Conclusion and Future work Conclusion– More accurate sketch-based 3D model retrieval.
• Cross-Domain
CDi M
Manifold
if 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.
i

2013/11/25

51