(57)【要約】【課題】エッジ検出を短時間でかつ効率よく行うことができるエッジ検出方法を提供すること。【解決手段】画像のエッジを判別するエッジ判別方法であって、注目する位置を含むように注目する位置の近傍にある複数の画素位置を結んで第１の多角形を構成するステップと、第１の多角形の１辺または２辺以上の隣接する辺の組み合わせにより構成される経路を少なくとも２種類以上作成するステップと、少なくとも２種類以上の経路のそれぞれに沿った画素の並びに基づいて画素値が変化する回数を判別するステップと、各経路における判別結果の組み合わせに基づいて注目位置近傍のエッジの有無を判別するステップとを具備する。【選択図】        図１
2006146787.tif 000002
【特許請求の範囲】
【請求項１】
画像のエッジを判別するエッジ判別方法であって、
注目する位置を含むように前記注目する位置の近傍にある複数の画素位置を結んで第１の多角形を構成するステップと、
前記第１の多角形の１辺または２辺以上の隣接する辺の組み合わせにより構成される経路を少なくとも２種類以上作成するステップと、
前記少なくとも２種類以上の経路のそれぞれに沿った画素の並びに基づいて画素値が変化する回数を判別するステップと、
前記各経路における判別結果の組み合わせに基づいて注目位置近傍のエッジの有無を判別するステップと、
を具備することを特徴とするエッジ判別方法。
【請求項２】
画像のエッジを判別するエッジ判別方法であって、
注目する位置を含むように前記注目する位置の近傍にある複数の画素位置を結んで第１の多角形を構成するステップと、
前記第１の多角形を含むように前記複数の画素位置の外部に位置する複数の画素位置を結んで第２の多角形を構成するステップと、
前記第１及び第２の多角形の１辺または２辺以上の隣接する辺の組み合わせにより構成される経路を少なくとも２種類以上作成するステップと、
前記少なくとも２種類以上の経路のそれぞれに沿った画素の並びに基づいて画素値が変化する回数を判別するステップと、
前記各経路における判別結果の組み合わせに基づいて注目位置近傍のエッジの有無を判別するステップと、
を具備することを特徴とするエッジ判別方法。
【請求項３】
前記第１または第２の多角形上で少なくとも２個以上の経路を構成する辺の組み合わせを少なくとも２通り以上構成し、各組み合わせにおける経路に関する前記判別結果を少なくとも１つ以上含むような組み合わせにより注目位置近傍のエッジ状態の判別を行うことを特徴とする請求項１または２に記載のエッジ判別方法。
【請求項４】
前記各経路に沿った画素の並びに方向性を持たせ、当該方向に基づいて各画素の輝度レベルが上昇する場合のエッジと当該輝度レベルが下降する場合のエッジの場合分けを行い、これを符号付きの数値で表すステップを含むことを特徴とする請求項１から３のいずれか１つに記載のエッジ判別方法。
【請求項５】
前記複数の経路でのエッジ判別の結果を符号付き数値の加算及び乗算で表すステップを含むことを特徴とする請求項１から４のいずれか１つに記載のエッジ判別方法。
【請求項６】
前記符号付き数値が２ビットで有ることを特徴とする請求項５に記載のエッジ判別方法。
【請求項７】
前記エッジ判別を行う前に、画像に対して２値化処理を行うことを特徴とする請求項１から４のいずれか１つに記載のエッジ判別方法。
【請求項８】
前記エッジ判別を行う前に、画像に対して符号付きの２ビットの３値化処理を行うことを特徴とする請求項１から４のいずれか１つに記載のエッジ判別方法。
【請求項９】
画像のエッジを判別するエッジ判別方法であって、
注目する位置を含むように前記注目する位置の近傍にある複数の画素位置を結んで第１の多角形を構成するステップと、
前記第１の多角形の１辺または２辺以上の隣接する辺の組み合わせにより構成される経路を少なくとも２種類以上作成するステップと、
前記少なくとも２種類以上の経路のそれぞれに沿った画素の並びに基づいて画素値が変化する回数を判別するステップと、
前記各経路における判別結果の組み合わせに基づいて、前記エッジの状態を階層的に符号化するステップと、
を具備することを特徴とするエッジ判別方法。
【請求項１０】
画像のエッジを判別するエッジ判別方法であって、
注目する位置を含むように前記注目する位置の近傍にある複数の画素位置を結んで第１の多角形を構成するステップと、
前記第１の多角形を含むように前記複数の画素位置の外部に位置する複数の画素位置を結んで第２の多角形を構成するステップと、
前記第１及び第２の多角形の１辺または２辺以上の隣接する辺の組み合わせにより構成される経路を少なくとも２種類以上作成するステップと、
前記少なくとも２種類以上の経路のそれぞれに沿った画素の並びに基づいて画素値が変化する回数を判別するステップと、
各多角形上の経路でのエッジ判別結果を少なくとも１つ以上含むような複数の経路でのエッジ判別の組み合わせに基づいて、注目画素近傍のエッジの状態を階層的に符号化するステップを含むことを特徴とするエッジ判別方法。
【請求項１１】
前記第１または第２の多角形上で少なくとも２個以上の経路を構成する辺の組み合わせを少なくとも２通り以上構成し、各組み合わせにおける経路の判別結果を少なくとも１つ以上含むような複数の経路でのエッジ判別の組み合わせにより注目画素近傍のエッジ状態を符号化するステップを含むことを特徴とする請求項９または１０に記載のエッジ判別方法。
【請求項１２】
前記各経路に沿った画素の並びに方向性を持たせ、当該方向に基づいて各画素の輝度レベルが上昇する場合のエッジと当該輝度レベルが下降する場合のエッジの場合分けを行い、これを符号付きの数値で表すステップを含むことを特徴とする請求項１１に記載のエッジ判別方法。
【請求項１３】
前記複数の経路でのエッジ判別の結果を符号付き数値の加算及び乗算で表すステップを含むことを特徴とする請求項１１に記載のエッジ判別方法。
【請求項１４】
前記符号付き数値が２ビットで有ることを特徴とする請求項１３に記載のエッジ判別方法。
【請求項１５】
前記エッジ判別を行う前に、画像に対して２値化処理を行うことを特徴とする請求項１１に記載のエッジ判別方法。
【請求項１６】
前記エッジ判別を行う前に、画像に対して符号付きの２ビットの３値化処理を行うことを特徴とする請求項１１に記載のエッジ判別方法。
【請求項１７】
注目する画素位置の近傍の画像のエッジの状態を符号化するエッジ符号化方法であり、
注目する画素位置の近傍の画素位置を結んで構成される多角形で、注目する画素位置が、多角形に内包される様に多角形を構成し、
該多角形の１辺か、２辺以上の隣接する辺の組み合わせによりなる経路を少なくとも２個以上作成し、
該作成した各々の経路に沿った画素の並びでエッジが過ぎった数を判別し、
さらに、前記作成した各々の経路でのエッジ判別の結果を用いて、エッジの状態を階層的に符号化するステップを含むことを特徴とするエッジ符号化方法。
【請求項１８】
注目する画素位置の近傍の画像のエッジの状態を符号化するエッジ符号化方法であり、
注目する画素位置の近傍の画素位置を結んで構成される多角形で、注目する画素位置が、多角形に内包されるように第１の多角形を構成し、
前記第１の多角形を内包するようにさらに外側の画素位置を結んで構成される第２の多角形を構成し、
前記各多角形上の１辺か、２辺以上の隣接する辺の組み合わせによりなる経路を前記各多角形上で少なくとも２個以上作成し、該作成した各々の経路に沿った画素の並びでエッジが過ぎった数を判別し、
さらに各多角形上の経路でのエッジ判別結果を少なくとも１つ以上含むような複数の経路でのエッジ判別の組み合わせにより注目画素近傍のエッジの状態を階層的に符号化するステップを含むことを特徴とするエッジ符号化方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明はエッジ判別方法及びエッジ符号化方法に関するものである。
【背景技術】
【０００２】
例えば、日本国特許第３３９８３０１号公報では、画像形成装置のエッジ補間方法において、補間前の多値画像データと補間後の多値画像データのサイズを変えずに、注目画素の周囲の状況に応じてその注目画素のドットサイズを変化させてエッジ補間を行うことを開示している。
【０００３】
図１３は、補間を行うべき点Ｘの１６点の近傍の画素におけるエッジ状態のパターンの種類をカウントするための図である。例えば、Ｘを横切るエッジがａ〜ｆのいずれかの位置を通り、かつ、ｉ−ｘｉの点を横切るものとすると、１つのパターンに対して左右反転の２パターン、回転角度（０°、９０°、１８０°、２７０°）の４パターン、を考慮すると、図１３において１６画素を２つの領域に分割するエッジは２７６通りのパターンが存在する（符号反転は含まない）。これらのパターンの鏡像関係と反転による縮退を考慮してパターン数を削減しても２１パターンは存在する。
【０００４】
実際のエッジ判別のアルゴリズムにおいて、このようなパターン判別の条件分岐を何回も繰り返すことは、計算速度、演算速度の観点からみて効率的ではない。
【０００５】
そこで、効率性を考慮して、図１４に示すように、注目する点Ｘに隣接する４点からなり、辺ａ、ｂ、ｃ、ｄをもつ４角形と、この４角形を囲み、辺Ａ，Ｂ，Ｃ，Ｄをもつ大きな４角形に着目し、各辺上のエッジの有無を観察する事を考える。各辺ａ、ｂ、ｃ、ｄ、Ａ，Ｂ，Ｃ，Ｄ上のエッジの有無と輝度の上下の方向を考えると、辺の組み合わせで６通り（Ａ−Ｂ，Ａ−Ｃ，Ａ−Ｄ，Ｂ−Ｃ，Ｂ−Ｄ，Ｃ−Ｄ）、各辺方向での画素値の増加減少を符号で表わしたときに、符号の組み合わせで２通り（異符号のエッジはエッジとはみなさず、カウントしない）、さらには内側と外側の辺の組み合わせで６×２×２の２４通りでテストを行わなければならない。しかも、２４通りのテストではエッジが横切った位置までは特定されない。
【０００６】
このようなエッジ判別において、エッジの形状そのものが必要な場合には精密な判別が必要となるが、例えば、変倍処理のための画素補間処理などは精密な分類処理を必要としない場合がある。
【特許文献１】日本国特許第３３９８３０１号公報
【発明の開示】
【発明が解決しようとする課題】
【０００７】
上記したように、従来技術によるエッジ検出方法には、計算に時間がかかり、効率が低いという問題があった。
【０００８】
本発明は、このような課題に着目してなされたものであり、その目的とするところは、エッジ検出を短時間でかつ効率よく行うことができるエッジ判別方法及びエッジ符号化方法を提供することにある。
【課題を解決するための手段】
【０００９】
上記の目的を達成するために、本発明の第１の態様は、画像のエッジを判別するエッジ判別方法であって、注目する位置を含むように前記注目する位置の近傍にある複数の画素位置を結んで第１の多角形を構成するステップと、前記第１の多角形の１辺または２辺以上の隣接する辺の組み合わせにより構成される経路を少なくとも２種類以上作成するステップと、前記少なくとも２種類以上の経路のそれぞれに沿った画素の並びに基づいて画素値が変化する回数を判別するステップと、前記各経路における判別結果の組み合わせに基づいて注目位置近傍のエッジの有無を判別するステップと、を具備する。
【００１０】
また、本発明の第２の態様は、画像のエッジを判別するエッジ判別方法であって、注目する位置を含むように前記注目する位置の近傍にある複数の画素位置を結んで第１の多角形を構成するステップと、前記第１の多角形を含むように前記複数の画素位置の外部に位置する複数の画素位置を結んで第２の多角形を構成するステップと、前記第１及び第２の多角形の１辺または２辺以上の隣接する辺の組み合わせにより構成される経路を少なくとも２種類以上作成するステップと、前記少なくとも２種類以上の経路のそれぞれに沿った画素の並びに基づいて画素値が変化する回数を判別するステップと、前記各経路における判別結果の組み合わせに基づいて注目位置近傍のエッジの有無を判別するステップと、を具備する。
【００１１】
また、本発明の第３の態様は、第１の態様または第２の態様において、前記第１または第２の多角形上で少なくとも２個以上の経路を構成する辺の組み合わせを少なくとも２通り以上構成し、各組み合わせにおける経路に関する前記判別結果を少なくとも１つ以上含むような組み合わせにより注目位置近傍のエッジ状態の判別を行う。
【００１２】
また、本発明の第４の態様は、第１から第３の態様のいずれか１つにおいて、前記各経路に沿った画素の並びに方向性を持たせ、当該方向に基づいて各画素の輝度レベルが上昇する場合のエッジと当該輝度レベルが下降する場合のエッジの場合分けを行い、これを符号付きの数値で表すステップを含む。
【００１３】
また、本発明の第５の態様は、第１から第４の態様のいずれか１つにおいて、前記複数の経路でのエッジ判別の結果を符号付き数値の加算及び乗算で表すステップを含む。
【００１４】
また、本発明の第６の態様は、第５の態様において、前記符号付き数値が２ビットで有る。
【００１５】
また、本発明の第７の態様は、第１から第４の態様のいずれか１つにおいて、前記エッジ判別を行う前に、画像に対して２値化処理を行う。
【００１６】
また、本発明の第８の態様は、第１から第４の態様のいずれか１つにおいて、前記エッジ判別を行う前に、画像に対して符号付きの２ビットの３値化処理を行う。
【００１７】
また、本発明の第９の態様は、画像のエッジを判別するエッジ判別方法であって、注目する位置を含むように前記注目する位置の近傍にある複数の画素位置を結んで第１の多角形を構成するステップと、前記第１の多角形の１辺または２辺以上の隣接する辺の組み合わせにより構成される経路を少なくとも２種類以上作成するステップと、前記少なくとも２種類以上の経路のそれぞれに沿った画素の並びに基づいて画素値が変化する回数を判別するステップと、前記各経路における判別結果の組み合わせに基づいて、前記エッジの状態を階層的に符号化するステップと、を具備する。
【００１８】
また、本発明の第１０の態様は、画像のエッジを判別するエッジ判別方法であって、注目する位置を含むように前記注目する位置の近傍にある複数の画素位置を結んで第１の多角形を構成するステップと、前記第１の多角形を含むように前記複数の画素位置の外部に位置する複数の画素位置を結んで第２の多角形を構成するステップと、前記第１及び第２の多角形の１辺または２辺以上の隣接する辺の組み合わせにより構成される経路を少なくとも２種類以上作成するステップと、前記少なくとも２種類以上の経路のそれぞれに沿った画素の並びに基づいて画素値が変化する回数を判別するステップと、各多角形上の経路でのエッジ判別結果を少なくとも１つ以上含むような複数の経路でのエッジ判別の組み合わせに基づいて、注目画素近傍のエッジの状態を階層的に符号化するステップを含む。
【００１９】
また、本発明の第１１の態様は、第９または第１０の態様において、前記第１または第２の多角形上で少なくとも２個以上の経路を構成する辺の組み合わせを少なくとも２通り以上構成し、各組み合わせにおける経路の判別結果を少なくとも１つ以上含むような複数の経路でのエッジ判別の組み合わせにより注目画素近傍のエッジ状態を符号化するステップを含む。
【００２０】
また、本発明の第１２の態様は、第１１の態様において、前記各経路に沿った画素の並びに方向性を持たせ、当該方向に基づいて各画素の輝度レベルが上昇する場合のエッジと当該輝度レベルが下降する場合のエッジの場合分けを行い、これを符号付きの数値で表すステップを含む。
【００２１】
また、本発明の第１３の態様は、第１１の態様において、前記複数の経路でのエッジ判別の結果を符号付き数値の加算及び乗算で表すステップを含む。
【００２２】
また、本発明の第１４の態様は、第１３の態様において、前記符号付き数値が２ビットで有る。
【００２３】
また、本発明の第１５の態様は、第１１の態様において、前記エッジ判別を行う前に、画像に対して２値化処理を行う。
【００２４】
また、本発明の第１６の態様は、第１１の態様において、前記エッジ判別を行う前に、画像に対して符号付きの２ビットの３値化処理を行う。
【００２５】
また、本発明の第１７の態様は、注目する画素位置の近傍の画像のエッジの状態を符号化するエッジ符号化方法であり、注目する画素位置の近傍の画素位置を結んで構成される多角形で、注目する画素位置が、多角形に内包される様に多角形を構成し、該多角形の１辺か、２辺以上の隣接する辺の組み合わせによりなる経路を少なくとも２個以上作成し、該作成した各々の経路に沿った画素の並びでエッジが過ぎった数を判別し、さらに、前記作成した各々の経路でのエッジ判別の結果を用いて、エッジの状態を階層的に符号化するステップを含む。
【００２６】
また、本発明の第１８の態様は、注目する画素位置の近傍の画像のエッジの状態を符号化するエッジ符号化方法であり、注目する画素位置の近傍の画素位置を結んで構成される多角形で、注目する画素位置が、多角形に内包されるように第１の多角形を構成し、さらに、前記第１の多角形を内包するようにさらに外側の画素位置を結んで構成される第２の多角形を構成し、前記各多角形上の１辺か、２辺以上の隣接する辺の組み合わせによりなる経路を前記各多角形上で少なくとも２個以上作成し、該作成した各々の経路に沿った画素の並びでエッジが過ぎった数を判別し、さらに各多角形上の経路でのエッジ判別結果を少なくとも１つ以上含むような複数の経路でのエッジ判別の組み合わせにより注目画素近傍のエッジの状態を階層的に符号化するステップを含む。
【発明の効果】
【００２７】
本発明によれば、エッジ判別においてパターン分類を系統化し、演算量を軽減したので、短時間でかつ効率よくエッジ検出を行うことができる。
【発明を実施するための最良の形態】
【００２８】
以下、図面を参照して本発明の実施形態を詳細に説明する。まず、図１に示すように、注目する位置Ｘの周りの４画素からなる四角形を考える。すると、この四角形を経路上に同じ数の画素を持つ２つの経路に分離する仕方はｉ、ｊの２通り存在する。次に、図２に示すように、注目する位置Ｘの周りの４画素からなる四角形と、その周りの１２画素からなる四角形を考える。すると、２つの四角形を経路上に同じ数の画素を持つ２つの経路に分離する仕方は内側の四角形に関しては図１と同様に２通り、外側の四角形に関してはｐ〜ｕの６通り存在する。この６通りの内、ｐ，ｑを対と考えると、この対のパターンは９０度回転と、上下反転の対が縮退しており、同じ分割の仕方は２パターンしかない。これに対して、残りの４パターンｒ−ｕは９０度回転と上下反転が別になっている。ここで図２の、外側の１２画素にエッジが横断しているときのパターン数を考える。
【００２９】
図３のように外側の１２画素に番号１〜１２を付与すると、経路の始点と終点の位置の取り方は、始点については１２通り、各始点に対する終点の取り方は１０通り存在するので、経路の取り方は全部で１２×１０＝１２０通り存在することになる。さらに、エッジ（後述）の符号を考えるとこの倍の２４０通りとなる。この経路を辞書式に調べていく方法もあるが、少なからぬ計算時間を要する。
【００３０】
ここで、計算時間を短縮することができる本実施形態の方法を説明するためにエッジの概念を定義する。図２に示される１６個の画素において、各画素の輝度レベルの平均値を求め、この平均値よりも高い画素（図２の白丸の画素）は＋で表現し、平均値よりも低い画素（図２のハッチングが施された画素）は−で表現する。これによって各経路に沿って＋、−の符号パターンができるが、経路中で符号の反転が１回のみの場合をエッジとみなす。そして経路方向に増加する（−から＋への変化）エッジを＋１のエッジフラグ、減少する（＋から−への変化）エッジを−１のエッジフラグで表現して両者を区別する。また、符号の反転が経路中で全然ないかあるいは２回以上の場合にはエッジとみなさない。すなわち、
（１）  ＋１のエッジフラグが１個存在するとき  ＋１
（２）  −１のエッジフラグが１個存在するとき  −１
（３）  それ以外  ０
のごとく、エッジの状態を符号付きの数値を用いて表現（符号化）することにする。
【００３１】
図２に示す経路のうち、ｐ，ｑの場合にはエッジが辺Ａを２度に渡って横断しているので両方ともエッジフラグは０となる。また、ｓとｕの経路の取り方では、エッジが一度だけ辺Ａを横断しているので、図のハッチングの位置の画素のフラグを−１とすると、（ｐ，ｑ，ｒ，ｓ，ｔ，ｕ）のエッジフラグの状態は
（ｐ，ｑ，ｒ，ｓ，ｔ，ｕ）＝（０，０，０，−１，０，−１）            （１）
となる（ここでは、フラグはエッジの方向性だけを表現し経路のどの位置でエッジを横断したかのデータを使用していない）。
【００３２】
以下、このような方法で、上の２４０通りのパターンはすべて符号化できる。従って、外周の１２画素からなる四角形に関わるエッジの状態は６回のテストですべてのパターンが分類可能になる。
【００３３】
図４は、各種のエッジの状態（左側のパターン）と、これを式１で説明した方法で符号化して得られるエッジフラグの状態（右側のパターン）を示している。さらに、図１に示した四角形のエッジ状態の組み合わせは２通りなので、合計で８通りのテストで外周と内周の四角形を通るエッジの状態を判別することができる。
【００３４】
さらに、エッジ適応の画素補間処理などの様に、エッジ判別の目的によっては精密なエッジパターンの分類は必要としない。このような場合には符号化の階層を減らし、分類を大きくする事により効果的にエッジ判別が可能になる。例えば、上述の式１の様に図２の６個の経路パターン（ｐ，ｑ，ｒ，ｓ，ｔ，ｕ）から得られるエッジフラグをすべて使わずに、ｐ，ｑのみのエッジフラグを使うことで、大まかな分類が可能になる。
【００３５】
以下に符号化される経路パターンの数を減らすための一方法について説明する。図１４において、点Ｘを囲む四角形（辺ａ，ｂ，ｃ，ｄ）とそれを囲む四角形（辺Ａ，Ｂ，Ｃ，Ｄ）に着目すると、輝度レベルによって点Ｘの近傍の画素を２つの領域に分けるような単一のエッジが存在する場合、それぞれの四角形上の全辺を１経路と考えると、その経路を２回横断することになる。さらに、この経路を複数とるように考えれば、内側の四角形上の辺からなる複数の経路のうちエッジが１回過ぎる辺の組み合わせによる経路が２つ存在する。外側の四角形では経路の組み合わせを、図２のｐとｑの経路の取り方と同じように、Ａ−ＢとＣ−Ｄまたは、Ｃ−ＡとＤ−Ｂの辺の組み合わせを使うと、エッジが１回横断する辺の組み合わせの経路が２つ存在するか、エッジが２回横断する辺が１つ存在するかのどちらかになる。ここで、四角形を構成する辺の上をエッジが２回以上横断する場合を考慮しない様に単純化するとアルゴリズムは以下の様になる。
【００３６】
複数の辺の組み合わせの経路（例えば図ではＡ−ＢとＣ−Ｄ）でエッジが横断した回数をカウントし、各経路において１個づつであった場合にエッジと判別する。
【００３７】
さらに、エッジの状態を分離したければ、エッジを横断した辺がＡあるいはＢ、ＣあるいはＤと判別する。さらにＡを横断してＢを横断する場合もあるので、エッジの組み合わせをＣ−Ａ、Ｄ−Ｂとして同様に各経路でのエッジの回数をカウントする。
【００３８】
以下に本実施形態に係るエッジ判別方法の詳細を図５を参照して説明する。入力画像が２値画像であれば各画素に−１と＋１を割り当てることにより符号化する（ステップＳ０１）。また、入力画像が多値画像であると判断された場合（ステップＳ０２）には、補間を行うべき点Ｘの周りの１６点の画素のレベルの平均値を求め、各画素値がこの平均値よりも大きい場合には＋１、小さい場合には−１を割り当てることにより符号化する（ステップＳ３）。
【００３９】
次のステップＳ０４〜Ｓ０６では、外周、内周の四角形での２辺の組み合わせの符号反転の状態を調べる。符号反転が２回以上の場合は０とする。すなわち、ステップＳ０４では、各辺（辺Ａ，Ｂ，Ｃ，Ｄ，ａ，ｂ，ｃ，ｄ）において符号が反転している箇所を調べる（ステップＳ０４）。ここでは、隣接する画素間が同符号であり符号反転がない場合には０を割り当てる。また、異符号である場合に−１から＋１への符号反転については＋１のフラグを割り当て、＋１から−１への符号反転については−１のフラグを割り当てる。
【００４０】
次に、各辺での符号反転箇所の非ゼロ要素の数が１のときにフラグにその要素として１を代入する（ステップＳ０５）。次に、内側の四角形の２辺の組み合わせの経路を作成し、エッジの状態フラグを作成する（ステップＳ０６）。
【００４１】
図６（Ａ）は、内側と外側の２つの四角形に関して図２のｐの経路を示した図であり、図６（Ｂ）は、内側と外側の２つの四角形に関して図２のｑの経路を示した図である。内側の四角形は４辺ａ、ｂ、ｃ、ｄを有し、外側の四角形は４辺Ａ、Ｂ、Ｃ、Ｄを有する。
【００４２】
ステップＳ０７では、このような外側の四角形上の経路の符号反転フラグと、内側の四角形上の経路のフラグを統合した組み合わせでの符号反転のフラグを割り当てる。ここでは、辺Ａ−Ｂ，ａ−ｂ，Ｃ−Ｄ，ｃ−ｄの組み合わせ、辺Ｃ−Ａ，ｃ−ａ，Ｄ−Ｂ，ｄ−ｂの組み合わせ、辺Ａ−Ｂ，ｃ−ａ，Ｃ−Ｄ，ｄ−ｂの組み合わせ、辺Ｃ−Ａ，ａ−ｂ，Ｄ−Ｂ，ｃ−ｄの組み合わせが考えられ、それぞれについて判別フラグｆｌｇ_１〜ｆｌｇ_４を用意する。
【００４３】
ここで、例えば、辺Ａ−Ｂ ａ−ｂ、Ｃ−Ｄ，ｃ−ｄの組み合わせで符号反転のフラグが正方向ですべて一致する場合にはフラグｆｌｇ_１＝１、負方向では、フラグｆｌｇ_１＝−１、フラグが一致しない場合には０とする。また、図６に示すような経路の組み合わせにおいて、点線の経路同士（辺Ａ−Ｂ ａ−ｂ、または辺Ｃ−Ａ，ｃ−ａ）で符号反転の位置が揃っており、かつ、実線の経路同士で符号反転の位置が揃っていればｆｌｇ_１またはｆｌｇ_２が有効になる。
【００４４】
図７〜図９は、このような方法によりフラグパターンを分類したようすを示しており、ｆｌｇ_１、ｆｌｇ_２を用いた例である。図７〜図９はｆｌｇ_１だけが＋１になり、ｆｌｇ_２が０の場合である。
【００４５】
図１０は、フラグパターンに対して回転操作（０°，９０°，１８０°，２７０°）または線対称の反転操作（上下反転）を行ったパターンとそれに対する符号を示す図である。ここではｆｌｇ_２が＋１あるいは−１、１８０°回転はｆｌｇ_１が−１となる。このような回転操作、反転操作を加えても、フラグｆｌｇ_１，ｆｌｇ_２は同時に同じ値になることは無い。
【００４６】
図１１は、ｆｌｇ_１，ｆｌｇ_２が同時に同じフラグになる例を示す図である。この場合には縦方向または横方向の相関が強いことがわかる。この後に縦横の峻別を行うためには、辺ａに符号反転のフラグが有るかどうかを調べればわかる。
【００４７】
この例の様に、エッジパターンに対して少ない判別操作で、大まかな分類を行って、後に詳細な分類を行う様にすれば良い。例えば、図１４のｘの位置をエッジ適応で推定（エッジ適応補間）を行う場合、この程度の分類精度から出発して、徐々に付加条件を加えていくアルゴリズムで十分な場合が多い。
【００４８】
図１２は、２値化した画像に対して、経路上にエッジが１個だけ存在する場合にのみ１を出力するロジックの一例であり、入力１〜７と、ＥＸ−ＯＲ回路１０−１〜１０−６と、反転器１１、１３と、加算器１４と、比較器１２と、乗算器１５とから構成される。この構成によれば、１，２が異なる場合にのみＥＸ−ＯＲ回路１０−１が１を出力するので、比較器１２は、１〜７の入力のうち符号反転が１回のときのみに有効な信号を出力する。また、両端の入力１，７の差分を加算器１４で計算し、この出力と比較器１２の出力とをかけ算すると、符号反転が１回だけのときに正か負のフラグが出力される。図１２の回路の前段にバッファを備えれば、図２の６個のパターンのフラグを調べることができる。
【００４９】
上記した実施形態によれば、エッジ判別においてパターン分類を系統化し、演算量を軽減したので、短時間でかつ効率よくエッジ検出を行うことができる。
【００５０】
なお、本実施形態では四角形の隣接する２辺の組み合わせからなる経路について説明したが、これに限定されず、多角形の１辺または２辺以上の隣接する辺の組み合わせにより構成される経路に適用することができる。さらには閉領域を経路とすることも可能である。
【００５１】
本発明のエッジ判別方法は、画像入力機器（デジタルカメラ、スキャナ、コピー、ファックス）や画像表示装置におけるエッジの判別に適用可能である。特には、画像入力機器、画像表示装置における画像の変倍処理のための補間処理において、エッジの判別を行う場合に用いることができる。
【図面の簡単な説明】
【００５２】
【図１】注目する位置Ｘの周りの４画素からなる四角形について取り得る経路を示す図である。
【図２】注目する位置Ｘの周りの４画素からなる四角形と、その周りの１２画素からなる四角形について取り得る経路を示す図である。
【図３】番号１〜１２を付与した外側の１２画素を示す図である。
【図４】各種のエッジの状態と、これを式１で説明した方法で符号化して得られるエッジフラグの状態を示している。
【図５】本実施形態に係るエッジ判別方法の詳細を説明するための図である。
【図６】経路ｐ、ｑについての経路の一例を示す図である。
【図７】フラグパターンを分類したようすを示す図である。
【図８】フラグパターンを分類したようすを示す図である。
【図９】フラグパターンを分類したようすを示す図である。
【図１０】フラグパターンに対して回転操作（０°，９０°，１８０°，２７０°）または線対称の反転操作（上下反転）を行ったパターンとそれに対する符号を示す図である。
【図１１】ｆｌｇ_１，ｆｌｇ_２が同時に同じフラグになる例を示す図である。
【図１２】２値化した画像に対して、経路上にエッジが１個だけ有る場合にのみ１を出力するロジックの一例を示す図である。
【図１３】従来のエッジ検出の第１の方法について説明するための図である。
【図１４】効率性を考慮した従来のエッジ検出の第２の方法を説明するための図である。
【符号の説明】
【００５３】
１〜７  入力
１０−１〜１０−６  ＥＸ−ＯＲ回路
１１  反転器
１２  比較器
１３  反転器
１４  加算器
１５  乗算器
【図１】
2006146787.tif 000003
【図２】
2006146787.tif 000004
【図３】
2006146787.tif 000005
【図４】
2006146787.tif 000006
【図５】
2006146787.tif 000007
【図６】
2006146787.tif 000008
【図７】
2006146787.tif 000009
【図８】
2006146787.tif 000010
【図９】
2006146787.tif 000011
【図１０】
2006146787.tif 000012
【図１１】
2006146787.tif 000013
【図１２】
2006146787.tif 000014
【図１３】
2006146787.tif 000015
【図１４】
2006146787.tif 000016