(57)【特許請求の範囲】
【請求項１】
濃淡画像である原画像を２値化する方法であって、
前記原画像を第１のしきい値で２値化して得られる画像の境界部分と、前記原画像を微分した微分画像を第２のしきい値で２値化して得られる画像について画像面を上下及び左右の４方向に走査したときにそれぞれの方向で最初に得られるエッジの和集合との一致度が高くなるように、前記第１及び第２のしきい値をそれぞれ決定し、決定した第１のしきい値で前記原画像を２値化する際に、前記一致度を、
前記原画像を第１のしきい値ｓで２値化したときに濃度１となる画素の集合をＩ（ｓ）とし、
前記微分画像を第２のしきい値ｔで２値化したときに濃度１となる画素の集合をＪ（ｔ）とし、
注目画素の近傍画素の濃度が前記第１のしきい値ｓ以上となる画素の集合をＩｍｉｎ（ｓ）とし、
前記微分画像において、注目画素に向けて前記４方向に走査したときの各方向における最大濃度と前記注目画素の濃度との中で最小濃度が前記第２のしきい値ｔ以上の画素の集合をＪｍｉｎ（ｔ）とし、
前記Ｉ（ｓ）と前記Ｊ（ｔ）の積集合の要素の数であるＮ〔Ｉ（ｓ）∩Ｊ（ｔ）〕と、
前記Ｉｍｉｎ（ｓ）と前記Ｊ（ｔ）との積集合の要素の数であるＮ〔Ｉｍｉｎ（ｓ）∩Ｊ（ｔ）〕と、
前記Ｉ（ｓ）と前記Ｊｍｉｎ（ｔ）との積集合の要素の数であるＮ〔Ｉ（ｓ）∩Ｊｍｉｎ（ｔ）〕と、
前記Ｉｍｉｎ（ｓ）と前記Ｊｍｉｎ（ｔ）との積集合の要素の数であるＮ〔Ｉｍｉｎ（ｓ）∩Ｊｍｉｎ（ｔ）〕と、によって決定する、
ことを特徴とする画像の２値化方法。
【請求項２】
濃淡画像である原画像を第１のしきい値で２値化して得られる画像の境界部分と、前記原画像を微分した微分画像を第２のしきい値で２値化して得られる画像について画像面を上下及び左右の４方向に走査したときにそれぞれの方向で最初に得られるエッジの和集合との一致度が高くなるように、前記第１のしきい値を決定する際に、前記一致度を、
前記原画像を第１のしきい値ｓで２値化したときに濃度１となる画素の集合をＩ（ｓ）とし、
前記微分画像を第２のしきい値ｔで２値化したときに濃度１となる画素の集合をＪ（ｔ）とし、
注目画素の近傍画素の濃度が前記第１のしきい値ｓ以上となる画素の集合をＩｍｉｎ（ｓ）とし、
前記微分画像において、注目画素に向けて前記４方向に走査したときの各方向における最大濃度と前記注目画素の濃度との中で最小濃度が前記第２のしきい値ｔ以上の画素の集合をＪｍｉｎ（ｔ）とし、
前記Ｉ（ｓ）と前記Ｊ（ｔ）の積集合の要素の数であるＮ〔Ｉ（ｓ）∩Ｊ（ｔ）〕と、
前記Ｉｍｉｎ（ｓ）と前記Ｊ（ｔ）との積集合の要素の数であるＮ〔Ｉｍｉｎ（ｓ）∩Ｊ（ｔ）〕と、
前記Ｉ（ｓ）と前記Ｊｍｉｎ（ｔ）との積集合の要素の数であるＮ〔Ｉ（ｓ）∩Ｊｍｉｎ（ｔ）〕と、
前記Ｉｍｉｎ（ｓ）と前記Ｊｍｉｎ（ｔ）との積集合の要素の数であるＮ〔Ｉｍｉｎ（ｓ）∩Ｊｍｉｎ（ｔ）〕と、によって決定する、
ことを特徴とする画像の２値化のためのしきい値の決定方法。
【請求項３】
入力された濃淡画像である原画像を格納する原画像格納手段と、
前記原画像を微分して微分画像を得る微分手段と、
前記原画像を第１のしきい値で２値化して得られる画像の境界部分と、前記微分画像を第２のしきい値で２値化して得られる画像について画像面を上下及び左右の４方向に走査したときにそれぞれの方向で最初に得られるエッジの和集合との一致度が高くなるように、前記第１及び第２のしきい値をそれぞれ決定するしきい値決定手段と、
決定された前記第１のしきい値によって前記原画像を２値化する２値化手段と、を有し、
前記しきい値決定手段は、前記一致度を、
前記原画像を第１のしきい値ｓで２値化したときに濃度１となる画素の集合をＩ（ｓ）とし、
前記微分画像を第２のしきい値ｔで２値化したときに濃度１となる画素の集合をＪ（ｔ）とし、
注目画素の近傍画素の濃度が前記第１のしきい値ｓ以上となる画素の集合をＩｍｉｎ（ｓ）とし、
前記微分画像において、注目画素に向けて前記４方向に走査したときの各方向における最大濃度と前記注目画素の濃度との中で最小濃度が前記第２のしきい値ｔ以上の画素の集合をＪｍｉｎ（ｔ）とし、
前記Ｉ（ｓ）と前記Ｊ（ｔ）の積集合の要素の数であるＮ〔Ｉ（ｓ）∩Ｊ（ｔ）〕と、
前記Ｉｍｉｎ（ｓ）と前記Ｊ（ｔ）との積集合の要素の数であるＮ〔Ｉｍｉｎ（ｓ）∩Ｊ（ｔ）〕と、
前記Ｉ（ｓ）と前記Ｊｍｉｎ（ｔ）との積集合の要素の数であるＮ〔Ｉ（ｓ）∩Ｊｍｉｎ（ｔ）〕と、
前記Ｉｍｉｎ（ｓ）と前記Ｊｍｉｎ（ｔ）との積集合の要素の数であるＮ〔Ｉｍｉｎ（ｓ）∩Ｊｍｉｎ（ｔ）〕と、によって決定する、
ことを特徴とする画像の２値化装置。
【請求項４】
入力された濃淡画像である原画像を格納する原画像格納手段と、
入力された微分画像を格納する微分画像格納手段と、
前記原画像を第１のしきい値で２値化して得られる画像の境界部分と、前記微分画像を第２のしきい値で２値化して得られる画像について画像面を上下及び左右の４方向に走査したときにそれぞれの方向で最初に得られるエッジの和集合との一致度が高くなるように、前記第１及び第２のしきい値をそれぞれ決定するしきい値決定手段と、
決定された前記第１のしきい値によって前記原画像を２値化する２値化手段と、を有し、
前記しきい値決定手段は、前記一致度を、
前記原画像を第１のしきい値ｓで２値化したときに濃度１となる画素の集合をＩ（ｓ）とし、
前記微分画像を第２のしきい値ｔで２値化したときに濃度１となる画素の集合をＪ（ｔ）とし、
注目画素の近傍画素の濃度が前記第１のしきい値ｓ以上となる画素の集合をＩｍｉｎ（ｓ）とし、
前記微分画像において、注目画素に向けて前記４方向に走査したときの各方向における最大濃度と前記注目画素の濃度との中で最小濃度が前記第２のしきい値ｔ以上の画素の集合をＪｍｉｎ（ｔ）とし、
前記Ｉ（ｓ）と前記Ｊ（ｔ）の積集合の要素の数であるＮ〔Ｉ（ｓ）∩Ｊ（ｔ）〕と、
前記Ｉｍｉｎ（ｓ）と前記Ｊ（ｔ）との積集合の要素の数であるＮ〔Ｉｍｉｎ（ｓ）∩Ｊ（ｔ）〕と、
前記Ｉ（ｓ）と前記Ｊｍｉｎ（ｔ）との積集合の要素の数であるＮ〔Ｉ（ｓ）∩Ｊｍｉｎ（ｔ）〕と、
前記Ｉｍｉｎ（ｓ）と前記Ｊｍｉｎ（ｔ）との積集合の要素の数であるＮ〔Ｉｍｉｎ（ｓ）∩Ｊｍｉｎ（ｔ）〕と、によって決定する、
ことを特徴とする画像の２値化装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、画像の２値化方法及び装置に関し、例えば与えられた画像の中に映っている対象物の輪郭を抽出してその対象物を認識するために利用される。
【０００２】
物体を撮影した画像を２値化してその物体の輪郭又は形状を認識する技術は、組み立て工程における自動化のために不可欠な技術である。また、コンピュータによる画像合成又は画像変換などを行うに当たって、原画像から対象物の輪郭を抽出する際に、例えば人の顔の画像から顔の輪郭又は目や鼻の位置を抽出する際に、画像の２値化が行われる。
【０００３】
画像の２値化を行うに当たりそのしきい値が不適切であると、抽出される輪郭は実際の対象物とは全く異なったものになることがあるので、しきい値を適切に設定した上で２値化を行う必要がある。
【０００４】
【従来の技術】
従来より、画像の２値化方法として次の３つの方法がある。
▲１▼  固定しきい値法
この方法は、実験などによって決定した固定値をしきい値とする方法であり、簡便ではあるが対象となる画像の変化に弱いという欠点がある。
▲２▼  判別分析法
この方法は、対象となる画像について、各濃度値毎にその濃度値を持つ画素の個数を表した濃度ヒストグラム作成してそれを２つのクラスに分割し、分割の境界をしきい値とする。その際に、クラス間分散が最大となるようにしきい値を定める。しかしこの方法は、画素の位置情報を利用していないので、物体の抽出には不向きである。
▲３▼  エッジと境界が一致するようにしきい値を決定する方法
この方法は、原画像を第１のしきい値で２値化して得られる画像の境界部分と、原画像を微分した画像を第２のしきい値で２値化して得られる画像（エッジ）との一致度が高くなるように、２つのしきい値をそれぞれ決定し、そのうちの第１のしきい値を用いて２値化を行う方法である（例えば、鳥生，岩瀬，後藤，「最小値フィルタを利用した２値化のしきい値選択法」，信学論，Ｊ７２−Ｄ−ＩＩ，ｐｐ１８００−１８０６，１９８９、又は特開平１−１８４５８３号）。
【０００５】
【発明が解決しようとする課題】
しかし、上述した３番目の方法（以下「従来方法」という）では、物体の内部にエッジが存在する場合には、そのエッジの影響を受けてしまうために物体の輪郭を旨く抽出することができないという欠点がある。これについて、具体例によって説明する。
【０００６】
図５に示す原画像ＦＲ１を第１のしきい値Ｖｓで２値化すると、しきい値Ｖｓの値の大小に応じて、例えば図６（Ａ）又は図６（Ｃ）に示す２つの２値化画像ＦＴ１，２が得られる。つまり、物体画像のどの部分の濃度値よりも低いしきい値Ｖｓ１を用いた場合には２値化画像ＦＴ１が得られ、物体画像の周縁部と内方の歯形状部との中間の濃度値のしきい値Ｖｓ２を用いた場合には２値化画像ＦＴ２が得られる。
【０００７】
これらの２値化画像ＦＴ１，２から境界部分を抽出すると、それぞれ図６（Ｂ）又は図６（Ｄ）に示す境界画像ＦＥ１，２が得られる。
一方、原画像ＦＲ１を微分すると、図７（Ａ）に示す微分画像ＦＤ１が得られる。この微分画像ＦＤ１において、原画像ＦＲ１がシャープな画像である場合にはエッジ部分の濃度値が高くなっており、したがって、微分画像ＦＤ１を第２のしきい値Ｖｔ１，２で２値化した場合に、いずれの場合においても、図７（Ｂ）に示す微分２値化画像（エッジ画像）ＦＦ１が得られる。
【０００８】
従来においては、２値化画像ＦＴ１，２と微分２値化画像ＦＦ１とが比較され、その一致度の高い方のしきい値Ｖｓ，Ｖｔが選定される。そうすると、２値化画像ＦＴ２の方が２値化画像ＦＴ１よりも多くの有効画素（濃度値が１である画素）を含んでいるため、しきい値Ｖｓ２が選定され、その結果、２値化画像ＦＴ２が出力される。しかし、２値化画像ＦＴ２は物体の外形又は輪郭を表すものではない。
【０００９】
上述した原画像ＦＲ１のような特徴を示す物体は、例えばプラスチックの成形品、鋳物製品、内部形状の複雑な製品、多くの模様が描かれた製品などにしばしば見られる。したがって、従来方法によるときは、これらの物体の外形又は輪郭を正しく認識することができないので、例えばロボットでこれらの物体を把持するための対象物認識のための方法として適用することができない。
【００１０】
本発明は、上述の問題に鑑みてなされたもので、対象物の内部にエッジが含まれている場合であっても、対象物の外形又は輪郭を正しく抽出することのできる画像の２値化方法及び装置を提供することを目的とする。
【００１１】
【課題を解決するための手段】
図１は請求項１の発明の原理を模式的に示す図である。
図１において、原画像ＦＲを第１のしきい値ｓによって２値化した２値化画像ＦＴから境界を抽出して境界画像ＦＥを得る。また、原画像ＦＲを微分した微分画像ＦＤを第２のしきい値ｔによって２値化して微分２値化画像ＦＦを得て、その微分２値化画像ＦＦの外側エッジを抽出して外側エッジ画像ＦＧを得る。境界画像ＦＥと、２値化画像ＦＦを上下及び左右の４方向に走査したときにそれぞれの方向で最初に得られるエッジの和集合からなる外側エッジ画像ＦＧと、が比較され、その一致度が高くなるようなしきい値の組（ｓ，ｔ）が決定され、決定されたしきい値のうちの原画像ＦＲの２値化に用いられたしきい値ｓによって原画像ＦＲの２値化が行われる。
前記一致度は、前記原画像ＦＲを第１のしきい値ｓで２値化したときに濃度１となる画素の集合をＩ（ｓ）とし、前記微分画像ＦＤを第２のしきい値ｔで２値化したときに濃度１となる画素の集合をＪ（ｔ）とし、注目画素の近傍画素の濃度が前記第１のしきい値ｓ以上となる画素の集合をＩｍｉｎ（ｓ）とし、前記微分画像ＦＤにおいて、注目画素に向けて前記４方向に走査したときの各方向における最大濃度と前記注目画素の濃度との中で最小濃度が前記第２のしきい値ｔ以上の画素の集合をＪｍｉｎ（ｔ）とし、前記Ｉ（ｓ）と前記Ｊ（ｔ）の積集合の要素の数であるＮ〔Ｉ（ｓ）∩Ｊ（ｔ）〕と、前記Ｉｍｉｎ（ｓ）と前記Ｊ（ｔ）との積集合の要素の数であるＮ〔Ｉｍｉｎ（ｓ）∩Ｊ（ｔ）〕と、前記Ｉ（ｓ）と前記Ｊｍｉｎ（ｔ）との積集合の要素の数であるＮ〔Ｉ（ｓ）∩Ｊｍｉｎ（ｔ）〕と、前記Ｉｍｉｎ（ｓ）と前記Ｊｍｉｎ（ｔ）との積集合の要素の数であるＮ〔Ｉｍｉｎ（ｓ）∩Ｊｍｉｎ（ｔ）〕と、によって決定される。
【００１２】
しきい値ｓの決定に当たっては、種々のしきいについて原画像ＦＲに対する２値化、境界の抽出、微分などの処理を実際に行って、最適のしきい値を決定してもよい。また、そのような処理を実際には行うことなく、演算によって最適のしきい値ｓを決定してもよい。なお、これら２つのしきい値ｓ，ｔは、互いに異なる値の場合もあるし、互いに同じ値の場合もある。
【００１３】
請求項２の発明に係る方法は、濃淡画像である原画像を第１のしきい値で２値化して得られる画像の境界部分と、前記原画像を微分した画像を第２のしきい値で２値化して得られる画像の外側エッジ部分との一致度が高くなるように、前記第１及び第２のしきい値をそれぞれ決定し、そのうちの第１のしきい値を原画像の２値化のためのしきい値として決定する方法である。
本方法においても、前記一致度は、請求項１の発明に係る方法と同様にして決定される。
【００１４】
請求項３の発明に係る装置は、入力された濃淡画像である原画像を格納する原画像格納手段と、前記原画像を微分して微分画像を得る微分手段と、前記原画像を第１のしきい値で２値化して得られる画像の境界部分と、前記微分画像を第２のしきい値で２値化して得られる画像の外側エッジ部分との一致度が高くなるように、第１及び第２のしきい値をそれぞれ決定するしきい値決定手段と、決定された前記第１のしきい値によって前記原画像を２値化する２値化手段と、を有してなる。
前記しきい値決定手段は、前記一致度を、前記原画像を第１のしきい値ｓで２値化したときに濃度１となる画素の集合をＩ（ｓ）とし、前記微分画像を第２のしきい値ｔで２値化したときに濃度１となる画素の集合をＪ（ｔ）とし、注目画素の近傍画素の濃度が前記第１のしきい値ｓ以上となる画素の集合をＩｍｉｎ（ｓ）とし、前記微分画像において、注目画素に向けて前記４方向に走査したときの各方向における最大濃度と前記注目画素の濃度との中で最小濃度が前記第２のしきい値ｔ以上の画素の集合をＪｍｉｎ（ｔ）とし、前記Ｉ（ｓ）と前記Ｊ（ｔ）の積集合の要素の数であるＮ〔Ｉ（ｓ）∩Ｊ（ｔ）〕と、前記Ｉｍｉｎ（ｓ）と前記Ｊ（ｔ）との積集合の要素の数であるＮ〔Ｉｍｉｎ（ｓ）∩Ｊ（ｔ）〕と、前記Ｉ（ｓ）と前記Ｊｍｉｎ（ｔ）との積集合の要素の数であるＮ〔Ｉ（ｓ）∩Ｊｍｉｎ（ｔ）〕と、前記Ｉｍｉｎ（ｓ）と前記Ｊｍｉｎ（ｔ）との積集合の要素の数であるＮ〔Ｉｍｉｎ（ｓ）∩Ｊｍｉｎ（ｔ）〕と、によって決定する。
【００１５】
請求項４の発明に係る装置は、前記微分手段に代えて、入力された微分画像を格納する微分画像格納手段を有する。
なお、本発明における濃淡画像とは、濃度に階調性を実質的に有している画像であり、例えばフルカラー画像も含まれる。
【００１６】
【発明の実施の形態】
図２は本発明に係る第１の態様の画像２値化装置１を示すブロック図、図４は画像２値化装置１における処理内容を示すフローチャートである。
【００１７】
図２において、画像２値化装置１は、原画像格納部１１、２値化処理部１２、画像出力部１３、微分処理部１４、及びしきい値決定部１５からなっている。原画像格納部１１は、入力される原画像ＦＲのデータ（原画像データ）ＤＲを格納する。２値化処理部１２は、しきい値決定部１５から与えられるしきい値（第１のしきい値）Ｖｓを用いて原画像ＦＲの２値化を行う。画像出力部１３は、最終的に決定されたしきい値Ｖｓによって２値化された画像データＤＧを外部に出力する。
【００１８】
微分処理部１４は、原画像ＦＲのエッジを抽出するために、原画像ＦＲに対して微分処理を行い、微分画像データＤＤを出力する。しきい値決定部１５は、原画像ＦＲと、原画像ＦＲを微分して得られた微分画像ＦＤとに基づいて、最適のしきい値Ｖｓを決定する。しきい値Ｖｓの決定に当たっては、原画像ＦＲをしきい値Ｖｓで２値化して得られる画像の境界部分と、微分画像ＦＤを別のしきい値Ｖｔで２値化して得られる画像の外側エッジ部分との一致度が最大となるような、そのようなしきい値Ｖｓ，Ｖｔの組を決定し、そのうちの１つのしきい値Ｖｓを原画像ＦＲの２値化のためのしきい値として決定する。これら２つのしきい値Ｖｓ，Ｖｔは、互いに異なる値の場合もあるし、互いに同じ値の場合もある。
【００１９】
微分処理部１４においては、種々のしきい値Ｖｓ，Ｖｔについて原画像ＦＲに対する２値化、境界の抽出、微分などの処理を実際に行って、最適のしきい値Ｖｓを決定してもよく、また、そのような処理を実際には行うことなく、例えば後述するような手法で計算によって最適のしきい値Ｖｓを決定してもよい。
【００２０】
図４において、まず、原画像データＤＲを読み込んで原画像格納部１１に格納する（＃１）。格納された原画像データＤＲに対し、微分処理部１４で微分処理を行う（＃２）。しきい値決定部１５において、一致度を最大にするしきい値Ｖｓ，Ｖｔを演算により求める（＃３）。２値化処理部１２において、求めたしきい値Ｖｓを用いて原画像データＤＲに対して２値化処理を行い（＃４）、２値化された画像データＤＧを出力する（＃５）。
【００２１】
次に、画像２値化装置１の処理動作を、図５に示す原画像ＦＲを用いた場合について具体的に説明する。原画像ＦＲに対する２値化、境界の抽出、微分などについては従来の技術の項において説明したとおりであるので、ここでの説明は省略する。画像２値化装置１においては、さらに微分２値化画像ＦＦ１の外側エッジを抽出し、外側エッジ部分の画像（外側エッジ画像）ＦＧ１と境界画像ＦＥ１，２とを比較してその一致度が最大となるようなしきい値Ｖｓ，Ｖｔを決定する。
【００２２】
外側エッジ画像ＦＧ１は、図７（Ｃ）に示すように、物体の輪郭を示すものであり、これと図６（Ｂ）に示す境界画像ＦＥ１又は図６（Ｄ）に示す境界画像ＦＥ２とを比較すると、図６（Ｂ）に示す境界画像ＦＥ１の一致度が高いので、それに対応するしきい値Ｖｓ１が決定される。これによって、画像出力部１３は、図６（Ａ）に示す２値化画像ＦＴ１についての画像データＤＧを出力することとなる。
【００２３】
２値化画像ＦＴ１は、原画像ＦＲにおける対象物の外形及び輪郭を正確に表したものであり、これによって物体認識を正確に行うことができる。したがって、画像２値化装置１は、原画像ＦＲに表れた物体をロボットで把持するための対象物認識のために利用することができる。
【００２４】
図３は本発明に係る第２の態様の画像２値化装置１Ａを示すブロック図である。
画像２値化装置１Ａでは、微分処理部１４に代えて微分画像格納部１４ａが設けられており、外部から原画像ＦＲを微分した微分画像ＦＤについてのデータ（微分画像データ）ＤＤが入力され、それが微分画像格納部１４ａに格納される。微分画像格納部１４ａから読み出された微分画像データＤＤは、画像２値化装置１の場合と同様にしきい値決定部１５に出力される。この画像２値化装置１Ａでは、微分処理部１４が不要であるとともに、外部から与えられた原画像ＦＲと微分画像ＦＤに基づいて最適の２値化処理を行うことができる。
【００２５】
次に、画像２値化装置１における処理について、理論的な側面からさらに詳しく説明する。
与えられた原画像をＩ（ｘ，ｙ）、それを微分して得られる微分画像をＪ（ｘ，ｙ）とする。このとき、本発明の方法は次の評価関数Ｋ（ｓ，ｔ）を最大にするしきい値ｓ及びｔを求め、そのしきい値ｓ及びｔによってＩ（ｘ，ｙ）及びＪ（ｘ，ｙ）を２値化するものである。
【００２６】
評価関数Ｋ（ｓ，ｔ）は、境界画像と外側エッジ画像との一致度を表しており、境界でありかつ外側エッジである画素の個数を、境界又は外側エッジである画素の個数で割ったものである。したがって評価関数Ｋ（ｓ，ｔ）は次の（１）式で示される。
【００２７】
0003614215.tif 000002
但し、Ｎ（Ｘ）は集合Ｘの要素の個数を表し、Ｂｓはしきい値ｓでＩ（ｘ，ｙ）を２値化したときの境界の集合であり、Ｅｔはしきい値ｔでＪ（ｘ，ｙ）を２値化したときの外側エッジの集合である。
【００２８】
２値化とは、画像の各画素に対してその濃度値がしきい値以上ならばその画素の濃度値を１に、そうでないならば０にする処理である。ここでは、２値化された画像についての境界を、濃度値１を持ち且つ近傍に濃度値０の画素が存在する画素の集合であると定義している。したがって、次の（２）式が成り立つ。
【００２９】
0003614215.tif 000003
但し、Ｉｍｉｎ  （ｘ，ｙ）はＩ（ｘ，ｙ）に最小値フィルタを施した濃淡画像である。最小値フィルタとは、注目画素（ｘ，ｙ）に対して、その近傍の画素でのＩの最小値をＩｍｉｎ  （ｘ，ｙ）としたものである。
【００３０】
ここで、外側エッジを、微分画像Ｊを２値化してそれを指定された方向から見たときに一番最初に濃度値１になる画素のことであると定義する。例えば、図８に示す画像ＦＦ２の外側エッジは、左側から見たときに、１段目では３番目の画素、２段目では４番目の画素となる。複数の方向が指定された場合には、それぞれの方向で定まる外側エッジの和集合を取る。例えば、図８に示す画像ＦＦ２を左側と右側の両方から見たときの外側エッジは、１段目では３番目と４番目の画素、２段目では４番目と５番目の画素となる。したがって、次の（３）式が成り立つ。
【００３１】
0003614215.tif 000004
である。なお、上の式は、上下左右４つの方向から見た場合の外側エッジを表している。例えば、外側エッジとして左右のみから見たものを考える場合には、
0003614215.tif 000005
とする。上述の（３）式は次のように証明される。
【００３２】
すなわち、Ｅｔはしきい値ｔでＪ（ｘ，ｙ）を２値化したときの外側エッジの集合である。したがって、（ｘ，ｙ）∈Ｅｔは、Ｊ（ｘ，ｙ）≧ｔであり且つ次の条件のどれかが成り立つことと等価になる。
▲１▼  左から見た外側エッジ  ｘ’＜ｘを満たすすべてのｘ’に対してＪ（ｘ’，ｙ）＜ｔ
▲２▼  右から見た外側エッジ  ｘ’＞ｘを満たすすべてのｘ’に対してＪ（ｘ’，ｙ）＜ｔ
▲３▼  上から見た外側エッジ  ｙ’＜ｙを満たすすべてのｙ’に対してＪ（ｘ，ｙ’）＜ｔ
▲４▼  下から見た外側エッジ  ｙ’＞ｙを満たすすべてのｙ’に対してＪ（ｘ，ｙ’）＜ｔ
ここで、ｘ’＜ｘを満たすすべてのｘ’に対してＪ（ｘ’，ｙ）＜ｔが成り立つことと、Ｊｘ−（ｘ，ｙ）＝ｍａｘ  ｘ’＜ｘＪ（ｘ’，ｙ）＜ｔが成り立つこととは等価であるので、（３）式は自明である。なお、画像面の左上端を座標の原点とし、右方及び下方に向かって座標値が増加するものとした。
【００３３】
次に、効率的に評価関数Ｋ（ｓ，ｔ）を計算する手法を説明する。この計算手法を用いることによって高速演算が可能となる。その準備のためにいくつかの記号を定義する。
【００３４】
0003614215.tif 000006
例えば、Ｉ（ｓ）は、Ｉをしきい値ｓで２値化したときに濃度値１となる画素の集合である。総ての（ｘ，ｙ）に対して、Ｉ（ｘ，ｙ）＞Ｉｍｉｎ  （ｘ，ｙ）、Ｊ（ｘ，ｙ）＞Ｊｍｉｎ  （ｘ，ｙ）であるので、次の（７）式、
Ｉ（ｓ）⊃Ｉｍｉｎ  （ｓ）
Ｊ（ｔ）⊃Ｊｍｉｎ  （ｔ）    ……（７）
が成り立つことが分かる。したがって、Ｉ（ｓ）∩Ｉｍｉｎ  （ｓ）＝Ｉｍｉｎ  （ｓ）などが成立する。また、次の（８）式、
Ｂｓ＝Ｉ（ｓ）∩¬Ｉｍｉｎ  （ｓ）
Ｅｔ＝Ｊ（ｔ）∩¬Ｊｍｉｎ  （ｔ）    ……（８）
が成り立つ。但し、¬Ｘは集合Ｘの補集合を表す。これらより、Ｎ（Ｂｓ），Ｎ（Ｅｔ），Ｎ（Ｂｓ∩Ｅｔ）は、次の（９）式で表される。
【００３５】
0003614215.tif 000007
上述の（９）式の３番目の式は、集合Ａ，Ｂ，Ｃについての関係式である次の（１０）式、
0003614215.tif 000008
において、Ａ＝Ｉｍｉｎ  （ｓ），Ｂ＝Ｊｍｉｎ  （ｔ），Ｃ＝Ｉ（ｓ）∩Ｊ（ｔ）と置くことで示される。濃淡画像の最小濃度値を０とするとき、Ｎ〔Ｉ（ｓ）〕＝Ｎ〔Ｉ（ｓ）∩Ｊ（０）〕などが成り立つことに注意すると、（１）式及び（９）式より、評価関数Ｋ（ｓ，ｔ）の計算は、結局、４つの２次元累積ヒストグラム、Ｎ〔Ｉ（ｓ）∩Ｊ（ｔ）〕，Ｎ〔Ｉｍｉｎ  （ｓ）∩Ｊ（ｔ）〕，Ｎ〔Ｉ（ｓ）∩Ｊｍｉｎ  （ｔ）〕，Ｎ〔Ｉｍｉｎ  （ｓ）∩Ｊｍｉｎ  （ｔ）〕の計算に帰着することが分かる。
【００３６】
次に、これらの２次元累積ヒストグラムの計算を２次元ヒストグラムを用いて行う方法について述べる。画像Ｘと画像Ｙの２次元ヒストグラムｈｉｓｔ（Ｘ，Ｙ）とは、２次元配列でその（ｉ，ｊ）要素の値ｈｉｓｔ（Ｘ，Ｙ）〔ｉ〕〔ｊ〕が、画像Ｘが濃度値ｉになり画像Ｙが濃度値ｊになる画素の個数を表すものである。２次元ヒストグラムは、２つの画像を同時に１回走査することにより簡単に計算できる。
【００３７】
２次元累積ヒストグラムｃｈｉｓｔ  （Ｘ，Ｙ）とは、２次元配列でその（ｉ，ｊ）要素の値ｃｈｉｓｔ  （Ｘ，Ｙ）〔ｉ〕〔ｊ〕が、画像Ｘが濃度値ｉ以上になり画像Ｙが濃度値ｊ以上になる画素の個数を表すものである。したがって、ｃｈｉｓｔ  （Ｉ，Ｊ）〔ｓ〕〔ｔ〕＝Ｎ〔Ｉ（ｓ）∩Ｊ（ｔ）〕などが成立する。２次元累積ヒストグラムｃｈｉｓｔ  （Ｘ，Ｙ）は、２次元ヒストグラムｈｉｓｔ（Ｘ，Ｙ）を大きい方から順に足し合わせていくことにより計算できる。２次元配列上で上書きして計算する方法の例を次に示す。
▲１▼  すべてのｉに対してｊ＝最大濃度値−１から最小濃度値まで順に以下の計算
を行う。
【００３８】
0003614215.tif 000009
▲２▼  すべてのｊに対してｉ＝最大濃度値−１から最小濃度値まで順に以下の計算
を行う。
【００３９】
0003614215.tif 000010
▲３▼  求める２次元累積ヒストグラムｃｈｉｓｔ  は計算後のｈｉｓｔに格納されている。
【００４０】
評価関数Ｋ（ｓ，ｔ）の最大値を探すには、濃淡画像の最小濃度値から最大濃度値までの数ｍ（多くの場合はｍ＝２５６）の２乗の大きさの４つの２次元累積ヒストグラムを全数探索し、総ての（ｓ，ｔ）の組み合わせにおけるＫ（ｓ，ｔ）の値を比較すればよい。これに必要な演算量は，Ｏ（ｍ２  ）である。２次元累積ヒストグラムは、画素の総数ｎ（例えばｎ＝６４０×４８０）に比例した手間で作成できる２次元ヒストグラムを２回走査することで得られるので、Ｏ（ｎ＋ｍ２  ）の演算量で作成できる。したがって、Ｋ（ｓ，ｔ）の最大値は、Ｏ（ｎ＋ｍ２  ）の演算量で計算できる。これは実際に計算可能な大きさである。例えば、総てのしきい値について２値化などを行って適切なしきい値を求める方法では数時間を要するが、ここに述べた効率的な評価関数を計算する手法によると数分で行える。
【００４１】
次に、微分画像ＦＤを作成する方法の例について説明する。
図１０に示す２つのウインドウＷＤ１，２を用いて空間フィルタ処理を行い、それらの絶対値の和又は２乗平均を微分画像ＦＤとする。その処理手順は次のとおりである。
▲１▼  初期化
注目画素を画像面の左上端に置く。
▲２▼  ウインドウＷＤ１，２との畳み込み演算
注目画素がウインドウＷＤ１，２の中央になるように画像上にウインドウＷＤ１，２を置き、ウインドウＷＤ１，２下の各画素の濃度値とウインドウＷＤ１，２の各要素の値を掛け、それらをウインドウＷＤ１，２の全要素にわたって足し合わせる。
▲３▼  微分画像への書き込み
２つのウインドウＷＤ１，２に対する畳み込み演算の結果の絶対値の和を微分画像Ｊの対応する画素に書き込む。
▲４▼  注目画素の移動
注目画素を１つ右に移動する。右端にきたときには１段下の左端に移動する。下へ行けないときには終了する。
▲５▼  繰り返し
再びウインドウＷＤ１，２との畳み込み演算を行う。
【００４２】
次に、Ｉｍｉｎ  （ｘ，ｙ）の作成方法の例について説明する。
▲１▼  初期化
注目画素を画像面の左上端に置く。
▲２▼  注目画素の近傍での最小値計算
注目画素の近傍（例えば、上下左右斜めの８近傍、上下左右の４近傍など）
でのＩの最小値をその画素でのＩｍｉｎ  の濃度値とする。
▲３▼  注目画素の移動
注目画素を１つ右に移動する。右端にきたときには１段下の左端に移動する。下へ行けないときには終了する。
▲４▼  繰り返し
再び注目画素の近傍での最小値計算を行う。
【００４３】
次に、Ｊｘ−（ｘ，ｙ），Ｊｘ＋（ｘ，ｙ），Ｊｙ−（ｘ，ｙ），Ｊｙ＋（ｘ，ｙ）の作成方法の例について説明する。なお、これら４つは互いに走査方向が異なるのみであるので、そのうちのＪｘ−（ｘ，ｙ）についてのみ説明する。
▲１▼  初期化
注目画素を画像面の左上端に置く。一時的な変数ｍａｘ  を用意する。
▲２▼  行の先頭内での処理
各行の先頭でｍａｘ  ＝０を代入する
▲３▼  行内での最大値計算
ｍａｘ  の値をその画素でのＪｘ−の濃度値とする。また、更新前のＪｘ−の濃  度値をｍａｘ  と比較して大きい方の値をｍａｘ  に入れ直す。
▲４▼  注目画素の移動
注目画素を１つ右に移動する。右端にきたときには１段下の左端に移動する。下へ行けないときには終了する。
▲５▼  繰り返し
再び行の先頭での処理又は行内での最大値計算を行う。
【００４４】
例えば、図９に示す画像ＦＦ３を左側から走査した場合には、変数ｍａｘ  の値は同図に示すようになる。図９でよく分かるように、上述の処理によると、変数ｍａｘ  は画像ＦＦ３の画素値よりも１画素遅れで積算されていく。この場合に、例えば画素値が２以上で且つＪｍｉｎ  が２未満の画素の位置は左から３番目である。
【００４５】
次に、Ｊｍｉｎ  （ｘ，ｙ）の作成方法の例について説明する。
▲１▼  初期化
注目画素を画像面の左上端に置く。
▲２▼  注目画素での最小値計算
注目画素におけるＪｘ−などの濃度値の中で最小のものをその画素でのＪｍｉｎ  の濃度値とする。
▲３▼  注目画素の移動
注目画素を１つ右に移動する。右端にきたときには１段下の左端に移動する。下へ行けないときには終了する。
▲５▼  繰り返し
再び注目画素での最小値計算を行う。
【００４６】
次に、２次元ヒストグラムｈｉｓｔ（Ｘ，Ｙ）の作成方法の例について説明する。▲１▼  初期化
注目画素を画像面の左上端に置く。ｉ，ｊの総ての組み合わせに対してｈｉｓｔ（Ｘ，Ｙ）〔ｉ〕〔ｊ〕＝０とする。
▲２▼  注目画素でのヒストグラム加算
注目画素における画像Ｘの濃度値をｉ、画像Ｙの濃度値をｊとして、ｈｉｓｔ（Ｘ，Ｙ）〔ｉ〕〔ｊ〕の値を１つ増す。
▲３▼  注目画素の移動
注目画素を１つ右に移動する。右端にきたときには１段下の左端に移動する。下へ行けないときには終了する。
▲４▼  繰り返し
再び注目画素でのヒストグラム加算を行う。
【００４７】
次に、Ｋ（ｓ，ｔ）の最大値計算方法の例について説明する。
▲１▼  初期化
ｓ，ｔ＝０とする。一時的な変数ｍａｘｓ，ｍａｘｔ，ｍａｘＫを用意する。ｍａｘＫ＝０としておく。
▲２▼  Ｋ（ｓ，ｔ）の計算
今のｓ，ｔに対して、Ｋ（ｓ，ｔ）の値を計算する。
▲３▼  最大値の置き換え
もし、Ｋ（ｓ，ｔ）がｍａｘＫよりも大きい場合には、その値でｍａｘＫを置き換えるとともに、ｍａｘｓ，ｍａｘｔにｓ，ｔを代入する。
▲４▼  ｓ，ｔの変更
ｔを１増やす。ｔがそれ以上増やせないときには、ｔ＝０としてｓを１増やす。ｓもそれ以上増やせないときには終了する。
▲５▼  繰り返し
再びＫ（ｓ，ｔ）の計算を行う。
【００４８】
上述したように、図５の原画像ＦＲを２値化する場合には、図７（Ｂ）に示す微分２値化画像ＦＦ１を上下左右４つの方向から見て得られる外側エッジ画像ＦＧ１を用いるが、例えば、図１１（Ａ）に示すような微分２値化画像ＦＦ４である場合には、上と左右の３つの方向から見て外側エッジ画像ＦＧを得ることとなる。また、図１１（Ｂ）に示すように、微分２値化画像ＦＦ５が入り組んだ形状のものである場合には、その入り組んだ内部にある位置を始点として走査を行う。
【００４９】
【発明の効果】
請求項１乃至請求項６の発明によると、対象物の内部にエッジが含まれている場合であっても、対象物の外形又は輪郭を正しく抽出することができる。
【００５０】
請求項２の発明によると、外側エッジ部分の抽出が容易である。
請求項６の発明によると、微分手段が不要であるとともに、外部から与えられる原画像と微分画像に基づいて最適の２値化処理を行うことができる。
【図面の簡単な説明】
【図１】本発明の原理を模式的に示す図である。
【図２】本発明に係る第１の態様の画像２値化装置を示すブロック図である。
【図３】本発明に係る第２の態様の画像２値化装置を示すブロック図である。
【図４】画像２値化装置における処理内容を示すフローチャートである。
【図５】原画像の例を示す図である。
【図６】図５に示す原画像から得られる２値化画像及び境界画像の例を示す図である。
【図７】図５に示す原画像から得られる微分画像及び外側エッジ画像の例を示す図である。
【図８】外側エッジの抽出過程を説明するための画像の画素値の例を示す図である。
【図９】外側エッジの抽出過程を説明するための図である。
【図１０】微分演算ウインドウの例を示す図である。
【図１１】外側エッジ画像の例を示す図である。
【符号の説明】
１，１Ａ  画像２値化装置（２値化装置）
１１  原画像格納部（原画像格納手段）
１２  ２値化処理部（２値化手段）
１４  微分処理部（微分手段）
１４ａ  微分画像格納部（微分画像格納手段）
１５  しきい値決定部（しきい値決定手段）
ＦＲ  原画像
【図１】
0003614215.tif 000011
【図２】
0003614215.tif 000012
【図３】
0003614215.tif 000013
【図４】
0003614215.tif 000014
【図５】
0003614215.tif 000015
【図６】
0003614215.tif 000016
【図７】
0003614215.tif 000017
【図８】
0003614215.tif 000018
【図９】
0003614215.tif 000019
【図１０】
0003614215.tif 000020
【図１１】
0003614215.tif 000021