(57)【要約】      （修正有）【課題】並べ替えに使用するメモリサイズを最小に抑え、データのコピー回数が少なく高速に並び替えを行うことができ、また、インターレースデータのインターレース間隔に関係なく同一アルゴリズムですべてのインターレースデータの並び替えを実現する。【解決手段】ｈ，ｉを正の整数、ｉ＜ｈとして、全ｈ行の画像データ列がインターレース間隔ｉのインターレース方式で格納されたメモリ空間から現在画像データを取り出し、同一のメモリ空間に全ｈ行のノンインターレース方式の画像データに並び替える画像データの変換方法において、着目した現在画像データの行番号を現在行番号ｙとして設定し、並び替えた後の目的画像データの目的行番号を取得する関数ｆ（ｙ）を、下記のものとし、行番号リンクリストを作成して行う。2007271988.tif 000038  （ただし０≦ｙ≦ｈ−１）【選択図】図３
2007271988.tif 000002
【特許請求の範囲】
【請求項１】
ｈ，ｉを正の整数、ｉ＜ｈとして、全ｈ行の画像データ列がインターレース間隔ｉのインターレース方式で格納されたメモリ空間から現在画像データを取り出し、同一のメモリ空間に全ｈ行のノンインターレース方式の画像データに並び替える画像データの変換方法において、
着目した現在画像データの行番号を現在行番号ｙとして設定し、並び替えた後の目的画像データの目的行番号を取得する関数ｆ（ｙ）を、
【数１】
2007271988.tif 000027
（ただし０≦ｙ≦ｈ−１）
として算出し、
求められた目的行番号ｆ（ｙ）の値を次の現在行番号ｙとして新たな目的行番号ｆ（ｙ）を求め、
この処理を繰り返して、目的行番号ｆ（ｙ）が最初に設定した現在行番号ｙに一致するまでこの処理を行い、
これらの処理を必要に応じて繰り返し、すべての現在行番号ｙについて目的行番号ｆ（ｙ）を得ることを特徴とする画像データ変換方法。
【請求項２】
ｈ，ｉを正の整数、ｉ＜ｈとして、全ｈ行の画像データ列がインターレース間隔ｉのインターレース方式で格納されたメモリ空間から現在画像データを取り出し、同一のメモリ空間に全ｈ行のノンインターレース方式の画像データに並び替える画像データの変換方法において、
着目した現在画像データの行番号を現在行番号ｙとして設定し、並び替えた後の目的画像データの目的行番号を取得する関数ｆ（ｙ）を、
【数２】
2007271988.tif 000028
（ただし０≦ｙ≦ｈ−１）
として算出し、
求められた目的行番号ｆ（ｙ）の値を次の現在行番号ｙとして新たな目的行番号ｆ（ｙ）を求め、
この処理を繰り返して、目的行番号ｆ（ｙ）が最初に設定した現在行番号ｙに一致するまでこの処理を行い、
現在行番号と目的行番号の対を備えた行番号リンクリストを作成し、
この行番号リンクリストから選択した一つの画像データ行を前記メモリ空間外に待避し、
前記行番号リンクリストを参照して待避した列に該列に配置されるべき画像データを移動する画像データ行の移動処理を行うことを特徴とする画像データ変換方法。
【請求項３】
ｈ，ｉを正の整数、ｉ＜ｈとして、全ｈ行の画像データ列がインターレース間隔ｉのインターレース方式で格納されたメモリ空間から現在画像データを取り出し、同一のメモリ空間に全ｈ行のノンインターレース方式の画像データに並び替える画像データの変換装置において、
着目した現在画像データの行番号を現在行番号ｙとして設定し、並び替えた後の目的画像データの目的行番号を取得する関数ｆ（ｙ）を、
【数３】
2007271988.tif 000029
（ただし０≦ｙ≦ｈ−１）
として算出する目的行番号演算手段と、
求められた目的行番号ｆ（ｙ）の値を次の現在行番号ｙとして新たな目的行番号ｆ（ｙ）を求め、この処理を繰り返して、目的行番号ｆ（ｙ）が最初に設定した現在行番号ｙに一致するまでこの処理を行い、これらの処理を必要に応じて繰り返し、すべての現在行番号ｙについて目的行番号ｆ（ｙ）を得る処理を行う演算制御手段と、
を備えることを特徴とする画像データ変換装置。
【請求項４】
ｈ，ｉを正の整数、ｉ＜ｈとして、全ｈ行の画像データ列がインターレース間隔ｉのインターレース方式で格納されたメモリ空間から現在画像データを取り出し、同一のメモリ空間に全ｈ行のノンインターレース方式の画像データに並び替える画像データの変換装置において、
着目した現在画像データの行番号を現在行番号ｙとして設定し、並び替えた後の目的画像データの目的行番号を取得する関数ｆ（ｙ）を、
【数４】
2007271988.tif 000030
（ただし０≦ｙ≦ｈ−１）
として算出する目的番号算出手段と、
求められた目的行番号ｆ（ｙ）の値を次の現在行番号ｙとして新たな目的行番号ｆ（ｙ）を求め、この処理を繰り返して、目的行番号ｆ（ｙ）が最初に設定した現在行番号ｙに一致するまでこの処理を行い、現在行番号と目的行番号の対を備えた行番号リンクリストを作成する行番号リンクリスト作成手段と、
この行番号リンクリストから選択した一つの画像データ行が待避される前記メモリ空間外に配置された画像待避メモリと、
前記行番号リンクリストを参照して待避した列に該列に配置されるべき画像データを順次移動する画像データ行の移動処理を行うデータ移動制御手段と、
を備えることを特徴とする画像データ変換装置。
【請求項５】
請求項1又は２の画像データ変換方法を備え、ノンインターレース方式の画像を表示することを特徴とする画像データ表示方法。
【請求項６】
請求項３又は４の画像データ変換装置を備え、ノンインターレース方式の画像を表示することを特徴とする画像データ表示装置。
【請求項７】
請求項1又は２の画像データ変換方法を格納したことを特徴とするコンピュータプログラム。
【請求項８】
請求項３又は４の画像データ表示方法を格納したことを特徴とするコンピュータプログラム。
【請求項９】
電子線源からの電子線で試料の所定範囲を走査して照射する電子光学系と、試料から発生する荷電粒子ビームを受け前記電子線の走査に対応させて試料の画像情報を得る演算処理装置とを備え、前記電子光学系は、荷電粒子ビームを、ｈ，ｉを正の整数、ｉ＜ｈとして、全ｈ行、インターレース間隔ｉで走査するよう制御され、
前記演算処理装置には、インターレース方式で得られた画像を現在画像データとして記録する画像メモリを備え、
前記画像メモリには、画像データ処理装置が接続され、
該画像データ処理装置は、
着目した現在画像データの行番号を現在行番号ｙとして設定し、並び替えた後の目的画像データの目的行番号を取得する関数ｆ（ｙ）を、
【数５】
2007271988.tif 000031
（ただし０≦ｙ≦ｈ−１）
として算出する目的行番号演算手段と、
求められた目的行番号ｆ（ｙ）の値を次の現在行番号ｙとして新たな目的行番号ｆ（ｙ）を求め、この処理を繰り返して、目的行番号ｆ（ｙ）が最初に設定した現在行番号ｙに一致するまでこの処理を行い、これらの処理を必要に応じて繰り返し、すべての現在行番号ｙについて目的行番号ｆ（ｙ）を得る処理を行う演算制御手段と、
求められた目的行番号ｆ（ｙ）の値を次の現在行番号ｙとして新たな目的行番号ｆ（ｙ）を求め、この処理を繰り返して、目的行番号ｆ（ｙ）が最初に設定した現在行番号ｙに一致するまでこの処理を行い、現在行番号と目的行番号の対を備えた行番号リンクリストを作成する行番号リンクリスト作成手段と、
この行番号リンクリストから選択した一つの画像データ行が待避される前記メモリ空間外に配置された画像待避メモリと、
前記行番号リンクリストを参照して待避した列に該列に配置されるべき画像データを順次移動する画像データ行の移動処理を行うデータ移動制御手段と、
前表示手段に表示させる演算手段を有することを特徴とする荷電粒子ビーム装置。
【請求項１０】
ｈ，ｉを正の整数、ｉ＜ｈとして、全ｈ行のデータ列がインターレース間隔ｉのインターレース方式で格納されたメモリ空間から現在データを取り出し、同一のメモリ空間に全ｈ行のノンインターレース方式のデータに並び替えるデータの変換方法において、
着目した現在データの行番号を現在行番号ｙとして設定し、並び替えた後の目的データの目的行番号を取得する関数ｆ（ｙ）を、
【数６】
2007271988.tif 000032
（ただし０≦ｙ≦ｈ−１）
として算出し、
求められた目的行番号ｆ（ｙ）の値を次の現在行番号ｙとして新たな目的行番号ｆ（ｙ）を求め、
この処理を繰り返して、目的行番号ｆ（ｙ）が最初に設定した現在行番号ｙに一致するまでこの処理を行い、
これらの処理を必要に応じて繰り返し、すべての現在行番号ｙについて目的行番号ｆ（ｙ）を得ることを特徴とするデータ変換方法。
【請求項１１】
ｈ，ｉを正の整数、ｉ＜ｈとして、全ｈ行のデータ列がインターレース間隔ｉのインターレース方式で格納されたメモリ空間から現在データを取り出し、同一のメモリ空間に全ｈ行のノンインターレース方式のデータに並び替えるデータの変換方法において、
着目した現在データの行番号を現在行番号ｙとして設定し、並び替えた後の目的データの目的行番号を取得する関数ｆ（ｙ）を、
【数７】
2007271988.tif 000033
（ただし０≦ｙ≦ｈ−１）
として算出し、
求められた目的行番号ｆ（ｙ）の値を次の現在行番号ｙとして新たな目的行番号ｆ（ｙ）を求め、
この処理を繰り返して、目的行番号ｆ（ｙ）が最初に設定した現在行番号ｙに一致するまでこの処理を行い、
これらの処理を必要に応じて繰り返し、すべての現在行番号ｙについて目的行番号ｆ（ｙ）を得ることを特徴とするデータ変換方法。
【請求項１２】
ｈ，ｉを正の整数、ｉ＜ｈとして、全ｈ行のデータ列がインターレース間隔ｉのインターレース方式で格納されたメモリ空間から現在データを取り出し、同一のメモリ空間に全ｈ行のノンインターレース方式のデータに並び替えるデータの変換方法において、
着目した現在データの行番号を現在行番号ｙとして設定し、並び替えた後の目的データの目的行番号を取得する関数ｆ（ｙ）を、
【数８】
2007271988.tif 000034
（ただし０≦ｙ≦ｈ−１）
として算出し、
求められた目的行番号ｆ（ｙ）の値を次の現在行番号ｙとして新たな目的行番号ｆ（ｙ）を求め、
この処理を繰り返して、目的行番号ｆ（ｙ）が最初に設定した現在行番号ｙに一致するまでこの処理を行い、
現在行番号と目的行番号の対を備えた行番号リンクリストを作成し、
この行番号リンクリストから選択した一つのデータ行を前記メモリ空間外に待避し、
前記行番号リンクリストを参照して待避した列に該列に配置されるべきデータを移動するデータ行の移動処理を行うことを特徴とするデータ変換方法。
【請求項１３】
ｈ，ｉを正の整数、ｉ＜ｈとして、全ｈ行のデータ列がインターレース間隔ｉのインターレース方式で格納されたメモリ空間から現在データを取り出し、同一のメモリ空間に全ｈ行のノンインターレース方式のデータに並び替えるデータの変換装置において、
着目した現在データの行番号を現在行番号ｙとして設定し、並び替えた後の目的データの目的行番号を取得する関数ｆ（ｙ）を、
【数９】
2007271988.tif 000035
（ただし０≦ｙ≦ｈ−１）
として算出する目的行番号演算手段と、
求められた目的行番号ｆ（ｙ）の値を次の現在行番号ｙとして新たな目的行番号ｆ（ｙ）を求め、この処理を繰り返して、目的行番号ｆ（ｙ）が最初に設定した現在行番号ｙに一致するまでこの処理を行い、これらの処理を必要に応じて繰り返し、すべての現在行番号ｙについて目的行番号ｆ（ｙ）を得る処理を行う演算制御手段と、
を備えることを特徴とするデータ変換装置。
【請求項１４】
ｈ，ｉを正の整数、ｉ＜ｈとして、全ｈ行のデータ列がインターレース間隔ｉのインターレース方式で格納されたメモリ空間から現在データを取り出し、同一のメモリ空間に全ｈ行のノンインターレース方式のデータに並び替えるデータの変換装置において、
着目した現在データの行番号を現在行番号ｙとして設定し、並び替えた後の目的データの目的行番号を取得する関数ｆ（ｙ）を、
【数１０】
2007271988.tif 000036
（ただし０≦ｙ≦ｈ−１）
として算出する目的番号算出手段と、
求められた目的行番号ｆ（ｙ）の値を次の現在行番号ｙとして新たな目的行番号ｆ（ｙ）を求め、この処理を繰り返して、目的行番号ｆ（ｙ）が最初に設定した現在行番号ｙに一致するまでこの処理を行い、現在行番号と目的行番号の対を備えた行番号リンクリストを作成する行番号リンクリスト作成手段と、
この行番号リンクリストから選択した一つのデータ行が待避される前記メモリ空間外に配置された待避メモリと、
前記行番号リンクリストを参照して待避した列に該列に配置されるべきデータを順次移動するデータ行の移動処理を行うデータ移動制御手段と、
を備えることを特徴とするデータ変換装置。
【請求項１５】
ｈmodｉ≠０のとき、
ｈ＝ｈ’
【数１１】
2007271988.tif 000037
なるｉで割切れるｈを設定して処理をすることを特徴とする請求項１もしくは２記載の画像データ変換方法、請求項３もしくは４記載の画像データ変換装置、請求項５記載の画像データ表示装置、請求項６記載の画像データ表示装置、請求項７もしくは８記載のコンピュータプログラム、請求項９記載の荷電粒子ビーム装置、請求項１０もしくは１１記載のデータ変換方法、または、請求項１２もしくは１３記載のデータ変換装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、インターレース方式で作成された画像データをノンインターレース方式の画像データに並び替える画像データ処理方法、画像データ処理装置、画像表示方法、画像表示装置、コンピュータプログラム、荷電粒子ビーム装置、データ処理方法、データ処理装置に関する。
【背景技術】
【０００２】
従来の荷電粒子ビーム装置例えば走査電子顕微鏡にあっては、試料のチャージアップを防止する観点から、試料の撮影領域に電子線を走査して照射するとき、インターレース方式を使用している。即ち、試料に電子ビームを走査するとき、隣り合う走査線領域に連続して電子線などを照射すると、試料に電子が貯溜してチャージアップし、撮影画像に悪影響を及ぼすこととなる。
【０００３】
このような事態を防止するため、試料に電子線を走査するとき、複数列おきに複数回に分けて領域全体を走査するインターレース方式を採用している。このように電子線を複数列（２、３，４，…）に分けると、走査された走査線領域に隣接する領域には、電子線が数走査後のタイミングで走査されるため、チャージアップを防止することができる。
【０００４】
しかしながら、電子顕微鏡で得られた画像について表示する場合には、試料の走査領域が連続して表示されるノンインターレース方式が採用されていることから、インターレース方式の画像データをノンインターレース方式に変換しなければならない。
【０００５】
従来このような変換を行うためには、図１３に示すように、別のメモリ領域へコピーしながら並び替える方法や、図１４に示すようにインターレース間隔の本数に応じたアルゴリズムを作成し、同一メモリ空間内で並び替えるものとしている。
【０００６】
また、一般的なデジタルデータを並べ替える際に、並べ替える先のメモリ領域を指定して並べ替える技術も知られている(例えば特許文献１段落〔００１１〕〜〔００２３〕及び特許文献２段落〔００１０〕〜〔００１６〕参照)。
【特許文献１】特許３１４６７７２号公報
【特許文献２】特許２９０６８６９号公報
【発明の開示】
【発明が解決しようとする課題】
【０００７】
しかしながら、図１３に示す方法や、特許文献１、特許文献２に記載された一般的なデジタルデータの並べ替え方法にあっては、別にメモリ空間を必要とするため新たなメモリ装置を増設しなければならない。また図１４に示す方法は、インターレース間隔や画像データ行数によりアルゴリズムを最適化する必要があるし、データのコピー回数がアルゴリズムに依存して多くなる他、複雑な処理を実行しなければならないため並べ替え処理が遅かったりした。
【０００８】
そこで、本発明は、並べ替えに使用するメモリサイズを最小に抑え、データのコピー回数が少なく高速に並び替えを行うことができ、また、インターレースデータのインターレース間隔に関係なく同一アルゴリズムですべてのインターレースデータの並び替えを実現することができるコンピュータプログラム、画像データ処理方法、画像データ処理装置、画像表示方法、画像表示装置、荷電粒子ビーム装置を提供することを目的とする。
【課題を解決するための手段】
【０００９】
請求項１の発明は、ｈ，ｉを正の整数、ｉ＜ｈとして、全ｈ行の画像データ列がインターレース間隔ｉのインターレース方式で格納されたメモリ空間から現在画像データを取り出し、同一のメモリ空間に全ｈ行のノンインターレース方式の画像データに並び替える画像データの変換方法において、着目した現在画像データの行番号を現在行番号ｙとして設定し、並び替えた後の目的画像データの目的行番号を取得する関数ｆ（ｙ）を、
【００１０】
【数１】
2007271988.tif 000003
（ただし０≦ｙ≦ｈ−１）
【００１１】
として算出し、求められた目的行番号ｆ（ｙ）の値を次の現在行番号ｙとして新たな目的行番号ｆ（ｙ）を求め、この処理を繰り返して、目的行番号ｆ（ｙ）が最初に設定した現在行番号ｙに一致するまでこの処理を行い、これらの処理を必要に応じて繰り返し、すべての現在行番号ｙについて目的行番号ｆ（ｙ）を得ることを特徴とする画像データ変換方法である。
【００１２】
請求項２の発明は、ｈ，ｉを正の整数、ｉ＜ｈとして、全ｈ行の画像データ列がインターレース間隔ｉのインターレース方式で格納されたメモリ空間から現在画像データを取り出し、同一のメモリ空間に全ｈ行のノンインターレース方式の画像データに並び替える画像データの変換方法において、着目した現在画像データの行番号を現在行番号ｙとして設定し、並び替えた後の目的画像データの目的行番号を取得する関数ｆ（ｙ）を、
【００１３】
【数２】
2007271988.tif 000004
（ただし０≦ｙ≦ｈ−１）
として算出し、求められた目的行番号ｆ（ｙ）の値を次の現在行番号ｙとして新たな目的行番号ｆ（ｙ）を求め、この処理を繰り返して、目的行番号ｆ（ｙ）が最初に設定した現在行番号ｙに一致するまでこの処理を行い、現在行番号と目的行番号の対を備えた行番号リンクリストを作成し、この行番号リンクリストから選択した一つの画像データ行を前記メモリ空間外に待避し、前記行番号リンクリストを参照して待避した列に該列に配置されるべき画像データを移動する画像データ行の移動処理を行うことを特徴とする画像データ変換方法である。
【００１４】
請求項３の発明は、ｈ，ｉを正の整数、ｉ＜ｈとして、全ｈ行の画像データ列がインターレース間隔ｉのインターレース方式で格納されたメモリ空間から現在画像データを取り出し、同一のメモリ空間に全ｈ行のノンインターレース方式の画像データに並び替える画像データの変換装置において、着目した現在画像データの行番号を現在行番号ｙとして設定し、並び替えた後の目的画像データの目的行番号を取得する関数ｆ（ｙ）を、
【００１５】
【数３】
2007271988.tif 000005
（ただし０≦ｙ≦ｈ−１）
として算出する目的行番号演算手段と、求められた目的行番号ｆ（ｙ）の値を次の現在行番号ｙとして新たな目的行番号ｆ（ｙ）を求め、この処理を繰り返して、目的行番号ｆ（ｙ）が最初に設定した現在行番号ｙに一致するまでこの処理を行い、これらの処理を必要に応じて繰り返し、すべての現在行番号ｙについて目的行番号ｆ（ｙ）を得る処理を行う演算制御手段と、を備えることを特徴とする画像データ変換装置である。
【００１６】
請求項４の発明は、ｈ，ｉを正の整数、ｉ＜ｈとして、全ｈ行の画像データ列がインターレース間隔ｉのインターレース方式で格納されたメモリ空間から現在画像データを取り出し、同一のメモリ空間に全ｈ行のノンインターレース方式の画像データに並び替える画像データの変換装置において、着目した現在画像データの行番号を現在行番号ｙとして設定し、並び替えた後の目的画像データの目的行番号を取得する関数ｆ（ｙ）を、
【００１７】
【数４】
2007271988.tif 000006
（ただし０≦ｙ≦ｈ−１）
として算出する目的番号算出手段と、求められた目的行番号ｆ（ｙ）の値を次の現在行番号ｙとして新たな目的行番号ｆ（ｙ）を求め、この処理を繰り返して、目的行番号ｆ（ｙ）が最初に設定した現在行番号ｙに一致するまでこの処理を行い、現在行番号と目的行番号の対を備えた行番号リンクリストを作成する行番号リンクリスト作成手段と、この行番号リンクリストから選択した一つの画像データ行が待避される前記メモリ空間外に配置された画像待避メモリと、前記行番号リンクリストを参照して待避した列に該列に配置されるべき画像データを順次移動する画像データ行の移動処理を行うデータ移動制御手段と、を備えることを特徴とする画像データ変換装置である。
【００１８】
請求項５の発明は、請求項1又は２の画像データ変換方法を備え、ノンインターレース方式の画像を表示することを特徴とする画像データ表示方法である。
【００１９】
請求項６の発明は、請求項３又は４の画像データ変換装置を備え、ノンインターレース方式の画像を表示することを特徴とする画像データ表示装置である。
【００２０】
請求項７の発明は、請求項1又は２の画像データ変換方法を格納したことを特徴とするコンピュータプログラムである。
【００２１】
請求項８の発明は、請求項３又は４の画像データ表示方法を格納したことを特徴とするコンピュータプログラムである。
【００２２】
請求項９の発明は、電子線源からの電子線を試料の所定範囲で走査して照射する電子光学系と、試料から発生する荷電粒子ビームを受け前記電子線の走査に対応させて試料の画像情報を得る演算処理装置とを備え、前記電子光学系は、荷電粒子ビームを、ｈ，ｉを正の整数、ｉ＜ｈとして、全ｈ行、インターレース間隔ｉで走査するよう制御され、前記演算処理装置には、インターレース方式で得られた画像を現在画像データとして記録する画像メモリを備え、前記画像メモリには、画像データ処理装置が接続され、該画像データ処理装置は、着目した現在画像データの行番号を現在行番号ｙとして設定し、並び替えた後の目的画像データの目的行番号を取得する関数ｆ（ｙ）を、
【００２３】
【数５】
2007271988.tif 000007
（ただし０≦ｙ≦ｈ−１）
として算出する目的行番号演算手段と、求められた目的行番号ｆ（ｙ）の値を次の現在行番号ｙとして新たな目的行番号ｆ（ｙ）を求め、この処理を繰り返して、目的行番号ｆ（ｙ）が最初に設定した現在行番号ｙに一致するまでこの処理を行い、これらの処理を必要に応じて繰り返し、すべての現在行番号ｙについて目的行番号ｆ（ｙ）を得る処理を行う演算制御手段と、求められた目的行番号ｆ（ｙ）の値を次の現在行番号ｙとして新たな目的行番号ｆ（ｙ）を求め、この処理を繰り返して、目的行番号ｆ（ｙ）が最初に設定した現在行番号ｙに一致するまでこの処理を行い、現在行番号と目的行番号の対を備えた行番号リンクリストを作成する行番号リンクリスト作成手段と、この行番号リンクリストから選択した一つの画像データ行が待避される前記メモリ空間外に配置された画像待避メモリと、前記行番号リンクリストを参照して待避した列に該列に配置されるべき画像データを順次移動する画像データ行の移動処理を行うデータ移動制御手段と、前記表示手段に表示させる演算手段を有することを特徴とする荷電粒子ビーム装置である。
【００２４】
請求項１０の発明は、ｈ，ｉを正の整数、ｉ＜ｈとして、全ｈ行のデータ列がインターレース間隔ｉのインターレース方式で格納されたメモリ空間から現在データを取り出し、同一のメモリ空間に全ｈ行のノンインターレース方式のデータに並び替えるデータの変換方法において、着目した現在データの行番号を現在行番号ｙとして設定し、並び替えた後の目的データの目的行番号を取得する関数ｆ（ｙ）を、
【数６】
2007271988.tif 000008
（ただし０≦ｙ≦ｈ−１）
として算出し、
求められた目的行番号ｆ（ｙ）の値を次の現在行番号ｙとして新たな目的行番号ｆ（ｙ）を求め、この処理を繰り返して、目的行番号ｆ（ｙ）が最初に設定した現在行番号ｙに一致するまでこの処理を行い、これらの処理を必要に応じて繰り返し、すべての現在行番号ｙについて目的行番号ｆ（ｙ）を得ることを特徴とするデータ変換方法である。
【００２５】
請求項１１の発明は、ｈ，ｉを正の整数、ｉ＜ｈとして、全ｈ行のデータ列がインターレース間隔ｉのインターレース方式で格納されたメモリ空間から現在データを取り出し、同一のメモリ空間に全ｈ行のノンインターレース方式のデータに並び替えるデータの変換方法において、着目した現在データの行番号を現在行番号ｙとして設定し、並び替えた後の目的データの目的行番号を取得する関数ｆ（ｙ）を、
【数７】
2007271988.tif 000009
（ただし０≦ｙ≦ｈ−１）
として算出し、求められた目的行番号ｆ（ｙ）の値を次の現在行番号ｙとして新たな目的行番号ｆ（ｙ）を求め、この処理を繰り返して、目的行番号ｆ（ｙ）が最初に設定した現在行番号ｙに一致するまでこの処理を行い、これらの処理を必要に応じて繰り返し、すべての現在行番号ｙについて目的行番号ｆ（ｙ）を得ることを特徴とするデータ変換方法である。
【００２６】
請求項１２の発明は、ｈ，ｉを正の整数、ｉ＜ｈとして、全ｈ行のデータ列がインターレース間隔ｉのインターレース方式で格納されたメモリ空間から現在データを取り出し、同一のメモリ空間に全ｈ行のノンインターレース方式のデータに並び替えるデータの変換方法において、  着目した現在データの行番号を現在行番号ｙとして設定し、並び替えた後の目的データの目的行番号を取得する関数ｆ（ｙ）を、
【数８】
2007271988.tif 000010
（ただし０≦ｙ≦ｈ−１）
として算出し、求められた目的行番号ｆ（ｙ）の値を次の現在行番号ｙとして新たな目的行番号ｆ（ｙ）を求め、この処理を繰り返して、目的行番号ｆ（ｙ）が最初に設定した現在行番号ｙに一致するまでこの処理を行い、現在行番号と目的行番号の対を備えた行番号リンクリストを作成し、この行番号リンクリストから選択した一つのデータ行を前記メモリ空間外に待避し、前記行番号リンクリストを参照して待避した列に該列に配置されるべきデータを移動するデータ行の移動処理を行うことを特徴とするデータ変換方法である。
【００２７】
請求項１３の発明は、ｈ，ｉを正の整数、ｉ＜ｈとして、全ｈ行のデータ列がインターレース間隔ｉのインターレース方式で格納されたメモリ空間から現在データを取り出し、同一のメモリ空間に全ｈ行のノンインターレース方式のデータに並び替えるデータの変換装置において、着目した現在データの行番号を現在行番号ｙとして設定し、並び替えた後の目的データの目的行番号を取得する関数ｆ（ｙ）を、
【数９】
2007271988.tif 000011
（ただし０≦ｙ≦ｈ−１）
として算出する目的行番号演算手段と、求められた目的行番号ｆ（ｙ）の値を次の現在行番号ｙとして新たな目的行番号ｆ（ｙ）を求め、この処理を繰り返して、目的行番号ｆ（ｙ）が最初に設定した現在行番号ｙに一致するまでこの処理を行い、これらの処理を必要に応じて繰り返し、すべての現在行番号ｙについて目的行番号ｆ（ｙ）を得る処理を行う演算制御手段と、を備えることを特徴とするデータ変換装置である。
【００２８】
請求項１４の発明は、ｈ，ｉを正の整数、ｉ＜ｈとして、全ｈ行のデータ列がインターレース間隔ｉのインターレース方式で格納されたメモリ空間から現在データを取り出し、同一のメモリ空間に全ｈ行のノンインターレース方式のデータに並び替えるデータの変換装置において、
着目した現在データの行番号を現在行番号ｙとして設定し、並び替えた後の目的データの目的行番号を取得する関数ｆ（ｙ）を、
【数１０】
2007271988.tif 000012
（ただし０≦ｙ≦ｈ−１）
として算出する目的番号算出手段と、
求められた目的行番号ｆ（ｙ）の値を次の現在行番号ｙとして新たな目的行番号ｆ（ｙ）を求め、この処理を繰り返して、目的行番号ｆ（ｙ）が最初に設定した現在行番号ｙに一致するまでこの処理を行い、現在行番号と目的行番号の対を備えた行番号リンクリストを作成する行番号リンクリスト作成手段と、この行番号リンクリストから選択した一つのデータ行が待避される前記メモリ空間外に配置された待避メモリと、前記行番号リンクリストを参照して待避した列に該列に配置されるべきデータを順次移動するデータ行の移動処理を行うデータ移動制御手段と、を備えることを特徴とするデータ変換装置である。
【００２９】
請求項１５の発明は、ｈmodｉ≠０のとき、
ｈ＝ｈ’
【数１１】
2007271988.tif 000013
なるｉで割切れるｈを設定して処理をすることを特徴とする請求項１もしくは２記載の画像データ変換方法、請求項３もしくは４記載の画像データ変換装置、請求項５記載の画像データ表示装置、請求項６記載の画像データ表示装置、請求項７もしくは８記載のコンピュータプログラム、請求項９記載の荷電粒子ビーム装置、請求項１０もしくは１１記載のデータ変換方法、または、請求項１２もしくは１３記載のデータ変換装置である。
【発明の効果】
【００３０】
本発明によれば、インターレース間隔に関係なく同一アルゴリズムで並び替えを可能にすることができる他、メモリを最小限増加させるだけで、インターレースデータを同一メモリ空間内でノンインターレースデータに並び替えることができ、しかも高速にこの並べ替えを行うことができる。
【発明を実施するための最良の形態】
【００３１】
まず本発明に係る画像データ変換方法に用いられる並べ替えの理論について説明する。
インターレースデータを次のように定義する。
インターレース行間隔：ｉ  ただしｉ≧０、
全データ行数：ｈ
とする。
【００３２】
ｈmodｉ＝０（ｈがｉで割り切れる）として説明する。
例えばｉ＝２、ｈ＝８のインターレース方式のデータと目的となるノンインターレース方式のデータは図４に示すようになる。
【００３３】
ここで、格納されているデータのある現在の行番号ｙに格納されているデータの並び替えた後の格納先である目的の行番号取得関数ｆ（ｙ）は次のように表せる。
【００３４】
【数１２】
2007271988.tif 000014
…式１
ただし０≦ｙ≦ｈ−１
【００３５】
ここで、記号
【数１３】
2007271988.tif 000015
は、床関数（フロアー：ｆｌｏｏｒ）を表しある実数に対してその実数以下の最大の整数を表す。
【００３６】
現在格納されているインターレースデータの現在の行番号集合をＳ、並び替える目的の行番号集合をＤとする。
例えばｉ＝２、ｈ＝８のインターレースデータの行番号集合Ｓと本来の行番号集合Ｄは、
Ｓ＝{０，２，４，６，１，３，５，７}
Ｄ＝{０，１，２，３，４，５，６，７}
と表せる。
【００３７】
ここで、本発明で使用する再起関数を下記のように定義する。
【数１４】
2007271988.tif 000016
即ち、Ｋｆ（ｙ）はｙ又はｆ（ｙ）又はＫｆ（ｙ）をとるということである。
【００３８】
この関数の展開例は以下のようになる。
【数１５】
2007271988.tif 000017
【００３９】
いまＳ＝Ｄが成立するとき、次の式
【数１６】
2007271988.tif 000018
… 式2
が成立する。
【００４０】
式１について、この関係が、一般的に成り立つかどうかは不明であるが、発明者は式１、式２が本発明が実施される領域である、ｉ＝１２８まで，ｈ＝１０＾７オーダまで成立することを確認した。
【００４１】
例えば、ｉ＝２、ｈ＝８でこの式を展開すると、
【数１７】
2007271988.tif 000019
となる。
【００４２】
前記式２が成立したことで、下記ａ．ｂ．のことが式１について言えることとなる。
【００４３】
ａ．データの並び替えについて、現在の行番号ｙに格納されているデータは、並び替えた後の目的の行番号格納先ｆ（ｙ）のデータである。
ｂ．データのリンクについて、目的の行番号格納先ｆ（ｙ）を現在の行番号として再度目的の行番号取得関数の引数としてｆ（ｆ（ｙ））として繰り返すと、必ず最初に指定した現在の行番号ｙに戻る。
【００４４】
これにより、式１を用いてすべての現在行番号について、その変換先の行番号を１対１に対応づけたリストを作成できることが判明した。
【００４５】
以下本発明に係る画像変換方法の実施の形態について説明する。図５に示すように、ｉ＝２，ｈ＝８のインターレースデータがあるとする。即ち、現在の行番号（現在画像：インターレース方式）の画像において、ｙが０から７まで並んでいる。それぞれの行にＡＡＡ〜ＨＨＨまでの画像データが格納されている。この画像データは、試料上では、ＡＡＡ，ＢＢＢ，ＣＣＣ，…、ＨＨＨの順に並んでいた。本図では、説明を簡単にするため、予めノンインターレース方式に並べ替える行番号をｆ（ｙ）の欄に示している。
【００４６】
まず、行番号のデータのリンクリスト（行番号リンクリスト）を生成する。図６に示すように、最初に探索開始の行番号を０とし探索するが、ｆ（０）＝０が成立するため(並び替えの必要がない)、次の行番号位置ｆ（１）から探索して行番号リンクリストを生成する。行番号リンクリストは、図６（ａ）に示すようになる。
【００４７】
まず、ｙ＝１を式１に代入すると、
ｆ（１）＝２
が求まり、このｆ（１）＝２をｆ（ｙ）に代入する。
すると、
ｆ（２）＝４
同様に、
ｆ（４）＝１
となり、最初のｙに戻ってくる。
即ち、図６（ｂ）に示すように、１→２→４→１と、行番号が循環するリンクが完成した。
【００４８】
次に、データの並び替えを行う。並び替えはこの例では、一番大きな行番号４から行う。現在行番号ｙの目的のデータを格納する先はｆ（ｙ）であるから、データを壊さないよう、図７に示すように、（１）〜（３）のようにリンクの末尾から逆方向にたどりデータを並び替える。
（１）行番号リンクの一番末尾のデータを退避する。
（２）行番号リンクの末尾からリンクの一つ前の格納してあるデータを複写し続ける
（３）退避したデータを先頭に格納する
【００４９】
最初のデータの並べ替えが終了したら、次の行番号リンク生成位置の探索を行う。探索即ち、次のリンクの生成位置は、図８に示すように、現在の行位置と目的の行番号が不一致を起こす行を探していくことにより行う。
【００５０】
不一致が検出されたら上記行番号リンク生成から繰り返す。図９に示すように、次の不一致が見つからず、最終行番号−１（ｆ（ｈ−１）＝ｈ−１となるため）まで到達したら、図８に示すように、並び替えは終了する。
【００５１】
以下にｈ＝０〜ｈ＝７までの演算を示す。
【００５２】
【数１８】
2007271988.tif 000020
【００５３】
このようにして、すべての並べ替えが終了する。
同様の計算をｉ＝３，ｈ＝１８について行った場合の計算を以下に示し、その行番号リンクリストの作成状態を図１０に示す。
【００５４】
【数１９】
2007271988.tif 000021
【００５５】
図１０では、ｈ＝１８の画像データａ〜ｒをｉ＝３でスキャンしてインターレース型式の取得データを得ている。これを変換データに変換するものである。ｙ＝０のときｆ（０）＝０を処理した後、取得データの計算開始ｙ＝１から上述のようにｆ（ｙ）を計算して、次にこの値をｆ（ｙ）に代入する処理を続けて行いｆ（６）のとき１に戻って循環するリンクが完成している。
【００５６】
このようにして、ｉ＝３、ｈ＝１８の場合でも同様のアルゴリズムで行番号リンクリストを作成できることが分かる。この例では、一回の行番号リンクリストの作成ですべての行がリンクされたが、他の例では必ずしも一回の行番号リンクリストの作成ではすべての行番号について処理できないことがある。この場合には、上述した画像行データの移動を終了した後、未処理行番号を探索して新たな行番号リンクリストを作成し画像データの移動を行い、これらの処理をすべての行番号が終了するまで続ける。
【００５７】
同様に、発明者が検証したｉ＝１２８まで，ｈ＝１０＾７オーダまで同様のアルゴリズムで行番号リンクリストを作成して画像データの変換を行うことができる。
【００５８】
次に、このような手順で行われる本発明に係る画像変換方法と従来の並び替え手法との比較を行う。比較対象としたアルゴリズムは下記のとおり。表中のアルゴリズム名は今回の比較用に命名したものである。表中「別メモリ」は図１３に示した方法、「Ｑソート」は数値集合の並べ替えアルゴリズムで最も早いとされるクイックソート、「本数別」は従来から知られた同一メモリ空間上での並べ替えアルゴリズム（図１４に示した）を示している。
【００５９】
【表１】
2007271988.tif 000022
【００６０】
比較はインターレースデータをグレイスケール２５６階調(1バイト/ピクセル)画像とし、インターレース型式の画像をノンインターレース型式に変換完了するまでに使用したメモリにアクセスしたバイト数と、メモリのトータル使用量で行った。
【００６１】
まず、メモリにアクセスしたバイト数についてみる。表２と図１１とにその結果を示した。メモリにアクセスする行為は、ＣＰＵから見ると比較的重い処理に当たり、そのアクセスのサイズが増えれば速度も比例して遅くなる。そのため、アルゴリズム別に実装し、画像サイズとメモリにアクセスしたバイト数を測定した。「今回」に記載の「本数」はインターレース間隔によりメモリにアクセスする量が変化するため２，４，８，１６，３２本について記載した。尚、「Ｑソート」アルゴリズムは、どのアルゴリズムよりもおおよそ３倍メモリアクセス回数が多いため、グラフには記載していない。
【００６２】
【表２】
2007271988.tif 000023
【００６３】
この結果から、「別メモリ」が最も速いアルゴリズムであり、「今回」本発明に係る方法は、それとほぼ匹敵する速度となり、同一画像メモリ空間で並び替えるアルゴリズムでは最速のものの一つであることが分かった。
【００６４】
次に、メモリ使用量についてみる。表３と図１２にその結果を示した。「本数別」に記載の本数はインターレース間隔によりメモリにアクセスする量が変化するため、２，４，８，１６，３２本について行った。
【００６５】
【表３】
2007271988.tif 000024
【００６６】
変換に必要とされるメモリサイズは、「別メモリ」アルゴリズムが他のアルゴリズムより多い。これは、「別メモリ」アルゴリズムがデータと同一サイズの別領域を必要とするためである。また、本発明の画像データ処理方法である「今回」は、最も使用メモリの小さい「Ｑソート」アルゴリズムとほぼ同等のメモリサイズを実現している。さらに、「本数別」アルゴリズムと比較すると最大で８７０ＫＢほど差が開く結果になった。また、本発明に係る画像データの処理方法はどのようなインターレース間隔においても使用メモリサイズが変化しない。
【００６７】
以上により、本願発明に係る画像データ変換方法によれば、他の変換アルゴリズムに比して、並べ替えに使用するメモリサイズを最小とでき、また、データのコピー回数を少ないものとでき、さらに高速に並び替えを行うことができることが分かる。また、インターレースデータのインターレース間隔に関係なく同一アルゴリズムですべてのインターレースデータの並び替えを実現することができる
【００６８】
次に本発明の実施の形態に係る荷電粒子ビーム装置について説明する。本実施の形態に係る荷電粒子ビーム装置は上記画像データの変換装置を採用している。図１は本発明の実施の形態例に係る電子顕微鏡を示す模式図である。
【００６９】
本例に係る荷電粒子ビーム装置１０は、鏡筒２０、試料室３０及び演算処理装置４１及び画像表示装置４２を備える制御手段４０を備えてなる。鏡筒２０内には、電子線を発生する電子線源２１、電子線源２１からの電子線を所定の方向に偏向する２台の偏向器２２，２２、図示しない収束レンズ、及び反射電子線、二次電子線、荷電粒子を検出する検出器２３を備える。また、試料室３０には、試料台が配置され試料３１が載置されている。
【００７０】
制御手段４０は、偏向器２２，２２での電子線の偏向状態を制御する偏向制御装置４４、検出器２３からの信号と偏向制御装置４４からの走査信号とに基づいて画像信号を作成する演算処理装置４１、ＣＲＴやＬＣＤからなり演算処理装置４１からの信号に基づいて観察像を表示する画像表示装置４２を備えている。本例では、演算処理装置４１は、図示しないＣＰＵ、ＲＯＭ，ＲＡＭを備え、予め格納されたプログラムに基づいて、前記基板電流の信号から観察画像を獲得して、画像メモリ４３に格納する。また、偏向制御装置４４は、偏向器２２，２２を制御して、電子線の走査範囲、電子線の走査方向を設定することができるものである。
【００７１】
本例において、上述したように、画像メモリ４３には画像データ処理装置５０が接続されており、画像データ処理装置５０は、画像メモリ４３に取得したインターレース型式の画像データを格納するとともに、画像データ処理装置５０により変換されたノンインターレース型式の画像データを格納する。
【００７２】
以下本例に係る荷電粒子ビーム装置１０の画像データ処理装置５０について説明する。図２は図１に示した画像処理装置の構成を示すブロック図である。本例では、画像データ処理装置５０は、装置全体を制御する演算制御部５１と、前記式１を実行する演算実行部５２と、作成した行番号リンクリストを格納する行番号リンクリスト５３と、画像データ書き換え時に１行分の画像データを待避させる画像一行メモリ５４とを備えてなる。
【００７３】
演算制御部５１は、図示しないＣＰＵ、ＲＯＭ，ＲＡＭを備え、予め格納されたプログラムに基づいて画像メモリ４３に格納されたインターレース型式の画像データをノンインターレース型式の画像データに書き換える。以下画像データ処理装置５０の動作について説明する。
【００７４】
図３は図１に示した画像データ処理装置５０の作動を示すフローチャートである。最初に探索開始の行番号を０とし探索するが、ｆ（０）＝０が成立するため(並び替えの必要がない)、次の行番号位置ｆ（１）から探索して行番号リンクリストを生成する。次に、演算制御部５１は、初回の書き換えを開始するため現在行番号を「１」とする（Ｓ１）。次に演算実行部５２により、目的行番号ｆ（１）を算出して（Ｓ２）、行番号リンクリスト５３に、（１，ｆ（１））の対を格納し、ｎ＝ｆ（１）とする（Ｓ３）。次に、演算実行部５２で現在行番号をｎとして次の目的行番号ｆ（ｎ）＝ｍを算出する（Ｓ４）。
【００７５】
そして、行番号（ｎ，ｍ）の対を格納する。Ｓ４，Ｓ５の処理をｍ＝１になるまで、即ちリンクが循環するまで行い（Ｓ６、Ｓ７）、第１回の行番号リンクリストを作成する。
【００７６】
次にこの作成した第１回の行番号リンクリスト５３に基づいて行番号の末尾の画像データを画像一行メモリ５４に待避して、図７に示したように、順次画像データの移動を行う（Ｓ８）。
【００７７】
この処理が終了すると、図８に示したように、次の行番号を探索し（Ｓ９）、次の業界紙番号がなければ処理を終了する。次の行番号を発見したときには、次の開始行番号ｐを決定し（Ｓ１０）次に演算実行部５２により、目的行番号ｆ（ｐ）＝ｎを算出して（Ｓ１１）、行番号リンクリスト５３に、（ｐ，ｎ）の対を格納する（Ｓ１２）。次に、演算実行部５２で現在行番号をｎとして次の目的行番号ｆ（ｎ）＝ｍを算出する（Ｓ１４）。
【００７８】
Ｓ１３，Ｓ１４の処理をｍ＝ｐになるまで、即ちリンクが循環するまで行い（Ｓ１５、Ｓ１６）、今回の行番号リンクリストを作成する。
【００７９】
次にこの作成したこの回の行番号リンクリスト５３に基づいて行番号の末尾の画像データを画像一行メモリ５４に待避して、図７に示したように、順次画像データの移動を行う。
【００８０】
Ｓ９〜Ｓ１７の処理をすべての行番号について行った後、一連の画像データ処理は終了する（Ｓ１８）。
【００８１】
以上説明したように、本発明に係る荷電粒子ビーム装置１０によれば、演算処理装置４１に配置された画像メモリ４３の他に画像データ処理装置５０を設け、メモリとして行番号リンクリスト５３、画像一行メモリ５４を追加するだけで、迅速なインターレース型式からノンインターレース型式への画像データ変換を行うことができる。
【００８２】
次に、ｈmodｉ≠０のときについて説明する。
この場合には、
ｈ＝ｈ’
【数２０】
2007271988.tif 000025
なるｉで割切れるｈを設定して処理をする。
即ち、処理において不足するデータをダミーの行番号およびデータを用意して並び替えることにより処理を行うことができる。
例えば
ｈ＝１０，ｉ＝３
のとき
Ｓ＝｛０，３，６，９，１，４，７，１０，２，５｝
ｈ’＝１０
ｈ＝４×３＝１２
の場合においては、
増えた二つ分の不足行番号１０，１１に
ｆ（１０）＝８
ｆ（１１）＝１１
Ｓ＝｛０，３，６，９，１，４，７，１０，２，５，８，１１｝
として、上述した変換を行うことができる。
【００８３】
ここで、記号
【数２１】
2007271988.tif 000026
は、天井関数（セイル：ｃｅｉｌ）を表しある実数に対してその実数を下回らない最小の整数を表す。
【００８４】
尚上記例では、変換するデータとして画像データを例にして説明したが、これは画像データに限らずどのようなデータであっても良い。
【図面の簡単な説明】
【００８５】
【図１】本発明の実施の形態例に係る電子顕微鏡を示す模式図である。
【図２】図１に示した画像データ処理装置の構成を示すブロック図である。
【図３】図２に示した画像データ処理装置の作動を示すフローチャートである。
【図４】インターレースデータと、ノンインターレースデータとを示す模式図である。
【図５】インターレースデータを示す模式図である。
【図６】行番号リンクリストの生成を示す模式図である。
【図７】画像データの並び替えを示す模式図である。
【図８】次の行番号リンクリスト作成のための行番号探索を示す模式図である。
【図９】並べ替えの終了状態を示す模式図である。
【図１０】ｉ＝３，ｈ＝１８の場合の行番号リンクリスト作成を示す模式図である。
【図１１】従来例との比較を示す画像サイズと、メモリにアクセスしたバイト数との関係を示すグラフである。
【図１２】従来例との比較を示す画像サイズと、使用メモリサイズとの関係を示すグラフである。
【図１３】従来の画像変換方法を示す模式図である。
【図１４】従来の画像変換方法を示す模式図である。
【符号の説明】
【００８６】
１０・・・荷電粒子ビーム装置
２０・・・鏡筒
２１・・・電子線源
２２・・・偏向器
２３・・・検出器
３０・・・試料室
３１・・・試料
４０・・・制御手段
４１・・・演算処理装置
４２・・・画像表示装置
４３・・・画像メモリ
４４・・・偏向制御装置
５０・・・画像データ処理装置
５１・・・演算制御部
５２・・・演算実行部
５３・・・行番号リンクリスト
５４・・・画像一行メモリ
【図１】
2007271988.tif 000039
【図２】
2007271988.tif 000040
【図３】
2007271988.tif 000041
【図４】
2007271988.tif 000042
【図５】
2007271988.tif 000043
【図６】
2007271988.tif 000044
【図７】
2007271988.tif 000045
【図８】
2007271988.tif 000046
【図９】
2007271988.tif 000047
【図１０】
2007271988.tif 000048
【図１１】
2007271988.tif 000049
【図１２】
2007271988.tif 000050
【図１３】
2007271988.tif 000051
【図１４】
2007271988.tif 000052