コンピュータビジョン4.2節

研究室のゼミで発表したRichard Szeliski 著，玉木徹ら訳の『コンピュータビジョン − アルゴリズムと応用』4.2節のスライド

Transcript

1. 4.2 અ Τοδ ઒ౡوେ June 11, 2018 ిؾ௨৴େֶ ঙ໺ݚڀࣨ B4
2. ໨࣍ 1. Τοδͷݕग़ 2. Τοδͷ࿈݁ 2
3. Τοδͷݕग़
4. Τοδͷݕग़ ྠֲઢͳͲͷΤοδ͸͖ΘΊͯଟ͘ͷ৘ใΛؚΉ ਓखʹΑΔΤοδݕग़ (ਤ 4.31) ˠ͜ΕΛύιίϯ༷ʹ΍Β͍ͤͨ 3
5. Τοδͷݕग़ ୯७ͳΤοδͷݕग़ํ๏ɿΤοδΛٸܹͳً౓มԽͱͯ͠ѻ͏ ˠً౓஋ͷޯ഑Λߟ͑Δ I(x) ΛϐΫηϧ x = (x, y)⊤ ্ͷً౓஋ͱ͢Δͱɼً౓ޯ഑ J(x) ͸ J(x) = ∇I(x) = ( ∂I ∂x , ∂I ∂y ) (x) (4.19) 4
6. Τοδͷݕग़ ϕΫτϧ J(x) ͷ • ޲͖ɿً౓ؔ਺ͷ࠷ٸޯ഑ํ޲ • େ͖͞ɿً౓ؔ਺ͷมԽ౓߹͍ 5
7. Τοδͷݕग़ ߴप೾੒෼ʹ͸ϊΠζ͕ଟ͍ ˠϩʔύεϑΟϧλͰฏ׈Խ͔ͯ͠Βޯ഑Λܭࢉ ローパス フィルタ 6
8. Τοδͷݕग़ ϑΟϧλద༻ޙ΋ޯ഑ͷ޲͖͕ਖ਼͘͠อଘ͞Ε͍ͯͯ΄͍͠ ˠԁܗͷϑΟϧλ ෼཭ՄೳͳԁܗϑΟϧλ͸Ψ΢εϑΟϧλͷΈ (3.2 અɼਤ 3.14) ˠΤοδݕग़ͷͨΊͷϩʔύεϑΟϧλ͸Ψ΢γΞϯ͕ఆ൪ 7
9. Τοδͷݕग़ ඍ෼͸ઢܗԋࢉͰ͋ΔͷͰଞͷϑΟϧλԋࢉͱՄ׵ Ψ΢εϑΟϧλؔ਺Λ Gσ(x) = 1 2πσ2 exp ( − x2 + y2 2σ2 ) ͱ͢Δ ฏ׈Խޙͷը૾ͷޯ഑Λ Jσ(x) ͱॻ͘ͱɼ Jσ(x) = ∇[Gσ(x) ∗ I(x)] = [∇Gσ(x)] ∗ I(x) (4.20) ͱͳΓɼΨ΢εϑΟϧλؔ਺ͷඍ෼ͱͷͨͨΈࠐΈͰදݱͰ͖Δ 8
10. Τοδͷݕग़ Ψ΢εϑΟϧλؔ਺ͷඍ෼ͷධՁ ∇Gσ(x) = ( ∂ ∂x , ∂ ∂y )⊤ Gσ(x) = ( ∂ ∂x , ∂ ∂y )⊤ 1 2πσ2 exp ( − x2 + y2 2σ2 ) = 1 σ2 (−x, − y)⊤ 1 2πσ2 exp ( − x2 + y2 2σ2 ) ((4.21) ࣜͱ߹Θͳ͍͕ͨͿΜ͜ΕͰ͍͋ͬͯΔ) 9
11. Τοδͷݕग़ thinning ΤοδΛ 1 ըૉͷଠ͞Ͱදݱ͍ͨ͠৔߹͕ଟ͍ (ࡉઢԽ; thinning) (ը૾͸ [1] ΑΓ) 10
12. Τοδͷݕग़ thinning ʮΤοδʹରͯ͠ਨ௚ͳํ޲ͷޯ഑ڧ౓͕࠷େʹͳΔ࠲ඪʯΛٻ ΊΕ͹Α͍ ˠً౓ͷ 2 ֊ඍ෼ (ϥϓϥγΞϯ) Λߟ͑Ε͹Αͦ͞͏ͩ ͜ͷ 2 ֊ඍ෼ͷ஋ Sσ(x) ͸ɼ∇2 = ∇ · ∇(= div grad) ΑΓ Sσ(x) = ∇ · Jσ(x) = [∇2Gσ(x)] ∗ I(x) (4.22) 11
13. Τοδͷݕग़ thinning Ψ΢εϑΟϧλͷϥϓϥγΞϯͷධՁ ∇2Gσ(x) = ∇ · [ 1 σ2 (−x, − y)⊤ 1 2πσ2 exp ( − x2 + y2 2σ2 )] = ∂ ∂x [ − x 2πσ4 exp ( − x2 + y2 2σ2 )] + ∂ ∂y [ − y 2πσ4 exp ( − x2 + y2 2σ2 )] = 1 2πσ2 ( x2 + y2 − 2σ2 σ4 ) exp ( − x2 + y2 2σ2 ) 12
14. Τοδͷݕग़ thinning ∇2Gσ(x) ͷ܎਺Λແࢹˠ LoG(Laplacian of Gaussian) ϑΟϧλ LoG(x) = ( x2 + y2 − 2σ2 σ4 ) exp ( − x2 + y2 2σ2 ) 13
15. Τοδͷݕग़ thinning Sσ(x) ͷූ߸͕มԽ ˠ૬ରతͳ໌Δ͕͞มԽ Sσ(x) ͷθϩަࠩ఺Λ୳ͤ͹ Α͍ 14
16. Τοδͷݕग़ thinning sign(Sσ(xi)) ̸= sign(Sσ(xj)) ͱͳΔྡ઀ϐΫηϧ xi, xj ͓Αͼθ ϩަࠩ఺ xz Λ୳͢ Sσ(xi) ͱ Sσ(xj) ͱΛ݁Ϳઢ෼͕θϩͱަࠩ͢Δ఺ xz ΛٻΊΔ 15
17. Τοδͷݕग़ thinning Sσ(xj) − Sσ(xi) xj − xi (xz − xi) + Sσ(xi) = 0 ∴ xz = xiSσ(xj) + xjSσ(xi) Sσ(xj) + Sσ(xi) ͕ಘΒΕΔɽ3 ࣍ݩҎ্ͷ৔߹΋ಉ༷ʹ xz = xiSσ(xj) + xjSσ(xi) Sσ(xj) + Sσ(xi) (4.25) Ͱ͋Δ 16
18. Τοδͷݕग़ εέʔϧબ୒ͱϘέྔਪఆ LoG ʹద౰ͳ σ ΛઃఆˠӶ͍/ಷ͍ΤοδΛநग़ (ਤ 4.32, (b), (c)) 17
19. Τοδͷݕग़ εέʔϧબ୒ͱϘέྔਪఆ ޿͍ײ౓ͰΤοδΛͱΓ͍ͨͳΒʁ ˠεέʔϧεϖʔεͷΞϓϩʔν 1. ͍͔ͭ͘ͷ σ Λ༻ҙ 2. ͦΕͧΕͷ σ ʹ͍ͭͯޯ഑ ͱ 2 ֊ඍ෼Λܭࢉ 3. ҆ఆʹΤοδΛݕग़Ͱ͖Δ ࠷খͷ σ Λબ୒ɼͦΕΑΓ େ͖͍ σ Ͱݕग़͞ΕͨΤο δΛ௥Ճ 18
20. Τοδͷݕग़ εέʔϧબ୒ͱϘέྔਪఆ ޿͍ σ ͰΤοδΛநग़ (ਤ 4.32, (f)) 19
21. Τοδͷݕग़ Χϥʔը૾ͰͷΤοδݕग़ Χϥʔը૾Ͱ΋Τοδݕग़Λ͍ͨ͠ ୯७ʹً౓ޯ഑ΛݟΔͱɼ౳ً౓৭ؒͷΤοδΛݕग़Ͱ͖ͳ͍ ղܾҊ 1ɿRGB ֤੒෼͝ͱʹً౓ޯ഑Λܭࢉ͢Δ • ֤৭Ͱූ߸ͷҟͳΔޯ഑͕ग़Δͱɼ୯७ͳ଍͠߹ΘͤͰ͸૬ ࡴ͕ى͜Δ ղܾҊ 2ɿ֤ըૉͷपลͰہॴతͳ౷ܭྔΛ͍Ζ͍Ζௐ΂Δ • ୯७ͳً౓ɾ໌౓ɾ৭͚ͩͰͳ͘ɼςΫενϟͷมԽͳͲ΋ ଊ͑ΒΕΔ 20
22. Τοδͷݕग़ ਤ 4.33ɽBGɿ໌౓ɼCGɿ৭ɼTGɿςΫενϟ 21
23. Τοδͷ࿈݁
24. Τοδͷ࿈݁ நग़͞ΕͨΤοδΛ࿈݁ͯ͠Ұܨ͗ʹ͍ͨ͠ thinning ͞ΕͨΤοδͷըૉ৘ใΛ͍࣋ͬͯΔͱָ ˠ͍ۙ୺఺Λ୳ࡧͯ͠ܨ͛͹Α͍ ΤοδΛ࿈݁͢ΔͱΑΓѹॖͨ͠දݱ͕ՄೳʹͳΔ 22
25. Τοδͷ࿈݁ νΣΠϯίʔυ 8 ͭͷํ֯ (N, NE, E, SE, S, SW, W, NW) Λ 3bit ͰίʔυԽ (ਤ 4.34) 23
26. Τοδͷ࿈݁ νΣΠϯίʔυ νΣΠϯίʔυͰͷΤϯίʔυޙɼϥϯϨϯάεූ߸Ͱ͞Βʹѹ ॖͰ͖Δ ϥϯϨϯάεූ߸ ܁Γฦ͠ͷจࣈΛͦͷճ਺Ͱදݱ AAAABBBCCCCC ˠ A4B3C5 24
27. Τοδͷ࿈݁ arc-length parameterization ʮހʯͷ௕͞ͱΤοδ࠲ඪΛ༻͍ͯදݱ (ਤ 4.35) 1. x0 = (1, 0.5)⊤ ͔Βελʔτ 2. s = 0 ʹ x0 ͷ࠲ඪΛͦΕͧΕϓϩοτ 3. x1 = (2, 0.5)⊤ 4. s = ∥x1 − x0∥ = 1 ʹ x1 ͷ࠲ඪΛͦΕͧΕϓϩοτ 5. ࢝఺ʹ໭Δ·Ͱ܁Γฦ͢ 25
28. Τοδͷ࿈݁ arc-length parameterization Q. Կ͕͏Ε͍͠ͷ͔ʁ A. Ϛονϯά΍ฏ׈ԽͳͲͷॲཧ͕༰қʹͳΔ ܗঢ়ͷࣅͨΤοδΛߟ͑Δ (ਤ 4.36) 26
29. Τοδͷ࿈݁ arc-length parameterization 1. Τοδͷ࠲ඪͷฏۉ஋ ¯ x0 = ∫ S x(s)ds Λݮࢉ 2. s Λ 0 ∼ S ͔Β 0 ∼ 1 ʹਖ਼نԽ 3. ͦΕͧΕʹ͍ͭͯϑʔϦΤม׵ 27
30. Τοδͷ࿈݁ arc-length parameterization ΋ͱͷΤοδಉ͕࢜εέʔϦϯάͱճసͷҧ͍͔͠ͳ͍ ˠϑʔϦΤม׵ͷ݁Ռ͸ڧ౓ͱҐ૬ͷζϨ͔͠ҟͳΒͳ͍͸ͣ (։࢝఺͕ҟͳΔͱઢܗͷҐ૬ͷζϨ΋ग़Δ) 28
31. Τοδͷ࿈݁ arc-length parameterization ཭ࢄԽ࣌ʹੜ͡ΔϊΠζͷฏ׈Խʹ΋༗ޮ ͔͠͠ී௨ʹฏ׈ԽϑΟϧλΛ͔͚Δͱॖখͯ͠ฏ׈Խ͞ΕΔ ਤ 4.37(a), ԁͷ൒ܘ͕ॖখ͍ͯ͠Δ 29
32. Τοδͷ࿈݁ arc-length parameterization 2 ֊ඍ෼ʹجͮ͘Φϑηοτ߲Λ଍͔͢ɼΑΓେ͖ͳ (ͦ͢ͷ޿ ͍ʁ) ฏ׈ԽϑΟϧλΛ༻͍Δ ਤ 4.37(b) 30
33. ·ͱΊ • άϨʔεέʔϧը૾Ͱ͸ً౓ޯ഑ͰΤοδΛݕग़ ϊΠζআڈ΋ಉ࣌ʹߦ͏ͨΊʹΨ΢γΞϯϑΟϧλͷ 1 ֊ඍ ෼ͱͨͨΈࠐΉ • thinning ͍ͨ͠৔߹͸ LoG ϑΟϧλΛ͔͚ͯθϩަࠩ఺Λٻ ΊΔ • Χϥʔը૾ͷΤοδݕग़͸໌౓ɾ৭ɾςΫενϟͳͲͷ౷ܭ ྔ͕༗ޮ • thinning ͞ΕͨΤοδͷ࿈݁͸νΣΠϯίʔυ΍ arc-length parameterization ͕༗ޮ • arc-length parameterization ޙ͸Ϛονϯά΍ϊΠζআڈΛ͠ ΍͍͢ 31
34. References I [1] R. Rao. Image sampling, pyramids, and edge detection. https://courses.cs.washington.edu/courses/cse455/ 09wi/Lects/lect3.pdf, 2009.