1 of 35

Pyramid of Arclength Descriptor for Generating Collage of Shapes

賈智量

2 of 35

Outline

  • Introduction
  • PAD vector
  • PAD flow
  • Result
  • Discussion
  • Limitations
  • Contribution

3 of 35

Introduction

  • 製作 collage of shapes 的方法
    • Top-down
      • 計算量較低，但空間使用率可能不佳
    • Bottom-up
      • 計算量較大，但空間使用率較佳
  • PAD採用的是Bottom-up的方法

top-down

bottom-up

4 of 35

Introduction

  • A core of collage generation approach is a efficient partial shape matching method
  • Shape descriptor
    • Global shape descriptor
      • 太專注於global的資訊而忽略了 local
      • 若把global shape descriptor切成多段 則會導致計算量太大(N2M2)
    • Local shape descriptor
      • 現今的local shape descriptor 沒有考慮到scale這個因素(scale scope *NM)
  • PAD 最終選用local shape descriptor但考慮了scale(NM)

​

5 of 35

Introduction

6 of 35

PAD vector

    • 找到一個 Scale-invariant local shape descriptor

​

​

7 of 35

PAD vector

    • 找到一個 Scale-invariant local shape descriptor
  • 採用曲率積分

​

​

  • 但曲率積分可能會有巧合發生

​

8 of 35

PAD vector

  • 最終採用 曲率積分 + 弧長 這2個領域的結合

Scale-invariant

Not scale-invariant

9 of 35

PAD vector

  • 最終採用 曲率積分 + 弧長 這2個領域的結合
  • 固定曲率積分大小∆τ(0.2) 的弧長

長 🡪 不彎, 短 🡪 彎

10 of 35

PAD vector

  • 最終採用 曲率積分 + 弧長 這2個領域的結合
  • ∆τ(0.2) 個曲率積分的弧長
  • 以Sampled point為中心左右各取n level(n=5)

20∆τ

21∆τ

2n-1∆τ

2n-2∆τ

11 of 35

PAD vector

20∆τ

21∆τ

2n-1∆τ

2n-2∆τ

12 of 35

PAD vector

20∆τ

21∆τ

2n-1∆τ

2n-2∆τ

除上最長的arclength以達到scale-invariant(0~1)

但是 Arclength 不是 Scale-invariant

13 of 35

PAD vector

每個PAD sample point 都建1個PAD vector

每個PAD vector都是自己往左右各取2n(n = 5)個曲率積分

最後在除上最長的arclength以達到scale-invariant

+代表凸 –代表凹

14 of 35

PAD flow

幫每個shape取sample points並算PAD vector

比對PAD vector來找出best K%

計算shared arclength

丟進objective function來找出最好的match

Merge 2 shapes

All shapes

(seed shape)

All shapes

(with PAD)

Best K(1)% shapes

Best K% shapes

Best match

Result

Finish

The rest shapes

15 of 35

PAD flow

16 of 35

PAD flow(step1)

幫每個shape取sample points並算PAD vector

比對PAD vector來找出best K%

計算shared arclength

丟進objective function來找出最好的match

Merge 2 shapes

All shapes

(seed shape)

All shapes

(with PAD)

Best K(1)% shapes

Best K% shapes

Best match

Result

Finish

The rest shapes

17 of 35

PAD flow(step1)

每0.2個pixel取sample point

每個sample point都建1個PAD vector

18 of 35

PAD flow(step2)

幫每個shape取sample points並算PAD vector

比對PAD vector來找出best K%

計算shared arclength

丟進objective function來找出最好的match

Merge 2 shapes

All shapes

(seed shape)

All shapes

(with PAD)

Best K(1)% shapes

Best K% shapes

Best match

Result

Finish

The rest shapes

19 of 35

PAD flow(step2)

因為已經都建好PAD vector了

所以直接點對點的相減即可

D越小代表2條曲線是越接近的

最後取出前K%(1%)當 output

< threshold(0.4)

20 of 35

PAD flow(step3)

幫每個shape取sample points並算PAD vector

比對PAD vector來找出best K%

計算shared arclength

丟進objective function來找出最好的match

Merge 2 shapes

All shapes

(seed shape)

All shapes

(with PAD)

Best K(1)% shapes

Best K% shapes

Best match

Result

Finish

The rest shapes

21 of 35

PAD flow(step3)

  • 找出他的 first end-point
  • 找出旋轉與縮放係數並把2圖形的first end-point拼在一起
  • 建一個在S的boundary上為0的signed distance field
  • 距離 < threshold(4pixel)的部分視為相連

(允許gap and overlap)

​

S(seed shape)

S’(要拼的)

22 of 35

PAD flow(step4)

幫每個shape取sample points並算PAD vector

比對PAD vector來找出best K%

計算shared arclength

丟進objective function來找出最好的match

Merge 2 shapes

All shapes

(seed shape)

All shapes

(with PAD)

Best K(1)% shapes

Best K% shapes

Best match

Result

Finish

The rest shapes

23 of 35

PAD flow(step4)

Shared arclength

Weight of shared arclength

Gap

Weight of Gap

Overlap

Weight of Overlap

也可以加入其他constraint

Scale range constraint 🡪 讓2個matching不要差太多

orientation constraint 🡪 讓2個matching不要上下顛倒

24 of 35

PAD flow(step5)

幫每個shape取sample points並算PAD vector

比對PAD vector來找出best K%

計算shared arclength

丟進objective function來找出最好的match

Merge 2 shapes

All shapes

(seed shape)

All shapes

(with PAD)

Best K(1)% shapes

Best K% shapes

Best match

Result

Finish

The rest shapes

25 of 35

PAD flow(step5)

  • Simply cut and paste
  • Reconstruct 交界處的PAD

Recall step3

26 of 35

PAD flow

幫每個shape取sample points並算PAD vector

比對PAD vector來找出best K%

計算shared arclength

丟進objective function來找出最好的match

Merge 2 shapes

All shapes

(seed shape)

All shapes

(with PAD)

Best K(1)% shapes

Best K% shapes

Best match

Result

Finish

The rest shapes

27 of 35

Result

Shape collage

28 of 35

Result

Creative design

puzzle

mosaic

29 of 35

Result

Shape collage + deformation

30 of 35

Discussion

Compare with other methods

3個都是 top-down

大家都有各自的goal

但是目的是最相近的了

​

每個shapes只能出現1次

為了公平 都是採用PAD裡面有出現的shape

​

問題大多都是 沒有同時考慮gap and overlap

只針對凸多邊形等等

31 of 35

Discussion

Compare with other description methods

32 of 35

Discussion

Compare with other description methods

可做12HR PAD用750sec 完成

33 of 35

Limitations

  • 可能無法選出gobal最佳
  • 只能處理shape 無法處理color
  • Noise的影響無法解決
  • 無法處理open curve的直線

​

​

34 of 35

Contribution

  • 提出PAD 可非常有效的做 partial matching
  • 因為大幅減低search space 所以大大加快了collage
  • 不只 collage shape PAD在其他地方也有應用

​

35 of 35