(57)【要約】【課題】画像データの圧縮（色分け）を高速化することあるいは画像データを圧縮（色分け）するための画像処理装置を低廉化する。【解決手段】画像処理装置ＭＦＰは、複数の画素の各々を識別するための識別情報に対応付けて画素の色データを記憶し、所定の個数のバスケットの各々について参照値と統計値とを記憶するためのメモリ１０２と、複数の画素の各々を、対応する色データと参照値とに基づいて、所定の個数のバスケットのいずれか１つに分類する分類手段１００３と、複数の画素の各々に対応する色データに基づいて、複数の画素の各々が分類されたバスケットの統計値と参照値とを更新する更新手段１００４と、統計値に基づいてバスケット毎の代表色を決定し、バスケット毎の代表色と画素毎の分類結果とを出力する決定手段１００５とを備える。【選択図】図３
2011018970.tif 000002
【特許請求の範囲】
【請求項１】
複数の画素を所定の個数のバスケットに分類することによって、画像データを色分けする画像処理装置であって、
前記複数の画素の各々を識別するための識別情報に対応付けて前記画素の色データを記憶し、前記所定の個数のバスケットの各々について参照値と統計値とを記憶するためのメモリと、
前記複数の画素の各々を、対応する前記色データと前記参照値とに基づいて、前記所定の個数のバスケットのいずれか１つに分類する分類手段と、
前記複数の画素の各々に対応する前記色データに基づいて、前記複数の画素の各々が分類されたバスケットの統計値と参照値とを更新する更新手段と、
前記統計値に基づいて前記バスケット毎の代表色を決定し、前記バスケット毎の代表色と前記画素毎の分類結果とを出力する決定手段とを備える、画像処理装置。
【請求項２】
前記分類手段は、
前記複数の画素の各々について、前記色データがいずれかのバスケットの参照値に基づいて当該バスケットに分類されるべきか否かを判断する第１の判断部と、
前記色データがすべてのバスケットに分類されない場合に、未だ参照値が対応付けられていない前記バスケットが存在するか否かを判断する第２の判断部と、
全てのバスケットに参照値が対応付けられている場合に、参照値同士の距離と、参照値と色データとの距離とを計算する計算手段と、
前記距離のうち最も小さい距離が参照値同士の距離である場合、当該距離に対応する２つのバスケットを結合する結合手段とを含み、
前記分類手段は、
前記色データがいずれかのバスケットに分類されるべきときに、対象となる画素を当該参照値に対応する前記バスケットに分類し、
未だ参照値が対応付けられていないバスケットが存在する場合に、対象となる画素を当該バスケットに分類し、
前記距離のうち最も小さい距離が参照値と色データとの距離である場合、当該距離に対応するバスケットに対象となる画素を分類する、請求項１に記載の画像処理装置。
【請求項３】
前記画像データは、複数の画素からなる複数のブロックを含み、
前記メモリは、前記ブロック毎に前記所定の個数のバスケットに関する一時情報を記憶し、
前記分類手段は、対応する前記一時情報に基づいて前記複数のブロックを貫くラインに沿って順次画素を分類する、請求項１または２に記載の画像処理装置。
【請求項４】
前記メモリは、前記分類手段が前記画像データを構成する第２のブロック内の第１のラインの画素を分類している間、前記画像データを構成する第１のブロック内の前記第１のラインに関する前記一時情報を記憶する、請求項３に記載の画像処理装置。
【請求項５】
前記メモリは、前記一時情報として、前記識別情報に対応付けて分類先のバスケットを記憶するとともに、前記所定の個数のバスケットの各々について参照値と統計値とを記憶する、請求項４に記載の画像処理装置。
【請求項６】
前記メモリは、前記一時情報として、前記複数の画素の各々を識別するための識別情報に対応付けて分類先のバスケットを記憶するとともに、前記所定の個数のバスケットの各々について統計値を記憶し、
前記分類手段は、前記第１のブロック内の第２のラインの画素の分類を行なう際に、前記統計値に基づいて、前記所定の個数のバスケットの各々について参照値を計算する、請求項４に記載の画像処理装置。
【請求項７】
前記メモリは、前記一時情報として、前記複数の画素の各々を識別するための識別情報に対応付けて分類先のバスケットを記憶し、前記所定の個数のバスケットの各々について参照値を記憶し、
前記分類手段は、前記第１のブロック内の第２のラインの画素の分類を行なう際に、前記参照値に基づいて、前記所定の個数のバスケットの各々について統計値を計算する、請求項４に記載の画像処理装置。
【請求項８】
前記所定の個数のバスケットの各々に関する参照値は、前記バスケットに分類された画素の色データの最大値および最小値を含む、請求項１から７のいずれかに記載の画像処理装置。
【請求項９】
前記所定の個数のバスケットの各々に関する統計値は、前記バスケットに分類された画素の色データの累計値を含む、請求項１から８のいずれかに記載の画像処理装置。
【請求項１０】
前記所定の個数のバスケットの各々に関する統計値は、前記バスケットに分類された画素の色データの平均値を含む、請求項１から９のいずれかに記載の画像処理装置。
【請求項１１】
前記所定の個数のバスケットの各々に関する統計値は、前記バスケットに分類された画素の色データの最大値および最小値を含む、請求項１から７のいずれかに記載の画像処理装置。
【請求項１２】
前記記憶部は、前記バスケット毎の代表色と前記画素毎の分類結果とを記憶する、請求項１から１１のいずれかに記載の画像処理装置。
【請求項１３】
前記バスケット毎の代表色と前記画素毎の分類結果とに基づいて画像を再生する再生部をさらに備える、請求項１から１２のいずれかに記載の画像処理装置。
【請求項１４】
請求項１から１３のいずれかに記載の画像処理装置と、
前記画像処理装置からの前記バスケット毎の代表色と前記画素毎の分類結果とを記憶する画像記録装置とを備える、画像処理システム。
【請求項１５】
請求項１から１３のいずれかに記載の画像処理装置と、
前記画像処理装置からの前記バスケット毎の代表色と前記画素毎の分類結果とに基づいて画像を再生する画像再生装置を備える、画像処理システム。
【請求項１６】
請求項１から１３のいずれかに記載の画像処理装置と、
前記画像処理装置からの前記バスケット毎の代表色と前記画素毎の分類結果とを記憶する画像記録装置と、
前記画像処理装置からの前記バスケット毎の代表色と前記画素毎の分類結果とに基づいて画像を再生する画像再生装置とを備える、画像処理システム。
【請求項１７】
メモリと演算処理部とを含む画像処理装置における画像処理方法であって、
前記演算処理部が、前記メモリに、前記複数の画素の各々を識別するための識別情報に対応付けて前記画素の色データを格納するステップと、
前記演算処理部が、前記メモリに、前記所定の個数のバスケットの各々について参照値と統計値とを格納するステップと、
前記演算処理部が、前記複数の画素の各々を、対応する前記色データと前記参照値とに基づいて、前記所定の個数のバスケットのいずれか１つに分類するステップと、
前記演算処理部が、前記複数の画素の各々に対応する前記色データに基づいて、前記複数の画素の各々が分類されたバスケットの統計値と参照値とを更新するステップと、
前記演算処理部が、前記統計値に基づいて前記バスケット毎の代表色を決定するステップと、
前記演算処理部が、前記バスケット毎の代表色と前記画素毎の分類結果とを出力するステップとを備える、画像処理方法。
【請求項１８】
メモリと演算処理部とを含む画像処理装置に画像処理させるための画像処理プログラムであって、前記演算処理部に、
前記メモリに、前記複数の画素の各々を識別するための識別情報に対応付けて前記画素の色データを格納するステップと、
前記メモリに、前記所定の個数のバスケットの各々について参照値と統計値とを格納するステップと、
前記複数の画素の各々を、対応する前記色データと前記参照値とに基づいて、前記所定の個数のバスケットのいずれか１つに分類するステップと、
前記複数の画素の各々に対応する前記色データに基づいて、前記複数の画素の各々が分類されたバスケットの統計値と参照値とを更新するステップと、
前記統計値に基づいて前記バスケット毎の代表色を決定するステップと、
前記バスケット毎の代表色と前記画素毎の分類結果とを出力するステップとを実行させる、画像処理プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は画像処理装置、画像処理システム、画像処理方法、および画像処理プログラムに関し、特に、画像データを圧縮するための画像処理装置、画像処理システム、画像処理方法、および画像処理プログラムに関する。
【背景技術】
【０００２】
画像データを圧縮するための技術が知られている。当該技術の一例として、ＢＴＣ（Block  Truncation  Coding）圧縮方法が挙げられる。
【０００３】
さらに、たとえば、特許第２８６１３７９号明細書（特許文献１）、特許第２８６１３８０号明細書（特許文献２）、特許第２８６１３８１号明細書（特許文献３）には、画像データの符号化回路が開示されている。特許第２８６１３７９号明細書（特許文献１）、特許第２８６１３８０号明細書（特許文献２）、特許第２８６１３８１号明細書（特許文献３）によると、画像データの符号化回路は、付加コードとして、画素データの中央値と上位ビットを除去した１／２のダイナミックレンジのデータとを伝送することにより、伝送しなければならない付加コードのビット数を減らす。
【０００４】
また、特許第２８７４００３号明細書（特許文献４）には、ブロック符号化で発生した付加データのデータ量を圧縮するようにした高能率符号化装置が開示されている。特許第２８７４００３号明細書（特許文献４）によると、高能率符号化装置は、入力ディジタル画像データをブロック化するブロック化回路と、ブロック毎のダイナミックレンジに適応してブロック内の画素データを符号化するブロック符号化回路と、ブロック符号化回路で使用されるブロック毎の付加コードの最大値を所定数のブロックにわたって検出する検出回路と、検出回路の出力に基づいて所定数のブロックの期間の付加コードに割り当てるビット数を決定する決定回路と、決定回路の出力に基づいて付加コードのビット数を変更する変更回路とを有する。ブロック符号化回路の出力と変更回路からの付加コード及び決定回路からのビット数識別コードを伝送することにより、付加コードのデータ量を圧縮できる。
【０００５】
また、特許第３１０６７４１号明細書（特許文献５）には、適応ダイナミックレンジ符号化又は復号化装置が開示されている。特許第３１０６７４１号明細書（特許文献５）によると、入力信号をブロックに分割し、このブロック毎の信号の最大値と最小値との差を示すダイナミックレンジに応じてブロック内の信号に対して適応量子化を行い、または、この適応量子化された情報を復号して元の入力信号を得る。
【０００６】
さらに、特開平１０−４０３６４号公報（特許文献６）には、カラー画像生成方法が開示されている。特開平１０−４０３６４号公報（特許文献６）によると、画像処理装置は、画像読み取り装置を介して入力されたフルカラー画像を、その初期代表色Ｎ個を用いて、その画像を表現するための色空間に箱を作成し、カラー画像の現れる各色をその箱に入れる。初期代表色以外の色は新しい箱として作成し、常に箱がＮ個となるように箱同士の体積が最小になるように箱をマージする。最終的に作成されたＮ個の重心を代表色として、近似画像を生成し、画像出力装置に出力する。
【先行技術文献】
【特許文献】
【０００７】
【特許文献１】特許第２８６１３７９号明細書
【特許文献２】特許第２８６１３８０号明細書
【特許文献３】特許第２８６１３８１号明細書
【特許文献４】特許第２８７４００３号明細書
【特許文献５】特許第３１０６７４１号明細書
【特許文献６】特開平１０−４０３６４号公報
【発明の概要】
【発明が解決しようとする課題】
【０００８】
しかしながら、ＢＴＣ圧縮においては、ブロック内の色をブロック内の画素数ｍより小さいｎ色に色分け分類し、ｎ色の色情報（代表値）と各画素がどの色（代表値）に対応するかの情報とを記録することによって、画像を圧縮する。そのため、ブロック内のデータ全体を走査することによって色分けのための基準を決める必要がある。そして、分類された画素値から、代表値を求める必要がある。したがって、従来技術では色分け処理をハードウェアに実装するためには、少なくとも色分け処理が終了してグループ毎の代表値が算出までブロック内の画像データ全体をハードウェア内に保持している必要が生じる。これによって、画像処理の速度も遅くなってしまう。
【０００９】
ブロック内の画像データを保持するためには、画像処理装置がブロックを含む画像データをバンド単位で保存するためのラインメモリを含む必要があった。しかし、バンド単位で画像データを保持することができるメモリは容量が大きく高価である。そして、圧縮率向上のためにブロックサイズを大きくすればするほど、要求されるラインメモリのサイズも大きくなってしまう。
【００１０】
本発明は上記の問題点を解決するためになされたものであって、本発明の主たる目的は、画像データの圧縮（色分け）を高速化することあるいは画像データを圧縮（色分け）するための画像処理装置を低廉化することである。
【課題を解決するための手段】
【００１１】
この発明のある局面に従うと、複数の画素を所定の個数のバスケットに分類することによって、画像データを色分けする画像処理装置が提供される。画像処理装置は、複数の画素の各々を識別するための識別情報に対応付けて画素の色データを記憶し、所定の個数のバスケットの各々について参照値と統計値とを記憶するためのメモリと、複数の画素の各々を、対応する色データと参照値とに基づいて、所定の個数のバスケットのいずれか１つに分類する分類手段と、複数の画素の各々に対応する色データに基づいて、複数の画素の各々が分類されたバスケットの統計値と参照値とを更新する更新手段と、統計値に基づいてバスケット毎の代表色を決定し、バスケット毎の代表色と画素毎の分類結果とを出力する決定手段とを備える。
【００１２】
好ましくは、分類手段は、複数の画素の各々について、色データがいずれかのバスケットの参照値に基づいて当該バスケットに分類されるべきか否かを判断する第１の判断部と、色データがすべてのバスケットに分類されない場合に、未だ参照値が対応付けられていないバスケットが存在するか否かを判断する第２の判断部と、全てのバスケットに参照値が対応付けられている場合に、参照値同士の距離と、参照値と色データとの距離とを計算する計算手段と、距離のうち最も小さい距離が参照値同士の距離である場合、当該距離に対応する２つのバスケットを結合する結合手段とを含む。分類手段は、色データがいずれかのバスケットに分類されるべきときに、対象となる画素を当該参照値に対応するバスケットに分類し、未だ参照値が対応付けられていないバスケットが存在する場合に、対象となる画素を当該バスケットに分類し、距離のうち最も小さい距離が参照値と色データとの距離である場合、当該距離に対応するバスケットに対象となる画素を分類する。
【００１３】
好ましくは、画像データは、複数の画素からなる複数のブロックを含む。メモリは、ブロック毎に所定の個数のバスケットに関する一時情報を記憶する。分類手段は、対応する一時情報に基づいて複数のブロックを貫くラインに沿って順次画素を分類する。
【００１４】
好ましくは、メモリは、分類手段が画像データを構成する第２のブロック内の第１のラインの画素を分類している間、画像データを構成する第１のブロック内の第１のラインに関する一時情報を記憶する。
【００１５】
好ましくは、メモリは、一時情報として、識別情報に対応付けて分類先のバスケットを記憶するとともに、所定の個数のバスケットの各々について参照値と統計値とを記憶する。
【００１６】
好ましくは、メモリは、一時情報として、複数の画素の各々を識別するための識別情報に対応付けて分類先のバスケットを記憶するとともに、所定の個数のバスケットの各々について統計値を記憶する。分類手段は、第１のブロック内の第２のラインの画素の分類を行う際に、統計値に基づいて、所定の個数のバスケットの各々について参照値を計算する。
【００１７】
好ましくは、メモリは、一時情報として、複数の画素の各々を識別するための識別情報に対応付けて分類先のバスケットを記憶し、所定の個数のバスケットの各々について参照値を記憶する。分類手段は、第１のブロック内の第２のラインの画素の分類を行う際に、参照値に基づいて、所定の個数のバスケットの各々について統計値を計算する。
【００１８】
好ましくは、所定の個数のバスケットの各々に関する参照値は、バスケットに分類された画素の色データの最大値および最小値を含む。
【００１９】
好ましくは、所定の個数のバスケットの各々に関する統計値は、バスケットに分類された画素の色データの累計を含む。
【００２０】
好ましくは、所定の個数のバスケットの各々に関する統計値は、バスケットに分類された画素の色データの平均値を含む。
【００２１】
好ましくは、所定の個数のバスケットの各々に関する統計値は、バスケットに分類された画素の色データの最大値および最小値を含む。
【００２２】
好ましくは、記憶部は、バスケット毎の代表色と画素毎の分類結果とを記憶する。
好ましくは、バスケット毎の代表色と画素毎の分類結果とに基づいて画像を再生する再生部をさらに備える。
【００２３】
この発明の別の局面に従うと、上記の画像処理装置と、画像処理装置からのバスケット毎の代表色と画素毎の分類結果とを記憶する画像記録装置とを備える、画像処理システムが提供される。
【００２４】
この発明の別の局面に従うと、上記の画像処理装置と、画像処理装置からのバスケット毎の代表色と画素毎の分類結果とに基づいて画像を再生する画像再生装置を備える、画像処理システムが提供される。
【００２５】
この発明の別の局面に従うと、上記の画像処理装置と、画像処理装置からのバスケット毎の代表色と画素毎の分類結果とを記憶する画像記録装置と、画像処理装置からのバスケット毎の代表色と画素毎の分類結果とに基づいて画像を再生する画像再生装置とを備える、画像処理システムが提供される。
【００２６】
この発明の別の局面に従うと、メモリと演算処理部とを含む画像処理装置における画像処理方法が提供される。画像処理方法は、演算処理部が、メモリに、複数の画素の各々を識別するための識別情報に対応付けて画素の色データを格納するステップと、演算処理部が、メモリに、所定の個数のバスケットの各々について参照値と統計値とを格納するステップと、演算処理部が、複数の画素の各々を、対応する色データと参照値とに基づいて、所定の個数のバスケットのいずれか１つに分類するステップと、演算処理部が、複数の画素の各々に対応する色データに基づいて、複数の画素の各々が分類されたバスケットの統計値と参照値とを更新するステップと、演算処理部が、統計値に基づいてバスケット毎の代表色を決定するステップと、演算処理部が、バスケット毎の代表色と画素毎の分類結果とを出力するステップとを備える。
【００２７】
この発明の別の局面に従うと、メモリと演算処理部とを含む画像処理装置に画像処理させるための画像処理プログラムが提供される。画像処理プログラムは、演算処理部に、メモリに、複数の画素の各々を識別するための識別情報に対応付けて画素の色データを格納するステップと、メモリに、所定の個数のバスケットの各々について参照値と統計値とを格納するステップと、複数の画素の各々を、対応する色データと参照値とに基づいて、所定の個数のバスケットのいずれか１つに分類するステップと、複数の画素の各々に対応する色データに基づいて、複数の画素の各々が分類されたバスケットの統計値と参照値とを更新するステップと、統計値に基づいてバスケット毎の代表色を決定するステップと、バスケット毎の代表色と画素毎の分類結果とを出力するステップとを実行させる。
【発明の効果】
【００２８】
以上のように、この発明によれば、画像データの圧縮を高速化することあるいは画像処理装置を低廉化することができる画像処理装置、画像処理システム、画像処理方法、および画像処理プログラムが提供される。
【図面の簡単な説明】
【００２９】
【図１】本実施の形態に係る画像処理装置の動作概要を示す概念図である。
【図２】本実施の形態に係る画像処理装置のハードウェア構成を示す模式図である。
【図３】本実施の形態に係る画像処理装置の機能構成を示すブロック図である。
【図４】本実施の形態に係る画像処理装置における画像圧縮処理の処理手順を示すフローチャートである。
【図５】本実施の形態に係る画像処理装置における画像振り分け処理の処理手順を示すフローチャートである。
【図６】本実施の形態に係る画像処理装置ＭＦＰにおける出力処理の処理手順を示すフローチャートである。
【図７】本実施の形態に係る画像圧縮処理における画像データの流れを示す概念図である。
【図８】本実施の形態に係るＣＭＹＫの出力フォーマットを示す概念図である。
【図９】本実施の形態に係るＲＧＢの出力フォーマットを示す概念図である。
【図１０】ＢＴＣアルゴリズムを示す第１の概念図である。
【図１１】ＢＴＣアルゴリズムを示す第２の概念図である。
【図１２】ＡＢＴＣアルゴリズムを示す概念図である。
【図１３】その他のアルゴリズムを示す概念図である。
【図１４】画像処理装置を含む画像処理システムを示す概略図である。
【発明を実施するための形態】
【００３０】
以下に、図面を参照しつつ、本発明の実施の形態について説明する。以下の説明では、同一の部品および構成要素には同一の符号を付してある。それらの名称および機能も同じである。
【００３１】
本実施の形態においては、本発明にかかる画像処理装置として代表的に、複写機能やスキャン機能やＦＡＸ送信機能などを統合したＭＦＰ（Multi Function Peripheral）について説明する。まず、以下では、本実施の形態に係る画像処理装置ＭＦＰの動作概要について説明する。
【００３２】
＜動作概要＞
図１は、本実施の形態に係る画像処理装置ＭＦＰの動作概要を示す概念図である。図１を参照して、画像処理装置ＭＦＰは、バスケット方式（ボックス方式）に基づいて画像データを圧縮する。画像処理装置ＭＦＰは、色分けされたバスケット（ボックス）を用意する。換言すれば、画像処理装置ＭＦＰは、色の属性地が付与されたバスケットを用意する。画像処理装置ＭＦＰは、画像を構成する複数の画素の各々がどのバスケットに入るか判断することによって、複数の画素の各々をバスケットに振り分ける。
【００３３】
なお、図１は、画像処理装置ＭＦＰが、画像を構成する複数の画素の各々を６色に色分けする例を示す。換言すれば、図１は、画像処理装置ＭＦＰが、複数の画素の各々を６種類のバスケットに振り分ける例を示す。
【００３４】
より詳細には、画像処理装置ＭＦＰは、バスケット毎に代表色や色空間を設定する。画像処理装置ＭＦＰは、画像を構成する複数の画素の各々をいずれかのバスケットに割り振ったり、近い色を有するバスケットをまとめて新たな１つのバスケットを生成（ボックスのマージ処理に相当）したりする。画像処理装置ＭＦＰは、画素の振り分けとバスケットの生成とを繰り返すことによって、画素を色分けする。
【００３５】
特に、本実施の形態に係る画像処理装置ＭＦＰは、複数の画素の各々をバスケットに振り分ける際に、すなわち各画素がどのバスケットに入るかを示す情報を記録する際に、その後の画素を振り分けるために参照する情報と、バスケットに振り分けられた画素の強度の累計を示す情報とを順次に記録する。これによって、画像データを圧縮する際の、画像データへのアクセス回数を低減することができる。
【００３６】
換言すれば、画像データを構成する複数の画素を取得する順序で当該複数の画素の振り分け処理が完了するので、１ブロック分や１バンド分の画像データを全て保持しておく必要が無い。すなわち、中間データ（一時情報）として、バスケット毎に振り分けられた画素データに関する値（参照値や統計値など）のみを保持することによって画像データを圧縮することができる。
【００３７】
以下、このような機能を実現するための構成について詳述する。なお、説明のために、本実施の形態に係る画像データは、６４（８×８）のブロックから構成される。本実施の形態に係る各ブロックは、６４（８×８）の画素から構成されるものとする。本実施の形態に係る画像処理装置ＭＦＰは、ブロックを構成する６４個の画素を６つのバスケットに振り分ける。
【００３８】
＜画像処理装置ＭＦＰのハードウェア構成＞
図２は、本実施の形態に係る画像処理装置ＭＦＰのハードウェア構成を示す模式図である。
【００３９】
図２を参照して、画像処理装置ＭＦＰは、ＣＰＵ（Central Processing Unit）１００と、メモリ１０２と、時計ＩＣ（Integrated Circuit）１０８とを含む。これらの部位は、バス１２４を介して互いに接続される。なお、メモリ１０２は、ＲＯＭ（Read Only Memory）や、Ｓ−ＲＡＭ（Static-Random Access Memory）や、ＮＶ−ＲＡＭ（Non-Volatile Random Access Memory）や、ＨＤＤ（Hard Disk Drive）などによって構成される。
【００４０】
ＣＰＵ１００は、メモリ１０２の不揮発性メモリを構成するＲＯＭやＨＤＤなどに予め格納されたプログラムを、同じくメモリ１０２の作業用メモリを構成するＳ−ＲＡＭに読み出して実行することにより、本実施の形態に係る画像処理を実現する。なお、ＨＤＤなどによって構成されるメモリ１０２は、比較的大容量のデータを不揮発的に格納することができ、後述する通信インターフェイス１２２がサーバ装置ＳＲＶから受信した画像データや、後述するスキャナ１１２が画像を読み取ることによって取得した画像データなどを複数格納することができる。時計ＩＣ１０８は、水晶発振器などを含んで構成され、現在時刻を計測する。
【００４１】
さらに、画像処理装置ＭＦＰは、スキャナ１１２と、操作パネル１１４と、プリンタ１１６と、プリンタコントローラ１１８と、出力処理部１２０とを含む。
【００４２】
スキャナ１１２は、スキャナ機能を実現するための部位であり、原稿を読取って画像データを生成する。スキャナ１１２は、概して、原稿をセットするための載置台と、原稿台ガラスと、載置台にセットされた原稿を原稿台ガラスに自動的に一枚ずつ搬送する搬送部と、読取られた原稿を排出するための排出台とを含む（いずれも図示しない）。
【００４３】
プリンタ１１６は、画像データに基づいて、紙媒体等への画像のプリント処理を行う。プリンタ１１６は、露光器や現像ローラ等からなる作像ユニット、作像ユニットで形成されたトナー像を紙媒体に転写する転写ローラ、転写されたトナー像を定着させる定着器、および各部の動作を制御する制御回路などを含む。
【００４４】
プリンタコントローラ１１８は、サーバ装置ＳＲＶやパーソナルコンピュータからの画像データや、ＢＯＸ内の画像データや、スキャナ１１２からの画像データを、プリンタ１１６でのプリント処理に適したプリントデータへと変換する。画像処理装置ＭＦＰがカラー方式であれば、プリンタコントローラ１１８は、画像データをイエロー（Ｙ）、マゼンタ（Ｍ）、シアン（Ｃ）、ブラック（Ｋ）の４色のラスターデータに変換し、各色のラスターデータをプリンタ１１６へ出力する。
【００４５】
出力処理部１２０は、プリンタ１１６で画像処理された後の紙媒体に対する処理を行う部位であり、代表的に「ソート処理」、「グループ処理」、「ステープル処理」、「パンチ処理」などを実行する。ここで、「ソート処理」とは、いわゆる部単位印刷を意味する。「グループ処理」とは、設定された複数部数の紙媒体がページ毎に出力される処理である。また、「ステープル処理」は、出力される紙媒体を綴じ針（ステープル）によって綴じる処理であり、「パンチ処理」は、出力される紙媒体に綴じ穴を形成する処理である。
【００４６】
さらに、画像処理装置ＭＦＰは、通信インターフェイス１２２を含む。通信インターフェイス１２２は、後述するネットワークＮＷを介してパーソナルコンピュータＰＣやサーバ装置ＳＲＶとの間で画像データなどを送受信するための部位である。
【００４７】
＜画像処理装置ＭＦＰの機能構成＞
次に、画像処理装置ＭＦＰの機能構成について詳述する。図３は、本実施の形態に係る画像処理装置ＭＦＰの機能構成を示すブロック図である。図３を参照して、画像処理装置ＭＦＰは、ライン切替部１００１と、画素切替部１００２と、分類部１００３と、更新部１００４と、決定部１００５と、メモリ１０２を含む。分類部１００３は、第１の判断部１００６と、第２の判断部１００７と、距離計算部１００８と、結合部１００９とを含む。
【００４８】
ライン切替部１００１と、画素切替部１００２と、分類部１００３と、更新部１００４と、決定部１００５と、第１の判断部１００６と、第２の判断部１００７と、距離計算部１００８と、結合部１００９とは、ＣＰＵ１００がＲＯＭやＨＤＤなどに予め格納されていたプログラムをＳ−ＲＡＭに読み出して実行することにより実現されるものである。すなわち、ライン切替部１００１と、画素切替部１００２と、分類部１００３と、更新部１００４と、決定部１００５と、第１の判断部１００６と、第２の判断部１００７と、距離計算部１００８と、結合部１００９とは、画像処理装置ＭＦＰのＣＰＵ１００が有する機能である。
【００４９】
以下、画像処理装置ＭＦＰが有する機能ブロックの各々について詳述する。まず、上述したように、メモリ１０２は、Ｓ−ＲＡＭやＨＤＤなどによって実現される。メモリ１０２は、画像データを構成する複数のブロック毎に、第１のバスケット情報１０４１、第２のバスケット情報１０４２、第３のバスケット情報１０４３と、第４のバスケット情報１０４４と、第５のバスケット情報１０４５と、第６のバスケット情報１０４６とを記憶する。
【００５０】
本実施の形態に係る画像処理装置ＭＦＰは、画像データを構成する複数のブロック（８×８ブロック）のうち、横１列分のブロック（８ブロック）を１バンドとして取り扱う。すなわち、メモリ１０２は、８ブロック分の第１のバスケット情報１０４１〜第６のバスケット情報１０４６を記憶する。第１のバスケット情報１０４１〜第６のバスケット情報の各々は、バスケットに画素を振り分けるための参照値と、バスケットの代表値を計算するための統計値と、バスケットに振り分けられる画素を特定するための識別情報とを含む。
【００５１】
本実施の形態においては、各バスケットの参照値は、対応する色空間（直方体）を特定するための対角点、すなわちバスケットに振り分けられた画素の強度あるいは輝度の最大値と最小値とを含む。あるいは、各バスケットの参照値は、対応する色空間（直方体）の中心点あるいは重心点を含む。各バスケットの統計値は、対応するバスケットに振り分けられた画素の強度あるいは輝度の累計を含む。以下では、画素毎の、複数色の強度あるいは輝度を示すデータを、まとめて色データあるいは画素データともいう。
【００５２】
ＣＰＵ１００は、ブロックを構成する画素の各々を第１のバスケットから第６のバスケットに振り分ける際に、メモリ１０２から対応の第１のバスケット情報１０４１〜第６のバスケット情報１０４６を読み出す。ＣＰＵ１００は、当該第１のバスケット情報１０４１〜第６のバスケット情報１０４６と対象となる画素データとに基づいて、対象となる画素を第１のバスケットから第６のバスケットのいずれかに振り分ける。
【００５３】
ライン切替部１００１は、画像データを受け付けて、１ライン分の画素データ（ラインデータ）を画素切替部１００２に入力する。ライン切替部１００１は、画素切替部１００２からのライン終了通知を受け付けて、次のラインデータを画素切替部１００２に入力する。ライン切替部１００１は、ブロック（バンド）の全ての画素データを分類部１００３に入力すると、決定部１００５にブロック（バンド）終了通知を送る。
【００５４】
画素切替部１００２は、ライン切替部１００１からラインデータを受け付けて、画素データを分類部１００３に入力する。画素切替部１００２は、更新部１００４からの画素終了通知を受け付ける度に、順次次の画素データを分類部１００３に入力する。画素切替部１００２は、ラインデータの全ての画素データを分類部１００３に入力すると、ライン切替部１００１にライン終了通知を送る。
【００５５】
分類部１００３の第１の判断部１００６は、対象となる画素データに含まれる画素の強度が、第１のバスケット情報１０４１〜第６のバスケット情報１０４６の参照値に含まれるか否かを判断する。あるいは、第１の判断部１００６は、画素データに含まれる画素の強度が、第１のバスケット情報１０４１〜第６のバスケット情報１０４６の参照値に一致するか否かを判断する。
【００５６】
分類部１００３の第２の判断部１００７は、対象となる画素データに含まれる画素の強度が、第１のバスケット情報１０４１〜第６のバスケット情報１０４６の参照値に含まれない場合、未だ参照値が設定されていないバスケットが存在するか否かを判断する。あるいは、第２の判断部１００７は、画素データに含まれる画素の強度が、第１のバスケット情報１０４１〜第６のバスケット情報１０４６の参照値に一致しない場合、未だ参照値が設定されていないバスケットが存在するか否かを判断する。
【００５７】
分類部１００３の距離計算部１００８は、対象となる画素データに含まれる画素の強度が第１のバスケット情報１０４１〜第６のバスケット情報１０４６の参照値に含まれず（あるいは画素データに含まれる画素の強度が第１のバスケット情報１０４１〜第６のバスケット情報１０４６の参照値に一致せず）、かつ、未だ参照値が設定されていないバスケットが存在しない場合、全てのバスケットに関する参照値同士の色空間における第１の距離を計算する。距離計算部１００８は、対象となる画素の強度と、全てのバスケットに関する参照値との色空間における第２の距離を計算する。
【００５８】
分類部１００３の結合部１００９は、第１の距離と第２の距離との中で、第１の距離が最も距離が短い場合、対応する参照値に対する２つのバスケットを結合して、新たな１つのバスケットを生成する。
【００５９】
分類部１００３は、対象となる画素データに含まれる画素の強度が、第１のバスケット情報１０４１〜第６のバスケット情報１０４６の参照値に含まれる場合、当該画素を当該参照値に対応するバスケットに振り分ける。あるいは、分類部１００３は、対象となる画素データに含まれる画素の強度が、第１のバスケット情報１０４１〜第６のバスケット情報１０４６の参照値に一致する場合、当該画素を当該参照値に対応するバスケットに振り分ける。
【００６０】
分類部１００３は、対象となる画素データに含まれる画素の強度が、第１のバスケット情報１０４１〜第６のバスケット情報１０４６の参照値に含まれない場合に、未だ参照値が設定されていないバスケットが存在するとき、対象となる画素を当該バスケットに振り分ける。あるいは、分類部１００３は、画素データに含まれる画素の強度が、第１のバスケット情報１０４１〜第６のバスケット情報１０４６の参照値に一致しない場合に、未だ参照値が設定されていないバスケットが存在するとき、対象となる画素を当該バスケットに振り分ける。
【００６１】
分類部１００３は、結合部１００９が、２つのバスケットを結合して新たな１つのバスケットを生成した際に、すなわち６つのバスケットが５つのバスケットに変化した際に、新たに未だ画素が振り分けられていないバスケットを生成する。すなわち、分類部１００３は、新たに６つ目のバスケットを生成して、対象となる画素を当該新たな６つ目のバスケットに振り分ける。一方、分類部１００３は、第１の距離と第２の距離との中で、第２の距離が最も距離が短い場合、対応する参照値に対応するバスケットに対象となる画素を振り分ける。
【００６２】
分類部１００３は、画素をバスケットへ分類すると、当該画素を特定するための識別情報と画素の強度と分類先のバスケットの番号とを更新部１００４に受け渡す。
【００６３】
更新部１００４は、分類部１００３から当該画素を特定するための識別情報と画素データと分類先のバスケットの番号とを受け付けて、画素の強度に基づいて分類先のバスケットに関する参照値と統計値とを更新する。更新部１００４は、分類先のバスケットの参照値と統計値とを更新すると、画素終了通知を画素切替部１００２に送る。
【００６４】
たとえば、更新部１００４は、画素データを構成する各色の強度に基づいて、画素が振り分けられたバスケットの各色の強度の最大値あるいは最小値を更新する。これによって、色空間における当該バスケットのサイズが大きくなる。更新部１００４は、画素データを構成する各色の強度に基づいて、画素が振り分けられたバスケットの各色の強度の累計を更新する。
【００６５】
決定部１００５は、ライン切替部１００１からブロック（バンド）終了通知を受け付けて、第１のバスケット情報１０４１〜第６のバスケット情報１０４６に基づいて、分類結果を他のアプリケーションや他の装置などに出力する。
【００６６】
たとえば、メモリ１０２あるいはＨＤＤ１１０が、決定部１００５として機能するＣＰＵ１００からの分類結果を格納する。また、ＣＰＵ１００が、分類結果に基づいて、ディスプレイ１３８に圧縮画像を表示させる。あるいは、ＣＰＵ１００が、分類結果に基づいて、プリンタ１１６に圧縮画像をプリントさせる。
【００６７】
なお、ここでは、参照値をバスケット毎の画素の強度の最大値と最小値とし、統計値をバスケット毎の画素の強度の累計としている。しかしながら、たとえば、参照値をバスケット毎の画素の強度の平均値とし、統計値をバスケット毎の画素の強度の最大値と最小値としてもよい。さらに、参照値をバスケット毎の画素の強度の最大値と最小値とし、統計値をバスケット毎の画素の強度の平均値としてもよい。
【００６８】
＜画像圧縮処理＞
以下では、主に図１〜図４を参照して、画像圧縮処理の処理手順について説明する。なお、図４は、本実施の形態に係る画像処理装置ＭＦＰにおける画像圧縮処理の処理手順を示すフローチャートである。
【００６９】
まず、ライン切替部１００１として機能するＣＰＵ１００は、対象となるブロック内の画素を振り分けるためのバスケットを準備する（ステップＳ１０２）。より詳細には、ＣＰＵ１００は、メモリ１０２の一時退避領域から、対象となるブロックのための第１のバスケット情報１０４１〜第６のバスケット情報１０４６（一時情報）を読み出して、メモリ１０２の作業領域に格納する。なお、メモリ１０２の一時退避領域とメモリ１０２の作業領域とは、異なる記憶装置によって実現されてもよいし、同一の記憶装置の異なるエリアによって実現されてもよい。
【００７０】
分類部１００３として機能するＣＰＵ１００は、対象となるブロックの対象となるラインの画素（８画素）に対して振り分け処理を実行する（ステップＳ２００）。振り分け処理（ステップＳ２００）については後述する。
【００７１】
ＣＰＵ１００は、対象となるブロックのうちの対象となるラインの８画素の振り分け処理が終了すると、メモリ１０２の作業領域から、次のラインに渡すデータ（対象となるブロックのための第１のバスケット情報１０４１〜第６のバスケット情報１０４６）を読み出して、当該データをメモリ１０２の一時退避領域に格納する（ステップＳ１０４）。
【００７２】
より詳細には、ステップＳ１０４は、次のブロックの処理を行うために一旦データを退避させるための処理である。メモリ１０２は、８画素の振り分け処理終了後、バスケット毎の「ＣＭＹＫの強度の最大値と最小値」、バスケット毎の「ＣＭＹＫの強度の累計」、バスケット毎の「バスケットに振り分けられた画素の数」、各画素が振り分けられたバスケットの番号（インデックス）を、次のラインの処理へと引き継ぐデータとして、次のラインの振り分け処理が開始されるまで保存する。
【００７３】
なお、メモリ１０２の使用領域を節約するためには、すなわちコストを下げるためには、保存すべきデータの量が少ないほうが望ましい。ＣＰＵ１００は、ステップＳ１０４において、各画素が振り分けられたバスケットの番号（インデックス）に関し、バスケット毎の「どの画素が入っているかを示すフラグ」（３８４ｂｉｔ＝６４ｂｉｔ（６４画素分のＯＮ／ＯＦＦ）×６バスケット）から、画素毎の「どのバスケットに入っているかを示すデータ」（１９２ｂｉｔ＝６４画素×３ｂｉｔ（バスケットの識別番号））に変換して保存する。そして、ＣＰＵ１００は、８画素の振り分け処理（ステップＳ２００）終了後は、次のブロックの振り分け処理へと移る。
【００７４】
つまり、ここでは、画素をｎ種類のバスケットに振り分けるために必要な情報が、「ＣＭＹＸの強度の最大値と最小値」である。統計情報は、バスケット毎の「ＣＭＹＫの強度の累計」と、バスケット毎の「バスケットに振り分けられた画素数」である。
【００７５】
上述したように、次のラインに渡すデータは一時情報としてメモリ１０２に保存する必要があるので、データの量が少ないほうが望ましい。そこで、ステップＳ１０４に関して以下のような構成を採用してもよい。これによって、メモリ１０２が保存するデータの量がさらに低減される。
【００７６】
すなわち、メモリ１０２は、８画素の振り分け処理終了後、ステップＳ１０４において、バスケット毎に「ＣＭＹＫの強度の累計」、バスケット毎の「バスケットに振り分けられた画素数」、各画素が振り分けられたバスケットの番号（インデックス）を、次のラインの処理へと引き継ぐデータとして、次のラインの振り分け処理が開始されるまで保存する。
【００７７】
換言すれば、ＣＰＵ１００は、ステップＳ１０４において、各画素が振り分けられたバスケットの番号（インデックス）に関し、バスケット毎の「どの画素が入っているかを示すフラグ」（３８４ｂｉｔ＝６４ｂｉｔ（６４画素のＯＮ／ＯＦＦ）×６バスケット）を、画素毎の「どのバスケットに入っているかを示すデータ（１９２ｂｉｔ＝６４画素×３ｂｉｔ（バスケットの識別番号））へと変換して保存する。
【００７８】
そして、ＣＰＵ１００は、８画素の振り分け処理（ステップＳ２００）終了後は、次のブロックの振り分け処理へと移る。
【００７９】
なお、このままでは次のラインの振り分け処理時に、画素を色分けするための判別データである「ＣＭＹＫの強度の最大値と最小値」がなくなってしまうので、ステップＳ１０２のバスケットの準備時に、メモリ１０２が保存しているＣＭＹＫの強度の累計と画素数とから平均値を算出して、最大値および最小値に同じ値（平均値）を代入する。このように構成しても、画像処理装置ＭＦＰによる画素の色分けは正しく行われ、画質の変化はほとんど無い。累計も保存されているので、代表値である平均値が正しく算出される。
【００８０】
ここで、メモリ１０２は、一時情報の統計値としてバスケット毎の強度の累計の代わりにバスケット毎の強度の平均値を保存し、ＣＰＵ１００が当該平均値を代表値として出力しても良い。逆に、メモリ１０２は、一時情報の統計値として「ＣＭＹＫの強度の最大値と最小値」を保存し、ＣＰＵ１００が累計または平均値を算出してもよい。
【００８１】
また、ＣＰＵ１００による計算量を少なくするために、本実施の形態に係る画像処理装置ＭＦＰは画素数を一時情報として記憶しているが、インデックスから画素数を算出してもよい。
【００８２】
ＣＰＵ１００は、Ｓ１０２、Ｓ２００、Ｓ１０４において対象となったブロックの右隣にさらにブロックが存在するか否かを判断する（ステップＳ１０６）。ＣＰＵ１００は、Ｓ１０２、Ｓ２００、Ｓ１０４において対象となったブロックの右隣にさらにブロックが存在する場合（ステップＳ１０６においてＹＥＳである場合）、ステップＳ１０２からの処理を繰り返す。
【００８３】
一方、ＣＰＵ１００は、Ｓ１０２、Ｓ２００、Ｓ１０４において対象となったブロックの右隣にブロックが存在しない場合（ステップＳ１０６においてＮＯである場合）、８ライン分（６４画素）の画素の振り分けが終了したか否かを判断する（ステップＳ１０８）。ＣＰＵ１００は、８ライン分（６４画素）の画素の振り分けが終了していない場合（ステップＳ１０８においてＮＯである場合）、ステップＳ１０２からの処理を繰り返す。すなわち、ＣＰＵ１００は、画像データの左端のブロックに対するバスケットを準備する（ステップＳ１０２）。そして、次のラインの画素をバスケットに振り分ける。
【００８４】
一方、ＣＰＵ１００は、８ライン分（６４画素）の画素の振り分けが終了した場合（ステップＳ１０８においてＹＥＳである場合）、出力処理（ステップＳ３００）を実行する。出力処理（ステップＳ３００）については後述する。
【００８５】
＜画素振り分け処理＞
以下では、主に図１〜図３、図５を参照して、画像振り分け処理の処理手順について説明する。なお、図５は、本実施の形態に係る画像処理装置ＭＦＰにおける画像振り分け処理の処理手順を示すフローチャートである。
【００８６】
まず、分類部１００３として機能するＣＰＵ１００は、対象となる画素データに含まれる画素の強度が、第１のバスケット情報１０４１〜第６のバスケット情報１０４６の参照値に含まれるか否かを判断する（ステップＳ２０２）。あるいは、ＣＰＵ１００は、画素データに含まれる画素の強度が、第１のバスケット情報１０４１〜第６のバスケット情報１０４６の参照値に一致するか否かを判断する。
【００８７】
対象となる画素データに含まれる画素の強度が第１のバスケット情報１０４１〜第６のバスケット情報１０４６の参照値に含まれる場合（ステップＳ２０２においてＹＥＳである場合）、ＣＰＵ１００は、当該画素を当該参照値に対応するバスケットに振り分ける（ステップＳ２０４）。あるいは、ＣＰＵ１００は、対象となる画素データに含まれる画素の強度が、第１のバスケット情報１０４１〜第６のバスケット情報１０４６の参照値に一致する場合、当該画素を当該参照値に対応するバスケットに振り分ける。ＣＰＵ１００は、Ｓ２０６からの処理を実行する。
【００８８】
なお、対象となる画素を含んだバスケットに関し、後述する「どの画素が入っているかを示すフラグ」や「ＣＭＹＫの強度の累計」や「バスケットが含む画素数」が更新される。
【００８９】
対象となる画素データに含まれる画素の強度が第１のバスケット情報１０４１〜第６のバスケット情報１０４６の参照値に含まれない場合（ステップＳ２０２においてＮＯである場合）、ＣＰＵ１００は、未だ参照値が設定されていないバスケットが存在するか否かを判断する（ステップＳ２０８）。あるいは、画素データに含まれる画素の強度が、第１のバスケット情報１０４１〜第６のバスケット情報１０４６の参照値に一致しない場合（ステップＳ２０２）、ＣＰＵ１００は、未だ参照値が設定されていないバスケットが存在するか否かを判断する（ステップＳ２０８）。
【００９０】
未だ参照値が設定されていないバスケットが存在する場合（ステップＳ２０８においてＹＥＳである場合）、対象となる画素を当該バスケットに振り分ける（ステップＳ２１０）。ＣＰＵ１００は、若い番号のバスケットから順番に画素を振り分ける。
【００９１】
なお、対象となる画素を含んだバスケットに関し、後述する「どの画素が入っているかを示すフラグ」や「ＣＭＹＫの強度の累計」や「バスケットが含む画素数」が更新される。ここでは、対象となる画素のＣＭＹＫの強度がそのまま各色プレーンの最大値と最小値とに代入される。ＣＰＵ１００は、ステップＳ２０６からの処理を実行する。
【００９２】
未だ参照値が設定されていないバスケットが存在しない場合（ステップＳ２０８においてＮＯである場合）、ＣＰＵ１００は、全てのバスケットに関する参照値同士の色空間における第１の距離を計算する。このとき、距離計算部１００８は、対象となる画素の強度と、全てのバスケットに関する参照値との色空間における第２の距離を計算する。
【００９３】
ＣＰＵ１００は、第１の距離と第２の距離の中で、第１の距離が最も距離が短い場合、対応する参照値に関する２つのバスケットを結合して、新たな１つのバスケットを生成する（ステップＳ２１２）。ＣＰＵ１００は、新たに未だ画素が振り分けられていないバスケットを生成して、対象となる画素を当該バスケットに振り分ける。一方、ＣＰＵ１００は、第１の距離と第２の距離との中で、第２の距離が最も距離が短い場合、対応する参照値に対応するバスケットに対象となる画素を振り分ける。ＣＰＵ１００は、ステップＳ２０６からの処理を実行する。
【００９４】
換言すれば、ＣＰＵ１００は、色差が最小の組み合わせで、バスケット番号の小さいバスケットを大きいバスケットにマージする。ＣＰＵ１００は、マージ後のバスケットに関し、後述する「どの画素が入っているかを示すフラグ」についてのＯＲ処理を行い、「ＣＭＹＫの強度の累計」の合算し、「画素数」の合算する。また、ＣＰＵ１００は、マージされるバスケット同士のＣＭＹＫの強度の最大値と最小値とを比較し、マージ後のバスケットの最大値と最小値を更新する。
【００９５】
ＣＰＵ１００は、対象となる画素とバスケットの何れかの代表値とが近い場合は、当該バスケットに対象となる画素のデータを加え、後述する「どの画素が入っているかを示すフラグ」、「ＣＭＹＫの強度の累計」、「ＣＭＹＫの強度の最大値と最小値」を更新する。
【００９６】
ステップＳ２０６において、ＣＰＵ１００は、８画素のバスケットの振り分けが終了したか否かを判断する（ステップＳ２０６）。８画素のバスケットの振り分けが終了した場合（ステップＳ２０６においてＹＥＳである場合）、ＣＰＵ１００は、振り分け処理を終了する。一方、８画素のバスケットの振り分けが終了していない場合（ステップＳ２０６においてＮＯである場合）、ＣＰＵ１００は、ステップＳ２０２からの処理を繰り返す。
【００９７】
＜出力処理＞
以下では、主に図１〜図３、図６を参照して、出力処理の処理手順について説明する。なお、図６は、本実施の形態に係る画像処理装置ＭＦＰにおける出力処理の処理手順を示すフローチャートである。
【００９８】
ここでは、決定部１００５として機能するＣＰＵ１００は、バスケットの各々のＣＭＹＫの強度の平均値（代表値）と各画素が振り分けられたバスケットの番号（インデックス）を出力する。すなわち、本実施の形態においては、ＣＰＵ１００は、８ライン（６４画素終了後）、以下の手順でデータを出力する。
【００９９】
まず、ＣＰＵ１００は、バスケットの各々について、強度の累計と画素数とからＣＭＹＫの各々の強度の平均値を求める（ステップＳ３０２）。ＣＰＵ１００は、各バスケットのＣＭＹＫ平均値と各画素のバスケット番号（インデックス）を出力する（ステップＳ３０４）。
【０１００】
なお、メモリ１０２あるいはＨＤＤ１１０が、決定部１００５として機能するＣＰＵ１００からの分類結果を格納してもよい。また、ＣＰＵ１００が、分類結果に基づいて、ディスプレイ１３８に圧縮画像を表示させてもよい。あるいは、ＣＰＵ１００が、分類結果に基づいて、プリンタ１１６に圧縮画像をプリントさせてもよい。
【０１０１】
＜画像データの流れ＞
ここで、上記画像圧縮処理における画像データの流れについて説明する。図７は、本実施の形態に係る画像圧縮処理における画像データの流れを示す概念図である。
【０１０２】
図７を参照して、バスケットの準備（ステップＳ１０２）においては、ＣＰＵ１００は、前のラインの画素の振り分けが終了したときに一時退避領域に格納された対象となるブロックの第１のバスケット情報１０４１〜第６のバスケット情報１０４６を作業領域にコピーする。
【０１０３】
ここで、一時退避領域に格納されているデータは、以下の通りである。すなわち、本実施の形態に係るメモリ１０２は、１バンドに含まれるブロック（対象となるラインが貫くブロック）毎に、以下のデータを格納する。なお、以下では、画像はシアン（Ｃ）、マゼンタ（Ｍ）、イエロー（Ｙ）、ブラック（Ｋ）から構成されるものとする。各色プレーンの強度は８ｂｉｔで表されるものとする。
・色プレーンの最大値と最小値
（８ｂｉｔ（強度の最大値）＋８ｂｉｔ（強度の最小値））×４色×６バスケット
＝３８４ｂｉｔ
・バスケットの累計
１４ｂｉｔ×４色×６バスケット＝３３６ｂｉｔ
・バスケットに振り分けられた画素数
６ｂｉｔ（画素数）×６バスケット＝３６ｂｉｔ
・画素のバスケット番号（分類結果）
３ｂｉｔ×６４画素＝１９２ｂｉｔ
これらのデータの１ブロック分の合計は、９４８ｂｉｔである。
【０１０４】
振り分け処理（ステップＳ２００）においては、作業領域に格納されているデータは、以下の通りである。すなわち、本実施の形態に係るメモリ１０２は、対象となるブロックについてのみ、バスケット毎に以下のデータを格納する。
・どの画素が入っているかを示すフラグ（６４画素分）
６４ｂｉｔ
・バスケットに振り分けられた画素の個数
６ｂｉｔ
・画素の強度の累計
１４ｂｉｔ×４色＝５６ｂｉｔ
・各色プレーンの最大値と最小値
１６ｂｉｔ×４色＝６４ｂｉｔ
これらのデータの６バスケット分の合計は、１１４０ｂｉｔ（＝１９０ｂｉｔ×６バスケット）である。
【０１０５】
ステップＳ１０４においては、ＣＰＵ１００は、対象となるブロックの１ライン分の画素の振り分け処理が終了すると、終了時点において作業領域に格納されている各バスケットに関するデータに基づいて、対象となるブロックに関するデータを一時退避領域に格納する。一時退避領域に格納されるデータは、上述したものと同様であるため、ここでは説明を繰り返さない。
【０１０６】
ＣＰＵ１００は、対象となるブロックの１ライン分の画素の振り分け処理が終了すると、次のブロックの当該ラインの画素の振り分け処理に移行する。ＣＰＵ１００は、バスケットの準備（ステップＳ１０２）と振り分け処理（ステップＳ２００）とを繰り返す。
【０１０７】
ＣＰＵ１００は、対象となるライン（第１のライン）の全ての画素の振り分け処理が終了すると、次のライン（第２のライン）関する画素の振り分け処理を行う。ここでも、上述したように、ブロック毎にバスケットを準備して（ステップＳ１０２）、第２のラインに含まれる画素の振り分け処理を行う（ステップＳ２００）。
【０１０８】
ＣＰＵ１００は、全てのライン（１バンド）の画素の振り分け処理が終了すると、すなわち８ラインの画素の振り分けが終了すると、ステップＳ３００において、ＣＭＹＫの強度の累計と画素数とからＣＭＹＫの強度の平均値（代表値）を計算する。ＣＰＵ１００は、各バスケットの代表値と、各画素のバスケット番号とを出力する。
【０１０９】
ここで、ＣＰＵ１００が他のアプリケーションや他の装置などに出力するデータについて説明する。図８は、本実施の形態に係るＣＭＹＫの出力フォーマットを示す概念図である。図９は、本実施の形態に係るＲＧＢの出力フォーマットを示す概念図である。
【０１１０】
図８を参照して、画素がバスケットに振り分けられたＣＭＹＫの圧縮データは、インデックス部分と、Ｃ成分の代表値と、Ｍ成分の代表値と、Ｙ成分の代表値と、Ｋ成分の代表値とを含む。インデックス部分は、各画素がどのバスケットに属するかを示す。データ量は、１９２ｂｉｔ（＝３ｂｉｔ×６４画素）である。Ｃ成分の代表値と、Ｍ成分の代表値と、Ｙ成分の代表値と、Ｋ成分の代表値とは、各々、バスケット毎の代表値（８ｂｉｔ）を含む。Ｃ成分の代表値と、Ｍ成分の代表値と、Ｙ成分の代表値と、Ｋ成分の代表値の、各々のデータ量は、４８ｂｉｔ（＝８ｂｉｔ×６バスケット）である。
【０１１１】
図９を参照して、画素がバスケットに振り分けられたＲＧＢの圧縮データは、インデックス部分と、Ｒ（Ｒｅｄ）成分の代表値と、Ｇ（Ｇｒｅｅｎ）成分の代表値と、Ｙ（Ｙｅｌｌｏｗ）成分の代表値とを含む。インデックス部分は、各画素がどのバスケットに属するかを示す。データ量は、１９２ｂｉｔ（＝３ｂｉｔ×６４画素）である。Ｒ成分の代表値と、Ｇ成分の代表値と、Ｂ成分の代表値とは、各々、バスケット毎の代表値（８ｂｉｔ）を含む。Ｒ成分の代表値と、Ｇ成分の代表値と、Ｂ成分の代表値の、各々のデータ量は、４８ｂｉｔ（＝８ｂｉｔ×６バスケット）である。
【０１１２】
＜他の画像圧縮方法との比較＞
以下では、本実施の形態に係る画像処理方法（画像圧縮方法）と他の画像圧縮方法との違いについて説明する。
【０１１３】
（ＢＴＣアルゴリズムの概要）
まず、ＢＴＣアルゴリズムを利用した画像圧縮方法について説明する。図１０は、ＢＴＣアルゴリズムを示す第１の概念図である。図１１は、ＢＴＣアルゴリズムを示す第２の概念図である。
【０１１４】
図１０を参照して、画像処理装置は、ブロック内の画素に関して、プレーン毎に４色（２ｂｉｔで表現される。）に減色する。さらに、画像処理装置は、当該４色中の２色のみを記録することによって、データ量を削減する。たとえば、画像処理装置は、「０１」と「１０」に関する代表色などを記録しない。
【０１１５】
元の画像は１画素毎に８ｂｉｔのデータを有する。すなわち、元の画像は全体として５１２ｂｉｔ（＝８ｂｉｔ×６４画素）のデータを有する。画像処理装置は、画像を減色することによって、画像全体のデータ量を１４４ｂｉｔ（＝２ｂｉｔ×６４画素＋８ｂｉｔ×２色）に削減する。すなわち、元の画像を２８％にまで圧縮することができる。なお、ブロックの画素数が４×４である場合には、元の画像を３４％にまで圧縮することができる。
【０１１６】
図１１を参照して、ＢＴＣアルゴリズムにおいては、画像処理装置は、たとえば、ブロック内の画素の強度の最大値と最小値の間を複数領域に分けて、それぞれの画素がどの領域に属するのかに基づいて画素の色分けを行う。画像処理装置は、ブロック内の最大値と最小値とを求めた後で、それぞれの画素の色分けを行う必要があるので、画像データのそれぞれの画素に少なくとも２回アクセスする必要がある。すなわち、このような技術をハードウェアに実装する場合には、画像処理装置がブロック内の全画素のデータを一旦保持することが可能な構成にする必要がある。
【０１１７】
（ＡＢＴＣアルゴリズムの概要）
次に、ＡＢＴＣアルゴリズムを利用した画像圧縮方法について説明する。図１２は、ＡＢＴＣアルゴリズムを示す概念図である。
【０１１８】
図１２を参照して、画像処理装置は、ブロック内の画素に関して、プレーン毎に４色（２ｂｉｔで表現される。）に減色する。
【０１１９】
なお、元の画像は１画素毎に２４ｂｉｔ（＝８ｂｉｔ×３原色）のデータを有する。すなわち、元の画像は全体として１５３６ｂｉｔ（＝２４ｂｉｔ×６４画素）のデータを有する。画像処理装置は、画像を４色に減色することによって、画像全体のデータ量を２２４ｂｉｔ（＝２ｂｉｔ×６４画素＋２４ｂｉｔ×４色）に削減する。すなわち、元の画像を１５％にまで圧縮することができる。
【０１２０】
（その他のアルゴリズム１の概要）
次に、その他の第１のアルゴリズムを利用した画像圧縮方法について説明する。図１３は、その他のアルゴリズムを示す概念図である。
【０１２１】
図１３を参照して、画像処理装置は、簡易均等色空間Ｌ、ｒ＿ｇ、ｂを利用する。画像処理装置は、最大のレンジ方向に分割を繰り返す、領域分割は色の切れ目を探索する。画像処理装置は、ブロック内の画素値の色空間内の分布を見て領域分割をすることによって、色分けを行う。当該アルゴリズムにおいては、画像処理装置ＭＦＰが、画素値の分布を評価してから色分けを行うためと、色分けを行ってから代表値（画素値の平均）を求めるため、画像データに３回アクセスする必要がある。すなわち、画像処理装置は、一旦ブロック内のデータを全部保持する必要がある。
【０１２２】
（その他のアルゴリズム２の概要）
次に、その他の第２のアルゴリズムを利用した画像圧縮方法について説明する。たとえば、特開平１０−４０３６４号公報（特許文献６）のように、画像処理装置は、色空間に箱を作成し、カラー画像の現れる各色をその箱に入れる。画像処理装置は、初期代表色以外の色は新しい箱として作成し、常に箱がＮ個となるように箱同士の体積が最小になるように箱をマージする。画像処理装置は、最終的に作成されたＮ個の重心を代表色として、近似画像を生成し、画像出力装置に出力する。
【０１２３】
より詳細には、画像処理装置は、原画像から重複しない最初のＮ個の色を長さ１の箱として作成する。画像処理装置は、ＭｅｒｇｅＢｏｘ法を用いて原画像を表現している色空間をＮ個の箱にする。画像処理装置は、作成された箱の代表点を求め、その代表点に画像の各点をマッピングし、求める画像を作成する。
【０１２４】
まず、画像処理装置は、Ｍｅｒｇｅｂｏｘ法に基づいて色空間を統合する。初めは長さ１のＮ個の箱である。画像処理装置は、入力画像をスキャンし、そこに存在する色（長さ１の箱として考える）が作成したＮ個の箱と同様のものかを調べる。その時、どの箱にも入らない箱だったら、新しく長さ１の箱を生成し、その点（色）を代入する。Ｎ＋１個になった箱をＮ個にするために、生成された箱と箱をマージする。その対象となる箱は、マージして体積が最小になるような箱を選択する。選択する方法は、すべての箱の組み合わせで体積を計算し、最小になる組の箱どうしをマージする。また、マージする方法は、２つの箱の最も離れているコーナーを用いて、新しい箱とする。これを入力画像のすべての画素に対して行い、Ｎ個の箱を作成する。
【０１２５】
次に、画像処理装置は、近似画像を作成する。前述したように、Ｍｅｒｇｅｂｏｘ法で統合されたＮ個の箱は、入力画像を表している色をよく似た色で区画したものである。これらの箱にあるどれかの色を代表色としなければいけない。処理速度を考慮して、ここでは箱の重心を採用する。重心とは、箱に存在する点をＲＧＢ各軸に射影して、各辺の座標値の平均を取ったものとする。このようにして、画像処理装置は、箱の重心を求め、これを代表色とする。
【０１２６】
しかし、この方法であっても、画像処理装置は、区画をした後、その範囲内に入る画素値を集計することになるので、画像データに２回アクセスすることになる。
【０１２７】
（本実施の形態に係る画像処理装置ＭＦＰの利点）
一方、本実施の形態に係る画像処理装置ＭＦＰは、色分けされたバスケットを用意し、各画素がどのバスケットに入るのか逐次（その都度）判断することによって色分けを行う。画像処理装置ＭＦＰは、画素の振り分けることと、近い色のバスケットをまとめることとを繰り返すことによって、画像の圧縮を行う。本実施の形態に係る画像処理装置ＭＦＰは、色分け処理と同時に、その画素がどのバスケットに属するかの情報と、代表値を求めるのに必要な情報とを記録することによって、通常の画像データ取得順に沿って画素を振り分けつつ、当該画像データへの１回のアクセスによって色分け後の各バスケットの代表値算出までを完了することができる。
【０１２８】
そのため、本実施の形態に係る画像処理装置ＭＦＰは、ブロック分の画像データを保持する必要が無い。画像処理装置ＭＦＰは、中間データとしてバスケット内のデータのみ保持すればよいのみである。ブロックを含むような帯状の領域の画像データを保持したり、ブロック部分のデータを切り出して保持したりする必要が無くなり、高速化と低コストを両立できるようになる。
【０１２９】
［その他の実施の形態］
本実施の形態においては、画像処理装置ＭＦＰの内部のメモリ１０２あるいはＨＤＤ１１０が、ＣＰＵ１００からの分類結果を格納する。ＣＰＵ１００が、分類結果に基づいて、ディスプレイ１３８に圧縮画像を表示させる。あるいは、ＣＰＵ１００が、分類結果に基づいて、プリンタ１１６に圧縮画像をプリントさせる。
【０１３０】
しかし、画像処理装置ＭＦＰの外部の装置が、ＣＰＵ１００からの分類結果を格納してもよい。また、画像処理装置ＭＦＰの外部の装置が、分類結果に基づいて圧縮画像を表示してもよい。画像処理装置ＭＦＰの外部の装置が、分類結果に基づいて圧縮画像をプリントしてもよい。すなわち、画像処理装置は、記憶機能や、プリンタ機能や、表示機能を有していなくてもよい。
【０１３１】
以下では、上記の画像処理装置ＭＦＰあるいは記憶機能やプリンタ機能や表示機能を有さない画像処理装置１０が、画像処理システム１の一部を構成する場合について説明する。図１４は、画像処理装置ＭＦＰ（１０）を含む画像処理システム１を示す概略図である。
【０１３２】
図１４に示すように、画像処理システム１は、画像処理装置ＭＦＰ（１０）と、記録装置１１と、表示装置１２と、プリンタ装置１３とを含む。画像処理装置ＭＦＰ（１０）と、記録装置１１と、表示装置１２と、プリンタ装置１３とは、ネットワークＮＷを介して、相互に画像データや圧縮データ（分類結果）を送受信可能に構成される。なお、ネットワークＮＷは、ＬＡＮ（Local Area Network）やＷＡＮ（Wide Area Network）などの専用回線や、インターネットや仮想プライベートネットワーク（Virtual Private Network）などの公衆回線からなるものであって、さらにその一部または全部が無線ＬＡＮなどの無線通信回線であってもよい。
【０１３３】
記録装置１１は、ネットワークＮＷを介して画像処理装置ＭＦＰ（１０）から分類結果を受信して、当該分類結果を内部に格納する。
【０１３４】
表示装置１２は、ネットワークＮＷを介して画像処理装置ＭＦＰ（１０）から分類結果を受信して、当該分類結果に基づいて画像を表示する。
【０１３５】
プリンタ装置１３は、ネットワークＮＷを介して画像処理装置ＭＦＰ（１０）から分類結果を受信して、当該分類結果に基づいて画像を印刷する。
【０１３６】
すなわち、画像処理装置ＭＦＰと、記録装置１１と、表示装置１２と、プリンタ装置１３などが、１つの装置として実現されてもよいし、ネットワークを介して接続されるシステムとして実現されてもよい。
【０１３７】
本発明に係るプログラムは、コンピュータのオペレーティングシステム（ＯＳ）の一部として提供されるプログラムモジュールのうち、必要なモジュールを所定の配列で所定のタイミングで読み出して処理を実行させるものであってもよい。その場合、プログラム自体には上記モジュールが含まれずＯＳと協働して処理が実行される。このようなモジュールを含まないプログラムも、本発明にかかるプログラムに含まれ得る。
【０１３８】
また、本発明にかかるプログラムは他のプログラムの一部に組込まれて提供されるものであってもよい。その場合にも、プログラム自体には上記他のプログラムに含まれるモジュールが含まれず、他のプログラムと協働して処理が実行される。このような他のプログラムに組込まれたプログラムも、本発明にかかるプログラムに含まれ得る。
【０１３９】
提供されるプログラム製品は、ハードディスクなどのプログラム格納部にインストールされて実行される。なお、プログラム製品は、プログラム自体と、プログラムが記憶された記憶媒体とを含む。
【０１４０】
さらに、本発明に係るプログラムによって実現される機能の一部または全部を専用のハードウェアによって構成してもよい。
【０１４１】
今回開示された実施の形態はすべての点で例示であって制限的なものではないと考えられるべきである。本発明の範囲は上記した説明ではなくて特許請求の範囲によって示され、特許請求の範囲と均等の意味および範囲内でのすべての変更が含まれることが意図される。
【符号の説明】
【０１４２】
ＭＦＰ  画像処理装置、ＮＷ  ネットワーク、ＰＣ  パーソナルコンピュータ、ＳＲＶ  サーバ装置、１  画像処理システム、１０  画像処理装置、１１  記録装置、１２  表示装置、１３  プリンタ装置、１０２  メモリ、１１２  スキャナ、１１４  操作パネル、１１６  プリンタ、１１８  プリンタコントローラ、１２０  出力処理部、１２２  通信インターフェイス、１２４  バス、１３８  ディスプレイ、１００１  ライン切替部、１００２  画素切替部、１００３  分類部、１００４  更新部、１００５  決定部、１００６  判断部、１００７  判断部、１００８  距離計算部、１００９  結合部、１０４１−１０４６  バスケット情報。
【図２】
2011018970.tif 000003
【図３】
2011018970.tif 000004
【図４】
2011018970.tif 000005
【図５】
2011018970.tif 000006
【図６】
2011018970.tif 000007
【図７】
2011018970.tif 000008
【図８】
2011018970.tif 000009
【図９】
2011018970.tif 000010
【図１１】
2011018970.tif 000011
【図１３】
2011018970.tif 000012
【図１４】
2011018970.tif 000013
【図１】
2011018970.tif 000014
【図１０】
2011018970.tif 000015
【図１２】
2011018970.tif 000016