著者
和田 幸一 萩原 兼一 都倉 信樹
出版者
電子通信学会
雑誌
電子通信学会論文誌 D (ISSN:0374468X)
巻号頁・発行日
vol.68, no.5, pp.p1011-1018, 1985-05

VLSIチップを平面格子と呼ばれるグラフでモデル化し,回路を素子間の配線の仕方を表すグラフGで表し,Gを平面格子に埋込んだとき,どれほどの面積を占めるかはVLSIチップの設計においては重要な問題であり,種々のグラフに対して,平面格子に埋込んだときの面積の上下界が議論されている.本論文では,次数が5以上のグラフが埋込めるように拡張したモデルのもとで,d次シャフルグラフを平面格子に埋込む問題を考える.d次シャフルグラフはシャフルエクスチェンジグラフやCCCなどと同様にデータの置換などを高速に行なうことができ理論的にも興味深いグラフである.ここでは,グラフの交差数と面積の関係を用いて,無限個のd,kに対して,dk頂点d次シャフルグラフを埋込むために(dk+1/k)2に比例した面積が必要となることを示す.この結果を用いると従来の面積の下界が改善される.また,あるグラフGの埋込みに対して,すでに埋込み面積がわかっているグラフを利用したGの埋込みの手法を与え,この結果を用いて,dが2のベキ乗の場合,dk頂点d次シャフルグラフは(dk+1/k)2に比例した面積で埋込めることを示す.
著者
高木 直史 安浦 寛人 矢島 脩三
出版者
電子通信学会
雑誌
電子通信学会論文誌 D (ISSN:0374468X)
巻号頁・発行日
vol.66, no.6, pp.p683-690, 1983-06
被引用文献数
27
著者
山本 正信 Yamamoto Masanobu
出版者
電子情報通信学会
雑誌
電子通信学会論文誌 D (ISSN:0374468X)
巻号頁・発行日
vol.69, no.11, pp.p1631-1638, 1986-11
被引用文献数
42

両眼ステレオ視は,3次元情報の手軽な獲得法ではあるが,左右画像間の対応付けの際に,(1)多重対応,(2)隠れ,(3)順序の逆転,(4)水平エッジ,などがある場合に於て,対応点探索が困難になる.本論文では,視点を移動させつつ得られた連続ステレオ画像から,シーンの3次元情報を推定する手法を提案する.まず,連続ステレオ画像から,見かけの運動軌跡が線分として画像化されるような2次元画像を合成する.その時,対応付け問題は,合成画像上の線分検出問題として簡略化される.検出された線分の相互関係を調べることにより,隠れの検出や,見かけの逆転が起きた場合の対応付けも容易になる.更に,視点を一方向だけではなく,それと直交する方向にも移動させることにより,エッジの向きに依存しない一意な対応付けが可能となる.大量の連続ステレオ画像が高速に入力可能な装置を構成し,実際に,複雑なシーンの3次元構造を復元する.
著者
大津 展之
出版者
電子通信学会
雑誌
電子通信学会論文誌 D (ISSN:0374468X)
巻号頁・発行日
vol.63, no.4, pp.p349-356, 1980-04
被引用文献数
369