(57)【特許請求の範囲】
【請求項１】
入力画像にテキストメッセージを透かし入れする方法であって、
（ａ）前記テキストメッセージを論理0のデータビットおよび論理1のデータビットのバイナリーコードのデータビットシーケンスに転換し、前記バイナリーコードのデータビットシーケンスを非データのマーカービットからなるブロック境界で定義されるメッセージブロック内に配列するステップと、
（ｂ）前記バイナリーコードのデータビットシーケンス内の論理0のデータビットに第1ビットパターン記号を割り当てるステップであって、前記第1ビットパターン記号は、中心が同心となる第１の正方形輪郭および第２の正方形輪郭から第１の角領域を欠損させた三角形輪郭となるよう並べられたばらばらの矩形切片の第1の予め定義された幾何学的配列であるステップと、
（ｃ）前記バイナリーコードのデータビットシーケンス内の論理1のデータビットに第2ビットパターン記号を割り当て、前記第2ビットパターン記号を前記非データのマーカービットに割り当てるステップであって、前記第2ビットパターン記号は、中心が同心となる第１の正方形輪郭および第２の正方形輪郭から第２の角領域を欠損させた三角形輪郭となるよう並べられたばらばらの矩形切片の第2の予め定義された幾何学的配列であるステップと、
（ｄ）複数の前記メッセージブロックを前記入力画像にマッピングし、前記マッピングに従い前記第1および第2ビットパターン記号を前記入力画像に書き込むステップと、を有する入力画像にテキストメッセージを透かし入れする方法。
【請求項２】
前記三角形輪郭は各々直列に配列された前記ばらばらの矩形切片の集まりからなる2つの同心の部分的な正方形輪郭から形成され、前記ばらばらの矩形切片は長さが幅より長く、
各部分的な正方形輪郭は部分的正方形輪郭の共通斜辺に沿った角領域が1つ欠損しており、各欠損角領域は各々の部分的正方形輪郭の半分未満で、各々の欠損領域に隣接する各同心の正方形輪郭の2つの角は角が欠損している領域に部分的に及ぶ、請求項1に記載の入力画像にテキストメッセージを透かし入れする方法。
【請求項３】
前記ステップ（ａ）は
連続するメッセージブロックの頭を交互に1または2行の論理0ビットで引き延ばすステップと、
固定ビット長の予め定義されたデータビットシーケンスを前記バイナリーコードのデータビットシーケンスの第1データビットのすぐ前に挿入するステップと、を含む、請求項1に記載の入力画像にテキストメッセージを透かし入れする方法。
【請求項４】
前記入力画像の正しい配向は前記入力画像を0度から90度、270度、360度と移動させて4つの配向に配置し、各配向において再生できる有効なビットパターンの数を判定することにより判断され、最多数の有効なビットパターンを具現する配向が前記正しい配向とみなされる請求項1に記載の入力画像にテキストメッセージを透かし入れする方法。
【請求項５】
前記バイナリーコードのデータビットシーケンスはすべてのメッセージブロック内の対応位置からすべての論理0ビットおよび論理1ビットを集め、論理0または論に1と識別できないビット位置を未知と特定し、未知と特定されたビット位置を無視しながら各ビット位置における支配的データビットを特定し、各ビット位置のその支配的データビット値を割り当てることにより判定可能である、請求項1に記載の入力画像にテキストメッセージを透かし入れする方法。
【請求項６】
前記データビットおよびマーカービットは前記入力画像の背景区域にのみ書き込まれる
請求項1に記載の入力画像にテキストメッセージを透かし入れする方法。
【請求項７】
隣接する矩形切片間の間隔は透かし入り画像に印刷およびスキャン操作を受けさせると
複数の矩形切片が部分的につながり合成形状を形成するように選択される、請求項1に記載の入力画像にテキストメッセージを透かし入れする方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明はスキャンされた画像に透かしを入れる分野に向けられ、具体的に入力画像に透かしコードを挿入し、入力画像から透かしコードを抽出することに向けられる。
【背景技術】
【０００２】
可視透かしはユーザー提供の画像（すなわち入力画像）にビット符号化文字列からなるメッセージを、入力画像を印刷する前にかぶせる技術である。得られる印刷されたページは透かし入りの画像で、秘密または隠された透かしメッセージで透かし入りされたとされる。このような符号化の背後にある主要な動機は、透かしメッセージが正しく符号化された場合、前以て印刷された透かし入りの画像のスキャンから抽出できることである。
【０００３】
可視透かし機構はネットワークプリンターから印刷する際文書にユーザーIDを符号化させること、印刷の日付と時間を印刷文書に目立たぬよう配置すること、等々など、多数のシナリオにおいて有用であり得る。
【０００４】
透かしメッセージは出力画像にかぶせたテキストメッセージとして組み入れることができるが、透かしメッセージが出力画像を何気なく見る者により簡単に認識できないことが好ましい。すなわちテキスト文字は自由に読め、何気なく見る者にとって邪魔になり、何気なく見る者の注意を出力画像自体からそらす可能性が高いので、透かしメッセージがテキスト文字を用いて印刷されないことが通常好ましい。従って、何気なく見る者が簡単に認識できない符号化機構を用いて透かしメッセージをまず符号化し、次に符号化メッセージを出力画像にかぶせることが通例である。符号化メッセージは何気なく見る者にとって当たり障りなく、出力画像の主題から注意をそらさないことが好ましい（例えば特許文献１参照）。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】米国特許第７１０３２３０号明細書
【発明の概要】
【発明が解決しようとする課題】
【０００６】
メッセージを符号化する代表的な方法は標準ASCIIコードを使用することで、これは技術上知られているようにテキスト文字毎に別個の8ビットのバイナリーコードを提供する。このように、ASCII符号化メッセージは出力画像にかぶせられた一連の0および1として印刷でき、何気なく見る者に簡単に認識されない。しかし、人間の目で感知できる一連の0および1で出力画像を散らかすのは通常最適な解決ではない。
【０００７】
符号化メッセージを隠す1つの方法は透かしメッセージを既に出力画像の一部であり得るテキスト文字に符号化することである。この方法において、出力画像内の既存のテキスト文字が上部領域と下部領域に分割され、2つの領域の相対的暗さレベルを変調して符号化透かしメッセージが記入される。例えば、テキスト文字の上部領域を下部領域より暗くして論理0を表すことができる。あるいはテキスト文字の下部領域を上部領域より暗くして論理1を表すことができる。この方法は出力文書を何気なく読む者から透かしメッセージを効果的に隠すことに成功するが、透かしメッセージをうまく記入し、複数のスキャン・印刷サイクルの後透かしメッセージをうまく抽出するために透かし入りの出力画像を処理するのに用いられるスキャンおよび印刷機器の質にある程度依存し得る。
【０００８】
本発明の一目的は透かしメッセージを符号化し抽出する簡単な方法を提供することである。
また本発明の別の目的は画像上の透かしメッセージにより何気なく見る者が気をそらされるのを低減することである。
【課題を解決するための手段】
【０００９】
本発明の入力画像にテキストメッセージを透かし入れする方法は、
（ａ）前記テキストメッセージを論理0のデータビットおよび論理1のデータビットのバイナリーコードのデータビットシーケンスに転換し、前記バイナリーコードのデータビットシーケンスを非データのマーカービットからなるブロック境界で定義されるメッセージブロック内に配列するステップと、
（ｂ）前記バイナリーコードのデータビットシーケンス内の論理0のデータビットに第1ビットパターン記号を割り当てるステップであって、前記第1ビットパターン記号は同心の三角形配列を形成するよう並べられたばらばらの矩形切片の第1の予め定義された幾何学的配列であるステップと、
（ｃ）前記バイナリーコードのデータビットシーケンス内の論理1のデータビットに第2ビットパターン記号を割り当て、前記第2ビットパターン記号を前記非データのマーカービットに割り当てるステップであって、前記第2ビットパターン記号は同心の三角形配列を形成するよう並べられたばらばらの矩形切片の第2の予め定義された幾何学的配列であるステップと、
（ｄ）複数の前記メッセージブロックを前記入力画像にマッピングし、前記マッピングに従い前記第1および第2ビットパターン記号を前記入力画像に書き込むステップとを有することを特徴とする。
【００１０】
また、本発明の入力画像にテキストメッセージを透かし入れする方法において、前記第1ビットパターン記号は第1直角三角形を形成し、前記第2ビットパターン記号は第2直角三角形を形成し、前記第1および第2直角三角形は類似したサイズで、前記第1および第2直角三角形は一定の配向を有し、
前記一定の配向は前記第1および第2直角三角形を横に並べた場合に、
（A）  前記第1直角三角形の頂点は前記第2直角三角形の底辺と位置合わせされ、前記第2直角三角形の頂点は前記第1直角三角形の底辺と位置合わせされ、
（B）  前記第1直角三角形の辺は前記第2直角三角形の辺と平行になり、
（C）  前記第1直角三角形の斜辺は前記第2直角三角形の斜辺の位置合わせと交差するよう位置合わせされることを特徴とする。
【００１１】
また、本発明の入力画像にテキストメッセージを透かし入れする方法において、前記第1直角三角形の前記辺は前記第1直角三角形の左側にあり、前記第2直角三角形の前記辺は前記第2直角三角形の左側にあることを特徴とする。
【００１２】
また、本発明の入力画像にテキストメッセージを透かし入れする方法において、前記同心の三角形輪郭は各々直列に配列された前記ばらばらの矩形切片の集まりからなる2つの同心の部分的な正方形輪郭から形成され、前記ばらばらの矩形切片は長さが幅より長く、
各部分的な正方形輪郭は部分的正方形輪郭の共通斜辺に沿った角領域が1つ欠損しており、各欠損角領域は各々の部分的正方形輪郭の半分未満で、各々の欠損領域に隣接する各同心の正方形輪郭の2つの角は角が欠損している領域に部分的に及ぶことを特徴とする。
【００１３】
また、本発明の入力画像にテキストメッセージを透かし入れする方法において、前記ステップ（ａ）は
連続するメッセージブロックの頭を交互に1または2行の論理0ビットで引き延ばすステップと、
固定ビット長の予め定義されたデータビットシーケンスを前記バイナリーコードのデータビットシーケンスの第1データビットのすぐ前に挿入するステップとを含むことを特徴とする。
【００１４】
また、本発明の入力画像にテキストメッセージを透かし入れする方法において、前記入力画像の正しい配向は前記入力画像を0度から90度、270度、360度と移動させて4つの配向に配置し、各配向において再生できる有効なビットパターンの数を判定することにより判断され、最多数の有効なビットパターンを具現する配向が前記正しい配向とみなされることを特徴とする。
【００１５】
また、本発明の入力画像にテキストメッセージを透かし入れする方法において、論理1データビットに割り当てられた第2ビットパターン記号は、
（ｉ）ビットパターンの各行について第1ビットパターン記号の数および第2ビットパターン記号の数を判定し、前記第1ビットパターン記号の数を前記第2ビットパターン記号の数から引いて結果をその行におけるビットパターン記号の合計数で割ることにより行・エッジ得点を割り当て、前記行・エッジ得点の行ヒストグラムを作成し、すべての行・エッジ得点の平均に前記行ヒストグラムの標準偏差の1.75倍を足すことから判定される閾値で前記行ヒストグラムを閾値化するステップ、によって、ブロック境界を定めるマーカービットに割り当てられた第2ビットパターン記号から識別でき、行閾値を超えた任意の行・エッジ得点は見込み行境界と特定されることを特徴とする。
【００１６】
また、本発明の入力画像にテキストメッセージを透かし入れする方法において、前記ステップ（ｉ）はさらに前記行ヒストグラムのピーク間距離の中央値を推測水平ブロック寸法と解釈することを含み、位置をピーク間距離の中央値内に計算しても第1の予め定義された許容値を超えて前の中央値を変えないような見込み行境界の行のみが水平ブロック境界とみなされることを特徴とする。
【００１７】
また、本発明の入力画像にテキストメッセージを透かし入れする方法において、前記第1の予め定義された許容値は5％であることを特徴とする。
【００１８】
また、本発明の入力画像にテキストメッセージを透かし入れする方法において、さらに、（ii）ビットパターンの各列について第1ビットパターン記号の数および第2ビットパターン記号の数を判定し、前記第1ビットパターン記号の数を前記第2ビットパターン記号の数から引いて結果をその列におけるビットパターン記号の合計数で割ることにより列・エッジ得点を割り当て、前記列・エッジ得点の列ヒストグラムを作成し、すべての列・エッジ得点の平均に前記列ヒストグラムの標準偏差の1.75倍を足すことから判定される閾値で前記列ヒストグラムを閾値化するステップで、列閾値を超えた任意の列・エッジ得点は見込み列境界と特定されるステップ、を含むことを特徴とする。
【００１９】
また、本発明の入力画像にテキストメッセージを透かし入れする方法において、前記ステップ（ii）はさらに前記列ヒストグラムのピーク間距離の中央値を推測垂直ブロック寸法と解釈することを含み、位置をピーク間距離の中央値内に計算しても第2の予め定義された許容値を超えて前の中央値を変えないような見込み列境界の列のみが垂直ブロック境界とみなされることを特徴とする。
【００２０】
また、本発明の入力画像にテキストメッセージを透かし入れする方法において、前記第2の予め定義された許容値は5％であることを特徴とする。
【００２１】
前記バイナリーコードのデータビットシーケンスはすべてのメッセージブロック内の対応位置からすべての論理0ビットおよび論理1ビットを集め、論理0または論に1と識別できないビット位置を未知と特定し、未知と特定されたビット位置を無視しながら各ビット位置における支配的データビットを特定し、各ビット位置のその支配的データビット値を割り当てることにより判定可能であることを特徴とする。
【００２２】
また、本発明の入力画像にテキストメッセージを透かし入れする方法において、前記データビットおよびマーカービットは前記入力画像の背景区域にのみ書き込まれることを特徴とする。
【００２３】
また、本発明の入力画像にテキストメッセージを透かし入れする方法において、隣接する矩形切片間の間隔は透かし入り画像に印刷およびスキャン操作を受けさせると複数の矩形切片が部分的につながり合成形状を形成するように選択されることを特徴とする。
【図面の簡単な説明】
【００２４】
【図１】3つのビットタイプを表す2つのビットパターン記号を示す図である。
【図２】図1におけるビットパターン記号の構成のより詳細な図である。
【図３】画像処理における画像侵食および画像膨張を示す図である。
【図４】入力画像からビットパターン記号を定義するために侵食−膨張サイクルをどのように用い得るかを示す図である。
【図５】入力画像の正しい配向を特定する方法を示す図である。
【図６】画像に対し好ましいビットパターン記号の配置方法の例を示す図である。
【図７】ビットパターンを配置し得る領域を特定するために入力画像に対する第1接続成分操作の適用を示す図である。
【図８】透かし入り画像の例を示す図である。
【図９】解読する必要のある見込みのビットパターン記号を特定するために透かし入り画像に対する第2接続成分操作の適用を示す図である。
【図１０】接続成分マスクを作成する好ましい方法を示す図である。
【図１１】代表的な透かし符号化シーケンスを示す図である。
【図１２】好ましいメッセージマッピング機構を示す図である。
【図１３】図１３Ａは透かし入り画像からの例を示す図である。図１３Ｂは図13Aの例から特定された論理1ビットを示す図である。図１３Ｃは図13Aの例から特定された論理0ビットを示す図である。
【図１４】透かし入り画像のビット行に沿って特定された論理1ビットから作成された行ヒストグラムを示す図である。
【図１５】透かし入り画像のビット列に沿って特定された論理1ビットから作成された列ヒストグラムを示す図である。
【発明を実施するための形態】
【００２５】
本発明の詳細に入る前に、代表的なビット符号化機構を呈示する。複数のビット符号化機構が技術的に知られ、具体的なビット符号化機構の選択は本発明に肝要でないことが理解されよう。
【００２６】
最初にユーザー提供のメッセージ列がビット符号化により適当な形に転換される。ユーザー提供のメッセージ列は任意の文字列であって良く、本明細書では例示の目的から“Hello world”の文字列と仮定する。このテキスト文字列（すなわちメッセージ列）は次に論理ローの“0”ビットおよび論理ハイの“1”の集まりとして表示し直される（すなわち符号化される）。この符号化操作において、メッセージ列のすべての固有文字は対応する固有の、好ましくは0から255の範囲にある数字コードに相関される。次に各数字コードがバイト（8ビットのバイナリー数字）などデータビットの固有グループで表される。これはユーザー提供のメッセージ列におけるテキスト文字をそれらに等価のASCII コードに転換することにより達成することができる。
【００２７】
技術的に知られるように、ASCIIコードとはAmerican Standard Code for Information Interchange（情報交換用米国標準コード）で、テキスト文字を各8ビットの機械読み取り可能なバイナリーコードに転換する文字符号化機構を提供する。“Hello world”の本代表的メッセージ列について、各テキスト文字に対するASCII の等価数字コードを表1に示す。
【００２８】
【表１】
0005136679.tif 000002
【００２９】
従って“Hello world”のメッセージ列は次の
0100100001100101011011000110110001101111001000000111011101101111011100100110110001100100
のバイナリービットベクターとして表すことができる。
【００３０】
メッセージは論理0および1の集まりとなったので、必要なことは論理0および論理1を印刷画像上に表す方法だけである。論理0および1の表示は本発明の重要な面である。
【００３１】
可視画像透かし入れで用いる0ビットおよび1ビットを表す新規かつ印刷可能なパターン記号デザイン（またはビットパターンデザイン）を以下に説明する。しかし現在ユーザー提供のメッセージ列は入力画像に透かし入り（すなわち符号化）する前に全長のメッセージ列にフォーマットすることが好ましいので、本明細書において好ましいビットパターン記号デザインを説明する前に、まず「全長メッセージ列」を定義することが有益である。「全長メッセージ列」の定義される長さはデザイン上の選択であることが理解されよう。
【００３２】
本明細書において、入力画像上に符号化されるすべてのメッセージ列は「全長メッセージ列」を定義する同じ長さであることが好ましく、合計64バイト（または64個の1バイト文字）の固定長に限定されることが好ましい。より小さいメッセージ列は既知のビットデータで引き延ばして最終のビット長を64バイトに等しくすることができる。例えば、本代表的メッセージ列である“Hello world”は11文字のみからなるが、終わりに複数の空白を添付した“Hello world                           ”と書き直すことができる。言い換えれば、53個の空白文字を元の11文字の“Hello world”メッセージ列に添付して64文字の全長メッセージ列にすることができる。一旦全長メッセージ列のビットデータ表示が得られると、ビットパターン記号デザインが必要となる。
【００３３】
図1を参照すると、本明細書において好ましい実施形態は2つのビットパターン記号11および13を用いて3つの別個のビットを表す。ビットパターン11は論理0ビット（すなわち0ビット）を表し、ビットパターン13は論理1ビット（すなわち1ビット）とマーカービットｄ（すなわちMB）双方を表す。
【００３４】
ビットパターン記号13がマーカービットとして用いられる場合、論理データを伝達せず、復号化手順を容易にするためにメッセージ列（または以下の定義するようなメッセージブロック）の境界を分けるのに用いられる。ビットパターン記号13がいつ論理1ビットとして用いられ、いつマーカービットとして用いられるかを区別する好ましい方法は以下により詳しく説明される。
【００３５】
入力メッセージ列を表すビットパターン記号11および13の配列は入力画像の背景区域にかぶせられるのが好ましく、入力画像の前景ピクセルにかぶせられないことが好ましい。しかし各ビットパターン記号11および13の色の選択は入力画像の明るい領域はより暗いビットパターン記号がかぶせられ、入力画像の暗い領域はより明るいビットパターンがかぶせられるように適応して変えることができる。
【００３６】
ビットパターン記号11および13双方とも各々直列に配列されたばらばらの矩形切片19の集まりからなる2つの同心の部分的正方形輪郭15および17からなる。ばらばらの矩形切片19は長さが幅より長い。
【００３７】
図2を参照すると、各部分的正方形輪郭15および17は各々正方形輪郭の共通斜辺に沿って1つの角領域21および23が欠損している。各欠損角領域21および23は各々の部分的正方形輪郭15および17の半分未満を構成する。このように、各々の欠損領域に隣接する各同心の正方形輪郭は角が欠損している領域に部分的に及ぶ。
【００３８】
好ましい実施形態において、外側の部分的正方形輪郭17は部分的正方形輪郭17の反対の角において2つの閉鎖された角25を形成する2つの、くの字形矩形切片、および2つの閉鎖された角25間の角において、くの字形の開放された角29を形成する2つの接触する矩形を有する。
【００３９】
さらに好ましい実施形態において、内側の部分的正方形輪郭15は正方形輪郭を4つの別個の切片31に分割し、各々は内側の部分的正方形輪郭15の角を定義する。この構成において、内側の部分的正方形輪郭15は欠損角領域21に対応する別個の切片21を欠いている。
【００４０】
本ビットパターン記号の重要な特徴の1つは印刷およびスキャンのサイクル後、ビットパターン記号は細い、少なくとも部分的に連続したオブジェクトに見えることである。つまり、印刷およびスキャンのサイクルはビットパターン記号11および13を、個々のばらばらな矩形切片19を区別するのはより難しくなるが、同時に細くなった外観により透かし入り画像を何気なく見る者にとってそれほど目立たなくなるようにぼかす傾向がある。本ビットパターンは強度がはるかに軽く、エンドユーザーにとって視覚的邪魔にそれほどならないが、適当なサイズの接続成分操作はぼかされたビットパターン記号11または13のばらばらな矩形切片を接続するのに有効で、異なる三角形のビットパターン記号を正しく識別する。
【００４１】
どのようにビットパターン記号11および13をうまく区別するかを考察する前に、まず画像処理の分野における画像侵食および画像膨張のトピックを考察するのが有益である。
【００４２】
図3Aを参照すると、画像侵食は一般的にバイナリー画像31に適用され、基本的に画像31の周囲が予め定義された形の予め定義された構成要素33に従い再構成される方法である。本例において、画像31は正方形を定義し、構成要素33は中心35を有する円、またはディスクである。
【００４３】
画像31の内側周辺に沿って構成要素33を移動させるにつれ、中心35は内側周辺画像31に追随する新しい形の輪郭37を作り出す。輪郭37の正確な形は中心35がどれだけ厳密に内側周辺に追随するかにより決定され、これはまた内側周辺に沿って移動する構成要素33に形で限定される。本例において、輪郭37は円33の半径で定義される量だけ元の正方形31より小さい新規正方形39を定義する。
【００４４】
実際的に、画像がにじむペンで描かれたように染みだらけに見える場合、画像侵食は太い線を細くし、文字"o"内の孔のような開口をより良く定義する効果を有する。
【００４５】
図3Bを参照すると、画像膨張も構成要素33により画像39の周辺を再構成するが、画像膨張において構成要素33の中心35は画像39の周辺に沿ってトレースされる。構成要素33が画像39の周辺をトレースするにつれ、構成要素39自体の外側周辺は新規輪郭41を定義する。このように、構成要素の形により定義される輪郭は元の形より大きい新規の形43を作り出す。本例において、構成要素33は円形であるので、新規の形43は正方形31と類似したサイズの正方形に似ているが、角が丸められている。要するに、膨張は侵食の反対で、細く描かれた図形は膨張されるとより太くなる。
【００４６】
図3Cを参照すると、画像31に対し同じ構成要素33を用いて侵食プロセスを適用して直後に膨張処理を続ける効果は、構成要素33が元の画像31の内側周辺に沿って移動する際、元の画像31の外側周辺が構成要素33の外側周辺にワープされる結果となる。これは構成要素33の輪郭に追随する新規輪郭41をもたらす。従って、最終画像43の形は構成要素33の形、および構成要素33がどれだけ厳密に元の画像31ｎ内側周辺に追随するかに依存する。
【００４７】
本明細書において好ましい実施形態において、侵食−膨張サイクルを用いてビットパターン記号11（すなわち0ビット）およびビットパターン記号13（1ビットおよびMB）を検出するのに役立てる。
【００４８】
例えば図4Aにおいて、ビットパターン13のスキャン画像2が示される。スキャン画像2は良く定義されていないが、図4Bにおいて、スキャン画像2に接続成分操作を適用すると接続成分形状3をもたらし、これはスキャン画像2より良く定義されるが、まだあまり厳密にビットパターン記号13の三角形に追随していない。
【００４９】
図4Cを参照すると、本明細書において好ましい実施形態において、画像侵食−膨張サイクルを用い、スキャンされたビットパターン記号を定義するのに役立てる。三角形の構成要素4（直角を有することが好ましい）が用いられる。例示の目的から、接続成分3の内側周辺に配置された、いくつかの三角形構成要素4の全般的配置が示される。
【００５０】
図4Dおよび4Eに図示されるように、侵食−膨張サイクルを適用する結果、接続成分形状3の形状を変えて構成要素4により定義された角度に沿って平坦化された側面とより良く定義された角を有する処理された輪郭5を実現する。構成要素4は三角形であるので、処理された輪郭5の全般的な形は三角形である。次に予め定義された、いくつかの幾何学的パラメーターがビットパターン11および13の幾何学的パラメーターと一致するか（予め定義された許容誤差内で）判定することにより処理された輪郭5がビットパターン11または13のいずれかと一致するか判定することができる。これらの幾何学的パラメーターは例えば側面間の角度、周辺対面積の比率、高さ−底辺サイズ、特定角の角度の正接および／または正弦および／または余弦、等々であって良い。
【００５１】
一旦ビットパターン記号11および13の三角形のマーキングが判定されると、次のステップは透かし入り画像を読み取る、すなわち解読する、準備としてマーキングの正しい配向を判定することである。
ビットパターン11および13の形状の利点はビットパターン記号11および13の正確な検出が透かし入り画像の回転に影響されないことである。つまり、ビットパターン記号11および13を用いて作成されたメッセージは正しい配向においてのみ解読できる。
【００５２】
本明細書において好ましい実施形態は場当たり的な形態変換を用いてビットを検出する。これらのビットは回転的に突出するという利点を有する。場当たり的な操作は図5A‐5Dに示すようにパターンを回転感応的にする。図1に示されるように、ビットパターン記号11および13双方とも予め定義された配向（すなわち左から右へ）に沿って平坦な壁（すなわち垂直な側面）を必要とする。つまり、各ビットパターン記号11および13の最も左の側面は垂直壁である。ビットパターン記号の最も左の側面に垂直側面を提供する配向を検出することにより、透かしメッセージの正しい配向を識別することができる。より具体的に、全体画像の小サンプル（面積で10％未満が好ましく、画像の角から取ることが好ましい）を90度ずつ増分して回転し、各配向における可能なビットパターン形状を識別し、各配向において可能なビットパターン形状を2つの真のビットパターン記号11および13に照合し、最多数のビットパターン記号を提供する配向を特定（予め定義された左から右への配向を横切る際遭遇する第1側面に沿った垂直側面（すなわち垂直壁）を有することを含み、上述の幾何学的パラメーターの照合により特定）することにより、透かしメッセージの正しい配向を判定することができる。
【００５３】
図5Aを参照すると、より大きい画像の小サンプル10（未知の配向）が示される。ビットパターン記号を識別する上述のプロセスが適用される。ビットパターン記号はすべて最も左の側面（本明細書の好ましい実施形態において）が垂直壁であることが必要のため、図5Ａの配向は領域12内図に14の有効なビットパターン記号を提供する。
【００５４】
図5Aの画像を90度回転した結果図5Bの画像が得られる。再度ビットパターン記号を識別する上述のプロセスが適用される。図5Aにおける可能なビットパターンのいずれも最も左の側面に垂直壁を有しないのでこの配向は合致するビットパターン記号がない。
【００５５】
図5Bの画像を90度回転した結果図5Cの画像が得られる。ビットパターン記号を識別する上述のプロセスを適用すると、領域14および16において6つの有効なビットパターンしか得られない。
【００５６】
図5Cの画像を90度回転した結果図5Dの画像が得られる。ビットパターン記号を識別する上述のプロセスを図5Dの画像に適用すると、20の有効なビットパターン記号が識別される。図5Dの配向が最多数の有効なビットパターン記号をもたらしたのでその配向が、図5Dがほんの一部をなす元の画像全体の正しい配向とみなされる。
【００５７】
このように、正しい回転（縦長対横長、および上向き対下向き）は画像の小サンプルを回転して認識されたビット（すなわち0、1、およびマーカービットの組み合わせ）が最多数得られる配向を求めることにより見出すことができる。
【００５８】
次にトピックは透かしメッセージの符号化（すなわち書き込み）および復号化（すなわち読み取りまたは解読）に移る。
【００５９】
図6を参照すると、本明細書の好ましい実施形態において、ビットパターン記号は前景を含む境界箱の周囲だけでなく、実際の前景の周り全体にかぶせられている。さらに前景ピクセルは境界マーカービットからすらも触れられていない。この特長は符号化画像の美的な質を向上させる。
【００６０】
メッセージの符号化およびメッセージの抽出双方の準備として、接続成分マスク（すなわちバイナリーマスク）が作成される。メッセージの符号化に対し、透かしメッセージが書き込まれる入力画像の第1接続成分が作成される。メッセージの抽出に対し、スキャン画像（または透かしメッセージが抽出される画像）の第2接続成分マスクが作成される。第1および第2接続成分マスク間の基本的な差は接続成分のサイズを決定する面積閾値パラメーターである。
【００６１】
図7を参照すると、画像75は透かしメッセージが書き込まれる入力画像の部分図を示す。第1接続成分を作成する目的は入力画像75内で透かしメッセージを書き込める区域を特定することである。本例において、画像77はもたらされた第1接続成分マスクで、透かしメッセージを書き込める区域を白で示し、透かしメッセージを書き込むべきでない区域を黒で示す。
【００６２】
図8を参照すると、画像71は透かし入りメッセージの例である。画像71から透かしメッセージを抽出するために、第2接続成分マスクが作成され、入力画像75において画像71内のマーカービットまたはデータビット情報を含む区域（すなわちビット画像）を特定する。
【００６３】
図9は透かし入り画像に第2接続成分プロセスを適用した結果を示す。読み取るべき見込みのあるビットパターン記号（すなわちビット画像）は黒い領域における白の区域として識別される。
【００６４】
接続成分マスク（第1または第2接続成分マスクのいずれかについて）の構築に対する一般的なプロセスを図10に示す。接続成分マスクを作成するために、提出画像51はまず単一チャンネル画像に転換される（ステップ53）。提出画像51は入力画像の全体であって良いことが理解されよう。あるいは、入力画像は複数の画像ブロックに分割され、ステップ51において各画像ブロックが提出画像として個々に処理されても良い。画像ブロックが符号化の目的の場合、後述のように画像ブロックはマーカービットで線引きしたメッセージブロックとサイズおよび位置的に一致することができる。本発明の一実施形態において、全体画像がメッセージの符号化用に提出され、複数の画像ブロックがメッセージの抽出用に提出されるが、これはデザイン上の選択である。
【００６５】
プロセスステップ51‐63が各画像ブロックに別々に適用されるよう（ステップ64＝はい）別個の画像ブロックが個々に提出される場合、ステップ65における出力マスクは画像ブロックに等しいサイズのマスクブロックとなる。あるいは、ステップ51‐63が全入力画像に適用されるよう（ステップ64＝いいえ）提出画像51が全入力画像の全体である場合、もたらされる接続成分区域マスクはステップ65で結果を出力する前に画像ブロックに等しいサイズのマスクブロックに分割することができる（ステップ67）。
【００６６】
ステップ53における単一チャンネルへの転換は画像51にRGBからYCbCrへの転換を適用し、次に続くすべての処理を輝度（Y）チャンネルのみに実施することにより達成できる。輝度チャンネル画像（すなわち強度I）の光強度勾配画像が次に
∇I ＝ ∇Ix ＋ ∇Iy
の関係を用いて生成される（55）。
【００６７】
次に、各強度値を1つの強度閾値59と比較することにより光強度勾配画像の2値化画像が作成される（57）。2値化画像の接続成分が次にラベル付けされる（61）。次にサイズが面積閾値63の±25％より大きく変動するすべての接続成分を切り捨てることにより区域マスク（すなわちバイナリーマスク）を作成することができる（65）。面積閾値63のサイズはメッセージ挿入（すなわち書き込み）用に第1接続成分マスクまたはメッセージ抽出（すなわち読み取り）用に第2接続成分マスクを作成するかに依存する。メッセージ挿入の場合、面積閾値63は透かしメッセージを挿入する区域を定義し、一実施形態において、一般的に画像の前景を背景から分離する。メッセージ抽出の場合、面積閾値63ははるかに小さく、パターンビットの面積と類似したサイズであることが好ましい。
【００６８】
画像がまだ透かし入りされていない場合、透かしメッセージは符号化された形で上述のビットパターン記号11および13を用いてかぶせられる（すなわち印刷される）。入力画像の背景および前景部分を識別することは随意の透かし変形を適用するのに有利である。例えば、好ましい実施形態において、データビットパターンおよびマーカービットパターンは入力画像の背景部分にのみ印刷される。
【００６９】
望まれる場合、データビットパターンおよびマーカービットパターンは周囲の画像ピクセルの全般的強度により強度を変化させることができる。つまり、入力画像が明るい区域（すなわち予め定義された強度閾値を超える）においてビットパターンは周囲の画像ビットより暗く印刷することができ、入力画像が暗い区域（すなわち予め定義された強度閾値を超えない）においてビットパターンは周囲の画像ビットより明るく印刷される。
【００７０】
逆に、画像が前に透かし入り画像（前に印刷された透かし入り画像のスキャン画像など）の場合、区域マスク（すなわちマスクブロック）は抽出および復号化を容易にするためにビットパターン記号をハイライト（すなわちパターン画像を作成）する。
【００７１】
図11を参照すると、一般的な透かし符号化シーケンスはマスクブロック121、メッセージブロック122、および画像ブロック123を提供することから始まることができ、各マスクブロックとその対応画像ブロックとの間に1対1の関係が確立される（ステップ125）。入力画像は複数の画像ブロックに分割され得、接続成分マスクも画像ブロックと同じ数およびサイズの複数のマスクブロックに分割され得る。
【００７２】
フォーマットされたメッセージブロックは固定サイズであって良い。メッセージブロックは必ずしも形状が正方形でなく、画像ブロックと同じサイズでもないことが理解されよう。本明細書において、メッセージブロックは画像ブロックより小さいことが好ましい。
【００７３】
すべての画像ブロックが処理された場合、符号化プロセスはステップ128で終了するが、すべての画像ブロックが処理されていない場合（ステップ127）、入力画像から抽出された画像ブロック123はメッセージ長に基づきその対応マスクブロック121で掛けられマスクフィルター化ブロックが作成される（ステップ129）。もたらされるマスクフィルター化ブロックは画像ブロックにおいてビットパターンが符号化されるべきでない区域をマスクで除外し、さらにメッセージバターンサイズのサブブロックに細分される。
【００７４】
すべてのメッセージパターンサイズのサブブロックが処理されると（ステップ133＝はい）、すなわち透かしが符号化されると、プロセスはステップ127にもどり、処理すべき別の画像ブロックが残っているか判定する。
【００７５】
メッセージパターンサイズのサブブロックが符号化される必要があると仮定すると（ステップ133＝いいえ）、現在のメッセージブロックを定義されるフォーマットされたメッセージで定義されるビットパターンがその対応メッセージパターンサイズのサブブロックにかぶせ（すなわち符号化）られる（ステップ135）。ビットパターンは画像ブロックの前景領域にかぶせられないことが特筆される。
【００７６】
メッセージブロックにおける透かしパターン記号の合計数は「メッセージビット総数」と特定され、透かしメッセージの符号化は0に等しい計数変数nを定義することから始まる（ステップ135）。計数変数nがメッセージビット総数を超えると（ステップ137＝はい）、すべての透かしパターン記号が符号化された（すなわち現在のメッセージサブブロックに組み入れられた）ことを意味し、処理はステップ133に戻り符号化すべき追加サブブロックが残っているか判定される。
【００７７】
nがメッセージビット総数より高くない場合（ステップ137＝いいえ）、現在のメッセージパターンサイズのサブブロックで定義される現在の画像ブロック領域が符号化に適しているか判定される（ステップ139）。つまり、ステップ139で現在のサブブロック領域が符号化に適していないと特定された場合（ステップ139＝いいえ）、処理はステップ137に戻る。逆に、ステップ139で現在のサブブロック領域が符号化に適していると特定された場合（ステップ139＝はい）、処理はステップ140に進み、メッセージブロックからのn番目のビットパターンが画像ブロックの現在の領域に符号化される。
【００７８】
ビット符号化はさらに予め定義されたマッピング機構に従うことが好ましい。つまり、各ブロック内における第1データビットの位置はマッピング機構に従い定義される。
【００７９】
符号化段階の際、ビットパターンは入力画像にかぶせられる。パターンをかぶせる本明細書における好ましい方法はユーザーが透かし復元段階を実施不可能にすることを防ぐようデザインされたマッピング機構を用いる。先行技術における符号化機構は攻撃者が各メッセージブロックに対し寸分たがわずの位置に暗い円を描いた場合無効化され得る。そうした場合、復元段階はどのブロック内においてもいずれの透かしメッセージを確認できず、従って最後にいずれのメッセージも生成できないので攻撃者は透かし機構全体を破壊したことになる。この簡単な攻撃はメッセージをすべて一貫して破壊するのに充分であった。
【００８０】
新規機構はこのような攻撃を防護する。攻撃者が各ブロックに対し同じ位置に類似した円を描いても、マッピングは欠損ビットが残りのブロックから得られることを保証する。新規機構によると、符号化ビットは固定マッピングに従い同等の位置にかぶせられる。これは1つのブロックにおけるメッセージビットの位置がxの場合、他のすべてのブロックにおける位置はxまたは（x＋Δ）で、Δは予め定義された位置移動である。この方法は各メッセージブロック内の透かしメッセージの一部である第1データビットの位置という点で説明される。
【００８１】
上述のように、本明細書において好ましい実施形態は前景領域にデータビットまたはマーカービットを印刷しない。従って、位置x、または位置x＋Δを特定する上で、前景領域に対応するビット位置は無視される。
【００８２】
図12を参照すると、列A、B、およびCはマーカービットの列で、各列はブロック境界を定義する。本例において、列Bは2つの連続メッセージブロック34および36を分割する。簡単な復号化を保証するために、連続メッセージブロックの初めは交互に1行（38）または2行（40）の0ビットで引き延ばされる。加えて、メッセージが始まる行はメッセージ44の初めの直前に来る予め定義された8ビットパターン42で引き延ばされる。予め定義された8ビットパターンは1ビットで始まる一連の交互の1および0である。これは最初の有効ビットが常に位置（dim*n＋8）で始まるように位置マッピングを生成し、dimはメッセージブロックの寸法（ビットでの）でnは引き延ばし用に用いられた0ビットの行数（本例では1または2）である。これにより有効ビットが常に固定位置マッピングに対応することを保証する。現在の実施では2つのマッピングのみが用いられるが、容易に現在のデザインに複数のマッピングを組み入れることができる。
【００８３】
本明細書で好ましい実施形態において、第1メッセージブロックは0ビットの最初の1行で引き延ばされ、第2メッセージブロックは0ビットの最初の2行で引き延ばされ、第3メッセージブロックは0ビットの最初の1行で引き延ばされ、以下同様である。このように、メッセージブロックの境界を示すマーカービットを識別することは本発明の肝要な面である。しかし、上述のように、マーカービットは論理1ビットを特定するのと同じビットパターン記号（図1からの13）で特定されることが好ましい。従ってビットパターン記号13がいつマーカービットを表すはずで、いつ論理1を特定するはずかを判定する方法が望まれる。
【００８４】
ビットマスク画像から識別されるマーカービットはブロック境界を示すために用いられる。ブロック境界が判定された後、各ブロックは個々に復号化される。任意の特定行または列について、識別されたビットパターン記号13（すなわち1ビットまたはマーカービット）の数は識別されたビットパターン記号11（すなわち0ビットのビット）の数と比較され、識別されたビットパターン記号13がマーカービットを表し、従ってブロック境界パターンを示すか、正規のデータパターン（すなわちデータビット）を表すかを指示するものとして有効なビットパターン記号（0ビットと1ビットの合計）で加重される（すなわち割られる）。各列および行はこのように
【００８５】
【数１】
0005136679.tif 000003
と定義されるエッジ得点が与えられる。
【００８６】
例えば、図13Aはメッセージブロック境界およびデータビットの混合を含む画像の一部を示す。図13Bは解読されたビットパターン記号13（すなわち論理1ビット）を示し、図13Cは解読されたビットパターン記号11（すなわち論理0ビット）を示す。図13Bにおける論理1ビットの最初の行を図13Cにおける対応する0ビットを有しない最初の行と比較すると
【００８７】
【数２】
0005136679.tif 000004
をエッジ得点が得られる。
第2行のエッジ得点は
【００８８】
【数３】
0005136679.tif 000005
となる。このプロセスはすべての行および列（すなわち水平および垂直方向）について続けられる。次に行のエッジ得点および列のエッジ得点の集まりからヒストグラムが構築される。
【００８９】
行のエッジ得点の行ヒストグラム52が図14に示され、列のエッジ得点の列ヒストグラム54が図15に示される。行ヒストグラム52に第1閾値56が適用され、列ヒストグラム54に第2閾値58が適用される。第1および第2閾値56および58の各々は各々のヒストグラムの平均足す各々のヒストグラムの標準偏差の1.75倍から作成される。これは水平および垂直ブロック境界を識別するのにかなり効果的であるが、ヒストグラム内のより小さいピークのいくつかは各々の閾値を超えるだけ大きく、偽陽性の読み出しをもたらすかもしれない。
【００９０】
この問題はさらに各ヒストグラムのピーク間距離の中央値を推測ブロック寸法（ヒストグラムにより水平の行寸法または垂直の列寸法）として解釈することにより確実に解決することができる。従って、より小さいピークが間違ってブロック境界として記録される場合、推測ブロック寸法に基づき予期される境界位置に起こっていないことに留意することにより排除することができる。
【００９１】
これを実施する1つの方法は、見込みの境界行または列の位置が各々のピーク間距離の中央値内に計算され、見込みの境界行または列が前の中央値で第1の予め定義された許容範囲を超えて変えない場合、それをブッロク境界とみなすことである。
【００９２】
しかし見込みの境界行または列を計算された中央値に組み入れると予め定義された許容範囲を超えて中央値を変える場合、それはブロック境界でないとみなされる。この予め定義された許容範囲は行ヒストグラムおよび列ヒストグラム双方について5％であることが好ましい。
【００９３】
メッセージブロック境界を識別すると、次のステップは各ブロック内に符号化された透かしメッセージを解読することである。
各ブロックは同じメッセージのコピーを保有するので、論理1ビットまたは論理0ビットの真の正体は他のブロック内において同じビット位置のビット値を比較することにより見分けられる。
基本的に、復号化はすべてのメッセージブロックの対応位置からすべてのビットを集め、各ビット位置における最も支配的なビットを推測する。簡略化された例として、透かしメッセージが各々4ビットとして、5つの透かしメッセージ（各々の5つのブロックから）の復号化メッセージは以下の
【００９４】
【表２】
0005136679.tif 000006
のようなビットシーケンスであり、ハイフン“‐”は欠損ビットを意味する場合、論理1ビットは最初の2列において支配的なビットで、論理0ビットは最後の2列において支配的なビットである。従って、このような集まりから推定される最終メッセージは1 1 0 0で、これはメッセージビットのビット的最大である。
【００９５】
この方法を用いることにより、先行技術の方法で用いられるような列のマッチングが必要なくなる。ビット的最大の操作が既になされているので、列のマッチングが必要ない。さらに、解読できないビットは支配的なビットから推測することができるので、この方法は欠損ビットにより良く応じる。
【００９６】
加えて、この方法はブロック毎のメッセージ解読を必要としない。この方法は欠損ビットを未知とみなしブロック毎のメッセージをビットの集まりとして集める。従って、現在この方法はブロック毎のメッセージを生成しない。
【００９７】
発明はいくつかの具体的な実施形態と併せて説明されたが、当業者であれば前述の説明に照らしさらに多数の代替、修正、および変更が明らかになることが明白であろう。従って本明細書において説明される発明は添付クレームの精神および範囲に入るそのような代替、修正、応用、および変更すべてを包含することを意図する。
【符号の説明】
【００９８】
１１    ビットパターン、１３    ビットパターン、１５    部分的正方形輪郭、１７    部分的正方形輪郭、１９    ばらばらの矩形切片、２１    角領域、２３    角領域、２５    閉鎖された角、２９    くの字形の開放された角、３１    画像（正方形）、３３    円、３５    中心、３７    輪郭。
【図１】
0005136679.tif 000007
【図２】
0005136679.tif 000008
【図９】
0005136679.tif 000009
【図１０】
0005136679.tif 000010
【図１１】
0005136679.tif 000011
【図１４】
0005136679.tif 000012
【図１５】
0005136679.tif 000013
【図３】
0005136679.tif 000014
【図４】
0005136679.tif 000015
【図５】
0005136679.tif 000016
【図６】
0005136679.tif 000017
【図７】
0005136679.tif 000018
【図８】
0005136679.tif 000019
【図１２】
0005136679.tif 000020
【図１３】
0005136679.tif 000021