日本船舶海洋工学会講演会論文集 （この行は学会にて記入します）

Voxel 図形の塗り潰しと細線化による配管自動設計に関する研究
正 会 員
学生会員

木村 元*
佐多 広海**

学生会員

慶田

航**

Automatic Piping Arrangement Design Using Filling and Thinning Operations in Voxel Space
byHajime Kimura, Member
Hiromi Sata, Student Member

Kou Keida, Student Member

Key Words: Pipe arrangement, Automatic design, Voxel fill, Voxel thinning, pipe routing, X3D

1. 緒言

造船業界の配管設計作業は未だに熟練技術者の経験に頼る部分が大きく，設計作業に膨大な時間を要している．
近年では各造船所とも熟練者の確保が困難になってきており，若手技術者への技術伝承問題も発生している．特に配管経路の設計作業は艤装設計における作業時間の大きな割合を占めており，船舶の設計作業全体の効率化を検討するうえで重要な課題である．以上のことから，配管設計作業を省力化するシステムの必要性は日増しに高まっていると考えられるが，配管設計問題は未だ学術的な検討が十分に行われた分野ではなく，未だに配管設計を自動的に行う実用的なシステムは存在していない．本
研究では配管自動設計システムの構築に向けて，船殻の曲がりに対応することやより複雑な形状の障害物の回避など，実用に即した問題設定での配管経路探索を行う手法について検討する．先行研究 1)においては、配管方向が直交座標系のみという点と，設計空間が対象とするパイプに対して大きい場合探索に非常に時間がかるという点で非実用的であった．そこで本研究では Voxel 図形処理を利用することによる計算時間の短縮と，船殻の曲がり等に対応した配管設計を行う手法を検討する．

2. 配管自動設計システムの概要
本研究は木村の提案する自動配管設計システム 2)に関するものである．システムは大きく分けて前半の経由点候補生成処理，後半の配管経路探索処理の 2 つの処理で構成される(Fig. 1)．前者の目的はパイプの有望な経路となりうる経由点候補を設計対象空間に配置することである．後者の目的は前者で配置した経由点候補で構成されるネットワークにおいて、よりコストの小さい配管経路の探索を行うことである．
本研究では処理前半部分にて経由点候補を配置するために，対象空間を 1 辺が任意長の立方体でメッシュ分割し，Voxel 図形処理を用いることを特徴とする．

* 九州大学 大学院工学研究院海洋システム工学部門** 九州大学 大学院工学府海洋システム工学専攻
原稿受付 (学会にて記入します)
秋季講演会において講演 (学会にて記入します)©日本船舶海洋工学会

Fig. 1 The process of the proposed piping arrangement
system.

3. Voxel 図形処理による経由点候補の生成
3. 1 概要
本研究で使用する配管経路探索アルゴリズムは，経由点候補を節点として構成されるネットワークからダイクストラ法を用いてコストが最小となる経路を探索する．
ただ，経由点候補を多く配置すればより多くの解を得ることができる反面，経由点候補が増えるほど経路探索にかかる時間が長くなっていく．そのため経由点候補は必要最低限の配置に留め，無駄な経由点候補の配置をできる限り減らす必要がある．そこで本研究では，設計対象空間におけるパイプの配管経路のトポロジを考えることで経由点候補の配置場所を判定することを提案する．ここでのトポロジとは，設計対象空間における大まかな配管経路候補を指す．トポロジを参考に経由点候補を配置することで，袋小路のようなパイプの通り得ない無駄な場所に配置することを防ぐことができる(Fig. 2)．

Fig. 2Topology of the routing space.

2 次元平面においてこのような処理を機械的に行うための方法として，細線化に代表される画像処理で使われている技術を用いるものがある．Fig. 3 はその流れを簡単に示したものである．与えられた空間の障害物以外の部分を塗りつぶし，それを 1 画素幅にする（細線化）ことでその空間のトポロジを得ることができる．本研究では，トポロジを得るための手段として Voxel 図形処理を用いる．Voxel とは，volume（体積）と pixel（画素）を組み合わせた混成語である．先行研究で行っていた設計対象空間を等幅のメッシュに区切るという処理はまさしくVoxel 図形化処理であり，先行研究の自動配管システムにおけるダイクストラ法などの経路探索法とも容易に併用することができる．ている．塗りつぶされた Voxel を 1，それ以外の Voxelを 0 として，消去可能性を判定するパターンを用意し，上下左右前後方向からラスタースキャンを行う．パターンとマッチした場合，対象画素を消去する(0 に置き換える)という処理を繰り返し行うことで細線化を行う．Fig.
4 が上から塗りつぶし前，塗りつぶし後，細線化後の処理結果の例である．

Fig. 3 Outline of the process of getting the topology.
3. 2 Voxel 図形の塗りつぶし処理
障害物を配置した空間にパイプが通るかどうかの判定として塗りつぶし処理を行う．まずパイプの始点と終点の位置情報を入力する．パイプの始点を起点として，パイプ径と同じ径の球が障害物と干渉せずに置ける位置に対して塗りつぶしを行う．塗りつぶしが行われなかった
場所はパイプが通れないことを示す．また、塗りつぶし処理後に終点まで塗りつぶされているかを確認することでパイプが始点から終点まで到達できるかの判定ができる．
3. 3 Voxel 図形の細線化処理
先行研究では，設計空間をメッシュ状に分割した格子点全てを経由点候補として経路探索をしているために，探索に非常に時間がかかり非実用的であった．本研究では塗りつぶし処理後の Voxel 図形に対して細線化処理を行い，経由候補点を限定することによって探索時間を大幅に短縮することを目指す．細線化とは幅を持つ線分を 1画素の線幅に変換する処理のことを言う．Fig. 4 に 2 次元の図形での細線化処理の例を挙げる．細線化処理を行うと下図のような「ひげ」と呼ばれる枝状のノイズが生じる．

Fig. 4

Thinning examples

細線化処理では標準的なパターンマッチング 3)を用い

Fig. 5 A Filling result and a thinning result.

また，本研究では消去可能性を判定するパターンを追加することで袋小路等経路として成立しない点に関しては，細線化結果が残らないように改良を加えた(Fig. 6)．

Fig. 7

Fig. 6

Erasing a dead end.

4. 特徴点に関する処理
細線化によって得られた結果は，複数の線分によって構成される図形と捉えることができる．そこで，“分岐”や“折れ曲がり”などの特徴点(keynode3))を抽出し，それらを結んで Key Node Graph4)を作成する(Fig. 7)．Key
Node Graph から線分の位置ベクトルを得られるため，後の経由点候補の配置に細線化結果をより効果的に用いることができるようになる．

Extraction of keynodes and a KeyNode Graph.

5. 経由点候補の生成
経由点候補とは，ダイクストラ法による経路探索の際にグラフのノードとなるものである．位置座標の他に，その点におけるパイプ配管方向を指定する相対座標軸を状態量として持っているのが特徴である．先行研究では全ての経由点候補において相対座標軸を絶対座標軸と平行に配置していた，しかし本研究では先述の特徴点に関する処理結果に応じて，狭隘空間において相対座標軸を適切な方向に回転することで，より良い経路探索結果を得る(Fig. 8)．狭隘空間の判定方法としては，塗りつぶし処理にも用いた球と障害物の干渉判定を用いる．用いる
球の直径はパイプ径などを考慮して初期値を決める．その後直径を徐々に小さくし，keynode 間においてどのVoxel が障害物との距離が最も小さいかを判定する．

Fig. 8 Result of the extraction of key nodes
and a key node graph.

6. シミュレーション結果
本研究では設計対象空間をいくつか用意し，シミュレーション実験を行った．パイプコストに関してはパイプ直径を φ，パイプの長さ L として，φ×L を用いている．
初めに 2 本のパイプの経路探索を行った．経由点候補の配置を① 配管可能な格子全てに配置② 細線化結果を基に，回転をさせずに配置③ 細線化結果を基に，狭隘区間では回転させたものも配置の 3 パターンに分けて探索を行った．尚，③においては，②における経由点候補も残しつつそれに加える形で経由点候補を配置した．
Fig. 9 が処理結果である．実験①，②と実験③の結果を比較すると，前者の青のパイプが障害物の間を通る際にエルボを用いて配管されているのに対し，後者ではエルボを使用せずに障害物の間を配管することができているのが分かる．Table. 1 は経由点候補の数，探索時間，パイプコストを実験ごとにまとめたものである．パイプコストを見ると，実験①が他と比べて大きくなっている．
実験①では経由点候補をほぼ全ての格子に配置しているためこの実験での最適解，つまり最短経路を得られる可能性は高いが，同時に解候補が多くなるという問題もあるため局所解に陥った可能性がある．実験②と③ではパイプコストに若干減少が見られ，より短い経路が探索できていることが分かる．探索時間を比較すると，本研究の手法を用いた実験②，③では 30 秒以内に探索が終了しているのに対し，やはり経由点候補の多い実験①では他と比べて非常に長い時間がかかっている．また，実験②と③に関しては経由候補点が③の方が多いにも関わらず計算時間は 12 秒短い結果となっている．これについては回転させた経由候補点を配置したことによる無駄なエルボの解消が，パイプ同士の干渉をしない経路の獲得を容易にしたからであると考えられる．パイプコストもわず
かだが大きいことを考えると，非常に短い時間でより良い結果が得られた本研究の手法が有効であることが分かった．

①②③Fig. 9 Results of the simulations.

Table 1 Results of the simulations.

実験条件

パイプNo.

従来の手法

12合計
12合計
12合計

細線化
のみ
細線化
＋回転

経由点候補の数

パイプコスト

7143
8441

26785
27164
53949
27833
24779
52612
28998
23271
52269

108
104
111107探索時間

点候補を回転させて配置することにより，パイプの曲がりの少ない経路を獲得することができた．狭隘な空間にも本研究による手法による配管設計は有効である事がわかった．

5638 秒
7. 結
21 秒

9秒

参 考 文 献1)

次に，曲面狭隘空間でのシミュレーション実験を行った．Fig. 10(A)が経由点候補を回転せずに配管，Fig. 10(B)が経由点候補を回転させて配管した処理結果である．

2)

3)

4)

(A)

Fig. 10(B)
Piping arrangement results of the previous method(A) and the proposed method (B).

今までの回転しない経由点候補生成では Fig. 10(A)のようにパイプが少ない距離で何度も曲がるような経路を獲得してしまっている．しかし，本研究の手法では経由言本研究では Voxel 図形処理を用いてパイプの自動配管システムにおける経由点候補の配置手法を提案し，計算時間を数百分の一に縮めるなど有効性を示した．今後の課題としては、パイプサポートや作業用通路、施工性や機器操作性も考慮した経由点候補の配置が挙げられる．

安藤 悠人，木村 元：エルボおよびベンドを考慮した配管設計アルゴリズム，日本船舶海洋工学会論文集，第 15 号， pp.219- 226，2012.
木村 元：パイプサポートや曲がり船殻に対応した配管自動設計に関する研究，日本船舶海洋工学会講演
会論文集 Vol.22 (2016 年 5 月 26～27 日，福岡県中小企業センター，福岡市) 講演予定.
K.Palágyi, A.Kuba: A 3D 6-subiteration thinningalgorithm for extracting medial lines, Pattern Recognition
Letters 19 (1998) 613–627.
K.Xu, R.Fu, L.Deng, Y.Ou, X.Wu: A Fast Robot Path
Planning Algorithm Based On Image Thinning,
International Conference on Intelligent Robotics andApplications (2010) 548-557.