(57)【要約】  【課題】  複数のオブジェクトそれぞれを識別する識別情報を符号化する符号化装置を提供する。  【解決手段】  画像処理装置２は、全順序に配列された複数のオブジェクトに対して、基準となる配列順序からの置換パターンを示す識別子（順序符号）を付与する。この置換パターンの識別子は、Ｎ個のオブジェクトが存在する場合に、（ｌｏｇ２Ｎ！）ビットで表現できる。一方、Ｎ個のオブジェクトそれぞれに固有の識別子を付与すると、（Ｎ×ｌｏｇ２Ｎ）ビット必要になる。このように、置換パターンの識別子をオブジェクトの識別情報とすることにより、各オブジェクトに固有の識別子を付与する場合と比較して、データ量を小さくすることができる。【選択図】図２
2007329904.tif 000002
【特許請求の範囲】
【請求項１】
入力された複数のオブジェクトの配列順序を特定する順序特定手段と、
前記順序特定手段により特定された配列順序を示す順序符号を生成する符号生成手段と、
入力された前記複数のオブジェクトに対して、前記符号生成手段により生成された順序符号を付与する符号付与手段と
を有する符号化装置。
【請求項２】
入力されるオブジェクトそれぞれには、各オブジェクトを一意に特定する個別識別子が付与されており、
前記順序特定手段は、入力された複数のオブジェクトに付与された個別識別子に基づいて、これらのオブジェクトの配列順序を特定し、
前記符号付与手段は、入力された複数のオブジェクトに付与された複数の個別識別子を前記順序符号で置換する
請求項１に記載の符号化装置。
【請求項３】
前記符号生成手段は、既定数のオブジェクトが配列された場合の配列順序のみを示す符号を前記順序符号として生成する
請求項１に記載の符号化装置。
【請求項４】
入力された複数のオブジェクトを基準となる順序で配列した場合の各オブジェクトの順序を示す順序識別子を生成する順序識別子生成手段と、
前記順序特定手段により特定されたオブジェクトの配列順序に対応するように、前記順序識別子生成手段により生成された順序識別子を並べ替える識別子配列手段と
をさらに有し、
前記符号生成手段は、前記識別子配列手段により配列された順序識別子の順序を符号化する
請求項２に記載の符号化装置。
【請求項５】
前記順序識別子生成手段は、全順序となるように前記順序識別子を生成する
請求項４に記載の符号化装置。
【請求項６】
入力された複数のオブジェクトの配列順序を特定する順序特定手段と、
基準となるオブジェクトの配列順序から、前記順序特定手段により特定された配列順序への置換パターンを符号化する符号生成手段と、
入力された前記複数のオブジェクトに対して、前記符号生成手段により符号化された置換パターンを付与する符号付与手段と
を有する符号化装置。
【請求項７】
前記符号生成手段は、前記置換パターンを、入力されたオブジェクト全体に対して一様に置換する全体置換と、入力されたオブジェクトの一部に対して置換する部分置換との組合せに変換し、変換された全体置換及び部分置換をそれぞれ符号化する
請求項６に記載の符号化装置。
【請求項８】
前記全体置換は、オブジェクト全体の順序を所定数だけずらす置換であり、
前記部分置換は、一部のオブジェクトのみを入れ替える巡回置換であり、
前記符号生成手段は、基準となる配列順序の各序数と、前記順序特定手段により特定された配列順序の各序数との差分をそれぞれ算出し、算出された差分の最頻値を前記全体置換として符号化し、前記最頻値に基づく全体置換がなされたオブジェクトの配列順序に基づいて、前記部分置換を決定し、決定された部分置換を示す情報を符号化する
請求項７に記載の符号化装置。
【請求項９】
所定の順序で配列された複数のオブジェクトと、これらのオブジェクトの配列から基準となる配列順序への置換パターンを示す符号とを取得する符号取得手段と、
前記符号取得手段により取得された置換パターンの符号を復号化して、置換パターンを特定する置換パターン特定手段と、
前記置換パターン特定手段により特定された置換パターンと、基準となる配列順序とに基づいて、前記符号取得手段により取得された複数のオブジェクトそれぞれを特定するオブジェクト特定手段と
を有する復号化装置。
【請求項１０】
前記置換パターン特定手段は、オブジェクト全体に対して一様に置換する全体置換と、オブジェクトの一部に対して置換する部分置換との組合せから、本来のオブジェクトの配列順序を特定する
請求項９に記載の復号化装置。
【請求項１１】
入力された複数のオブジェクトの配列順序を特定し、
特定された前記配列順序を示す順序符号を生成し、
入力された前記複数のオブジェクトに対して、生成された前記順序符号を付与する
符号化方法。
【請求項１２】
入力された複数のオブジェクトの配列順序を特定するステップと、
特定された前記配列順序を示す順序符号を生成するステップと、
入力された前記複数のオブジェクトに対して、生成された前記順序符号を付与するステップと
をコンピュータに実行させるプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、オブジェクトの識別情報を符号化する符号化装置に関する。
【背景技術】
【０００２】
例えば、特許文献１は、画像データに含まれる画像領域（ブロブ）を一意のブロブ識別子で管理することを開示する。
また、非特許文献１は、複数のオブジェクトを識別子で管理することを開示する。
【特許文献１】特開２００５−２２８３４１号公報
【非特許文献１】PDF Reference, fifth edition: Adobe Portable Document Format version 1.6., Adobe Systems Incorporated
【発明の開示】
【発明が解決しようとする課題】
【０００３】
本発明は、上述した背景からなされたものであり、複数のオブジェクトそれぞれを識別する識別情報を符号化する符号化装置を提供することを目的とする。
【課題を解決するための手段】
【０００４】
［符号化装置］
上記目的を達成するために、本発明にかかる符号化装置は、入力された複数のオブジェクトの配列順序を特定する順序特定手段と、前記順序特定手段により特定された配列順序を示す順序符号を生成する符号生成手段と、入力された前記複数のオブジェクトに対して、前記符号生成手段により生成された順序符号を付与する符号付与手段とを有する。
【０００５】
好適には、入力されるオブジェクトそれぞれには、各オブジェクトを一意に特定する個別識別子が付与されており、前記順序特定手段は、入力された複数のオブジェクトに付与された個別識別子に基づいて、これらのオブジェクトの配列順序を特定し、前記符号付与手段は、入力された複数のオブジェクトに付与された複数の個別識別子を前記順序符号で置換する。
【０００６】
好適には、前記符号生成手段は、既定数のオブジェクトが配列された場合の配列順序のみを示す符号を前記順序符号として生成する。
【０００７】
好適には、入力された複数のオブジェクトを基準となる順序で配列した場合の各オブジェクトの順序を示す順序識別子を生成する順序識別子生成手段と、前記順序特定手段により特定されたオブジェクトの配列順序に対応するように、前記順序識別子生成手段により生成された順序識別子を並べ替える識別子配列手段とをさらに有し、前記符号生成手段は、前記識別子配列手段により配列された順序識別子の順序を符号化する。
【０００８】
好適には、前記順序識別子生成手段は、全順序となるように前記順序識別子を生成する。
【０００９】
また、本発明にかかる符号化装置は、入力された複数のオブジェクトの配列順序を特定する順序特定手段と、基準となるオブジェクトの配列順序から、前記順序特定手段により特定された配列順序への置換パターンを符号化する符号生成手段と、入力された前記複数のオブジェクトに対して、前記符号生成手段により符号化された置換パターンを付与する符号付与手段とを有する。
好適には、前記符号生成手段は、前記置換パターンを、入力されたオブジェクト全体に対して一様に置換する全体置換と、入力されたオブジェクトの一部に対して置換する部分置換との組合せに変換し、変換された全体置換及び部分置換をそれぞれ符号化する。
好適には、前記全体置換は、オブジェクト全体の順序を所定数だけずらす置換であり、前記部分置換は、一部のオブジェクトのみを入れ替える巡回置換であり、前記符号生成手段は、基準となる配列順序の各序数と、前記順序特定手段により特定された配列順序の各序数との差分をそれぞれ算出し、算出された差分の最頻値を前記全体置換として符号化し、前記最頻値に基づく全体置換がなされたオブジェクトの配列順序に基づいて、前記部分置換を決定し、決定された部分置換を示す情報を符号化する。
【００１０】
［復号化装置］
また、本発明にかかる復号化装置は、所定の順序で配列された複数のオブジェクトと、これらのオブジェクトの配列から基準となる配列順序への置換パターンを示す符号とを取得する符号取得手段と、前記符号取得手段により取得された置換パターンの符号を復号化して、置換パターンを特定する置換パターン特定手段と、前記置換パターン特定手段により特定された置換パターンと、基準となる配列順序とに基づいて、前記符号取得手段により取得された複数のオブジェクトそれぞれを特定するオブジェクト特定手段とを有する。
好適には、前記置換パターン特定手段は、オブジェクト全体に対して一様に置換する全体置換と、オブジェクトの一部に対して置換する部分置換との組合せから、本来のオブジェクトの配列順序を特定する。
【００１１】
［符号化方法］
また、本発明にかかる符号化方法は、入力された複数のオブジェクトの配列順序を特定し、特定された前記配列順序を示す順序符号を生成し、入力された前記複数のオブジェクトに対して、生成された前記順序符号を付与する。
【００１２】
［プログラム］
また、本発明にかかるプログラムは、入力された複数のオブジェクトの配列順序を特定するステップと、特定された前記配列順序を示す順序符号を生成するステップと、入力された前記複数のオブジェクトに対して、生成された前記順序符号を付与するステップとをコンピュータに実行させる。
【発明の効果】
【００１３】
本発明の符号化装置によれば、複数のオブジェクトを識別するための識別情報を高い圧縮率で符号化することができる。
【発明を実施するための最良の形態】
【００１４】
まず、本発明の理解を助けるために、その背景及び概略を説明する。
データファイルに複数のオブジェクトが含まれている場合には、それぞれのオブジェクトを識別するための識別子が付与され、この識別子を用いて管理されることがある。
例えば、図１（Ａ）に例示するように、複数のオブジェクトを合成して画像を構成するようなマルチオブジェクト形式のデータがある。マルチオブジェクト形式のデータにおいては、各オブジェクトを識別するためにオブジェクトを一意的に識別する固有識別子（ラベルや識別子など）が付加される。本例では、図１（Ｂ）に例示するように、各オブジェクトにシリアル番号が付与され、このシリアル番号が固有識別子として用いられている。
【００１５】
そして、１つのデータファイルに含まれるオブジェクトの数が多くなると、これらのオブジェクトを識別する識別子を表すためのビット数も増加する。
すなわち、本来ビット数が小さくて済むように識別子を設計しても、全オブジェクトを表すために必要なビット数に準じて、識別子のビット数が大きくなってしまうという問題があった。例えば、３個のオブジェクトを表すための識別子は２ビットで表現できるが、２５６個のオブジェクトを表すための識別子は８ビット必要になる。
【００１６】
そこで、図３に例示する本実施形態における画像処理装置２は、図１（Ｃ）のように各オブジェクトに対して識別子を付与するのではなく、シリアルに配列されたオブジェクト群に対して、配列順序を示す識別子（順序符号）を付与する。
より具体的には、本例の画像処理装置２は、シリアルに配列されたオブジェクト群に対して、基準となる配列順序からの置換パターンを示す識別子（順序符号）を付与する。置換パターンとは、既定数の要素の配列パターンであり、例えば、Ｎ個の要素が存在する場合には、Ｎ！個のパターンが存在する。したがって、置換パターンの識別子に要するビット数は、｛ｌｏｇ２Ｎ！｝となる。ここで、｛ｘ｝は、ｘより大きい最小の整数（ｘの少数点以下を切りあげた整数）である。
一方、Ｎ個のオブジェクトに固有識別子を付与する場合、各固有識別子に要するビット数は、｛ｌｏｇ２Ｎ｝であるため、Ｎ個の固有識別子に要するビット数は、Ｎ×｛ｌｏｇ２Ｎ｝となる。一般に、整数Ｍより小さい整数Ｎに対して｛ｌｏｇ２Ｎ｝は｛ｌｏｇ２Ｍ｝より小さく、かつ、｛ｌｏｇ２Ｎ＋ｌｏｇ２Ｍ｝は、｛ｌｏｇ２Ｎ｝＋｛ｌｏｇ２Ｍ｝以下となるので、明らかに｛ｌｏｇ２Ｎ！｝は、Ｎ×｛ｌｏｇ２Ｎ｝より小さい。
【００１７】
例えば、オブジェクトが３つ存在する場合には、図２（Ａ）に例示するように、識別子（固有符号１〜３）は少なくとも２ビットとなり、３つのオブジェクトが存在するため、データファイルに含まれる識別子の総ビット数は、６ビットとなる。
一方、３つのオブジェクトを置換した場合のパターンは、図２（Ｂ）に例示するように、６個（３！）だけ存在する。そして、この６つの置換パターンを表現するためには、３ビット（ｌｏｇ２３）で足りる。
本例では、図２（Ｃ）に例示するように、置換パターンを識別するための順序符号（６ビット）を、シリアルに配列されたオブジェクト群（オブジェクト１〜３）に付与する。
このように、本例の符号化方法は、オブジェクトが３つ存在する場合には、識別情報に要するビット数を、固有符号（図２（Ａ））を付与する形態の半分にすることができる。
【００１８】
［ハードウェア構成］
次に、本実施形態における画像処理装置２のハードウェア構成を説明する。
図３は、本発明にかかる符号化方法が適応される画像処理装置２のハードウェア構成を、制御装置２１を中心に例示する図である。
図３に例示するように、画像処理装置２は、ＣＰＵ２１２及びメモリ２１４などを含む制御装置２１、通信装置２２、ＨＤＤ・ＣＤ装置などの記録装置２４、並びに、ＬＣＤ表示装置あるいはＣＲＴ表示装置及びキーボード・タッチパネルなどを含むユーザインターフェース装置（ＵＩ装置）２５から構成される。
画像処理装置２は、例えば、スキャナ／プリンタ装置３から画像データを取得し、取得された画像データに対して画像処理を施し、画像処理が施された画像データを符号化してスキャナ／プリンタ装置３に送信する。
【００１９】
［符号化プログラム］
次に、画像処理装置２により実行される符号化処理を説明する。
図４は、制御装置２１（図３）により実行され、本発明にかかる符号化方法を実現する符号化プログラム５の機能構成を例示する図である。
図４に例示するように、第１の符号化プログラム５は、データ入力部５００、順序特定部５１０、符号生成部５２０、及び符号付与部５３０を有する。
なお、本例では、シリアル番号を固有識別子としてオブジェクトが管理されている場合を具体例として説明する。
【００２０】
符号化プログラム５において、データ入力部５００は、複数のオブジェクトを含むデータファイルが入力されると、入力されたデータファイルをそのまま符号付与部５３０に出力し、データフィルに含まれる各オブジェクトの識別情報を順序特定部５１０に出力する。
本例のデータ入力部５００は、図２（Ａ）に例示するデータファイルが入力されると、入力されたデータファイルをそのまま符号付与部５３０に出力し、データファイルに含まれるオブジェクトの識別子（固有符号１〜３）を順序特定部５１０に出力する。本例の固有符号１〜３は、オブジェクトに付与されたシリアル番号である。
【００２１】
順序特定部５１０は、データファイルに含まれるオブジェクトの配列順序を特定し、特定された配列順序と、オブジェクトの総数とを符号生成部５２０に出力する。
本例の順序特定部５１０は、データ入力部５００から入力された識別子（オブジェクトのシリアル番号）の入力順に基づいて、オブジェクトの配列順序を特定する。
【００２２】
符号生成部５２０は、既定の手順で、順序特定部５１０により特定された配列順序（オブジェクトの配列順序）を示す順序符号を生成し、生成された順序符号を符号付与部５３０に出力する。順序符号は、置換パターンを示す符号であり、置換パターンの種類に応じて生成される。この置換パターンの種類は、オブジェクトの総数によって算出される。
本例の符号生成部５２０は、順序特定部５１０から入力されたオブジェクトの総数に基づいて置換パターンを生成し、生成された置換パターンに対して識別子（順序符号）を付与することにより、置換パターンの符号表を作成し、作成された符号表を参照して、順序特定部５１０から入力された配列順序に対応する識別子（順序符号）を選択して符号付与部５３０に出力する。
【００２３】
符号付与部５３０は、入力された複数のオブジェクトに対して、符号生成部５２０から入力された順序符号を付与する。
より具体的には、符号付与部５３０は、入力された複数のオブジェクトを入力順にシリアルに配列し、この配列順序を示す順序符号を、これら複数のオブジェクトに付与する。
本例の符号付与部５３０は、データ入力部５００から入力されたデータファイルのうち、各オブジェクトの識別子（図２（Ａ）の固有符号１〜３）を、符号生成部５２０から入力された順序符号で置換する。これにより、図２（Ｃ）に例示するデータファイルが生成される。
【００２４】
［復号化プログラム］
次に、復号化処理を説明する。
図５は、制御装置２１（図３）により実行される復号化プログラム６の機能構成を例示する図である。
図５に例示するように、復号化プログラム６は、符号入力部６００、総数特定部６１０、符号表生成部６２０、識別子復号部６３０、及びオブジェクト特定部６４０を有する。
なお、本例では、上記符号化プログラム５により符号化されたデータファイルを入力される場合を具体例として説明する。
【００２５】
復号化プログラム６において、符号入力部６００は、所定の順序で配列された複数のオブジェクトと、このオブジェクト群の配列に対応する順序符号とを含むデータファイルが入力されると、入力されたデータファイルに含まれるオブジェクト群をオブジェクト特定部６４０に出力し、データフィルに含まれる順序符号を識別子復号部６３０に出力する。
本例の符号入力部５００は、図２（Ｃ）に例示するデータファイルが入力されると、入力されたデータファイルのうち、オブジェクト群をそのままオブジェクト特定部６４０に出力し、順序符号を識別子復号部６３０に出力する。
【００２６】
総数特定部６１０は、データファイルに含まれるオブジェクトの総数を特定し、特定されたオブジェクトの総数を符号表生成部６２０に出力する。
本例の総数特定部６１０は、データ入力部５００に入力されるオブジェクトの数をカウントし、カウント値（オブジェクトの総数）を符号表生成部６２０に出力する。
【００２７】
符号表生成部６２０は、既定の手順（例えば、符号生成部５２０と同じ手順）で、総数特定部６１０により特定されたオブジェクトの総数に応じた符号表を生成する。
より具体的には、符号表生成部６２０は、符号化プログラム５の符号生成部５２０と同じ手順で、入力されたオブジェクト群の置換パターンを生成し、生成された置換パターンに対して識別子（順序符号）を付与する。識別子（順序符号）が付与された置換パターンのテーブルが符号表となる。
【００２８】
識別子復号部６３０は、入力された順序符号を復号化して、オブジェクトの置換パターンを特定し、特定された置換パターンをオブジェクト特定部６４０に出力する。
本例の識別子復号部６３０は、符号表生成部６２０により生成された符号表を参照して、入力された順序符号に対応する置換パターン（図２（Ｂ）の置換パターン）を特定する。
【００２９】
オブジェクト特定部６４０は、識別子復号部６３０により特定された置換パターンに基づいて、符号入力部６００から入力された複数のオブジェクトそれぞれを特定する。すなわち、置換パターンは、基準となる配列順序（本例では、オブジェクト１、オブジェクト２、オブジェクト３の順序）からの置換類型であり、入力された複数のオブジェクトの配列順序を示すものであるから、この置換パターンに基づいて、シリアルに配列された複数のオブジェクトそれぞれを特定することは可能である。
本例のオブジェクト特定部６４０は、置換パターンに基づいて、入力された複数のオブジェクトそれぞれを特定し、特定されたオブジェクトそれぞれに、各オブジェクトを識別する固有符号（図２（Ａ））を付与する。
【００３０】
以上説明したように、本実施形態における画像処理装置２は、複数のオブジェクトの識別情報を符号化する場合に、これらのオブジェクトの配列順序を示す順序符号を生成し、シリアルに配列された複数のオブジェクトに、生成された順序符号を付与することにより、識別情報の符号量を小さくすることができる。
本例のように、複数のオブジェクトに対してシリアル番号が固有識別子として付与されている場合には、この固有識別子（シリアル番号）の体系をそのまま基準となる配列順序として置換パターンを定義できるため好適である。
【００３１】
［第１変形例］
次に、上記実施形態の第１の変形例を説明する。
上記実施形態では、データファイルに含まれるオブジェクトに対してシリアル番号が固有識別子として付与されている形態を説明したが、これに限定されるものではない。
第１の変形例では、オブジェクトに付与された固有識別子の順序が不明確な場合（以下、このような識別子を個別識別子という）を説明する。例えば、図６（Ａ）に例示するように、半順序となる個別識別子が付与される場合や、識別子が数値ではなく文字列である場合などである。
このような場合に、本変形例の画像処理装置２は、図６（Ｂ）に例示するように、全順序を定義し、全順序で再構成された個別識別子に対して、図６（Ｃ）に例示するように順序識別子を対応付け、この順序識別子に基づいて、上記実施形態のように置換パターンを特定する。この順序識別子は、オブジェクトの基準となる配列順序を示す情報であり、オブジェクトに１：１で対応付けられる。
【００３２】
図７は、第２の符号化プログラム５２の機能構成を例示する図である。
図７に例示するように、第２の符号化プログラム５２は、図４の符号化プログラム５に、順序ＩＤ生成部５４０及び順序ＩＤ配列部５５０を追加した構成をとる。
【００３３】
本変形例のデータ入力部５００は、複数のオブジェクトを含むデータファイルが入力されると、入力されたデータファイルをそのまま符号付与部５３０に出力し、データフィルに含まれる各オブジェクトの個別識別子（図６）を順序特定部５１０及び順序ＩＤ生成部５４０に出力する。
本変形例の順序特定部５１０は、データファイルに含まれるオブジェクトの個別識別子を入力順に配列し、配列された個別識別子と、オブジェクトの総数とを順序ＩＤ配列部５５０に出力する。
【００３４】
順序ＩＤ生成部５４０は、入力された複数のオブジェクトを基準となる順序で配列した場合の各オブジェクトの順序を示す順序識別子を生成する。基準となる順序とは、例えば、他のテーブルにおける個別識別子の順序（後述する属性データファイルなど）、データファイルにおける個別識別子の出現順などである。
より具体的には、順序ＩＤ生成部５４０は、入力されたオブジェクトの総数だけ、序数からなる順序識別子を生成し、生成された順序識別子を、図６（Ｃ）に例示するように、個別識別子に対応付ける。
本例の順序ＩＤ生成部５４０は、後述する属性データファイル（図９）における個別識別子の順序を基準となる配列順序とし、この配列順序に沿って順序識別子を生成し、生成された順序識別子を、各オブジェクトの個別識別子に対応付ける。
【００３５】
順序ＩＤ配列部５５０は、順序特定部５１０により特定されたオブジェクトの配列順序に応じて、順序ＩＤ生成部５４０により生成された順序識別子を配列し、配列された順序識別子を、このオブジェクト群の置換パターンとして符号生成部５２０に出力する。
換言すると、順序ＩＤ配列部５５０は、順序ＩＤ生成部５４０により生成された順序識別子に応じて配列されたオブジェクト群の配列順序を基準配列として、入力されたオブジェクト群の置換パターンを特定する。
本例の順序ＩＤ配列部５５０は、順序特定部５１０により配列された個別識別子の順に、順序ＩＤ生成部５４０により各個別識別子に対応付けられた順序識別子を配列し、配列された順序識別子を置換パターンとして符号生成部５２０に出力する。
なお、順序特定部５１０から入力されたオブジェクトの総数は、順序ＩＤ配列部５５０を介して、符号生成部５２０に出力される。
【００３６】
本変形例の符号生成部５２０は、上記実施形態と同様に、順序特定部５１０から入力されたオブジェクトの総数に基づいて符号表を作成し、作成された符号表を参照して、順序ＩＤ配列部５５０から入力された順序識別子の配列順序に対応する順序符号を選択して符号付与部５３０に出力する。
本変形例の符号付与部５３０は、データ入力部５００から入力されたデータファイルのうち、各オブジェクトの個別識別子を、符号生成部５２０から入力された順序符号で置換する。
なお、符号付与部５３０は、順序識別子及び個別識別子を互いに対応付けるテーブル（すなわち、図６（Ｃ）に例示した順序定義）を、データファイルに添付してもよい。
【００３７】
次に、第１の変形例における画像処理装置２（符号化プログラム５２）の全体動作を説明する。
図８は、符号化プログラム５２（図７）による符号化処理（Ｓ１０）のフローチャートである。なお、本例では、入力される複数のオブジェクトに対して、これらの全順序を一義的に定義できない個別識別子（図６）、又は、これらの全順序を一義的に定義できる固有符号（図２（Ａ））が付与されている場合を具体例として説明する。
【００３８】
図８に示すように、ステップ１００（Ｓ１００）において、データ入力部５００（図７）は、外部から、データファイルが入力されると、入力されたデータファイルをそのまま符号付与部５３０に出力し、入力されたデータファイルに含まれる識別子（個別識別子又は固有符号）を順序特定部５１０及び順序ＩＤ生成部５４０に出力する。
【００３９】
ステップ１１０（Ｓ１１０）において、順序特定部５１０は、データ入力部５００から入力された識別子（個別識別子又は固有符号）に基づいて、オブジェクトの配列順序及び総数を特定する。
【００４０】
ステップ１２０（Ｓ１２０）において、符号化プログラム５２は、入力された識別子が個別識別子（すなわち、全順序が一義的に定義できない識別子）である場合に、Ｓ１３０の処理に移行し、入力された識別子が固有符号（すなわち、全順序が一義的に定義できる識別子）である場合に、Ｓ１６０の処理に移行する。
なお、入力された識別子が固有符号である場合に、順序特定部５１０は、固有符号の配列順序を置換パターンとして特定し、順序ＩＤ配列部５５０を介して、特定された置換パターン及びオブジェクトの総数を符号生成部５２０に出力する。
【００４１】
ステップ１３０（Ｓ１３０）において、順序ＩＤ生成部５４０は、序数からなる順序識別子を生成し、生成された順序識別子を、データ入力部５００から入力された個別識別子に対応付ける。
具体的には、図９（Ａ）に例示するように、入力されるデータファイルには、オブジェクトそれぞれの属性情報が含まれた属性データファイル９０２と、オブジェクトのデータがシリアルに配列されたオブジェクトデータファイル９０４とが含まれている。属性データファイル９０２では、各オブジェクトの属性情報（例えば、画像オブジェクトの座標情報、色数など）がオブジェクトの個別識別子（Ａ〜Ｄ）に対応付けられている。また、オブジェクトデータファイル９０４では、各オブジェクトのデータ（オブジェクトＤ、オブジェクトＡ、・・・）がオブジェクトの個別識別子（Ａ〜Ｄ）に対応付けられている。
このような状況において、順序ＩＤ生成部５４０は、属性データファイル９０２における個別識別子の出現順序に応じて、順序識別子を生成する。この結果、図９（Ｂ）に例示するように、各個別識別子に対して、属性データファイル９０２におけるエントリ順に、順序識別子が割り当てられることになる。
【００４２】
ステップ１４０（Ｓ１４０）において、順序ＩＤ配列部５５０（図７）は、順序特定部５１０により特性された個別識別子の配列順序に応じて、順序ＩＤ生成部５４０により各個別識別子に割り当てられた順序識別子を配列する。
本例では、図９（Ａ）に例示するように、オブジェクトデータファイル９０４において、個別識別子Ｄ、個別識別子Ａ、個別識別子Ｂ、個別識別子Ｃの順に４つの個別識別子が配列されているため、図９（Ｂ）の対応関係に基づいて、順序識別子４、順序識別子１、順序識別子２、順序識別子３の順に４つの順序識別子が配列される。
【００４３】
ステップ１５０（Ｓ１５０）において、符号生成部５２０は、順序ＩＤ配列部５５０により配列された順序識別子の配列順序を特定する。
特定された配列順序（本例では、順序識別子４、順序識別子１、順序識別子２、順序識別子３）は、置換パターンとなる。
【００４４】
ステップ１６０（Ｓ１６０）において、符号生成部５２０は、入力されたオブジェクトの総数に応じて、全ての置換パターンそれぞれを順序符号に対応付ける符号表を生成し、特定された置換パターンに対応する順序符号を選択する。
【００４５】
ステップ１７０（Ｓ１７０）において、符号付与部５３０は、符号生成部５２０により選択された順序符号で、入力されたデータファイルに含まれる識別子（個別識別子又は固有符号）を置換する。
個別識別子が置換されると、図９（Ｃ）に例示するように、オブジェクト群に対して１つの順序符号が付されることになる。
【００４６】
ステップ１８０（Ｓ１８０）において、符号付与部５３０は、図９（Ｃ）に例示するように、入力された属性データファイル９０２と、順序符号が付されたオブジェクト群を含むオブジェクトデータファイル９０４'とを１つのデータファイルとして外部に出力する。
【００４７】
なお、このように符号化されたデータファイルを復号化する場合には、オブジェクト特定部６４０（図５）が、属性データファイル９０２を参照して、個別識別子を順序識別子に対応付けるテーブル（図９（Ｂ））を生成し、生成されてテーブルと、識別子復号部６３０から入力された置換パターンとに基づいて、各オブジェクトを特定する。特定された各オブジェクトに対して、再度個別識別子を付与するようにしてもよい。
【００４８】
以上説明したように、本変形例の画像処理装置２は、入力されるオブジェクトに対して一義的に全順序が定義されていない場合には、全順序となるような順序識別子を定義し、この順序識別子の置換パターンを符号化する。
【００４９】
［符号表の作成方法］
次に、符号表の作成方法（符号生成部５２０及び符号表生成部６２０）の一例を説明する。
符号表は、序数の置換パターンを既定の手順で特定し、特定された置換パターンに符号を割り当てることにより作成される。したがって、置換パターンの特定が符号化側及び復号化側で一致している必要がある。
【００５０】
互いに重複しないｎ個の数字に対する置換全体は、互いに重複しない（ｎ−１）個の数字に対する置換全体から構成できる。なお、互いに重複しないｎ個の任意の数字は、適当な１対１対応により、１、２、...、ｎに変換でき、かつ、逆の変換も可能であるので、以下の説明では、ｎ個の数字を１、２、...、ｎとするが、これによって、一般性を失うものではない。
【００５１】
互いに重複しないｎ個の数字に対する置換全体の集合Ｓｎを構成する具体的な手順は、以下である。
［手順１］
（ｎ−１）個の数字１、２、...、ｎ−１の置換全体の集合をＳｎ−１とすると、Ｓｎ−１の各要素の数字すべてに１を足し、新たにできた集合をＳ'ｎ−１とおく。元の数字の最小値は１であるので、１を足すことによりＳ'ｎ−１の各要素において最小の数字は、２となる。
［手順２］
Ｓ'ｎ−１の各要素の数字の並び（順序対）を保ったまま、Ｓ'ｎ−１の各要素の先頭に１を追加して、ｎ個の数字からなる順序対を新たに構成し、新たにできた集合をＳ１ｎとおく。
Ｓ１ｎは、ｎ個の数字１、２、...、ｎの置換全体の集合Ｓｎの部分集合となっている。
［手順３］
Ｓ１ｎの各要素に対して互換（１，２）を適用して、新たにできた集合をＳ２ｎとおく。ここで、互換（ｍ，ｎ）とは、数字ｍと数字ｎとを入れ替える操作である。
［手順４］
同様にして、ｉ＝ｎまでＳｉ−１ｎに互換（ｉ−１，ｉ）を適用して集合Ｓｉｎを次々と構成する。
［手順５］
Ｓ１ｎ、Ｓ２ｎ、...、Ｓｎｎの和集合Ｓ'ｎが、Ｓｎとなる。
［手順６］
符号（順序符号）を割り当てる場合は、例えば、Ｓ１ｎの各要素に１〜（ｎ−１）！の符号（シリアル番号）を付与する。さらに［手順５］において各部分集合を順番に並べて、各部分集合の各要素順にインクリメントして符号（シリアル番号）を付与する。例えば、Ｓ２ｎの最初の要素が（ｎ−１）！＋１となるようにする。同様にＳｉｎの最初の要素が（ｉ−１）（ｎ−１）！＋１となるようにする。
実際に、Ｓ'ｎの要素（置換）の数は、ｎ×（ｎ−１）！＝ｎ！である。
【００５２】
なお、上記［手順３］と［手順４］は纏めて次のようにしてもよい。
ｉ＝２からｉ＝ｎまでＳｉ−１ｎに互換（ｉ−１，ｉ）を適用して集合Ｓｉｎを構成する。
【００５３】
なお、上記では、符号表の作成方法の一例を示したが、符号化側と復号化側とで、置換パターンと順序符号との組合せが一致していれば、他の方法で符号表を生成してもよい。
【００５４】
［第２変形例］
次に、上記実施形態の第２の変形例を説明する。
上記実施形態及び第１の変形例では、基準となる配列順序からオブジェクトの配列順序に置換する単一の置換を置換パターンとして符号化しているが、これに限定されるものではない。
第２の変形例では、基準となる配列順序からオブジェクトの配列順序への置換を、複数の置換処理に分解し、分解された複数の置換処理それぞれを示す情報を符号化する。より具体的には、第２の変形例では、基準となる配列順序からオブジェクトの配列順序への置換を、オブジェクト全体の順序を所定数だけずらす置換（全体置換）と、一部のオブジェクトのみを入れ替える巡回置換（部分置換）とに分解し、全体置換を示す情報（具体的には、オブジェクトをずらす数）と、部分置換を示す情報（一部のオブジェクトに対する置換パターンの識別子）とを符号化する。
【００５５】
以下、符号化対象情報Ｉがｎ個の数字(最小値は０、最大値はｎ−１)の置換で表せるとして、第２の変形例をより具体的に説明する。
［符号化処理］
まず、符号化対象情報Ｉ（識別子の配列以外でもよい）を所定の方法で整数化する（ｘ＝ｆ（Ｉ）、ここで、ｆは所定の整数化方法、ｘは整数化された情報である）。
符号生成部５２０は、ｘをインデックスとする置換ρに対して、差分di ＝ｉ−ρ(ｉ)をとり、diの最頻値dを求める。ここで、ｉは、基準となる配列順序の序数（例えば、０，１，２，３，４，・・・）である。
次に、符号生成部５２０は、第２の置換ρ'(ｉ)＝(ρ(ｉ)＋d) mod n を導出し、第２の置換を巡回置換ρ''に変換する。ここで、巡回置換ρ''は、部分置換の具体例である。
最後に、符号生成部５２０は、巡回置換ρ''と最頻値d（全体置換のずらし量）とをそれぞれ符号化する。なお、差分di ＝ρ(ｉ)−ｉiの最頻値dを減算してもよい。
このように、全体置換を最頻値ｄで規定しているのは、ρ''(ｉ)＝ｉとなるｉを多くなるようにして、部分置換（本例では、巡回置換ρ''）の対象を少なくするためである。
【００５６】
次に、ｎ＝１０（オブジェクト数が１０）の実施例を以下に示す。図１０（Ａ）に例示する置換パターンρ（すなわち、オブジェクトの配列順序ρ）を符号化する場合を考える。なお、この配列順序ρの識別子（０〜９）をそのまま表現するのに必要なビット数は、10×log2 10＝ 10×4＝40 [bit]である。
また、上記実施形態の方法では、配列順序ρに対応する10次の対称群(Ｓ１０)の辞書式順序によるインデックス（＝3265921）を求めることにより、符号化対象情報Ｉ（＝ρ）は整数3265921に変換される。整数3265921はビット列（110001  11010101  10000001）で表せるので、22[bit]にデータ量が削減できる。
【００５７】
本変形例の符号生成部５２０は、以下のように、この置換パターンρに対して、各項の差分を求める。
d0 ＝0−ρ(0)＝0−9＝−9
d1 ＝1−ρ(1)＝1−0＝1
d2 ＝2−ρ(2)＝2−1＝1
d3 ＝3−ρ(3)＝3−2＝1
d4 ＝4−ρ(4)＝4−3＝1
d5 ＝5−ρ(5)＝5−4＝1
d6 ＝6−ρ(6)＝6−5＝1
d7 ＝7−ρ(7)＝7−6＝1
d8 ＝8−ρ(8)＝8−8＝0
d9 ＝9−ρ(9)＝9−7＝2
【００５８】
次に、符号生成部５２０は、このように算出された複数の差分diの最頻値dを求める。
d ＝ mode(d0，d1，d2，d3，d4，d5，d6，d7，d8，d9) ＝ 1
ここで、mode Aは、順序対Ａに対してＡに含まれる要素の内、最も多く存在する要素を返す。
このように算出された最頻値ｄは、全体置換のずらし量に相当する。
【００５９】
次に、符号生成部５２０は、置換ρから、最頻値ｄに応じた全体置換の分を除去し、残りの置換ρ'を算出する。具体的には、以下のように算出する。
ρ'(0)＝(ρ(0)＋d) mod 10＝(9＋1) mod 10＝0
ρ'(1)＝(ρ(1)＋d) mod 10＝(0＋1) mod 10＝1
ρ'(2)＝(ρ(2)＋d) mod 10＝(1＋1) mod 10＝2
ρ'(3)＝(ρ(3)＋d) mod 10＝(2＋1) mod 10＝3
ρ'(4)＝(ρ(4)＋d) mod 10＝(3＋1) mod 10＝4
ρ'(5)＝(ρ(5)＋d) mod 10＝(4＋1) mod 10＝5
ρ'(6)＝(ρ(6)＋d) mod 10＝(5＋1) mod 10＝6
ρ'(7)＝(ρ(7)＋d) mod 10＝(6＋1) mod 10＝7
ρ'(8)＝(ρ(8)＋d) mod 10＝(8＋1) mod 10＝9
ρ'(9)＝(ρ(9)＋d) mod 10＝(7＋1) mod 10＝8
【００６０】
図１０（Ｂ）をみてわかるように、残りの置換ρ'は、「８」と「９」を入れ替える部分置換だけである。
そこで、符号生成部５２０は、この置換ρ'を、一部のオブジェクトに対する置換である巡回置換ρ''（部分置換）に変換する。
ρ''＝(8 9)
【００６１】
ここで、符号化すべき情報は、部分置換ρ''＝(8 9)と、全体置換を規定する最頻値d ＝ 1 である。これらを符号化する場合、データ量は、13 [bit]（＝2× log2 10＋1＋ log2 10）となる。すなわち、部分置換ρ''は、２つの数字で表せるので２× log2 ｎ［bit］で表現でき、全体置換は、整数値ｄ（−ｎ < d < ｎ ）で表されるので、１＋log2 ｎ［bit］で表現できる。
このように、上記実施形態では、２２bit必要であった置換パターンを、全体置換と部分置換とに分解して表現することにより、１３bitに圧縮できた。
なお、本変形例は任意のビット列に対して適用可能である。すなわち、ビット列を所定の置換に変換し、この置換を表現するデータ量が小さくなるように全体置換と部分置換に変換しているので、ラベル、識別子以外の情報を符号化することもできる。
【００６２】
図１１は、置換とインデックスの１対１対応の例として、５次の対称群(Ｓ５)の辞書式順序によるインデックスを示す。
例えば、符号化対象情報Ｉがビット列（110001）の場合、10進数で整数化すると49となるので、図１１より49をインデックスとする置換ρは、基準となる配列［ 0 1 2 3 4 ] を配列 [ 2 0 1 4 3 ] に置換するものとなる。
【００６３】
［復号化処理］
次に、第２の変形例における復号化処理を説明する。復号化処理は、上記符号化処理と逆の手順を辿る。
すなわち、復号化プログラムは、部分置換ρ''の符号と、最頻値dの符号とを復号化して、部分置換（巡回置換）ρ''と、全体置換（すなわち、最頻値ｄだけずらす置換）とを特定し、特定された部分置換（巡回置換）ρ''を基準となる配列順序に適用して、置換ρ'を再現し、再現された置換ρ'に対して全体置換（最頻値ｄだけずらす置換）を行う。具体的には、基本配列（０，１，２，・・・，ｎ−１）に対して部分置換ρ''を作用させて、置換ρ'をもとめ、以下の式のように、この置換ρ'の各項から最頻値ｄを減算して、置換ρを求める。
ρ(ｉ)＝(ρ'(ｉ)−d＋ｎ) mod n
さらにρに対応するインデックス情報（整数ｘ）から元の符号化対象情報が求められる（Ｉ＝ｆ−１（ｘ））。
【００６４】
ｎ＝１０の例では、符号データρ''＝(8 9)、ｄ＝１に対して、部分置換ρ''＝(8 9)を基準配列に作用させると、図１０（Ｂ）が再現される。
これから差分の最頻値dを減算して置換ρを求める。
ρ(0)＝(ρ'(0)−d＋10) mod 10＝(0−1＋10) mod 10＝9
ρ(1)＝(ρ'(1)−d＋10) mod 10＝(1−1＋10) mod 10＝0
ρ(2)＝(ρ'(2)−d＋10) mod 10＝(2−1＋10) mod 10＝1
ρ(3)＝(ρ'(3)−d＋10) mod 10＝(3−1＋10) mod 10＝2
ρ(4)＝(ρ'(4)−d＋10) mod 10＝(4−1＋10) mod 10＝3
ρ(5)＝(ρ'(5)−d＋10) mod 10＝(5−1＋10) mod 10＝4
ρ(6)＝(ρ'(6)−d＋10) mod 10＝(6−1＋10) mod 10＝5
ρ(7)＝(ρ'(7)−d＋10) mod 10＝(7−1＋10) mod 10＝6
ρ(8)＝(ρ'(8)−d＋10) mod 10＝(9−1＋10) mod 10＝8
ρ(9)＝(ρ'(9)−d＋10) mod 10＝(8−1＋10) mod 10＝7
以上により、図１０（Ａ）の置換パターンが再現される。
ρに対応する10次の対称群(Ｓ１０)の辞書式順序によるインデックスは3265921である。このインデックスをビット列で表すと（110001  11010101  10000001）となり、元の符号化対象情報Ｉが復号できた。なお、オブジェクトの配列情報の場合は置換パターンρの導出で十分である。
このように、第２の変形例によれば、ラベル、識別子以外の情報を符号化することができる。また、オブジェクト数ｎが大きくなっても、符号化処理による圧縮効果を維持できる。
【図面の簡単な説明】
【００６５】
【図１】マルチオブジェクト形式のデータファイルを例示する図である。
【図２】固有符号と順序符号とを比較する図である。
【図３】本発明にかかる符号化方法が適応される画像処理装置２のハードウェア構成を、制御装置２１を中心に例示する図である。
【図４】制御装置２１（図３）により実行され、本発明にかかる符号化方法を実現する符号化プログラム５の機能構成を例示する図である。
【図５】制御装置２１（図３）により実行される復号化プログラム６の機能構成を例示する図である。
【図６】順序識別子を説明する図である。
【図７】第２の符号化プログラム５２の機能構成を例示する図である。
【図８】符号化プログラム５２（図７）による符号化処理（Ｓ１０）のフローチャートである。
【図９】順序識別子を定義して符号化されたデータファイルを例示する図である。
【図１０】置換パターンの分解を説明するための図である。
【図１１】５次の対称群(Ｓ５)の辞書式順序によるインデックスを例示する図である。
【符号の説明】
【００６６】
２・・・画像処理装置
５，５２・・・符号化プログラム
５００・・・データ入力部
５１０・・・順序特定部
５２０・・・符号生成部
５３０・・・符号付与部
５４０・・・順序ＩＤ生成部
５５０・・・順序ＩＤ配列部
６・・・復号化プログラム
６００・・・符号入力部
６１０・・・総数特定部
６２０・・・符号表生成部
６３０・・・識別子復号部
６４０・・・オブジェクト特定部
【図１】
2007329904.tif 000003
【図２】
2007329904.tif 000004
【図３】
2007329904.tif 000005
【図４】
2007329904.tif 000006
【図５】
2007329904.tif 000007
【図６】
2007329904.tif 000008
【図７】
2007329904.tif 000009
【図８】
2007329904.tif 000010
【図９】
2007329904.tif 000011
【図１０】
2007329904.tif 000012
【図１１】
2007329904.tif 000013