(57)【特許請求の範囲】
【請求項１】
多数の画素で構成された２次元画面上に、線分の始点と終点を指定し、前記始点から終点に向かって、線分を構成する画面各行の走査方向線分を求めて線分を描画する線分描画処理方法において、
走査方向に対する線分の傾きが所定値以下か否か判断し、
前記線分の傾きが所定値以下の場合には、線分を構成する画面各行の走査方向線分の開始画素から二分探索を行って該走査方向線分の終端画素を探索し、
前記線分の傾きが所定値以下でない場合には、線分を構成する画面各行の走査方向線分の開始画素から１画素ずつ探索を行う、線型探索を行って該走査方向線分の終端画素を探索する、
ことを特徴とする線分描画処理方法。
【請求項２】
画面走査方向をｘ方向とし、線分の始点終点のｘ方向差分ｄｘ、ｙ方向差分ｄｙとし、
線分の傾きｄｙ／ｄｘを計算して、ｄｙ／ｄｘ≦αを満足するか判断し、満足する場合に二分探索を適用することを特徴とする請求項１に記載の線分描画処理方法。
【請求項３】
所定値αは少なくとも１／８以下の値とすることを特徴とする請求項２に記載の線分描画処理方法。
【請求項４】
二分探索では、現在着目している画素の位置をｘ方向にΔｘｐ移動させて、移動後の画素での誤差ｅｐ＝Δｘｐ＊ｄｙ／ｄｘを計算し、誤差ｅｐが１≦ｅｐ＜２ならば、該移動後の画素を走査方向線分の終端画素とし、
誤差ｅｐが０＜ｅｐ＜１ならば、Δｘｐ←１／２＊Δｘｐとして、当該画素をｘ座標が大になる方向に更に移動させ、誤差ｅｐがｅｐ≧２ならば、Δｘｐ←１／２＊Δｘｐとして、当該画素をｘ座標が小になる方向に更に移動させ、これを１≦ｅｐ＜２になるまで繰り返す、
ことを特徴とする請求項２あるいは３に記載の線分描画処理方法。
【請求項５】
画面走査方向をｘ方向とし、線分の始点終点のｘ方向差分ｄｘ、ｙ方向差分ｄｙとし、
２ｋ＊ｄｙ≦ｄｘ（ｋは定数）を満足するか判断し、満足する場合に二分探索を適用することを特徴とする請求項１に記載の線分描画処理方法。
【請求項６】
定数ｋは少なくとも３以上の値とすることを特徴とする請求項５に記載の線分描画処理方法。
【請求項７】
二分探索では、現在着目している画素の位置をｘ方向にΔｘｐ移動させて、移動後の画素での誤差Ｅｐ＝Δｘｐ＊ｄｙを計算し、誤差Ｅｐがｄｘ≦Ｅｐ＜２＊ｄｘならば、該移動後の画素を走査方向線分の終端画素とし、
誤差Ｅｐが０＜Ｅｐ＜ｄｘならば、Δｘｐ←１／２＊Δｘｐとして、当該画素をｘ座標が大になる方向に更に移動させ、誤差ＥｐがＥｐ≧２＊ｄｘならば、Δｘｐ←１／２＊Δｘｐとして、当該画素をｘ座標が小になる方向に更に移動させ、これをｄｘ≦Ｅｐ＜２＊Δｘｐになるまで繰り返す、
ことを特徴とする請求項５あるいは６に記載の線分描画処理方法。
【請求項８】
ｘ方向移動量Δｘｐの初期値は、少なくとも画面のｘ方向の画素数の半分以上の値とすることを特徴とする請求項４あるいは７に記載の線分描画処理方法。
【請求項９】
ｘ方向移動量Δｘｐの初期値の値を、処理対象行が線分の終点の行に近づくに従って徐々に減少させることを特徴とする請求項８に記載の線分描画処理方法。
【請求項１０】
請求項１乃至９のいずれか１項に記載の線分描画処理方法を実施することを特徴とする線分描画処理装置。
【請求項１１】
撮像装置で撮影された撮像画像を処理する画像処理手段と、線分を生成する線分処理手段と、前記撮像画像に前記線分を重畳した合成画像を生成する合成手段と、前記合成画像を表示する表示手段からなる線分描画処理装置において、
前記線分処理手段は、請求項１０に記載の線分描画処理装置からなることを特徴とする撮像画像処理装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、撮影した画像に任意の線分を重畳表示させる場合などに好適な線分描画処理方法及び装置、並びにそれを適用した撮像画像処理装置に関する。
【背景技術】
【０００２】
カメラなど撮像装置の機能の一つとして、撮影した画像に任意の線分を重畳表示させて、ユーザの操作等を支援する機能が今日では一般的になっている。例えば、車載カメラでは、車両の後方等を撮影した画像に重畳して、車幅線を表示することが行われている。
【０００３】
従来から、デジタル座標平面上の任意の２点で結ばられる線分上の各点（画素）を求めるアルゴリズムの一つとしてブレゼンハム方式がある。このブレゼンハム方式は乗算・除算を必要せず、加減算のみで線分を描画できるため、適用範囲の広いアルゴリズムとして知られている。
【０００４】
ブレゼンハム方式では、線分を構成する画面各行の走査方向線分を求める処理が行われる。これは、具体的には走査方向線分の開始画素から終端画素を探索する処理である。この場合、従来のブレゼンハム方式では、走査方向線分の開始画素から終端画素を探索するのに、１画素ずつ探索を行う、いわゆる線型探索を用い、当該画素が終端画素かどうかは誤差項という値を求め、これを閾値と比較することにより行っていた。しかしながら、１画素ずつの線型探索では、走査方向線分が長い場合は探索時間が多くかかり、全体として処理時間が長くなる問題があった。
【０００５】
また、プレゼン方式の変形例として線分の描画をブロック単位で処理し、各ブロック毎にその描画開始点の座標値と誤差項を独立に計算することで、処理時間の短縮を可能にした方法も提案されている（特許文献１）。しかし、この方法も各ブロック領域内の線分描画処理はブレゼンハムアルゴリズムを適用しているため、処理時間の短縮には限界があり、また、除算を用いてブロックの描画開始点の誤差項を求めているため、逆にブレゼンハム方式の利点を損なう問題がある。
【発明の概要】
【発明が解決しようとする課題】
【０００６】
ユーザの操作等を支援するため、撮影した画像に重畳して表示させる線分などの場合、傾きが小さい線分であることが多い。
【０００７】
本発明は、傾きが特に小さい線分の描画処理時間の短縮が可能になる線分描画処理方法及び装置、並びにそれを適用した画像処理装置を提供することを目的とする。
【０００８】
さらに、本発明は、リソースが複雑になる除算は行わずに、小リソース環境で線分の描画処理を実現する線分描画処理方法及び装置、並びにそれを適用した撮像画像処理装置を提供することを目的とする。
【課題を解決するための手段】
【０００９】
請求項１の発明は、多数の画素で構成された２次元画面上に、線分の始点と終点を指定し、前記始点から終点に向かって、線分を構成する画面各行の走査方向線分を求めて線分を描画する線分描画処理方法において、走査方向に対する線分の傾きが所定値以下か否か判断し、前記線分の傾きが所定値以下の場合には、線分を構成する画面各行の走査方向線分の開始画素から二分探索を行って該走査方向線分の終端画素を探索し、前記線分の傾きが所定値以下でない場合には、線分を構成する画面各行の走査方向線分の開始画素から１画素ずつ探索を行う、線型探索を行って該走査方向線分の終端画素を探索することを特徴とする。
【００１０】
請求項２の発明は、請求項１に記載の線分描画処理方法において、画面走査方向をｘ方向とし、線分の始点終点のｘ方向差分ｄｘ、ｙ方向差分ｄｙとし、線分の傾きｄｙ／ｄｘを計算して、ｄｙ／ｄｘ≦αを満足するか判断し、満足する場合に二分探索を適用することを特徴とする。
【００１１】
請求項３の発明は、請求項２に記載の線分描画処理方法において、所定値αは少なくとも１／８以下の値とすることを特徴とする。
【００１２】
請求項４の発明は、請求項２あるいは３に記載の線分描画処理方法において、二分探索では、現在着目している画素の位置をｘ方向にΔｘｐ移動させて、移動後の画素での誤差ｅｐ＝Δｘｐ＊ｄｙ／ｄｘを計算し、誤差ｅｐが１≦ｅｐ＜２ならば、該移動後の画素を走査方向線分の終端画素とし、誤差ｅｐが０＜ｅｐ＜１ならば、Δｘｐ←１／２＊Δｘｐとして、当該画素をｘ座標が大になる方向に更に移動させ、誤差ｅｐがｅｐ≧２ならば、Δｘｐ←１／２＊Δｘｐとして、当該画素をｘ座標が小になる方向に更に移動させ、これを１≦ｅｐ＜２になるまで繰り返す、ことを特徴とする。
【００１３】
請求項５の発明は、請求項１に記載の線分描画処理方法において、画面走査方向をｘ方向とし、線分の始点終点のｘ方向差分ｄｘ、ｙ方向差分ｄｙとし、２ｋ＊ｄｙ≦ｄｘ（ｋは定数）を満足するか判断し、満足する場合に二分探索を適用することを特徴とする。
【００１４】
請求項６の発明は、請求項５に記載の線分描画処理方法において、定数ｋは少なくとも３以上の値とすることを特徴とする。
【００１５】
請求項７の発明は、請求項５あるいは６に記載の線分描画処理方法において、二分探索では、現在着目している画素の位置をｘ方向にΔｘｐ移動させて、移動後の画素での誤差Ｅｐ＝Δｘｐ＊ｄｙを計算し、誤差Ｅｐがｄｘ≦Ｅｐ＜２＊ｄｘならば、該移動後の画素を走査方向線分の終端画素とし、誤差Ｅｐが０＜Ｅｐ＜ｄｘならば、Δｘｐ←１／２＊Δｘｐとして、当該画素をｘ座標が大になる方向に更に移動させ、誤差ＥｐがＥｐ≧２＊ｄｘならば、Δｘｐ←１／２＊Δｘｐとして、当該画素をｘ座標が小になる方向に更に移動させ、これをｄｘ≦Ｅｐ＜２＊Δｘｐになるまで繰り返す、ことを特徴とする。
【００１６】
請求項８の発明は、請求項４あるいは７に記載の線分描画処理方法において、ｘ方向移動量Δｘｐの初期値は、少なくとも画面のｘ方向の画素数の半分以上の値とすることを特徴とする。
【００１７】
請求項９の発明は、請求項８に記載の線分描画処理方法において、ｘ方向移動量Δｘｐの初期値の値を、処理対象行が線分の終点の行に近づくに従って徐々に減少させることを特徴とする。
【００１８】
請求項１０の発明は、請求項１乃至９のいずれか１項に記載の線分描画処理方法を実施する線分描画処理装置を特徴とする。
【００１９】
請求項１１の発明は、撮像装置で撮影された撮像画像を処理する画像処理手段と、線分を生成する線分処理手段と、前記撮像画像に前記線分を重畳した合成画像を生成する合成手段と、前記合成画像を表示する表示手段からなる線分描画処理装置において、前記線分処理手段は、請求項１０に記載の線分描画処理装置からなることを特徴とする。
【発明の効果】
【００２０】
本発明では、傾きが特に小さい線分の場合、線分を構成する画面各行の走査方向線分にの開始画素から終端画素を探索する処理に、線型探索でなく二分探索を行うことで、処理時間を短縮することができる。また、Δｘ，Δｙを比較することで直線の傾きの大きさを判定し、新たな誤差Ｅｐを定義することで、除算を不要とし、小リソース環境の低コストで線分の描画処理が可能になる。なお、本発明のこれ以外の更なる作用効果は、以下の実施例の説明で明らかになる。
【図面の簡単な説明】
【００２１】
【図１】本発明の線分描画処理機能を適用した撮像画像処理装置の一実施例の全体構成図である。
【図２】本発明の線分描画処理方法の考え方を説明する図である。
【図３】本発明の線分描画処理方法の基本的処理フローを示す図である。
【図４】本発明で利用される二分探索の具体的処理イメージを示す図である。
【図５】本発明が適用可能な種々の傾きの線分の一例を示す図である。
【図６】図１の線分処理部の全体的処理フローを示す図である。
【図７】図６中のＶsync処理の概略処理フローを示す図である。
【図８】図６中のＨref処理の概略処理フローを示す図である。
【図９】図８中の二分探索処理の詳細処理フローを示す図である。
【図１０】処理対象線分が複数の場合のＶsync処理の概略処理フローを示す図である。
【図１１】処理対象線分が複数の場合のＨref処理の概略処理フローを示す図である。
【図１２】種々の傾きの線分について線型探索と二分探索の命令数を比較した表である。
【発明を実施するための形態】
【００２２】
はじめに、本発明の線分描画処理方法について説明する。いま、図２（ａ）のように、多数の画素（ピクセル）から構成されたｘｙ座標平面（画面）上に、始点Ａと終点Ｂを結ぶ線分１を、該線分を構成する画面各行の走査方向線分を求める処理を繰り返し行って描画する場合を考える。始点Ａの座標を（ｘｓ，ｙｓ）、終点Ｂの座標を（ｘｅ，ｙｅ）とし、画面走査方向はｘ方向とする。線分１の傾きｄｙ／ｄｘは（ｙｅ−ｙｓ）／（ｘｅ−ｘｓ）で表わされる。この傾きｄｙ／ｄｘを所定値αと比較する。αについては後述するが、例えばαは１／８程度が適当である。ここで、ｄｙ／ｄｘ＞αの場合（描画する線分の傾きが大きい）は、線分１を構成する画面各行の走査方向線分を求めるのに、従来のブレゼンハム方式などのアルゴリズムを適用し、走査方向線分の開始画素から１画素ずつ順次、いわゆる線型探索を行って終端画素を探索する。一方、ｄｙ／ｄｘ≦αの場合（描画する線分の傾きが小さい）は、走査方向線分の開始画素を基準にして、二分探索により終端画素を探索する。これが本発明の特徴である。以下、二分探索について詳述する。
【００２３】
傾きｄｙ／ｄｘの線分上に存在する或る点Ｐが主走査方向（ｘ方向）に１ピクセルずれた時、副走査方向（ｙ方向）にｄｙ／ｄｘピクセルだけずれるが、傾きｄｙ／ｄｘが小さい場合、その点は線分上に存在し続けることになる。いま、点Ｐを主走査方向にΔｘｐピクセルずらした場合に、その点（ピクセル）が線分上に存在するための副走査方向のずれを誤差ｅｐと呼ぶ。すなわち、誤差ｅｐはｅｐ＝Δｘｐ＊ｄｙ／ｄｘ（＊は乗算）で表わされる。現在処理している行における、走査方向線分の開始画素（Ｐとする）から主走査方向にΔｘｐピクセルずらし、その時の誤差ｅｐが１≦ｅｐ＜２になるような点（ピクセル）が、当該行の走査方向線分の終端画素の位置となる。
【００２４】
なお、処理対象行の走査方向線分の開始画素は、前の行の走査方向線分の終端画素の位置から一意に決まる。また、描画する線分の最初の行の走査方向線分の開始画素は、該描画する線分の始点（図２（ａ）のＡ）の画素となる。
【００２５】
図２（ｂ）は、処理対象行を描画する線分１の最初の行（ｙｓ）とし、始点Ａの画素を当該行の走査方向線分の開始画素Ｐとして、これから主走査方向（ｘ方向）にΔｘｐピクセルずらした画素Ｐ’における線分１と誤差ｅｐの関係を示したものである。誤差ｅｐが１≦ｅｐ＜２を満たすか判定し、満たさない場合、移動量を半分ずつ減少させながら、誤差ｅｐの大きさに応じて、画素Ｐ’の位置をｘ軸の正あるいは負方向に移動させる処理を繰り返し、誤差ｅｐが１≦ｅｐ＜２を満たす画素Ｐ’の位置を探索する（二分探索）。誤差ｅｐが１≦ｅｐ＜２を満した場合、その時の画素Ｐ’の位置を当該行（図２（ｂ）ではｙｓ）の走査方向線分の終端画素として、画素Ａから画素Ｐ’までの画素群を当該行の走査方向線分と決定する。次の行では、前の行の走査方向線分の終端画素を基に当該行の走査方向線分の開始画素を一義的に決定し、該開始画素を基準に同様に二分探索を行って終端画素を探索する。以下、同様の処理を終点Ｂの行（ｙｅ）まで繰り返す。
【００２６】
図３に、本発明の線分描画処理方法の基本処理フローを示す。この処理フローは、描画する線分の傾きｄｙ／ｄｘがｄｙ／ｄｘ≦α（描画する線分の傾きが小さい）の場合に適用される。ここで、描画する線分の傾きがｄｙ／ｄｘ≦α（αは例えば１／８）であることは、すでに判定済みとする。
【００２７】
いま、処理対象の行の走査方向線分の開始画素をＰとし、該画素Ｐのｘ座標、ｙ座標をｘｐ，ｙｐで表わす。まず、画素Ｐのｘ方向移動量Δｘｐの初期値を設定する（ステップ１０１）。この初期値については、計算コストを減らすため、２の階乗値にする。初期値の大きさは、画面の主走査方向の画素数の半分以上の値にすればよい。例えば、画面サイズを１８０（主走査方向画素数）×１２０（副走査方向画素数）とした場合、Δｘｐの初期値を２７（＝１２８）とする。なお、この初期値の値は、処理済みの行が所定数になる毎に、すなわち、線分の終点の行に近づくに従い、順次、減少するようにしてもよい。これにより、二分探索の回数を減らすことが可能になる。
【００２８】
次に、画素Ｐの位置をｘ方向にΔｘｐ移動させ（ステップ１０２）、移動後の画素Ｐ（便宜上、Ｐ’とする）の位置での誤差ｅｐを計算する（ステップ１０３）。先に述べたように、誤差ｅｐはｅｐ＝Δｘｐ＊ｄｙ／ｄｘで表わされる。
【００２９】
次に、誤差ｅｐの大きさを判定する（ステップ１０４）。ここで、１≦ｅｐ＜２ならば、画素Ｐ’を当該行の走査方向線分の終端画素として、画素Ｐから画素Ｐ’までの画素群を当該行の走査方向線分と決定し（ステップ１０５）、当該行の処理が終了となる。そして、処理は次の行に移行する。
【００３０】
一方、０＜ｅｐ＜１ならば、現在の画素Ｐ’の位置からｘ座標が大きくなる方向（正方向）に画素Ｐ’を移動させるような移動量Δｘｐを設定する（ステップ１０６）。この時の移動量Δｘｐは前の半分とする。移動量Δｘｐを設定後、ステップ１０２へ戻る。また、ｅｐ≧２ならば、現在の画素Ｐ’の位置からｘ座標が小さくなる方向（負方向）に画素Ｐ’を移動させるような移動量Δｘｐを設定する（ステップ１０７）。この時も、該移動量Δｘｐは前の半分とする。移動量Δｘｐを設定後、同様にステップ１０２に戻る。以後、１≦ｅｐ＜２になるまで、ステップ１０２，１０３，１０４，１０６または１０７をループし、１≦ｅｐ＜２になったならステップ１０５に進む。
【００３１】
図４に、図３の処理フローの具体的な処理イメージを示す。図４（ａ）は、多数の画素から構成されたｘｙ座標平面の画面全体を示し、図４（ｂ）は、その一部分（線分を描画する部分）を拡大して示したものである。ここでも、画面走査方向はｘ方向とする。
【００３２】
いま、描画する線分の始点をＡ、終点をＢとし、ｙ＝ｎ−１行までの線分描画処理が完了し、ｙ＝ｎ行での線分描画処理を開始する場合を考える。なお、図４（ａ）の黒線は、描画済みの線分を示したものである。
【００３３】
図４（ｂ）において、Ｐはｙ＝ｎ行の走査方向線分の開始画素で、該画素Ｐのｘ座標、ｙ座標をそれぞれｘｐ，ｙｐと表わし、（ｘｐ，ｙｐ）＝（ｍ，ｎ）とする。該画素Ｐは、前の行ｙ＝ｎ−１の走査方向線分の終端画素ｐｅの位置（ｍ−１，ｎ−１）から一意に決定することができる。まず、移動量Δｘｐの初期値を設定して、画素Ｐからｘ座標正方向にΔｘｐピクセル移動し、移動後の画素Ｐ１について、誤差ｅｐを求め、該誤差ｅｐが１≦ｅｐ＜２を満足するか判定する。ここでは満足せず、ｅｐ≧２であったため、次に、画素Ｐ１からｘ座標負方向に前回の１／２Δｘｐピクセル移動し、移動後の画素Ｐ２について、誤差ｅｐを求め、該誤差ｅｐが１≦ｅｐ＜２を満足するか判定する。ここでも満足せず、まだｅｐ≧２であったため、再び、画素Ｐ２からｘ座標負方向に前回の更に半分の１／４Δｘｐピクセル移動し、移動後の画素Ｐ３について、誤差ｅｐを求め、該誤差ｅｐが１≦ｅｐ＜２を満足するか判定する。ここでも満足せず、今度は０＜ｅｐ＜１であったため、画素Ｐ３からｘ座標正方向に前回の半分の１／８Δｘｐピクセル移動し、移動後の画素Ｐ４について、誤差ｅｐを求め、該誤差ｅｐが１≦ｅｐ＜２を満足するか判定する。ここで満足したので、画素Ｐ４（ｍ’，ｎ）をｙ＝ｎ行の走査方向の線分の終端画素とし、ｍ≦ｘ＜ｍ’の範囲の画素群（ＰからＰ４までの画素）を、ｙ＝ｎ行での走査方向線分と決定する。そして、これら画素群が塗り潰されることになる。
【００３４】
次に処理は、ｙ＝ｎ＋１行に進むが、その走査方向線分の開始画素Ｐ（ｘｐ，ｙｐ）は、前のｙ＝ｎ行での線分終端画素Ｐ４の位置（ｍ’，ｎ）を基に、Ｐ（ｘｐ，ｙｐ）＝（ｍ’＋１，ｎ＋１）と決定される。
【００３５】
以上、本発明の線分描画処理方法の基本的考え方を説明したが、描画する線分の傾きや方向は、図４のような場合とは限らず、例えば、図５（ａ）〜（ｃ）のような場合も考えられる。いずれの場合も、Ａは始点、Ｂは終点とする。ここで、図５（ａ）の場合は、着目する行において、最初は当該行の走査方向線分の開始画素をｘ座標負方向にΔｘｐピクセル移動するようにすればよい。その後の処理は、図４の場合と同様である。また、図５（ｂ）や（ｃ）の場合は、主走査方向をｙ方向とすればよい。
【００３６】
傾きが特に小さい線分の場合、上述のように二分探索方式を用いて、各行毎に走査方向線分の終端画素を探索することにより、従来のブレゼンハム方式のように、走査方向線分の開始画素から１画素ずつ誤差項を求めて終端画素を探索（線型探索）する場合に比べて、処理時間を短縮することが可能になる。
【００３７】
次に、本発明の線分描画処理方法の具体的な実施例について説明する。
【００３８】
図１は、本発明の線分描画処理機能を備えた撮像画像処理装置の一実施形態の全体構成を示した図である。なお、撮像画像処理装置は、他に操作部などを備えているが、図１では省略してある。
【００３９】
カメラなどの撮像装置１０で撮影された画像データは画像処理部２０に送られる。画像データは、一般にカラー画像データであるが、モノクロ画像データでもよい。ここで、撮像装置１０からは、画像データと共に、画面（フレーム）の開始を示す同期信号Ｖsync、画面（フレーム）の各行の開始を示す同期信号Ｈrefも送出される。
【００４０】
画像処理部２０は、撮像装置１０から送られた画像データに対して所定の画像処理を施す。所定の画像処理とは、例えば、ベイヤー補完処理、倍率色収差補正処理、ＹＵＶ変換処理、ＭＴＦ補正処理、歪曲収差補正処理、γ補正処理などである。これらの画像処理は、同期信号Ｖsync、Ｈrefなどに同期して実施され、処理結果の画像データはフレームメモリ５０に格納される。各画像処理は、一般にシーケンシャルに実施されるため、画像処理部２０とフレームメモリ５０との間のデータの流れは双方向になる。
【００４１】
線分処理部３０は、画像処理部２０から同期信号Ｖsync、Ｈrefを受け取り、該同期信号に同期して線分処理を実行する。線分の始点・終点座標は、あらかじめ線分メモリ４０に保持しておく。描画する線分は、１つ以上いくつでもよい。線分処理部３０では、フレーム毎に同期信号Ｖsyncに同期して、線分メモリ４０から処理対象線分の始点・終点座標を読み込んで、線分の傾き、走査方向線分の開始画素などの初期値計算を行った後、同期信号Ｈrefに同期して、フレームの各行毎に、描画すべき線分（走査方向線分）の画素を決定する。その結果は線分メモリ４０に保持される。ここで、線分メモリ４０に保持される値は、走査方向線分の各画素の表示色などを表わすデータであり、線分を赤色で表示する場合、走査方向線分の各画素に対応するメモリアドレスに赤色の画素データが保持される。
【００４２】
合成部６０では、線分メモリ４０に保持された走査方向線分の各画素の表示色などを表わす画素データと、フレームメモリ５０に保持された画像データとを入力して、画像上に線分を重畳する処理を行う。表示装置７０は、合成部６０から出力された撮影画像と、線分の重畳画像をモニタ表示する。例えば、撮影画像に重畳して、線分を赤色で表示する。なお、線分の種類ごとに色分けして表示することも可能である。
【００４３】
ここで、本発明の特徴は線分処理部３０にある。線分処理部３０は、例えばマイクロプロセッサからなり、アセンブラ言語などを用いて線分描画の処理を実行する。以下、線分処理部３０での線分描画処理について詳述する。
【００４４】
図６に線分処理部３０の全体的な処理フローを示す。線分処理部３０での線分描画処理は画像処理部２０側の処理と同期して行われる必要がある。そこで、線分処理部３０は、画像処理部２０から同期信号が到来するのを待つ（ステップ２０１）。画像処理部２０から同期信号を受け取ると、該同期信号がＶsync信号かＨref信号か判断する（ステップ２０２）。Ｖsync信号は画面（フレーム）の開始を示す同期信号、Ｈref信号は画面の各行の開始を示す信号である。Ｖsync信号を受け取った場合にはＶsync処理を実行し（ステップ２０３）、Ｈref信号を受け取った場合にはＨref処理を実行する（ステップ２０４）。その後、ステップ２０１に戻る。ここで、Ｖsync処理では、主に線分描画処理のための前処理が実行される。Ｈref処理では、フレーム各行の走査方向線分描画処理が実行される。
【００４５】
図７はＶsync処理の概略処理フローである。線分処理部３０は、画面（フレーム）の開始を示すＶsync信号がオンになると（ステップ３０１）、線分描画処理のための初期値を計算する（ステップ３０２）。初期値は、描画する線分の傾き、先頭行の走査方向線分の開始画素の座標などである。線分処理部３０は、処理対象線分の始点座標（ｘｓ，ｙｓ）、終点座標（ｘｅ，ｙｅ）を線分メモリ４０から読み出して、傾きｄｙ／ｄｘを計算すると共に、始点座標（ｘｓ，ｙｓ）を描画する線分の先頭行の走査方向線分の開始画素座標とする。そして、該描画する線分の傾き、開始画素座標などの初期値を、線分メモリ４０に保存する（ステップ３０３）。
【００４６】
なお、ここでは、線分の傾きｄｙ／ｄｘにかえて、ｄｘ＝ｘｅ−ｘｓ，ｄｙ＝ｙｅ−ｙｓ
を線分メモリ４０に保持するとする。これにより、ｄｙ／ｄｘを計算する必要がなく、除算を省略することができる。
【００４７】
図８はＨref処理の概略処理フローである。線分処理部３０は、画面（フレーム）の各行の開始を示すＨref信号がオンになると（ステップ４０１）、線分メモリ４０から初期値を読み込む（ステップ４０２）。そして、線分の傾きｄｙ／ｄｘが所定値α以下かどうか判定する（ステップ４０３）。ここでは、除算を必要としないように、２ｋ＊ｄｙ≦ｄｘかどうか判定する。すなわち、ｄｙをｋビットシフトして大きくした値とｄｘを比較し、ｄｘが等しいか大きければ、線分の傾きは主走査方向に対して小さいと判断できる。例えば、α＝１／８は、ｋ＝３の場合に対応する。
【００４８】
線分の傾きｄｙ／ｄｘがｄｙ／ｄｘ≦αの場合、すなわち、２ｋ＊ｄｙ≦ｄｘである場合には、二分探索処理により、着目する行について、走査方向線分の開始画素から探索を開始して、走査方向線分の終端画素を求める（ステップ４０４）。そして、走査方向線分の開始画素と終端画素とこれらに挟まれた画素とを線分描画画素として画素データを線分メモリ４０へ保存する（ステップ４０６）。例えば、線分メモリ４０内の対応するメモリアドレスに赤色などの画素データを保存する。また、求まった走査方向線分の終端画素の走査方向位置から走査方向へ１ピクセルずらした位置の座標値を、同様に線分メモリ４０へ保存する。一方、線分の傾きｄｙ／ｄｘがｄｙ／ｄｘ＞αの場合、すなわち、２ｋ＊ｄｙ＞ｄｘである場合には、ブレゼンハム方式などを適用して、線型探索処理により、着目する行について、走査方向線の開始画素から１画素ずつ探索を行って、走査方向線分の終端画素を求める（ステップ４０５）。そして、ステップ４０６へ進む。
【００４９】
二分探索処理や線型探索処理は、実際には描画する線分の始点の行（線分の先頭行）から開始して、終点の行で終了となる。処理が線分の先頭行の時、線分メモリ４０に初期値として保存されている処理対象線分の始点座標に対応する画素が、該先頭行の走査方向線分の開始画素として用いられる。それ以降の各行では、順次、ステップ４０６で線分メモリへ保存される、前の行の走査方向線分の終端画素の走査方向位置から走査方向へ１ピクセルずらした位置の座標値に対応する画素が当該行の走査方向線分の開始画素として利用される。
【００５０】
なお、図８において、ステップ４０３の線分の傾き判定は、最初にＨref信号がオンになった場合にのみ、すなわち、処理対象の行が画面先頭行に戻った場合にのみ実行し、それ以降はステップ４０３はスキップして、直ちにステップ４０４あるいは４０５に進むようにしてもよい。また、図７のステップ３０２の初期値計算で、線分の傾き判定も実行して、その判定結果を線分メモリ４０に保存しておくとこでもよい。
【００５１】
図９は図８の二分探索処理（ステップ４０４）についての具体的な処理フローを示したものである。これは、先の図３の処理フローと基本的に同じであるが、誤差ｅｐに替えて新たに誤差Ｅｐを定義して、傾きｄｙ／ｄｘの除算を不要としたものである。また、描画する線分は、図２（ａ）に示したような線分としている。
【００５２】
処理対象の行の走査方向線分の開始画素をＰとし、該画素Ｐのｘ座標、ｙ座標をｘｐ，ｙｐで表わす。まず、画素Ｐのｘ方向移動量Δｘｐの初期値を設定する（ステップ５０１）。ここでは、Δｘｐの初期値は２７とする。先に述べたように、このΔｘｐの初期値は、画面の主走査方向の画素数の半分以上の値にするのが望ましい。また、処理済みの行が所定数になるごとに、順次、値を減少するようにしてもよい。
【００５３】
次に、画素Ｐの位置をｘ方向にΔｘｐ移動させる（ステップ５０２）。そして、この移動後の画素Ｐ（便宜上、Ｐ’とする）が、当該行の走査方向線分の終端画素となるか否か調べるため、画素Ｐ’での誤差を計算する（ステップ５０３）。
【００５４】
先に述べたように、誤差はｅｐ＝Δｘｐ＊ｄｙ／ｄｘで表わされる。該誤差ｅｐが１≦ｅｐ＜２になるような点（ピクセル）が、当該行の走査方向線分の終端画素となる。しかし、ｄｙ／ｄｘの値を求めるには、除算を必要とする。先の線分の傾き判定に２ｋ＊ｄｙ≦ｄｘを定義して除算を不要としたように、ここでは、誤差ｅｐにかえて新たに誤差Ｅｐ＝ｄｘ＊ｅｐ＝Δｘｐ＊ｅｙを定義する。該誤差Ｅｐがｄｘ≦Ｅｐ＜２＊ｄｘとなるような点（ピクセル）を求めれば、それが当該行の走査方向線分の終端画素となる。このように誤差Ｅｐを定義することで、傾きｄｙ／ｄｘの値を必要とせず、除算なしで走査方向線分の終点画素を求めることができる。
【００５５】
次に、誤差Ｅｐの大きさにより、二分探索処理を終了させるか、継続させるか判断する（ステップ５０４）。ここで、ｄｘ≦Ｅｐ＜２＊ｄｘならば、画素Ｐ’を当該行の走査方向線分の終端画素として、画素Ｐから画素Ｐ’までの画素群を当該行の走査方向線分と決定する（ステップ５０５）。０＜Ｅｐ＜ｄｘならば、現在の画素Ｐ’の位置からｘ座標が大きくなる方向（正方向）に画素Ｐ’を移動させるような移動量Δｘｐを設定する（ステップ５０６）。このときの移動量Δｘｐは前の半分にする。移動量Δｘｐを設定後、ステップ５０２へ戻る。また、Ｅｐ≧２＊ｄｘならば、現在の画素Ｐ’の位置からｘ座標が小さくなる方向（負方向）に画素Ｐ’を移動させるような移動量Δｘｐを設定する（ステップ５０７）。この時も該移動量Δｘｐは前の半分にする。移動量Δｘｐを設定後、同様にステップ５０２へ戻る。
【００５６】
これまで、処理対象線分を１本として説明してきたが、一般に画像に重畳する線分は１本とは限らない。以下に、処理対象線分を複数に拡張した場合の線分処理部３０での線分描画処理について説明する。全体の処理フローは図６と同様である。
【００５７】
図１０は、線分処理部３０がＶsync信号を受け取った際の処理フローである。処理対象線分の総数、各線分の始点と終点の座標などはあらかじめ線分メモリ４０に保持されているとする。
【００５８】
まず、ｎを１に初期設定する（ステップ６０１）。次に、ｎ本目の線分について、その始点と終点の座標を線分メモリ４０から読み込み（ステップ６０２）、ラインプロパティ（ＬＰ）を計算する（ステップ６０３）。ここで、線分描画処理の際に頻繁に利用される種々の値をラインプロパティ（ＬＰ）と呼ぶことにする。
【００５９】
ラインプロパティ（ＬＰ）の具体的な値としては、
傾きの方向を示す値：ＳtepＸ
終点のＹ座標：ｙｅ
始点終点のＸ方向差分：ｄｘ
始点終点のＹ方向差分：ｄｙ
線分描画点のＸ座標：ＤrawＸ
線分描画点のＹ座標：ＤrawＹ
などがある。
【００６０】
ＳｔｅｐＸは傾きの方向（“／”  ｏｒ  “＼”  の方向）を示す値である。この値により、線分の始点から終点への向きが分かるようになる。ＤrawＸの更新の際に利用される。ｙｅは直線の描画処理を終了する際に利用される。ｄｘとｄｙは直線の傾きの大きさを判断する際に利用される。ＤrawＸ，ＤrawＹは現在描画処理中の線分における着目行の走査方向線分のカレントＸ座標、Ｙ座標を表し、描画処理中に値が更新されていく。この座標（ＤrawＸ，ＤrawＹ）で示される点（画素）に沿って線分は描画されることになる。
【００６１】
ここで、ラインプロパティ（ＬＰ）は以下のように算出される。
【００６２】
ＳtepＸ＝（終点のＸ座標−始点のＸ座標）の符号値（１  or  −１）
ｙｅ＝終点のＹ座標
ｄｘ＝｜終点のＸ座標−始点のＸ座標｜
ｄｙ＝｜終点のＹ座標−始点のＹ座標｜
ＤrawＸ＝線分の始点のＸ座標
ＤrawＹ＝線分の始点のＹ座標
なお、ＳｔｅｐＸ，ｙｅ，ｄｘとｄｙは処理対象線分の描画処理を通して定数として扱われるが、ＤrawＸとＤrawＹは後述のＬＰ更新処理の際に値が変更されていく。ステップ６０３で設定されるＤrawＸとＤrawＹは初期値である。
【００６３】
次に、ステップ６０３で算出したラインプロパティ（ＬＰ）を線分メモリ４０に存在する。そして、全ての処理対象線分のラインブプロパティを計算したか判定し（ステップ６０５）、未処理のものがあれば、ｎを＋１して（ステップ６０６）、ステップ６０２に戻る、以下、全ての処理対象線分のラインプロパティを計算して、Ｖsync処理が終了となる。
【００６４】
図１１は、線分処理部３０がＨref信号を受け取った際の処理フローを示したものである。まず、ｎを１に初期設定する（ステップ７０１）。次に、ｎ本目の線分について、その時点のラインプロパティ（ＬＰ）を線分メモリ４０から読み込む（ステップ７０２）。次に、現在処理対象になっている行（ｓＦとする）に、ＤrawＹが一致するか判定する（ステップ７０３）。ｓＦ≠ＤrawＹならば、現在処理対象になっている行について、当該線分の線分描画処理を開始する必要がないため、そのまま、ステップ７１０に行く。
【００６５】
一方、ｓＦ＝ＤrawＹならば、当該線分の現在処理対象になっている行の線分描画処理を開始する。初めに、当該線分の傾きの大きさを判断する（ステップ７０４）。ここでは、先に述べたように、ｄｙ／ｄｘ≦αのかわりに２ｋ＊ｄｙ≦ｄｘ（ｋは定数）を用いて判断する。すなわち、２ｋ＊ｄｙ≦ｄｘならば、主走査方向に対する傾きが特に小さい線分と判断できる。２ｋ＊ｄｙ≦ｄｘの場合、二分探索処理により、当該線分の現在処理対象になっている行の走査方向線分を求める（ステップ７０５）。これは図９と同じである。すなわち、図９のｘｐをＤrawＸに置き換えればよい。２ｋ＊ｄｙ＞ｄｘの場合には、従来のブレゼンハム方式などを適用して線型探索処理により、当該線分の現在の処理対象になっている行の走査方向線分を求める（ステップ７０６）。そして、ステップ７０５あるいは７０６で求まった当該線分の処理対象行の走査方向線分に対応する画素群の画素データ（例えば、赤色データ）を線分メモリ４０の該当アドレスに書き込む（ステップ７０７）。
【００６６】
次に、ＤrawＹが当該線分の終点のＹ座標ｙｅに一致するか判定する（ステップ７０８）。ＤrawＹ＝ｙｅならば、そのままステップ７１０にいく。ＤrawＹ≠ｙｅならば、当該線分の次の行における線分描画処理のため、ＤrawＸとＤrawＹの値を次のように更新する（ステップ７０９）
ＤrawＸ  ←  ＤrawＸ＋ＳtepＸ
ＤrawＹ  ←  ＤrawＹ＋１
これらの値が、当該線分における次の行の走査方向線分の開始画素の座標値となる。更新後、線分メモリ４０に保存する。
【００６７】
その後、全ての処理対象線分について処理したか判定し（ステップ７１０）、未処理のものがあれば、ｎを＋１して（ステップ７１１）、ステップ７０２に戻る。以下、処理対象線分の数だけステップ７０２〜７１１の処理を繰り返す。
【００６８】
次に、二分探索処理と線形探索処理を場合分けする際に用いられる、線分の傾きｄｙ／ｄｘの閾値αの具体的値について説明する。図１２は、種々の傾きの線分について、線形探索処理と二分探索処理により描画した場合の命令数を比較したものである。ここで、線型探索には通常のブレゼンハムアルゴリズムを用いた。また、画面サイズは１８０（主走査方向画素数）×１２０（副走査方向の画素数）であり、二分探索処理ではΔｘｐの初期値を２７とした。命令数は、各行の線分描画処理に掛かる命令数のうち、最大の命令数を意味する。図１２より、線分の傾きｄｙ／ｄｘが特に１／８＝０．１２５以下の場合に、二分探索処理を適用すればよいことが分かる。先に述べたように、α＝１／２ｋの関係にあり、α＝１／８は、ｋ＝３の場合に対応する。したがって、２３＊ｄｙ≦ｄｘの場合、二分探索処理を適用すればよいとも云える。この場合、ｄｙをビットシフトした値とｄｘを比較するだけで、線分の傾きが特に小さいか否か判断でき、除算が不要になる。
【００６９】
なお、二分探索処理と線形探索処理を場合分けするための判断基準である線分の傾きの閾値αや１／２ｋの最適値は、上記の具体例に限定されないことは云うまでもない。
【００７０】
また、本発明の具体的実施形態として、撮像画像に線分を重畳して表示する実施例を示したが、本発明の線分描画処理方法の適用は、これに限定されるものではない。
【符号の説明】
【００７１】
１０  撮像装置
２０  画像処理部
３０  線分処理部
４０  線分メモリ
５０  フレームメモリ
６０  合成部
７０  表示装置
【先行技術文献】
【特許文献】
【００７２】
【特許文献１】特開２００３−３１７１０８号公報
【図１】
0005428629.tif 000002
【図２】
0005428629.tif 000003
【図３】
0005428629.tif 000004
【図４】
0005428629.tif 000005
【図５】
0005428629.tif 000006
【図６】
0005428629.tif 000007
【図７】
0005428629.tif 000008
【図８】
0005428629.tif 000009
【図９】
0005428629.tif 000010
【図１０】
0005428629.tif 000011
【図１１】
0005428629.tif 000012
【図１２】
0005428629.tif 000013