Uo1.50No.2(2013)pp.73-78
3次 元 形 状 モ デ リン グの ため の 点 群 の 再 構 成 に関 す る研 究
粟 野 直 之* AStudyonGeometryReconstructionofAcquiredPointCloudsfor3DShapeModeling NaoyukiAWANO ABSTRACT:Overthepastfewyears,pointcloudshaveattractedattentionasanewshapemodel,because 廿ieycanbeeasilycreatedus血g3D-digitizers,whichhaveseenrapiddevelopmentlately.Correspondingly, 廿serehasbeenanincreaseinresearchonpointclouds血 廿iefieldofCGandCAD.Generally,po血tclouds 血cludemanynoisesanddefects.Therefore,it'ssodifficulttoapplyexistingCGme廿codsforpolygonmesh topointcloudssuchasrendering,model血g,visualization,etc.Thispaper血troducesoneofmyresearch worksofgeometryreconstructionforpo血tcloudsmodeling. Keywords:3DCG,modeling,pointcloud,geometryreconstruction (ReceivedSeptember2Q2013) 1.は じ め に 3DCGや3DCADに お い て,3次 元CGオ ブ ジ ェ ク トを容 易 に 作 成 で き る こ とは 重 要 な 問題 で あ る。 従 来 は モ デ リ ン グ ソ フ トウ ェア を利 用 して3次 元 形 状 を作 成 す る こ と が 一 般 的 で あ った が,そ の 完 成 度 は 専 門 知 識 や 経 験 に 依 存 す る。 一 方,実 物 を計 測 す るだ けで3次 元 形 状 を作 成 で き る3次 元 計 測機 器 が 急 速 に 発 達 して きた 。 最 近 で は 安 価 な 計 測機 器 も市 販 され て い るた め,そ の 用 途 は 急 速 に 広 が って い る。 3次 元 計 測機 器 に よ る形 状 作 成 で は,通 常 の カ メ ラ と 同 様 に 計 測 対 象 を撮影(計 測)す る こ とで3次 元 デ ー タ を得 る こ とが で き る。 しか し,3次 元 デ ー タは 一 方 向 か らの 計 測 で は そ の す べ て を取 得 す る こ とは 困 難 で あ り, 図1の 太 線 部 の よ うな カ メ ラか ら可 視 の 部 分 を計 測 した 後 に 別 方 向 か ら再 計 測 す る こ とや,計 測 対 象 を回 転 させ る こ とに よ って 全 体 を計 測 で き る よ うに す る必 要 が あ る。 そ の た め,よ り簡 単 に 計 測 で き る よ うに す るた め,近 年 で は ハ ンデ ィ タイ プ の3次 元 計 測機 器 も開 発 され て い る。 3次 元計 測 機 器 か ら得 られ るデ ー タは 形 状 を点 群 で構 成 してい るデ ー タ で あ る。上述 した よ うに,多 方 向か ら計 測す る必 要 が あ るた め,得 られ る点 群 の 密度 は不 均 一 とな *:情 報 科 学 科 助 教(naoyuki -awano@st .seikei.ac.jp) る。 これ ま で,点 群 を 形 状 モ デ ル と して 扱 う研 究 で は,CG に お い て 一 般 に 利 用 され て い る ポ リ ゴ ン モ デ ル よ り も 優 位 性 の あ る 面 も あ る こ と が 示 さ れ て い る が,で き る だ け 均 一 な 点 群 で あ る こ と を前 提 と して い る こ とが 多 い1)。 提 案 手 法 で は,点 群 を3次 元 空 間 上 で で き る だ け均 一 に な る よ うに 再 構 成 す る 手 法 に っ い て 述 べ る。 な お,本 稿 は 著 者 に よ る論 文z)を 概 説 した も の で あ る 。 2.関 連 研 究 点 群 か ら ノ イ ズ を 除 去 して 均 一 に な る よ うに 再 構 成 す る 方 法 と して,移 動 最 小 二 乗 曲 面 を用 い た 平 滑 化 や,曲 面 上 で 点 群 を再 サ ン プ リ ン グ す る 手 法 な ど が あ る3}-5)。 しか し,曲 面 を利 用 す る こ と で 形 状 の エ ッ ジ を構 成 す る 部 分 が 欠 落 す る こ とや,曲 面 を構 築 す る た め の サ ン プ リ ン グ 問 題 に よ り細 部 が 欠 落 す る な ど の 問 題 が あ る。 3次 元 計 測 機 器 図13次 元計 測曲 面 を構 築 せ ず,点 群 を 均 一 に な る よ う に 再 構 成 す る 手 法 と し て,LocallyOptimalProjection(LOP)6)が あ る 。 こ の 手 法 で は,点 群 の 各 点 に お け る 近 隣 点 の み か ら再 構 成 後 の 点 座 標 を 算 出 で き る 。 ま た,出 力 す る 点 群 の 点 数 も 任 意 の 点 数 と す る こ と が で き る 。 さ ら に,LOPに よ る 出 力 点 群 を よ り 均 一 に な る よ う に 改 良 し た 手 法 と し て WeightedLocallyOptimalProjection(WLOP)7)も あ る。 WLOPで は,入 力 点 群 と射 影 点 群 の2種 類 の 点 群 を 用 意 し,射 影 点 群 を 入 力 点 群 」二に 射 影 す る 。 そ して,で き る だ け 均 一 に な る よ う に 整 列 さ せ る こ と に よ っ て,射 影 点 群 を 再 構 成 後 の 点 群 と し て 取 得 す る 手 法 で あ る 。 具 体 的 に は ・ 入 力 点 飾 一3Jje Cこ 対 し て 射 影 点 群 X={擁.、 ⊂ 卿 を 射 影 す る 場 合,式(1)∼(9)を 任 意 回 数 k(=1,2,...)回 反 復 計 算 す る こ と に よ っ て,徐 々 に 均 一 な 点 群Xを 得 る こ と がで き る。 kx ,.+'=Ek1+μ ξ wk/y
Ekl=ン Σ方
り
Ek2-(xk-x'`,)&瓢 器 β誰 ka .._ Jθ購 一乃)
k 第 一Pノ 罵 一小 一齋 一kx,., v.J-1+Σ θ転 一乃) ノ∈JA{ノ})
た ガ た 彦溜
㌻
W θの 一 θ一〆爾 ηの 一 一r (1) (2) (3) (4) (5) (6) (7) (g) (9) こ こで,1とJは 異 な る2種 類 の集 合 を表 して お り,式(1) 中の μ は,射 影 点 群Xを 入 力 点 群Pに 吸 着 させ る吸 着 項 E,と,射 影 点群 の 点 問 で 反発 させ る反 発 項EZの 調 整 係 数 で あ る。 この と き,ユ ー ザ 設 定 の パ ラ メー タの 指 標 と し て ・ ・ 一・・45功 一4画 が 最 適 で あ る と し て い る ・ ま た,dbbは 入 力 点 群 の バ ウ ン デ ィ ン グ ボ ッ ク ス の 対 角 距 離 で あ る。 ・} 視 点.・ 入 力 点 群 球面 図2球 面 反転 に よ る 陰 点消 去 しか し,WLOPに お い て も形 状 のエ ッジ を構 成 す る部 分 を維 持す る こ とが難 しい とい う問題 が あ る。 これ は, 式(2)で 表 され る吸 着 項E,に 注 目す る と,重 み 付 き 平 均 座 標 を 計算 して い る こ とが わ か る。 形 状 の 各 点 にお い て 近 隣 点 との 平均 座 標 を新 た な 点座 標 とす れ ばス ムー ジ ン グ の効 果 が 得 られ る こ と と同様 に,吸 着 項E,の 算 出 方 法 が エ ッ ジを構 成 す る 部分 を維 持 す る こ とが 難 しい 要 因 で あ る と考 え られ る。 3.エ ッ ジ を維 持 した 形 状 再 構 成 入 力 点群 の エ ッジ を構 成 す る部 分 を維 持 した ま ま 再構 成 を行 うた め,前 章 で 述 べ たWLOPを 改 良す る。こ こで, WLOPで はエ ッジ を構 成 す る部 分 を維 持 す る こ とが難 し い が,そ れ 以外 の部 分 で あ れ ば適 切 に 再構 成 を行 うこ と が で き る。 この こ とに着 目 し,エ ッ ジ を構 成 す る部 分 を な め らか に す る空 間へ 写 像 し,そ の 空 間 でWLOPを 適 用 した後 に,元 の空 間へ 逆 写 像 す る。逆 写 像 の 方 法 と して, 本 手法 で は 図2に 示 す よ うなKatzら の 点群 描 画 法8)を 参 考 にす る。 同 図 に示 す よ うに,視 点 を 中心 と した 球 を入 力 点群 を包 含す る よ うに 作成 し,球 面 で 点 群 を反 転 させ る。 反 転後 の 点群 は 球 面 に 近 い な め らか な 形 状 へ と変 形 され る こ とか ら,反 転後 の 点群 と視 点 を用 い て 凸包 を作 成 し,凸 包 を構 成 す る点 は 入 力 点群 の 空 間 で 可 視 表 面 上 の 点群 で あ る と して い る。 提 案 手 法 で は,球 面 反 転 に よ っ て な め らか な 形状 の 点群 へ と変 形 され る こ と を利 用 し, これ を 逆 写像 の 方法 と して利 用す る。 以 下,各 点 に お け る球 の 中心座 標Cの 算 出方 法 と球 の 」 半径Rに つ い て説 明 し,反 転 空 間上 で の 吸着 項E'1の 算 出 方 法 に つ い て も説 明 す る。 3.1球 の 中 心座 標 提 案 手 法 で は,各 射 影 点xに お い て 距 離h内 に あ る点 」 群 をそ れ ぞ れ 参 照 して 球 を作 成 し,入 力 点 群 と射 影 点x J を 球 面反 転 す る。 そ の た め射 影 点 ご とに 球 を作 成 で き るよ う に す る 。 具 体 的 に は,入 力 点 群 の 法 線 ベ ク トル N一 転、jE7を 利 肌 ・式(10)∼(12)に よ っ て 球 の 中 心 座 馬 を 算 出 す る よ う に す る 。 こ の と き,kは 射 影 点xか ら距 hJ 離h内 に あ る近 隣点 数 を表 してい る。 c.=x.十 彦 彦 %Σ た1穐 2kh 。,g。・。亀@.⑮ 「P;).ゆ nノ'=1 Σ 脅、(Pi-P、) 9ノ= 砿 (10) (11) (12) こ こで,一 般 に定 義 され る法 線 ベ ク トル は 形 状 表 面 に対 して 外 側 を 向 くよ うな ベ ク トル を指 す が,式(ll)∼(12)で 求 め る法線 ベ ク トル は 逆 方 向 とな る こ とが あ る。しか し, 提 案 手 法 に お け る球 の 中心 が 順 方 向 か 逆 方 向か に関 わ ら ず,球 面反 転 後 の 点 群 は な め らか に な るた め,逆 方 向 の ベ ク トル で もそ の ま ま 利 用 す る。 ま た,同 じよ うな 簡 易 法 線 ベ ク トル の 算 出 方 法 と して,主 成 分 分析(PCA)の 第3 主 軸 を 利 用 す る方 法 も広 く利 用 され て い るが,エ ッ ジ を 構 成 す る部 分 に お い て,図3に 示 す よ うに方 向が 不 安 定 に な る こ とが 多 い た め,同 式 を 用 い た 簡 易 法 線 ベ ク トル を 利 用 す る。 3.2球 の 半 径 Katzら の 手 法 で は,入 力 点群 は 閉 じた 曲 面 上 に サ ンプ リン グ され た もの で あ る こ とを 前 提 と して い る。 そ の た め,入 力 点 群 の 空 間 に 対 して 半径Rを 大 き く しす ぎた 場 合,例 え ば 図2に 示 した 点 群 が す べ て 可 視 と判 定 され る (b)PCA (a)入 力 点 群 ) 2 q = . ぴ 佳 .. ↑ D ロ ひ ㌦ ・ ・ 式 . 一 ) . F 。 . G ﹂ ( よ うに な る。 これ を解 決 す るた め に,可 視 と不 可 視 の境 界 が正 し く求 ま る よ うな 半径Rを 算 出 で き る よ うに して い る。 一方 で提 案 手 法 で は,反 転 す る点 群 を射 影 点xか ら距 」 離h内 に あ る局 所 的 な 点群 の み に 限定 して い る た め,開 い た 曲 面 上 の 点 群 と仮 定 で き る。 した が っ て,Katzら の 手 法 の よ うに 可 視 と不 可 視 の境 界 とな る よ うな 点群 に関 して は 考 慮 す る必 要 が ない た め,半 径 はRはhに 対 して 十 分 大 き い値 とす る。 3.3反 転 後 の 空 間 で のE'1 前節 ま で に説 明 した方 法 に よっ て 求 め た 球 の 中心 座標 と半径 を利 用 して,入 力 点群 を 球 面反 転 す る。 そ して, 同 時 に射 影 点xも 球 面 反 転 し,得 られ たx'を 用 い て 球 面 JJ 反 転空 間 上 でE'1を 算 出す る。こ こで,図4に 示 す よ うな 状 況 に お い て,球 面反 転 前 と反 転 後 に お け る近 隣 点 数 が 大 き く異 な る こ とが わ か る。 これ は,球 面 反 転 後 の 点群 は 入 力 点群 と比 較 して 大 き く広 が りを もつ た め で あ る。 しか し,式(2)で 示 した 吸 着 項 は 局 所 的 な 点 群 に 吸 着 させ る こ とを前 提 と して い る。 そ こで,局 所 領 域 を参 照 しつ つ,こ の 問 題 に 対 処 す る た め,反 転 後 の 点群 を ア ップ サ ンプ リン グす る。 具 体 的 に は,反 転 球 の 中心Cか ら射 影 点xま で のベ ク トル'を 生 JJ 成 し,xの 近 隣 点 を'移 動 させ,さ ら に 反 転 球 の 半 径 を 」 ll,ll/2拡大 す る 。 こ の 条 件 で 再 度 球 面 反 転 す る と,部 分 的 に ア ッ プ サ ン プ リ ン グす る こ と が で き る。 同様 に,射 影 点 の 近 隣 点 を さ ら に 移 動 させ,反 転 球 の 半 径 も さ ら に 拡 大 し た 条 件 で 球 面 反 転 す る 処 理 を,x'、 の 近 隣 点 数k'hが x;の 近 隣 点 数kh以 上 に な る ま で 繰 り返 す 。 し た が っ て,射 影 点xを 点 群 に 吸 着 させ る 場 合,式(13) 」 を 用 い て 球 面 反 転 後 のx' 、=f(x,.,c,.,R)を 求 め る 。 プ(副 一p-・+2ひ 一IIρ一ゆIll≡ill(13) ま た,式(14)《15)に よ っ て ア ッ プ サ ン プ リ ン グ 後 の 点 群 σ を 得 る 。 こ の と き,Kは 」とJと は 異 な る 集 合 を 表 す 。 」 砿 一 藪1ul=。Pl、(帆 ≦ん1毒 κ
蹴 の一{亜
・lt,c,.,〔1・
馴
(14) (1s> 図3簡 易法 線 ベ ク トル脇 ＼ κ メ 0 '
ゲ
κ
図4反 転 前 と反 転 後 の 空 間 x'、とU;を 用 い て 式(16>一(18)に よ っ てE'1を 算 出 し,最 後 に 式(19)に よ っ て 元 の 空 間 へ 球 面 逆 反 転 す る こ と に よ っ て 提 案 手 法 に お け るElを 得 る 。 呂 一ais/V'sus kESsEKais/Vs a,s=小
一篤)
x'.‐us ぬ 一1+Σ θ(1篤一殉ll) s'eK¥{s}E,=fE
c
R
(16) (17) (1g) (19) (a)頂 点 数21,009点(b)頂 点 数155,354点 図5実 験 対 象 の メ ッ シ ュ デ ー タ (・ …)1 1.4 1.2 1.0 誤 差0.8, 0.6 0.4 0.z O.0. 4.結 果 と 考 察 提 案 手 法 の 有 効 性 を検 証 す るた め に実 験 を行 った 。 以 後,形 状 のバ ウ ンデ ィ ン グ ボ ッ クス の対 角 距 離 で あ るdbb を1.0と して 正 規 化 して い る も の と して 実 験 を 行 う。 ま た,十 分 に 収 束 させ た 結 果 で 評 価 す る た め,kを100と す る。 4.1精 度 の 検 証 精 度 の検 証 方 法 を以 下 に 示 す。 ① 入 力 メ ッ シ ュデ ー タの 頂 点 を点 群 と して 扱 い,ラ ン ダ ム に 選 出 した 頂 点 群 を射影 点群 とす る。 ②WLOPと 提 案 手 法 を適 用 す る。 ③ 再 構成 後 の 点 群 の 各 点 にお い て,最 近 隣 メ ッ シ ュま で の 距 離 を算 出 す る。 ④ ③ で 算 出 した 距 離 の 平 均 を誤 差(精 度)と す る。 実 験 に は,図5に 示 す2種 類 の 形 状 を用 い た 。 実 験 で は,主 に 形 状 の エ ッ ジ を構 成 す る部 分 を維 持 で きて い る か に 着 目す る。 そ の た め,頂 点 の 並 び が 不 均 一 な メ ッ シ ュデ ー タ の 形 状 を用 い,そ の 形 状 が どの 程 度 維 持 で き る の か を検 証 した 。 そ の 結 果 を図6に 示 す 。 同図 よ り,提 案 手 法 は誤 差 が 少 な く,精 度 が 高 い こ とが わ か る。 図5(a) 図5(b) 図6誤 差 の 算 出結 果 晦反轍
点魅
入力点群 球面/＼.
○●● 麗 ● 、Oo。 鴇 i C=.00ブ
20, OO 図7反 転 後 の 形 状 の 違 い 4.2移 動 ベ ク トル'に つ い て δ 提 案 手 法 で は 球 面 反 転 後 の空 間 に お い て 吸 着 項E'1を 算 出す る際 に ア ップ サ ン プ リ ング を行 っ て い る。こ こ で, 図4に 示 した よ うに 球 面反 転 の 対 象 とな る点群 は局 所 的 に 参 照 した 点群 で あ り,微 小領 域 は お お よそ 平 面 を構成 して い るた め,同 図 に示 した よ うア ップ サ ンプ リン グが 可 能 とな る。 一 方,エ ッ ジ を構 成 す る部 分 で は,球 面反 転 後 の 形状 が 大 き く異 な る。 図7に 示 す よ うに,入 力 形 状 がCに 近 い 場 合 に は,同 図 中 の① で 示す 反 転 後 の 点群 」 が 得 られ る が,Cか ら遠 い場 合 に は 同 図 中 の② で 示 す反 」 転 後 の 点群 が得 られ,① と② で は反 転 後 の 点群 の 形 状 が 大 き く 異 な る。 そ の た め,Iltllを で き る だ け 微 小 に し,② の よ うにCか ら大 き く離 れ た位 置 で球 面反 転 を しな い よ 」 うに す る必 要 が あ る 。 そ こ で,ll,ll=R/mと し,前 節 で 示 し た 精 度 を 異 な るmで 検 証 した と こ ろ,m>10に お い て 大 き な 差 異 が な い こ と を 実 験 に よ り確 認 し た 。 そ こ で,提 案 手 法 で はm=20 と し,以 後 す べ て の 実 験 で も 同 様 と す る。 4.3計 測 点 群 で の 検 証 計 測 点群 を 用 い て 提 案 手 法 の 有 効 性 の 検 証 を行 うた め, 図8に 示 す 形 状 で 実 験 を行 った 。 こ こで,射 影 点 群 は 入 力 点群 か ら ラ ンダ ム に20,000点 選 出 した 。視 覚 的 に,同 図 の左 側 に 示 す 入 力 点 群 よ りも,右 側 に 示 す 提 案 手 法 の ほ うが 均 一 で あ る こ とが わ か る。 》 蘇越 (a)入 力 点 群=889,076点,射 影 点 群=20,000点
