多次元デー タ構造上での知 的記号処理に よる高能率画像 ・図面処理方式 の研 究 坂内 正 夫 東京大学生産 技術研 究所 教 授 1 , は じめに 情 報処 理 の 高度化 に伴 う画像 処理 へ の エ ー ズの 高 ま りは広範 な ものが あ り, テ レビ画 デ ー タを対象 と した処理 ・認識 につい ては多 くの効 果が得 られて 像程 度 の解像度 の L T l 像 い る。 しか し, 地 図や各種 設計図面 な どの図面処理 , カ ラ ー動画像 な ど実用上 重要 な画 像 には, きわめて 大面積 ・大容量 な ものが 多 く, こ の様 な画像 デ ー タに対 す る汎 用で右 効 な処理 方法 は まだ開発 されて い ない 。画素 レベ ル情 報 を逐次処理 す る とい う通常 のL W j 像処 理 手法 で は 多大 な時間がかか りす ぎ, またその解決策 と しての専 用 プ ロセ ッサ 化 も コス ト面や拡 張性 の 面で問題 が 多い ためであ る。 本研究 で は 、新 しい アプ ロー チの大面積 ・大容量画像処理 方式 を創案 して上 記 の 問題 点 を解決す る こ とを 目的 とす る。即 ち, まず 画像 デ ー タをあ る程度抽 象 レベ ルの 高 い f d 号 プ リ ミテ ィブに変換 し, こ れ を多次 元 パ ター ンデ ー タ構 造 とよぶ 独 向の 記憶 方式 で管 理 して, そ の上 での高速 で知的 な記 号処理 を実行す る とい う形 の 画像処理 方式 を開発 し よ う とす る もので あ る。 この ため に, 本 研究 で は次 の 課題 につ い て研究 した。 1 . 大 面積 , 大 容量 の 図面 ・画像情 報処理 の 新 しい 枠組 を提示す る。 2 . 各 種 の パ ター ン情 報 ( 図形情報 を含 む) を, 汎 用高能率 に管理 す る多次 元 グラフ ィッ クデ ー タ構 造 を開発 し, 文 , よ り有効 な方式 の創案 を行 な う。 3.1の 枠組 みの 中 で , 実 際 の 大面積 図面画像 の認識 ・理 解 ・処理 方式 を開発す る。 4.1の 枠組 みの 中 で カラー画像 の知的 量子化方式 を開発す る。 以 下, こ れ らにつ い て研究成果 の概 要 を述 べ る。 2 . 新 しい大面積 大容量画像 ・図面処理方式の提示 大 面積 の 画像処理 にお い て, 抽 象化 レベ ルの低 い 大量 の 画像 デ ー タの まま扱 っていて は, 岸 i 速で知的 な処理 は望 め ない 。 そ こで , 本 研究 で は, 図 1 に 示す ように、 け‐ え られ た画 像 デ ー タを高速且 つ 比較的 簡 坊な方法 で図形 プリミテ イブ ( 画像 の辺稼部 のベ クトル, 空 間内 の点 な ど) に変換 する。以降 の処理 は 同質 の領域 , 色 L W l 素 /Ltて この 図形 プリミテ ィ ブに対 して実行す る。L F l 像 プ リ ミテ ィブ上 で能 処理 , 認 識処理 で必 要 となる演 算 をl K l 形 率 よ く実行す るこ とは通 常 の 方法 では困難 で あ るが , これ を 可能 と した のが 多次 元 パ タ ー ンデ ー タ構 造 の導入で あ る。 ここが 本研究 の独創的 な点 で あ り, 用 い るデ ー タ構 造そ の もの も 3 . で 述 べ る ように独 r l のもので ある。こ う して画1 象に対す る処理 は 多次 元デ ー -2 夕構造 上での各種 グ フ イック演 算 とな り, 高 速 化 され, また知識型処理 との適 合性 も す ぐれた もの となる ( 具体 的 には 4 . 5 . で 述 べ る) デー タ lFl像 己号プ l ミテリ 言 ィブす 由出 ↓ 多次元パ ター ンデー タ構造で管理 多次 元 デ ー タ構 造 1 1 での 高速 ・知的 グラフ ィック演 算 ￨ _ 所 望 の画像 ・図面処I 里 結果 ￨ は1 1 本 研究での画像処理 の 枠組 3 . 多 次元 パ タ ー ンデ ー タ構造 の 開発 本研究 にお ける山1 像処理 の 中核 となるデ ー タ構 造 を提 供す るだけで な く, ハ般 の グラ フ ィック ス処理 , マ ルチ メデ ィアデ ー タベ ー ス にお け る高次 な検索 ・演 算 に も有効 な 多 次 元 パ ター ンデ ー タ構 造 グラフィックスB D 木 を開発 した. 更 にその特性 を改良す る幾 つ かの構 造 , 卜I D 木, M L 本 な ど, を も合 わせ て創案 した. ( グラ フ ィ ノクB D 木 ) グラフ ィックB D 木 は, 研 究者 が既 に開発 して い た 多次 元点 デ ー タ構 造 B D 木 を, 線 ゃ画 面 ・立体等 の 図形 ・画像 を扱 える形 に拡 張 ・改良 した もので あ る. 即 ち, 多次 元の図形 を, そ の 重心点 と最小外接 長方形 の組 合 せ で とらえ, え ず重心点位 置 に もとず き, 多次 元空間 を階呼的 に分￨ ￨ して, ト リー ( 木) を形成す る, 次 い で各種 の グラフ ィックス演 算 をr 有 能卒 に実行で きる よ うに, 本 の 各 ノー ドに対 し, ド位 ノー ドに含 まれ る全デ ー タの 最小 外接 長 方形情 報 を1十 、ケす る た この グラフィックB D 木 のデ ー タ管理特性 をシ ミュ レー ション竿 に よ り評価 し, 従 来 方式 に比 して大幅 に性 能が改 洋され るこ とを示 した, また, 本 デ ー タ管 理構造 1 1 で各f T l 処 理 や校索 を行 な うための効率 よい 恭本牲埋 アル ゴ リ ズ2 、 を開発 し, そ の性 能 の よ さ も実証 して い る. 共 体的 には￨ メ 1 杉ゃ点 を指 定 して, そ れ に 最近接 す るデ ー タベ ー ス中 の 図形 を求 め るア ルゴ リズと、 , 空 間中の範阿 を指定 して, そ の 範囲内 に含 まれ る全ての 図形 を津i 速に探査 す るアル ゴ リズユ、 , L / 1 形の 認識 や理 解 で必 要 と なる隊l 形の1 司 辺 の 各種特 徴 単 とを求 め るア ルゴ リズユ、な どで あ る を 本 デ ー タ構 造 は, 本研究 の 1 的 の ための 中核構 造 と して使 用 されて い る. 1 像控 F 里 -3 (MD木 ) 先 に開発 したB D 木 は, デ ー タ管理効率 な どの点 か らは, ま だ改良 の 余地 があ ったc M D 本 はそのため に創案 された もので あ る3 M D 木 は, 1 次 元 デ ー タの管理構 造 で あ る 2 - 3 木 ( 3 次 のB 一t r e e ) を多次 元 に拡張 した もので あ り, 完 全平衡木が構 成で きる こ と, 最 悪 時 で も6 7 % の メモ リ効率が保証 で きる こ とを特 長 とす るc シ ミュレー シ ョンに よれば, M D 木 で は, 本 の作 成 時 間 は従来 の 手法 よ り 5 ∼ 1 0 % 増 加す る ものの , デ ー タの投 入順序 や分布 に よらず メモ リ効率 は8 0 % 以 上 となる こ とが示 され, また, 検 索効率 も改善 され るこ とが実 証 で きた。 ( M L 木〉 ー グラフイックデー タ構 造 を一 般 に利 用 しようとす る と, 図 形 デ タを, レイヤ ( 種類) 別 に 一 の 本構 造 の ノー ドに レイヤ管理機 能 を もた 管理す る必 要の あ る場 合 があ る. M L 木 は, 単 せ た もので , 通 常考 え られ る方法 に比 して, 数 倍 以上 の パ フォーマ ンス向上 が実現 された. 4 . 図 面処理 ・理解 システムの 開発 の延理 や 2 . で 述 べ た本 研究 による一 般的 な枠組 みの もとに, 地 凶や設 計図 な どのl X l 面 認識 ・理 解 シ ステム を実現 した。 開発 した シ ステムは 日的 や 重点 のお き方 の違 い で 3 種 , インテ リジェ ン トデ イジ タイ ザ , 自動認識処理 , 人 間 ・機械協 調型処理 , に 分け られるが , い ず れ もラ ンレグス待 号 の形 で与 え られ る図面画像 デ ー タを, 対 象物 ( ^ 般 に, 黒 い線状 , シ ンボ ル, 文 字等 の形 状 をなす ) の輪郭線 の ベ クトルデー タに変換 し, これ をグラフイックB D 木 で 管 F 里し, 必 要 一 な図面処理 認識 を全て グラフ イック演 算 の形 で実現 してい る点 は同 であ る. ( インテ リジ ェ ン トデ イジ タイザ) デ ー タで与 え られた図面内 の 対象物形状 を, 図 形 プリ ミテイブ ( 代表的 には 大面積 の l F l 像 点列 デ ー タ( つま り, ベ ク トルや 円等 ) に変換 す るA I 一M U D A M S と A I 一M U D A M S で 呼 ぶ システム を開発 した― は, 輪 郭 線 ベ クトルの形 で グラフイックB D 木 で管理 された原デ ー タか ら, 先ず , 信 頼性 の 高 い 部分 を優 先 して中心線 ( 芯線 ) を抽 出す る. 次 い で , 後 まわ しに された 分岐部 や他 の 対象物 との接触 部 につい ては, 既 処理結 果 と同囲状 況 , 輪 郭 ベ ク トルの状 況 ー を知的 に判断 して, 結 合, 分 離 を行 な ってい くを 本 シ ステムは, C 言 語 とい う汎 用ポ タ ブ ル な言語 に よる純粋 な ソフ トウ ェアに よ り実現 されて い るが , 実 現 された処理速 度 は A 6 0 0 0 画素) で 1 ∼ 3 分 ( いI I P S 計算機 ) と, 専 用 ハ ー ドウェアに よる 3 図 面 1 枚 程度 ( 4 0 0 0 × システ ム を しの ぐもので あ り, 更 に高度 な処理 品質 を も実現 して い る!
© Copyright 2024 ExpyDoc
