(57)【要約】【課題】ラスタ走査順に画素を選択して画素値を更新する処理と逆ラスタ走査順に画素を選択して画素値を更新する処理とを含む画像処理を高速に実行することを可能にする。【解決手段】処理対象の画像を構成する複数の画素からラスタ走査順に処理対象の画素を選択し、当該画素の画素値を、当該処理対象の画素および周囲のラスタ処理済画素の画素値を参照して更新するラスタ処理回路４０と、前記複数の画素から逆ラスタ走査順に処理対象の画素を選択し、当該画素の画素値を、当該処理対象の画素および周囲の逆ラスタ処理済画素の画素値を参照して更新する逆ラスタ処理回路５０と、ラスタ処理回路４０と逆ラスタ処理回路５０とを並列に動作させるとともに、両回路の参照する画素の一部が重複する場合に、一方の処理が完了するまで他方の処理の開始を延期するメモリコントローラ２０とを有する画像処理装置１を提供する。【選択図】図１
2015111353.tif 000002
【特許請求の範囲】
【請求項１】
処理対象の画像を構成する複数の画素からラスタ走査順に画素を選択し、当該画素の画素値を、当該画素および周囲のラスタ処理済画素の画素値を参照して更新するラスタ処理回路と、
前記複数の画素から逆ラスタ走査順に画素を選択し、当該画素の画素値を、当該画素および周囲の逆ラスタ処理済画素の画素値を参照して更新する逆ラスタ処理回路と、
を有し、
前記ラスタ処理回路と前記逆ラスタ処理回路とを並列動作させる
ことを特徴とする画像処理装置。
【請求項２】
前記ラスタ処理回路の参照する画素と前記逆ラスタ処理回路の参照する画素の一部が重複する場合に、一方の回路の処理が完了するまで他方の回路の処理の開始を待たせるコントローラをさらに有することを特徴とする請求項１に記載の画像処理装置。
【請求項３】
処理対象の画像を構成する各画素が前記ラスタ処理回路の処理または前記逆ラスタ処理回路の処理を実行済みであるか否かを画素毎に示すフラグを格納するレジスタを含み、
前記ラスタ処理回路と前記逆ラスタ処理回路は、処理対象として選択した画素について前記フラグを参照し、前記何れかの処理が実行済みでなければ所定の前処理を行った後に当該処理回路の処理を行う
ことを特徴とする請求項１または請求項２に記載の画像処理装置。
【請求項４】
前記ラスタ処理回路は距離変換処理におけるラスタ処理を実行する回路であるとともに、前記逆ラスタ処理回路は前記距離変換処理における逆ラスタ処理を実行する回路であり、
前記処理対象の画像は２値画像である
ことを特徴とする請求項１乃至３の何れか１項に記載の画像処理装置。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、画像処理装置に関し、特に、ラスタ走査順に画素を選択して画素値を更新する処理と、逆ラスタ走査順に画素を選択して画素値を更新する処理とを実行する画像処理装置に関する。
【背景技術】
【０００２】
画像認識分野においては、キャプチャした図形がどのような形状であるかを認識する場合に２値化することが多い。例えば、画素値が予め定められた閾値以上の画素についてはその画素値を１に置き換え、画素値が閾値未満の画素についてはその画素値を０に置き換えるといった具合である。これにより、図形内の画素の画素値は１に置き換えられ、背景画素の画素値は０に置き換えられる。２値画像がどのような骨格を持っているのかを認識する場合やエッジ周辺のノイズを除去する場合には、距離変換処理を行うことが効果的である。距離変換処理とは、２値画像の図形内の各画素の画素値を背景画素からの最短距離を表す値に置き換えた距離変換画像を生成する処理である。
【０００３】
距離変換処理は、初期化処理、ラスタ処理、および逆ラスタ処理の３つの処理により構成されている。初期化処理とは、以下の数１に示すように、２値画像を構成する各画素について、画素値ｆ（ｉ，ｊ）が０であるか１であるかを判別し、０であれば距離変換画像において対応する画素の画素値ｄ（ｉ、ｊ）を０に初期化し、１であれば距離変換画像において対応する画素の画素値を０以外の予め定められた最大値に初期化する処理である。例えば、２値化前の画像において各画素値が８ビットで表現されていた場合には、上記最大値として２５５が採用される。なお、添え字ｉは水平走査方向の画素の位置を表し、添え字ｊは垂直走査方向の画素の位置を表す。具体的には、添え字ｉおよびｊの両者が小さいほど左上隅側の画素を表し、逆に、添え字ｉおよびｊの両者が大きいほど右下隅側の画素を表す（数２においても同様）。
【数１】
2015111353.tif 000003
【０００４】
ラスタ処理とは、初期化処理にて生成された距離変換画像ｄの構成画素を左上隅から右下隅に向けて順（すなわち、ラスタ走査順）に走査し（図４(ａ)参照）、処理対象の画素（図４（ａ）では、斜め線のハッチングで表記）の画素値ｄ´（ｉ，ｊ）を、以下の数２にしたがって算出する処理である。数２の右辺のｄ（ｉ，ｊ）は処理対象の画素について初期化処理にて得られた画素値であり、ｄ´（ｉ−１，ｊ）、およびｄ´（ｉ，ｊ−１）は処理対象画素に隣接するラスタ処理済の画素（図４（ａ）では、縦線のハッチングで表記）の画素値である。数２の右辺は、ｄ（ｉ，ｊ） 、ｄ´（ｉ−１，ｊ）＋１、およびｄ´（ｉ，ｊ−１）＋１のうちの最小のものを意味する。なお、図４（ａ）では図形内の画素は点描のハッチングの付与された矩形で表されており、背景画素は白抜きの矩形で表されている。図４（ｂ）は、ラスタ処理の処理結果を表す図である。図４（ｂ）においては、背景画素は白抜きの矩形で表されており、図形内の画素は内部に数字の表記された矩形で表されている。図形内の画素に対応する各矩形内の数字は、下記数２にしたがって算出された画素値ｄ´（ｉ，ｊ）であり、当該画素から見て左側および上側の背景画素までの距離のうちの小さい方を表す。
【数２】
2015111353.tif 000004
【０００５】
逆ラスタ処理とは、ラスタ処理済の距離変換画像ｄ´の構成画素をラスタ処理における走査順とは逆順（すなわち、逆ラスタ走査順）に走査し（図４(ｃ)参照）、処理対象の画素（図４（ｃ）では、斜め線のハッチングで表記）の画素値ｄ´´（ｋ、ｌ）を以下の数３にしたがって算出する処理である。なお、数３における添え字ｋは数２における添え字ｉと同様に水平走査方向の画素の位置を表し、添え字数ｌは数２における添え字ｊと同様に垂直走査方向の画素の位置を表す（後述する数４においても同様）。また、数３の右辺のｄ´（ｋ、ｌ）はラスタ処理にて得られた画素値であり、ｄ´´（ｋ＋１，ｌ）、およびｄ´´（ｋ，ｌ＋１）は処理対象画素に隣接する逆ラスタ処理済の画素（図４（ｃ）では、横線のハッチングで表記）の画素値である。図４（ｄ）は、逆ラスタ処理の処理結果を表す図である。図４（ｄ）においても背景画素は白抜きの矩形で表されており、図形内の画素は内部に数字の表記された矩形で表されている。図形内の画素に対応する各矩形内の数字は、下記数３にしたがって算出された画素値ｄ´´（ｋ，ｌ）であり、当該画素から見て右側、左側、上側および下側の各背景画素までの距離のうちの最小値を表す。以上説明したように、距離変換処理では、ｄ→ｄ´→ｄ´´と画素値が更新されることで最後に距離変換画像ｄ´´が得られる。なお、距離変換処理に関する先行技術の一例としては、特許文献１および特許文献２が挙げられる。
【数３】
2015111353.tif 000005
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特開昭６２−２００７７号公報
【特許文献２】特公平４−６２１０４号公報
【発明の概要】
【発明が解決しようとする課題】
【０００７】
従来の距離変換処理では、画像全体の初期化処理の際に２値画像を表す画像データ全体をメモリから読み出して数１に基づいて距離変換画像を生成する必要があるため、初期化処理に時間がかかるといった問題や、距離変換処理を構成する３つの処理をシーケンシャルに実行する必要があるため、処理時間がかかるといった問題があった。このため、距離変換処理は、リアルタイム処理が必要とされる場合に大きな問題となっていた。このような問題は、距離変換処理において典型的であるが、ラスタ走査順に画素を選択して画素値を更新する処理と逆ラスタ走査順に画素を選択して画素値を更新する処理とを含み、一方の処理の処理結果を他方において利用する画像処理であれば、同様の問題が発生する。
【０００８】
本発明は以上に説明した課題に鑑みて為されたものであり、ラスタ走査順に画素を選択して画素値を更新する処理と逆ラスタ走査順に画素を選択して画素値を更新する処理とを含む画像処理を高速に実行することを可能にする技術を提供することを目的とする。
【課題を解決するための手段】
【０００９】
上記課題を解決するために本発明は、処理対象の画像を構成する複数の画素からラスタ走査順に画素を選択し、当該画素の画素値を、当該画素および周囲のラスタ処理済画素の画素値を参照して更新するラスタ処理回路と、前記複数の画素から逆ラスタ走査順に画素を選択し、当該画素の画素値を、当該画素および周囲の逆ラスタ処理済画素の画素値を参照して更新する逆ラスタ処理回路と、を有し、前記ラスタ処理回路と前記逆ラスタ処理回路とを並列動作させることを特徴とする画像処理装置、を提供する。
【００１０】
本発明によれば、ラスタ処理回路による処理（すなわち、ラスタ走査順に画素を選択して画素値を更新する処理）と逆ラスタ処理回路による処理（すなわち、逆ラスタ走査順に画素を選択して画素値を更新する処理）とが並列に実行されるため、これらの処理をシーケンシャルに実行する場合に比較して全体の処理時間が短くなる。このように本発明によれば、ラスタ走査順に画素を選択して画素値を更新する処理と逆ラスタ走査順に画素を選択して画素値を更新する処理とを含む画像処理を高速化することが可能になる。
【００１１】
より好ましい態様においては、前記ラスタ処理回路の参照する画素と前記逆ラスタ処理回路の参照する画素の一部が重複する場合に、一方の回路の処理が完了するまで他方の回路の処理の開始を待たせるコントローラをさらに有することを特徴とする。このような態様においては、ラスタ処理回路の参照する画素と逆ラスタ処理回路の参照する画素の一部が重複する場合には一方の回路の処理が完了するまで他方の回路の処理の開始がコントローラによって延期されるため、所謂リード・モディファイ・ライトの問題が発生することを回避することができる。
【００１２】
さらに別の好ましい態様においては、処理対象の画像を構成する各画素が前記ラスタ処理回路の処理または前記逆ラスタ処理回路の処理を実行済みであるか否かを画素毎に示すフラグを格納するレジスタを含み、前記ラスタ処理回路と前記逆ラスタ処理回路は、処理対象として選択した画素について前記フラグを参照し、前記何れかの処理が実行済みでなければ所定の前処理を行った後に当該処理回路の処理を行うことを特徴とする。このような態様によれば、ラスタ処理回路および逆ラスタ処理回路による処理に先立って何らかの前処理を行う必要のある画像処理（例えば、前述した距離変換処理）においてサイズの大きな画像を処理対象とする場合に、当該前処理を実行済の画像データを別個に生成する態様に比較して全体の処理時間を短くすることが可能になる。
【００１３】
ここで、ラスタ処理回路による処理の具体例としては距離変換処理におけるラスタ処理が挙げられる。同様に、逆ラスタ処理回路による処理の具体例としては距離変換処理における逆ラスタ処理が挙げられる。この場合、処理対象の画像は２値画像である。このような態様によれば、従来よりも高速に距離変換処理を実行することが可能になる。
【図面の簡単な説明】
【００１４】
【図１】本発明の一実施形態の画像処理装置１の構成例を示す図である。
【図２】同画像処理装置１の動作を説明するための図である。
【図３】ラスタ処理において画素値が更新または参照される画素と逆ラスタ処理にて画素値が更新または参照される画素の重複パターンを示す図である。
【図４】距離変換処理を説明するための図である。
【発明を実施するための形態】
【００１５】
以下、図面を参照しつつ、本発明の実施形態について説明する。
図１は、本発明の一実施形態の画像処理装置１の構成例を示すブロック図である。画像処理装置１は、画像認識装置に組み込まれる画像処理ＬＳＩであり、画像認識の対象の２値画像データに距離変換処理を施し、後段の画像認識回路（図１では図示略）に与える。図１に示すように、画像処理装置１は、メモリ１０、メモリコントローラ２０、メモリＩ／Ｆ部３０Ａおよび３０Ｂ、ラスタ処理回路４０、逆ラスタ処理回路５０を含んでいる。
【００１６】
メモリ１０は例えばＲＡＭなどの揮発性メモリである。メモリ１０には、距離変換処理の処理対象となる２値画像データｆが格納される。また、メモリ１０は、２値画像データｆに距離変換処理を施すことにより得られた距離変換画像データを格納する役割も担っている。本発明では、メモリ１０内の２値画像データｆとは別に距離変換画像データを作成する。すなわち、２値画像データｆの各画素の画素値を参照して、距離変換画像データの対応する画素の画素値を前掲数１に示す処理と同じ処理である前処理により算出する。距離変換の過程において、前処理、ラスタ処理、逆ラスタ処理が行われ、これらの処理が全て終了した時点で距離変換画像データが完成する。言い換えると、距離変換画像データの各画素の画素値は各処理により順次更新され、最後に距離変換画像データがメモリ１０内で完成する。メモリ１０には、メモリ１０からの画素値の読み出し、およびメモリ１０への画素値の書き込みを制御するメモリコントローラ２０が接続されている。そして、メモリコントローラ２０には、メモリＩ／Ｆ部３０Ａを介してラスタ処理回路４０が接続されているとともに、メモリＩ／Ｆ部３０Ｂを介して逆ラスタ処理回路５０が接続されている。
【００１７】
メモリコントローラ２０は、例えばＣＰＵ（Central Processing Unit）とレジスタとを含んでいる。メモリコントローラ２０のＣＰＵはアービトレーション処理２１０およびアドレスチェック処理２２０を実行する。レジスタには、距離変換対象の２値化画像データｆを構成する各画素について従来の距離変換処理における初期化処理と同等の処理を完了しているか否かを示すフラグＡｃｃ＿ｆｌａｇが格納される。例えば、距離変換処理の処理対象の２値画像データｆがｙピクセル×ｘピクセルのサイズを有する場合、フラグＡｃｃ＿ｆｌａｇのデータサイズは１ビット×ｙ×ｘとなる。
【００１８】
従来の距離変換処理では、前掲数１に示す初期化処理を行うためにメモリ１０から処理対象の２値画像データｆを読み出し、０／１を判定後、０または最大値を中間結果（すなわち、距離変換画像データｄ（ｉ，ｊ））として再びメモリへ書き込み、２値画像データｆとは別の距離変換画像データｄを作成する処理が行われており、この初期化処理のみでかなりの処理時間がかかっていた。
【００１９】
これに対して、本実施形態の画像処理装置１では、メモリコントローラ２０内に距離変換画像データの各画素に対して書き込み（ラスタ処理または逆ラスタ処理による画素値の更新）を行ったかどうかを示す１ビットのフラグＡｃｃ＿ｆｌａｇがレジスタで実装されている。フラグＡｃｃ＿ｆｌａｇの初期化（すべて０にリセットすること）は通常１サイクルで終了する。Ａｃｃ＿ｆｌａｇ[ｉ] [ｊ]＝０である場合は、前掲数１に示す処理と同じ処理である前処理が行われていないことも意味する。
【００２０】
ラスタ処理回路４０は、メモリＩ／Ｆ部３０Ａおよびメモリコントローラ２０を介してメモリ１０から２値画像データｆまたは逆ラスタ処理済の距離変換画像データを読み出し、従来の距離変換処理におけるラスタ処理を実行する回路である。一方、逆ラスタ処理回路５０は、メモリＩ／Ｆ部３０Ｂおよびメモリコントローラ２０を介してメモリ１０から２値画像データｆまたはラスタ処理済の距離変換画像データを読み出し、従来の距離変換処理における逆ラスタ処理を実行する回路である。このように、ラスタ処理を実行する回路と逆ラスタ処理を実行する回路とを各々別個のハードウェアとして設けた点、およびこれら２つの回路を並列に動作させる点に本実施形態の特徴がある（図４（ｅ）参照）。
【００２１】
ラスタ処理回路４０は、２値画像データｆの左上隅から右下隅までラスタ走査順に処理対象画素を一画素ずつ選択し、その処理対象画素についてのフラグＡｃｃ＿ｆｌａｇ[ｉ] [ｊ]を参照する。フラグＡｃｃ＿ｆｌａｇ[ｉ] [ｊ]＝０であれば、ラスタ処理回路４０は、処理対象画素の画素値を表す画素データｆ（ｉ，ｊ）を読み出し、前掲数１に示す処理と同じ処理である前処理を実行した後に前掲数２に示す要領で、距離変換画像の画素値を表す画素データｄ´（ｉ，ｊ）を求め、距離変換画像データへ書き込み、さらにフラグＡｃｃ＿ｆｌａｇ[ｉ] [ｊ]に１をセットする。これに対して、フラグＡｃｃ＿ｆｌａｇ[ｉ] [ｊ]＝１であれば、ラスタ処理回路４０は、処理対象画素の距離変換画像データ上の逆ラスタ処理済の画素データを数２右辺のｄ（ｉ、ｊ）として用い、前掲数２に示す要領で画素データｄ´（ｉ，ｊ）に更新する処理のみを実行する。本実施形態では、フラグＡｃｃ＿ｆｌａｇ[ｉ] [ｊ]の０から１への更新はラスタ処理回路４０と逆ラスタ処理回路５０の何れかによって行われる。ラスタ処理回路４０の実行するラスタ処理において処理対象画素のフラグＡｃｃ＿ｆｌａｇ[ｉ] [ｊ]が１になっているということは、当該処理対象画素について逆ラスタ処理回路５０による逆ラスタ処理を実行済みであることを意味する。つまり、フラグＡｃｃ＿ｆｌａｇ[ｉ] [ｊ]＝１の場合にラスタ処理回路４０により読み出される処理対象画素の画素データは、距離変換画像データ上の逆ラスタ処理済の画素データである。したがって、ラスタ処理回路４０によるラスタ処理においてフラグＡｃｃ＿ｆｌａｇ[ｉ] [ｊ]＝１となっている画素については逆ラスタ処理→ラスタ処理の順に処理が施されることになる。
【００２２】
逆ラスタ処理回路５０は、２値画像データｆの右下隅から左上隅まで逆ラスタ走査順に処理対象画素を一画素ずつ選択し、その処理対象画素についてのフラグＡｃｃ＿ｆｌａｇ[ｋ] [ｌ]を参照する。フラグＡｃｃ＿ｆｌａｇ[ｋ] [ｌ]＝０であれば、逆ラスタ処理回路５０は、処理対象画素の画素値を表す画素データｆ（ｉ，ｊ）を読み出し、前掲数１に示す処理と同じ処理である前処理を実行した後に、以下の数４に示す要領で、距離変換画像の画素値を表す画素データｄ´（ｋ，ｌ）を求め、距離変換画像データへ書き込み、さらにフラグＡｃｃ＿ｆｌａｇ[ｋ] [ｌ]に１をセットする。これに対して、フラグＡｃｃ＿ｆｌａｇ[ｋ] [ｌ]＝１であれば、逆ラスタ処理回路５０は、処理対象画素の距離変換画像データ上のラスタ処理済の画素データを数４の右辺のｄ（ｋ、ｌ）として用い、数４に示す要領で画素データｄ´（ｋ，ｌ）に更新する処理のみを実行する。逆ラスタ処理回路５０の実行する逆ラスタ処理において処理対象画素のフラグＡｃｃ＿ｆｌａｇ[ｉ] [ｊ]が１になっているということは、当該処理対象画素についてラスタ処理回路４０によるラスタ処理を実行済みであることを意味する。つまり、フラグＡｃｃ＿ｆｌａｇ[ｉ] [ｊ]＝１の場合に逆ラスタ処理回路５０により読み出される処理対象画素の画素データは、距離変換画像データ上のラスタ処理済の画素データである。したがって、逆ラスタ処理回路５０による逆ラスタ処理においてフラグＡｃｃ＿ｆｌａｇ[ｉ] [ｊ]＝１となっている画素についてはラスタ処理→逆ラスタ処理の順に処理が施されることになる。
【数４】
2015111353.tif 000006
【００２３】
本実施形態では、ラスタ処理回路４０と逆ラスタ処理回路５０とをメモリコントローラ２０による制御の下で並列に動作させる。つまり、本実施形態では、図４（ｅ）に示すように、距離変換処理の処理対象となる２値画像データｆに対してその左上隅の画素から右下隅の画素へ向けてラスタ走査順にラスタ処理回路４０による処理が一画素ずつ施されるのと同時に、右下隅の画素から左上隅の画素へ向けて逆ラスタ走査順に逆ラスタ処理回路５０による処理が一画素ずつ施される。したがって、本実施形態においては、ラスタ処理を施された後に逆ラスタ処理を施される画素と逆ラスタ処理を施された後にラスタ処理を施される画素とが１つの距離変換画像の中に混在することとなる。ラスタ処理においては、処理に使用される３つの画素が逆ラスタ処理を施されたものであるかどうかに関係なく、それら３つの画素の画素値に基づいて処理対象画素の画素値が算出される。同様に逆ラスタ処理においては、処理に使用される３つの画素がラスタ処理を施されたものであるかどうかに関係なく、それら３つの画素の画素値に基づいて処理対象画素の画素値が算出される。ラスタ処理と逆ラスタ処理は、ある画素においてどちらを先に実行したとしても処理結果に違いが生じることはなく、特段の問題は生じない。
【００２４】
ラスタ処理回路４０による処理速度と逆ラスタ処理回路５０による処理速度とが同じであれば、処理対象となる２値画像データｆの中央付近の画素において両回路による処理が競合することとなり、内容の不定な書き込み（所謂、リード・モディファイ・ライト：以下、ＲＭＷ）の問題に配慮する必要がある。アービトレーション処理２１０およびアドレスチェック処理２２０は、この問題の回避のための処理である。
【００２５】
より詳細に説明すると、ラスタ処理回路４０は、処理対象画素の２値画像データｆ上のアドレスまたは距離変換画像データｄ上のアドレスおよび当該処理対象画素の隣接画素の各々の距離変換画像データｄ上のアドレスをメモリコントローラ２０へ通知し画素値の読み出しを指示する。例えば、処理対象画素がｉ行ｊ列目の画素である場合、ラスタ処理回路４０は、２値画像データｆまたは距離変換画像データｄ上のｉ行ｊ列目、距離変換画像データｄ上のｉ−１行ｊ列目およびｉ行ｊ−１列目の各画素のアドレスをメモリコントローラ２０へ通知し画素値の読み出しを指示する。これに加え、ラスタ処理回路４０は、これらの画素値の読み出し指示を与えた時点から処理対象画素の画素値を数２に示すｄ´（ｉ、ｊ）に更新するまでのサイクルをＲＭＷサイクルとし、メモリコントローラ２０のレジスタに格納されたＲＭＷｆｌａｇ１に１をセットする。同様に、逆ラスタ処理回路５０は、処理対象画素の２値画像データｆ上のアドレスまたは距離変換画像データｄ上のアドレスおよび当該処理対象画素の隣接画素の各々の距離変換画像データｄ上のアドレスをメモリコントローラ２０へ通知し画素値の読み出しを指示するとともに、当該指示を与えた時点から処理対象画素の画素値の更新が完了するまでのサイクルをＲＭＷサイクルとし、メモリコントローラ２０のレジスタに格納されたＲＭＷｆｌａｇ２に１をセットする。例えば、逆ラスタ処理回路５０の処理対象画素がｋ行ｌ列目の画素である場合、逆ラスタ処理回路５０は、２値画像データｆまたは距離変換画像データｄ上のｋ行ｌ列目、距離変換画像データｄ上のｋ＋１行ｌ列目およびｋ行ｌ＋１列目の各画素のアドレスをメモリコントローラ２０へ通知し、処理対象画素の画素値を数４に示すｄ´（ｋ、ｌ）に更新するまでＲＭＷｆｌａｇ２を１に維持する。
【００２６】
メモリコントローラ２０はラスタ処理回路４０と逆ラスタ処理回路５０とを並列に動作させる。このとき、メモリコントローラ２０はラスタ処理回路４０と逆ラスタ処理回路５０からのメモリアクセス要求（すなわち、画素値の読み出し）に対して調停を行う。より詳細に説明すると、メモリコントローラ２０のＣＰＵ（図示略）は、ラスタ処理回路４０から出力されたアドレスおよびＲＭＷｆｌａｇ１と、逆ラスタ処理回路５０から出力されたアドレスおよびＲＭＷｆｌａｇ２とを受け取り、一方のＲＭＷサイクルにおける処理対象画素と他方のＲＭＷサイクルにおける処理対象画素とが重複しているか否か（すなわち、両ＲＭＷサイクルにおける処理対象画素のアドレスが衝突しているか否か）をチェックする。例えば、２値画像データｆ上のｉ行ｊ列の画素に対して画素値の読み出し要求が発せられ、その後に距離変換画像データｄ上のｉ行ｊ列の画素に対して画素値の読み出し要求が発せられた場合は、メモリアドレスは同じではないが、ｉ行ｊ列が同じため、衝突が発生したと判断する。このチェック処理が図１におけるアドレスチェック処理２２０である。そして、ＣＰＵは、アドレスチェック処理２２０により処理対象画素のアドレスの衝突を検出した場合には、先行するＲＭＷサイクルが終了するまで他方のメモリアクセスを待たせる処理（図１におけるアービトレーション処理２１０）を実行する。
【００２７】
例えば、図２には、ラスタ処理回路４０の処理対象画素（図２に示す例ではｉ行ｊ列目の画素）と、逆ラスタ処理回路５０の処理対象画素（図２に示す例では、ｋ行ｌ列目の画素）とが重複している場合（図３（ａ）参照）について例示されている。図２に示す例では、ラスタ処理回路４０のＲＭＷサイクルが先にスタートしている。このため、逆ラスタ処理回路５０による逆ラスタ処理は、ラスタ処理回路４０によるＲＭＷサイクルが完了するまでのその開始が待たされる。すなわち、ラスタ処理回路４０による画素値の読み出しおよび処理対象画素の画素値の更新が完了した後に、逆ラスタ処理回路５０による画素値の読み出しおよび処理対象画素の画素値の更新が行われる。
【００２８】
以上説明したように、本実施形態の画像処理装置１では、ラスタ処理と逆ラスタ処理とが並列に実行されるため、これらをシーケンシャルに実行する従来の距離変換処理に比較して処理全体に要する処理時間が短くなる。なお、本実施形態では、ラスタ処理と逆ラスタ処理とが並列に実行されるのであるが、メモリコントローラ２０による調停が為されるため、両処理における処理対象画素が重複していたとしても、リード・モディファイ・ライトの問題が発生することはない。また、本実施形態では、従来の距離変換処理における初期化処理と同等の処理である前処理が、レジスタに格納されたフラグＡｃｃ＿ｆｌａｇを用いてラスタ処理および逆ラスタ処理の一部として実行される。つまり、０または最大値を距離変換画像データｄに書き込まない。この点からも本実施形態によれば、従来の距離変換処理に比較して処理全体に要する処理時間が短くなる。つまり、本実施形態によれば、距離変換処理を従来よりも高速に実行することが可能になる。
【００２９】
以上本発明の一実施形態について説明したが、この実施形態に以下の変形を加えても勿論良い。
（１）上記実施形態では、ラスタ処理および逆ラスタ処理の両者に前処理が含まれていた。しかし、前処理については、従来の距離変換処理と同様に、ラスタ処理や逆ラスタ処理とは別個にこれらに先行して実行される処理とし、この前処理の実行後に、ラスタ処理と逆ラスタ処理とを並列に実行するようにしても良い。このような態様であっても、ラスタ処理と逆ラスタ処理とが並列に実行される分だけ、ラスタ処理と逆ラスタ処理とをシーケンシャルに実行する従来の距離変換処理に比較して高速化することができる。
【００３０】
（２）上記実施形態では、距離変換処理への適用例を説明したが本発明の適用対象は距離変換処理に限定される訳ではない。要は、処理対象の画像を構成する複数の画素からラスタ走査順に画素を選択し、当該画素の画素値を、当該画素および周囲のラスタ処理済画素の画素値を参照して更新するラスタ処理と、当該複数の画素から逆ラスタ走査順に画素を選択し、当該画素の画素値を、当該画素および周囲の逆ラスタ処理済画素の画素値を参照して更新する逆ラスタ処理とを含み、かつ両者の実行順序を入れ替えても結果に違いが生じない画像処理であれば、本発明を適用することで高速化することができる。また、両者の実行順序を入れ替えることにより処理結果に相違が生じる場合であっても、その相違が無視し得る程度のものであれば、本発明の適用による高速化を行っても良い。
【００３１】
（３）上記実施形態では、ラスタ処理回路４０の処理対象画素と逆ラスタ処理回路５０による処理対象画素とが重複する場合（図３（ａ）参照）に、メモリアクセス要求についての調停をメモリコントローラ２０に行わせる場合について説明した。これは、距離変換処理におけるラスタ処理（数２に示す画素値の更新処理）および逆ラスタ処理（数４に示す画素値の更新処理）では、少なくとも処理対象画素が重複する場合にＲＭＷの問題が発生するからである。
【００３２】
しかし、より一般的なラスタ処理および逆ラスタ処理を含む画像処理への本発明の適用を可能にするため、以下の要領でメモリアクセス要求の調停を行っても良い。すなわち、ラスタ処理および逆ラスタ処理のうちの先行する方において画素値の更新または参照が行われる画素と他方の処理において画素値の更新または参照が行われる画素の一部が重複する場合（例えば、図３（ａ）〜図３（ｆ）に示す各場合）に、先行する方の処理による画素値の更新が完了した後に、他方の処理による画素値の読み出しおよび更新が行われるようにメモリアクセス要求についての調停を行うのである。但し、重複する画素について画素値の参照のみが行われる場合（例えば、図３（ｃ）、図３（ｅ）および図３（ｆ）に示す各場合）には、メモリアクセス要求の調停を行う必要はなく、このような重複パターンをメモリアクセス要求の調停の対象から除外しても勿論良い。
【００３３】
（４）上記実施形態では、２値画像データｆと距離変換画像データｄとは別別の画像データとして記述している。しかし、２値画像データｆの各画素の画素値を逐次更新することで、更新した結果として２値画像データｆが距離変換画像データｄに変換されるケースも上記実施形態の記載から自明なことである。
【符号の説明】
【００３４】
１…画像処理装置、１０…メモリ、２０…メモリコントローラ、２１０…アービトレーション処理、２２０…アドレスチェック処理、３０Ａ，３０Ｂ…メモリＩ／Ｆ部、４０…ラスタ処理回路、５０…逆ラスタ処理回路。
【図１】
2015111353.tif 000007
【図２】
2015111353.tif 000008
【図３】
2015111353.tif 000009
【図４】
2015111353.tif 000010