TOP > 国内特許検索 > 画像処理装置、方法およびプログラム > 明細書

明細書 :画像処理装置、方法およびプログラム

発行国 日本国特許庁(JP)
公報種別 特許公報(B2)
特許番号 特許第3883993号 (P3883993)
公開番号 特開2005-071243 (P2005-071243A)
登録日 平成18年11月24日(2006.11.24)
発行日 平成19年2月21日(2007.2.21)
公開日 平成17年3月17日(2005.3.17)
発明の名称または考案の名称 画像処理装置、方法およびプログラム
国際特許分類 G06T   3/00        (2006.01)
G06T   7/60        (2006.01)
FI G06T 3/00 500A
G06T 7/60 150D
G06T 7/60 150S
請求項の数または発明の数 27
全頁数 19
出願番号 特願2003-303000 (P2003-303000)
出願日 平成15年8月27日(2003.8.27)
審査請求日 平成15年9月29日(2003.9.29)
特許権者または実用新案権者 【識別番号】503360115
【氏名又は名称】独立行政法人科学技術振興機構
発明者または考案者 【氏名】寅市 和男
【氏名】河副 文夫
【氏名】中村 浩二
【氏名】ポール・ダブリュー・エイチ・カン
【氏名】諸岡 泰男
個別代理人の代理人 【識別番号】100103171、【弁理士】、【氏名又は名称】雨貝 正彦
審査官 【審査官】▲広▼島 明芳
参考文献・文献 特開昭60-049483(JP,A)
特開平11-069170(JP,A)
特開昭64-053272(JP,A)
調査した分野 G06T 1/00 - 7/60
特許請求の範囲 【請求項1】
画像の入力を行う画像入力手段と、
前記画像入力手段によって入力された画像の形状を示す複数のセグメントを抽出するセグメント抽出手段と、
前記セグメント抽出手段によって抽出されたセグメントに対して、このセグメントの始点と終点を初期状態として、誤差が基準値以下になるまでセグメント長を減少させて、円弧および直線のそれぞれに対応する区間を検出する関数区間検出手段と、を備え、
前記関数区間検出手段は、前記セグメントの全部あるいは一部を検出候補に設定し、この検出候補とその始点および終点を通る円弧あるいは直線との間の誤差が前記基準値を超える場合には前記検出候補を短くし、反対に前記誤差が前記基準値以下になった場合には前記検出候補を長くすることにより最終的に決定された前記検出候補を円弧あるいは直線に対応する区間として検出するとともに、前記検出候補の長さを増減する場合の増減の長さである調整値Lを最初は前記セグメントの長さの半分に設定し、2回目以降の増減における前記調整値Lを前回の1/2に設定することを特徴とする画像処理装置。
【請求項2】
請求項1において、
前記セグメント抽出手段は、
前記画像の輪郭線に対応する画素列に含まれる接合点を抽出する接合点抽出手段と、
前記接合点抽出手段によって抽出された接合点を境界として、前記画素列を前記複数のセグメントに分割するセグメント分割手段と、
を有することを特徴とする画像処理装置。
【請求項3】
請求項2において、
前記接合点抽出手段は、前記画素列の前後の配置に基づいて、明らかな角点に相当する画素を前記接合点として抽出することを特徴とする画像処理装置。
【請求項4】
請求項1~3のいずれかにおいて、
前記関数区間検出手段は、前記複数のセグメントのそれぞれについて、直線に対応する区間検出と円弧に対応する区間検出とを別々に行うことを特徴とする画像処理装置。
【請求項5】
請求項4において、
前記関数区間検出手段によって検出された円弧、直線、これらの円弧および直線以外の部分の順に、円弧、直線、自由曲線をそれぞれ当てはめて関数化処理を行う関数化処理手段をさらに備えることを特徴とする画像処理装置。
【請求項6】
請求項5において、
前記関数化処理手段は、前記関数区間検出手段によって検出された円弧と直線に共通の画素が含まれている場合に、円弧を優先させて関数化処理を行うことを特徴とする画像処理装置。
【請求項7】
請求項1~6のいずれかにおいて、
前記関数区間検出手段は、円弧に対応する区間を検出する場合に、前記検出候補の始点、終点およびこれら以外の中間点を通る円弧と前記検出区間との誤差を算出することを特徴とする画像処理装置。
【請求項8】
請求項1~7のいずれかにおいて、
前記関数区間検出手段は、前記検出候補を構成する各画素と検出対象となる前記近似関数との距離の二乗の平均値e1を前記誤差として計算することを特徴とする画像処理装置。
【請求項9】
請求項8において、
前記関数区間検出手段は、前記平均値e1とともに、前記検出候補を構成する各画素と検出対象となる前記近似関数との距離の二乗の最大値e2を前記誤差として計算することを特徴とする画像処理装置。
【請求項10】
画像の入力を行う第1のステップと、
入力された画像の形状を示す複数のセグメントを抽出する第2のステップと、
抽出された前記セグメントに対して、このセグメントの始点と終点を初期状態として、誤差が基準値以下になるまでセグメント長を減少させて、円弧および直線のそれぞれに対応する区間を検出する第3のステップと、を備え、
前記第3のステップでは、前記セグメントの全部あるいは一部を検出候補に設定し、この検出候補とその始点および終点を通る円弧あるいは直線との間の誤差が前記基準値を超える場合には前記検出候補を短くし、反対に前記誤差が前記基準値以下になった場合には前記検出候補を長くすることにより最終的に決定された前記検出候補を円弧あるいは直線に対応する区間として検出するとともに、前記検出候補の長さを増減する場合の増減の長さである調整値Lを最初は前記セグメントの長さの半分に設定し、2回目以降の増減における前記調整値Lを前回の1/2に設定することを特徴とする画像処理方法。
【請求項11】
請求項10において、
前記第2のステップは、
前記画像の輪郭線に対応する画素列に含まれる接合点を抽出する第4のステップと、
抽出された前記接合点を境界として、前記画素列を前記複数のセグメントに分割する第5のステップと、
を有することを特徴とする画像処理方法。
【請求項12】
請求項11において、
前記第4のステップは、前記画素列の前後の配置に基づいて、明らかな角点に相当する画素を前記接合点として抽出することを特徴とする画像処理方法。
【請求項13】
請求項10~12のいずれかにおいて、
前記第3のステップでは、前記複数のセグメントのそれぞれについて、直線に対応する区間検出と円弧に対応する区間検出とが別々に行われることを特徴とする画像処理方法。
【請求項14】
請求項13において、
前記第3のステップにおいて検出された円弧、直線、これらの円弧および直線以外の部分の順に、円弧、直線、自由曲線をそれぞれ当てはめて関数化処理を行う第6のステップをさらに有することを特徴とする画像処理方法。
【請求項15】
請求項14において、
前記第6のステップは、前記第3のステップにおいて検出された円弧と直線に共通の画素が含まれている場合に、円弧を優先させて関数化処理を行うことを特徴とする画像処理方法。
【請求項16】
請求項10~15のいずれかにおいて、
前記第3のステップは、円弧に対応する区間を検出する場合に、前記検出候補の始点、終点およびこれら以外の中間点を通る円弧と前記検出区間との誤差を算出することを特徴とする画像処理方法。
【請求項17】
請求項10~16のいずれかにおいて、
前記第3のステップは、前記検出候補を構成する各画素と検出対象となる前記近似関数との距離の二乗の平均値e1を前記誤差として計算することを特徴とする画像処理方法。
【請求項18】
請求項17において、
前記第3のステップは、前記平均値e1とともに、前記検出候補を構成する各画素と検出対象となる前記近似関数との距離の二乗の最大値e2を前記誤差として計算することを特徴とする画像処理方法。
【請求項19】
コンピュータを、
画像の入力を行う画像入力手段と、
前記画像入力手段によって入力された画像の形状を示す複数のセグメントを抽出するセグメント抽出手段と、
前記セグメント抽出手段によって抽出されたセグメントに対して、このセグメントの始点と終点を初期状態として、誤差が基準値以下になるまでセグメント長を減少させて、円弧および直線のそれぞれに対応する区間を検出する関数区間検出手段と、
して機能させるための画像処理プログラムであって、
前記関数区間検出手段は、前記セグメントの全部あるいは一部を検出候補に設定し、この検出候補とその始点および終点を通る円弧あるいは直線との間の誤差が前記基準値を超える場合には前記検出候補を短くし、反対に前記誤差が前記基準値以下になった場合には前記検出候補を長くすることにより最終的に決定された前記検出候補を円弧あるいは直線に対応する区間として検出するとともに、前記検出候補の長さを増減する場合の増減の長さである調整値Lを最初は前記セグメントの長さの半分に設定し、2回目以降の増減における前記調整値Lを前回の1/2に設定する画像処理プログラム。
【請求項20】
請求項19において、
前記セグメント抽出手段は、
前記画像の輪郭線に対応する画素列に含まれる接合点を抽出する接合点抽出手段と、
前記接合点抽出手段によって抽出された接合点を境界として、前記画素列を前記複数のセグメントに分割するセグメント分割手段と、
を有することを特徴とする画像処理プログラム。
【請求項21】
請求項20において、
前記接合点抽出手段は、前記画素列の前後の配置に基づいて、明らかな角点に相当する画素を前記接合点として抽出することを特徴とする画像処理プログラム。
【請求項22】
請求項19~21のいずれかにおいて、
前記関数区間検出手段は、前記複数のセグメントのそれぞれについて、直線に対応する区間検出と円弧に対応する区間検出とを別々に行うことを特徴とする画像処理プログラム。
【請求項23】
請求項22において、
コンピュータを、さらに、前記関数区間検出手段によって検出された円弧、直線、これらの円弧および直線以外の部分の順に、円弧、直線、自由曲線をそれぞれ当てはめて関数化処理を行う関数化処理手段として機能させるための画像処理プログラム。
【請求項24】
請求項23において、
前記関数化処理手段は、前記関数区間検出手段によって検出された円弧と直線に共通の画素が含まれている場合に、円弧を優先させて関数化処理を行うことを特徴とする画像処理プログラム。
【請求項25】
請求項19~24のいずれかにおいて、
前記関数区間検出手段は、円弧に対応する区間を検出する場合に、前記検出候補の始点、終点およびこれら以外の中間点を通る円弧と前記検出区間との誤差を算出することを特徴とする画像処理プログラム。
【請求項26】
請求項19~25のいずれかにおいて、
前記関数区間検出手段は、前記検出候補を構成する各画素と検出対象となる前記近似関数との距離の二乗の平均値e1を前記誤差として計算することを特徴とする画像処理プログラム。
【請求項27】
請求項26において、
前記関数区間検出手段は、前記平均値e1とともに、前記検出候補を構成する各画素と検出対象となる前記近似関数との距離の二乗の最大値e2を前記誤差として計算することを特徴とする画像処理プログラム。
発明の詳細な説明 【技術分野】
【0001】
本発明は、入力画像の輪郭線形状を関数化処理する際にその前処理として輪郭線形状に含まれる直線や円弧等の特定形状の検出を行う画像処理装置、方法およびプログラムに関する。
【背景技術】
【0002】
情報技術の進歩により、デスクトップパブリッシング(DTP)、テレビジョン放送、書籍などの画像を扱う技術分野の進展は著しく、より高精細、高美麗さのニーズも高まっている。また、パーソナルコンピュータとそれを取り巻く種々のデバイスの普及により、デジタル画像の高精細化、処理の高速化が進展し、特にJPEG、GIF、PNGなどに代表される画像の圧縮、拡大・縮小等の画像変換技術の進展は目覚しい。
【0003】
しかし、これらの一般的なJPEG、GIF、PNGに代表されるピクセル符号化方式では、拡大時にジャギーノイズを生じるなど、画質が劣化してしまうため、関数符号化方式が提案されている。画像の輪郭を追跡し、それを関数近似することによって、ピクセル符号化画像を関数符号化画像へ自動的に変換する手法の研究が行われている(例えば、特許文献1参照。)。
【0004】
例えば、文字、イラスト、ロゴマークといった画像をフルーエンシ関数系により高精度に関数化することができる。フルーエンシ情報理論では、信号の滑らかさの基準を示す連続微分可能性に基づいたパラメータmを用いて信号空間を類別している。m次のフルーエンシ関数は、(m-2)回のみ連続微分可能な(m-1)次の区分的多項式から構成されている。画像関数近似では、輪郭線はその形状によった種類の関数を用いて近似される。m=2、m=3、m=∞のフルーエンシ関数はそれぞれ、直線、自由曲線、円弧を表現するのに用いられる。

【特許文献1】特開2001-51670号公報(第5-13頁、図1-11)
【発明の開示】
【発明が解決しようとする課題】
【0005】
ところで、上述した特許文献1に開示された手法では、輪郭線の形状を関数化処理する前処理として、明らかに直線と判断される部分を直線区間として検出し、このような直線と判断される部分が隣接する場合にはこれらの隣接部分を一つにして直線区間を延長する処理を行っている。このように、輪郭線の一部を構成する短い直線区間を延長し、輪郭線形状と直線との誤差が少ない場合にはこの直線区間を徐々に伸ばしていく方法では、誤差によって直線でないと判断される短い区間があると、その周辺が直線区間であっても、全体が一つの直線区間とは判断されないことになり、誤差の影響を受けやすいため、単一形状の長い区間検出が難しいという問題があった。検出される単一形状の区間は、長ければ長いほど、データ量の削減等の観点からは、その後に行われる近似関数の決定において有利である。また、直線区間の検出だけでなく、円弧区間を検出する場合にも同様の問題がある。
【0006】
本発明は、このような点に鑑みて創作されたものであり、その目的は、画素列に含まれる単一形状の長い区間検出を行うことができる画像処理装置、方法およびプログラムを提供することにある。
【課題を解決するための手段】
【0007】
上述した課題を解決するために、本発明の画像処理装置は、画像の入力を行う画像入力手段と、画像入力手段によって入力された画像の形状を示す複数のセグメントを抽出するセグメント抽出手段と、セグメント抽出手段によって抽出されたセグメントに対して、このセグメントの始点と終点を初期状態として、誤差が基準値以下になるまでセグメント長を減少させて、近似関数に対応する区間を検出する関数区間検出手段とを備えている。
【0008】
また、本発明の画像処理方法は、画像の入力を行う第1のステップと、入力された画像の形状を示す複数のセグメントを抽出する第2のステップと、抽出されたセグメントに対して、このセグメントの始点と終点を初期状態として、誤差が基準値以下になるまでセグメント長を減少させて、近似関数に対応する区間を検出する第3のステップとを有している。
【0009】
また、本発明の画像処理プログラムは、コンピュータを、画像の入力を行う画像入力手段と、画像入力手段によって入力された画像の形状を示す複数のセグメントを抽出するセグメント抽出手段と、セグメント抽出手段によって抽出されたセグメントに対して、このセグメントの始点と終点を初期状態として、誤差が基準値以下になるまでセグメント長を減少させて、近似関数に対応する区間を検出する関数区間検出手段として機能させる。
【0010】
このように、画像の形状を示す各セグメントについてセグメント全体を初期状態として誤差が少なくなるまで徐々にセグメントを短くすることにより近似関数に対応する区間の検出が行われるため、近似関数に対応する短い区間を検出した後にこの区間を徐々に伸ばす場合に比べて、近似関数に対応する単一形状の長い区間を検出することが可能になる。
【0011】
また、上述したセグメント抽出手段は、画像の輪郭線に対応する画素列に含まれる接合点を抽出する接合点抽出手段と、接合点抽出手段によって抽出された接合点を境界として、画素列を複数のセグメントに分割するセグメント分割手段とを有することが望ましい。これにより、画像の輪郭線に含まれる近似関数に対応する区間をできるだけ長い状態で検出することができる。
【0012】
また、上述した接合点抽出手段は、画素列の前後の配置に基づいて、明らかな角点に相当する画素を接合点として抽出することが望ましい。明らかな角点のみを接合点として抽出することにより、接合点の設定位置が不適切であったために単一形状の長い区間が誤って分断されることを防止することができる。
【0013】
また、上述した関数区間検出手段によって区間検出が行われる近似関数は直線であることが望ましい。これにより、画像の形状に含まれる長い直線部分の検出が可能になる。また、上述した関数区間検出手段によって区間検出が行われる近似関数は円弧であることが望ましい。これにより、画像の形状に含まれる長い円弧部分の検出が可能になる。
【0014】
また、上述した関数区間検出手段によって区間検出が行われる近似関数は直線と円弧であり、複数のセグメントのそれぞれについて、直線に対応する区間検出と円弧に対応する区間検出とが別々に行われることが望ましい。これにより、画像の形状に含まれる長い直線部分と長い円弧部分を検出することが可能になり、それぞれの検出結果を用いた最適な関数化処理を行うことができる。特に、上述した関数区間検出手段によって検出された円弧、直線、これらの円弧および直線以外の部分の順に、円弧、直線、自由曲線をそれぞれ当てはめて関数化処理を行う関数化処理手段をさらに備えることが望ましい。これにより、自由曲線よりも円弧や直線を優先させて関数化処理を行うことにより、関数化処理によるさらなるデータ量の削減が可能になる。また、上述した関数化処理手段は、関数区間検出手段によって検出された円弧と直線に共通の画素が含まれている場合に、円弧を優先させて関数化処理を行うことが望ましい。円弧は短い直線の集まりとして表現することもできるため、円弧を優先させることにより、精度の高い関数化処理を行うことが可能になる。
【0015】
また、上述した関数区間検出手段は、セグメントの全部あるいは一部を検出候補に設定し、この検出候補とその始点および終点を結ぶ直線との間の誤差が基準値を超える場合には検出候補を短くし、反対に誤差が基準値以下になった場合には検出候補を長くすることにより最終的に決定された検出候補を直線に対応する区間として検出することが望ましい。これにより、次第にセグメントに含まれる直線部分を絞っていって最終的に検出可能な最大長の直線部分を検出することが可能になる。
【0016】
また、上述した関数区間検出手段は、セグメントの全部あるいは一部を検出候補に設定し、この検出候補とその始点、終点およびこれら以外の中間点を通る円弧との間の誤差が基準値を超える場合には検出候補を短くし、反対に誤差が基準値以下になった場合には検出候補を長くすることにより最終的に決定された検出候補を円弧に対応する区間として検出することが望ましい。これにより、次第にセグメントに含まれる円弧部分を絞っていって最終的に検出可能な最大長の円弧部分を検出することが可能になる。
【0017】
また、上述した関数区間検出手段は、それまでの検出候補の長さをLとしたときに、L/2だけ検出候補の長さを長くあるいは短くすることが望ましい。これにより、最終的に直線部分あるいは円弧部分を検出するまでの検出候補の長さを変更する回数の削減が可能になり、直線部分あるいは円弧部分の検出に要する時間を短縮することができる。
【0018】
また、上述した関数区間検出手段は、検出候補を構成する各画素と検出対象となる近似関数との距離の二乗の平均値e1を誤差として計算することが望ましい。平均二乗誤差e1によって誤差の大小を評価することにより、画像の読み取り等において発生するノイズの影響を少なくすることができる。
【0019】
また、上述した関数区間検出手段は、平均値e1とともに、検出候補を構成する各画素と検出対象となる近似関数との距離の二乗の最大値e2を誤差として計算することが望ましい。検出対象となる直線部分や円弧部分を長くすればするほど、これらの近似関数の形状に一致しない局所的な特異形状があっても平均二乗誤差e1が小さくなるため、この特異形状部分が無視されて関数化処理が行われやすくなる。しかし、最大二乗誤差e2が考慮されるため、局所的な特異形状が無視されることがなく、精度の高い関数化処理を行うことができる。
【発明を実施するための最良の形態】
【0020】
以下、本発明を適用した一実施形態の画像処理装置について、図面に基づいて詳細に説明する。
【0021】
図1は、一実施形態の画像処理装置の構成を示す図である。図1に示すように、本実施形態の画像処理装置は、画像処理演算部100、スキャナ200、キーボード210、マウス212、ディスプレイ装置220、プリンタ230を含んで構成されている。
【0022】
スキャナ200は、ロゴマーク等の被写体を光学的に読み取って、白黒の二値画像を生成する。この生成された二値画像は、画像処理演算部100に入力される。キーボード210およびマウス212は、画像処理演算部100に対して利用者が各種の操作指示を行うために用いられる。例えば、スキャナ200を用いた画像取込の操作指示や、その後の関数化処理の演算開始指示、関数化処理された画像データから原画像への復元指示、復元の際の拡大倍率等がキーボード210やマウス212を用いて行われる。
【0023】
ディスプレイ装置220は、各種の操作画面や、取り込んだ画像および関数化処理された画像データを用いて原画像を復元した結果等を表示する。プリンタ230は、復元された所定倍率の原画像を所定サイズの紙に印刷する。
【0024】
画像処理演算部100は、入力画像に対して関数化処理を行うとともに、この関数化されたデータに基づいて画像を生成する処理を行う。このために、画像処理演算部100は、画像格納部110、画素列追跡部120、接合点抽出部130、セグメント分割部140、直線検出部150、円弧検出部160、関数化処理部170、出力画像生成部180を備えている。この画像処理演算部100は、CPU、ROM、RAMおよびハードディスク装置を備えたコンピュータによって実現することが可能であり、ROM、RAMあるいはハードディスク装置に格納された画像処理プログラムをCPUで実行することにより、画素列追跡部120、接合点抽出部130、セグメント分割部140、直線検出部150、円弧検出部160、関数化処理部170、出力画像生成部180の各機能が実現される。また、画像格納部110は、主にハードディスク装置によって実現される。
【0025】
画像格納部110は、スキャナ200を用いて読み取られた原画像に対応する画像データや、関数化処理等を行うために必要な中間データ、関数化処理によって得られた関数化データ等を格納する。
【0026】
画素列追跡部120は、入力画像の輪郭線を構成する画素列に対して追跡処理を行う。例えば、二値化処理された後の入力画像に対してその輪郭線を抽出する処理が行われる。なお、二値化処理された入力画像の代わりに多値画像が入力された場合には、画素列追跡処理の前処理として二値化処理を行えばよい。また、カラー画像が入力された場合には、RGBの各色成分に分解した後に二値化処理を行って、各色成分毎に以後の処理を実施するようにしてもよい。
【0027】
接合点抽出部130は、画素列追跡部120による追跡によって得られた画素列の中から明らかな接合点を抽出する。ここで、接合点とは、その前後で画素列の傾向が変化する画素である。例えば、接合点抽出部130は、デジタル曲率に基づいて前後の輪郭線が所定角度以上屈曲した角点を明らかな接合点として抽出する。具体的には、輪郭線を構成する画素列の一点P0 に着目し、その前後に画素K個分だけ離れた点P1 、P2 を設定し、線分P0 1 と線分P0 2 のなす角度の余弦Cを計算する。そして、この計算した余弦Cが所定値(例えば-0.6)以上であるときに、この着目点を角点、すなわち明らかな接合点として抽出する。この計算を輪郭線を構成する画素列の全てについて行うことにより、画素列に含まれる全ての明らかな接合点が抽出される。
【0028】
なお、上述した説明では、余弦Cが-0.6以上のときに着目点が角点であると判定したが、この判定の閾値(-0.6)は適宜変更してもよい。また、入力画像が回路図のように細線からなる場合には、入力画像そのものが輪郭線に相当し、しかも輪郭線を構成する画素列に分岐が含まれるため、この分岐を明らかな接合点として抽出するようにしてもよい。
【0029】
セグメント分割部140は、接合点抽出部130によって抽出された接合点を用いて、画素列追跡部120によって追跡された画素列を複数のセグメントに分割する。直線検出部150は、セグメント分割部140によって分割された各セグメントに含まれる直線部分を検出する。同様に、円弧検出部160は、セグメント分割部140によって分割された各セグメントに含まれる円弧部分を検出する。これらの直線部分および円弧部分の検出は、全てのセグメントを対象にして個別に行われるため、並行して行ってもよいし、前後して別々に行うようにしてもよい。本実施形態の画像処理装置では、最も長い直線部分や円弧部分を、後処理で延長することなく直接検出している点に特徴がある。
【0030】
関数化処理部170は、セグメント分割部140によって複数に分割された各セグメント毎に、直線検出部150および円弧検出部160による検出結果を用いて関数化処理を行う。具体的には、自由曲線、円弧、直線のいずれかの関数を輪郭線形状に当てはめて関数化処理を行うが、円弧部分や直線部分はわずかに形状がゆがんでも不自然に感じるとともにデータ量削減の観点からも、これらを用いた関数化処理が可能な場合には自由曲線よりも優先的に円弧や直線による関数化処理を行う必要がある。また、円弧は短い直線の集まりでも表現できることから、直線よりも円弧を優先する方が好ましい。したがって、円弧検出部160によって検出された円弧部分に直線検出部150によって検出された直線部分が含まれている場合には、この共通する画素については円弧を用いて関数化処理される。それ以外の直線部分に含まれる画素については直線を用いて関数化処理され、円弧にも直線にも含まれない画素については自由曲線(例えば二次曲線)を用いて関数化処理される。
【0031】
出力画像生成部180は、関数化処理部170によって得られた関数化データを用いて原画像を生成する。この原画像生成では倍率を指定することができ、原画像を指定された倍率で拡大した画像が生成される。
【0032】
上述したスキャナ200が画像入力手段に、接合点抽出部130、セグメント分割部140がセグメント抽出手段に、接合点抽出部130が接合点抽出手段に、セグメント分割部140がセグメント分割手段に、直線検出部150、円弧検出部160が関数区間検出手段に、関数化処理部170が関数化処理手段にそれぞれ対応する。
【0033】
本実施形態の画像処理装置はこのような構成を有しており、次にその動作を説明する。
【0034】
図2は、本実施形態の画像処理装置の全体の動作手順を示す流れ図である。画像格納部110は、スキャナ200を用いて読み取られた画像が入力されると(ステップ100)、この入力画像データを格納する。
【0035】
次に、画素列追跡部120は、入力画像の輪郭線を構成する画素列に対して追跡を行う(ステップ101)。また、接合点抽出部130は、追跡された画素列に含まれる明らかな接合点を抽出する(ステップ102)。セグメント分割部140は、抽出された接合点によって輪郭線を構成する画素列を複数のセグメントに分割する(ステップ103)。
【0036】
次に、直線検出部150は、セグメント分割部140によって分割された一のセグメントを取り出してこのセグメントに含まれる直線部分を検出する(ステップ104)。なお、セグメントによっては直線部分が全く含まれない場合や複数個が離散的に含まれる場合が考えられる。直線検出部150は、一のセグメントについて直線部分の検出処理を終了すると、輪郭線を構成する全てのセグメントについて直線部分の検出処理が終了したか否かを判定する(ステップ105)。直線部分の検出処理が行われていないセグメントが存在する場合には否定判断が行われ、未処理の他のセグメントについてステップ104の直線部分の検出処理が繰り返される。
【0037】
また、輪郭線を構成する全てのセグメントについて直線部分の検出処理が終了するとステップ105の判定において肯定判断が行われ、次に、同様の手順で各セグメントについて円弧部分の検出が行われる。すなわち、円弧検出部160は、セグメント分割部140によって分割された一のセグメントを取り出してこのセグメントに含まれる円弧部分を検出する(ステップ106)。なお、セグメントによっては円弧部分が全く含まれない場合や複数個が離散的に含まれる場合が考えられる。円弧検出部160は、一のセグメントについて円弧部分の検出処理を終了すると、輪郭線を構成する全てのセグメントについて円弧部分の検出処理が終了したか否かを判定する(ステップ107)。円弧部分の検出処理が行われていないセグメントが存在する場合には否定判断が行われ、未処理の他のセグメントについてステップ106の円弧部分の検出処理が繰り返される。
【0038】
なお、上述した説明では、ステップ104、105において直線部分の検出動作を行った後にステップ106、107において円弧部分の検出動作を行ったが、これら2種類のの検出動作は、並行して行ったり、順番を反対にして行うようにしてもよい。
【0039】
このようにして輪郭線を構成する全てのセグメントについて直線部分と円弧部分の検出が終了した後、関数化処理部170は、分割されたセグメント毎に、関数化処理(関数近似処理)を行う(ステップ108)。例えば、最初に、円弧検出部160によって検出された各円弧部分に対して円弧を当てはめる関数化処理を行い、次に、直線検出部150によって検出された直線部分に対して直線を当てはめる関数化処理を行い(直線部分の一部あるいは全部が円弧部分に含まれる場合には、その範囲については円弧による関数近似を優先させる)、最後に、円弧部分にも直線部分にも該当しない画素列に対して自由曲線を用いた関数化処理を行う。このようにして関数化処理された結果は画像格納部110に格納される(ステップ109)。出力画像生成部180は、関数化処理された結果を用いて、元の画像を所定倍率で拡大して復元する処理を行う。このようにして復元された画像がディスプレイ装置220の画面に表示されたり、プリンタ230から記録紙に印刷される(ステップ110)。
【0040】
次に、直線検出部150によって行われる直線部分の検出動作の詳細について説明する。図3、図4および図5は、直線検出部150による直線部分の検出動作の詳細を示す流れ図である。
【0041】
まず、直線検出部150は、一のセグメントを読み込んで(ステップ200)、この読み込んだセグメントの始点と終点のそれぞれを比較直線の始点と終点に設定するとともに(ステップ201)、調整値Lをセグメント長に設定する(ステップ202)。ここで、「比較直線」とは、始点と終点が一致したセグメント(検出候補)と比較され、誤差算出が行われる直線である。また、「調整値L」とは、比較直線とセグメントとを比較した結果に応じて、処理対象となるセグメントの長さを増減する場合のその増減の長さであり、処理の途中で順次値が変更される。また、セグメント長は、隣接する画素間の距離をこれらの画素の配置状態にかかわらずに(左右上下に配置されている場合と斜め方向に配置されている場合とで区別することなく)1として、構成画素数で示したものである。
【0042】
次に、直線検出部150は、比較直線とセグメントとの間の平均二乗誤差e1と最大二乗誤差e2を算出する(ステップ203、204)。ここで、平均二乗誤差e1とは、セグメントを構成する各画素から比較直線に下ろした垂線の長さを二乗した合計値をセグメントの画素数で割った値である。また、最大二乗誤差e2とは、セグメントの構成する各画素から比較直線に下ろした垂線の長さを二乗した値の最大値である。なお、平均二乗誤差e1と最大二乗誤差e2の計算の順番はどちらが先であってもよいし、並行して行うようにしてもよい。
【0043】
次に、直線検出部150は、平均二乗誤差e1が基準値E1未満で、かつ、最大二乗誤差e2が基準値E2未満であるか否かを判定する(ステップ205)。例えば、実験的評価からE1=0.2、E2=1.0に設定されている。これら2つの条件を満たす場合には肯定判断が行われ、次に、直線検出部150は、上述した比較線分を直線候補Dとして画像格納部110に格納して記憶した後(ステップ206)、比較直線の終点がセグメントの終点の初期値と一致するか否かを判定する(ステップ207)。セグメントの終点の初期値とは、ステップ200において読み込まれたセグメントの終点のことであり、輪郭線を分割した際の接合点に一致する。本実施形態では、セグメントの形状が比較直線にほぼ一致していて平均二乗誤差e1と最大二乗誤差e2がともに小さい場合には、セグメントの終点が延長された後に同様の判定処理が繰り返されるが、比較直線の終点がセグメントの終点の初期値と同じ場合にはこのような終点の延長を行うことができないため、このような場合には肯定判断が行われた後、直線検出部150は、直線候補Dを検出直線Sとして記憶する(ステップ214)。これにより、ステップ200において読み込まれた一のセグメントの全体に対する直線部分の検出動作が終了する。
【0044】
また、比較直線の終点とセグメントの終点の初期値とが一致しない場合にはステップ207の判定において否定判断が行われる。次に、直線検出部150は、調整値Lの値を半分にした後(ステップ208)、この変更後の調整値Lが所定値以下か否かを判定する(ステップ209)。上述したように、本実施形態では、セグメントの形状が比較直線にほぼ一致している場合に、セグメントの終点を延長するがこの延長する長さ(調整値L)は延長する回数が増えるにしたがってそれぞれ半分に減っていく(ステップ208)。したがって、調整値Lが小さな値に収束したときにステップ209において肯定判断が行われる。次に、直線検出部150は、直線候補Dを検出直線Sとして記憶する(ステップ211)。また、直線検出部150は、セグメントの始点を検出直線Sの終点に、セグメントの終点を初期値にそれぞれ設定した後(ステップ212)、この始点と終点が変更されたセグメントの長さが所定値以下であるか否かを判定する(ステップ213)。これは、あまりにも短いセグメントに対して直線部分の検出を行わないようにするための判定動作であり、セグメント長が短くなりすぎた場合には肯定判断が行われ、ステップ200において読み込まれた一のセグメントの全体に対する直線部分の検出動作が終了する。一方、セグメント長が所定値よりも長い場合にはステップ213の判定において否定判断が行われ、ステップ202に戻って、新しいセグメントについて直線部分を検出する動作が繰り返される。
【0045】
また、変更後の調整値Lが所定値よりも大きい場合にはステップ209の判定において否定判断が行われ、次に、直線検出部150は、セグメントの終点を調整値Lだけ終点の初期値側にずらした後(ステップ210)、ステップ203に戻って平均二乗誤差e1や最大二乗誤差e2の計算以降の動作が繰り返される。
【0046】
また、「平均二乗誤差e1が基準値E1未満、かつ、最大二乗誤差e2が基準値E2未満」という条件を満たさない場合、すなわち、平均二乗誤差e1が基準値E1以上であったり、あるいは、最大二乗誤差e2が基準値E2以上である場合にはステップ205の判定において否定判断が行われる。次に、直線検出部150は、セグメント長は所定値以下か否かを判定する(ステップ215)。この判定は、これ以上セグメント長を短くして直線部分の検出を継続するか否かを判定するために行われるものである。セグメント長が短くて所定値以下の場合には肯定判断が行われ、直線検出部150は、セグメントの始点を調整値Lだけ終点側にずらすとともに(ステップ216)、セグメントの終点を初期値に設定する(ステップ217)。このように、セグメントに含まれる直線部分が検出されずに比較直線とセグメントが徐々に短くなって所定値以下になってしまった場合には、ここでのセグメントの終点側の残りのセグメントを用いて新たに直線部分の検出動作を行うために新しいセグメントの始点と終点の再設定が行われた後、ステップ202に戻って直線部分を検出する動作が繰り返される。
【0047】
また、セグメント長が所定値よりも大きい場合にはステップ215の判定において否定判断が行われる。次に、直線検出部150は、調整値Lの値を半分にするとともに(ステップ218)、セグメントの終点を調整値Lだけ始点側にずらしてセグメントを短くした後(ステップ219)、ステップ203に戻って平均二乗誤差e1や最大二乗誤差e2の計算以降の動作が繰り返される。
【0048】
図6および図7は、直線部分の検出の具体例を示す図である。直線検出部150は、最初は、セグメント分割部140によって分割された一のセグメントSG(0)の全体と、このセグメントSG(0)の始点S(0)と終点E(0)を通る比較直線とを比較し、平均二乗誤差e1と最大二乗誤差e2の両方が所定の条件を満たすか否かを調べる(図6(A))。
【0049】
この例では条件を満たさないため、次に、セグメント長の半分に設定された調整値Lだけ始点S(0)側にずらしたセグメントSG(1)の新たな終点E(1)を設定した後(ステップ218、219)、この短くなったセグメントSG(1)と、このセグメントSG(1)の始点S(0)と終点E(1)を通る新たな比較直線とを比較し、平均二乗誤差e1と最大二乗誤差e2の両方が所定の条件を満たすか否かを調べる(図6(B))。
【0050】
この例ではこれら2つの条件を満たしており、次に、さらに半分の値に変更された調整値Lだけ終点E(0)側にずらしたセグメントSG(2)の新たな終点E(2)を設定した後(ステップ208、210)、この少し長くなったセグメントSG(2)と、このセグメントSG(2)の始点S(0)と終点E(2)を通る新たな比較直線とを比較し、平均二乗誤差e1と最大二乗誤差e2の両方が所定の条件を満たすか否かを調べる(図6(C))。
【0051】
このようにして、セグメントの終点位置が順次変更され、最終的に始点S(0)の最も長い比較直線が検出直線Sとして検出される。一の検出直線Sが決定された後は、この検出直線S以外の残りの部分を検出対象としての新たなセグメントに設定し(ステップ212)、再度直線部分の検出動作が繰り返される。
【0052】
なお、セグメント分割部140によって分割された一のセグメントSG(0)の始点S(0)近傍に直線部分が含まれない場合(図7(A))には、セグメント長をどれだけ短くしていっても平均二乗誤差e1や最大二乗誤差e2の両方が所定の条件を満たすようにはならない。このような場合には、終点E(0)側にずらした始点S(1)を有するあらたなセグメントが設定され(ステップ216、217)、再度直線部分の検出動作が繰り返される(図7(B))。
【0053】
円弧検出部160によって行われる円弧部分の検出動作についても上述した直線検出動作と基本的に同じであり、以下では相違点に着目して説明する。
【0054】
図8、図9および図10は、円弧検出部160による円弧部分の検出動作の詳細を示す流れ図である。これらの図に示す流れ図は、図3~図5に示した流れ図に含まれる比較直線を比較円弧に、直線候補Dを円弧候補Dに、検出直線Sを検出円弧Sにそれぞれ変更するとともにステップ数を改めた点が異なっており、動作手順自体は基本的に同じである。
【0055】
また、平均二乗誤差e1と最大二乗誤差e2の算出方法については、直線と円弧とでは異なっている。具体的には、セグメントの始点と終点の他に中間点を合わせた3点を通る円弧を比較円弧として設定し、この円弧の半径と円弧の中心からセグメントを構成する画素までの距離の差の二乗を用いて平均二乗誤差e1や最大二乗誤差e2が計算される。
【0056】
なお、円弧検出の検出精度を高めるために以下の(1)~(3)の工夫がなされている。
【0057】
(1)比較円弧を設定する際の3点はセグメントの始点、終点、中間点を基本とするが、円弧の中心角が4π/3以上の場合、始点と終点が接近しすぎて、近似円のふれが大きくなってしまう。そのため、円弧の中心角が4π/3以上の場合は始点と始点からの中心角が4π/3となる点とこれらの中間点により比較円弧の設定を行う。
【0058】
(2)比較円弧の中心角によって基準値E1、E2の値を変化させる。中心角の大きな比較円弧については、基準値E1、E2を大きくして判断の基準を甘くするようにする。
【0059】
(3)中心角に閾値を設け、あまりに中心角が小さな比較円弧は設定されないようにする。例えば、中心角がπ/2よりも小さな比較円弧は設定されないようにする。
【0060】
図11、図12、図13および図14は、具体的な図形に対して直線検出と円弧検出を行った実験結果を示す図であり、本実施形態の手法と従来手法の両方を用いた結果が示されている。実験では図11に示す画像が用いられた。
【0061】
図12(A)、(B)には、本実施形態の手法によって検出された直線部分と円弧部分がそれぞれ示されている。これらの図に含まれる「×」は、検出された直線あるいは円弧の始点あるいは終点を示している。また、図12(A)において点線で囲まれた部分は直線として検出されたが、結果的には優先順位にしたがって円弧として関数近似された部分を表している。また、比較のために、図13(A)、(B)には従来の多段抽出法を用いて検出された直線部分と円弧部分がそれぞれ示されている。図14(A)、(B)には従来のDP(Dynamic Programming)法を用いて検出された直線部分と円弧部分がそれぞれ示されている。
【0062】
図12~図14を比較して明らかなように、本実施形態の手法を用いることにより、従来手法に比べて、より長い直線部分、円弧部分を検出することに成功している。また、本実施形態の手法で検出した直線部分、円弧部分は、従来手法で検出した直線部分、円弧部分を包含していることがわかる。これは、従来手法が開始点から直線、円弧区間を徐々に延ばしていくアルゴリズムであるのに対して、本実施形態の手法はセグメント画素列の最大長から直線、円弧区間を徐々に削っていくアルゴリズムであるからであると思われる。
【0063】
このように、画像の輪郭形状を示す各セグメントについてセグメント全体を初期状態として誤差が少なくなるまで徐々にセグメントを短くすることにより近似関数に対応する区間の検出が行われるため、近似関数に対応する短い区間を検出した後にこの区間を徐々に伸ばす場合に比べて、近似関数に対応する単一形状の長い区間を検出することが可能になる。
【0064】
また、画像の輪郭線を構成する画素列の前後の配置に基づいて、明らかな角点に相当する画素を接合点として抽出することにより、画素列を複数のセグメントに分割しており、明らかな角点のみを接合点として抽出することにより、接合点の設定位置が不適切であったために単一形状の長い区間が誤って分断されることを防止することができる。
【0065】
また、区間検出が行われる近似関数として直線あるいは円弧を採用することにより、画像の輪郭線形状に含まれる長い直線部分あるいは円弧部分の検出が可能になる。
【0066】
また、複数のセグメントのそれぞれについて、直線に対応する区間検出と円弧に対応する区間検出とを別々に行うことにより、画像の形状に含まれる長い直線部分と長い円弧部分の両方を検出することが可能になり、それぞれの検出結果を用いた最適な関数化処理を行うことができる。特に、上述した関数区間検出手段によって検出された円弧、直線、これらの円弧および直線以外の部分の順に、円弧、直線、自由曲線をそれぞれ当てはめて、自由曲線よりも円弧や直線を優先させて関数化処理を行うことにより、関数化処理によるさらなるデータ量の削減が可能になる。また、検出された円弧と直線が重複している場合に、円弧を優先させて関数化処理を行うことにより、精度の高い関数化処理を行うことが可能になる。
【0067】
また、分割された各セグメントの全部あるいは一部を検出候補としてのセグメントに設定し、この検出候補としてのセグメントとその始点および終点を結ぶ直線との間の誤差が基準値を超える場合には検出候補としてのセグメントを短くし、反対に誤差が基準値以下になった場合には検出候補としてのセグメントを長くすることにより最終的な直線部分を検出することにより、次第にセグメントに含まれる直線部分を絞っていって最終的に検出可能な最大長の直線部分を検出することが可能になる。
【0068】
また、分割された各セグメントの全部あるいは一部を検出候補としてのセグメントに設定し、この検出候補としてのセグメントとその始点、終点およびこれらの中間点を通る円弧との間の誤差が基準値を超える場合には検出候補としてのセグメントを短くし、反対に誤差が基準値以下になった場合には検出候補としてのセグメントを長くすることにより最終的な円弧部分を検出することにより、次第にセグメントに含まれる円弧部分を絞っていって最終的に検出可能な最大長の円弧部分を検出することが可能になる。
【0069】
また、直線部分あるいは円弧部分の検出は、それまでの検出候補としてのセグメントのの長さをLとしたときに、L/2だけセグメント長を長くあるいは短くして行っており、これにより、最終的に直線部分あるいは円弧部分を検出するまでのセグメント長を変更する回数の削減が可能になり、直線部分あるいは円弧部分の検出に要する時間を短縮することができる。
【0070】
また、平均二乗誤差e1によって誤差の大小を評価することにより、画像の読み取り等において発生するノイズの影響を少なくすることができる。また、検出対象となる直線部分や円弧部分を長くすればするほど、これらの近似関数の形状に一致しない局所的な特異形状があっても平均二乗誤差e1が小さくなるため、この特異形状部分が無視されて関数化処理が行われやすくなる。しかし、最大二乗誤差e2が考慮されるため、局所的な特異形状が無視されることがなく、精度の高い関数化処理を行うことができる。
【0071】
なお、本発明は上記実施形態に限定されるものではなく、本発明の要旨の範囲内において種々の変形実施が可能である。上述した実施形態では、スキャナ200を用いて画像入力を行ったが、その他の入力装置(例えばデジタルカメラ)を用いたり、光磁気ディスク等に格納された画像データを読み込むことにより入力するようにしてもよい。
【0072】
また、上述した実施形態では、画像の読み取り等において発生したノイズについては特に対策をしていないが、ノイズ対策を行うことでさらに精度の高い関数化処理を行うようにしてもよい。例えば、関数化処理の過程では、誤差の評価を行いながら適切な近似関数を選定することになるが、セグメント長が十分短い区間に対応する画素列に対しては自由曲線を用いた関数化処理が行われる場合が多い。このような場合には、隣接するセグメントの近似関数と比べて曲率が異なる場合にはこの自由曲線の部分はノイズであることが多い。このため、このような現象が発生した場合には、その発生状況をディスプレイ装置220の画面上に表示し、ノイズに相当する画素の削除の可否を操作者に問い合わせるようにしてもよい。
【0073】
また、上述した実施形態では、検出された直線と円弧とが重複している場合には、円弧を優先させて関数化処理が行われるため、図2に示すステップ106、107における円弧検出を先に行うとともに、円弧として検出された部分を除いた区間を対象にステップ104、105における直線検出を行うようにしてもよい。
【図面の簡単な説明】
【0074】
【図1】一実施形態の画像処理装置の構成を示す図である。
【図2】本実施形態の画像処理装置の全体の動作手順を示す流れ図である。
【図3】直線検出部による直線部分の検出動作の詳細を示す流れ図である。
【図4】直線検出部による直線部分の検出動作の詳細を示す流れ図である。
【図5】直線検出部による直線部分の検出動作の詳細を示す流れ図である。
【図6】直線部分の検出の具体例を示す図である。
【図7】直線部分の検出の具体例を示す図である。
【図8】円弧検出部による円弧部分の検出動作の詳細を示す流れ図である。
【図9】円弧検出部による円弧部分の検出動作の詳細を示す流れ図である。
【図10】円弧検出部による円弧部分の検出動作の詳細を示す流れ図である。
【図11】具体的な図形に対して直線検出と円弧検出を行った実験結果を示す図である。
【図12】具体的な図形に対して直線検出と円弧検出を行った実験結果を示す図である。
【図13】具体的な図形に対して直線検出と円弧検出を行った実験結果を示す図である。
【図14】具体的な図形に対して直線検出と円弧検出を行った実験結果を示す図である。
【符号の説明】
【0075】
100 画像処理演算部
110 画像格納部
120 画素列追跡部
130 接合点抽出部
140 セグメント分割部
150 直線検出部
160 円弧検出部
170 関数化処理部
180 出力画像生成部
200 スキャナ
210 キーボード
212 マウス
220 ディスプレイ装置
230 プリンタ
図面
【図1】
0
【図2】
1
【図3】
2
【図4】
3
【図5】
4
【図6】
5
【図7】
6
【図8】
7
【図9】
8
【図10】
9
【図11】
10
【図12】
11
【図13】
12
【図14】
13