(57)【要約】      （修正有）【課題】少ない画素アクセス量でプロセッサの並列可能数を有効に使用して画像変換を行う装置を提供する。【解決手段】画像変換装置３は、入力画像内の行単位の画素値を複数の区間に分割し、各行の区間毎にプロセッサが並列実行可能なスレッドを割り当てる割り当て部３１と、各行で割り当てられたスレッド毎に、入力画像の所定数値の画素からの距離を各行の区間において算出し、距離を示す値を格納した第１距離画像を生成する行スキャン部３２と、各行で割り当てられたスレッド毎に、各行の他の区間の所定数値の画素からの距離を示す第１境界値を、各行の他の区間における第１境界値の算出結果を用いて算出する行リダクション部３５と、各行で割り当てられたスレッド毎に、第１距離画像内の値と第１境界値に基づいて算出した所定数値の画素からの距離を示す値とのうち小さい値で第１距離画像内の値を更新した第２距離画像を出力する行方向合算部３６とを備える。【選択図】図１０
2020091799.tif 000002
【特許請求の範囲】
【請求項１】
入力画像内の行単位の画素値を複数の区間に分割し、各行の前記区間毎に、プロセッサが並列実行可能なスレッドを割り当てる第１割り当て部と、
前記各行で割り当てられたスレッド毎に、前記入力画像の所定数値の画素からの距離を前記各行の区間において算出し、前記距離を示す値を格納した第１距離画像を生成する第１生成部と、
前記各行で割り当てられたスレッド毎に、前記各行の他の区間の所定数値の画素からの距離を示す第１境界値を、前記各行の他の区間における前記第１境界値の算出結果を用いて算出する第１算出部と、
前記各行で割り当てられたスレッド毎に、前記第１距離画像内の値と、前記第１境界値に基づいて算出した前記所定数値の画素からの距離を示す値とのうち小さい値で前記第１距離画像内の値を更新した第２距離画像を出力する第１更新部と、
前記第２距離画像内の列単位の画素値を複数区間に分割し、各列の前記区間毎に前記プロセッサが並列実行可能なスレッドを割り当てる第２割り当て部と、
前記各列で割り当てられたスレッド毎に、前記第２距離画像における画素値に基づいて、前記所定数値の画素からの距離を示す値を前記各列の区間において算出し、算出した値を格納した第３距離画像を生成する第２生成部と、
前記各列で割り当てられたスレッド毎に、各列の他の区間の所定数値の画素からの距離を示す第２境界値を、前記各列の他の区間における前記第２境界値の算出結果を用いて算出する第２算出部と、
前記各列で割り当てられたスレッド毎に、前記第３距離画像内の値と、前記第２境界値に基づいて算出した前記所定数値の画素からの距離を示す値とのうち小さい値で前記第３距離画像内の値を更新する第２更新部と、
を備えることを特徴とする画像変換装置。
【請求項２】
前記第１算出部は、前記各行の他の区間の第１境界値に他の区間から行内の所定区間までの距離を加算した値の最小値と、前記行内の所定区間の端の画素値に１を加算した値とのうち小さい値を、前記所定区間の第１境界値として格納し、
前記第２算出部は、前記各列の他の区間の第２境界値に他の区間から列内の所定区間までの距離を加算した値の最小値と、前記列内の所定区間の端の画素値に１を加算した値とのうち小さい値を、前記列内の所定区間の新たな第２境界値として格納する、
ことを特徴とする請求項１記載の画像変換装置。
【請求項３】
前記画像変換装置のプロセッサにおいて、同じグループ内の複数のスレッドが同一カウンタを共有可能であり、１グループ内に所定数のスレッドが割り当て可能であり、
前記第１割り当て部は、前記入力画像内の行単位の画素値を、前記所定数の区間に分割し、前記各行の区間毎にスレッドを割り当て、
前記第２割り当て部は、前記第２距離画像内の列単位の画素値を前記所定数の区間に分割し、前記各列の区間毎にスレッドを割り当てる
ことを特徴とする請求項１または請求項２記載の画像変換装置。
【請求項４】
前記画像変換装置のプロセッサにおいて、スレッドが同じグループ内の他のスレッドの変数をレジスタ経由で参照可能であり、１グループ内に所定数のスレッドが割り当て可能であり、
前記第１割り当て部は、前記入力画像内の行単位の画素値を、前記所定数の区間に分割し、前記各行の区間毎にスレッドを割り当て、
前記第２割り当て部は、前記第２距離画像内の列単位の画素値を前記所定数の区間に分割し、前記各行の区間毎にスレッドを割り当てる
ことを特徴とする請求項１または請求項２記載の画像変換装置。
【請求項５】
入力画像内の行単位の画素値を複数の区間に分割し、各行の前記区間毎に、プロセッサが並列実行可能なスレッドを割り当て、
前記各行で割り当てられたスレッド毎に、前記入力画像の所定数値の画素からの距離を前記各行の区間において算出し、前記距離を示す値を格納した第１距離画像を生成し、
前記各行で割り当てられたスレッド毎に、前記各行の他の区間の所定数値の画素からの距離を示す第１境界値を、前記各行の他の区間における前記第１境界値の算出結果を用いて算出し、
前記各行で割り当てられたスレッド毎に、前記第１距離画像内の値と、前記第１境界値に基づいて算出した前記所定数値の画素からの距離を示す値とのうち小さい値で前記第１距離画像内の値を更新した第２距離画像を出力し、
前記第２距離画像内の列単位の画素値を複数区間に分割し、各列の前記区間毎に前記プロセッサが並列実行可能なスレッドを割り当て、
前記各列で割り当てられたスレッド毎に、前記第２距離画像における画素値に基づいて、前記所定数値の画素からの距離を示す値を前記各列の区間において算出し、算出した値を格納した第３距離画像を生成し、
前記各列で割り当てられたスレッド毎に、各列の他の区間の所定数値の画素からの距離を示す第２境界値を、前記各列の他の区間における前記第２境界値の算出結果を用いて算出し、
前記各列で割り当てられたスレッド毎に、前記第３距離画像内の値と、前記第２境界値に基づいて算出した前記所定数値の画素からの距離を示す値とのうち小さい値で前記第３距離画像内の値を更新する
処理をコンピュータに実行させるための画像変換プログラム。
【請求項６】
コンピュータが、
入力画像内の行単位の画素値を複数の区間に分割し、各行の前記区間毎に、プロセッサが並列実行可能なスレッドを割り当て、
前記各行で割り当てられたスレッド毎に、前記入力画像の所定数値の画素からの距離を前記各行の区間において算出し、前記距離を示す値を格納した第１距離画像を生成し、
前記各行で割り当てられたスレッド毎に、前記各行の他の区間の所定数値の画素からの距離を示す第１境界値を、前記各行の他の区間における前記第１境界値の算出結果を用いて算出し、
前記各行で割り当てられたスレッド毎に、前記第１距離画像内の値と、前記第１境界値に基づいて算出した前記所定数値の画素からの距離を示す値とのうち小さい値で前記第１距離画像内の値を更新した第２距離画像を出力し、
前記第２距離画像内の列単位の画素値を複数区間に分割し、各列の前記区間毎に前記プロセッサが並列実行可能なスレッドを割り当て、
前記各列で割り当てられたスレッド毎に、前記第２距離画像における画素値に基づいて、前記所定数値の画素からの距離を示す値を前記各列の区間において算出し、算出した値を格納した第３距離画像を生成し、
前記各列で割り当てられたスレッド毎に、各列の他の区間の所定数値の画素からの距離を示す第２境界値を、前記各列の他の区間における前記第２境界値の算出結果を用いて算出し、
前記各列で割り当てられたスレッド毎に、前記第３距離画像内の値と、前記第２境界値に基づいて算出した前記所定数値の画素からの距離を示す値とのうち小さい値で前記第３距離画像内の値を更新する
処理を実行することを特徴とする画像変換方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、画像変換装置、画像変換プログラムおよび画像変換方法に関する。
【背景技術】
【０００２】
特定の部分のみを表示し、特定の部分以外の部分を表示しないようにするマスク処理を行うことにより、例えば、特定の部分の画素に１を格納し、特定の部分以外の部分の画素に０を格納した２値画像が生成される。以下、０が格納された画素を０画素と称する。そして、２値画像の各画素から最も近い０画素までの距離を算出し、算出した距離を格納した距離画像を生成する技術が用いられている。生成された距離画像は、例えば、画像内の領域の分割に用いられる。
【０００３】
関連する技術として、２値画像を距離変換して距離画像を作成し、距離画像を用いて２値画像に対してクロージング処理を実行し、クロージング処理の前後の画像の差分からボイドを抽出する技術が提案されている（例えば、特許文献１を参照）。
【０００４】
また、関連する技術として、物体の形状を表す複数の形状データを統合する画像処理装置が提案されている（例えば、特許文献２を参照）。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開２０１５−６８７５５号公報
【特許文献２】特開２００９−３２１２２号公報
【発明の概要】
【発明が解決しようとする課題】
【０００６】
２値画像を距離画像に変換する方法として、２値画像の各行および各列の画素をスキャンして０画素からの距離を決定する方法が考えられる。この方法を用いた場合、各行および各列にスレッドを割り当てると、並列数は、２値画像の行数または列数となる。よって、並列可能数が大きいプロセッサ（例えば、Graphics Processing Unit（ＧＰＵ））を用いた場合に並列可能数を有効に使えない可能性がある。
【０００７】
また、各画素にスレッドを割り当てて各行および各列をスキャンし、０画素からの距離を決定する方法が考えられる。この方法を用いた場合、各画素に対して独立したスレッドで並列実行が行われるため、並列可能数を有効に使える。しかし、一つの画素に対して複数のスレッドでアクセスするため、画素に対するアクセス量が多くなる。
【０００８】
１つの側面として、本発明は、少ない画素アクセス量でプロセッサの並列可能数を有効に使用して画像変換を行うことを目的とする。
【課題を解決するための手段】
【０００９】
１つの態様では、画像変換装置は、入力画像内の行単位の画素値を複数の区間に分割し、各行の前記区間毎に、プロセッサが並列実行可能なスレッドを割り当てる第１割り当て部と、前記各行で割り当てられたスレッド毎に、前記入力画像の所定数値の画素からの距離を前記各行の区間において算出し、前記距離を示す値を格納した第１距離画像を生成する第１生成部と、前記各行で割り当てられたスレッド毎に、前記各行の他の区間の所定数値の画素からの距離を示す第１境界値を、前記各行の他の区間における前記第１境界値の算出結果を用いて算出する第１算出部と、前記各行で割り当てられたスレッド毎に、前記第１距離画像内の値と、前記第１境界値に基づいて算出した前記所定数値の画素からの距離を示す値とのうち小さい値で前記第１距離画像内の値を更新した第２距離画像を出力する第１更新部と、前記第２距離画像内の列単位の画素値を複数区間に分割し、各列の前記区間毎に前記プロセッサが並列実行可能なスレッドを割り当てる第２割り当て部と、前記各列で割り当てられたスレッド毎に、前記第２距離画像における画素値に基づいて、前記所定数値の画素からの距離を示す値を前記各列の区間において算出し、算出した値を格納した第３距離画像を生成する第２生成部と、前記各列で割り当てられたスレッド毎に、各列の他の区間の所定数値の画素からの距離を示す第２境界値を、前記各列の他の区間における前記第２境界値の算出結果を用いて算出する第２算出部と、前記各列で割り当てられたスレッド毎に、前記第３距離画像内の値と、前記第２境界値に基づいて算出した前記所定数値の画素からの距離を示す値とのうち小さい値で前記第３距離画像内の値を更新する第２更新部と、を備える。
【発明の効果】
【００１０】
１つの側面によれば、少ない画素アクセス量でプロセッサの並列可能数を有効に使用して画像変換を行うことができる。
【図面の簡単な説明】
【００１１】
【図１】２次元上でのマンハッタン距離の例を示す図である。
【図２】マスク処理が行われた入力画像を距離画像に変換する例を示す図である。
【図３】領域分割の一例を示す図である。
【図４】第１の関連技術における画像変換装置を示す図である。
【図５】行Ｆｏｒｗａｒｄスキャン部の処理の一例を示す図である。
【図６】行Ｂａｃｋｗａｒｄスキャン部の処理の一例を示す図である。
【図７】第２の関連技術における画像変換装置を示す図である。
【図８】第２の関連技術における画像変換処理の概要を示す図である。
【図９】第１の関連技術および第２の関連技術における並列数を示す図である。
【図１０】実施形態における画像変換装置の機能構成の一例を示す図である。
【図１１】行方向スキャン処理の一例を示す図である。
【図１２】行方向リダクション部における右境界値の算出例を示す図である。
【図１３】行方向リダクション部における左境界値の算出例を示す図である。
【図１４】行方向リダクション部の処理の一例を示す図（その１）である。
【図１５】行方向リダクション部の処理の一例を示す図（その２）である。
【図１６】行方向合算部の処理の一例を示す図である。
【図１７】列Ｆｏｒｗａｒｄスキャン処理の一例を示す図である。
【図１８】列Ｂａｃｋｗａｒｄスキャン処理の一例を示す図である。
【図１９】実施形態の行方向の処理の一例を示すフローチャートである。
【図２０】実施形態の列方向の処理の一例を示すフローチャートである。
【図２１】第１の関連技術、第２の関連技術および実施形態における並列数を示す図である。
【図２２】画像変換装置のハードウェア構成の一例を示す図である。
【発明を実施するための形態】
【００１２】
以下、実施形態の画像変換処理の関連技術について説明する。２値画像の各画素から最も近い０画素までの距離を算出し、算出した距離を格納した距離画像を生成する際に、例えば、マンハッタン距離が用いられる。例えば、ｎ次元における点ｐ（ｐ１，ｐ２，・・・ｐｎ）と点ｑ（ｑ１，ｑ２，・・・ｑｎ）との間のマンハッタン距離ｄ（ｐ，ｑ）は、以下の式（１）により算出される。
【００１３】
【数１】
2020091799.tif 000003
【００１４】
また、２次元における点ｐ（ｐ１，ｐ２）と点ｑ（ｑ１，ｑ２）との間のマンハッタン距離は、以下の式（２）により算出される。
【００１５】
【数２】
2020091799.tif 000004
【００１６】
図１は、２次元上でのマンハッタン距離の例を示す図である。図１（ａ）において、点Ａ（１，３）と点Ｂ（１，１）との距離は、上記式（２）に基づいて算出すると２となる。また、図１（ｂ）において、点Ｃ（３，３）と点Ｄ（１，１）との距離は、上記式（２）に基づいて算出すると４となる。
【００１７】
なお、以下の説明において、画素間の距離には、上述のマンハッタン距離が用いられる。以下の説明において、マンハッタン距離を単に「距離」と記載することがある。
【００１８】
図２は、マスク処理が行われた入力画像を距離画像に変換する例を示す図である。図２に示す入力画像は、画像の画素毎に、前景の画素に１が格納され、背景の画素に０が格納された２値画像である。図２では、所定画素から最も近い０画素への距離を、その所定画素の画素値とする画像変換処理を行うことにより距離画像が生成されている。
【００１９】
図３は、領域分割の一例を示す図である。図３に示す例では、入力画像として、領域Ａと領域Ｂを含むカラー画像が用いられる。ただし、カラー画像において領域Ａと領域Ｂとの境界が明確でないとする。
【００２０】
ＡとＢの領域分割をする場合、まず、カラー画像がグレースケール画像に変換され、グレースケール画像が２値画像（１）に変換される。そして、２値画像（１）は、各画素から最も近い０画素への距離を格納した距離画像に変換される。そして、距離画像は、例えば、所定値以上の数値が格納された画素を黒とし、所定値未満の数値が格納された画素を白とした２値画像（２）に変換される。そして、例えば、２値画像（２）の各画素に対してラベリングが行われ、Ｗａｔｅｒｓｈｅｄアルゴリズムを適用することにより、領域Ａと領域Ｂとの境界が明確になる。すなわち、領域Ａと領域Ｂとが分割された分割後画像が生成される。
【００２１】
次に、実施形態における画像変換処理の比較対象である関連技術について説明する。なお、以下に説明する関連技術は、図３に示す画像変換のうち、２値画像（１）から距離画像への画像変換に関する技術である。
【００２２】
図４は、第１の関連技術における画像変換装置１を示す図である。画像変換装置１は、第１行Ｆｏｒｗａｒｄスキャン部１１と、第１行Ｂａｃｋｗａｒｄスキャン部１２と、第１列Ｆｏｒｗａｒｄスキャン部１３と、第１列Ｂａｃｋｗａｒｄスキャン部１４とを含む。なお、以下の説明において、画像の左端から右端への方向をＦｏｒｗａｒｄとし、画像の右端から左端への方向をＢａｃｋｗａｒｄとする。
【００２３】
第１行Ｆｏｒｗａｒｄスキャン部１１は、入力画像（２値画像）の各行に対してＦｏｒｗａｒｄスキャンを行い、スキャンの対象画素から最も近い０画素への距離を、その対象画素の画素値とした距離画像を生成する。そして、第１行Ｆｏｒｗａｒｄスキャン部１１は、距離画像を第１行Ｂａｃｋｗａｒｄスキャン部１２に出力する。
【００２４】
第１行Ｂａｃｋｗａｒｄスキャン部１２は、第１行Ｆｏｒｗａｒｄスキャン部１１から取得した距離画像の各行に対してＢａｃｋｗａｒｄスキャンを行う。そして、第１行Ｂａｃｋｗａｒｄスキャン部１２は、スキャンの対象画素の直前にスキャンした画素の画素値に１を加算した値と第１行Ｆｏｒｗａｒｄスキャン部１１から取得した距離画像の画素値とのうち小さい値を、新たな距離画像の画素値として格納する。そして、第１行Ｂａｃｋｗａｒｄスキャン部１２は、新たな距離画像を第１列Ｆｏｒｗａｒｄスキャン部１３に出力する。
【００２５】
第１行Ｆｏｒｗａｒｄスキャン部１１および第１行Ｂａｃｋｗａｒｄスキャン部１２は、各行の処理を並列で実行する。
【００２６】
第１列Ｆｏｒｗａｒｄスキャン部１３は、第１行Ｂａｃｋｗａｒｄスキャン部１２から取得した距離画像の各列に対してＦｏｒｗａｒｄスキャンを行う。第１列Ｆｏｒｗａｒｄスキャン部１３は、スキャンの対象画素の直前にスキャンした画素の画素値に１を加算した値と、第１行Ｂａｃｋｗａｒｄスキャン部１２から取得した距離画像の画素値とのうち小さい値を、新たな距離画像の画素値として格納する。そして、第１列Ｆｏｒｗａｒｄスキャン部１３は、新たな距離画像を第１列Ｂａｃｋｗａｒｄスキャン部１４に出力する。
【００２７】
第１列Ｂａｃｋｗａｒｄスキャン部１４は、第１列Ｆｏｒｗａｒｄスキャン部１３から取得した距離画像の各列に対してＢａｃｋｗａｒｄスキャンを行う。第１列Ｂａｃｋｗａｒｄスキャン部１４は、スキャンの対象画素の直前にスキャンした画素の画素値に１を加算した値と、第１列Ｆｏｒｗａｒｄスキャン部１３から取得した距離画像の画素値とのうち小さい値を、新たな距離画像の画素値として格納する。そして、第１列Ｂａｃｋｗａｒｄスキャン部１４は、新たな距離画像を、入力画像に基づく距離画像として出力する。
【００２８】
第１列Ｆｏｒｗａｒｄスキャン部１３および第１列Ｂａｃｋｗａｒｄスキャン部１４は、各列の処理を並列に実行する。
【００２９】
図５は、第１行Ｆｏｒｗａｒｄスキャン部１１の処理の一例を示す図である。第１行Ｆｏｒｗａｒｄスキャン部１１は、入力画像の各行に対してＦｏｒｗａｒｄスキャンを行い、各画素から最も近い０画素への距離を画素値とした距離画像を生成する。第１行Ｆｏｒｗａｒｄスキャン部１１は、入力画像の左端から１画素ずつスキャンを行う。図５では、入力画像の所定の行を距離画像に変換する例を示している。
【００３０】
第１行Ｆｏｒｗａｒｄスキャン部１１は、所定の行の列番号０において、前の列が存在しないため、距離画像の画素値として不定値（∞）を設定する。第１行Ｆｏｒｗａｒｄスキャン部１１は、所定の行の列番号１において、入力画像のスキャン対象画素の画素値が０であるため、距離画像の画素値として０を格納する。第１行Ｆｏｒｗａｒｄスキャン部１１は、所定の行の列番号２において、入力画像のスキャン対象画素の画素値が１（０以外）であるため、第１列に存在する０画素からの距離である１を距離画像の画素値として格納する。第１行Ｆｏｒｗａｒｄスキャン部１１は、所定の行の列番号３において、入力画像のスキャン対象画素の画素値が１（０以外）であるため、第１列に存在する０画素からの距離である２を距離画像の画素値として設定する。
【００３１】
第１行Ｆｏｒｗａｒｄスキャン部１１は、同様の処理を最終列まで続け、全ての行に対して同様の処理を行うことにより、入力画像を距離画像に変換する。
【００３２】
図６は、第１行Ｂａｃｋｗａｒｄスキャン部１２の処理の一例を示す図である。第１行Ｂａｃｋｗａｒｄスキャン部１２は、スキャンの対象画素の直前にスキャンした画素の画素値に１を加算した値と第１行Ｆｏｒｗａｒｄスキャン部１１から取得した距離画像の画素値とのうち小さい値を、新たな距離画像の画素値として格納する。第１行Ｂａｃｋｗａｒｄスキャン部１２は、入力画像の右端から１画素ずつスキャンを行う。
【００３３】
第１行Ｂａｃｋｗａｒｄスキャン部１２は、列番号７において、スキャン対象画素の直前の画素が存在しないため、距離画像の画素値を変更しない。第１行Ｂａｃｋｗａｒｄスキャン部１２は、列番号５において、距離画像（更新前）の画素値（４）と、スキャン対象画素の直前の画素値（０）に１を加算した値（１）とのうち小さい値である１を、距離画像（更新後）に格納する。第１行Ｂａｃｋｗａｒｄスキャン部１２は、列番号４において、距離画像（更新前）の画素値（３）と、スキャン対象画素の直前の画素値（１）に１を加算した値（２）とのうち小さい値である２を、距離画像（更新後）に格納する。
【００３４】
第１行Ｂａｃｋｗａｒｄスキャン部１２は、同様の処理を最終列まで続けることにより、距離画像のうち所定の行の画素値を更新する。第１行Ｂａｃｋｗａｒｄスキャン部１２は、全ての行に対して同様の処理を行うことにより、距離画像を更新する。
【００３５】
なお、第１列Ｆｏｒｗａｒｄスキャン部１３および第１列Ｂａｃｋｗａｒｄスキャン部１４の処理は、第１行Ｂａｃｋｗａｒｄスキャン部１２の処理と同様であるため、詳細な説明を省略する。
【００３６】
以上の処理により、画像変換装置１は、入力画像（２値画像）を、距離画像に変換する。距離画像は、図２の例に示すように、対象画素から最も近い０画素への距離をその対象画素の画素値とした画像である。
【００３７】
第１の関連技術では、第１行Ｆｏｒｗａｒｄスキャン部１１および第１行Ｂａｃｋｗａｒｄスキャン部１２における並列処理数は、入力画像の行数である。第１列Ｆｏｒｗａｒｄスキャン部１３および第１列Ｂａｃｋｗａｒｄスキャン部１４の並列処理数は、入力画像の列数である。よって、第１の関連技術による画像変換処理では、並列可能数が大きいＧＰＵを用いた場合に、並列処理数がＧＰＵの並列可能数より少なくなり、並列可能数を有効に使えない可能性がある。
【００３８】
図７は、第２の関連技術における画像変換装置２を示す図である。画像変換装置２は、第２行Ｆｏｒｗａｒｄスキャン部２１と、第２行Ｂａｃｋｗａｒｄスキャン部２２と、第２列Ｆｏｒｗａｒｄスキャン部２３と、第２列Ｂａｃｋｗａｒｄスキャン部２４とを含む。画像変換装置２の処理は、画素毎にスレッドを割り当ててスキャンを行う点で第１の関連技術における処理と異なる。
【００３９】
第２行Ｆｏｒｗａｒｄスキャン部２１は、入力画像を行毎にシェアードメモリにコピーし、画素毎にＦｏｒｗａｒｄスキャンを行う。第２行Ｆｏｒｗａｒｄスキャン部２１は、所定画素からスキャンして最初の０画素が見つかった場合、移動数をその所定画素の画素値として格納する。第２行Ｆｏｒｗａｒｄスキャン部２１は、入力画像の全ての画素に対応する画素値を距離画像に格納した場合、距離画像を第２行Ｂａｃｋｗａｒｄスキャン部２２に出力する。
【００４０】
第２行Ｂａｃｋｗａｒｄスキャン部２２は、第２行Ｆｏｒｗａｒｄスキャン部２１から取得した距離画像を行毎にシェアードメモリにコピーし、画素毎にＢａｃｋｗａｒｄスキャンを行う。第２行Ｂａｃｋｗａｒｄスキャン部２２は、所定画素からスキャンして最初の０画素が見つかった場合、その所定画素からの移動数と第２行Ｆｏｒｗａｒｄスキャン部２１から取得した距離画像の画素値とのうち小さい値を更新後の距離画像の画素値として格納する。第２行Ｂａｃｋｗａｒｄスキャン部２２は、取得した距離画像の全ての画素を更新した場合、更新後の距離画像を第２列Ｆｏｒｗａｒｄスキャン部２３に出力する。
【００４１】
第２列Ｆｏｒｗａｒｄスキャン部２３および第２列Ｂａｃｋｗａｒｄスキャン部２４の処理は、第２行Ｆｏｒｗａｒｄスキャン部２１および第２行Ｂａｃｋｗａｒｄスキャン部２２の処理と同様である。
【００４２】
図８は、第２の関連技術における画像変換処理の概要を示す図である。第２行Ｆｏｒｗａｒｄスキャン部２１は、グローバルメモリに記憶されている入力画像を行毎にシェアードメモリにコピーし、画素毎にＦｏｒｗａｒｄスキャンを行う。図８に示すように、第２行Ｆｏｒｗａｒｄスキャン部２１は、列数のスレッド（スレッドｔｈ０、ｔｈ１・・・ｔｈＭ−１）の並列処理を行う。同様に、第２行Ｂａｃｋｗａｒｄスキャン部２２は、第２行Ｆｏｒｗａｒｄスキャン部２１が出力した距離画像を行毎にシェアードメモリにコピーし、画素毎にＢａｃｋｗａｒｄスキャンを行う。図８に示すように、第２行Ｂａｃｋｗａｒｄスキャン部２２は、列数のスレッド（スレッドｔｈ０、ｔｈ１・・・ｔｈＭ−１）の並列処理を行う。
【００４３】
第２列Ｆｏｒｗａｒｄスキャン部２３および第２列Ｂａｃｋｗａｒｄスキャン部２４も同様に、距離画像を列毎にシェアードメモリにコピーに、画素毎にスキャンを行う。
【００４４】
第２の関連技術では、画素毎にスレッドが割り当てられ並列処理が行われるため、並列数が多く、ＧＰＵの並列可能数を有効に利用することができる。しかし、図８に示すように、一つの画素に対して、複数のスレッドでスキャンが行われる可能性があり、第１の関連技術と比べて、演算量と画素アクセス数が多い。
【００４５】
図９は、第１の関連技術および第２の関連技術における並列数を示す図である。図９は、第１の関連技術および第２の関連技術を用いて、４Ｋ（３８４０×２１６０）、ＦｕｌｌＨｉｇｈ  Ｄｅｆｉｎｉｔｉｏｎ（ＨＤ）（１９２０×１０８０）、ＨＤ（１２８０×７２０）の画像を変換した場合の行方向の処理と列方向の処理の並列数を示している。第１の関連技術における行方向の処理の並列数は、入力画像の行数であり、列方向の並列数は入力画像の列数である。第２の関連技術における行方向および列方向の並列数は、入力画像の行数×列数である。
【００４６】
例えば、使用するＧＰＵのコア数が３５８４である場合、並列可能数は３５８４となる。この場合、第１の関連技術では、４Ｋの列方向の処理以外、並列可能数を有効に利用しないことになる。一方、第２の関連技術では、使用するＧＰＵの並列可能数を有効に利用するが、上述のように、第１の関連技術と比べて、演算量および画素アクセス数が多い。
【００４７】
以下、図面を参照して、実施形態について説明する。図１０は、実施形態における画像変換装置３の機能構成の一例を示す図である。画像変換装置３は、割り当て部３１と、行方向スキャン部３２と、行方向リダクション部３５と、行方向合算部３６と、列方向スキャン部３７と、列方向リダクション部４０と、列方向合算部４１と、第１記憶部４２と第２記憶部４３とを含む。画像変換装置３は、コンピュータの一例である。画像変換装置３のプロセッサとしてＧＰＵが用いられるとする。
【００４８】
割り当て部３１は、入力画像内の行単位の画素値を複数の区間に分割し、各行の区間毎に、プロセッサが並列実行可能なスレッドを割り当てる。割り当て部３１は、第１割り当て部および第２割り当て部の一例である。
【００４９】
行方向スキャン部３２は、行Ｆｏｒｗａｒｄスキャン部３３と、行Ｂａｃｋｗａｒｄスキャン部３４とを含む。行方向スキャン部３２は、各行で割り当てられたスレッド毎に、入力画像の所定数値の画素からの距離を各行の区間において算出し、距離を示す値を格納した距離画像Ｂを生成する。また、行方向スキャン部３２は、他の区間の所定数値の画素からの距離を示す境界値を算出する。なお、本実施形態では、所定数値の画素として０画素を用いる。行方向スキャン部３２は、第１生成部の一例である。距離画像Ｂは、第１距離画像の一例である。
【００５０】
行Ｆｏｒｗａｒｄスキャン部３３は、入力画像に対して区間毎にＦｏｒｗａｒｄスキャンを行い入力画像内の０画素からの距離を区間毎に算出し、算出結果を距離画像Ａの画素値として格納する。そして、行Ｆｏｒｗａｒｄスキャン部３３は、各区間の右端の画素値に１を加算した値をその区間の右境界値として格納する。行Ｆｏｒｗａｒｄスキャン部３３は、距離画像Ａを行Ｂａｃｋｗａｒｄスキャン部３４に出力し、右境界値を行方向リダクション部３５に出力する。
【００５１】
行Ｂａｃｋｗａｒｄスキャン部３４は、行Ｆｏｒｗａｒｄスキャン部３３から取得した距離画像Ａの各区間内の画素に対してＢａｃｋｗａｒｄスキャンを行う。行Ｂａｃｋｗａｒｄスキャン部３４は、スキャンの対象画素の直前にスキャンした画素の画素値に１を加算した値と距離画像Ａとの画素値とのうち小さい値を、新たな距離画像Ｂの画素値として格納する。そして、行Ｂａｃｋｗａｒｄスキャン部３４は、各区間の左端の画素値に１を加算した値をその区間の左境界値として格納する。行Ｂａｃｋｗａｒｄスキャン部３４は、左境界値を行方向リダクション部３５に出力し、距離画像Ｂを行方向合算部３６に出力する。
【００５２】
行方向リダクション部３５は、各行で割り当てられたスレッド毎に、各行の他の区間の０画素からの距離を示す第１境界値を、各行の他の区間における第１境界値の算出結果を用いて算出する。行方向リダクション部３５は、例えば、各行の他の区間の第１境界値に他の区間から行内の所定区間までの距離を加算した値の最小値と、区間内の第１境界値とのうち小さい値を、行内の所定区間の新たな第１境界値として格納する。区間の第１境界値は、行内の所定区間の端の画素値に１を加算した値である。第１境界値は、例えば、右境界値または左境界値である。
【００５３】
具体的には、行方向リダクション部３５は、例えば、他の区間（所定区間より左側の区間）の右境界値に他の区間から所定区間までの距離を加算した値の最小値と、所定区間の現在の右境界値とのうち小さい値を、所定区間の新たな右境界値として格納する。また、行方向リダクション部３５は、例えば、他の区間（所定区間より右側の区間）の左境界値に他の区間から所定区間までの距離を加算した値の最小値と、所定区間の現在の左境界値とのうち小さい値を、所定区間の新たな左境界値として格納する。行方向リダクション部３５は、第１算出部の一例である。
【００５４】
行方向合算部３６は、各行で割り当てられたスレッド毎に、行Ｂａｃｋｗａｒｄスキャン部３４から取得した距離画像内の値と、境界値（右境界値および左境界値）に基づいて算出した行全体をスコープとした０画素からの距離を示す値とのうち小さい値でその距離画像内の値を更新する。そして、行方向合算部３６は、更新後の距離画像Ｅを出力する。行方向合算部３６は、第１更新部の一例である。距離画像Ｅは、第２距離画像の一例である。
【００５５】
割り当て部３１は、行方向合算部３６が出力した距離画像Ｅ内の列単位の画素値を複数区間に分割し、各列の区間毎に、プロセッサが並列実行可能なスレッドを割り当てる。
【００５６】
列方向スキャン部３７は、列Ｆｏｒｗａｒｄスキャン部３８と、列Ｂａｃｋｗａｒｄスキャン部３９とを含む。列方向スキャン部３７は、行方向合算部３６が出力した距離画像Ｅを取得し、前記各列で割り当てられたスレッド毎に、距離画像Ｅにおける画素値に基づいて、所定数値の画素からの距離を示す値を各列の区間において算出し、算出した値を格納した距離画像Ｇを生成する。列方向スキャン部３７は、第２生成部の一例である。距離画像Ｇは、第３距離画像の一例である。
【００５７】
列Ｆｏｒｗａｒｄスキャン部３８は、行方向合算部３６から取得した距離画像Ｅの各区間内の画素に対してＦｏｒｗａｒｄスキャンを行う。列Ｆｏｒｗａｒｄスキャン部３８は、スキャンの対象画素の直前にスキャンした画素の画素値に１を加算した値と距離画像Ｅとの画素値とのうち小さい値を、新たな距離画像Ｆの画素値として格納する。そして、列Ｆｏｒｗａｒｄスキャン部３８は、各区間の下端の画素値に１を加算した値をその区間の下境界値として格納する。列Ｆｏｒｗａｒｄスキャン部３８は、距離画像Ｆを列Ｂａｃｋｗａｒｄスキャン部３９に出力し、下境界値を列方向リダクション部４０に出力する。
【００５８】
列Ｂａｃｋｗａｒｄスキャン部３９は、列Ｆｏｒｗａｒｄスキャン部３８から取得した距離画像Ｆの各区間内の画素に対してＢａｃｋｗａｒｄスキャンを行う。列Ｂａｃｋｗａｒｄスキャン部３９は、スキャンの対象画素の直前にスキャンした画素の画素値に１を加算した値と距離画像Ｆとの画素値とのうち小さい値を、新たな距離画像Ｇの画素値として格納する。そして、列Ｂａｃｋｗａｒｄスキャン部３９は、各区間の上端の画素値に１を加算した値をその区間の上境界値として格納する。列Ｂａｃｋｗａｒｄスキャン部３９は、距離画像Ｇを列方向合算部４１に出力し、上境界値を列方向リダクション部４０に出力する。
【００５９】
列方向リダクション部４０は、各列で割り当てられたスレッド毎に、各列の他の区間の０画素からの距離を示す第２境界値を、各列の他の区間における第２境界値の算出結果を用いて算出する。列方向リダクション部４０は、例えば、各列の他の区間の第２境界値に他の区間から列内の所定区間までの距離を加算した値の最小値と、区間内の第２境界値とのうち小さい値を、列内の所定区間の新たな第２境界値として格納する。この区間内の第２境界値は、列内の所定区間の端の画素値に１を加算した値である。第２境界値は、例えば、下境界値または上境界値である。
【００６０】
具体的には、列方向リダクション部４０は、例えば、他の区間（所定区間より上側の区間）の下境界値に他の区間から所定区間までの距離を加算した値の最小値と、所定区間の現在の下境界値とのうち小さい値を、所定区間の新たな下境界値として格納する。また、列方向リダクション部４０は、例えば、他の区間（所定区間より下側の区間）の上境界値に他の区間から所定区間までの距離を加算した値の最小値と、所定区間の現在の上境界値とのうち小さい値を、所定区間の新たな上境界値として格納する。列方向リダクション部４０は、第２算出部の一例である。
【００６１】
列方向合算部４１は、各列で割り当てられたスレッド毎に、列Ｂａｃｋｗａｒｄスキャン部３９から取得した距離画像内の値と、境界値（下境界値および上境界値）に基づいて算出した０画素からの距離を示す値とのうち小さい値でその距離画像内の値を更新した距離画像Ｈを出力する。列方向合算部４１は、例えば、画像変換装置３に接続された他の情報処理装置等に距離画像Ｈを送信してもよいし、表示装置に距離画像Ｈを送信して距離画像Ｈを表示してもよい。列方向合算部４１は、第２更新部の一例である。
【００６２】
第１記憶部４２は、例えば、ＧＰＵ内のレジスタである。行方向リダクション部３５および列方向リダクション部４０の処理に用いられる各種データの記憶、スレッド間のデータの受け渡しには、第１記憶部４２が用いられる。
【００６３】
第２記憶部４３は、例えば、ＧＰＵ内のシェアードメモリ、グローバルメモリ等、およびＧＰＵの外部のメモリを含む。行方向リダクション部３５および列方向リダクション部４０以外の構成の処理に関する各種データ（距離画像、境界値等）の記憶、スレッド間のデータの受け渡しには、第２記憶部４３が用いられる。
【００６４】
図１１は、行方向スキャン処理の一例を示す図である。割り当て部３１は、入力画像内の行単位の画素値を複数の区間に分割し、各行の区間毎にスレッドを割り当る。本実施形態では、割り当て部３１は、入力画像の画素を３２区間に分割する。ただし、区間数およびスレッド数は３２でなくてもよい。図１１では、区間ｘから区間ｘ+５に関して実行される処理を示している。例えば、区間ｘに関する算出処理をスレッドｘが実行する。また、各スレッドの処理は並列で行われる。
【００６５】
行Ｆｏｒｗａｒｄスキャン部３３は、入力画像に対して区間毎にＦｏｒｗａｒｄスキャンを行い入力画像内の０画素からの距離を区間毎に算出し、算出結果を距離画像の画素値として格納する。行Ｆｏｒｗａｒｄスキャン部３３は、入力画像においてスキャン対象画素よりも前に０画素が存在しない場合、不定値（∞）を距離画像Ａの画素値として格納する。
【００６６】
例えば、行Ｆｏｒｗａｒｄスキャン部３３は、列番号０において、スキャン対象画素よりも前に０画素が存在しないため、∞を距離画像Ａの画素値として格納する。行Ｆｏｒｗａｒｄスキャン部３３は、列番号１および２において、入力画像内が０画素であるため、距離画像Ａの画素値として０を格納する。行Ｆｏｒｗａｒｄスキャン部３３は、列番号３において、入力画像内の０画素からの距離が１であるため、距離画像の画素値として１を格納する。すなわち、行Ｆｏｒｗａｒｄスキャン部３３は、第１の関連技術における第１行Ｆｏｒｗａｒｄスキャン部１１と同様の処理を区間毎に行う。
【００６７】
行Ｆｏｒｗａｒｄスキャン部３３は、同様に、区間毎にＦｏｒｗａｒｄスキャンを行い、距離画像Ａの画素値を格納する。そして、行Ｆｏｒｗａｒｄスキャン部３３は、各区間の右端の画素値に１を加算した値をその区間の右境界値として格納する。
【００６８】
なお、行Ｆｏｒｗａｒｄスキャン部３３は、入力画像を読み込む際に、図８で示した例と同様に、入力画像を行単位でシェアードメモリに読み込み、シェアードメモリ上でスキャンを行ってもよい。
【００６９】
行Ｂａｃｋｗａｒｄスキャン部３４は、行Ｆｏｒｗａｒｄスキャン部３３から取得した距離画像Ａの各区間内の画素に対してＢａｃｋｗａｒｄスキャンを行う。行Ｂａｃｋｗａｒｄスキャン部３４は、スキャンの対象画素の直前にスキャンした画素の画素値に１を加算した値と距離画像Ａとの画素値とのうち小さい値を、新たな距離画像Ｂの画素値として格納する。すなわち、行Ｂａｃｋｗａｒｄスキャン部３４は、第１の関連技術における第１行Ｂａｃｋｗａｒｄスキャン部１２と同様の処理を区間毎に行う。
【００７０】
例えば、行Ｂａｃｋｗａｒｄスキャン部３４は、列番号２３において、スキャンの対象画素の直前にスキャンした画素の画素値が存在しないため、距離画像Ａの画素値を新たな距離画像Ｂの画素値として格納する。行Ｂａｃｋｗａｒｄスキャン部３４は、列番号２２において、スキャンの対象画素の直前にスキャンした画素の画素値（２）に１を加算した値（３）と距離画像Ａの画素値（１）とのうち小さい値である１を新たな距離画像Ｂの画素値として格納する。行Ｂａｃｋｗａｒｄスキャン部３４は、列番号２１において、スキャンの対象画素の直前にスキャンした画素の画素値（１）に１を加算した値（２）と距離画像Ａの画素値（０）とのうち小さい値である０を新たな距離画像Ｂの画素値として格納する。
【００７１】
行Ｂａｃｋｗａｒｄスキャン部３４は、列番号２０において、スキャンの対象画素の直前にスキャンした画素の画素値（０）に１を加算した値（１）と距離画像Ａの画素値（∞）とのうち小さい値である１を新たな距離画像の画素値として格納する。
【００７２】
行Ｂａｃｋｗａｒｄスキャン部３４は、同様に、区間毎にＢａｃｋｗａｒｄスキャンを行い、距離画像Ｂの画素値を格納する。そして、行Ｂａｃｋｗａｒｄスキャン部３４は、各区間の左端の画素値に１を加算した値をその区間の左境界値として格納する。
【００７３】
図１２は、行方向リダクション部３５における右境界値の算出例を示す図である。行方向リダクション部３５は、他の区間（所定区間より左側の区間）の右境界値に他の区間から所定区間までの距離を加算した値の最小値と、所定区間の現在の右境界値とのうち小さい値を、所定区間の新たな右境界値として格納する。
【００７４】
例えば、区間ｘ+１に関して、行方向リダクション部３５は、区間ｘの右境界値である２に距離４を加算した値である６と、現在の右境界値∞のうち小さい値である６を新たな右境界値として格納する。
【００７５】
図１２に示す例では、行方向リダクション部３５は、区間ｘ＋１の右境界値のみ更新しているが、他の区間に関しても同様の処理により右境界値を更新する。
【００７６】
図１３は、行方向リダクション部３５における左境界値の算出例を示す図である。行方向リダクション部３５は、他の区間（所定区間より右側の区間）の左境界値に他の区間から所定区間までの距離を加算した値の最小値と、所定区間の現在の左境界値とのうち小さい値を、所定区間の新たな左境界値として格納する。
【００７７】
例えば、区間ｘ+１に関して、行方向リダクション部３５は、区間ｘ+２から区間ｘ+３１までの各左境界値に区間ｘ+１までの距離を加算した値の最小値と、区間ｘ+１の現在の左境界値とのうち小さい方を区間ｘ+１の新たな左境界値とする。図１３に示す例では、例えば、区間ｘ＋２の左境界値３に区間ｘ＋１までの距離４を加算した値「７」が、区間ｘ+１における新たな左境界値として格納される。
【００７８】
図１３では、区間ｘ+１の左境界値の算出について示しているが、同様の処理が全区間に関して行われる。
【００７９】
図１２および図１３に示した処理について、各スレッドは、他の区間における境界値の算出結果を用いて、処理対象区間の境界値を算出することにより、計算回数を削減することができる。例えば、図１３に示すように、区間ｘ+１の左境界値の更新のために区間ｘ+１から区間ｘ+３１までの３０区間について「左境界値＋距離」という計算が行われるが、一つのスレッドで３０回の計算を行わなくてもよい。この計算回数の削減について、詳細は後述する。
【００８０】
図１４および図１５は、行方向リダクション部３５の処理の一例を示す図である。図１４および図１５に示すように区間ＩＤとスレッドＩＤに同一の数値が付与される。また、区間内の画素数をＥとし、区間内の右境界値をＲ（ｎ）（ｎ：区間ＩＤ）とする。
【００８１】
行方向リダクション部３５は、各スレッドにおいて、Ｄ（ｎ）を∞で初期化する。なお、初期化に用いる値は、∞でなくてもよく、距離画像の要素として存在しない十分に大きい値であるとする。また、行方向リダクション部３５は、各スレッドにおいて、右境界値Ｒ（ｎ−１）＋ＥをＤ（ｎ）に代入する。以下、スレッド１７の演算処理に関して詳細に説明する。
【００８２】
行方向リダクション部３５は、演算処理１において、Ｄ１７をｍｉｎ（Ｄ１７，Ｄ１５＋Ｅ×２）で更新する。よって、演算処理１の時点でＤ１７の算出に区間１６および区間１４の算出結果が用いられている。
【００８３】
そして、行方向リダクション部３５は、演算処理２において、Ｄ１７をｍｉｎ（Ｄ１７，Ｄ１３＋Ｅ×４）で更新する。このＤ１３は、スレッド１３の演算処理１におけるｍｉｎ（Ｄ１３，Ｄ１１＋Ｅ×２）の算出結果である。このＤ１３の算出結果には、区間１２および１０の算出結果が用いられている。よって、演算処理２の終了時点で、Ｄ１７の算出に区間１６，１４，１２，１０の算出結果が用いられている。
【００８４】
そして、行方向リダクション部３５は、演算処理３において、Ｄ１７をｍｉｎ（Ｄ１７，Ｄ９＋Ｅ×８）で更新する。このＤ９は、スレッド９の演算処理２におけるｍｉｎ（Ｄ９，Ｄ５＋Ｅ×４）の算出結果である。このＤ９の算出結果には、区間８，６，４，２の境界値が用いられている。よって、演算処理３の終了時点で、Ｄ１７の算出に区間１６，１４，１２，１０，８，６，４，２の境界値が用いられている。
【００８５】
そして、行方向リダクション部３５は、演算処理４において、Ｄ１７をｍｉｎ（Ｄ１７，Ｄ１＋Ｅ×１６）で更新する。このＤ１は、スレッド１の演算処理３までの処理結果である。ただし、スレッド１において、演算処理１〜３は行われていないが、初期設定においてＤ１にＲ０＋Ｅが代入されている。よって、演算処理４の終了時点で、Ｄ１７の算出に区間１６，１４，１２，１０，８，６，４，２，０の境界値が用いられている。
【００８６】
そして、行方向リダクション部３５は、演算処理５において、Ｄ１７をｍｉｎ（Ｄ１７，Ｄ１６＋Ｅ）−Ｅで更新する。このＤ１６は、スレッド１６の演算処理４までの処理結果である。このＤ１６の算出結果には、区間１５，１３，１１，９，７，５，３，１の境界値が用いられている。よって、演算処理５の終了時点で、Ｄ１７の算出に区間１６〜０の境界値が用いられている。
【００８７】
なお、演算処理５において、図１４、１５に示すように演算処理５において「−Ｅ」を演算している。初期設定でＲ（ｎ−１）＋ＥをＤ（ｎ）に代入しており、最後に「−Ｅ」を演算することで、演算処理５の算出結果であるＤ（ｎ）は、更新後のＲ（ｎ−１）に相当する。
【００８８】
演算処理１〜５により、Ｄ１７は、ｍｉｎ（Ｄ１６，Ｄ１５＋Ｅ，Ｄ１４＋Ｅ×２，Ｄ１３＋Ｅ×３，Ｄ１２＋Ｅ×４，．．．，Ｄ０＋Ｅ×１６）となる。すなわち、行全体をスコープとした右境界値であるＤ（ｎ）が算出される。スレッド１７の処理について説明したが、他のスレッドに関しても同様のアルゴリズムにより右境界値が算出される。
【００８９】
以上のように、行方向リダクション部３５は、他の区間の右境界値に所定区間から他の区間までの距離を加算した値の最小値を用いて、所定区間の右境界値を更新する。図１４および１６に示すように、区間が３２である場合、スレッド毎の演算処理は計５回となる。従って、行方向リダクション部３５は、境界値を算出する際に、他の区間における境界値の算出結果を用いて算出することにより、少ない演算処理で境界値を算出することができる。なお、行方向リダクション部３５の右境界値の更新について説明したが、左境界値に関しても同様に行われる。
【００９０】
なお、区間数およびスレッド数は３２でなくてもよい。例えば、区間数をｎとした場合演算回数はＬｏｇ２（ｎ）となる。
【００９１】
例えば、画像変換装置３のプロセッサにおいて、同じグループ内の複数スレッドが同一プログラムカウンタを共有可能であり、１グループ内に所定数のスレッドが割り当て可能であるとする。その場合、割り当て部３１は、入力画像内の行単位の画素値を、その所定数の区間に分割し、区間毎にスレッドを割り当てる。また、割り当て部３１は、距離画像Ｅ内の列単位の画素値をその所定数の区間に分割し、区間毎にスレッドを割り当てる。これにより、行方向リダクション部３５および列方向リダクション部４０は、スレッド間の同期処理をしなくてもよい。
【００９２】
画像変換装置３のプロセッサにおいて、スレッドが同じグループ内の他のスレッドの変数をレジスタ経由で参照可能であり、１グループ内に所定数のスレッドが割り当て可能であるとする。この場合、割り当て部３１は、入力画像内の行単位の画素値を、その所定数の区間に分割し、各行の区間毎にスレッドを割り当てる。また、割り当て部３１は、距離画像Ｅ内の列単位の画素値を、その所定数の区間に分割し、区間毎にスレッドを割り当てる。これにより、行方向リダクション部３５および列方向リダクション部４０は、高速に処理を行うことができる。
【００９３】
以下、行方向リダクション部３５および列方向リダクション部４０の処理について、さらに詳細に説明する。上述のように、割り当て部３１は、入力した画像の行または列を抜き出し、その行または列を３２区間に分ける。区間数は対象のＣＰＵやＧＰＵに応じて変更可能とする。１区間あたりの要素数はＥとする。割り当て部３１は、３２区間に対して３２スレッド割り当て、各区間が並列で動作する。各区間では、Ｅ個のＦｏｒｗａｒｄスキャン（左から右方向へ）、Ｅ個のＢａｃｋｗａｒｄスキャン（右から左方向へ）により、それぞれ右境界値、左境界値が確定する。これは区間内の右端要素からゼロ値を持つ要素への距離、区間内の左端要素からゼロ値を持つ要素への距離と等しい。各区間の右境界値をＲ（０）、Ｒ（１）、Ｒ（２）、…、Ｒ（３１）とする。各区間の左境界値をＬ（０）、Ｌ（１）、Ｌ（２）、…、Ｌ（３１）とする。
【００９４】
以下、行方向リダクション部３５の基本の形について説明するが、列方向リダクション部４０の処理も同様であるとする。行方向リダクション部３５は、各区間の右境界値を使って、自区間を基準に左側の区間の中からゼロ値持つ区間を探し、その最短距離を確定する。同様に、各区間の左境界値を使って、自区間を基準に右側の区間の中からゼロ値を持つ区間を探し、その最短距離を確定する。例えば、区間３１を自区間とした場合、Ｌ（０）、Ｌ（１）、Ｌ（２）、…、Ｌ（３０）の中からゼロ値持つ区間を探し、区間３１から最も近い距離のＬ（ｘ）を求める。このとき、区間３１からＬ（０）はＥ＊３０、Ｌ（１）はＥ＊２９、…Ｌ（３０）はＥ＊１離れているので、それを足した距離で最短距離を求める。
【００９５】
行方向リダクション部３５は、３２区間に対して３２スレッド割り当て、各区間が並列で動作する。短い処理時間で求めるため、各スレッドのデータを共有しながら処理する。各区間の左側区間の最短距離を探す場合は、各スレッドがそれぞれ区間０、区間１、区間２、…、区間３１を自区間として担当する。ここでは各スレッドで自区間をｎとおき、次のように動作する。
【００９６】
図１４、１５に示した初期設定について説明する。行方向リダクション部３５は、自区間ｎの１つ隣のＲ（ｎ−１）を取得し、Ｒ（ｎ−１）＋ＥをＤ（ｎ）へ代入する。Ｅを足すのは、自区間ｎと基準とした場合に１個隣の区間はＥ離れているためである。行方向リダクション部３５は、以下の計算を並列で実行する。
Ｄ（０）＝∞
Ｄ（１）＝Ｒ（０）＋Ｅ
Ｄ（２）＝Ｒ（１）＋Ｅ
（省略）
Ｄ（３１）＝Ｒ（３０）＋Ｅ
【００９７】
すなわち、行方向リダクション部３５は、以下の式（３−１）を各スレッドで実行する。
Ｄ（ｎ）＝Ｒ（ｎ−１）＋Ｅ      （３−１）
【００９８】
図１４、１５に示した演算処理１について説明する。行方向リダクション部３５は、自区間ｎの２つ隣のＤ（ｎ−２）を取得し、Ｄ（ｎ−２）＋Ｅ＊２とＤ（ｎ）のうち、最小値を選び、Ｄ（ｎ）へ代入する。式（３−１）より、他スレッドが計算したＤ（ｎ−２）には、Ｒ（ｎ−３）＋Ｅが入っている。自区間ｎからの距離に直すため、Ｄ（ｎ−２）＋Ｅ＊２とする。
【００９９】
式（１）より、Ｄ（ｎ）には、Ｒ（ｎ−１）＋Ｅが入っている。したがって、行方向リダクション部３５は、以下の式（３−２）を各スレッドで実行する。
Ｄ（ｎ）＝Ｍｉｎ［Ｄ（ｎ−２）＋Ｅ＊２、Ｄ（ｎ）］
＝Ｍｉｎ［Ｒ（ｎ−３）＋Ｅ＊３、Ｒ（ｎ−１）＋Ｅ］      （３−２）
【０１００】
図１４、１５に示した演算処理２について説明する。行方向リダクション部３５は、自区間ｎの４個隣のＤ（ｎ−４）を取得し、Ｄ（ｎ−４）＋Ｅ＊４とＤ（ｎ）のうち、最小値を選び、Ｄ（ｎ）へ代入する。例えば、式（３−２）より、他スレッドが計算したＤ（ｎ−４）には、Ｍｉｎ［Ｒ（ｎ−７）＋Ｅ＊３、Ｒ（ｎ−５）＋Ｅ］が入っている。行方向リダクション部３５は、自区間ｎからの距離に直すため、比較対象をＤ（ｎ−４）＋Ｅ＊４とする。
【０１０１】
式（２−２）より、Ｄ（ｎ）には、Ｍｉｎ［Ｒ（ｎ−３）＋Ｅ＊３、Ｒ（ｎ−１）＋Ｅ］が入っている。したがって、行方向リダクション部３５は、以下の式（３−３）を各スレッドで実行する。
Ｄ（ｎ）＝Ｍｉｎ［Ｄ（ｎ−４）＋Ｅ＊４、Ｄ（ｎ）］
＝Ｍｉｎ［Ｍｉｎ［Ｒ（ｎ−７）＋Ｅ＊７、Ｒ（ｎ−５）＋Ｅ＊５］、Ｍｉｎ［Ｒ（ｎ−３）＋Ｅ＊３、Ｒ（ｎ−１）＋Ｅ］］
＝Ｍｉｎ［Ｒ（ｎ−７）＋Ｅ＊７、Ｒ（ｎ−５）＋Ｅ＊５、Ｒ（ｎ−３）＋Ｅ＊３、Ｒ（ｎ−１）＋Ｅ］      （３−３）
【０１０２】
図１４、１５に示した演算処理３について説明する。行方向リダクション部３５は、自区間ｎの８個隣のＤ（ｎ−８）を取得し、Ｄ（ｎ−８）＋Ｅ＊８とＤ（ｎ）のうち、最小値を選び、Ｄ（ｎ）へ代入する。式（３−３）より、他スレッドが計算したＤ（ｎ−８）には、Ｍｉｎ［Ｒ（ｎ−１５）＋Ｅ＊７、Ｒ（ｎ−１３）＋Ｅ＊５、Ｒ（ｎ−１１）＋Ｅ＊３、Ｒ（ｎ−９）＋Ｅ］が入っている。行方向リダクション部３５は、自区間ｎからの距離に直すため、比較対象をＤ（ｎ−８）＋Ｅ＊８とする。
【０１０３】
式（３−３）より、Ｄ（ｎ）には、Ｍｉｎ［Ｒ（ｎ−７）＋Ｅ＊７、Ｒ（ｎ−５）＋Ｅ＊５、Ｒ（ｎ−３）＋Ｅ＊３、Ｒ（ｎ−１）＋Ｅ］が入っている。したがって、行方向リダクション部３５は、以下の式（３−４）を各スレッドで実行する。
Ｄ（ｎ）＝Ｍｉｎ［Ｄ（ｎ−８）＋Ｅ＊８、Ｄ（ｎ）］
＝Ｍｉｎ［Ｍｉｎ［Ｒ（ｎ−１５）＋Ｅ＊１５、Ｒ（ｎ−１３）＋Ｅ＊１３、Ｒ（ｎ−１１）＋Ｅ＊１１、Ｒ（ｎ−９）＋Ｅ＊９］、Ｍｉｎ［Ｒ（ｎ−７）＋Ｅ＊７、Ｒ（ｎ−５）＋Ｅ＊５、Ｒ（ｎ−３）＋Ｅ＊３、Ｒ（ｎ−１）＋Ｅ］］
＝Ｍｉｎ［Ｒ（ｎ−１５）＋Ｅ＊１５、Ｒ（ｎ−１３）＋Ｅ＊１３、Ｒ（ｎ−１１）＋Ｅ＊１１、Ｒ（ｎ−９）＋Ｅ＊９、Ｒ（ｎ−７）＋Ｅ＊７、Ｒ（ｎ−５）＋Ｅ＊５、Ｒ（ｎ−３）＋Ｅ＊３、Ｒ（ｎ−１）＋Ｅ］      式（３−４）
【０１０４】
図１４、１５に示した演算処理４について説明する。行方向リダクション部３５は、自区間ｎの１６個隣のＤ（ｎ−１６）を取得し、Ｄ（ｎ−１６）＋Ｅ＊１６とＤ（ｎ）のうち、最小値を選び、Ｄ（ｎ）へ代入する。式（３−４）より、他スレッドが計算したＤ（ｎ−１６）には、Ｍｉｎ［Ｒ（ｎ−３１）＋Ｅ＊１５、Ｒ（ｎ−２９）＋Ｅ＊１３、Ｒ（ｎ−２７）＋Ｅ＊１１、Ｒ（ｎ−２５）＋Ｅ＊９、Ｒ（ｎ−２３）＋Ｅ＊７、Ｒ（ｎ−２１）＋Ｅ＊５、Ｒ（ｎ−１９）＋Ｅ＊３、Ｒ（ｎ−１７）＋Ｅ］が入っている。自区間ｎからの距離に直すため、比較対象をＤ（ｎ−１６）＋Ｅ＊１６とする。
【０１０５】
式（３−４）より、Ｄ（ｎ）には、Ｍｉｎ［Ｒ（ｎ−１５）＋Ｅ＊１５、Ｒ（ｎ−１３）＋Ｅ＊１３、Ｒ（ｎ−１１）＋Ｅ＊１１、Ｒ（ｎ−９）＋Ｅ＊９、Ｒ（ｎ−７）＋Ｅ＊７、Ｒ（ｎ−５）＋Ｅ＊５、Ｒ（ｎ−３）＋Ｅ＊３、Ｒ（ｎ−１）＋Ｅ］が入っている。したがって、したがって、行方向リダクション部３５は、以下の式（３−５）を各スレッドで実行する。
Ｄ（ｎ）＝Ｍｉｎ［Ｄ（ｎ−１６）＋Ｅ＊１６、Ｄ（ｎ）］
＝Ｍｉｎ［Ｍｉｎ［Ｒ（ｎ−３１）＋Ｅ＊３１、Ｒ（ｎ−２９）＋Ｅ＊２９、Ｒ（ｎ−２７）＋Ｅ＊２７、Ｒ（ｎ−２５）＋Ｅ＊２５、Ｒ（ｎ−２３）＋Ｅ＊２３、Ｒ（ｎ−２１）＋Ｅ＊２１、Ｒ（ｎ−１９）＋Ｅ＊１９、Ｒ（ｎ−１７）＋Ｅ＊１７］、Ｍｉｎ［Ｒ（ｎ−１５）＋Ｅ＊１５、Ｒ（ｎ−１３）＋Ｅ＊１３、Ｒ（ｎ−１１）＋Ｅ＊１１、Ｒ（ｎ−９）＋Ｅ＊９、Ｒ（ｎ−７）＋Ｅ＊７、Ｒ（ｎ−５）＋Ｅ＊５、Ｒ（ｎ−３）＋Ｅ＊３、Ｒ（ｎ−１）＋Ｅ］］
＝Ｍｉｎ［Ｒ（ｎ−３１）＋Ｅ＊３１、Ｒ（ｎ−２９）＋Ｅ＊２９、Ｒ（ｎ−２７）＋Ｅ＊２７、Ｒ（ｎ−２５）＋Ｅ＊２５、Ｒ（ｎ−２３）＋Ｅ＊２３、Ｒ（ｎ−２１）＋Ｅ＊２１、Ｒ（ｎ−１９）＋Ｅ＊１９、Ｒ（ｎ−１７）＋Ｅ＊１７、Ｒ（ｎ−１５）＋Ｅ＊１５、Ｒ（ｎ−１３）＋Ｅ＊１３、Ｒ（ｎ−１１）＋Ｅ＊１１、Ｒ（ｎ−９）＋Ｅ＊９、Ｒ（ｎ−７）＋Ｅ＊７、Ｒ（ｎ−５）＋Ｅ＊５、Ｒ（ｎ−３）＋Ｅ＊３、Ｒ（ｎ−１）＋Ｅ］      （３−５）
【０１０６】
図１４、１５に示した演算処理５について説明する。偶数区間の距離を考慮するため、行方向リダクション部３５は、Ｄ（ｎ−１）を取得し、Ｄ（ｎ−１）＋ＥとＤ（ｎ）のうち、最小値を選び、Ｄ（ｎ）へ代入する。式（３−５）より、Ｄ（ｎ−１）には、Ｍｉｎ［Ｒ（ｎ−３０）＋Ｅ＊２９、Ｒ（ｎ−２８）＋Ｅ＊２７、Ｒ（ｎ−２６）＋Ｅ＊２５、Ｒ（ｎ−２４）＋Ｅ＊２３、Ｒ（ｎ−２２）＋Ｅ＊２１、Ｒ（ｎ−２０）＋Ｅ＊１９、Ｒ（ｎ−１８）＋Ｅ＊１７、Ｒ（ｎ−１６）＋Ｅ＊１５、Ｒ（ｎ−１４）＋Ｅ＊１３、Ｒ（ｎ−１２）＋Ｅ＊１１、Ｒ（ｎ−１０）＋Ｅ＊９、Ｒ（ｎ−８）＋Ｅ＊７、Ｒ（ｎ−６）＋Ｅ＊５、Ｒ（ｎ−４）＋Ｅ＊３、Ｒ（ｎ−２）＋Ｅ］が入っている。自区間ｎからの距離に直すため、比較対象をＤ（ｎ−１）＋Ｅ＊１とする。
【０１０７】
式（３−５）より、Ｄ（ｎ）には、Ｍｉｎ［Ｒ（ｎ−３１）＋Ｅ＊３１、Ｒ（ｎ−２９）＋Ｅ＊２９、Ｒ（ｎ−２７）＋Ｅ＊２７、Ｒ（ｎ−２５）＋Ｅ＊２５、Ｒ（ｎ−２３）＋Ｅ＊２３、Ｒ（ｎ−２１）＋Ｅ＊２１、Ｒ（ｎ−１９）＋Ｅ＊１９、Ｒ（ｎ−１７）＋Ｅ＊１７、Ｒ（ｎ−１５）＋Ｅ＊１５、Ｒ（ｎ−１３）＋Ｅ＊１３、Ｒ（ｎ−１１）＋Ｅ＊１１、Ｒ（ｎ−９）＋Ｅ＊９、Ｒ（ｎ−７）＋Ｅ＊７、Ｒ（ｎ−５）＋Ｅ＊５、Ｒ（ｎ−３）＋Ｅ＊３、Ｒ（ｎ−１）＋Ｅ］
【０１０８】
したがって、行方向リダクション部３５は、以下の式（３−６）を各スレッドで実行する。Ｄ（ｎ）＝Ｍｉｎ［Ｄ（ｎ−１）＋Ｅ、Ｄ（ｎ）］−Ｅ
＝Ｍｉｎ［Ｒ（ｎ−３１）＋Ｅ＊３１、Ｒ（ｎ−３０）＋Ｅ＊３０、Ｒ（ｎ−２９）＋Ｅ＊２９、Ｒ（ｎ−２８）＋Ｅ＊２８、Ｒ（ｎ−２７）＋Ｅ＊２７、Ｒ（ｎ−２６）＋Ｅ＊２６、Ｒ（ｎ−２５）＋Ｅ＊２５、Ｒ（ｎ−２４）＋Ｅ＊２４、Ｒ（ｎ−２３）＋Ｅ＊２３、Ｒ（ｎ−２２）＋Ｅ＊２２、Ｒ（ｎ−２１）＋Ｅ＊２１、Ｒ（ｎ−２０）＋Ｅ＊２０、Ｒ（ｎ−１９）＋Ｅ＊１９、Ｒ（ｎ−１８）＋Ｅ＊１８、Ｒ（ｎ−１７）＋Ｅ＊１７、Ｒ（ｎ−１６）＋Ｅ＊１６、Ｒ（ｎ−１５）＋Ｅ＊１５、Ｒ（ｎ−１４）＋Ｅ＊１４、Ｒ（ｎ−１３）＋Ｅ＊１３、Ｒ（ｎ−１２）＋Ｅ＊１２、Ｒ（ｎ−１１）＋Ｅ＊１１、Ｒ（ｎ−１０）＋Ｅ＊１０、Ｒ（ｎ−９）＋Ｅ＊９、Ｒ（ｎ−８）＋Ｅ＊８、Ｒ（ｎ−７）＋Ｅ＊７、Ｒ（ｎ−６）＋Ｅ＊６、Ｒ（ｎ−５）＋Ｅ＊５、Ｒ（ｎ−４）＋Ｅ＊４、Ｒ（ｎ−３）＋Ｅ＊３、Ｒ（ｎ−２）＋Ｅ＊２、Ｒ（ｎ−１）＋Ｅ］−Ｅ  （３−６）
【０１０９】
演算処理４までは、隣の区間を基準とした演算であったため、最後に−Ｅをすることにより、自区間ｎの左端を基準とした値にする。
【０１１０】
図１６は、行方向合算部３６の処理の一例を示す図である。図１６における入力画像、距離画像Ｂは、図１１に示す内容と同じである。右境界値は、図１２に示す内容と同じであり、左境界値は、図１３に示す内容と同じである。
【０１１１】
行方向合算部３６は、右境界値に基づいて、他の区間の０画素からの距離を示す距離画像Ｃを生成する。行方向合算部３６は、所定区間の右境界値を、所定区間の右の区間の左端の画素に格納し、左端の数値から連続した値を各画素に格納する。図１６に示すように、例えば、距離画像Ｃの区間ｘ＋１の画素は、（区間ｘの右境界値、区間ｘの右境界値＋１、区間ｘの右境界値＋２、区間ｘの右境界値＋３）となる。
【０１１２】
同様に、行方向合算部３６は、左境界値に基づいて、他の区間の０画素からの距離を示す距離画像Ｄを生成する。行方向合算部３６は、所定区間の左境界値を、所定区間の左の区間の右端の画素に格納し、左端の数値から連続した値を各画素に格納する。図１６に示すように、例えば、区間ｘの画素は、（区間ｘ＋１の左境界値＋３、区間ｘ＋１の左境界値＋２、区間ｘ＋１の左境界値＋１、区間ｘ＋１の左境界値）となる。
【０１１３】
行方向合算部３６は、距離画像Ｂ，Ｃ，Ｄの各画素の最小値を更新後の距離画像Ｅとして出力する。
【０１１４】
図１７は、列Ｆｏｒｗａｒｄスキャン処理の一例を示す図である。列Ｆｏｒｗａｒｄスキャン部３８は、行方向合算部３６から出力された距離画像Ｅを取得し、列Ｆｏｒｗａｒｄスキャンを行い、距離画像Ｅを更新する。
【０１１５】
列Ｆｏｒｗａｒｄスキャン部３８は、スキャンの対象画素の直前にスキャンした画素の画素値に１を加算した値と、距離画像Ｅの画素値とのうち小さい値を、新たな距離画像の画素値として格納する。例えば、行番号０において、列Ｆｏｒｗａｒｄスキャン部３８は、直前にスキャンした画素が存在しないため、距離画像Ｅの画素値を、そのまま新たな距離画像Ｆの画素値として格納する。行番号１において、列Ｆｏｒｗａｒｄスキャン部３８は、直前にスキャンした画素の画素値（１）に１を加算した値（２）と距離画像Ｅの画素値（０）のうち、小さいほうの値（０）を新たな距離画像Ｆの画素値として格納する。
【０１１６】
行番号２において、列Ｆｏｒｗａｒｄスキャン部３８は、直前にスキャンした画素の画素値（０）に１を加算した値（１）と距離画像Ｅの画素値（４）のうち、小さいほうの値（１）を新たな距離画像Ｆの画素値として格納する。行番号３において、列Ｆｏｒｗａｒｄスキャン部３８は、直前にスキャンした画素の画素値（１）に１を加算した値（２）と距離画像Ｅの画素値（３）とのうち小さい値である２を新たな距離画像の画素値として格納する。
【０１１７】
列Ｆｏｒｗａｒｄスキャン部３８は、各区間において同様の処理を行い、距離画像Ｅを更新し、更新後の距離画像Ｆを出力する。そして、列Ｆｏｒｗａｒｄスキャン部３８は、各区間の下端の画素値に１を加算した値をその区間の下境界値として格納する。
【０１１８】
図１８は、列Ｂａｃｋｗａｒｄスキャン処理の一例を示す図である。列Ｂａｃｋｗａｒｄスキャン部３９は、列Ｆｏｒｗａｒｄスキャン部３８が出力した距離画像Ｆを取得し、列Ｂａｃｋｗａｒｄスキャンを行い、距離画像Ｆを更新する。
【０１１９】
列Ｂａｃｋｗａｒｄスキャン部３９は、スキャンの対象画素の直前にスキャンした画素の画素値に１を加算した値と、距離画像Ｆの画素値とのうち小さい値を、新たな距離画像Ｇの画素値として格納する。行番号１２７において、列Ｂａｃｋｗａｒｄスキャン部３９は、直前にスキャンした画素が存在しないため、距離画像Ｆの画素値を、そのまま新たな距離画像Ｇの画素値として格納する。行番号１２６において、列Ｂａｃｋｗａｒｄスキャン部３９は、直前にスキャンした画素の画素値（１）に１を加算した値（２）と距離画像Ｆの画素値（０）のうち、小さいほうの値（０）を新たな距離画像Ｇの画素値として格納する。
【０１２０】
行番号１２５において、列Ｂａｃｋｗａｒｄスキャン部３９は、直前にスキャンした画素の画素値（０）に１を加算した値（１）と距離画像Ｆの画素値（４）のうち、小さいほうの値（１）を新たな距離画像Ｇの画素値として格納する。行番号１２４において、列Ｂａｃｋｗａｒｄスキャン部３９は、直前にスキャンした画素の画素値（１）に１を加算した値（２）と距離画像Ｆの画素値（３）とのうち小さい値である２を新たな距離画像の画素値として格納する。
【０１２１】
列Ｂａｃｋｗａｒｄスキャン部３９は、各区間において同様の処理を行い、列Ｆｏｒｗａｒｄスキャン部３８が出力した距離画像Ｆを更新し、更新後の距離画像Ｇを出力する。そして、列Ｂａｃｋｗａｒｄスキャン部３９は、各区間の上端の画素値に１を加算した値をその区間の上境界値として格納する。
【０１２２】
列方向リダクション部４０は、列Ｆｏｒｗａｒｄスキャン部３８から下境界値を取得する。そして、列方向リダクション部４０は、他の区間（所定区間より上側の区間）の下境界値に他の区間から所定区間までの距離を加算した値の最小値と、所定区間の現在の下境界値とのうち小さい値を、所定区間の新たな下境界値として格納する。
【０１２３】
また、列方向リダクション部４０は、列Ｂａｃｋｗａｒｄスキャン部３９から上境界値を取得する。そして、列方向リダクション部４０は、他の区間（所定区間より下側の区間）の上境界値に他の区間から所定区間までの距離を加算した値の最小値と、所定区間の現在の上境界値とのうち小さい値を、所定区間の新たな上境界値として格納する。列方向リダクション部４０の処理は、図１４および図１５に示した行方向リダクション部３５の処理と方向が異なる以外は同様である。
【０１２４】
なお、列Ｆｏｒｗａｒｄスキャン部３８および列Ｂａｃｋｗａｒｄスキャン部３９は、スキャンを行う前に、距離画像の行と列を入れ替える転置処理を行ってからスキャン処理を行ってもよい。プロセッサは、処理対象の画素がアドレス順に並んでいた場合に、高速に処理を行うことができる。そのため、アドレスが行方向に連続して付与されている場合、列Ｆｏｒｗａｒｄスキャン部３８および列Ｂａｃｋｗａｒｄスキャン部３９は、距離画像を転置してからスキャン処理を行うことにより、処理を高速に行うことができる。例えば、行方向合算部３６が、列方向スキャン部３７に距離画像Ｅを出力する前に距離画像Ｅを転置してもよい。
【０１２５】
図１９は、実施形態の行方向の処理の一例を示すフローチャートである。図１９に示すように、画像変換装置３は、ステップＳ１０１の処理を、行毎に並列で実行する。また、ステップＳ１０２〜Ｓ１０７の処理に関して、各行の各区間にスレッドが割り当てられ、各スレッドが並列で実行する。すなわち、ステップＳ１０２〜Ｓ１０７について、行数Ｍ×区間数３２のスレッドが並列で動作する。
【０１２６】
割り当て部３１は、入力画像のｘ行目を読み込み、入力画像内の行単位の画素値を３２区間に分割し、区間毎にスレッドを割り当てる（ステップＳ１０１）。
【０１２７】
行Ｆｏｒｗａｒｄスキャン部３３は、入力画像に対して区間毎にＦｏｒｗａｒｄスキャンを行い入力画像内の０画素からの距離を区間毎に算出し、算出結果を格納した距離画像Ａを生成する（ステップＳ１０２）。そして、行Ｆｏｒｗａｒｄスキャン部３３は、区間ｉの右端の画素値に１を加算した値を区間ｉの右境界値として格納する（ステップＳ１０３）。
【０１２８】
行Ｂａｃｋｗａｒｄスキャン部３４は、距離画像Ａに行Ｂａｃｋｗａｒｄスキャンを行う。そして、行Ｂａｃｋｗａｒｄスキャン部３４は、スキャンの対象画素の直前にスキャンした画素の画素値に１を加算した値と距離画像Ａとの画素値とのうち小さい値で距離画像Ａを距離画像Ｂに更新する（ステップＳ１０４）。そして、行Ｂａｃｋｗａｒｄスキャン部３４は、区間ｉの左端の画素値に１を加算した値を区間ｉの左境界値として格納する（ステップＳ１０５）。
【０１２９】
行方向リダクション部３５は、他の区間の０画素からの距離を示す右境界値および左境界値を、他の区間における右境界値および左境界値の算出結果を用いて算出し、更新する（ステップＳ１０６）。
【０１３０】
行方向合算部３６は、行Ｂａｃｋｗａｒｄスキャン部３４から取得した距離画像Ｂ内の値と、境界値（右境界値および左境界値）に基づいて算出した０画素からの距離のうち小さい値で距離画像Ｂ内の値を更新した距離画像Ｅを出力する（ステップＳ１０７）。
【０１３１】
図２０は、実施形態の列方向の処理の一例を示すフローチャートである。図２０に示すように、画像変換装置３は、ステップＳ２０１の処理を、列毎に並列で実行する。また、ステップＳ２０２〜Ｓ２０７の処理に関して、各列の各区間にスレッドが割り当てられ、各スレッドが並列で実行する。すなわち、ステップＳ２０２〜Ｓ２０７について、列数Ｎ×区間数３２のスレッドが並列で動作する。
【０１３２】
割り当て部３１は、入力画像のｙ列目を読み込み、入力画像内の列単位の画素値を３２区間に分割し、区間毎にスレッドを割り当てる（ステップＳ２０１）。
【０１３３】
列Ｆｏｒｗａｒｄスキャン部３８は、行方向合算部３６が出力した距離画像Ｅに対して区間毎にＦｏｒｗａｒｄスキャンを行い、距離画像を更新する（ステップＳ２０２）。列Ｆｏｒｗａｒｄスキャン部３８は、スキャンの対象画素の直前にスキャンした画素の画素値に１を加算した値と距離画像Ｅとの画素値とのうち小さい値を、新たな距離画像Ｆの画素値として格納する。
【０１３４】
そして、列Ｆｏｒｗａｒｄスキャン部３８は、区間ｉの下端の画素値に１を加算した値を区間ｉの下境界値として格納する（ステップＳ２０３）。
【０１３５】
列Ｂａｃｋｗａｒｄスキャン部３９は、距離画像Ｆに列Ｂａｃｋｗａｒｄスキャンを行う。そして、列Ｂａｃｋｗａｒｄスキャン部３９は、スキャンの対象画素の直前にスキャンした画素の画素値に１を加算した値と距離画像Ｆとの画素値とのうち小さい値で距離画像Ｆを距離画像Ｇに更新する（ステップＳ２０４）。そして、列Ｂａｃｋｗａｒｄスキャン部３９は、区間ｉの上端の画素値に１を加算した値を区間ｉの上境界値として格納する（ステップＳ２０５）。
【０１３６】
列方向リダクション部４０は、他の区間の０画素からの距離を示す下境界値および上境界値を、他の区間における下境界値および上境界値の算出結果を用いて算出し、更新する（ステップＳ２０６）。
【０１３７】
列方向合算部４１は、列Ｂａｃｋｗａｒｄスキャン部３９から取得した距離画像Ｇ内の値と、境界値（下境界値および上境界値）に基づいて算出した０画素からの距離のうち小さい値で距離画像Ｇ内の値を更新した距離画像Ｈを出力する（ステップＳ２０７）。
【０１３８】
図２１は、第１の関連技術、第２の関連技術および実施形態における並列数を示す図である。図２１は、第１の関連技術、第２の関連技術および実施形態の処理を用いて、４Ｋ（３８４０×２１６０）、ＦｕｌｌＨＤ（１９２０×１０８０）、ＨＤ（１２８０×７２０）の画像を変換した場合の行方向の処理と列方向の処理の並列数を示している。
【０１３９】
例えば、実施形態の行方向処理を実行する場合、図１９に示したように、行毎に３２スレッドで並列処理が行われるため、行数×３２が並列数となる。また、実施形態の列方向処理を実行する場合、図２０に示したように、列毎に３２スレッドで並列処理が行われるため、列数×３２が並列数となる。
【０１４０】
図２１に示すように実施形態の処理を用いた場合、関連技術１よりも並列数が多い。また、上述のようにスレッドと区間が対応しており、一つの画素に対して複数のスレッドでアクセスを行うことがない。よって、関連技術２と比べて画素アクセス量、演算量が少ない。従って、画像変換装置３は、少ないアクセス量で並列可能数を有効に使用した画像変換を実行することができる。
【０１４１】
次に、画像変換装置３のハードウェア構成の一例を説明する。図２２は、画像変換装置３のハードウェア構成の一例を示す図である。図２２の例に示すように、画像変換装置３において、バス１００に、プロセッサ１１１とメモリ１１２と補助記憶装置１１３と通信インタフェース１１４と媒体接続部１１５と入力装置１１６と出力装置１１７とが接続される。
【０１４２】
プロセッサ１１１は、メモリ１１２に展開されたプログラムを実行する。実行されるプログラムには、実施形態における処理を行う画像変換プログラムが適用されてもよい。プロセッサ１１１は、例えば、複数のコアを有するＧＰＵまたはＣＰＵである。図１０の第１記憶部４２は、例えば、プロセッサ１１１内のレジスタが適用される。第２記憶部４３は、例えば、プロセッサ１１１内のシェアードメモリ、グローバルメモリ等が適用される。
【０１４３】
メモリ１１２は、例えば、Random Access Memory(ＲＡＭ)である。補助記憶装置１１３は、種々の情報を記憶する記憶装置であり、例えばハードディスクドライブや半導体メモリ等が適用されてもよい。補助記憶装置１１３に実施形態の処理を行う画像変換プログラムが記憶されていてもよい。
【０１４４】
通信インタフェース１１４は、Local Area Network（ＬＡＮ）、Wide Area Network（ＷＡＮ）等の通信ネットワークに接続され、通信に伴うデータ変換等を行う。
【０１４５】
媒体接続部１１５は、可搬型記録媒体１１８が接続可能なインタフェースである。可搬型記録媒体１１８には、光学式ディスク（例えば、Compact Disc(ＣＤ)またはDigital Versatile Disc(ＤＶＤ))、半導体メモリ等が適用されてもよい。可搬型記録媒体１１８に実施形態の処理を行う画像変換プログラムが記録されていてもよい。
【０１４６】
入力装置１１６は、例えば、キーボード、ポインティングデバイス等であり、ユーザからの指示及び情報等の入力を受け付ける。
【０１４７】
出力装置１１７は、例えば、表示装置、プリンタ、スピーカ等であり、ユーザへの問い合わせ又は指示、及び処理結果等を出力する。出力装置１１７は、例えば、列方向合算部４１が出力する距離画像Ｈを表示する。
【０１４８】
図１０に示す第２記憶部４３は、メモリ１１２、補助記憶装置１１３または可搬型記録媒体１１８等により実現されてもよい。図１０に示す割り当て部３１、行方向スキャン部３２、行方向リダクション部３５、行方向合算部３６、列方向スキャン部３７、列方向リダクション部４０、列方向合算部４１は、メモリ１１２に展開された画像変換プログラムをプロセッサ１１１が実行することにより実現されてもよい。
【０１４９】
メモリ１１２、補助記憶装置１１３および可搬型記録媒体１１８は、コンピュータが読み取り可能であって非一時的な有形の記憶媒体であり、信号搬送波のような一時的な媒体ではない。
【０１５０】
なお、画像変換装置３が図２２に示す全ての構成要素を含んでいなくてもよく、一部の構成要素が省略されていてもよい。また、一部の構成要素が画像変換装置３の外部装置に存在し、画像変換装置３が外部装置に接続して、外部装置内の構成要素を利用してもよい。
【０１５１】
本実施形態は、以上に述べた実施の形態に限定されるものではなく、本実施形態の要旨を逸脱しない範囲内で様々な変更、追加、省略が適用可能である。
【符号の説明】
【０１５２】
１，２，３    画像変換装置
１１    第１行Ｆｏｒｗａｒｄスキャン部
１２    第１行Ｂａｃｋｗａｒｄスキャン部
１３    第１列Ｆｏｒｗａｒｄスキャン部
１４    第１列Ｂａｃｋｗａｒｄスキャン部
２１    第２行Ｆｏｒｗａｒｄスキャン部
２２    第２行Ｂａｃｋｗａｒｄスキャン部
２３    第２列Ｆｏｒｗａｒｄスキャン部
２４    第２列Ｂａｃｋｗａｒｄスキャン部
３１    割り当て部
３２    行方向スキャン部
３３    行Ｆｏｒｗａｒｄスキャン部
３４    行Ｂａｃｋｗａｒｄスキャン部
３５    行方向リダクション部
３６    行方向合算部
３７    列方向スキャン部
３８    列Ｆｏｒｗａｒｄスキャン部
３９    列Ｂａｃｋｗａｒｄスキャン部
４０    列方向リダクション部
４１    列方向合算部
４２    第１記憶部
４３    第２記憶部
１００    バス
１１１    プロセッサ
１１２    メモリ
１１３    補助記憶装置
１１４    通信インタフェース
１１５    媒体接続部
１１６    入力装置
１１７    出力装置
１１８    可搬型記録媒体
【図１】
2020091799.tif 000005
【図２】
2020091799.tif 000006
【図３】
2020091799.tif 000007
【図４】
2020091799.tif 000008
【図５】
2020091799.tif 000009
【図６】
2020091799.tif 000010
【図７】
2020091799.tif 000011
【図８】
2020091799.tif 000012
【図９】
2020091799.tif 000013
【図１０】
2020091799.tif 000014
【図１１】
2020091799.tif 000015
【図１２】
2020091799.tif 000016
【図１３】
2020091799.tif 000017
【図１４】
2020091799.tif 000018
【図１５】
2020091799.tif 000019
【図１６】
2020091799.tif 000020
【図１７】
2020091799.tif 000021
【図１８】
2020091799.tif 000022
【図１９】
2020091799.tif 000023
【図２０】
2020091799.tif 000024
【図２１】
2020091799.tif 000025
【図２２】
2020091799.tif 000026