(57)【要約】【課題】入力データのデータ容量を容易に圧縮する。【解決手段】データ変換装置におけるデータ変換作業では、入力データに含まれる複数のセル種類のうち図形数が２以上であるセル種類から、図形数が多い順に第１セル種類および第２セル種類が決定される。続いて、第１セル種類および第２セル種類の組み合わせにおいて複数のセルペアの位置情報を求め、ペア数が多い同位置ペア群のセルペアから順に、第１セルと第２セルとが合成されて合成セルが生成される（ステップＳ３１）。そして、合成処理が所定回数だけ行われるまで（ステップＳ３２）、合成セルを入力データが示すセルに含めた図形数の再取得（ステップＳ３３）、および、上述の合成処理が繰り返され、階層化された合成セルを含むセルを示す出力データが得られる。これにより、入力データのデータ容量を迅速かつ容易に圧縮して出力データを生成することができる。【選択図】図４．Ｃ
2008040927.tif 000002
【特許請求の範囲】
【請求項１】
複数の図形要素のデータを含む入力データを階層化して出力データに変換するデータ変換方法であって、
ａ）入力データが示す複数の図形要素の各種類に対応する図形要素の個数を示す図形数を求める工程と、
ｂ）図形数の多さに基づいて、図形数が２以上である第１の図形要素の種類と図形数が２以上である第２の図形要素の種類との各組み合わせに優先順位を設定し、最も優先順位の高い組み合わせにおける第１の図形要素の種類と第２の図形要素の種類とを決定する工程と、
ｃ）それぞれが、複数の第１の図形要素のいずれかと複数の第２の図形要素のいずれかとの組み合わせである複数の図形要素ペアを求め、各図形要素ペアにおける第１の図形要素に対する第２の図形要素の位置ベクトルを示す位置情報を求める工程と、
ｄ）前記複数の図形要素ペアのうち前記位置情報が等しい図形要素ペアの少なくとも１つの集合を同位置ペア群として求め、各同位置ペア群に含まれる図形要素ペアの個数を示すペア数を求める工程と、
ｅ）ペア数が２以上であって前記ペア数が最も多い同位置ペア群を処理対象ペア群として特定できる場合に、前記処理対象ペア群の各図形要素ペアに含まれる第１の図形要素と第２の図形要素とを一の合成図形要素に合成する工程と、
ｆ）前記ｅ）工程において前記合成が行われなかった場合に、次に優先順位の高い組み合わせにおける第１の図形要素の種類と第２の図形要素の種類とを決定して前記ｃ）工程ないし前記ｅ）工程を繰り返す工程と、
ｇ）前記ｅ）工程において前記合成が行われた場合に、合成図形要素を前記入力データが示す図形要素に含めて前記ａ）工程ないし前記ｆ）工程を行うことにより、階層化された合成図形要素を含む図形要素を示す出力データを得る工程と、
を備えることを特徴とするデータ変換方法。
【請求項２】
請求項１に記載のデータ変換方法であって、
前記ｅ）工程と前記ｆ）工程との間に、
ｈ）各同位置ペア群のペア数から、前記ｅ）工程にて合成図形要素に変換された第１の図形要素および第２の図形要素の少なくとも一方を含む図形要素ペアの個数を減じる工程と、
ｉ）各同位置ペア群のペア数が全て１または０になるまで前記ｅ）工程および前記ｈ）工程を繰り返す工程と、
をさらに備えることを特徴とするデータ変換方法。
【請求項３】
請求項１または２に記載のデータ変換方法であって、
前記ｇ）工程の実行が、所定回数に制限されることを特徴とするデータ変換方法。
【請求項４】
請求項１ないし３のいずれかに記載のデータ変換方法であって、
前記ｇ）工程において、合成図形要素の各種類に対応する図形数が、一の合成図形要素の種類に属する合成図形要素の個数と、前記合成図形要素に含まれる図形要素の個数との積として求められることを特徴とするデータ変換方法。
【請求項５】
請求項１ないし４のいずれかに記載のデータ変換方法であって、
前記ｂ）工程および前記ｆ）工程において、前記第１の図形要素の種類と前記第２の図形要素の種類とが同じになることが許容されることを特徴とするデータ変換方法。
【請求項６】
請求項１ないし５のいずれかに記載のデータ変換方法であって、
前記ｃ）工程において、前記位置情報が、前記第１の図形要素に外接する矩形枠の第１頂点に対する、前記第２の図形要素に外接する矩形枠の前記第１頂点に対応する第２頂点の位置ベクトルとして求められることを特徴とするデータ変換方法。
【請求項７】
請求項１ないし６のいずれかに記載のデータ変換方法であって、
前記ｄ）工程において、各同位置ペア群に含まれる図形要素ペアの位置情報が、直交座標系の第１座標および第２座標にて表現され、前記第１座標および前記第２座標と前記各同位置ペア群のペア数との関係を示す共起行列が生成されることを特徴とするデータ変換方法。
【請求項８】
請求項１ないし７のいずれかに記載のデータ変換方法であって、
前記ｃ）工程において、各図形要素ペアにおける第１の図形要素と第２の図形要素との間の距離が所定距離以下に制限されることを特徴とするデータ変換方法。
【請求項９】
請求項１ないし８のいずれかに記載のデータ変換方法であって、
前記入力データが半導体集積回路用のパターンデータであることを特徴とするデータ変換方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、複数の図形要素のデータを含む入力データを階層化して出力データに変換するデータ変換方法に関する。
【背景技術】
【０００２】
従来より、半導体基板に形成されるＬＳＩ（Large Scale Integrated Circuit）の回路パターンは、複数の図形要素であるセルの集合として表現されている。近年、ＬＳＩの高集積化に伴い、当該回路パターンを示すパターンデータのデータ容量が大きくなっており、パターンデータを記憶する記憶装置の大型化やデータ処理の長時間化が指摘されている。
【０００３】
そこで、特許文献１では、パターンデータが示す回路パターンにおいて、等間隔で繰り返し出現する単独図形の二次元アレイを生成し、複数の二次元アレイのうち、中に含まれる単独図形の個数、配置およびピッチが等しい二次元アレイ同士をグループ化して複数図形の二次元アレイを生成することにより、パターンデータを階層化してデータ容量を圧縮する技術が提案されている。
【特許文献１】特開２００１−２３０６７６号公報
【発明の開示】
【発明が解決しようとする課題】
【０００４】
ところで、特許文献１のデータ圧縮装置では、等間隔で出現する単独図形のみが階層化の対象となるため、それ以外の単独図形の組み合わせは階層化の対象とならず、パターンデータのデータ容量の圧縮に限界があり、また、様々なパターンデータの圧縮に容易に対応することができない。
【０００５】
本発明は、上記課題に鑑みなされたものであり、入力データのデータ容量を容易に圧縮することを目的としている。
【課題を解決するための手段】
【０００６】
請求項１に記載の発明は、複数の図形要素のデータを含む入力データを階層化して出力データに変換するデータ変換方法であって、ａ）入力データが示す複数の図形要素の各種類に対応する図形要素の個数を示す図形数を求める工程と、ｂ）図形数の多さに基づいて、図形数が２以上である第１の図形要素の種類と図形数が２以上である第２の図形要素の種類との各組み合わせに優先順位を設定し、最も優先順位の高い組み合わせにおける第１の図形要素の種類と第２の図形要素の種類とを決定する工程と、ｃ）それぞれが、複数の第１の図形要素のいずれかと複数の第２の図形要素のいずれかとの組み合わせである複数の図形要素ペアを求め、各図形要素ペアにおける第１の図形要素に対する第２の図形要素の位置ベクトルを示す位置情報を求める工程と、ｄ）前記複数の図形要素ペアのうち前記位置情報が等しい図形要素ペアの少なくとも１つの集合を同位置ペア群として求め、各同位置ペア群に含まれる図形要素ペアの個数を示すペア数を求める工程と、ｅ）ペア数が２以上であって前記ペア数が最も多い同位置ペア群を処理対象ペア群として特定できる場合に、前記処理対象ペア群の各図形要素ペアに含まれる第１の図形要素と第２の図形要素とを一の合成図形要素に合成する工程と、ｆ）前記ｅ）工程において前記合成が行われなかった場合に、次に優先順位の高い組み合わせにおける第１の図形要素の種類と第２の図形要素の種類とを決定して前記ｃ）工程ないし前記ｅ）工程を繰り返す工程と、ｇ）前記ｅ）工程において前記合成が行われた場合に、合成図形要素を前記入力データが示す図形要素に含めて前記ａ）工程ないし前記ｆ）工程を行うことにより、階層化された合成図形要素を含む図形要素を示す出力データを得る工程とを備える。
【０００７】
請求項２に記載の発明は、請求項１に記載のデータ変換方法であって、前記ｅ）工程と前記ｆ）工程との間に、ｈ）各同位置ペア群のペア数から、前記ｅ）工程にて合成図形要素に変換された第１の図形要素および第２の図形要素の少なくとも一方を含む図形要素ペアの個数を減じる工程と、ｉ）各同位置ペア群のペア数が全て１または０になるまで前記ｅ）工程および前記ｈ）工程を繰り返す工程とをさらに備える。
【０００８】
請求項３に記載の発明は、請求項１または２に記載のデータ変換方法であって、前記ｇ）工程の実行が、所定回数に制限される。
【０００９】
請求項４に記載の発明は、請求項１ないし３のいずれかに記載のデータ変換方法であって、前記ｇ）工程において、合成図形要素の各種類に対応する図形数が、一の合成図形要素の種類に属する合成図形要素の個数と、前記合成図形要素に含まれる図形要素の個数との積として求められる。
【００１０】
請求項５に記載の発明は、請求項１ないし４のいずれかに記載のデータ変換方法であって、前記ｂ）工程および前記ｆ）工程において、前記第１の図形要素の種類と前記第２の図形要素の種類とが同じになることが許容される。
【００１１】
請求項６に記載の発明は、請求項１ないし５のいずれかに記載のデータ変換方法であって、前記ｃ）工程において、前記位置情報が、前記第１の図形要素に外接する矩形枠の第１頂点に対する、前記第２の図形要素に外接する矩形枠の前記第１頂点に対応する第２頂点の位置ベクトルとして求められる。
【００１２】
請求項７に記載の発明は、請求項１ないし６のいずれかに記載のデータ変換方法であって、前記ｄ）工程において、各同位置ペア群に含まれる図形要素ペアの位置情報が、直交座標系の第１座標および第２座標にて表現され、前記第１座標および前記第２座標と前記各同位置ペア群のペア数との関係を示す共起行列が生成される。
【００１３】
請求項８に記載の発明は、請求項１ないし７のいずれかに記載のデータ変換方法であって、前記ｃ）工程において、各図形要素ペアにおける第１の図形要素と第２の図形要素との間の距離が所定距離以下に制限される。
【００１４】
請求項９に記載の発明は、請求項１ないし８のいずれかに記載のデータ変換方法であって、前記入力データが半導体集積回路用のパターンデータである。
【発明の効果】
【００１５】
本発明では、入力データのデータ容量を容易に圧縮することができる。請求項２の発明では、入力データのデータ容量を迅速に圧縮することができる。請求項３ないし５並びに請求項８の発明では、入力データのデータ容量を効率良く圧縮することができる。請求項６の発明では、位置情報の取得を簡素化することができる。請求項７の発明では、処理対象ペア群の抽出を容易とすることができる。
【発明を実施するための最良の形態】
【００１６】
図１は、本発明の一の実施の形態に係るデータ変換装置１の構成を示す図である。データ変換装置１は、複数の図形要素のデータを含む入力データを階層化して出力データに変換する装置である。
【００１７】
本実施の形態では、入力データは、半導体集積回路であるＬＳＩ（Large Scale Integration）用の基板上に形成される回路パターンを示すパターンデータである。図２は、入力データにより表される回路パターンの一部を示す図である。図２に示すように、入力データでは、回路パターンを図形要素８（以下、「セル８」という。）の集合として捉えた上で、各セル８を特定する識別子、各セル８の形状を示すベクトルデータ、および、各セル８の基板９上における位置等を示すデータの集合として表現される。図２に示すように、セル８は通常、複数の矩形を組み合わせた多角形状である。また、入力データは、階層化されていないフラットなデータ構造（すなわち、各セル８を示すデータ要素が他のデータ要素を参照しない構造）を有する。
【００１８】
図１に示すように、データ変換装置１は、通常のコンピュータと同様に、各種演算処理を行うＣＰＵ１１、実行されるプログラムを記憶したり演算処理の作業領域となるＲＡＭ１２、基本プログラムを記憶するＲＯＭ１３、各種情報を記憶する固定ディスク１４、作業者に各種情報を表示するディスプレイ１５、および、キーボードやマウス等の入力部１６等を接続した構成となっている。固定ディスク１４内には、データ変換装置１により実行されるプログラム１４１が記憶される。プログラム１４１は、複数のセル８（図２参照）のデータを含む入力データを階層化して出力データに変換するプログラムである。
【００１９】
図３は、データ変換装置１のＣＰＵ１１（図１参照）等がプログラム１４１に従って演算処理を行うことにより実現される機能を他の構成と共に示すブロック図であり、図３中の記憶部２０、データ受付部２１、図形数取得部２２、シンボル化部２３、セル種類決定部２４、位置情報取得部２５、ペア数取得部２６、共起行列生成部２７、セル合成部２８およびデータ出力部２９が、ＣＰＵ１１等により実現される機能に相当する。なお、これらの機能は複数台のコンピュータにより実現されてもよい。
【００２０】
次に、データ変換装置１によるデータ変換の流れについて説明する。図４．Ａないし図４．Ｃ、並びに、図５は、データ変換装置１によるデータ変換の流れを示す図である。データ変換装置１では、まず、図３に示すデータ受付部２１により入力データが受け付けられる。図６は、入力データが示す基板９上の回路パターンを示す図である。図６に示すように、入力データには、複数種類のセル（本実施の形態では７種類のセルであり、それぞれ符号８ａ〜８ｇを付す。）に対応するデータ要素が含まれる。実際のデータ変換装置１では、後述する処理が、入力データに含まれる複数のセル８ａ〜８ｇ（以下、セル８ａ〜８ｇを区別する必要がない場合には、「セル８」と総称する。）に対応するデータ要素に対して行われるが、以下の説明では、理解を容易とするために、図６に示すセル８ａ〜８ｇを処理の取扱対象として説明する。なお、実際の入力データでは通常、図６に示すものよりも多種類かつ多数のセルを示すデータを含む。
【００２１】
入力データが受け付けられると、図形数取得部２２により、入力データが示す複数のセル８のうち同一形状（すなわち、同一種類）のセル８に同一の名称が付与される。本実施の形態では、図６に示すセル８ａ〜８ｇのそれぞれに対し、図７の表に示すように、「Ｃｅｌｌ＿Ａ」〜「Ｃｅｌｌ＿Ｇ」がセル種類の名称として付与される。そして、「Ｃｅｌｌ＿Ａ」〜「Ｃｅｌｌ＿Ｇ」の各セル種類に対応するセルの個数を示す図形数が、図形数取得部２２により求められて記憶部２０に記憶される（ステップＳ１１）。図７の表では、各セル種類の図形数も併せて記載している。
【００２２】
続いて、シンボル化部２３により、図６に示す複数のセル８ａ〜８ｇのそれぞれがシンボル化される（ステップＳ１２）。ここで、セルのシンボル化とは、図８に示すように、各セル８に外接する矩形枠８１（図８中にて二点鎖線にて示す。）により各セル８を表し、各セル８の基板９上における位置を、各セル８に外接する矩形枠８１の図８中における左下の頂点の座標にて表すことを意味する。本実施の形態では、各セル８の位置は、図８中における基板９の左下の頂点を原点とする直交座標系（すなわち、ＸＹ座標系）のＸ座標値およびＹ座標値にて表現される。図８では、図示の都合上、複数のセル８とこれらのセル８に外接する矩形枠８１とを僅かに離して描いている。
【００２３】
セルのシンボル化が終了すると、セル種類決定部２４により、図７に示すセル種類「Ｃｅｌｌ＿Ａ」〜「Ｃｅｌｌ＿Ｇ」が、図形数が多い順にソートされて図９に示す表（すなわち、セル種類と図形数との関係を示す表）が生成される（ステップＳ１３）。次に、図９に示す表に基づいて、図形数が２以上であるセル種類において図形数が多い方から２つのセル種類が選択され、以下の処理の対象となる「第１セル種類」および「第２セル種類」の組み合わせとされる（ステップＳ１４）。
【００２４】
このとき、選択された２つのセル種類のうち、図形数が多い方のセル種類が「第１セル種類」とされ、図形数が少ない方のセル種類が「第２セル種類」とされる。また、図形数が等しい場合は、図９に示す表において上に記載されているセル種類が「第１セル種類」とされ、下に記載されているセル種類が「第２セル種類」とされる。本実施の形態では、第１セル種類と第２セル種類とが同じになる（例えば、第１セル種類および第２セル種類共に「Ｃｅｌｌ＿Ａ」とされる）ことが許容される。したがって、最初の段階では、第１セル種類および第２セル種類の組み合わせとして、「Ｃｅｌｌ＿Ａ」および「Ｃｅｌｌ＿Ａ」が選択される。
【００２５】
このように、セル種類の重複を許容しつつ第１セル種類および第２セル種類の組み合わせが決定されると、位置情報取得部２５により、第１セル種類である「Ｃｅｌｌ＿Ａ」の１５個のセル８ａ（図６参照）のうち１個のセル８ａが第１セルとして選択され、第２セル種類である「Ｃｅｌｌ＿Ａ」の１５個のセル８ａのうち、第１セルとして選択されたセル８ａとは異なる１個のセル８ａが第２セルとして選択される。そして、第１セルと第２セルとの組み合わせであるセルペアにおいて、第１セルに対する第２セルの相対位置を位置ベクトルにて示す位置情報が求められる。
【００２６】
本実施の形態では、第１セルに外接する矩形枠８１の図８中における左下の頂点（すなわち、基板９上における直交座標系の原点に最も近い頂点）を第１頂点とし、第２セルに外接する矩形枠８１の当該第１頂点に対応する頂点を第２頂点として、第１頂点に対する第２頂点の位置ベクトルとして当該位置情報が求められる。位置情報は、図８に示す直交座標系（すなわち、ＸＹ座標系）のＸ座標値およびＹ座標値にて表現される。
【００２７】
位置情報取得部２５では、第１セルとして選択されたセル８ａ以外の１４個のセル８ａが順次第２セルとして選択され、第１セルに対する第２セルの位置情報が求められる。また、１５個のセル８ａが順次第１セルとして選択され、各第１セルに対して当該第１セル以外の１４個のセル８ａが順次第２セルとして選択されて位置情報の取得が繰り返される。換言すれば、位置情報取得部２５では、それぞれが、複数のセル８ａのいずれかと複数のセル８ａのいずれかとの組み合わせである複数のセルペアが求められ、各セルペアにおける第１セルに対する第２セルの位置情報が求められる（ステップＳ１５）。当該位置情報は、各セルペアに含まれる第１セルおよび第２セルの識別子と共に記憶部２０に記憶される。
【００２８】
このとき、第１セルと第２セルとの間の距離が所定距離よりも大きいセルペア（すなわち、第１セルと第２セルとが所定距離よりも離れているセルペア）については、位置情報等が記憶部２０に記憶されない。換言すれば、データ変換装置１では、各セルペアにおける第１セルと第２セルとの間の距離が所定距離以下に制限されて記憶部２０に記憶される。本実施の形態では、位置情報のＸ座標値が図８中の標準領域８２（すなわち、図８中において互いに近接して配置される４つのセルを囲む破線にて示す矩形）のＸ方向の辺の長さ以下であり、かつ、位置情報のＹ座標値が標準領域８２のＹ方向の辺の長さ以下である場合に、位置情報が記憶部２０に記憶される。なお、標準領域８２の大きさは、スタンダードセルと呼ばれる標準セル群の大きさに従って予め定められる。
【００２９】
一般的には、第１セルに対して上下左右に散在する多数の第２セルの位置情報が記憶部２０に記憶されるが、本実施の形態では、説明の都合上、標準領域８２を比較的小さく設定しているため、第１セル種類および第２セル種類が共に「Ｃｅｌｌ＿Ａ」である複数のセルペアのうち、図１０中において平行斜線を付すとともに実線の矩形枠８３にて囲む２組のセル８ａのセルペアのみの位置情報等が記憶部２０に記憶される。
【００３０】
次に、ペア数取得部２６により、複数のセルペアのうち、記憶部２０に記憶された位置情報が等しいセルペアの集合が同位置ペア群として求められ、各同位置ペア群に含まれるセルペアの個数がペア数として求められる。そして、共起行列生成部２７により、各同位置ペア群のペア数と各同位置ペア群に含まれるセルペアの位置情報とに基づいて、当該位置情報のＸ座標値およびＹ座標値とペア数との関係を示す共起行列が生成される（ステップＳ２１）。
【００３１】
図１０に示すように、第１セル種類および第２セル種類が共に「Ｃｅｌｌ＿Ａ」である複数のセルペアでは、２つのセルペアの位置情報が互いに異なるため、生成される共起行列は、図１１．Ａに示すように、ペア数が１の２つの要素を有する１行２列の行列となる。図１１．Ａでは、共起行列を表形式にて描いており、図１１．Ａ中の太線の矩形枠１０１に囲まれる部分が共起行列の要素となっている。図１１．Ａ中のＸ１，Ｘ２はそれぞれ、図１０中の上側および下側の矩形枠８３に囲まれたセルペアの位置情報のＸ座標値であり、Ｙ１は、図１０中の上側および下側の矩形枠８３に囲まれたセルペアの位置情報のＹ座標値である。具体的には、Ｘ１はセルの幅の約２倍の長さを示し、Ｘ２はセルの幅の約３倍の長さを示し、Ｙ１は０となる。図１１．Ａでは、座標（Ｘ１，Ｙ１）を位置情報として有する同位置ペア群のペア数が１であり、座標（Ｘ２，Ｙ１）を位置情報として有する同位置ペア群のペア数も１であることが示される（以下の共起行列を示す図においても同様）。
【００３２】
なお、本実施の形態では、上述のように標準領域８２を比較的小さく設定しているため、共起行列も図１１．Ａに示すように行数および列数が少ないものとなっているが、一般的には、共起行列生成部２７により生成される共起行列は、図１１．Ｂに示すように、複数行複数列となる。
【００３３】
共起行列が生成されると、セル合成部２８により、共起行列が２以上の値の要素を有するか否かが確認される（ステップＳ２２）。図１０の場合、図１１．Ａに示すように、共起行列の要素の値は全て１であるため、セル種類決定部２４により、次の第１セル種類および第２セル種類の組み合わせがあるか否かが確認される（ステップＳ２３）。ここで、次のセル種類の組み合わせが存在しない場合にはデータ変換装置１による処理が終了され、存在する場合には次のステップに進む。本実施の形態では、第１セル種類として「Ｃｅｌｌ＿Ａ」が固定された状態で、第２セル種類として「Ｃｅｌｌ＿Ａ」に次いで図形数が多い「Ｃｅｌｌ＿Ｂ」が選択され、次の第１セル種類および第２セル種類の組み合わせが決定される（ステップＳ２４）。
【００３４】
続いて、ステップＳ１５に戻って、位置情報取得部２５により、第１セルである図１２中のセル８ａと第２セルであるセル８ｂとの組み合わせである複数のセルペアが求められ、各セルペアにおける第１セルに対する第２セルの位置情報が求められる（ステップＳ１５）。そして、図１２中において平行斜線を付すとともに矩形枠８３１〜８３５にて囲んで示すように、第１セルと第２セルとの間の距離が所定距離以下の１８個のセルペアの位置情報等が記憶部２０に記憶される。図１２では、位置情報が等しいセルペアの集合（すなわち、１つの同位置ペア群）に含まれる各セルペアを、同じ線種の矩形枠にて囲んで示している。
【００３５】
次に、ペア数取得部２６により、複数のセルペアのうち位置情報が等しいセルペアの集合が同位置ペア群として求められ、各同位置ペア群に含まれるセルペアの個数がペア数として求められる。図１２に示すように、第１セル種類および第２セル種類が「Ｃｅｌｌ＿Ａ」および「Ｃｅｌｌ＿Ｂ」である複数のセルペアでは、５つの同位置ペア群のペア数が求められる。具体的には、図１２中において実線の矩形枠８３１に囲まれるセルペア、すなわち、セル８ａの右側にセル８ｂが隣接するセルペアのペア数が１２と求められる。また、破線の矩形枠８３２にて囲まれるセルペア（すなわち、セル８ａの左側にセル８ｂが隣接するセルペア）のペア数が３と求められ、長破線の矩形枠８３３にて囲まれるセルペア（すなわち、セル８ａの右側に２つのセルの幅だけ離間してセル８ｂが配置されるセルペア）、一点鎖線の矩形枠８３４にて囲まれるセルペア（すなわち、セル８ａの左側に１つのセルの幅だけ離間してセル８ｂが配置されるセルペア）、および、二点鎖線の矩形枠８３５にて囲まれるセルペア（すなわち、セル８ａの右側に１つのセルの幅だけ離間してセル８ｂが配置されるセルペア）のペア数がそれぞれ１と求められる。そして、共起行列生成部２７により、図１３に示す共起行列が生成される（ステップＳ２１）。
【００３６】
共起行列が生成されると、セル合成部２８により、共起行列が２以上の値の要素を有するか否かが確認される（ステップＳ２２）。図１３に示すように、共起行列には２以上の値の要素が含まれているため、セルペアに含まれる第１セルと第２セルとの合成処理が行われる（ステップＳ３１）。
【００３７】
合成処理が行われる際には、図１３に示す共起行列の最も値が大きい要素に対応する同位置ペア群（すなわち、ペア数が２以上であって、かつ、ペア数が最も多い同位置ペア群であり、本実施の形態では、図１２中において矩形枠８３１により囲まれるセルペアの集合）が処理対象ペア群として特定され、処理対象ペア群の各セルペアに含まれる第１セル（セル８ａ）と第２セル（セル８ｂ）とが合成されて一の合成図形要素である合成セルとされる（図５：ステップＳ４１）。これにより、図１４に示すように、１２個の合成セル８５ａが生成される。図１４では、各合成セル８５ａに含まれるセル８ａおよびセル８ｂを破線にて描いている。
【００３８】
セルの合成が終了すると、図１３に示す共起行列の各要素の値（すなわち、各同位置ペア群のペア数）から、合成セル８５ａに変換された第１セルと第２セルとに対応する値（すなわち、合成された第１セルおよび第２セルの少なくとも一方を含むセルペアの個数）が減じられる（ステップＳ４２）。具体的には、合成セル８５ａに変換されたセル８ａおよびセル８ｂの識別子と等しい識別子を有するセルペアが記憶部２０において検索され、当該セルペアが含まれる同位置ペア群のペア数が減じられる。これにより、図１２に示す矩形枠８３１に囲まれた１２個のセルペアを含む同位置ペア群のペア数から１２が減じられて０となり、矩形枠８３２に囲まれた３個のセルペアを含む同位置ペア群から１が減じられて２となる。また、矩形枠８３３，８３４，８３５に囲まれた１個のセルペアを含む同位置ペア群から１が減じられて０となり、図１３に示す共起行列が図１５に示すように変更される。
【００３９】
続いて、セル合成部２８により、共起行列が２以上の値の要素を有するか否かが確認される（ステップＳ４３）。図１５に示すように、共起行列には２以上の値の要素が含まれているため、ステップＳ４１に戻り、図１５に示す共起行列の最も値が大きい要素に対応する同位置ペア群（すなわち、図１４中において矩形枠８３２により囲まれるセルペアの集合）が処理対象ペア群として特定され、処理対象ペア群の各セルペアに含まれる第１セル（セル８ａ）と第２セル（セル８ｂ）とが合成されて合成セルとされる（ステップＳ４１）。これにより、図１６に示すように、２個の合成セル８５ｂが生成される。図１６では、図１４と同様に、各合成セル８５ｂに含まれるセル８ａおよびセル８ｂを破線にて描いている。
【００４０】
セルの合成が終了すると、図１５に示す共起行列の各要素の値から、合成セル８５ｂに変換された第１セルと第２セルとに対応する値が減じられ、図１７に示す共起行列とされる（ステップＳ４２）。次に、セル合成部２８により、共起行列が２以上の値の要素を有するか否かが確認される（ステップＳ４３）。データ変換装置１では、図１７に示すように、共起行列の要素の値（すなわち、同位置ペア群のペア数）が全て１または０になるまでセルの合成と共起行列からのペア数の減算が繰り返されて合成処理が終了した後、所定回数だけ合成処理が行われたか否かが確認される（図４．Ｃ：ステップＳ３２）。本実施の形態では、１組の第１セル種類および第２セル種類の組み合わせに対する合成処理を１回の合成処理と数え（例えば、上述の合成セル８５ａおよび合成セル８５ｂの生成を合わせて１回の合成処理と数え）、処理回数が５回未満である場合には次のステップに進んで合成処理が繰り返され、処理回数が５回となったときには以後の合成処理は行われない。換言すれば、データ変換装置１では、合成処理の処理回数が所定回数に制限されている。
【００４１】
図１６の段階では処理回数は１回であるため、図形数取得部２２により、合成セル８５ａ，８５ｂのそれぞれに対し、「Ｃｅｌｌ＿ＡＢ」、「Ｃｅｌｌ＿ＢＡ」がセル種類の名称として付与される。そして、図１６に示す複数のセル８ａ〜８ｇおよび合成セル８５ａ，８５ｂの図形数が図形数取得部２２により求められ（換言すれば、合成セル８５ａ，８５ｂを入力データが示すセル８ａ〜８ｇに含めて図形数が求められ）、セル種類の名称「Ｃｅｌｌ＿Ａ」〜「Ｃｅｌｌ＿Ｇ」、「Ｃｅｌｌ＿ＡＢ」、「Ｃｅｌｌ＿ＢＡ」に関連づけられて記憶部２０に記憶される（ステップＳ３３）。
【００４２】
図形数取得部２２では、合成セルの各種類（すなわち、「Ｃｅｌｌ＿ＡＢ」および「Ｃｅｌｌ＿ＢＡ」）に対応する図形数は、一の合成セルの種類に属する合成セルの個数と、当該合成セルにそれぞれ含まれるセルの個数の積として求められる。したがって、「Ｃｅｌｌ＿ＡＢ」の図形数は、合成セル８５ａの個数である１２個と、合成セル８５ａに含まれるセル（すなわち、セル８ａおよびセル８ｂ）の個数である２個との積である２４個とされる。また、「Ｃｅｌｌ＿ＢＡ」の図形数は、合成セル８５ｂの個数である２個と、合成セル８５ｂに含まれるセル（すなわち、セル８ａおよびセル８ｂ）の個数である２個との積である４個とされる。
【００４３】
図形数が取得されると、ステップＳ１３に戻って、セル種類決定部２４により、セル種類「Ｃｅｌｌ＿Ａ」〜「Ｃｅｌｌ＿Ｇ」、「Ｃｅｌｌ＿ＡＢ」、「Ｃｅｌｌ＿ＢＡ」が、図形数が多い順にソートされて図１８に示すセル種類と図形数との関係を示す表が生成される（ステップＳ１３）。続いて、図１８に示す表に基づいて、図形数が２以上であるセル種類において図形数が多い方から２つのセル種類が、セル種類が同じになることが許容されつつ選択され、「Ｃｅｌｌ＿ＡＢ」および「Ｃｅｌｌ＿ＡＢ」が、第１セル種類および第２セル種類の組み合わせとされる（ステップＳ１４）。
【００４４】
次に、位置情報取得部２５により、第１セルである複数の合成セル８５ａ（図１６参照）のいずれかと第２セルである複数の合成セル８５ａのいずれかとの組み合わせであるセルペアが求められ、各セルペアにおける第１セルに対する第２セルの位置情報が求められる（ステップＳ１５）。当該位置情報は、第１セルと第２セルとの間の距離が所定距離以下のセルペアのもののみ、各セルペアに含まれる第１セルおよび第２セルの識別子と共に記憶部２０に記憶される。本実施の形態では、図１９中において平行斜線を付すとともに実線の矩形枠８３にて囲む１組の合成セル８５ａのセルペアの位置情報等が記憶部２０に記憶される。
【００４５】
セルペアの位置情報が取得されると、ペア数取得部２６により、同位置ペア群に含まれるセルペアの個数がペア数として求められて共起行列が生成される（ステップＳ２１）。ここでは、セルペアが１個しかないため、共起行列は２以上の値の要素を持たず（ステップＳ２２）、セル種類決定部２４により、次の第１セル種類および第２セル種類の組み合わせがあるか否かが確認される（ステップＳ２３）。そして、第１セル種類として「Ｃｅｌｌ＿ＡＢ」が固定された状態で、第２セル種類として「Ｃｅｌｌ＿ＡＢ」に次いで図形数が多い「Ｃｅｌｌ＿Ｃ」が選択され、第１セル種類および第２セル種類の組み合わせが決定される（ステップＳ２４）。
【００４６】
続いて、ステップＳ１５に戻って、位置情報取得部２５により、第１セルである図２０中の合成セル８５ａと第２セルであるセル８ｃとの組み合わせである複数のセルペアが求められ、各セルペアにおける第１セルに対する第２セルの位置情報が求められる（ステップＳ１５）。そして、図２０中において平行斜線を付すとともに矩形枠８３６，８３７にて囲んで示すように、第１セルと第２セルとの間の距離が所定距離以下の６個のセルペアの位置情報等が記憶部２０に記憶される。図２０では、位置情報が等しいセルペアの集合（すなわち、１つの同位置ペア群）に含まれる各セルペアを、同じ線種の矩形枠にて囲んで示している。
【００４７】
次に、ペア数取得部２６により、複数のセルペアのうち位置情報が等しいセルペアの集合が同位置ペア群として求められ、各同位置ペア群に含まれるセルペアの個数がペア数として求められる。図２０に示すように、第１セル種類および第２セル種類が「Ｃｅｌｌ＿ＡＢ」および「Ｃｅｌｌ＿Ｃ」である複数のセルペアでは、２つの同位置ペア群のペア数が求められる。具体的には、図２０中において実線の矩形枠８３６に囲まれるセルペア、すなわち、合成セル８５ａの右側にセル８ｃが隣接するセルペアのペア数が５と求められ、破線の矩形枠８３７にて囲まれるセルペアのペア数が１と求められる。そして、共起行列生成部２７により、図２１に示す共起行列が生成される（ステップＳ２１）。
【００４８】
共起行列が生成されると、セル合成部２８により、共起行列が２以上の値の要素を有するか否かが確認される（ステップＳ２２）。図２１に示すように、共起行列には２以上の値の要素が含まれているため、セルペアに含まれる第１セルと第２セルとの合成処理が行われる（ステップＳ３１）。
【００４９】
合成処理が行われる際には、図２１に示す共起行列の最も値が大きい要素に対応する同位置ペア群（本実施の形態では、図２０中において矩形枠８３６により囲まれるセルペアの集合）が処理対象ペア群として特定され、処理対象ペア群の各セルペアに含まれる第１セル（合成セル８５ａ）と第２セル（セル８ｃ）とが合成されて、図２２に示す５個の合成セル８５ｃが生成される（ステップＳ４１）。図２２では、各合成セル８５ｃに含まれるセル８ａ、セル８ｂおよびセル８ｃを破線にて描いている。
【００５０】
セルの合成が終了すると、図２１に示す共起行列の各要素の値から、合成セル８５ｃに変換された第１セルと第２セルとに対応する値が減じられ、図２３に示す共起行列とされる（ステップＳ４２）。そして、セル合成部２８により、共起行列の要素の値（すなわち、同位置ペア群のペア数）が全て１または０になっていることが確認された後（ステップＳ４３）、合成処理の処理回数（２回）が所定回数（５回）以下であることが確認される（ステップＳ３２）。
【００５１】
続いて、図形数取得部２２により、合成セル８５ｃに対して「Ｃｅｌｌ＿ＡＢＣ」がセル種類の名称として付与され、図２２に示す複数のセル８ａ〜８ｇおよび合成セル８５ａ〜８５ｃの図形数が求められて記憶部２０に記憶される（ステップＳ３３）。図形数が取得されると、ステップＳ１３に戻って、セル種類決定部２４により、セル種類「Ｃｅｌｌ＿Ａ」〜「Ｃｅｌｌ＿Ｇ」、「Ｃｅｌｌ＿ＡＢ」〜「Ｃｅｌｌ＿ＡＢＣ」が、図形数が多い順にソートされて図２４に示すセル種類と図形数との関係を示す表が生成される（ステップＳ１３）。
【００５２】
次に、図形数が多い方から「Ｃｅｌｌ＿ＡＢＣ」および「Ｃｅｌｌ＿ＡＢＣ」が第１セル種類および第２セル種類の組み合わせとされ（ステップＳ１４）、当該組み合わせの各セルペアにおける第１セルに対する第２セルの位置情報が求められる（ステップＳ１５）。そして、同位置ペア群に含まれるセルペアの個数であるペア数が求められて共起行列が生成される（ステップＳ２１）。「Ｃｅｌｌ＿ＡＢＣ」および「Ｃｅｌｌ＿ＡＢＣ」が第１セル種類および第２セル種類とされる場合、図２２に示すように、２つの合成セル８５ｃが所定距離内に配置され、かつ、位置情報が等しいセルペアは存在しないため、共起行列は２以上の値の要素を持たず（ステップＳ２２）、次の第１セル種類および第２セル種類の組み合わせが決定される（ステップＳ２３，Ｓ２４）。
【００５３】
データ変換装置１では、第１セル種類として「Ｃｅｌｌ＿ＡＢＣ」が固定された状態で、第２セル種類として「Ｃｅｌｌ＿ＡＢＣ」に次いで図形数が多い「Ｃｅｌｌ＿ＡＢ」が選択され、各セルペアにおける位置情報、および、同位置ペア群のペア数が求められて共起行列が生成される（ステップＳ１５，Ｓ２１）。この場合も、図２２に示すように、合成セル８５ｃおよび合成セル８５ａが所定距離内に配置され、かつ、位置情報が等しいセルペアは存在しないため、セルの合成処理は行われず、次の第１セル種類および第２セル種類の組み合わせが決定される（ステップＳ２２〜Ｓ２４）。
【００５４】
セル種類決定部２４では、「Ｃｅｌｌ＿Ｄ」が第２セル種類として選択され、ステップＳ１５に戻って、位置情報取得部２５により、第１セルである図２５中の合成セル８５ｃと第２セルであるセル８ｄとの組み合わせである複数のセルペアが求められ、各セルペアにおける第１セルに対する第２セルの位置情報が求められる（ステップＳ１５）。そして、図２５中において平行斜線を付すとともに矩形枠８３８にて囲んで示すように、第１セルと第２セルとの間の距離が所定距離以下の５個のセルペアの位置情報等が記憶部２０に記憶される。
【００５５】
図２５に示すように、第１セル種類および第２セル種類が「Ｃｅｌｌ＿ＡＢＣ」および「Ｃｅｌｌ＿Ｄ」である５個のセルペアは位置情報が等しいため、これらのセルペアが含まれる同位置ペア群のペア数は５個とされ、値が５である１つの要素のみを有する共起行列が生成される（ステップＳ２１）。そして、セルペアに含まれる第１セル（合成セル８５ｃ）と第２セル（セル８ｄ）との合成処理が行われ（ステップＳ２２，Ｓ３１）、図２６に示す５個の合成セル８５ｄが生成される。図２６では、各合成セル８５ｄに含まれるセル８ａ、セル８ｂ、セル８ｃおよびセル８ｄを破線にて描いている。
【００５６】
セルの合成が終了すると、共起行列の各要素の値から、合成セル８５ｄに変換された第１セルと第２セルとに対応する値が減じられ（ステップＳ４２）、共起行列の要素の値（すなわち、同位置ペア群のペア数）が１または０（この場合は、０）になっていることが確認された後（ステップＳ４３）、合成処理の処理回数（３回）が所定回数（５回）以下であることが確認される（ステップＳ３２）。
【００５７】
続いて、合成セル８５ｄに対して「Ｃｅｌｌ＿ＡＢＣＤ」がセル種類の名称として付与され、図２６に示す複数のセル８ａ〜８ｇおよび合成セル８５ａ〜８５ｄの図形数が求められて記憶部２０に記憶される（ステップＳ３３）。図形数が取得されると、ステップＳ１３に戻って、セル種類決定部２４により、セル種類「Ｃｅｌｌ＿Ａ」〜「Ｃｅｌｌ＿Ｇ」、「Ｃｅｌｌ＿ＡＢ」〜「Ｃｅｌｌ＿ＡＢＣＤ」が、図形数が多い順にソートされて図２７に示すセル種類と図形数との関係を示す表が生成される（ステップＳ１３）。
【００５８】
ここでは、図形数が多い方から「Ｃｅｌｌ＿ＡＢＣＤ」および「Ｃｅｌｌ＿ＡＢＣＤ」が第１セル種類および第２セル種類の組み合わせとされ（ステップＳ１４）、各セルペアにおける位置情報、および、同位置ペア群のペア数が求められて共起行列が生成される（ステップＳ１５，Ｓ２１）。この場合、図２６に示すように、合成セル８５ｄおよび他の合成セル８５ｄが所定距離内に配置され、かつ、位置情報が等しいセルペアは存在しないため、セルの合成処理は行われず、次の第１セル種類および第２セル種類の組み合わせが決定される（ステップＳ２２〜Ｓ２４）。
【００５９】
データ変換装置１では、図２７に示す順に「Ｃｅｌｌ＿ＡＢ」「Ｃｅｌｌ＿Ｅ」「Ｃｅｌｌ＿Ｃ」「Ｃｅｌｌ＿ＢＡ」「Ｃｅｌｌ＿Ｄ」が順次第２セル種類として選択され、上記と同様にセルの合成処理が行われることなく、ステップＳ１５〜Ｓ２４が繰り返される（ステップＳ１５〜Ｓ２４）。なお、「Ｃｅｌｌ＿Ａ」「Ｃｅｌｌ＿Ｆ」「Ｃｅｌｌ＿Ｇ」「Ｃｅｌｌ＿ＡＢＣ」「Ｃｅｌｌ＿Ｂ」については、図形数が１以下であるため、同位置ペア群のペア数が２以上になる（すなわち、共起行列の要素の値が２以上になる）可能性がないため、第２セル種類として選択されない。
【００６０】
第２セル種類として選択できるセル種類がなくなると、第１セル種類が、「Ｃｅｌｌ＿ＡＢＣＤ」に次いで図形数が多い「Ｃｅｌｌ＿ＡＢ」に変更される。そして、上記と同様に、「Ｃｅｌｌ＿ＡＢ」「Ｃｅｌｌ＿Ｅ」「Ｃｅｌｌ＿Ｃ」「Ｃｅｌｌ＿ＢＡ」「Ｃｅｌｌ＿Ｄ」が順次第２セル種類として選択され、セルの合成処理が行われることなく、ステップＳ１５〜Ｓ２４が繰り返される（ステップＳ１５〜Ｓ２４）。
【００６１】
そして、「Ｃｅｌｌ＿ＡＢ」に次いで図形数が多い「Ｃｅｌｌ＿Ｅ」が第１セル種類および第２セル種類として選択され、各セルペアにおける第１セル（セル８ｅ）に対する第２セル（セル８ｅ）の位置情報が求められる（ステップＳ１５）。そして、図２８中において平行斜線を付すとともに矩形枠８３９にて囲んで示すように、第１セルと第２セルとの間の距離が所定距離以下の３個のセルペアの位置情報等が記憶部２０に記憶される。
【００６２】
図２８に示すように、第１セル種類および第２セル種類が共に「Ｃｅｌｌ＿Ｅ」である３個のセルペアは位置情報が等しいため、これらのセルペアが含まれる同位置ペア群のペア数は３個とされ、値が３である１つの要素のみを有する共起行列が生成される（ステップＳ２１）。そして、セルペアに含まれる第１セルと第２セルとの合成処理が行われ（ステップＳ２２，Ｓ３１）、図２９に示す３個の合成セル８５ｅが生成される。図２９では、各合成セル８５ｅに含まれるセル８ｅを破線にて描いている。
【００６３】
セルの合成が終了すると、共起行列の各要素の値から、合成セル８５ｅに変換された第１セルと第２セルとに対応する値が減じられ（ステップＳ４２）、共起行列の要素の値（すなわち、同位置ペア群のペア数）が１または０（この場合は、０）になっていることが確認された後（ステップＳ４３）、合成処理の処理回数（４回）が所定回数（５回）以下であることが確認される（ステップＳ３２）。
【００６４】
続いて、合成セル８５ｅに対して「Ｃｅｌｌ＿ＥＥ」がセル種類の名称として付与され、図２９に示す複数のセル８ａ〜８ｇおよび合成セル８５ａ〜８５ｅの図形数が求められて記憶部２０に記憶される（ステップＳ３３）。図形数が取得されると、ステップＳ１３に戻って、セル種類決定部２４により、セル種類「Ｃｅｌｌ＿Ａ」〜「Ｃｅｌｌ＿Ｇ」、「Ｃｅｌｌ＿ＡＢ」〜「Ｃｅｌｌ＿ＥＥ」が、図形数が多い順にソートされて図３０に示すセル種類と図形数との関係を示す表が生成される（ステップＳ１３）。
【００６５】
データ変換装置１では、「Ｃｅｌｌ＿ＡＢＣＤ」が第１セル種類として選択され、図３０に示す順に「Ｃｅｌｌ＿ＡＢＣＤ」「Ｃｅｌｌ＿ＡＢ」「Ｃｅｌｌ＿ＥＥ」「Ｃｅｌｌ＿Ｃ」「Ｃｅｌｌ＿ＢＡ」「Ｃｅｌｌ＿Ｄ」が順次第２セル種類として選択された状態で、ペア数が２以上の同位置ペア群が存在しないため、セルの合成処理が行われることなく、ステップＳ１５〜Ｓ２４が繰り返される（ステップＳ１５〜Ｓ２４）。
【００６６】
続いて、「Ｃｅｌｌ＿ＡＢ」が第１セル種類として選択され、「Ｃｅｌｌ＿ＡＢ」「Ｃｅｌｌ＿ＥＥ」「Ｃｅｌｌ＿Ｃ」「Ｃｅｌｌ＿ＢＡ」「Ｃｅｌｌ＿Ｄ」が順次第２セル種類として選択された状態で、セルの合成処理が行われることなく、ステップＳ１５〜Ｓ２４が繰り返される（ステップＳ１５〜Ｓ２４）。そして、「Ｃｅｌｌ＿ＡＢ」に次いで図形数が多い「Ｃｅｌｌ＿ＥＥ」が第１セル種類および第２セル種類として選択され、上記と同様に、セルの合成処理が行われることなく、ステップＳ１５〜Ｓ２４が繰り返される（ステップＳ１５〜Ｓ２４）。
【００６７】
次に、第１セル種類として「Ｃｅｌｌ＿ＥＥ」が固定された状態で、「Ｃｅｌｌ＿Ｃ」が第２セル種類として選択され、各セルペアにおける第１セル（合成セル８５ｅ）に対する第２セル（セル８ｃ）の位置情報が求められる（ステップＳ１５）。そして、図３１中において平行斜線を付すとともに矩形枠８４１，８４２にて囲んで示すように、第１セルと第２セルとの間の距離が所定距離以下の４個のセルペアの位置情報等が記憶部２０に記憶される。図３１では、位置情報が等しいセルペアの集合（すなわち、１つの同位置ペア群）に含まれる各セルペアを、同じ線種の矩形枠にて囲んで示している。
【００６８】
次に、複数のセルペアのうち位置情報が等しいセルペアの集合が同位置ペア群として求められ、各同位置ペア群に含まれるセルペアの個数がペア数として求められる。図３１に示すように、第１セル種類および第２セル種類が「Ｃｅｌｌ＿ＥＥ」および「Ｃｅｌｌ＿Ｃ」である複数のセルペアでは、２つの同位置ペア群のペア数が求められる。具体的には、図３１中において実線の矩形枠８４１に囲まれるセルペア、すなわち、合成セル８５ｅの右側にセル８ｃが隣接するセルペアのペア数が３と求められ、破線の矩形枠８４２にて囲まれるセルペア、すなわち、合成セル８５ｅの右側に１つのセルの幅だけ離間してセル８ｃが配置されるセルペアのペア数が１と求められる。そして、共起行列生成部２７により、図３２に示す共起行列が生成される（ステップＳ２１）。
【００６９】
共起行列が生成されると、ペア数が３の同位置ペア群のセルペア（すなわち、図３１中において矩形枠８４１に囲まれるセルペア）に含まれる第１セル（合成セル８５ｅ）と第２セル（セル８ｃ）との合成処理が行われ（ステップＳ２２，Ｓ３１）、図３３に示す３個の合成セル８５ｆが生成される。図３３では、各合成セル８５ｆに含まれるセル８ｅおよびセル８ｃを破線にて描いている。
【００７０】
セルの合成が終了すると、図３２に示す共起行列の各要素の値から、合成セル８５ｆに変換された第１セルと第２セルとに対応する値が減じられ、共起行列の要素の値（すなわち、同位置ペア群のペア数）が全て１または０になっていることが確認される（ステップＳ４３）。その後、合成処理の処理回数（５回）が所定回数（５回）と比較され（ステップＳ３２）、合成処理が所定回数だけ行われたことが確認されることにより、一連のデータ変換作業が終了する。データ変換装置１では、上述のデータ変換作業により入力データが変換されて出力データが生成され、当該出力データがデータ出力部２９により出力される。
【００７１】
以上に説明したように、データ変換装置１におけるデータ変換作業では、入力データに含まれる複数のセル種類のうち図形数が２以上であるセル種類に対して、図形数が多い順に優先順位が設定され、当該優先順位が最も高いものがそれぞれ第１セル種類および第２セル種類と決定される。続いて、第１セル種類および第２セル種類の組み合わせにおいて複数のセルペアの位置情報を求め、同位置ペア群のペア数が２以上のものがあれば、ペア数が多い同位置ペア群のセルペアから順に、第１セルと第２セルとが合成されて合成セルが生成される。ここで、セルの合成が行われた場合には、生成された合成セルを入力データが示すセルに含めてセルおよび合成セルの各種類に対応する図形数を求め、合成処理を繰り返すことにより、階層化された合成セルを含むセルを示す出力データが得られる。また、セルの合成が行われなかった場合には、次に優先度の高い組み合わせにおける第１セル種類と第２セル種類とが決定されてセルの合成の検討が繰り返される。
【００７２】
このように、図形数の多さに基づいて優先順位を設定してセルの合成を行うことにより、これらのセルを示す入力データを階層化することができ、入力データのデータ容量を迅速かつ容易に圧縮して出力データを生成することができる。通常、ＬＳＩ用のパターンデータでは、階層化によりデータ容量の大幅な圧縮が期待できる。このため、本実施の形態に係るデータ変換装置１によるデータ変換作業は、ＬＳＩ用のパターンデータの圧縮に特に適している。
【００７３】
また、データ変換装置１では、１組の第１セル種類および第２セル種類の組み合わせにおいて、同位置ペア群のペア数が全て１または０になるまでセルの合成が行われる。これにより、１組の第１セル種類および第２セル種類の組み合わせにおいて検出された位置情報が等しいセルペアを全て合成することができるため、入力データのデータ容量をより迅速に圧縮することができる。
【００７４】
データ変換装置１によるデータ変換作業では、第１セル種類および第２セル種類の組み合わせの決定において、第１セル種類と第２セル種類とが同じになることが許容されることにより、図形数が最も多いセル種類同士の組み合わせにおけるセルの合成を優先的に行うことができるため、入力データのデータ容量を効率良く圧縮することができる。また、合成セルの各種類に対応する図形数を、合成セルの個数と合成セルに含まれるセルの個数の積とすることにより、階層化された合成セルのデータを優先的に再度階層化することができるため、入力データのデータ容量をより効率良く圧縮することができる。
【００７５】
データ変換装置１では、第１セルに対する第２セルの位置情報を求める際に、所定距離よりも離れたセルの組み合わせに係る位置情報が記憶部２０に記憶されず、合成処理の対象とはされない。所定距離よりも離れたセルの組み合わせは、回路パターン等を示す入力データでは通常、出現頻度が高くないため、このような出現頻度が低いセルペアが合成されることを防止することにより、データ容量をさらに効率良く圧縮することができる。また、上述のように、データ変換作業における合成処理の回数が所定回数に制限されていることにより、圧縮率が高いセル種類の組み合わせにおける合成のみが行われるため、入力データのデータ容量をより一層効率良く圧縮することができる。
【００７６】
データ変換装置１では、入力データに含まれる複数のセルをシンボル化することにより、多角形状のセルの位置を簡素に表現することができるため、セルペアにおける第１セルに対する第２セルの位置情報の取得を簡素化することができる。また、同位置ペア群に含まれるセルペアの位置情報とペア数との関係を示す共起行列が生成されることにより、合成処理の対象とされる処理対象ペア群の抽出を容易とすることができる。
【００７７】
以上、本発明の実施の形態について説明してきたが、本発明は上記実施の形態に限定されるものではなく、様々な変更が可能である。
【００７８】
データ変換装置１では、第１セル種類および第２セル種類の組み合わせの決定は、必ずしも上述の方法にて行われる必要はなく、例えば、２つのセル種類の図形数の合計が多い順に２つのセル種類の組み合わせに優先順位が設定され、優先順位の高い組み合わせにおける２つのセル種類が、順次、セルの合成が検討される第１セル種類および第２セル種類と決定されてもよい。すなわち、データ変換装置１では、図形数の多さに基づく様々な手法にて、２以上の図形数を有する２つのセル種類の各組み合わせに優先順位が設定されてよい。なお、入力データが示す複数のセル種類において、合成に利用することが禁止されている合成不能セル種類が予め指定されている場合には、当該合成不能セル種類は第１セル種類および第２セル種類の組み合わせの決定において選択対象から除外される。
【００７９】
上述のように、データ変換装置１では、第１セルと第２セルとの間のＸ方向およびＹ方向の距離がそれぞれ、いわゆるスタンダードセルの大きさに従った標準領域のＸ方向およびＹ方向の長さ以下であるセルペアの位置情報のみが記憶部２０に記憶されて合成処理の対象とされる。上記実施の形態では、標準領域の各辺の長さは、数μｍ程度を想定しているが、入力データの種類により、例えば、１０μｍ以上であってもよく、逆に、１μｍ以下であってもよい。また、上記の位置情報取得では、例えば、第１セルと第２セルとの間のＸ方向およびＹ方向の距離がそれぞれ、標準領域の各辺の長さの整数倍以下であるセルペアの位置情報のみが取得されてもよい。この場合、図１１．Ｂに例示したように、当該位置情報と同位置ペア群のペア数を示す共起行列は、複数行複数列の要素を有する行列となる。さらには、セルペアの位置情報取得時の距離制限は、必ずしも標準領域の大きさに基づいて行われる必要はなく、他の様々な基準に基づいて行われてよい。
【００８０】
上記実施の形態では、合成処理の繰り返し回数が５回に制限されているが、処理回数の上限は２回以上であれば必ずしも５回には限定されない。また、処理の効率化よりもデータ容量の更なる圧縮が重要視される場合には、処理回数の制限は行われず、合成処理の対象となるセルおよび合成セルがなくなるまで上述の合成処理が繰り返されてもよい。
【００８１】
データ変換装置１により変換される入力データは、必ずしもＬＳＩ用のパターンデータには限定されず、例えば、他の回路基板や半導体基板、または、プラズマ表示装置や液晶表示装置等のフラットパネル表示装置若しくはフォトマスク用のガラス基板等の形成に利用されるパターンデータであってもよい。また、他の様々な目的に利用される入力データがデータ変換装置１により変換されて階層化されてもよい。
【図面の簡単な説明】
【００８２】
【図１】データ変換装置の構成を示す図である。
【図２】回路パターンの一部を示す図である。
【図３】データ変換装置の機能を示すブロック図である。
【図４．Ａ】データ変換の流れを示す図である。
【図４．Ｂ】データ変換の流れを示す図である。
【図４．Ｃ】データ変換の流れを示す図である。
【図５】データ変換の流れを示す図である。
【図６】回路パターンを示す図である。
【図７】セル種類の名称とセルとの関係を示す図である。
【図８】回路パターンの一部を示す図である。
【図９】セル種類と図形数との関係を示す図である。
【図１０】回路パターンを示す図である。
【図１１．Ａ】共起行列を示す図である。
【図１１．Ｂ】共起行列を示す図である。
【図１２】回路パターンを示す図である。
【図１３】共起行列を示す図である。
【図１４】回路パターンを示す図である。
【図１５】共起行列を示す図である。
【図１６】回路パターンを示す図である。
【図１７】共起行列を示す図である。
【図１８】セル種類と図形数との関係を示す図である。
【図１９】回路パターンを示す図である。
【図２０】回路パターンを示す図である。
【図２１】共起行列を示す図である。
【図２２】回路パターンを示す図である。
【図２３】共起行列を示す図である。
【図２４】セル種類と図形数との関係を示す図である。
【図２５】回路パターンを示す図である。
【図２６】回路パターンを示す図である。
【図２７】セル種類と図形数との関係を示す図である。
【図２８】回路パターンを示す図である。
【図２９】回路パターンを示す図である。
【図３０】セル種類と図形数との関係を示す図である。
【図３１】回路パターンを示す図である。
【図３２】共起行列を示す図である。
【図３３】回路パターンを示す図である。
【符号の説明】
【００８３】
８，８ａ〜８ｇ    セル
８１    矩形枠
８５ａ〜８５ｆ    合成セル
Ｓ１１〜Ｓ１５，Ｓ２１〜Ｓ２４，Ｓ３１〜Ｓ３３，Ｓ４１〜Ｓ４３    ステップ
【図１】
2008040927.tif 000003
【図２】
2008040927.tif 000004
【図３】
2008040927.tif 000005
【図４．Ａ】
2008040927.tif 000006
【図４．Ｂ】
2008040927.tif 000007
【図４．Ｃ】
2008040927.tif 000008
【図５】
2008040927.tif 000009
【図６】
2008040927.tif 000010
【図７】
2008040927.tif 000011
【図８】
2008040927.tif 000012
【図９】
2008040927.tif 000013
【図１０】
2008040927.tif 000014
【図１１．Ａ】
2008040927.tif 000015
【図１１．Ｂ】
2008040927.tif 000016
【図１２】
2008040927.tif 000017
【図１３】
2008040927.tif 000018
【図１４】
2008040927.tif 000019
【図１５】
2008040927.tif 000020
【図１６】
2008040927.tif 000021
【図１７】
2008040927.tif 000022
【図１８】
2008040927.tif 000023
【図１９】
2008040927.tif 000024
【図２０】
2008040927.tif 000025
【図２１】
2008040927.tif 000026
【図２２】
2008040927.tif 000027
【図２３】
2008040927.tif 000028
【図２４】
2008040927.tif 000029
【図２５】
2008040927.tif 000030
【図２６】
2008040927.tif 000031
【図２７】
2008040927.tif 000032
【図２８】
2008040927.tif 000033
【図２９】
2008040927.tif 000034
【図３０】
2008040927.tif 000035
【図３１】
2008040927.tif 000036
【図３２】
2008040927.tif 000037
【図３３】
2008040927.tif 000038