(57)【要約】      （修正有）【課題】新しい圧縮方式を使用することにより、符号化されたデータと関連付けられたビットストリームのサイズ及び複雑さを最小限にする方法及びシステムを提供する。【解決手段】エントロピー符号器は、ラン／データ値の対のリストを受信し、且つラン値及びデータ値を別個にエントロピー符号化して長さ及び大きさのそれぞれに従ってラン値及びデータ値のコードワードを選択し、符号化されたビットストリームにおいて結果として得られるコードワード対、最初にランコードワードを連結する。【選択図】図１
2013138422.tif 000002
【特許請求の範囲】
【請求項１】
整数値データのストリームに対応するラン／データ値の対データをエントロピー符号化する方法であって、
長さに基づいて各ランを分類するステップと、
前記ランが１である場合、１の長さの第１のコードを選択するステップ、
前記ランが短いとして分類される場合、第１の所定の長さの第１のコードを選択するステップと、ここで、第１の所定の長さの第１のコードの各々が前記他のランの分類を区別するプリアンブルを有し且つ前記ランの長さに基づいた値を有する；
前記ランが長いとして分類される場合、第２の所定の長さの第１のコードを選択するステップと、ここで、第２の所定の長さの第１のコードの各々が前記他のランの分類を区別するプリアンブルを有し且つ前記ランの長さに基づいた値を有する；
前記選択された第１のコードをチャネルに出力するステップ
とを有することを特徴とする方法。
【請求項２】
前記データ値は、前記ストリームにおいて２つの隣接するデータ値から取得された差分データであることを特徴とする請求項１に記載の方法。
【請求項３】
前記選択された第１のコードを前記チャネルに出力する前に、前記チャネルに前記ラン／データ値の対において前記ランに対応する前記データ値の符号化された表現を出力することを更に含むことを特徴とする請求項１に記載の方法。
【請求項４】
大きさに基づいて各データ値を分類するステップと、
前記データ値が小さいとして分類される場合、第３の所定の長さの第２のコードを選択するステップと、ここで、第３の所定の長さの第２のコードの各々が大きいデータ値を区別するプリアンブルを有し且つ前記データ値に基づいた値を有する；
前記データ値が大きいとして分類される場合、第４の所定の長さの第２のコードを選択するステップと、ここで、第４の所定の長さの第２のコードの各々が小さいデータ値を区別するプリアンブルを有し且つ前記データ値に基づいた値を有する；
前記選択された第２のコードを前記チャネルに出力するステップ
とを更に含むことを特徴とする請求項１に記載の方法。
【請求項５】
短いランの長さは１より長く且つ所定の閾値以下であり、
長いランの長さは前記所定の閾値より長い
ことを特徴とする請求項１に記載の方法。
【請求項６】
前記ストリームはビデオを表すことを特徴とする請求項１に記載の方法。
【請求項７】
前記ストリームは画像を表すことを特徴とする請求項１に記載の方法。
【請求項８】
整数値データのストリームに対応するラン／データ値の対データをエントロピー符号化する方法であって、
大きさに基づいて各データ値を分類するステップと、
前記データ値が小さいとして分類される場合、第１の所定の長さの第１のコードを選択するステップと、ここで、第１の所定の長さの第１のコードの各々が大きいデータ値を区別するプリアンブルを有し且つ前記データ値に基づいた値を有する；
前記データ値が大きいとして分類される場合、第２の所定の長さの第１のコードを選択するステップと、ここで、第２の所定の長さの第１のコードの各々が小さいデータ値を区別するプリアンブルを有し且つ前記データ値に基づいた値を有する；
前記選択された第１のコードをチャネルに出力するステップと
を有することを特徴とする方法。
【請求項９】
前記データ値は、前記ストリームにおいて２つの隣接するデータ値から取得された差分データであることを特徴とする請求項８に記載の方法。
【請求項１０】
前記選択された第１のコードを前記チャネルに出力した後に、前記チャネルに前記ラン／データ値の対において前記データ値に対応する前記ランの符号化された表現を出力することを更に含むことを特徴とする請求項８に記載の方法。
【請求項１１】
長さに基づいて各ランを分類するステップと、
前記ランが１である場合、１の長さの第２のコードを選択するステップと；
前記ランが短いとして分類される場合、第３の所定の長さの第２のコードを選択するステップと、ここで、第３の所定の長さの第２のコードの各々が前記他のランの分類を区別するプリアンブルを有し且つ前記ランの長さに基づいた値を有する；
前記ランが長いとして分類される場合、第４の所定の長さの第２のコードを選択するステップと、ここで、第４の所定の長さの第２のコードの各々が前記他のランの分類を区別するプリアンブルを有し且つ前記ランの長さに基づいた値を有する；
前記選択された第２のコードを前記チャネルに出力するステップと
を更に含むことを特徴とする請求項８に記載の方法。
【請求項１２】
前記ストリームはビデオを表すことを特徴とする請求項８に記載の方法。
【請求項１３】
前記ストリームは画像を表すことを特徴とする請求項８に記載の方法。
【請求項１４】
小さいデータ値は、大きさが０より大きく且つ所定の閾値以下のデータ値であることを特徴とする請求項８に記載の方法。
【請求項１５】
整数値データのストリームに対応するラン／データ値の対データをエントロピー符号化する方法であって、
長さに基づいて各ランを分類するステップと、
前記ランが１である場合、単一のビットを含む第１のコードを選択するステップと、
前記ランが短いとして分類される場合、第１のコードブックからｎ＋１ビットを含む第１のコードを選択するステップと、ここで、前記選択された第１のコードが前記第１のビットに対する所定のプリアンブルを有し且つ前記残りのｎビットに対する値が前記ランの長さに基づく；
前記ランが長いとして分類される場合、第２のコードブックからｎ＋１＋Ｍビットを含む第１のコードを選択するステップと、ここで、前記選択された第１のコードが前記第ｎ＋１ビットに対する所定のプリアンブルを有し且つ前記残りのＭビットに対する値が前記ランの長さに基づく；
前記選択された第１のコードをチャネルに出力するステップと
を有することを特徴とする方法。
【請求項１６】
前記データ値は、前記ストリームにおいて２つの隣接するデータ値から取得された差分データであることを特徴とする請求項１５に記載の方法。
【請求項１７】
前記選択された第１のコードを前記チャネルに出力する前に、前記チャネルに前記ラン／データ値の対において前記ランに対応する前記データ値の符号化された表現を出力するステップを更に含むことを特徴とする請求項１５に記載の方法。
【請求項１８】
大きさに基づいて各データ値を分類するステップと、
前記データ値が小さいとして分類される場合、第３のコードブックからｋ＋２ビットを含む第２のコードを選択するステップと、ここで、前記選択された第２の符号が前記第１のビットに対する所定のプリアンブルを有し且つ前記残りのｋ＋１ビットに対する値が前記データ値に基づく；
前記データ値が大きいとして分類される場合、第４のコードブックからＮ＋１ビットを含む第２のコードを選択するステップと、ここで、前記選択された第２のコードが前記第１のビットに対する所定のプリアンブルを有し且つ前記残りのＮビットに対する値が前記データ値及びＮに基づく；
前記選択された第２のコードを前記チャネルに出力するステップと
を更に含むことを特徴とする請求項１５に記載の方法。
【請求項１９】
前記ストリームはビデオを表すことを特徴とする請求項１５に記載の方法。
【請求項２０】
前記ストリームは画像を表すことを特徴とする請求項１５に記載の方法。
【請求項２１】
短いランの長さは１より長く且つ２n以下であり、
長いランの長さは２nより長い
ことを特徴とする請求項１５に記載の方法。
【請求項２２】
短いとして分類されたランの場合、
前記所定のプリアンブルは「０」ビットであり、
前記残りのｎビットの前記値は、前記ランの長さより１小さいバイナリコードであることを特徴とする請求項１５に記載の方法。
【請求項２３】
長いとして分類されたランの場合、
前記所定のプリアンブルはｎ＋１個の「０」ビットであり；
前記残りのＭビットの前記値は、前記ランレングスより１小さいバイナリコードであることを特徴とする請求項１５に記載の方法。
【請求項２４】
ランの長さが２Mより長い場合にランを３つ以上のサブランに分裂するステップを更に含み、
前記各サブランの前記長さは２M以下であり、
前記第１のサブランと関連付けられた前記データ値は、前記ランと関連付けられた前記データ値に等しく、
前記第１のサブランの後に各サブランと関連付けられた前記データ値はゼロであることを特徴とする請求項１５に記載の方法。
【請求項２５】
整数値データのストリームに対応するラン／データ値の対データをエントロピー符号化する方法であって、
大きさに基づいて各データ値を分類するステップと、
前記データ値が小さいとして分類される場合、第１のコードブックからｋ＋２ビットを含む第１のコードを選択するステップと、ここで、前記選択された第１のコードが前記第１のビットに対する所定のプリアンブルを有し且つ前記残りのｋ＋１ビットに対する値が前記データ値に基づく；
前記データ値が大きいとして分類される場合、第２のコードブックからＮ＋１ビットを含む第１のコードを選択するステップと、ここで、前記選択された第１のコードが前記第１のビットに対する所定のプリアンブルを有し且つ前記残りのＮビットに対する値が前記データ値及びＮに基づく；
前記選択された第１のコードをチャネルに出力するステップと
を有することを特徴とする方法。
【請求項２６】
前記データ値は、前記ストリームにおいて２つの隣接するデータ値から取得された差分データであることを特徴とする請求項２５に記載の方法。
【請求項２７】
前記選択された第１のコードを前記チャネルに出力した後に、前記チャネルに前記ラン／データ値対において前記データ値に対応する前記ランの符号化された表現を出力するステップをを更に含むことを特徴とする請求項２５に記載の方法。
【請求項２８】
長さに基づいて各ランを分類するステップと、
前記ランが１である場合、単一のビットを含む第２のコードを選択するステップと、
前記ランが短いとして分類される場合、第３のコードブックからｎ＋１ビットを含む第２のコードを選択するステップと、ここで、前記選択された第２のコードが前記第１のビットに対する所定のプリアンブルを有し且つ前記残りのｎビットに対する値が前記ランの長さに基づく；
前記ランが長いとして分類される場合、第４のコードブックからｎ＋１＋Ｍビットを含む第２のコードを選択するステップと、ここで、前記選択された第１のコードが前記第１のｎ＋１ビットに対する所定のプリアンブルを有し且つ前記残りのＭビットに対する値が前記ランの長さに基づく；
前記選択された第２のコードを前記チャネルに出力するステップと
を更に含むことを特徴とする請求項２５に記載の方法。
【請求項２９】
前記ストリームはビデオを表すことを特徴とする請求項２５に記載の方法。
【請求項３０】
前記ストリームは画像を表すことを特徴とする請求項２５に記載の方法。
【請求項３１】
小さいデータ値は、大きさが０より大きく且つ２k以下のデータ値であることを特徴とする請求項２５に記載の方法。
【請求項３２】
小さいとして分類されたデータ値の場合、
前記所定のプリアンブルは「０」ビットであり、
前記残りのｋ＋１ビットの前記値は、前記データ値の前記絶対値より１小さいバイナリコードであり、前記データ値が正又は負であるかを示すために１ビットが使用されることを特徴とする請求項２５に記載の方法。
【請求項３３】
大きいとして分類されたデータ値の場合、
前記所定のプリアンブルは「１」ビットであり、
前記残りのＮビットの前記値は、前記データ値モジュロ２Nに対するバイナリコードであることを特徴とする請求項２５に記載の方法。
【請求項３４】
Ｎは前記データ値のワードサイズに等しいことを特徴とする請求項２５に記載の方法。
【請求項３５】
整数値データのストリームに対応するラン／データ値の対データのリストをエントロピー符号化するシステムであって、
前記リストを受信するための入力を有するエントロピー符号器を備え、当該エントロピー符号器は、
ラン／データ値の対の前記リストをランコードワード／データ値コードワードの対のリストにエントロピー符号化し、前記ランが前記データ値から別個に符号化され、
全てのランコードワード／データ値コードワードの対に対して、前記データ値コードワードを対応するランコードワードと連結することにより符号化されたビットストリームを生成し、前記データ値コードワードが前記符号化されたビットストリームにおいて前記ランコードワードの前に現れるようにすることを特徴とするシステム。
【請求項３６】
前記データ値は、前記ストリームにおいて２つの隣接するデータ値から取得された差分データであることを特徴とする請求項３５に記載のシステム。
【請求項３７】
前記符号化されたビットストリームはチャネルに出力されることを特徴とする請求項３５に記載のシステム。
【請求項３８】
各ランコードワードは前記ランの長さに基づくことを特徴とする請求項３５に記載のシステム。
【請求項３９】
前記ランの前記長さが１である場合、前記ランコードは単一のビットを含み、
前記ランの前記長さが短い場合、前記ランコードワードは、前記第１のビットに対する所定のプリアンブルを有し且つ前記残りのｎビットに対する値が前記ランの長さに基づくｎ＋１ビットを含み、
前記ランの前記長さが長い場合、前記ランコードワードは、前記第１のｎ＋１ビットに対する所定のプリアンブルを有し且つ前記残りのＭビットに対する値が前記ランの長さに基づくｎ＋１＋Ｍビットを含む
ことを特徴とする請求項３５に記載のシステム。
【請求項４０】
各データ値コードワードは前記データ値の大きさに基づくことを特徴とする請求項３５に記載のシステム。
【請求項４１】
前記データ値の前記大きさが小さい場合、前記データ値コードワードは、前記第１のビットに対する所定のプリアンブルを有し且つ前記残りのｋ＋１ビットに対する値が前記データ値に基づくｋ＋２ビットを含み、
前記データ値の前記大きさが大きい場合、前記データ値コードワードは、前記第１のビットに対する所定のプリアンブルを有し且つ前記残りのＮビットに対する値が前記データ値及びＮに基づくＮ＋１ビットを含み、
前記データ値がゼロである場合、前記データ値コードワードは、前記第１のビットに対する所定のプリアンブルを有し且つ前記残りのＮビットに対する値が前記データ値及びＮに基づくＮ＋１ビットを含む
ことを特徴とする請求項４０に記載のシステム。
【請求項４２】
コンピュータにより実行された場合に、整数値データのストリームに対応するラン／データ値の対データをエントロピー符号化する方法を実行させる命令のセットで符号化されたコンピュータ可読媒体であって、前記方法は、
長さに基づいて各ランを分類するステップと、
前記ランが１である場合、１の長さの第１のコードを選択するステップと、
前記ランが短いとして分類される場合、第１の所定の長さの第１のコードを選択するステップと、ここで、第１の所定の長さの第１のコードの各々が前記他のランの分類を区別するプリアンブルを有し且つ前記ランの長さに基づいた値を有する；
前記ランが長いとして分類される場合、第２の所定の長さの第１のコードを選択するステップと、ここで、第２の所定の長さの第１のコードの各々が前記他のランの分類を区別するプリアンブルを有し且つ前記ランの長さに基づいた値を有する；
前記選択された第１のコードをチャネルに出力するステップと
を含むことを特徴とするコンピュータ可読媒体。
【請求項４３】
コンピュータにより実行された場合に、整数値データのストリームに対応するラン／データ値の対データをエントロピー符号化する方法を実行させる命令のセットで符号化されたコンピュータ可読媒体であって、前記方法は、
長さに基づいて各ランを分類するステップと、
前記ランが１である場合、単一のビットを含む第１のコードを選択するステップと、
前記ランが短いとして分類される場合、第１のコードブックからｎ＋１ビットを含む第１のコードを選択するステップと、ここで、前記選択された第１のコードが前記第１のビットに対する所定のプリアンブルを有し且つ前記残りのｎビットに対する値が前記ランの長さに基づく；
前記ランが長いとして分類される場合、第２のコードブックからｎ＋１＋Ｍビットを含む第１のコードを選択するステップと、ここで、前記選択された第１のコードが前記第ｎ＋１ビットに対する所定のプリアンブルを有し且つ前記残りのＭビットに対する値が前記ランの長さに基づく；
前記選択された第１のコードをチャネルに出力するステップと
を含むことを特徴とするコンピュータ可読媒体。
【請求項４４】
コンピュータにより実行された場合に、整数値データのストリームに対応するラン／データ値の対データをエントロピー符号化する方法を実行する命令のセットで符号化されたコンピュータ可読媒体であって、前記方法は、
大きさに基づいて各データ値を分類するステップと、
前記データ値が小さいとして分類される場合、第１の所定の長さの第１のコードを選択するステップと、ここで、第１の所定の長さの第１のコードの各々が大きいデータ値を区別するプリアンブルを有し且つ前記データ値に基づいた値を有する；
前記データ値が大きいとして分類される場合、第２の所定の長さの第１のコードを選択するステップと、ここで、第２の所定の長さの第１のコードの各々が小さいデータ値を区別するプリアンブルを有し且つ前記データ値に基づいた値を有する；
前記選択された第１のコードをチャネルに出力するステップと
を含むことを特徴とするコンピュータ可読媒体。
【請求項４５】
コンピュータにより実行された場合に、整数値データのストリームに対応するラン／データ値の対データをエントロピー符号化する方法を実行させる命令のセットで符号化されたコンピュータ可読媒体であって、前記方法は、
大きさに基づいて各データ値を分類するステップと、
前記データ値が小さいとして分類される場合、第１のコードブックからｋ＋２ビットを含む第１のコードを選択するステップと、ここで、前記選択された第１のコードが前記第１のビットに対する所定のプリアンブルを有し且つ前記残りのｋ＋１ビットに対する値が前記データ値に基づく；
前記データ値が大きいとして分類される場合、第２のコードブックからＮ＋１ビットを含む第１のコードを選択するステップと、ここで、前記選択された第１のコードが前記第１のビットに対する所定のプリアンブルを有し且つ前記残りのＮビットに対する値が前記データ値及びＮに基づく；
前記選択された第１のコードをチャネルに出力するステップと
を含むことを特徴とするコンピュータ可読媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、整数値データのストリームを圧縮するシステム及び方法に関する。
【背景技術】
【０００２】
例えばビデオ、画像等を表している整数値ビットストリームを符号化する種々の符号化方式が既知である。既知の符号化方式は、一般に、ランレングス符号化、可変長符号化、差分符号化及びそれらの種々の組合せを含む。
【０００３】
ランレングス符号化は、顕著な均一性を示すデータを圧縮するのに有用であるが、一般に、データ値が次々に異なる可能性の高い場合には非効率的である。後者の場合、ランレングス符号化と他のいくつかの種類の符号化との間で適応可能に切り替えることは、既知の圧縮方式の中では一般的である。切り替えは、一般に、ビットストリームと関連付けられた副情報又は計算により復号器において処理される。これにより、それぞれ、圧縮効率が低下するか又は計算の負荷が増加する。
【０００４】
ランレングス符号化の前に差分符号化を実行するためにランレングス符号化及び差分符号化を使用することは、既知の圧縮方式の中では一般的である。順序付けは、ビットストリームにおいて全てのデータ値に対して符号器が差分を計算し、復号器が和を計算する（すなわち、データ値を再構成する）ことを要求する。
【発明の概要】
【発明が解決しようとする課題】
【０００５】
従って、これらの既知の制限を除去するか、あるいはどんなに少なくとも緩和する符号化方式を使用するのが望ましい。
【図面の簡単な説明】
【０００６】
【図１】図１は、本発明の一実施形態に従って整数値データのストリームを符号化する方法を示す図である。
【図２】図２は、本発明の一実施形態に従ってラン／データ値対のリストを符号化する方法を示す図である。
【図３】図３は、例示的な整数値データのストリーム及びそれと関連付けられたランを示す図である。
【図４】図４は、本発明の一実施形態に係る符号器−復号器システムを示す図である。
【発明を実施するための形態】
【０００７】
本発明の実施形態は、新しい圧縮方式を使用することにより、符号化されたデータと関連付けられたビットストリームのサイズ及び複雑さを低減する。エントロピー符号器は、ラン／データ値の対のリストを受信し、且つラン及びデータ値を別個にエントロピー符号化して長さ及び大きさのそれぞれに従ってそれらのコードワードを選択し、符号化されたビットストリームにおいて結果として得られるコードワード対、最初にデータ値コードワードを連結する。符号化方式により、画像、ビデオ等を表す符号化されたビットストリームのサイズ及び複雑さを低減する。従って、ビットストリームはより少ない帯域幅で送信されてもよく、符号器及び復号器の双方への計算の負荷が減ってもよい。
【０００８】
図１は、本発明の一実施形態に従ってビットストリームを符号化する方法を示す。実施形態によると、方法は、所定の走査方向に従ってデータ値のアレイを走査する（ボックス１００）。方法は、アレイからのデータ値を一連のラン／データ値の対（つい）に変換する（ボックス１１０）。ボックス１２０において、ランの値に基づいてコードワードを選択する。同様に、ボックス１３０において、データ値の値に基づいてコードワードを選択する。ステップ１２０又はステップ１３０、あるいは双方のいずれかを実行してもよい。符号化されたラン／データ値データを符号化されたデータ対に連結する（ボックス１４０）。その後、データは、送信のために更に処理される。
【０００９】
具体的には、ブロック１００において、走査方向に従って、例えば画像、ビデオ等を表すソースデータのアレイを走査してもよい。種々のサイズ及び構成のデータアレイに適応してもよい。走査方向に従って考慮される場合に整数の多次元アレイがリニアアレイとして考えられてもよいため、本発明の説明はリニアアレイの例を扱うことが理解されるだろう。
【００１０】
ブロック１１０において、データ値の１次元アレイは、ランレングス符号化を使用してラン／データ値の対のリストに変換されてもよい。ここで、対の一方の整数（一般に、第１の整数）はランの長さであり、他方の整数（一般に、第２の整数）は対応するランを含むデータの値である。例えば、図３において示されるように、１次元アレイが１０個の要素、すなわち｛０、０、０、３、３、２、２、２、２、２｝から構成される場合、これらの１０個の要素は、以下の対、すなわち｛（３、０）、（２、３）、（５、２）｝に変換されるだろう。結果として得られる対は、０である３個の値、３である２個の値、及び、２である５個の値からそのような順序で構成されたことを示す。
【００１１】
一実施形態において、結果として得られるラン／データ値の対のリストは、ブロック１１０において、ラン／データ値の差分の対のリストに差分符号化されてもよい。上記において１０個の要素アレイが使用された例に戻ると、結果として得られるラン／データ値の差分の対のリストは、｛（３、＋１）、（２、＋３）、（５、−１）｝から構成される。ここで、［０−（−１）＝＋１］、［３−０＝＋３］及び［２−３＝−１］である。通常の状況下では、データ値差分はゼロにならないため、最初のランの先行ラン値を−１として処理することにより（上記の例において示されたように）先行ランに継続することを示し、非ゼロデータ値差分は保証されるだろう（本明細書において詳細に説明されるように、ランがサブランに分割されない限り）。
【００１２】
差分符号化の前にランレングス符号化を実行することにより、差分（符号器）又は和（復号器）は、全てのデータ値毎に１回ではなくラン毎に１回だけ計算される必要がある。このような順序付けの区別は、復号器において特に有用となる。この場合、このような順序付けの区別により、必要な計算量を減少するだけでなく、関連付けられたあらゆる十二音技法（serialism）を除去し、ランの同一のデータ値のうちのいくつかが同時に出力されるようにする。
【００１３】
上述したように、本発明の原理により、差分データ値及び非差分データ値の双方を使用してアプリケーションを発見する。従って、以下において指定されない限り、以下の説明は、包括的な意味で「データ値」を示し、差分データ値及び非差分データ値を同等に示す。
【００１４】
ブロック１２０、１３０において、結果として得られるラン／データ値の対のリストはエントロピー符号化される。ランはデータ値から別個に符号化されてもよく、そのような符号化は直列に（例えば、データ値の前のラン等）又は並列に実行されてもよい。本発明の実施形態により、本明細書において提案されたコードブックに基づくエントロピー符号化が要望に応じて他の符号化方式と共に使用される。例えば、本発明の説明は、図２に関して以下に概略的に示される処理に従ってラン値及びデータ値の双方を符号化することを提案するが、提案された方式に従って一方のデータの種類（例えば、ラン）のみを符号化し且つ別の機構に従って他方のデータの種類（例えば、データ値）を符号化できる。従って、本発明の原理は、要望に応じて他の符号化機構と統合されてもよい。
【００１５】
ラン値及びデータ値がエントロピー符号化された後、ブロック１４０において示されるように、ランコードワード／データ値のリストは連結されてもよく（すなわち、対毎に、結果として得られるデータ値コードワードは、結果として得られるランコードワードと連結される）、これらの連結されたコードワードは、最後の符号化されたビットストリームを共に形成する。対応するランコードワードの前にデータ値コードワードを入れることにより、データ値は、復号化中に、すなわちそのデータ値のランの長さを判定する前に再構成される。それにより、特定のラン値の専用のランレングス復号化が可能になる。例えば、ランコードワード復号化中にランが１であると判定される場合、データ値が既に復元されているために単一のデータ値が出力されることにより、ループを実行する必要はないか、さもなければ一般的な状況に適応しようとする必要がある。これは、計算オーバヘッドが処理から多少除去されることを意味する。
【００１６】
図２は、本発明の一実施形態に従ってエントロピー符号化の方法を示す。ブロック２００においてラン／データ値の対が受信され、ブロック２０５において各対内のランが所定の最大ランレングス内にあるかを確認する。ランは、整数であり、１からソースアレイのサイズの範囲である。エントロピー符号化するために、ランレングスは、例えば２Mの上限を有してもよい。ここで、Ｍは、ランコードワードのサイズが有限であることを保証するために使用された一般的なパラメータである。例えば、画像に対して、Ｍは、ランがサブランに分解されなくてもよいように画像のサイズに比例してもよい。
【００１７】
ランは、２Mより長い場合、各サブランが２M以下であるようにサブランに分裂されてもよい。ランがサブランに分裂される場合、第１のサブランは、ランがサブランに分割されなかったかのように同一のデータ値を取得し、後続のサブランの各々はゼロのデータ値を取得する。例えば、ラン／データ値の対（２１、＋２）について考察する。ここで、Ｍ＝３とする。この場合、ランが８より長くない（すなわち、２M＝２3＝８）ため、結果として得られるサブラン／データ値の対は、｛（８、＋２）、（８、０）、（５、０）｝（すなわち、８＋８＋５＝２１）となる。
【００１８】
それらの長さに依存して、ラン又はサブランは、ブロック２１０〜２２５において示されるように、３つの方法のうちの１つで符号化されてもよい。ブロック２１０において、ランは、「短い」又は「長い」のいずれか一方として分類される。１のランは、ブロック２１５により示されるように、単一の「１」ビットとして符号化されてもよい。１のランに対して単一のビットを使用することにより、隣接するデータ値が同一でない場合に圧縮効率への影響を最小限にし、復号器が１の符号化されたランと１より大きい符号化されたランとを区別するために符号テストを使用できるという計算上の利点を有する。
【００１９】
「短い」ランは、１より大きいが、所定の閾値２n以下であるランを含んでもよい。ここで、ｎは、任意に選択されるか又は圧縮されるデータに対して最適な圧縮を達成しようとする方式等を含む多数の所定の方式のうちのいずれかに従って選択されてもよい。短いランは、ブロック２２０により示されるように、単一の「０」ビットのプリアンブル及びそれに後続するラン値より１小さいｎビットの固定長バイナリコードから構成されるｎ＋１ビットで符号化されてもよい。
【００２０】
「長い」ランは、２nより大きいこれらのランを含んでもよい。長いランは、ブロック２２５により示されるように、ｎ＋１個の「０」ビットのプリアンブル及びそれに後続するラン値より１小さいＭビットの固定長バイナリコードから構成されるｎ＋１＋Ｍビットで符号化されてもよい。
【００２１】
尚、「短い」ラン及び「長い」ランの双方に対するコードワードは、ラン値より１小さい適切な長さの固定長バイナリコードである。説明された方式に係るランコードブックの一例として、テーブル１を考える。テーブル１は、ランの最大レングスが２０４８（すなわち、２11＝２０４８）であり、且つ「短い」ランが２と１６間（すなわち、２4＝１６）のランであるように、Ｍ＝１１及びｎ＝４のランコードブックを示す。
【００２２】
【表１】
2013138422.tif 000003
【００２３】
データ値は、大きさに依存して２つの方法のうちの１つで符号化されてもよい。ブロック２３０において示されるように、データ値は、絶対値に従って「小さい」又は「大きい」のいずれかとして分類される。これにより、単一のプレフィックスビットは２つの場合を区別できる。その結果、データ値コードワードを復号化する際、コードワードの第１のビットがコンピュータのワードの最も重要なビットに現れる場合、データ値が小さいか又は大きいかを判定するために簡単な符号テスト（ゼロと比較して）が実行されてもよい。
【００２４】
「小さい」データ値は、０より大きいが２k以下である大きさ（すなわち、絶対値）のこれらのデータ値を含んでもよい。ここで、ｋは、任意に選択されるか又は圧縮されるデータに対して最適な圧縮を達成しようとする方式等を含む多数の所定の方式のうちのいずれかに従って選択されてもよい。小さいデータ値は、ブロック２３５により示されるように、単一の「０」ビットのプリアンブル、データ値の大きさより１小さいｋビットの固定長バイナリコード及び差分符号を示す単一のビットから構成されるｋ＋２ビットで符号化される。
【００２５】
「大きい」データ値は、０であるか又は２kより大きいかのいずれかである大きさのこれらのデータ値を含んでもよい。大きいデータ値は、ブロック２４０により示されるように、データ値モジュロ２Nが後続する単一の「１」ビットのプリアンブルから構成されるＮ＋１ビットで符号化されてもよい。
【００２６】
説明された方式に係るデータ値コードブックの一例として、テーブル２を考える。テーブル２は、ｋ＝３及びＮ＝８であるデータ値コードブックを示す。ここで、１の符号ビットは、コードブックが５１２個のエントリ（すなわち、２＊２8＝５１２）を含むように、負のデータ値を示すために使用される。
【００２７】
【表２】
2013138422.tif 000004
【００２８】
変数ｎ（ランのエントロピー符号化と関連付けられた）及びｋ（データ値のエントロピー符号化と関連付けられた）は、おそらく符号器により符号化されてもよい種類のもの（例えば、写真、ビデオ等）を表す例示的なデータから収集された統計情報に基づいてもよい。
【００２９】
図４は、本発明の一実施形態に係る符号器４００及び復号器５００を示す。符号器４００は、本明細書において詳細に説明されるように、ハードウェア又はソフトウェアで実現されてもよく、ソースデータ４１０、整数値データの１次元アレイを受信する。ソースデータ４１０は、一般に本発明にとって重要でないソース処理動作（例えば、ビデオ符号化処理、オーディオ符号化処理等）を含む種々の他の符号化処理の結果であってもよい。
【００３０】
ラン／データ値符号器４２０は、ソースデータ４１０をラン／データ値の対のリストにランレングス符号化してもよい。エントロピー符号器４４０は、ラン／データ値符号器４２０からラン／データ値の対のリストを受信してもよく、本明細書において詳細に説明された処理に従ってラン値及びデータ値を符号化してもよい。エントロピー符号器４４０は、符号化されたビットストリームを形成するように、リストにおいて各対を含む結果として得られるコードワード、符号化されたデータ値を最初に連結してもよい。一実施形態において、架空で示されるように、ラン／データ値差分符号器４３０は、ラン／データ値符号器４２０からラン／データ値対のリストを受信してもよく、その対をラン／データ値の差分対のリストに差分符号化してもよい。これは、エントロピー符号器４４０により処理されてもよい。
【００３１】
送信バッファ４５０は、符号化されたビットストリームをチャネルに転送する前にそれを格納してもよい。チャネルは、符号化されたビットストリームを復号器に搬送する送信媒体を示してもよい。チャネルは、一般に、例えば通信ネットワーク又はコンピュータネットワークにより提供された光メモリ、磁気メモリ又は電気メモリ等の記憶装置及び通信チャネルを含む。
【００３２】
上述の符号化処理は、受信バッファ５１０、エントロピー復号器５２０、ラン／データ値差分復号器５３０、ラン／データ値復号器５４０及び復元されたデータストア５５０を含んでもよい復号器５００において逆方向に実行される。各ユニットは、符号器４００において対応するユニットの逆のことを実行するもので、ソースデータ４１０を複製する。復号器５００は、符号器４００において適用されたソース符号化処理を一致させるようにソース復号化を実行する他のブロック（不図示）を含んでもよい。
【００３３】
先行の明細書は種々の実施形態の詳細な説明を示すが、本発明の法的な範囲は以下に示す請求の範囲の用語により規定されることが理解されるべきである。詳細な説明は、単なる例として解釈されるべきであり、考えられる全ての実施形態を説明することは不可能ではないが非現実的であるため、本発明の考えられる全ての実施形態を説明しない。現在の技術又は依然として本発明を規定する請求の範囲の範囲内のこの特許の出願日の後に開発された技術のいずれかを使用して、多くの他の実施形態が実現されてもよい。
【００３４】
当業者には容易に明らかとなるように、本発明の他の変形及び変更の実現例、並びに種々の態様が存在し、且つ本発明は本明細書において説明された特定の実施形態により制限されないことが理解されるべきである。従って、本明細書において開示され且つ請求された基礎となる基本原理の範囲内の変更、変形又は等価物のいずれか及び全てを範囲に含むことが考えられる。
【図１】
2013138422.tif 000005
【図２】
2013138422.tif 000006
【図３】
2013138422.tif 000007
【図４】
2013138422.tif 000008
【手続補正書】
【提出日】平成25年1月15日(2013.1.15)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
整数値データのストリームに対応するラン／データ値の対データをエントロピー符号化する方法であって、
各データ値を、当該データ値の大きさに基づいて分類するステップと、
前記データ値が小さいと分類された場合、第１の所定長の第１のコードを選択するステップと、ここで、前記第１の所定長の第１のコードそれぞれは、大きいデータ値と区別するプリアンブルを有し、且つ、そのデータ値に基づいた値を有する；
前記データ値が大きいと分類された場合、第２の所定長の第１のコードを選択するステップと、ここで、前記第２の所定長の第１のコードそれぞれは、小さいデータ値と区別するプリアンブルを有し、且つ、そのデータに基づいた値を有する；
前記選択された第１のコードをチャネルに出力するステップと
とを有することを特徴とする方法。
【請求項２】
前記データ値は、前記ストリームにおいて２つの隣接するデータ値から取得された差分データであることを特徴とする請求項１に記載の方法。
【請求項３】
前記選択された第１のコードを前記チャネルに出力した後に、前記チャネルに前記ラン／データ値の対において前記データ値に対応する前記ランの符号化された表現を出力するステップを更に含むことを特徴とする請求項１に記載の方法。
【請求項４】
各ランをその長さに基づいて分類するステップと、
前記ランが１である場合、１の長さの第２のコードを選択するステップ、
前記ランが短いとして分類される場合、第３の所定長の第２のコードを選択するステップと、ここで、前記第３の所定長さの第２のコードの各々が前記他のランの分類を区別するプリアンブルを有し且つ前記ランの長さに基づいた値を有する；
前記ランが長いとして分類される場合、第４の所定長の第２のコードを選択するステップと、ここで、前記第４の所定の長さの第２のコードの各々が前記他のランの分類を区別するプリアンブルを有し且つ前記ランの長さに基づいた値を有する；
前記選択された第２のコードをチャネルに出力するステップ
とを有することを特徴とする請求項１に記載の方法。
【請求項５】
前記ストリームはビデオを表すことを特徴とする請求項１に記載の方法。
【請求項６】
前記ストリームは画像を表すことを特徴とする請求項１に記載の方法。
【請求項７】
小さいデータ値はその大きさがゼロより大きく、且つ、所定の閾値以下であることを特徴とする請求項１に記載の方法。
【請求項８】
前記データ値が小さいとして分類される場合の前記第１のコードは第１のコードブックからｋ＋２ビットを有し、ここで、前記選択された第１のコードは、最初のビットについては所定のプリアンブルを有し、残りのｋ＋１ビットは前記データ値に基づき、
前記データ値が大きいとして分類される場合の第１のコードは第２のコードブックからＮ＋１ビットを有し、ここで前記選択された第１のコードは、最初のビットについては所定のプリアンブルを有し、残りのＮビットは前記データ値及びＮに基づく
ことを特徴とする請求項１に記載の方法。
【請求項９】
ランが短いと分類された場合の前記第２のコードは第３のコードブックからｎ＋１ビットを有し、前記選択された第２のコードは、最初のビットについては所定のプリアンブルを有し、残りのｎビットはランの長さに基づき、
ランが長いと分類された場合の前記第２のコードは第４のコードブックからｎ＋１＋Ｍビットを有し、前記選択された第１のコードは最初のｎ＋１ビットについては所定のプリアンブルを有し、残りのＭビットはランの長さに基づく
ことを特徴とする請求項４に記載の方法。
【請求項１０】
小さいデータ値は、その大きさがゼロより大きく、２kより小さいデータであることを特徴とする請求項１に記載の方法。
【請求項１１】
データ値が小さいと分類された場合、
前記所定のプリアンブルは“０”のビットであり、
残りのｋ＋１ビットの値は、そのデータ値の絶対値より１つ小さい２進コードであって、そのうちの１ビットはデータ値の正負を表わすために用いられる
ことを特徴とする請求項８に記載の方法。
【請求項１２】
前記データ値が大きいと分類された場合、
前記所定のプリアンブルは“１”のビットであり。
残りのＮビットの値は、そのデータ値についてのモジュロ２Nの２進コードである
ことを特徴とする請求項８に記載の方法。
【請求項１３】
前記Ｎは前記データ値のワードサイズに等しいことを特徴とする請求項８に記載の方法。
【請求項１４】
整数値データのストリームに対応するラン／データ値の対データのリストをエントロピー符号化するシステムであって、
前記リストを受信するための入力を有するエントロピー符号器を備え、当該エントロピー符号器は、
各データ値を、当該データ値の大きさに基づいて分類し、
前記データ値が小さいと分類された場合、第１の所定長の第１のコードを選択し、ここで、前記第１の所定長の第１のコードそれぞれは、大きいデータ値と区別するプリアンブルを有し、且つ、そのデータ値に基づいた値を有する；
前記データ値が大きいと分類された場合、第２の所定長の第１のコードを選択し、ここで、前記第２の所定長の第１のコードそれぞれは、小さいデータ値と区別するプリアンブルを有し、且つ、そのデータに基づいた値を有する；
前記選択された第１のコードをチャネルに出力する
ことを特徴とするシステム。
【請求項１５】
前記データ値は、前記ストリームにおいて２つの隣接するデータ値から取得された差分データであることを特徴とする請求項１４に記載のシステム。
【請求項１６】
符号化されたビットストリームは、チャネルに出力されることを特徴とする請求項１４に記載のシステム。
【請求項１７】
各ランコードワードは、そのラン長に基づくことを特徴とする請求項１４に記載のシステム。
【請求項１８】
前記エントロピー符号器は、
各ランをその長さに基づいて分類し、
前記ランが１である場合、１の長さの第２のコードを選択し、
前記ランが短いとして分類される場合、第３の所定長の第２のコードを選択し、ここで、前記第３の所定長さの第２のコードの各々は前記他のランの分類を区別するプリアンブルを有し且つ前記ランの長さに基づいた値を有する；
前記ランが長いとして分類される場合、第４の所定長の第２のコードを選択し、ここで、前記第４の所定の長さの第２のコードの各々が前記他のランの分類を区別するプリアンブルを有し且つ前記ランの長さに基づいた値を有する；
前記選択された前記第２のコードをチャネルに出力する
ことを特徴とする請求項１４に記載のシステム。
【請求項１９】
各データ値コードワードは、前記データ値の大きさに基づくことを特徴とする請求項１４に記載のシステム。
【請求項２０】
前記データ値の大きさが小さい場合、前記データ値コードワードはｋ＋２ビットを有し、ここで最初のビットは所定のプリアンブルであり、残りのｋ＋１ビットは前記データ値に基づく、
前記データ値の大きさが大きい場合、前記データ値コードワードはＮ＋１ビットを有し、ここで最初のビットは所定のプリアンブルであり、残りのＮビットは前記データ値及びＮに基づく、
前記データ値が０の場合、前記データ値コードワードはＮ＋１ビットを有し、ここで、最初のビットは所定のプリアンブルであり、残りのＮビットは前記データ値及びＮに基づく
ことを特徴とする請求項１４に記載のシステム。
【請求項２１】
ランが短いと分類された場合の前記第２のコードは、第３のコードブックからｎ＋１ビットを有し、前記選択された第２のコードは、その最初のビットが所定のプリアンブルであり、残りのｎビットはランの長さに基づく、
ランが長いと分類された場合の第２のコードは、第４のコードブックからｎ＋１＋Ｍビットを有し、選択された第１のコードは、その最初のｎ＋１ビットが所定のプリアンブルであり、残りのＭビットはランの長さに基づく
ことを特徴とする請求項１８に記載のシステム。
【請求項２２】
コンピュータによって実行させた場合、整数値データのストリームに対応するラン／データ値の対データをエントロピー符号化する方法をコンピュータに実行させるための命令のセットを有する、コンピュータ可読記憶媒体であって、
各データ値を、当該データ値の大きさに基づいて分類するステップと、
前記データ値が小さいと分類された場合、第１の所定長の第１のコードを選択するステップと、ここで、前記第１の所定長の第１のコードそれぞれは、大きいデータ値と区別するプリアンブルを有し、且つ、そのデータ値に基づいた値を有する；
前記データ値が大きいと分類された場合、第２の所定長の第１のコードを選択するステップと、ここで、前記第２の所定長の第１のコードそれぞれは、小さいデータ値と区別するプリアンブルを有し、且つ、そのデータに基づいた値を有する；
前記選択された第１のコードをチャネルに出力するステップ
を実行させるための命令セットを記憶したコンピュータ可読記憶媒体。
【請求項２３】
前記データ値が小さいとして分類される場合、第１のコードブックからｋ＋２ビットを有する第１のコードを選択し、ここで、前記選択された第１のコードは、最初のビットについては所定のプリアンブルを有し、残りのｋ＋１ビットは前記データ値に基づき、
前記データ値が大きいとして分類される場合、第２のコードブックからＮ＋１ビットを有する第１のコードを選択し、ここで前記選択された第１のコードは、最初のビットについては所定のプリアンブルを有し、残りのＮビットは前記データ値及びＮに基づく、
そして、選択された前記第１のコードをチャネルに出力する
ことを特徴とする請求項２２に記載のコンピュータ可読記憶媒体。
【手続補正書】
【提出日】平成25年1月22日(2013.1.22)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】請求項１０
【補正方法】変更
【補正の内容】
【請求項１０】
小さいデータ値は、その大きさがゼロより大きく、２k以下のデータであることを特徴とする請求項１に記載の方法。
【外国語明細書】
2013138422000001.pdf