JP3026751B2

JP3026751B2 - 画像切出方法及び装置

Info

Publication number: JP3026751B2
Application number: JP8017249A
Authority: JP
Inventors: 豪徳山
Original assignee: International Business Machines Corp
Current assignee: International Business Machines Corp
Priority date: 1995-06-15
Filing date: 1996-02-02
Publication date: 2000-03-27
Anticipated expiration: 2016-02-02
Also published as: JPH0962846A; US5729628A

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、中間調を含む濃淡によ
って表された画像から、特徴的な画像の領域を切り出す
方法及び装置に関し、より詳しくは新規な目的関数のパ
ラメータを変化させることにより、カメラのピント合わ
せに類似の操作を行い、予め決められた大きさの鮮明な
画像を切り出す方法に関する。

【０００２】

【従来の技術】新聞等の写真は、同一又は異なる濃淡レ
ベルを有するピクセルによって表現されている画像であ
る。この画像の中に表された、所望の物体等を検索する
には、まず、画像中の物体等をその画像の他の領域から
分離しなければならない。よって、ｎ個のピクセル（画
素）を有する画像で、各ピクセルに濃淡レベルが与えら
れた時、その画像から与えられた大きさの部分画像を切
り出す問題を考えることになる。この部分画像は、図１
のように、連結しており、バックグラウンドに比して濃
淡レベルが高いものでなければならない。しかし、一般
に連結性のみでこの問題を解こうとすると、対応する最
適化問題はＮＰ（nondeterministic polynomial time）
困難問題（問題のサイズに対して、指数関数的に計算の
手間が必要となってしまうと広く予測されている問題）
となり、全ての場合を直接解くには非常に時間・手間が
かかることになる。

【０００３】そこで、単純に濃いピクセルから集めてく
る方法（例えば、P.P.Sahoo, S.Soltani, and A.K.C.Wo
ng:"A survey of thresholding techniques," Comput.
Vis.,Graph. Image Process.,Vol.41,pp.233-260,198
8）や、近傍にある、近い濃度のピクセルを集めていく
領域法が提案されているが、これらの方法では連結性を
保証しない上に、画面上の染みやノイズに対応するのが
難しいという欠点がある。

【０００４】また、差分を用いて境界曲線を発見する方
法（例えば、L.S.Davis:"A Surveyof edge detection t
echniques," Comput. Graph. Image Process.,Vol.4,p
p.248-270,1975）もあるが、境界曲線をはっきり求めら
れるような、例えば図１のような鮮明な画像でないと対
応できず、図２のような画像では有効とは言えない。ま
た、先に述べた方法との併用を提案しているものもある
が（例えば、P.J.Besland R.C.Jain:"Segmentation thr
ough variable-order surface fitting," IEEE Trans.
Pattern and Machine Intell.,Vol.10,pp.167-192,198
8）、欠点を完全には克服できない。

【０００５】上述の連結性に加えて各列との交わりも連
結であること（垂直凸性）を仮定した画像（図４）を許
容イメージと定義し、統計的な共分散を目的関数に対し
て最適な許容イメージを求めるアルゴリズムを道具にし
て、この一般的な問題を解くことも提案されている（例
えば、T.Asano, D.Z.Chen, N.Katoh, and T.Tokuyama,"
Polynominal-Time Solutions to Image Segmentation"
Preprint,1994）。一般的な連結性を有する画像は、許
容イメージから幾つかの許容イメージを集合論的に引い
たものとして捉えられる。例えば、一般的な連結性を有
する画像（図３）は、許容イメージ（図４）に含まれて
いる。この方法は、許容イメージの計算にＯ（ｎ^2.5）
と手間がかかることと、切り出す画像の大きさを制御で
きないという欠点がある。（Ｏ（ｎ^2.5）は、オーダー
ｎ^2.5の計算手間がかかることを示す。）

【０００６】

【発明が解決しようとする課題】このように全体画像か
ら、所定の大きさの鮮明な部分画像を切り出すのには多
くの計算量を必要とし、この計算量では実用的ではな
い。

【０００７】よって、計算量を減少させつつ、所定の大
きさに近い鮮明な、許容イメージである部分画像を切り
出すことを目的とする。また、許容イメージ自体を高速
に切り出すことも目的とする。

【０００８】

【課題を解決するための手段】上述の目的を達成するた
めに、本発明は、各画素が、中間調を含む濃淡により表
された全体画像から、特徴的な領域である部分画像を切
り出す方法であって、切り出される部分画像の画素数ｋ
を指定する指定ステップと、

【数３】（ｎは画素数、ｇ(i,j)は画素（ｉ，ｊ）の濃淡レベ
ル、｜Ｓ｜は部分画像Ｓの画素数）のＵ_α(Ｓ）を最大
化する部分画像を検出する検出ステップと、Ｕ_α(Ｓ）
を最大化した部分画像の画素数｜Ｓ｜と指定された画素
数ｋを比較する比較ステップと、比較ステップによる結
果が｜Ｓ｜＞ｋの場合、αを増加させ、｜Ｓ｜＜ｋの場
合、αを減少させるステップと、新たなαでもって検出
ステップ以後を実行するステップと、比較ステップによ
る結果が｜Ｓ｜＝ｋの場合には、当該Ｕ_α(Ｓ）を最大
化した部分画像を特徴的な領域として出力するステップ
とを含む画像切出方法である。新規な目的関数である数
３を導入し、パラメータαを増減することにより、イメ
ージの大きさを調節し、所定の大きさの鮮明な部分画像
を切り出すことが、高速に実施できる。

【０００９】先の検出ステップが、全体画像を複数の列
に分割し、分割された列につき動的計画法を適用するよ
うにすることもできる。この場合、切り出されるのは、
許容イメージである。

【００１０】また、ある部分画像の濃淡レベルの総和か
ら画素数にαを乗じた値を減じたものを評価値とし、先
の検出ステップが、全体画像の各列において、ある画素
を含み且つ評価値が最大となる画素の範囲を求める列内
範囲導出ステップと、全体画像の任意の画素（座標
（ｍ，ｔ））の前列にあるもう１つの画素（座標（ｍ−
１，ｌ））を含み且つ当該前列までで最大の評価値を有
する領域と、前記列内範囲導出ステップにより導出され
る、任意の画素及び前記もう１つの画素と同一行であっ
て前記任意の画素と同一列にある画素（座標（ｍ，
ｌ））を含む評価値が最大となる範囲とを加えた加算領
域を求め、各前記任意の画素につき、加算領域の評価値
が最大となる前記もう１つの画素を検出し、当該評価値
と共に記憶する検出記憶ステップと、全体画像で加算領
域の評価値が最大となる前記任意の画素を検出し、検出
記憶ステップで検出された前記もう１つの画素を用い
て、領域Ｓを導き出すステップとを含むようにすること
も考えられる。

【００１１】上述の方法をより一般化すると、以下のと
おりになる。すなわち、各画素が、中間調を含む濃淡に
より表された全体画像から、列方向に凸である部分画像
（許容イメージ）を切り出す方法であって、所定の条件
Ｎを入力するステップと、全体画像の各列において、あ
る画素（ｔ又はｌ）を含み且つ包含される画素（例えば
（ｉ，ｊ））の濃淡レベルｇ(i,j)からＮを減じた値
（ｇ(i,j)−Ｎ）の総和である評価値が最大となる画素
の範囲（ｈｉｇｈ（ｌ），ｌｏｗ（ｔ））を求める列内
範囲導出ステップと、全体画像の任意の画素（ｍ，ｔ）
の前列にあるもう１つの画素（ｍ−１，ｌ）を含み且つ
当該前列までで最大の評価値（Ｕ（ｍ−１，ｌ））を有
する領域と、列内範囲導出ステップの結果を用いること
により導出される、前記任意の画素（ｍ，ｔ）及び前記
もう１つの画素と同一行であって前記任意の画素と同一
列にある画素（ｍ，ｌ）を含む評価値が最大となる範囲
（ｃｏｖｅｒ（ｔ，ｌ））とを加えた加算領域を求め、
各前記任意の画素につき、前記加算領域の評価値が最大
となる前記もう１つの画素（ｍ−１，ｌ）を検出し（ｓ
（ｍ，ｔ））、当該加算領域の評価値（Ｕ（ｍ，ｔ））
と共に記憶する検出記憶ステップと、全体画像で加算領
域の評価値（Ｕ（ｍ，ｔ））が最大となる前記任意の画
素を検出し、検出記憶ステップで検出された前記もう１
つの画素を用いて、領域Ｓを導き出すステップとを含
む、というように記することができる。

【００１２】

【実施例】本発明を図５及び図６を用いて説明する。図
５には本発明に係る装置構成が記載されている。図５に
記載の装置は、１枚がｎピクセルであって、中間調を含
む濃淡により表された画像を、１又は複数記憶している
画像記憶部１、画像記憶部１から画像を読み出し且つ処
理する検出処理部３、検出処理部３からの｜Ｓ｜を表す
信号を受信して、入力された許容イメージである部分画
像の大きさｋを表す信号と比較する比較部５、比較結果
を表す信号Ａ，Ｂ，Ｃを比較部５から受信し、検出処理
部３の制御を行う制御部７と、検出された、所定の大き
さの鮮明な画像を検出処理部３から受信し、後の処理、
例えばその画像を表示等する後処理装置９とで構成され
る。この後処理装置９は、所定の大きさの鮮明な画像を
表示するのみではなく、その画像が許容イメージであれ
ば、一般的な連結性のみを有する画像を検出する処理
や、予め決められた画像との比較検査を行うような装置
であってもよい。

【００１３】では、上記装置の動作を図６を用いて説明
する。処理を開始すると、まず検出する画像の大きさを
示すｋを比較部３に入力する（ステップ２３）。また、
初期化動作として、検出処理部３内のパラメータαを０
に、そしてこのαを調節する変数εをｎにセットする
（ステップ２５）。そして、検出処理部３は画像記憶部
１から処理される画像を１枚取り出す。この検出処理部
３では、次のような目的関数を取り扱う。

【数４】

【００１４】ここで、処理される全体画像の画素数は
ｎ、当該画像中のｉ行ｊ列のピクセル（ｉ，ｊ）の濃淡
レベルをｇ(i,j)、切り出される部分画像の領域をＳ、
先に初期化されたαは実数パラメータであり、｜Ｓ｜は
部分画像Ｓ内のピクセルの数（Ｓの大きさ）を表すもの
である。また、以下の説明のため、０≦ｇ(i,j)≦１と
仮定するが、この仮定は容易に外すことができるもので
ある。

【００１５】そして検出処理部３は、あるαについてＵ
_α(Ｓ）を最大にするような、許容イメージである部分
画像Ｓを検出する（ステップ２７）。先に述べたように
最初αは０にセットされている。このステップ２７は、
処理全体の高速化に大きな影響を及ぼす。発明者は、全
体画像の各列に番号を付け、その列番号をインデックス
とした動的計画法にて処理することを提案している。す
なわち、各列ごとに処理を行っていき、それを連結する
のである。このようにすると、この動的計画法に現れる
行列に「モンジュ性」と呼ばれる擬凸性があること、区
間和の問い合わせデータ構造（例えば、A.Aggarwal and
T.Tokuyama:"Consequtive Interval Query and Dynami
c Programming on Intervals" LNCS 762,Proc.ISAAC93,
pp.466-475,1993参照のこと）を用いると、計算時間は
Ｏ（ｎ）になり、非常に高速である。この処理の詳細な
フローは後に詳細に述べる。しかし、本発明はこのよう
な方法に限定されるものではない。

【００１６】この処理で検出された部分画像Ｓは、同じ
ピクセル数を有する許容イメージの中では濃度和が最も
大きいものである。そして、あるαに対してＵ_α(Ｓ）
を最大化する許容イメージは、局所鮮明なイメージとい
う。実際に局所鮮明でない画像は通常人間の目で見ても
鮮明とは言えない。

【００１７】検出処理部３は、あるαに対して局所鮮明
な画像Ｓを検出すると、そのＳの大きさ｜Ｓ｜を比較部
５に出力する。この｜Ｓ｜は、Ｕ_α(Ｓ）計算中に用い
られるので、新たに計算する必要はない。比較部５で
は、先に入力された画像の所望の大きさｋと、｜Ｓ｜と
を比較する（ステップ２９，３１）。ステップ２９にて
ｋ＝｜Ｓ｜であると認められると、比較部５は制御部７
への出力Ａをアクティブにする。これは、局所鮮明な画
像であり、且つ大きさが所望のものであるから、処理は
終了する。よって、制御部７は、検出処理部３に、後処
理装置９へ、検出した局所鮮明な画像を出力するように
命ずる（ステップ３７）。

【００１８】これに対し、ｋ＝｜Ｓ｜でなければ、ｋ＜
｜Ｓ｜かどうかを検査し（ステップ３１）、この条件が
当てはまる場合には、比較部５は制御部７への出力Ｂを
アクティブにする。この場合、制御部７は、αを変数ε
分増加させるように検出処理部３に命令する（ステップ
３３）。

【００１９】また、ｋ＜｜Ｓ｜でない場合には、ｋ＞｜
Ｓ｜であり、この場合には比較部５は制御部７への出力
Ｃをアクティブにする。そうすると、制御部７はαを変
数ε分減少させるように検出処理部３に命令する（ステ
ップ３５）。

【００２０】ここで、αを増減させる変数εであるが、
２分探索を用いるとよい。すなわち、ステップ２５にて
セットしたようにεの初期値をｎとし、制御部７は繰り
返すごとにこのεを半分にしていく（ステップ４１）。
そして、εが１／γより小さくなった場合には、これ以
上の改良はないので、処理を中止して現在の画像を出力
するように検出処理部３に命ずる（ステップ４３）。先
のステップ２７の実施方法と合わせて、所望のサイズｋ
に最も近い局所鮮明な画像がＯ（ｎｌｏｇγ）で計算さ
れることがわかった。このγは問題の精度と呼ばれるも
のであるが、通常ｎとしても問題ない。よってＯ（ｎｌ
ｏｇｎ）で計算できることとなる。

【００２１】以上一実施例を説明してきたが、本発明は
本実施例のみに限定されるものではない。例えば、図５
に示した比較部５は３本の出力線を有していたが、これ
は３つの状態を示すことができればよいので、３本の出
力線に限定されない。例えば、２本の出力線で表すこと
ができる４つの状態のうち３つを、それぞれの状態に割
当てることもできるし、１本で異なる３つの状態を表す
ようにしてもよい。さらに、ステップ２９及び３１に
て、３つの状態を検出しているが、この順番は任意であ
り、先ほどは最後に判断されたｋ＞｜Ｓ｜を最初に検出
するようにすることは任意である。

【００２２】また、本発明は図５に示した特別の装置に
て実施するように記載したが、図６のようなアルゴリズ
ムのプログラムを実行する通常のコンピュータ・システ
ムにても実施可能である。この場合、検出処理部３、比
較部５、制御部７は、中央処理装置（ＣＰＵ）にて代用
され、場合によっては後処理装置９もこれに含まれる。
また、表示出力処理のみを後処理装置９が行う場合に
は、専用のグラフィック処理アダプタ等にて処理される
場合もある。さらに画像記憶部１は、補助記憶装置であ
る場合もあるし、主記憶装置である場合もある。上述の
プログラムは、記憶装置、例えばＣＤ−ＲＯＭやフロッ
ピーディスクに格納されていてもよい。

【００２３】［Ａｐｐｅｎｄｉｘ］ここでは、Ｕ_αを最
大化する許容イメージを濃淡画像から切り出す処理を詳
細に説明する。この許容イメージは、先に述べたように
１つの軸方向に凸であるイメージを言う。より正確に言
うと、Ｘ軸方向へ単調な２本の曲線で囲まれる連結イメ
ージを言う。このことは、図７に例を示す。左には、幅
１のＹ軸方向に伸びる帯で切ると必ず連結している例を
示しており、このようなイメージを許容イメージとい
う。また、右には、先のような帯で切ると連結していな
い例が示されており、このようなイメージを含めて切り
出そうとすると、その問題はＮＰ困難となってしまう。

【００２４】このような許容イメージに問題を限定する
と、Ｙ軸方向に伸びる帯は必ず連結しているので、ダイ
ナミックプログラミングを用いて、それらを順々に連結
していけばよい。但し、もう１つのパラメータを指定す
る必要がある。例えば、ピクセル数である。

【００２５】全体の許容イメージの連結性は、以下の事
項を考えると分かる。すなわち、ｋ個のピクセルを含
み、ｍ列より左のピクセルからなり、（ｍ，ｔ）の位置
を含むイメージ（図８参照のこと）を考え、この時に濃
淡度の総和をｆ（ｋ，ｍ，ｔ）とすると、これは以下の
数式を満たすものである。

【数５】

【００２６】ここで、ＩはＸ軸上ｍ列目の連続区間（範
囲）であり、ｔ，ｌを含む。また、ｆ（ｋ−｜Ｉ｜，ｍ
−１，ｌ）を計算する時に用いたＸ軸上ｍ−１列目の連
続区間（範囲）はｌを含むので、Ｉと連結している。従
って、帰納法よりｆ（ｋ，ｍ，ｔ）を求めるまでに用い
た連続区間全体は連結していることが保証されている。

【００２７】また、数４を以下のように変形する。すな
わち、部分画像Ｓに含まれるピクセルを各列Ｉごとに分
け、各列のピクセル数をその列番号ｋを用いてＨk、濃
淡度和をＧkと表し、且つ部分画像Ｓに含まれる列の番
号の集合をＲとすると、

【数６】のように変形される。このように、Ｕ_α（Ｓ）を最大に
するということは、部分画像Ｓ内の各列ｋにおいてもｎ
Ｇk−αＨkが最大となるような濃淡画像の列を連結して
いくこととなる。

【００２８】よって、数５の式と数６を合わせ考え、α
が与えられた時、数４を最大とする部分画像Ｓを求める
ため、Ｕ（ｍ，ｔ）という次のような式が導入できる。

【数７】この数７のＡは、ｔ，ｌを含む連続区間（範囲）全体で
数７のＢを最大化する連続区間（範囲）Ｉを見つけるこ
とを意味する。

【００２９】このＩをｃｏｖｅｒ（ｔ，ｌ）と記述する
こととする。いま、ｔ≦ｌを仮定すると、次の定義され
るｌｏｗ（ｔ），ｈｉｇｈ（ｌ）を用いれば、

【数８】となる。但し、ｌｏｗ（ｔ）は連続区間［ｉ，ｔ］全体
で数７のＢが最大となるｉであり、ｈｉｇｈ（ｌ）は連
続区間［ｌ，ｊ］全体で数７のＢが最大となるｊを言
う。

【００３０】このｌｏｗ（ｔ）やｈｉｇｈ（ｌ）はダイ
ナミック・プログラミング中では何度も用いられるの
で、ｌｏｗ（ｔ）やｈｉｇｈ（ｌ）を高速に求めること
ができれば有効である。このため、連続区間［ｉ，ｊ］
中の数７のＢが要素Ｋ（ｉ，ｊ）に入る行列Ｋを作る。
但し、ｉ＞ｊの場合にはＫ（ｉ，ｊ）＝（ｉ−ｊ）ｘ
（ｘは十分、その絶対値が大きい負の数。例えば、ｇ
（i,j)を全体について加算した値より絶対値が大きいな
らば十分である。）としておく。すると行番号ｌにおい
て最大値を有する列の列番号がｈｉｇｈ（ｌ）となる。
よって、すべてのｌ∈［１，Ｎ］についてｈｉｇｈ
（ｌ）を求める問題は、Ｋの各行の最大値の列番号を求
める問題となる。このような計算は、Ｏ（Ｎ）の計算量
で行える。

【００３１】このＫで各行の最大値に注目すると、行番
号が大きくなるにつれて最大値の列番号は単調に増加す
る。但し、同じ行に最大値が複数個ある時には、左端の
みを考える。このような行列を「単調な行列」と呼ぶ。
証明は省略するがこの行列Ｋは「完全単調な行列」（任
意の部分行列が単調行列であるような行列。）でもあ
る。Ｋの一例を図９に示し、斜線部が各行の最大値であ
る。単調な行列の全ての行の最大値を有する列番号を計
算するにはＯ（ＮｌｏｇＮ）の計算量が必要である。

【００３２】同様にしてｌｏｗ（ｔ）を計算する場合に
は、連続区間［ｉ，ｊ］中の数７のＢが要素Ｌ（ｊ，
ｉ）に入る行列Ｌを作り、行番号ｔにおける最大値を有
する列の列番号を求めれば、ｌｏｗ（ｔ）になる。今度
は上三角部分（ｉ＞ｊ）を−∞とする。このような行列
も完全単調な行列である。

【００３３】このようにして求めたｌｏｗ（ｔ）及びｈ
ｉｇｈ（ｌ）を用いれば、ｃｏｖｅｒ（ｔ，ｌ）が求ま
り、数７の変形である以下の式が計算可能となる。

【数９】

【００３４】Ｕ（ｍ，ｔ）を最大にするような、イメー
ジを見い出すには、Ｕ（ｍ，ｔ）の計算をＸ軸に垂直な
帯について順に行い、その帯を記憶しておき、それらを
連結すれば求まる。

【００３５】さらに高速化するには、

【数１０】を要素として有する行列Ｍ'を作り、行番号ｔの最大値
がＵ（ｍ，ｔ）となる。Ｍ'は先に説明した完全単調な
行列であり、すべてのｔについてＵ（ｍ，ｔ）はＯ
（Ｎ）で計算することができる。よって、すべてのｍに
ついてＵ（ｍ，ｔ）を計算するには、Ｏ（Ｎ²）の計算
量が必要となる。

【００３６】以上詳細を述べたが、必要なステップを以
下に示しておく。（１）全てのＸ軸に垂直な帯についてｌｏｗ（ｔ），ｈ
ｉｇｈ（ｌ）を計算しておく。（２）ｌｏｗ（ｔ），ｈｉｇｈ（ｌ）によりｃｏｖｅｒ
（ｔ，ｌ）が求まるので、数１０を要素とする行列Ｍ'
を計算する。（３）行列Ｍ'の各行の最大値を求め、その値をＵ
（ｍ，ｔ）として記憶する。（４）イメージ全体を把握するために、行列Ｍ'の各行
の最大値を示す列番号ｌをｓ（ｍ，ｔ）に入力する。ま
た、Ｐ（ｍ，ｔ）には、ピクセル数も記憶しておく。（５）Ｕ（ｍ，ｔ）を最大にするｍ，ｔを求め、（４）
で作ったｓ（ｍ，ｔ）及びｓ（ｍ，ｔ）に記憶されてい
るｌを用いて前列のｌｏｗ（ｔ），ｈｉｇｈ（ｌ）でも
って、イメージを把握する。また、Ｐ（ｍ，ｔ）にてピ
クセル数も把握できる。

【００３７】このステップを図１０及び図１１に示す。
ステップ６１０で開始した処理は、ステップ６２０にお
いてｍ＝１の初期化を行う。そしてｍ＝Ｎx＋１である
かを判断する（ステップ６３０）。これはループをＮx
回繰り返すためであり、Ｎxは濃淡画像（行列）の列数
である。

【００３８】この後に、

【数１１】を計算しておき、この行列の各行の最大値を求め、その
列番号ｊをｈｉｇｈ（ｍ，ｉ）とする（ステップ６４
０）。これにより、濃淡値画像のｍ列目のｈｉｇｈ
（ｉ）が求まった。

【００３９】また、

【数１２】を計算しておき、この行列の各行の最大値を求め、その
列番号ｊをｌｏｗ（ｍ，ｉ）＝ｊとする（ステップ６５
０）。これにより、濃淡画像のｍ列目のｌｏｗ（ｉ）が
求まった。

【００４０】その後にｍを１インクメントして（ステッ
プ６６０）、ステップ６３０に戻る。このように、まず
ｌｏｗとｈｉｇｈを最初にすべて計算しておく。図１１
の計算を実行するごとに必要なｌｏｗとｈｉｇｈを計算
するようにしてもよいが、この例のように一度に計算し
てしまってもよい。上述のように一度に計算した後に処
理はＸを介して図１１に進む。

【００４１】図１１においてＸから、Ｕ（ｍ，ｔ）を計
算する。まず、図８のような濃淡画像の一番左の列につ
いて処理する。すなわち、

【数１３】をｔ＝１からＮyについて計算する（ステップ７１
０）。ここでＮyは、濃淡画像（行列）の行番号であ
る。このようにすると、数１０の第１項の初期値となる
ものが計算されたこととなる。また、ピクセル数は後の
処理にて用いるので計算しておく。よって

【数１４】の値をも保持しておく。

【００４２】そして、ｍ＝２以降の値を計算するため
に、ｍ＝２とし（ステップ７２０）、以下のループをＮ
x−１回まわすため、ｍ＝Ｎx＋１かどうか判断する（ス
テップ７３０）。もし、ｍ＝Ｎx＋１でなければ、

【数１５】を計算しておき、この行列Ｍ'の各行の最大値を求め、
その列番号ｌをｓ（ｍ，ｔ）＝ｌ，そしてその列番号ｌ
における値をＵ（ｍ，ｔ）とする（ステップ７４０）。

【００４３】ｓ（ｍ，ｔ）は、列番号ｌが入力されるた
め、濃淡画像におけるｍ−１列とｍ列との連結状態を示
すこととなる。よって、このｓ（ｍ，ｔ）を手繰ってい
けば、イメージがどのように連結するものかを判断する
ことができるわけである。又、

【数１６】のようにＰ（ｍ，ｔ）も保持する。

【００４４】この後に、ｍを１インクリメントし（ステ
ップ７５０）、ステップ７３０に戻る。繰り返しが全て
終われば、Ｕ（ｍ，ｔ）を最大とするｍ，ｔが求まる。
Ｕ（ｍ，ｔ）を作りながら、常に最大となるｍ，ｔを保
持しておき、新たに作成された部分につき保持している
ｍ，ｔより大きな点を見い出した場合には更新するよう
にしていけばよい。このｍ，ｔを用いて、ｓ（ｍ，ｔ）
から、前列のｌが求まる。このｌとｔのうち小さい方を
ｌｏｗに大きい方をｈｉｇｈに入力する。例えば、ｔの
方が小さければ、ｌｏｗ（ｍ，ｔ），ｈｉｇｈ（ｍ，
ｌ）が求まる。また、ｓ（ｍ−１，ｌ）から、さらに前
列のｌ'が求まるので、ｌｏｗ（ｍ−１，ｌ'），ｈｉｇ
ｈ（ｍ−１，ｌ'）を求める。ここでは、ｌの方がｌ'よ
り小さい。これを繰り返していくと、イメージＳの全体
が分かる（ステップ７６０）。又、Ｐ（ｍ，ｔ）にて後
にｋとの比較の対象がわかる。

【００４５】但し、上では述べたかったが、もう１つの
工夫が必要である。負の数７のＢを有するイメージ部分
を付加しても、全体のＵ（ｍ，ｔ）は増加しない。よっ
て、ステップ７４０を実施する際に、Ｍ'(ｔ，ｌ）のあ
る行の最大値が負の値を有している場合にはそれに対応
するｓ（ｍ，ｔ）に、所定の値を入力しておき、連結関
係を切る必要がある。すなわち、ｓ（ｍ，ｔ）にはある
行の最大値を有する列番号ｌを入力するが、列番号とし
て可能性がないような値を入力することにより、連鎖が
切れ、よって最終的に得られるイメージＳには組み込ま
れなくなる。

【００４６】以上Ａｐｐｅｎｄｉｘで述べた事項をさら
に一般化する。すなわち、上述の数７のＢのαＨmのよ
うな条件を一般的にＮとすると、ｌｏｗとｈｉｇｈは、
以下のようになる。

【数１７】

【数１８】また、Ｕ（ｍ，ｔ）も、以下のように書ける。

【数１９】このような一般化がなされても、段落００３６で書かれ
たステップは、そのまま実行可能である。当然Ｍ'
（ｔ，ｌ）は、Ｕ（ｍ，ｔ）と同様の変形が必要であ
る。すなわち、

【数２０】

【００４７】よって、この一般化を説明すると、以下の
ようになる。各画素が、中間調を含む濃淡により表され
た全体画像から、列方向に凸である部分画像（許容イメ
ージ）を切り出す方法であって、所定の条件Ｎを入力す
るステップと、全体画像の各列において、あるピクセル
（ｔ又はｌ）を含み且つ包含されるピクセル（例えば
（ｉ，ｊ））の濃淡レベルｇ(i,j)からＮを減じた値
（ｇ(i,j)−Ｎ）の総和である評価値が最大となるピク
セルの範囲（ｈｉｇｈ（ｌ），ｌｏｗ（ｔ））を求める
列内範囲導出ステップと、全体画像の任意のピクセル
（ｍ，ｔ）の前列にあるもう１つのピクセル（ｍ−１，
ｌ）を含み且つ当該前列までで最大の評価値（Ｕ（ｍ−
１，ｌ））を有する領域と、列内範囲導出ステップの結
果を用いることにより導出される、前記任意のピクセル
（ｍ，ｔ）及び前記もう１つのピクセルと同一行であっ
て前記任意のピクセルと同一列にあるピクセル（ｍ，
ｌ）を含む評価値が最大となる範囲（ｃｏｖｅｒ（ｔ，
ｌ））とを加えた加算領域を求め、各前記任意のピクセ
ルにつき、前記加算領域の評価値が最大となる前記もう
１つのピクセル（ｍ−１，ｌ）を検出し（ｓ（ｍ，
ｔ））、当該加算領域の評価値（Ｕ（ｍ，ｔ））と共に
記憶する検出記憶ステップと、全体画像で加算領域の評
価値（Ｕ（ｍ，ｔ））が最大となる前記任意のピクセル
を検出し、検出記憶ステップで検出された前記もう１つ
のピクセルを用いて、領域Ｓを導き出すステップとを含
む、というように記することができる。

【００４８】

【発明の効果】以上述べたように、計算量を減少させつ
つ、所定の大きさに近い鮮明な、許容イメージである部
分画像を切り出すことができた。

【００４９】この計算量の減少は、従来の統計的な共分
散を用いた方法ではＯ（ｎ^2.5）であったのに対し、本
方法ではＯ（ｎｌｏｇｎ）で済むようにすることができ
た。よって、２００ピクセル×２００ピクセルの画像
（ｎ＝４００００）を扱う場合には、従来の方法に比し
ておよそ５２万倍高速である。

【図面の簡単な説明】

【図１】濃淡がはっきりした画像の例を示した図であ
る。

【図２】図１に比して濃淡が不鮮明な画像の例を示した
図である。

【図３】一般的な連結性を有する画像の例を示した図で
ある。

【図４】許容イメージの例を示した図である。

【図５】本発明の一実施例の装置構成を示す図である。

【図６】図５に示した装置の処理動作を示した図であ
る。

【図７】許容イメージの例を示した図である。

【図８】列と列の連結に関する説明のための図である。

【図９】単調な行列の説明のための図である。

【図１０】イメージ切り出しのフローを示す図である。

【図１１】イメージ切り出しのフローを示す図である。

【符号の説明】

１画像記憶部３検出処理部５比較部７制御部９後処理部

───────────────────────────────────────────────────── フロントページの続き (56)参考文献特開平７−182519（ＪＰ，Ａ) (58)調査した分野(Int.Cl.⁷，ＤＢ名) G06T 7/00

Claims

(57)【特許請求の範囲】

【請求項１】各画素が、中間調を含む濃淡により表され
た全体画像から、部分画像を切り出す方法であって、切り出される部分画像の画素数ｋを指定する指定ステッ
プと、【数１】（ｎは全体画像の画素数、ｇ(i,j)は画素（ｉ，ｊ）の
濃淡レベル、｜Ｓ｜は部分画像Ｓの画素数）のＵ
_α(Ｓ）を最大化する部分画像を検出する検出ステップ
と、Ｕ_α(Ｓ）を最大化した前記部分画像の画素数｜Ｓ｜と
指定された前記画素数ｋを比較する比較ステップと、前記比較ステップによる結果が｜Ｓ｜＞ｋの場合αを増
加させ、｜Ｓ｜＜ｋの場合αを減少させるステップと、新たなαでもって前記検出ステップ以後を実行するステ
ップと、前記比較ステップによる結果が｜Ｓ｜＝ｋの場合には、
当該Ｕ_α(Ｓ）を最大化した部分画像を出力するステッ
プとを含む画像切出方法。
【請求項２】前記検出ステップが、前記全体画像を複数
の列に分割し、分割された列につき動的計画法を適用す
ることを特徴とする請求項１記載の画像切出方法。
【請求項３】ある部分画像の濃淡レベルの総和から画素
数にαを乗じた値を減じたものを評価値とし、前記検出ステップが、前記全体画像の各列において、ある画素を含み且つ評価
値が最大となる画素の範囲を求める列内範囲導出ステッ
プと、前記全体画像の任意の画素（座標（ｍ，ｔ））の前列に
あるもう１つの画素（座標（ｍ−１，ｌ））を含み且つ
当該前列までで最大の評価値を有する領域と、前記列内
範囲導出ステップにより導出される、前記任意の画素及
び前記もう１つの画素と同一行であって前記任意の画素
と同一列にある画素（座標（ｍ，ｌ））を含む評価値が
最大となる範囲とを加えた加算領域を求め、各前記任意
の画素につき、前記加算領域の評価値が最大となる前記
もう１つの画素を検出し、当該評価値と共に記憶する検
出記憶ステップと、前記全体画像で加算領域の評価値が最大となる前記任意
の画素を検出し、前記検出記憶ステップで検出された前
記もう１つの画素を用いて、領域Ｓを導き出すステップ
とを含む請求項１記載の画像切出方法。
【請求項４】各画素が、中間調を含む濃淡により表され
た全体画像から、列方向に凸である部分画像を切り出す
方法であって、所定の条件Ｎを入力するステップと、前記全体画像の各列において、ある画素を含み且つ包含
される画素（座標（ｉ，ｊ））の濃淡レベルｇ(i,j)か
らＮを減じた値（ｇ(i,j)−Ｎ）の総和である評価値が
最大となる画素の範囲を求める列内範囲導出ステップ
と、前記全体画像の任意の画素（座標（ｍ，ｔ））の前列に
あるもう１つの画素（座標（ｍ−１，ｌ））を含み且つ
当該前列までで最大の評価値を有する領域と、前記列内
範囲導出ステップにより導出される、前記任意の画素
（座標（ｍ，ｔ））及び前記もう１つの画素と同一行で
あって前記任意の画素と同一列にある画素（座標（ｍ，
ｌ））を含む評価値が最大となる範囲とを加えた加算領
域を求め、各前記任意の画素につき、前記加算領域の評
価値が最大となる前記もう１つの画素を検出し、当該評
価値と共に記憶する検出記憶ステップと、前記全体画像で加算領域の評価値が最大となる前記任意
の画素を検出し、前記検出記憶ステップで検出された前
記もう１つの画素を用いて、領域Ｓを導き出すステップ
とを含む画像切出方法。
【請求項５】各画素が、中間調を含む濃淡により表され
た全体画像から、部分画像を切り出す装置であって、切り出される部分画像の画素数ｋを入力する入力手段
と、【数２】（ｎは画素数、ｇ(i,j)は画素（ｉ，ｊ）の濃淡レベ
ル、｜Ｓ｜は部分画像Ｓの画素数）のＵ_α(Ｓ）を最大
化する部分画像を検出する検出手段と、Ｕ_α(Ｓ）を最大化した前記部分画像の画素数｜Ｓ｜と
指定された前記画素数ｋを比較する比較手段と、前記比較手段による結果が｜Ｓ｜＞ｋの場合αを増加
し、｜Ｓ｜＜ｋの場合αを減少し、新たなαでもって前
記検出手段を動作させ、｜Ｓ｜＝ｋの場合には前記検出
手段に当該最大化された部分画像を出力させる制御手段
とを含む画像切出装置。
【請求項６】前記検出手段が、前記全体画像を複数の列
に分割し、分割された列につき動的計画法を適用するこ
とを特徴とする請求項５記載の画像切出装置。
【請求項７】ある部分画像の濃淡レベルの総和から画素
数にαを乗じた値を減じたものを評価値とし、前記検出手段が、前記全体画像の各列において、ある画素を含み且つ評価
値が最大となる画素の範囲を求める列内範囲導出手段
と、前記全体画像の任意の画素（座標（ｍ，ｔ））の前列に
あるもう１つの画素（座標（ｍ−１，ｌ））を含み且つ
当該前列までで最大の評価値を有する領域と、前記列内
範囲導出手段により導出される、前記任意の画素及び前
記もう１つの画素と同一行であって前記任意の画素と同
一列にある画素（座標（ｍ，ｌ））を含む評価値が最大
となる範囲とを加えた加算領域を求め、各前記任意の画
素につき、前記加算領域の評価値が最大となる前記もう
１つの画素を検出し、当該評価値と共に記憶する検出記
憶手段と、前記全体画像で加算領域の評価値が最大となる前記任意
の画素を検出し、前記検出記憶手段で検出された前記も
う１つの画素を用いて、領域Ｓを導き出す手段とを含む
請求項５記載の画像切出装置。
【請求項８】各画素が、中間調を含む濃淡により表され
た全体画像から、列方向に凸である部分画像を切り出す
装置であって、所定の条件Ｎを入力する手段と、前記全体画像の各列において、ある画素を含み且つ包含
される画素（座標（ｉ，ｊ））の濃淡レベルｇ(i,j)か
らＮを減じた値（ｇ(i,j)−Ｎ）の総和である評価値が
最大となる画素の範囲を求める列内範囲導出手段と、前記全体画像の任意の画素（座標（ｍ，ｔ））の前列に
あるもう１つの画素（座標（ｍ−１，ｌ））を含み且つ
当該前列までで最大の評価値を有する領域と、前記列内
範囲導出手段により導出される、前記任意の画素（座標
（ｍ，ｔ））及び前記もう１つの画素と同一行であって
前記任意の画素と同一列にある画素（座標（ｍ，ｌ））
を含む評価値が最大となる範囲とを加えた加算領域を求
め、各前記任意の画素につき、前記加算領域の評価値が
最大となる前記もう１つの画素を検出し、当該評価値と
共に記憶する検出記憶手段と、前記全体画像で加算領域の評価値が最大となる前記任意
の画素を検出し、前記検出記憶手段により検出された前
記もう１つの画素を用いて、領域Ｓを導き出す手段とを
含む画像切出装置。
【請求項９】各画素が、中間調を含む濃淡により表され
た全体画像から、列方向に凸である部分画像をコンピュ
ータに切り出させるプログラムコード手段を含む記憶装
置であって、前記プログラムコード手段が、コンピュータに、所定の条件Ｎを入力させるプログラム
コード手段と、コンピュータに、前記全体画像の各列において、ある画
素を含み且つ包含される画素（座標（ｉ，ｊ））の濃淡
レベルｇ(i,j)からＮを減じた値（ｇ(i,j)−Ｎ）の総和
である評価値が最大となる画素の範囲を求めさせる列内
範囲導出プログラムコード手段と、コンピュータに、前記全体画像の任意の画素（座標
（ｍ，ｔ））の前列にあるもう１つの画素（座標（ｍ−
１，ｌ））を含み且つ当該前列までで最大の評価値を有
する領域と、前記列内範囲導出プログラムコード手段及
びコンピュータにより導出される、前記任意の画素（座
標（ｍ，ｔ））及び前記もう１つの画素と同一行であっ
て前記任意の画素と同一列にある画素（座標（ｍ，
ｌ））を含む評価値が最大となる範囲とを加えた加算領
域を求めさせ、各前記任意の画素につき、前記加算領域
の評価値が最大となる前記もう１つの画素を検出させ、
当該評価値と共に記憶させる検出記憶プログラムコード
手段と、前記全体画像で加算領域の評価値が最大となる前記任意
の画素を検出し、前記検出記憶プログラムコード手段及
びコンピュータにより検出された前記もう１つの画素を
用いて、領域Ｓを導き出させるプログラムコード手段と
を含む記憶装置。