JP4956304B2 - 画像符号化装置及びその制御方法、並びに、コンピュータプログラム及びコンピュータ可読記憶媒体 - Google Patents

Description

本発明は画像データの符号化技術に関するものである。

特許文献１には、文字・線画と自然画が混在した多値画像を圧縮する技術を開示している。この文献では、入力画像を符号化の際の直交変換の単位となるブロックに分割した後、ブロック内で最も出現確率の高い最頻値を文字や線画であると仮定する。そして、その最頻値の色情報もしくは濃度情報の画素データを選択する。そしてブロックより、最頻となる画素データを抽出し、抽出された色及び抽出画素であるか否かを示す識別情報（以下、これら２つの情報を合わせて解像情報と称する）に対してランレングス符号化などの可逆符号化を行う。そして、文字や線画情報抽出した後の自然画の各画素の値を、文字線画として抽出された画素を除く、ブロックの平均値で置換する。そして、置換された自然画に対し、ＪＰＥＧ等の非可逆符号化を行うものである。

ここで、上記色情報の抽出について図１２に示す４×４画素ブロックの画素データを例に説明する。図１２のブロックの画素データは、平均レベルが“６６”の自然画の一部に“２４０”というレベルの文字（の一部）が上書きされていたものと考えられる。通常、自然画においてはスキャナやデジタルカメラ等のアナログ入力機器を通して生成されるため、ノイズ等により画素値にはばらつきが発生する。これに対し、デジタル的に発生させた文字では、ノイズが入り込まないので、同一の値が連続するはずである。このような仮定から着目ブロックの最頻値を検出し、文字・線画としてブロックから抽出する。図１２のブロックでは最頻値は“２４０”であるから、これが抽出色となる。よって、抽出画素の位置を示す識別情報は図１３に示ようになる。上記文字・線画の抽出色及び上記識別情報を可逆符号化にて圧縮する。

一方、上記識別情報が“０”となる画素データの平均値は“６６”であるので、上記識別情報の“１”となる領域の画素データを上記平均値で置換する。この置換後の画素データ（階調情報）は図１４に示される様になる。これを非可逆符号化にて圧縮する。

その他にも、多値画像を複数の成分に分離して、別々に符号化する技術が知られている（例えば、特許文献２、特許文献３、特許文献４）。
特開平０４-３２６６６９号公報 特開平０３-２５４５７３号公報 特開平０４-０４００７４号公報 特開２００２-０７７６３１号公報

上記の特許文献１は、図１２に示すブロックのように上書きされた文字の色が同一値である場合、符号化効率を向上させるには有効な手法である。しかし、その反面、グラデーションがかかっている文字（以下、グラデーション文字と称する）が自然画に上書きされている場合には、文字・線画部の画素値もばらつきが発生する。また、スキャナやデジタルカメラ等のアナログ入力機器を通して、文字・線画を含む画像を撮像した場合も同様である。このように、文字・線画の画素値にバラツキが発生すると、圧縮率を高めることが困難になるという問題がある。

この様子を図１５に示される４×４画素ブロックの画素データを例に説明する。

図１５に示される画素データは、平均レベルが“６６”の自然画像の一部に、文字が上書きされ、その値“２３１”、“２３３”、“２３５”、“２３９”、“２４０”である例である。従来手法では、ブロック内で最も出現確率の高い最頻値が抽出色となるため、上記例での抽出色は“６５”となり、この時の画素の位置を示す識別情報は図１６に示される様になる。そして、上記識別情報が“０”となる画素データの平均値が“１４４”であるので、上記識別情報は“１”となる画素は上記平均値で置換され、図１７に示すようになる（階調情報）。この階調情報は、図１５に示される画素データのエッジ成分を殆ど削減できておらず、その結果、圧縮率を高めることができない。

また、ブロック内のヒストグラムを求め、ヒストグラムから閾値を生成して文字部を抽出するような場合においても、復号時には置換画素（上記識別情報の“１”となる画素）は抽出色で置き換えられてしまう。従って、グラデーション文字等の階調を持ったブロックでは階調性を再現することは困難になる。

本発明は、上記課題に鑑みなされたものであり、複数種類の画像が混在した画像を高品位かつ高圧縮率で符号化する技術を提供するものであり、特に、ある程度ばらついた画素値で構成されるグラデーション文字・線画と、自然画とが混在した画像であっても、グラデーション文字・線画の階調も十分な品位で再現でき、且つ、符号化効率の高い技術を提供するものである。

この課題を解決するため、例えば本発明の画像符号化装置は以下の構成を備える。すなわち、
多値画像データを、複数の画素で構成されるブロック単位に入力する入力手段と、
前記入力したブロック内の各画素を、該各画素の値に応じて第１及び第２のグループに分類すると共に、各画素がいずれのグループに属するかを識別する識別情報を生成する識別情報生成手段と、
前記第１のグループに属する画素の値の平均値、前記第２のグループに属する画素の値の平均値、及び、該２つの平均値の差分値を算出する算出手段と、
前記第１のグループの平均値と前記第２のグループの平均値との差が小さくなるように、前記第１のグループに属する各画素の値に前記差分値を加算、又は前記第１のグループに属する各画素の値から前記差分値を減算することにより、前記第１のグループに属する画素の値を置換する置換手段と、
置換後のブロック内の各画素の値と、前記差分値と、前記識別情報とを符号化し、着目ブロックの符号化データを出力する符号化手段とを備える。

本発明によれば、複数種類の画像が混在した画像を高品位かつ高圧縮率で符号化することができる。特に、ある程度ばらついた画素値で構成されるグラデーション文字・線画と、自然画とが混在した画像であっても、グラデーション文字・線画の階調も十分な品位で再現でき、且つ、符号化効率の高い符号化データを生成することができる。

以下、添付図面に従って本発明に係る実施形態を詳細に説明する。

＜第１の実施形態＞
図１は、第１の実施形態における符号化装置のブロック構成図である。

図中、２５１は多値画像を入力する入力端子であり、２０３は多値画像を、入力単位であるブロック化する際に画素データを一時的に記憶するためのバッファである。２０４はブロック内の多値画像から抽出する画素データ（以下、抽出色と記す）を決定すると共に、各画素が抽出する画素であるか、非抽出の画素であるのかを識別するための識別情報（１画素につき１ビットの判定情報）を生成するための抽出部である。言い換えると、この抽出部２０４は、入力したブロック内の各画素を、画素値の置換対象の第１のグループと、非置換対象の第２のグループのいずれかに分類すると共に、各画素がいずれのグループに属するのかを識別するための識別情報を生成する識別情報生成部として機能する。なお、この識別情報は各画素の値に応じて決定し、各画素位置に対応づけて生成される。この抽出部２０４の詳細については後述する。

２０６は上記識別情報が示す領域毎に画素データの平均値を算出し、そこで得られた複数の平均値の差分値（以下、平均差分値と記す）を出力するための平均差分値生成部である。２０７は上記抽出対象となった画素の置換後の画素データ（以下、置換色と記す）を生成するための置換色生成部である。２０８は、入力した多値画像データ、置換色データのいずれか一方を選択し、出力するセレクタである。２０９は識別情報をランレングス等の符号化をするための第１の符号化部である。２１０は平均差分値を符号化するための第２の符号化部である。これら、符号化部２０９、２１０は可逆符号化データを生成する。２１１はセレクタ２０８の出力値（以下、階調情報と記す）を符号化する第３の符号化部である。この符号化部２１１は、可逆でも構わないが、実施形態では、ＪＰＥＧ等の自然画に好適な非可逆符号化部とする。２１２は夫々の符号化データを後段のメモリに格納しやすいようにパックして、符号化データとして出力するための多重化部であり、２５２は符号化データを出力するための出力端子である。

図１８は、多重化部２１２から出力される符号化データファイル１８００のデータ構造を示している。図示の如く、符号化データファイル１８００は、画像データのサイズ情報（水平、垂直方向の画素数）、色成分の数、各色のビット数等の復号に必要な情報を格納するファイルヘッダを備える。そして、そのファイルヘッダに後続して各ブロックの符号化データが格納されている。１つのブロックの符号化データは、図示のブロックデータ１８０１か、ブロックデータ１８０２のいずれかのタイプになる。ブロックデータ１８０１は、該当するタイプを示すブロックヘッダを有し、それに後続して、符号化部２０９で生成される識別情報の符号化データと、符号化部２１０で生成される平均差分値の符号化データ、及び、符号化部２１１で生成される階調情報符号化データが格納される。もう１つのブロックデータ１８０２は、該当するタイプであることを示すブロックヘッダを有し、それに後続して、入力した多値画像データを符号化部２１１で符号化したデータが格納される。かかる構造になる理由は以下の説明から明らかにする。

次に、図１の符号化装置の動作を説明する。説明を簡単にするため、実施形態で符号化する対象の多値画像データはモノクロ多値画像であるものとし、１画素が８ビット（２５６階調）であり、その値は濃度を示すものとする。

入力端子２５１から入力された多値画像は、一旦バッファ２０３に格納された後、ブロック単位に順次読み出され、抽出部２０４、及び平均差分値生成部２０６、及び置換色生成部２０７、及びセレクタ２０８へ送られる。

抽出部２０４では、抽出画素を決定し、ブロック内の各画素が抽出画素であるか、非抽出画素であるかを識別するための識別情報を生成する。具体的には、抽出部２０４は、ブロック単位に読み出された多値画像を閾値ＴＨ０によって２値化することで、識別情報をを生成する。ここで、上記識別情報の“１”は抽出対象画素であることを示し、“０”は非抽出対象画素を示すものとする。

以下、抽出部２０４の動作を、入力される多値画像が図１５に示される４×４画素として説明する。

抽出対象を決定するための閾値ＴＨ０が“２００”であるとすると、上記画素データのうち“２００”以上の画素データは“１”に、それ未満の値を持つ画素は“０”に２値化される。この結果、ブロック内の各画素位置毎に、０、又は、１の２値化データデータが生成される。図２は、上記のようにして２値化した１ブロック（４×４画素）の識別情報を示している。ここで、閾値ＴＨ０は図示しないＣＰＵ等によって設定された値、あるいは、ブロック平均値やブロックのヒストグラムなどより求められるものとする。

平均差分値生成部２０６では、抽出部２０４から出力された識別情報が“１”である画素群の平均値（ＡＶＥ１）と、識別情報が“０”である画素群の平均値（ＡＶＥ２）とを算出する。また、平均差分値生成部２０６は、算出した２つの平均値の差分値（差分情報）、すなわち平均差分値（Ｄ＝ＡＶＥ１−ＡＶＥ２）を算出する。こうして、平均差分値生成部２０６は、算出した２つの平均値（ＡＶＥ１，ＡＶＥ２）と、平均差分値（Ｄ＝ＡＶＥ１−ＡＶＥ２）を、置換色生成部２０７及び符号化部２１０に供給する。

なお、平均差分値（Ｄ）の絶対値が所定の閾値以下の場合は、抽出する必要がないと判断し、平均差分値、識別情報を共に０にクリアする。あるいは、平均差分値を０としても、後述する置換処理は実質的には動作しなくなるので、平均差分値のみを０にクリアするようにしても良い。この結果、平均差分値の絶対値が所定値以下の場合、そのブロックの符号化データは、図１８のブロック符号化データ１８０２に示すように、階調情報の符号化データのみとなる。

以下、平均差分値生成部２０６の構成を示す図３を用いて動作を説明する。

入力端子４５１より入力された多値画像は「“１”領域平均値生成部４０１」及び「“０”領域平均値生成部４０２」に送られる。

また、抽出部２０４から出力された識別情報も、入力端子４５２から入力されて、「“１”領域平均値生成部４０１」、及び反転回路４０４にて値が反転され、「“０”領域平均値生成部４０２」に送られる。

「“１”領域平均値生成部４０１」は、上記識別情報の“１”に対応する画素データの平均値（ＡＶＥ１）を算出する。

図４は上記「“１”領域平均値生成部４０１」の構成例を示す図であり、以下、同図を参照して、その動作を説明する。

図４において、５５１は抽出部２０４から出力された識別情報を入力する入力端子である。入力端子５５１を介して入力した識別情報は、セレクタ５０１及びカウンタ５０２に供給される。

セレクタ５０１は、入力端子５５２、５５３を備える。入力端子５５２には固定値“０”が予め設定されている。また、入力端子５５３には入力端子４５１から入力された多値画像の画素データが入力される。セレクタ５０１は、入力端子５５１に入力された識別情報（判定情報）が“１”の時は、入力端子５５３のデータ、すなわち、画素データを選択し、出力する。一方、識別情報が“０”の時、セレクタ５０１は、入力端子５５２にセットされた固定値“０”を選択し、出力する。

アキュムレータ５０３は、セレクタ５０１からの出力値を累積加算し、その累積加算結果を割り算器５０４に供給する。

一方、カウンタ５０２では、１ブロック分の識別情報の“１”の個数をカウントし、そのカウント結果を割り算器５０４に供給する。なお、上述したように、上記識別情報は“１”または“０”で構成されている。

１つのブロックの最終データが入力された直後のアキュムレータ５０３の出力値は、着目ブロック内の識別情報の“１”に対応する画素値の総和となる。また、カウンタ５０２の出力値は、識別情報の“１”の個数となる。従って、割り算器５０４は、アキュムレータ５０３の出力値をカウンタ５０２の出力値で除算することで、上記識別情報が“１”の領域の平均値、すなわち抽出画素データの平均値（ＡＶＥ１）を求めることができる。この抽出画素の平均値（ＡＶＥ１）は端子５５５より出力される。なお、カウンタ５０２の出力値が“０”の場合は、“０”が出力端子５５５より出力される。

また、上記平均値（ＡＶＥ１）の算出はブロックごとに行うので、各ブロックの先頭データの入力に先立って、上記カウンタ５０２及び、アキュムレータ５０３をクリアする必要がある。そのために、不図示の制御部は、ブロック内の抽出画素の平均値（ＡＶＥ１）を算出を開始する際に、カウンタ５０２、アキュムレータ５０３を、初期化信号５５４を介してゼロクリア（リセット）する。

ここで、図３に戻り、「“１”領域平均値生成部４０１」の出力値である“１”領域平均値（ＡＶＥ１）は、減算器４０３に送られる。

「“０”領域平均値生成部４０２」では、上記図５を用いて説明した「“１”領域平均値生成部４０１」と同じ構成であり、且つ同じ動作を行う。ただし、入力端子５５１には反転回路４０４にて反転された識別情報が入力される。そのため、「“０”領域平均値生成部４０２」の出力値は、入力端子４５２から入力された識別情報が“０”の領域、すなわち抽出画素でない画素データの平均値である“０”領域平均値（ＡＶＥ２）となる。そして上記“０”領域平均値（ＡＶＥ２）は、減算器４０３に送られる。

減算器４０３では、上記“１”領域平均値（ＡＶＥ１）から上記“０”領域平均値（ＡＶＥ２）を減算した結果（Ｄ＝ＡＶＥ１−ＡＶＥ２）を、出力端子４５３に出力する。

以下、平均差分値生成部２０６の具体的な動作を、図１５に示される４×４画素ブロックの多値画像データと、図２に示される識別情報が入力されたものとして説明する。

上記識別情報の“１”に対応する上記多値画像の画素データは“２３５”、“２３９”、“２４０”、“２３３”、“２３５”、“２３１”である。従って、上記画素データの平均値“２３５”が「“１”領域平均値生成部」の出力値、つまり“１”領域平均値（ＡＶＥ１）となる。

同様に上記識別情報の“０”に対応する上記多値画像の画素データは“６５”、“６８”、“６４”、“６６”、“６５”、“６５”、“６４”、“６６”、“６８”、“６７”である。従って、上記画素データの平均値“６５”が「“０”領域平均値生成部」の出力値、つまり“０”領域平均値（ＡＶＥ２）となる。よって平均差分値生成部２０６の出力値、すなわち平均差分値（Ｄ）は、減算器４０３にて上記“１”領域平均値から上記“０”領域平均値を減算した“１７０”となる。

図１に戻って、置換色生成部２０７は、上記バッファ２０３から出力されたブロック内の各多値画像の画素データから、上記平均差分値生成部２０６から出力された平均差分値（Ｄ）を減算する。そして、その結果は置換色として出力される。ただし、減算した結果が負となる場合は、置換色生成部２０７は着目画素の置換色を“０”（境界値）にクリップして出力する。

置換色生成部２０７の動作例を、入力される多値画像が図１５で示される４×４画素ブロックの画素データとし、入力される平均差分値（Ｄ）が平均差分値生成部２０６の動作例を示した時の平均差分値“１７０”として説明する。

置換色生成部２０７では、ブロック内のすべての画素データから平均差分値“１７０”を減算する。上述したように減算された値が負の場合には、置換色の値は０として出力する。この結果、置換色生成部は２０７は、図５に示される４×４の画素データを置換色として出力することになる。

セレクタ２０８では、入力される識別情報（判定情報）が“０”の時は識別情報の位置に対応する入力多値画像の画素データが選択される。一方、識別情報の“１” の時は識別情報の位置に対応する置換色生成部２０７にて出力された置換色の画素データが選択される。以上の処理をブロック終端画素まで繰り返すことで、着目ブロックの階調情報が得られる。

例えば、図１５で示される４×４画素ブロックの多値画像と、図５で示される４×４画素ブロックの置換色がセレクタ２０８に入力され、且つ、図２で示される４×４画素ブロックの識別情報が制御信号としてセレクタ２０８に入力されたとする。本実施形態では、識別情報が“１”となっている画素群の平均値（ＡＶＥ１）と、識別情報が“０”となっている画素群の平均値（ＡＶＥ２）との差が小さくなるように、一方の画素群の値を置換する。具体的には、識別情報の“０”に対応する画素では多値画像の画素データが選択され、一方、上記識別情報の“１”に対応する画素では上記置換色の画素データが選択される。この結果、セレクタ２０８の出力値は図６で示される４×４画素ブロックの階調情報が出力されることになる。図示に示すように、文字・線画として判定された位置の画素値は、非文字・線画の画素値とほぼ同じ値になる。つまり、あたかも文字線画を含まない自然画を生成することになる。

図６に示される階調情報は、符号化部２１１にて、例えばＪＰＥＧ符号化を用いて圧縮（非可逆符号化）される。なお、この非可逆符号化方法は、ＪＰＥＧに限らず、自然画に適した他の符号化を適用しても良い。

一方、抽出部２０４から出力された識別情報は、符号化部２０９にて、ランレングス符号化を用いて圧縮（可逆符号化）される。なお、この可逆符号化は２値データの符号化に適した他の符号化を適用しても良い。同じく、平均差分値生成部２０６から出力された平均差分値（Ｄ）は、符号化部２１０にて、圧縮（可逆符号化）される。なお、符号化部２０９、符号化部２１０による符号化は、画質に大きく影響するので可逆符号化が望ましい。一方、符号化部２１１による符号化は、高い圧縮率が期待されるので、非可逆符号化が望ましいが、目標の圧縮率になるのであれば可逆符号化でも構わない。

多重化部２１２は、符号化部２０９からの符号化データ、符号化部２１０からの符号化データ、及び符号化部２１１からの符号化データを後段のメモリに格納しやすいように結合し、それを出力端子２５２より出力する。多重化部２１２は、予め、全識別情報が“０”の符号化データを示すパターンデータを記憶するメモリを有し、符号化部２０９から出力された識別情報の符号化データとパターンデータとが一致するか否かを判定する。そして、両者が不一致の場合、すなわち、符号化部２０９から出力された識別情報の符号化データが、少なくとも１つの識別情報“１”があることを示している場合、符号化部２０９、２１０、２１１からの符号化データを結合し、図１８のブロックデータ１８０１のタイプの符号化データを生成し、出力する。一方、符号化部２０９から出力された識別情報の符号化データとパターンデータとが一致する場合、すなわち、符号化部２０９から出力された符号化データが、全識別情報“０”であることを示す場合、多重化部２１２は、符号化部２０９、２１０からの符号化データを破棄し、符号化部２１１からの符号化データを用いて、図１８のブロックデータ１８０２のタイプの符号化データを生成し、出力する。このようにして、先に説明したように図１８のブロック符号化データ１８０１、又は１８０２のデータで構成される符号化データファイルを生成する。

なお、上記では、多重化部２１２が符号化部２０９からの符号化データとパターンデータとを比較する例を示したが、これによって本発明が限定されるものではない。例えば、抽出部２０４が、１ブロック分の識別情報を生成した際、その全てが“０”であるか否かを示す信号を多重化部２１２に供給する。多重化部２１２は、抽出部２０４からのこの信号に従って、ブロックデータ１８０１、１８０２のいずれか一方を生成しても構わない。

次に、本実施形態における画像復号処理を説明する。図７は、実施形態における画像復号装置のブロック構成図である。

図中、８５１は不図示のメモリから読み出した符号化データを入力する入力端子であり、８０１は符号化データを符号化された識別情報、符号化された平均差分値（Ｄ）、及び、符号化された階調情報に分離する分離部である。８０２は上記識別情報を復号化させるための第１の復号化部であり、８０３は上記平均差分値（Ｄ）を復号化させるための第２の復号化部であり、８０４は上記階調情報を復号化させるための第３の復号化部である。そして、８０５は多値画像を復元し、その復元結果を出力する画像復元部である。

上記構成における１ブロックの復号処理を以下に説明する。

入力端子８５１から入力される１ブロック分の符号化データは、図１の出力端子２５１から出力された符号化データと等しい。

そこで、分離部８０１は、入力した着目ブロック分の符号化データのブロックヘッダを解析し、着目ブロックの符号化データが、図１８のブロックデータ１８０１、１８０２のいずれのタイプであるかを判定する。着目ブロックが、ブロックデータ１８０１のタイプであると判定した場合、ブロックヘッダに後続する識別情報の符号化データ、平均差分値の符号化データ、及び階調情報の符号化データを分離し、分離された各符号化データを各々に対応する復号化部８０２、８０３、８０４に供給する。

なお、分離部８０１は、予め、全識別情報が“０”の符号化データのパターンデータ、及び、平均差分値が“０”の符号化データのパターンデータを記憶するメモリを有する。そして、着目ブロックの符号化データがブロックデータ１８０２のタイプであると判定した場合、分離部８０１は、自身のメモリに予め記憶された全識別情報が“０”の符号化データのパターンデータを復号化部８０２に出力すると共に、自身のメモリに格納されている平均差分値が“０”の符号化データのパターンデータを復号化部８０３に出力する。そして、分離部８０１は、入力したブロックヘッダに後続する階調情報の符号化データを復号化部８０４に出力する。

復号部８０２は、入力した符号化識別情報を復号し、その結果を画像復元部８０５に出力する。復号部８０２は、図１の符号化部２０９に対応するものであり、可逆復号を行なう。それ故、復号化部８０２から出力された識別情報は、図１の抽出部２０４から出力された識別情報と完全に一致する。

復号部８０３は図１の符号化部２１０に対応するものであり、可逆復号を行なう。それ故、復号部８０３で復号した平均差分値は、図２の平均差分値生成部２０６から出力された符号化前の平均差分値（Ｄ）と完全に一致する。

復号化部８０４は、入力した１ブロック分の階調情報を復号する。実施形態における復号部８０４は非可逆符号化データを復号するものであるから、図１のセレクタ２０８から出力する階調データとは完全には一致しないが、適度に階調性を維持した階調情報を復元できる。

画像復元部８０５は、復号化部８０２から出力された識別情報の“０”の領域については、復号化部８０４から出力された階調情報をそのまま出力する。また、画像復元部８０５は、復号化部８０２から出力された識別情報（判定情報）の“１”の領域については、復号化部８０４から出力された階調情報に、復号化部８０３から出力された平均差分値（Ｄ）を加算し、出力する。

例えば、画像復元部８０５への入力が、図２に示される４×４画素ブロックの識別情報（判定情報）、図１の平均差分値生成部２０６の動作例を示した際に算出された平均差分値“１７０”、図８に示される４×４画素ブロックの階調情報であるとする。この場合、画像復元部８０５は、識別情報の“１”の領域に対応する上記階調情報に平均差分値“１７０”を加算することになるので、画像復元部８０５から出力される１ブロックの画像データは、図９に示される４×４の多値画像が復元される。

以上説明したように本実施形態によれば、図１５に示すような画像ブロックを入力したとしても、非可逆符号化処理では図６に示されるように、ほとんどエッジのない４×４画素の階調情報となる。このため、階調情報符号化時のエントローピーが大幅に減少し、符号化効率が大幅に向上することになる。

一方識別情報）と平均差分値（Ｄ）は可逆符号化されるため、文字や線画、自然画像が混在した多値画像でも画質劣化が起こりにくい。

さらに、抽出画素の階調性は階調情報によってほぼ復元されるため、グラデーション文字のように１つのレベルに収まらない文字と自然画像が混在した多値画像でも画質劣化が検知されにくい。

なお、上記実施形態では、分離部８０１は、着目ブロックの符号化データが、ブロックデータ１８０２のタイプであると判定した場合、ダミーの識別情報の符号化データ（パターンデータ）を復号化部８０２に出力し、ダミーの平均差分値の符号化データ（パターンデータ）を復号化部８０３に出力した。しかしながら、これによって本発明が限定されるものではない。例えば、次のようにしてもかまわない。

分離部８０１はブロックヘッダを解析して、着目ブロックの符号化データがブロックデータ１８０１、１８０２のいずれであるかを判定し、その判定結果を示す信号を画像復元部８０５に出力する。また、分離部８０１は、着目ブロックの符号化データがブロックデータ１８０２のタイプであると判断した場合には、ブロックヘッダに後続する階調情報の符号化データのみを復号化部８０４に出力する。画像復元部８０５は、着目ブロックがブロックデータ１８０１のタイプであることを示す信号を入力した場合には、上記処理を行なう。一方、着目ブロックがブロックデータ１８０２のタイプであることを示す信号を入力した場合には、復号化部８０４からの復号結果のみを選択し、出力する。以上のようにしても、上記実施形態と同様の結果を得ることができる。

また、上記実施形態では識別情報が“１”の画素を抽出画素としたが、識別情報が“０”の画素を抽出画素としても良い。この場合、置換画素も識別情報が“０”の画素となり、平均差分値（Ｄ）の絶対値が所定値以下の場合の識別情報は全て１にクリアすることになる。また、平均差分値を０としても置換処理は実質的には動作しなくなるので、識別情報を全て“１”にクリアする代わりに平均差分値（Ｄ）を０にクリアするようにしても良い。

また、上記実施形態では１ブロックを４×４画素サイズとした。しかしながら、符号化部２１１がＪＰＥＧ符号化処理を行なうのであれば、８×８サイズか、その整数倍であることが望ましい。実施形態で示した４×４のサイズは、簡単に説明するための一例であることに注意されたい。

また、本発明は文字部分とその他の部分を分離する場合に特に限定されない。本発明は、ある領域内にブロック内に高い値のグループと低い値のグループが存在し、これらを符号化する状況において、適宜用いることが可能である。

＜第１の実施形態の変形例＞
上記第１の実施形態をコンピュータプログラムによって実現しても構わない。その例を以下に説明する。

図１９は本変形例で適用する情報処理装置（パーソナルコンピュータ等）のブロック構成図である。

図中、１９０１は装置全体の制御を司るＣＰＵであり、１９０２はブートプログラム及びＢＩＯＳを記憶しているＲＯＭである。１９０３はＣＰＵ１９０１のワークエリアとして使用するＲＡＭである。１９０４はハードディスク等の大容量の外部記憶装置であり、ここにＯＳ（オペレーティングシステム）や、本変形例のアプリケーションプログラムをはじめ、各種データファイルが格納されている。１９０５はキーボード、１９０６はポインティングデバイスであるマウスである。１９０７は表示制御部であり、内部にはビデオメモリ、当該ビデオメモリへの描画処理とビデオメモリからの画像を映像信号として外部に出力するコントローラで構成される。１９０８は表示制御部１９０７からの映像信号を入力し表示する表示装置（ＣＲＴや液晶表示装置等）である。１９０９はネットワークインタ、１９１０はスキャナインタフェース、１９１１はイメージスキャナである。

上記構成において、本装置の電源がＯＮになると、ＣＰＵ１９０１はＲＯＭ１９０２のブートプログラムに従って、外部記憶装置１９０４からＯＳをＲＡＭ１９０３にロードすることで、本装置が情報処理装置として機能するようになる。この後、キーボード１９０５やマウス１９０６によって、本変形例のアプリケーションの起動が指示されると、ＣＰＵ１９０１は外部記憶装置１９０４から該当するアプリケーションをＲＡＭ１９０３にロードし、実行する。これにより、本装置が画像処理装置として機能するようになる。

以下は、このアプリケーションが起動した後のＣＰＵ１９０１が実行する処理手順を示している。なお、ここでは、イメージスキャナ１９１１から原稿画像を読み取り、それを圧縮符号化して外部記憶装置１９０４にファイルとして保存する例を説明する。

また、アプリケーションが実行されると、ＲＡＭ１９０３には、イメージスキャナ１９１１で読取った画像データを一時的に記憶するバッファ、及び、各種変数を格納するエリアが確保されるものとする。また、ここでも説明を簡単なものとするため、イメージスキャナ１９１１には、モノクロ多値モード（１画素８ビットとする）で原稿を読取るように設定するものとする。イメージスキャナ１９１１で読取った画像データは輝度値となる。これは上記第１の実施形態の濃度に対してちょうど逆の意味になり、二値化する際の０、１も逆の意味になる点に注意されたい。すなわち、輝度、濃度の違いは本質的な差とはならない。なぜなら、本発明では、文字・線画の画素と、非文字・線画とが分離できれば良いからである。

図２０は、本変形例のアプリケーションの画像符号化処理手順を示すフローチャートである。以下の説明において、イメージスキャナ１９１１で読取った画像データはＲＡＭ１９０３内の入力バッファに格納されるものとして説明する。また、外部記憶装置１９０４に書き出すファイルのヘッダ情報は既に生成しているものとして説明する。

まず、ステップＳ１では、入力バッファより１ブロック分の画像データを読取る。１ブロックのサイズは、本変形例の場合、８×８画素とする。入力した１ブロック分の画像データをＩＭ（ｉ，ｊ）として表現する（ｉ，ｊ＝０、１、２、…７）。

次いで、ステップＳ２において、入力した１ブロック内の各画素値を、予め設定された閾値ＴＨ０と比較し、２値化する。この２値化結果を、第１の実施形態と同様、識別情報と呼び、Ｂ（ｉ，ｊ）で表わす。

ステップＳ３では、Ｂ（ｉ，ｊ）＝１となっている画素値ＩＭ（ｉ，ｊ）の総和を算出し、その平均値ＡＶＥ１を算出する。演算式を示せば次式で表わすことができる。
ＡＶＥ１＝｛ΣＢ（ｉ，ｊ）×ＩＭ（ｉ，ｊ）｝／ΣＢ（ｉ，ｊ）
ここでΣは、ｉ，ｊ＝０、１、…７の合算関数である。また、ΣＢ（ｉ，ｊ）＝０の場合、ＡＶＥ＝０とする。

このステップＳ３の処理は、ちょうど、図３の“１”領域平均値生成部４０１の処理に相当するのは明らかであろう。

ステップＳ４では、Ｂ（ｉ，ｊ）＝０となっている画素値ＩＭ（ｉ，ｊ）の総和を算出し、その平均値ＡＶＥ２を算出する。
ＡＶＥ２＝｛Σ（１−Ｂ（ｉ，ｊ））×ＩＭ（ｉ，ｊ）｝／Σ（１−Ｂ（ｉ，ｊ））
で算出できる。また、Σ（１−Ｂ（ｉ，ｊ））＝０の場合、ＡＶＥ２＝０とする。

このステップＳ４の処理は、ちょうど、図３の“０”領域平均値生成部４０１の処理に相当するのは明らかであろう。

ステップＳ５では、ＡＶＥ１からＡＶＥ２を減じることで、差分値Ｄを求める。つまり、図３の減算器４０３の処理に相当する。

ステップＳ６では、差分値Ｄの絶対値が予め設定された閾値ＴＨ１以下であるか否かを判断する。このステップＳ６の判断がＹｅｓの場合、着目ブロックに存在するすべての画素値は、ほぼ等しい値と持つことになる。そこで、着目ブロックについては、ステップＳ７に進んで、ＪＰＥＧ符号化（非可逆符号化）を行なう。つまり、着目ブロックの符号化データは、図１８のブロック符号化データ１８０２となる。

一方、ステップＳ６の判定がＮｏの場合、すなわち、差分値Ｄの絶対値が閾値を超えると判断した場合、処理はステップＳ８に進み、Ｂ（ｉ，ｊ）＝１となった画素値から、差分値Ｄを減じることで、置換処理を行なう。置換後処理後の階調画素値をＴ（ｉ，ｊ）で表わすと、次の通りとなる。
・Ｂ（ｉ，ｊ）＝１の場合、Ｔ（ｉ，ｊ）＝ＩＭ（ｉ，ｊ）−Ｄ
ただし、Ｔ（ｉ，ｊ）＜０の場合には、Ｔ（ｉ，ｊ）＝０とする。
・Ｂ（ｉ，ｊ）＝０の場合、Ｔ（ｉ，ｊ）＝ＩＭ（ｉ，ｊ）

ステップＳ９では、置換処理で得られた階調画素値Ｔ（ｉ，ｊ）をＪＰＥＧ符号化（非可逆符号化）する。

次いで、ステップＳ１０では、２値識別情報Ｂ（ｉ，ｊ）を可逆符号化し、ステップＳ１１で差分値Ｄについても可逆符号化する。

この後、ステップＳ１２に進み、生成された符号化データをファイルの一部として出力する。因に、ステップＳ８乃至Ｓ１１の処理を経た場合の着目ブロックの符号化データは、図１８のブロック符号化データ１８０１の形式になる。

この後、ステップＳ１３にて、全ブロックについての符号化処理が完了したか否か判断し、否の場合にはステップＳ１以降の処理を繰り返すことになる。

以上の結果、第１の実施形態と同様な符号化データを生成することが可能になる。

次に、本変形例の復号処理手順を図２１のフローチャートに従って説明する。復号対象の符号化データファイルは、適当なＧＵＩ画面を表示装置１９０８に表示し、ユーザがマウス１９０６を操作して選択するものとする。

まず、ステップＳ２１では、選択したファイルから１ブロックの符号化データを入力する。そして、ステップＳ２２にて、ブロックヘッダを解析し、図１８のブロック１８０１、１８０２のいずれの形式のデータであるかを判断する。

入力した符号化データが、ブロックデータ１８０２の形式、すなわち、階調情報の符号化データのみで構成されると判断した場合には、ステップＳ２３に進んで、ＪＰＥＧ復号処理を行なう。

一方、入力した符号化データが、ブロックデータ１８０１の形式、すなわち、識別情報の符号化データ、差分値の符号化データ、及び、階調情報の符号化データで構成されると判断した場合には、ステップＳ２４に進む。

ステップＳ２４では２値識別情報Ｂ（ｉ，ｊ）を復号し、ステップＳ２５では差分値Ｄを復号する。そして、ステップＳ２６では階調情報Ｔ（ｉ，ｊ）を復号する。この後、ステップＳ２７にて逆置換処理を行なう。この逆置換処理後の画像データをＩＭ’（ｉ，ｊ）とするなら、次の通りである。
・Ｂ（ｉ，ｊ）＝１の場合、ＩＭ’（ｉ，ｊ）＝Ｔ（ｉ，ｊ）＋Ｄ
・Ｂ（ｉ，ｊ）＝０の場合、ＩＭ’（ｉ，ｊ）＝Ｔ（ｉ，ｊ）

ステップＳ２８では、ステップＳ２３又はステップＳ２７で復号して得られた１ブロック分の画像データを出力する。出力先が表示装置であれば、表示制御部１９０７に出力すればよいし、復号画像データをファイルとして保存するのであれば外部記憶装置１９０４で良い。

この後、ステップＳ２９に進み、全ブロック分の復号処理が完了したか否かを判断し、否の場合にはステップＳ２１以降の処理を繰り返す。

以上説明したように本変形例の如く、コンピュータプログラムによっても先に説明した第１の実施形態と同様の作用効果を奏することができる。

＜第２の実施形態＞
本第２の実施形態は、上述した第１の実施形態から更なる効果を得るために機能を追加するものである。

図１０に、第２の実施形態における符号化装置のブロック構成図を示す。

図１０の構成は、第１の実施形態である図１の構成に対し、ローパスフィルタ部１１０１を加えた点が異なり、それ以外は同じである。

第１の実施形態では、図１のセレクタ２０８の出力値、つまり階調情報を符号化部２１１がダイレクトに符号化した。これに対し、第２の実施形態では図１０で示されるように、セレクタ２０８の出力値、つまり階調情報の高周波成分をローパスフィルタ部１１０１を用いて抑制する。そして、符号化部２１１は、このローパスフィルタ処理後の高周波成分が抑制された画像データ（階調情報）を符号化する。ローパスフィルタ処理（以下、ＬＰＦと記す）を行うことのメリットは、ノイズ成分を除去するだけでなく、抽出画素（識別情報が“１”となる画素）と、非抽出画素の境界も滑らかになるため、更なる圧縮効率の向上が期待できる。また、上述したように、先の平均差分値（Ｄ）を用いた減算処理によって、ブロック内のエッジは既に抽出されて殆どなくなっているのでローパスフィルタをかけたとしても復元した画像のエッジは損なわれない。逆に、入力時に損なわれているエッジは、抽出（置換）処理後の階調情報にエッジとなって残るので、このローパスフィルタ処理により、損なわれたエッジが除去され、復元時に急峻なエッジとなる効果もある。

以下、エッジが改善される具体的な例を示して説明する。

図１１（Ａ）乃至（Ｆ）は第２の実施形態の動作を示す波形の例である。

図１１（Ａ）は入力波形で、ここでは８×１の１次元のブロックであるとする。この波形（ブロック）を所定の閾値（ここではブロック平均値）にて領域分割し、同図（Ｂ）に示すように識別情報が抽出される。この識別情報を用いて領域毎の平均値を求め（同図（Ｃ））、平均差分値が得られる。

この平均差分値を入力波形（図１１（Ａ）の“１”領域（識別情報が“１”となる画素）から減じて、図１１（Ｄ）の階調情報が得られる。なお、このとき、減算した結果が負となる場合は、上述したように０にクリップする。この階調情報にＬＰＦをかけ、圧縮伸長した結果、図１１（Ｅ）に示す波形が得られる。この波形（同図（Ｅ））の“１”領域（識別情報が“１”となる画素）に平均差分値を加算することで、元の波形（ブロック）が図１１（Ｆ）のように復元される。図１１（Ｆ）の矢印で示したように、“１”領域の境界部のエッジが急峻になっていることがわかる。

以上説明したように本第２の実施形態によれば、第１の実施形態（及びその変形例）の作用効果に加えて、ノイズ成分を除去と、復元時に急峻なエッジとすることが可能になる。

なお、本第２の実施形態に対応する処理を、コンピュータプログラムでもって実現できることは明らかである。

また、上記第１及び第２の実施形態では、識別情報が“１”となっている画素群を抽出対象とし、識別情報が“０”となっている画素群を非抽出対象とした。そして、抽出対象画素群に含まれる各画素の値から差分平均値を減じた。しかし、この逆でも構わない。すなわち、識別情報が“０”の画素群を抽出対象とし、その画素群に含まれる各画素の値に差分平均値を加算しても良い。この場合、平均差分の加算により、入力画素の取り得る範囲を超えた場合に上限値（境界値）にクリップすることになる。要するに、抽出対象画素群と非抽出画素群それぞれの平均値が小さくなるように、差分平均値を加算又は減算しても、構わない。

＜第３の実施形態＞
第１の実施形態では、置換色を生成する際、ブロック内の各多値画像データから平均差分値を減算し、もしその結果が負であれば置換色を”０”（下限値）にクリップして出力している。これは符号化部２１１がＪＰＥＧエンコーダのような正の値を入力としなければならない場合に対しての最も単純で効果的な対策である。これは置換色にクリップされた画素があったとしてもその数が少なく、クリップ幅が小さいものであれば、復元後の画質には大きく影響することはないことに基づいている（参考例：図１１）。

しかし、ごく稀だが入力画像によっては、または抽出部２０４での識別情報を生成するために使用した閾値によっては、復元後の画質劣化に影響してしましまう場合がある。以下、図２２を用いて具体的な例を示して説明する。図２２（Ａ）は入力波形で、ここでは８×１画素の１次元のブロックであるとする。この波形（ブロック）を所定の閾値にて領域分解することで、識別情報が生成される（同図（Ｂ））。そして識別情報を用いて領域毎の平均値を求め（同図（Ｃ））、得られた平均差分値を”１”領域の画素データから減算する。閾値や入力波形によっては、その減算結果が負となる場合がある。通常は第１の実施形態で説明したように画素値を”０”へクリップしたとしても、画質に大きく影響をすることはない。しかし、同図（Ｄ）に示すように、負となる画素が多い、もしくはそれが連続してしまう可能性もある。この場合、圧縮・伸張後（同図（Ｅ））に平均差分を加算し、復元した出力波形（図（Ｆ））に示すように入力波形（図（Ａ））で階調があった部分が失われてしまう。

本第３の実施形態は、このような問題点を解消するために機能を追加するものである。

図２３に第３の実施形態における符号化装置のブロック構成図を示す。

図２３の構成は、第１の実施形態である図１の構成に対し、置換色生成部２０７の代わりとして置換色生成部２３０１を備える点、及び、置換色生成部２３０２、比較部２３０３及びセレクタ２３０４を追加した点が異なる。それ以外の部分については前記第１の実施形態と同様である。

置換色生成部２３０１は、第１の実施形態で説明した図１の置換色生成部２０７に、後述する第１のカウント手段として機能するクリップカウンタを更に備えるものである。上記クリップカウンタは、識別情報が”１”で、且つ、バッファ２０３から出力されたブロック内の各多値画像の画素データから平均差分値（Ｄ）を減算した結果が負の場合にインクリメントされる。上記置換色生成部２３０１は、上記置換色生成部２０７と同じ手法にて置換色（ａ）を出力し、またクリップカウンタの値をクリップカウント値（ａ）として出力する。そして参照ブロックの上記置換色（ａ）及びクリップカウント値（ａ）が出力された後、上記クリップカウンタは”０”クリアされる。

上記クリップカウント値（ａ）はブロック内の識別情報が”１”に対応する置換色の画素のうち、”０”（下限値）にクリップされた画素の数を表している。

セレクタ２０８は、入力される識別情報（判定情報）が”０”の時は、識別情報の位置に対応する入力多値画像の画素データを選択し、出力する。一方、識別情報が”１”の時は、セレクタ部２０８は、識別情報の位置に対応する置換色生成部２３０２にて出力された置換色（ａ）の画素データを選択し、出力する。以上の処理をブロック終端画素まで繰り返すことで、着目ブロックの階調情報（ａ）が得られる。

置換色生成部２３０１とセレクタ２０８の具体的な動作を図２４に示される４×４画素ブロックの多値画素データが入力されたものとして説明する。

図示の場合、ブロック平均値は“７６”となるので、識別情報は図２５に示されるようになる。また、図２４、図２５より平均差分値（Ｄ）は”２００”となる。

置換色生成部２３０１では、ブロック内のすべての画素データから平均差分値”２００”を減算する。置換色生成部２３０１は、第１の実施形態で説明した置換色生成部２０７と同じように、減算された値が負の場合には、置換色の値を０にクリップして出力する。その時の識別情報が抽出画素を示す”１”であれば、クリップカウンタをインクリメントする。本動作例で、これに該当する画素は２箇所あるので、クリップカウンタは”２”を示す。この結果、置換色生成部２３０１は、４×４の画素データを図２６に示される置換色（ａ）として出力し、また、クリップカウンタの値”２”をクリップカウント値（ａ）として出力する。

セレクタ２０８では、図２６で示される置換色（ａ）の画素のうち、図２５に示される識別情報の”１”に対応する画素、及び、図２４で示される多値画像の画素のうち、上記識別情報が”０”に対応する画素を選択し、出力する。この結果、セレクタ２０８は、図２７に示される階調情報（ａ）を出力する。図示に示すように、文字・線画として判定された位置の画素値は、非文字・線画の画素値とほぼ同じ値になる。

置換色生成部２３０２は、バッファ２０３から出力されたブロック内の各多値画像の画素データから、平均差分値生成部２０６から出力された平均差分値（Ｄ）を加算する。そして、その結果は置換色（ｂ）として出力される。ただし、加算結果が画素データの取り得る範囲を超えた場合には、上限値（境界値）にクリップする。

また、置換色生成部２３０２は、上記置換色生成部２３０１と同じように第２のカウント手段として機能するクリップカウンタを備える。ただし、上記置換色生成部２３０２のクリップカウンタは上記置換色生成部２３０１のクリップカウンタとは異なる。すなわち、置換色生成部２３０２のクリップカウンタは、識別情報が”０”で、且つ、バッファ２０３から出力されたブロック内の各多値画像の画素データに平均差分値（Ｄ）を加算した結果が画素データの取り得る範囲の上限値（境界値）を超えた場合にインクリメントされる。上記クリップカウンタの値はクリップカウント値（ｂ）として出力される。そして参照ブロックの上記置換色（ｂ）及び、クリップカウント値（ｂ）が出力された後、上記クリップカウンタは”０”クリアされる。

上記クリップカウント値（ｂ）はブロック内の識別情報が”０”の置換色の中で、上限値（境界値）にクリップされた画素の数を表している。

セレクタ２３０４はセレクタ２０８と同じ機能を持つ。ただし、識別情報（判定情報）は反転して上記セレクタ２３０４へ入力されるので、識別情報（判定情報）が”１”の時は識別情報の位置に対応する入力多値画像の画素データを選択し、出力する。一方、識別情報が”０”の時は、セレクタ２３０４は、識別情報の位置に対応する置換色生成部２３０２にて出力された置換色（ｂ）の画素データを選択し、出力する。以上の処理をブロック終端画素まで繰り返すことで、着目ブロックの階調情報（ｂ）が得られる。

以上のように、セレクタ２０８は第１の置換部、セレクタ２３０４は第２の置換部として機能することになる。

置換色生成部２３０２とセレクタ２３０５の具体的な動作を図２４に示される４×４画素ブロックの多値画素データが入力されたものとして説明する。

この時、ブロック平均値は“７７”となるので、識別情報は図２５に示されるようになる。また、図２４、図２５より平均差分値（Ｄ）は”２００”となる。ただし、置換色生成部２３０２には反転された識別情報が入力されるので、識別情報の”１”の画素が非抽出画素、”０”が抽出画素となる。

置換色生成部２３０２では、ブロック内のすべての画素データに平均差分値”２００”を加算する。置換色生成部２３０２は加算された値が上限値（ここでは２５５）の時、置換色の値を”２５５”にクリップして出力する。その時の識別情報が抽出画素を示す”０”であれば、クリップカウンタをインクリメントする。本動作例では、これに該当する画素はなく、クリップカウンタは”０”を示す。この結果、置換色生成部２３０２は、図２８に示される４×４の画素データを置換色（ｂ）として出力し、また、クリップカウンタの値”０”をクリップカウント値（ｂ）として出力する。

セレクタ２３０４では図２８で示される置換色（ｂ）の画素のうち、図２５に示される識別情報の”０”に対応する画素、及び、図２４で示される多値画像の画素のうち、上記識別情報が”１”に対応する画素を選択し、出力する。この結果、セレクタ２３０２から出力される階調情報（ｂ）は図２９に示されるようになる。図示に示すように、非文字・線画として判定された位置の画素値は、文字・線画の画素値とほぼ同じ値になる。

比較部２３０３は１ブロックの処理画終了した時点で上記置換色生成部２３０１から出力されたクリップカウント値（ａ）と、上記置換色生成部２３０２から出力されたクリップカウント値（ｂ）を比較する。そして、比較部２３０３はクリップカウント値（ａ）がクリップカウント値（ｂ）と同じ、もしくは小さい場合は”０”を、それ以外は”１”を、判定信号ＳＥＬとして出力する。

そして、セレクタ２３０５は、図示していないブロックバッファを有し、上記比較部２３０３の判定信号に同期して上記ＳＥＬ信号が”０”の時はセレクタ２０８から入力された階調情報（ａ）を選択し、出力する。一方、セレクタ２３０５は、上記ＳＥＬ信号が”１”の時はセレクタ２３０４から入力された階調情報（ｂ）を選択し、出力する。つまり、セレクタ２３０５では、クリップした画素数の少ない方の階調情報を選択するのである。

セレクタ２３０５から出力された上記階調情報は、符号化部２１１にて、第１の実施形態と同様の圧縮方法で圧縮（非可逆符号化）される。また、抽出部２０４から出力される識別情報と平均差分値生成部２０６から出力される平均差分値は、それぞれ、符号化部２０９、符号化部２１０にて、第１の実施形態と同様の圧縮方法で圧縮（可逆符号化）される。

多重化部２３０６は、上記符号化部２０９、符号化部２１０、符号化部２１１で圧縮された符号化データと、上記符号化部２１１で符号化された階調情報のタイプ（階調情報（ａ）または階調情報（ｂ））を複合部に知らせるための上記ＳＥＬ信号（選択情報）を後段のメモリに格納しやすいように結合し、それを出力端子２５２より出力する。

なお、上記ＳＥＬ信号の代わりに平均差分値にサインビットを追加し、上記ＳＥＬ信号が”１”のときに上記平均差分値を負の値としてメモリに格納するようにしても良い。この場合、復号時には上記ＳＥＬ信号によって復号方法を切り替えるのではなく、識別情報が”１”となっている画素に上記平均差分値を加算することで、画像の復元ができる。なお、上記場合においては、必ずしも、
識別情報“１”の画素値＞識別情報”０”の画素値
となるとは限らないことに注意されたい（上記平均差分値を負の場合は上記関係が逆になる）。

以上、説明したように本第３の実施形態によれば、置換操作によるクリップの発生が殆どなくなるので、階調つぶれのない画像を復元することができる。

なお、本第３の実施形態に対応する処理を、コンピュータプログラムでもって実現できることは明らかである。

また、第３の実施形態に第２の実施形態で示したローパスフィルタを適用しても同様の効果が得られることは言うまでもない。

＜第４の実施形態＞
第３の実施形態においては差分値の識別（選択）信号が必要であった。本第４の実施形態では差分値の設定を工夫する（領域１の最小値が負にならないようにする）ことにより、上記識別（選択）信号なしに前記置換後の画素値が負になってしまう問題点を解消する。

図３０に第４の実施形態における符号化装置のブロック構成図を示す。

図３０の第４の実施形態の構成は、第１の実施形態である図１の構成に対し、平均差分値置換部２３０１を追加した点が異なり、それ以外の部分については前記第１の実施形態と同様である。以下、前記第１の実施形態と異なる部分のみ説明する。

平均差分値置換部２３０１は、バッファ２０３から出力されたブロック内の、抽出部２０４から出力された識別情報の”１”に対応する画素の最小値と、平均差分値生成部２０６から出力された差分値とを比較し、いずれか小さい方の値を選択し、出力する。以下、この平均差分値置換部２３０１で選択出力する値を補正値という。

以下、上記平均差分値置換部２３０１の詳細を説明する。

図３１は上記平均差分値置換部２３０１のブロック構成図である。

最小値検出部２４０１は、バッファ２０３から出力されたブロック内の各多値画像の画素データを入力し、抽出部２０４から出力された識別情報の”１”に対応する上記画素データの最小値を出力する。そして比較部２４０２では、上記最小値と平均差分値生成部２０６から出力された差分値とを比較して、上記差分値が上記最小値よりも小さい場合は”０”を、それ以外の場合には”１”を、選択信号として出力する。そして、選択部２４０３は上記選択信号に基づき、上記多値画像の最小画素値と上記差分値のいずれか小さい方を選択し、その選択した値を補正値として出力する。

次に平均差分値置換部２３０１の動作を説明する。入力される多値画像が図２４で示される４×４画素ブロックの画素データとした場合、差分値（Ｄ）は“２００”、識別情報は図２５で示されるようになる。

この時、上記識別情報が“１”に対応する画素データの最小値は“１０４”であり、上記最小値と、差分値（Ｄ）とを比較すると上記最小値の方が小さい。従って、平均差分値置換部２３０１は、比較結果の小さい上記最小値“１０４”を補正値として出力する。

これ以降は、第１の実施形態と同様に処理する。但し、置換色生成部２０７は、上記バッファ２０３から出力されたブロック内の各多値画像の画素データから、上記平均差分値生成部２０６から出力された置換値を減算する。このとき、減算した結果が負となっても構わない。なぜなら、負となった場合、セレクタ２０８はその値を選択しないからである。

図３２は第４の実施形態の効果を説明する図である。

図３２（Ａ）は入力波形で、ここでは８×１の１次元のブロックであるとする。この波形（ブロック）を閾値（例えばブロック平均値）にて領域分解され識別情報が生成される（同図（Ｂ））。そして識別情報を用いて領域毎の平均値を求めて（同図（Ｃ））、得られた仮平均差分値と、”１”領域の最小値となる画素データとを比較して、値が小さい方を平均差分値として（同図（Ｄ））、上記入力波形から減算する。減算結果は、同図（Ｅ）に示すように、負となる画素が存在しない。そのため、圧縮・伸張後（同図（Ｆ））に平均差分を加算し、復元した出力波形（図（Ｇ））のように、階調性が失われてしまうことがない。

以上の説明では、識別情報の”１”の画素値から補正値を減じる例を説明したが、識別情報が“０”の画素値に補正値を加算するようにしても構わない。後者の場合、平均差分値置換部２３０１は、バッファ２０３から出力されたブロック内の、抽出部２０４から出力された識別情報の“０”に対応する画素の最大画素値を求める。そして、平均差分値置換部２３０１は、その最大画素値と画素値の取り得る上限値（実施形態では“２５５”）の差分と、平均差分値生成部２０６から出力された平均差分値とを比較し、いずれか小さい方を、補正値として出力する。置換色生成部２０７は、上記バッファ２０３から出力されたブロック内の各多値画像の画素データに、上記平均差分値生成部２０６から出力された置換値を加算する。このとき、加算した値が上限値を超えても構わない。なぜなら、上限値を超えた場合、セレクタ２０８はその値を選択しないからである。

以上、説明したように本第４の実施形態によれば、置換操作によるクリップが発生しないので、階調つぶれのない画像を復元することができる。

なお、本第４の実施形態に対応する処理を、コンピュータプログラムでもって実現できることは明らかである。

また、第４の実施形態に第２の実施形態で示したローパスフィルタを適用しても同様の効果が得られることは言うまでもない。

なお、上記各実施形態では説明を容易にするためブロックのサイズを４×４（または８×１）で説明していたが、通常は階調情報を圧縮する符号化（例えば直交変換のサイズ）に合わせるほうが望ましい。例えば、ＪＰＥＧを用いる場合は、ＤＣＴのブロックサイズ（８×８）の整数倍が良い。例えば、８×１６画素を１ブロックとするなら、このブロックには８×８画素が２つ存在することになる。従って、符号化部２１１はＤＣＴ変換、量子化、エントロピー符号化処理を２つの８×８画素ブロックに対して行なえば良い。

また、第１の実施形態の変形例の如く、本発明はコンピュータプログラムによっても実現できる。通常、コンピュータプログラムは、ＣＤ−ＲＯＭ等のコンピュータ可読記憶媒体に格納されている。そして、その媒体を、コンピュータの読取り装置（ＣＤ−ＲＯＭドライブ等）にセットし、システムにコピーもしくはインストールすることで、実行可能になる。従って、かかるコンピュータ可読記憶媒体も本発明の範疇に入るのは明らかである。

第１の実施形態における符号化装置のブロック構成図である。 第１の実施形態における閾値ＴＨ０を“２００”とした場合の、４×４画素ブロックの識別情報を示す図である。 図１の平均差分値生成部のブロック構成図である。 図３の“１”領域平均値生成部のブロック構成図である。 図１の置換色生成部の出力値例を示す図である。 図１のセレクタの出力例を示す図である。 第１の実施形態における画像復元装置のブロック構成図である。 図７の画像復元部に入力される４×４画素ブロックの階調情報の例を示す図である。 図７の画像復元装置で復元された４×４画素ブロックの画素データの例を示す図である。 第２の実施形態における符号化装置のブロック構成図である。 第２の実施形態の動作を説明するための波形例である。 従来技術における符号化対象の画素ブロックの例を示す図である。 図１２の従来技術における識別情報を示す図である。 従来技術における画素置換後の階調情報の例を示す図である。 実施形態における符号化対象の画素ブロックの例を示す図である。 従来技術の問題点を説明するための図である。 従来技術の問題点を説明するための図である。 実施形態における符号化装置で生成される符号化データのデータ構造を示す図である。 第１の実施形態の変形例における装置のブロック構成図である。 図１９の装置の符号化処理手順を示すフローチャートである。 図１９の装置の復号処理手順を示すフローチャートである。 置換処理による不具合を説明するための図である。 第３の実施形態における符号化装置のブロック図である。 図２３の置換色生成部に入力される４×４画素ブロックの画素データの例を示す図である。 図２３の置換色生成部に入力される４×４画素ブロックの識別情報の例を示す図である。 図２３の第１の置換色生成部から出力される４×４画素ブロックの置換色の例を示す図である。 図２３の第１のセレクタから出力される４×４画素ブロックの階調情報の例を示す図である。 図２３の第２の置換色生成部から出力される４×４画素ブロックの置換色の例を示す図である。 図２３の第２のセレクタから出力される４×４画素ブロックの階調情報の例を示す図である。 第４の実施形態における符号化装置のブロック図である。 図３０の平均差分値置換部の例を示すブロック図である。 第４の実施形態における符号化装置の効果を示す図である。

Claims (20)

1. 多値画像データを、複数の画素で構成されるブロック単位に入力する入力手段と、
   前記入力したブロック内の各画素を、該各画素の値に応じて第１及び第２のグループに分類すると共に、各画素がいずれのグループに属するかを識別する識別情報を生成する識別情報生成手段と、
   前記第１のグループに属する画素の値の平均値、前記第２のグループに属する画素の値の平均値、及び、該２つの平均値の差分値を算出する算出手段と、
   前記第１のグループの平均値と前記第２のグループの平均値との差が小さくなるように、前記第１のグループに属する各画素の値に前記差分値を加算、又は前記第１のグループに属する各画素の値から前記差分値を減算することにより、前記第１のグループに属する画素の値を置換する置換手段と、
   置換後のブロック内の各画素の値と、前記差分値と、前記識別情報とを符号化し、着目ブロックの符号化データを出力する符号化手段と
   を備えることを特徴とする画像符号化装置。
2. 前記置換手段は、置換後の着目画素の値が、当該画素の取り得る範囲の上限値を上回る場合には前記上限値、前記画素の取り得る範囲の下限値を下回る場合には前記下限値に設定することを特徴とする請求項１に記載の画像符号化装置。
3. 更に、前記置換手段で置換したブロックに対し、ローパスフィルタ処理を実行するローパスフィルタ処理手段を備え、
   前記符号化手段は、前記ローパスフィルタ処理後のブロック内の画素値を符号化することを特徴とする請求項１又は２に記載の画像符号化装置。
4. 前記符号化手段は、前記差分値、及び、前記識別情報については可逆符号化することを特徴とする請求項１乃至３のいずれか１項に記載の画像符号化装置。
5. 前記符号化手段は、前記置換手段で置換した後のブロック内の各画素の値を、非可逆符号化することを特徴とする請求項４に記載の画像符号化装置。
6. 前記入力手段の入力単位のブロックのサイズが、前記符号化手段で非可逆符号化するブロックのサイズの整数倍であることを特徴とする請求項５に記載の画像符号化装置。
7. 更に、前記算出手段で算出される差分値の絶対値が、予め設定された閾値以下であるか否かを判断する判断手段と、
   該判断手段で前記差分値の絶対値が前記閾値以下であると判断した場合、前記置換手段による置換を行なわず、前記符号化手段に代わって、前記入力手段で入力したブロック内の画素を符号化し出力する第２の符号化手段とを備えることを特徴とする請求項１乃至６のいずれか１項に記載の画像符号化装置。
8. コンピュータが読み込み実行することで、前記コンピュータを、請求項１乃至７のいずれか１項に記載の画像符号化装置の各手段として機能させることを特徴とするコンピュータプログラム。
9. 請求項８に記載のコンピュータプログラムを格納したことを特徴とするコンピュータ可読記憶媒体。
10. 画像符号化装置の制御方法であって、
    入力手段が、多値画像データを、複数の画素で構成されるブロック単位に入力する入力工程と、
    識別情報生成手段が、前記入力したブロック内の各画素を、該各画素の値に応じて第１及び第２のグループに分類すると共に、各画素がいずれのグループに属するかを識別する識別情報を生成する識別情報生成工程と、
    算出手段が、前記第１のグループに属する画素の値の平均値、前記第２のグループに属する画素の値の平均値、及び、該２つの平均値の差分値を算出する算出工程と、
    置換手段が、前記第１のグループの平均値と前記第２のグループの平均値との差が小さくなるように、前記第１のグループに属する各画素の値に前記差分値を加算、又は前記第１のグループに属する各画素の値から前記差分値を減算することにより、前記第１のグループに属する画素の値を置換する置換工程と、
    符号化手段が、置換後のブロック内の各画素の値と、前記差分値と、前記識別情報とを符号化し、着目ブロックの符号化データを出力する符号化工程と
    を有することを特徴とする画像符号化装置の制御方法。
11. 多値画像データを複数の画素で構成されるブロック単位に入力する入力手段と、
    前記入力したブロック内の各画素を、該各画素の値に応じて第１及び第２のグループに分類すると共に、各画素がいずれのグループに属するかを識別する識別情報を生成する識別情報生成手段と、
    前記第１のグループに属する画素の値の平均値、前記第２のグループに属する画素の値の平均値、及び、該２つの平均値の差分値を算出する算出手段と、
    前記第１のグループの平均値と前記第２のグループの平均値との差が小さくなるように、前記第１のグループに属する各画素の値に前記差分値を加算し、前記第１のグループに属する各画素の値を置換したブロックを生成する第１の置換手段と、
    前記第２のグループに属する各画素の値から前記差分値を減算し、前記第２のグループに属する各画素の値を置換したブロックを生成する第２の置換手段と、
    前記第１の置換手段から出力されたブロックと前記第２の置換手段から出力されたブロックのいずれかを選択する選択手段と、
    前記選択手段で選択されたブロック内に含まれる各画素の値と、前記差分値と、前記識別情報と、前記選択手段がいずれのブロックを選択したのかを示す選択情報とを符号化し、着目ブロックの符号化データを出力する符号化手段と
    を備えることを特徴とする画像符号化装置。
12. 前記第１の置換手段、前記第２の置換手段それぞれは、置換後の着目画素の値が当該画素の取り得る範囲の上限値を上回る場合には前記上限値、置換後の着目画素の値が当該画素の取り得る範囲の下限値を下回る場合には前記下限値を、置換後の画素値として設定することを特徴とする請求項１１に記載の画像符号化装置。
13. 前記選択手段は、
    前記着目ブロックの前記第１のグループに属する各画素の値を置換した後の画素の値が当該画素の取り得る範囲を超える画素数をカウントする第１のカウント手段と、
    前記着目ブロックの前記第２のグループに属する各画素の値を置換した後の画素の値が当該画素の取り得る範囲を超える画素数をカウントする第２のカウント手段とを有し、
    前記第１のカウント手段によるカウントした値が、前記第２のカウント手段によるカウントした値と等しいか、小さい場合には、前記第１の置換手段から出力されたブロックを選択し、それ以外の場合には、前記第２の置換手段から出力されたブロックを選択する
    ことを特徴とする請求項１２に記載の画像符号化装置。
14. 画像符号化装置の制御方法であって、
    入力手段が、多値画像データを複数の画素で構成されるブロック単位に入力する入力工程と、
    識別情報生成手段が、前記入力したブロック内の各画素を、該各画素の値に応じて第１及び第２のグループに分類すると共に、各画素がいずれのグループに属するかを識別する識別情報を生成する識別情報生成工程と、
    算出手段が、前記第１のグループに属する画素の値の平均値、前記第２のグループに属する画素の値の平均値、及び、該２つの平均値の差分値を算出する算出工程と、
    第１の置換手段が、前記第１のグループの平均値と前記第２のグループの平均値との差が小さくなるように、前記第１のグループに属する各画素の値に前記差分値を加算し、前記第１のグループに属する各画素の値を置換したブロックを生成する第１の置換工程と、
    第２の置換手段が、前記第２のグループに属する各画素の値から前記差分値を減算し、前記第２のグループに属する各画素の値を置換したブロックを生成する第２の置換工程と、
    選択手段が、前記第１の置換工程で出力されたブロックと前記第２の置換工程で出力されたブロックのいずれかを選択する選択工程と、
    符号化手段が、前記選択工程で選択されたブロック内に含まれる各画素の値と、前記差分値と、前記識別情報と、前記選択工程でいずれのブロックを選択したのかを示す選択情報とを符号化し、着目ブロックの符号化データを出力する符号化工程と
    を有することを特徴とする画像符号化装置の制御方法。
15. 多値画像データを、複数の画素で構成されるブロック単位に入力する入力手段と、
    前記入力したブロック内の各画素を、該各画素の値に応じて、
    第１のグループに属する画素の値 ＞ 第２のグループに属する画素の値
    となるように分類し、各画素がいずれのグループに属するかを識別する識別情報を生成する識別情報生成手段と、
    前記第１のグループに属する画素の値の平均値、前記第２のグループに属する画素の値の平均値、及び、該２つの平均値の差分値を算出する算出手段と、
    前記差分値と、前記第１のグループに属する画素の最小画素値とを比較し、小さい方を補正値として出力する比較手段と、
    前記第１のグループの平均値と前記第２のグループの平均値との差が小さくなるように、前記第１のグループに属する各画素の値から、前記比較手段によって得られた前記補正値を減算し、前記第１のグループに属する画素の値を置換したブロックを生成する置換手段と、
    置換後のブロック内の各画素の値と、前記補正値と、前記識別情報とを符号化し、着目ブロックの符号化データを出力する符号化手段と
    を備えることを特徴とする画像符号化装置。
16. 画像符号化装置の制御方法であって、
    入力手段が、多値画像データを、複数の画素で構成されるブロック単位に入力する入力工程と、
    識別情報生成手段が、前記入力したブロック内の各画素を、該各画素の値に応じて、
    第１のグループに属する画素の値 ＞ 第２のグループに属する画素の値
    となるように分類し、各画素がいずれのグループに属するかを識別する識別情報を生成する識別情報生成工程と、
    算出手段が、前記第１のグループに属する画素の値の平均値、前記第２のグループに属する画素の値の平均値、及び、該２つの平均値の差分値を算出する算出工程と、
    比較手段が、前記差分値と、前記第１のグループに属する画素の最小画素値とを比較し、小さい方を補正値として出力する比較工程と、
    置換手段が、前記第１のグループの平均値と前記第２のグループの平均値との差が小さくなるように、前記第１のグループに属する各画素の値から、前記比較工程によって得られた前記補正値を減算し、前記第１のグループに属する画素の値を置換したブロックを生成する置換工程と、
    符号化手段が、置換後のブロック内の各画素の値と、前記補正値と、前記識別情報とを符号化し、着目ブロックの符号化データを出力する符号化工程と
    を有することを特徴とする画像符号化装置の制御方法。
17. 多値画像データを、複数の画素で構成されるブロック単位に入力する入力手段と、
    前記入力したブロック内の各画素を、該各画素の値に応じて、
    第１のグループに属する画素の値 ＞ 第２のグループに属する画素の値
    となるように分類し、各画素がいずれのグループに属するかを識別する識別情報を生成する識別情報生成手段と、
    前記第１のグループに属する画素の値の平均値、前記第２のグループに属する画素の値の平均値、及び、該２つの平均値の差分値を算出する算出手段と、
    前記差分値と、前記第２のグループに属する画素の最大画素値と画素値の取り得る上限値との差分値とを比較し、小さい方を補正値として出力する比較手段と、
    前記第１のグループの平均値と前記第２のグループの平均値との差が小さくなるように、前記第２のグループに属する各画素の値に、前記比較手段によって得られた前記補正値を加算し、前記第２のグループに属する画素の値を置換したブロックを生成する置換手段と、
    置換後のブロック内の各画素の値と、前記補正値と、前記識別情報とを符号化し、着目ブロックの符号化データを出力する符号化手段と
    を備えることを特徴とする画像符号化装置。
18. コンピュータが読み込み実行することで、前記コンピュータを、請求項１１乃至１３、１５、１７のいずれか１項に記載の画像符号化装置の各手段として機能させることを特徴とするコンピュータプログラム。
19. 請求項１８に記載のコンピュータプログラムを格納したことを特徴とするコンピュータ可読記憶媒体。
20. 画像符号化装置の制御方法であって、
    入力手段が、多値画像データを、複数の画素で構成されるブロック単位に入力する入力工程と、
    識別情報生成手段が、前記入力したブロック内の各画素を、該各画素の値に応じて、
    第１のグループに属する画素の値 ＞ 第２のグループに属する画素の値
    となるように分類し、各画素がいずれのグループに属するかを識別する識別情報を生成する識別情報生成工程と、
    算出手段が、前記第１のグループに属する画素の値の平均値、前記第２のグループに属する画素の値の平均値、及び、該２つの平均値の差分値を算出する算出工程と、
    比較手段が、前記差分値と、前記第２のグループに属する画素の最大画素値と画素値の取り得る上限値との差分値とを比較し、小さい方を補正値として出力する比較工程と、
    置換手段が、前記第１のグループの平均値と前記第２のグループの平均値との差が小さくなるように、前記第２のグループに属する各画素の値に、前記比較工程で得られた前記補正値を加算し、前記第２のグループに属する画素の値を置換したブロックを生成する置換工程と、
    符号化手段が、置換後のブロック内の各画素の値と、前記補正値と、前記識別情報とを符号化し、着目ブロックの符号化データを出力する符号化工程と
    を有することを特徴とする画像符号化装置の制御方法。

Images