IEEE 3DV 2014 talk slides:

Hashing Cross-Modal Manifold forScalable Sketch-based 3D Model Retrieval(Poster : 3-29)

Takahiko Furuya，Ryutarou Ohbuchi
University of Yamanashi

Introduction
 3D models are widely used.

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

– Ease of use.
– Efficiency.
– High retrieval accuracy.
2015/3/13

2

Introduction
 3D models are widely used.

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

– Ease of use.
– Efficiency.
– High retrieval accuracy.
2015/3/13

Sketch-based query
Binary features
Better feature similarities
3

Why sketch-based ?
Keywords
 Accessible for most people.
× 3D models lack keyword tags.

humansearch

3D model Sufficiently accurate for certain applications.
× 3D models often unavailable.

2D sketch Accessible for most people.
 Intuitively specify 2D shape.
× Inaccurate.
× Inefficient.

2015/3/13

4

Cross-modal matching problem
 Approach 1 : Image feature-based comparison.

– Renders 3D models into lines.
• e.g., Suggestive contour [DeCarlo03], …
– Adopted by most ([Yoon10], [Shao11], [Eitz12], … ).
featurecomparison…
…

2D sketch
2015/3/13

2D sketch-like images
5

Cross-modal matching problem
 Approach 1 : Image feature-based comparison.

Time-consuming for large-scale database.
20 views

100K models ×20 views= 2M comparisons per query

100K 3D models

…

…

…

2015/3/13…

…

sketchquery

20 views

6Cross-modal matching problem
 Approach 1 : Image feature-based comparison.

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

2D sketch
2015/3/13

2D sketch-like image
7

Cross-modal matching problem
 Approach 2 ： Semantic label-based comparison.

“human”“human”
label-basedcomparison

2D sketch
2015/3/13

3D model8

Cross-modal matching problem
 Approach 2 ： Semantic label-based comparison.

Learning sparse labeling is difficult.
“human”“chair”“human”?
“chair”

2D sketches
2015/3/13

3D models9

Our approach Efficiently & effectively combine features and labels.

 Matching by image feature-based similarity.

 Matching by semantic label-based similarity.
“human”

2015/3/13“human”

10Outline

Our previous work
– Cross-Domain Manifold Ranking [Furuya13]• Algorithm for cross-modal similarity metric learningProposed methodExperiments and resultsConclusion and future work

2015/3/13

11

Our previous work :Cross-Domain Manifold Ranking (CDMR)
 Ranking by diffusion distance on a Cross-Modal

Manifold (CMM) [Furuya13].
sketch-sketchfeature similarity

sketch-3D modelfeature similarity

3D model-3D modelfeature similarity

query

semantic labelsimilarity
2D sketch domain
2015/3/13

3D model domain
12Our previous work :Cross-Domain Manifold Ranking (CDMR)
 Ranking by diffusion distance on a Cross-Modal

Manifold (CMM) [Furuya13].
Relevance diffusion
by Manifold Ranking [Zhou03]
query

2D sketch domain
2015/3/13

3D model domain
13

Our previous work :Cross-Domain Manifold Ranking (CDMR)
Lack of scalability.
Costly relevance diffusion per query.

Insufficient accuracy.
“Outdated” visual features.

2015/3/13

BF-fGALIFBF-fGALIFBF-DSIFT[Eitz12][Eitz12][Furuya09]

14

Our previous work :Cross-Domain Manifold Ranking (CDMR)
Lack of scalability.
Costly relevance diffusion per query.

Insufficient accuracy.

Hashing CMM(comparison bybinary codes)

Better features“Outdated” visual features.

2015/3/13

BF-fGALIFBF-fGALIFBF-DSIFT[Eitz12][Eitz12][Furuya09]15

Outline

Our previous workProposed method– Cross-Modal Manifold Hashing (CMMH) algorithmExperiments and results

Conclusion and future work

2015/3/13

16

Proposed method

Cross-Modal Manifold Hashing (CMMH)
Accuracy: better features

Efficiency: hashing CMM

・ Improved visual features

・Manifold learning + hashing(efficient for large-scale CMM)

(Laplacian Eigenmaps (LE) [Belkin03]+ Iterative Quantization (ITQ) [Gong12])

2015/3/1300

1101

ITQ

LE

CMM

10

“flattend” CMM(real-valued space)“hashed” CMM(Hamming space)
17

Proposed method

Cross-Modal Manifold Hashing (CMMH)
 Hashes the CMM to generate compact binary codes.

1. Generates the CMM.
2. “Flattens” the CMM by Laplacian Eigenmaps (LE).
3. Hashes the flattened CMM by Iterative Quantization (ITQ).

2015/3/13

feature similarity(weight [0,1])

feature similarity(weight [0,1])

2D sketch domainlabel similarity(weight 1)

feature similarity(weight [0,1])

3D model domain
18Proposed method

Cross-Modal Manifold Hashing (CMMH)
 Hashes the CMM to generate compact binary codes.

1. Generates the CMM.
2. “Flattens” the CMM by Laplacian Eigenmaps (LE).
3. Hashes the flattened CMM by Iterative Quantization (ITQ).
CMM (e.g., 10K sketches+ 100K 3D models)flattend CMM(e.g., 512 dim. real-valued space)2015/3/1319

Proposed method

Cross-Modal Manifold Hashing (CMMH)
 Hashes the CMM to generate compact binary codes.

1. Generates the CMM.
2. “Flattens” the CMM by Laplacian Eigenmaps (LE).
3. Hashes the flattened CMM by Iterative Quantization (ITQ).
CMM (e.g., 10K sketches+ 100K 3D models)Randomized SVD [Halko11]
for LE on large CMM.

(7 minutes to flatten theCMM by using GPU).
flattend CMM(e.g., 512 dim. real-valued space)2015/3/1320

Proposed method

Cross-Modal Manifold Hashing (CMMH)
 Hashes the CMM to generate compact binary codes.

1. Generates the CMM.
2. “Flattens” the CMM by Laplacian Eigenmaps (LE).
3. Hashes the flattened CMM by Iterative Quantization (ITQ).
rotateandhash

1000

1101

(1011)(0010)(1110)…

flattened CMM(real-valued space)2015/3/13

hashed CMM(Hamming space)binary codes(e.g., 512 bit)21

Proposed method

Improved feature similarity
sketch-to-sketch

sketch-to-3D model

3D model-to-3D model

SV-MGALIFbSV-MGALIFSV-DSIFT +LL-MO1SIFT [Furuya14]

2D sketch domain
2015/3/13

3D model domain
22Proposed method

Improved feature similarity
must be efficient
for large-scale DB
sketch-to-sketch

sketch-to-3D model

3D model-to-3D model

SV-MGALIFbSV-MGALIFSV-DSIFT +LL-MO1SIFT [Furuya14]

2D sketch domain
2015/3/13

3D model domain
23Proposed method

Improved sketch-to-3D-model similarity
 bSV-MGALIF– Multi-scale GALIF + Super Vector (SV) for accuracy.
– ITQ hashing for efficiency.
~70K dim. 1024 bit

2D sketchview 1

3D modelview 20
multi-viewrendering
2015/3/13

MGALIFextraction

…

0
 
1
0
 

 0.71  0.36  0.59  0.11 

1
 
1
0
 

 0.71  0.36  0.59  0.11 

0
 
0
1
 

…

SV
aggregation…

distance…

…

 0.71  0.36  0.59  0.11 Hamming
distancecomputation

KPCA +
ITQ hashing24Outline

Our previous workProposed method– Cross-Modal Manifold Hashing (CMMH) algorithmExperiments and results

Conclusion and future work

2015/3/13

25

Experiments
 Evaluate accuracy and efficiency.

– Visual features for CMM.
New Feature Set (NFS)・ SV-MGALIF・ bSV-MGALIFOld Feature Set (OFS) [Furuya13]
・ BF-fGALIF

VS・ SV-DSIFT + LL-MO1SIFT

・ BF-fGALIF・ BF-DSIFT– Cross-modal similarity metric learning algorithms.
CMMH
00

10

VS
11

2015/3/13

CDMR [Furuya13]0126

Experiments

Small-scale benchmark database S-PSB [Eitz12]

・Test set (90 categories)
907 sketches

907 models

・Training set (92 categories)
907 sketches“human”
2015/3/13“pig”

907 models“human”“pig”
27

Experiments

Medium-scale benchmark database


SHREC2014 sketch-based 3D shape retrieval (SH14) [Li14]
・Test set (171 categories)
5,130 sketches

4,494 models
8,987 models

・Training set (171 categories)
8,550 sketches

4,493 models
・ randomly split
・ 10-fold validation“ant”
2015/3/13“duck”“ant”“duck”
28

Experiments

Large-scale benchmark database SH14X (100K 3D models)・Test set (171 categories)
5,130 sketches

91,013 “imposters”

8,987 models(same as SH14)(same as SH14)

randomly transformed
SH14 3D models

100K models
2015/3/1329

Experimental results

Effectiveness of new visual features (S-PSB)
 Proposed visual features (NFS) are more accurate.
0.0

BF-fGALIFOFSbSV-MGALIF
CDMR
CMMH (512bit)
2015/3/13

20.0

30.0

17.4

40.0

50.0
MAP
[%]

unsupervised
semi-supervised
27.9
31.1

CDMR
CMMH (512bit)

NFS

10.0

23.3
24.5
22.0
36.4

40.1
40.6
42.7
30

Experimental results

Efficiency of CMMH
 CMMH is efficient even for 100K-model database.

– About 1 second per query.
– Less than 1 GByte memory footprint.
 CDMR has a large memory footprint.

Comparison of efficiency for SH14X.
Algorithms

Computation timeper query [s]CDMR
CMMH (512 bit)

Memory footprint forretrieval [GBytes]
53.66

1.25

0.78

measured by using two Intel Xeon E5-2650 CPUs
256 GB RAM, Nvidia GeForce GTX 770 GPU
2015/3/13

31

Experimental results

Comparison with other retrieval algorithms (SH14)
 More accurate than state-of-the-arts.
0.0

BoF-JESC [Zou14]
SBR-VC [Li14]OPHOG [Tatsuma14]

5.0

10.0

2015/3/13

25.0

30.0[%]
MAP

unsupervised
semi-supervised

5.0
6.1
13.1

[Tatsuma14]

CMMH (512bit)

20.0

4.1

SCMR-OPHOGCDMR [Furuya13]

15.0

9.1

15.1
15.9

27.9
32

Conclusion and Future work Conclusion– Efficient & accurate sketch-based 3D model retrieval.
• Cross-Modal Manifold Hashing (CMMH)– About 1 second to query 100K-model database.
– More accurate than state-of-the-arts.
 Future work

– Further improvement in retrieval accuracy.
– Evaluation using realistic large-scale database.
• No “imposters”.

Poster : 3-29
2015/3/1333