ディジタル・ハーフトーニングへの・数理工学的アプローチ
菊地 洋右，浅野 哲夫………ll……＝‖‖‖‖‖‖‖‖‖‖‖‖‖‖‖‖‖‖‖‖‖‖‖‖‖‖‖‖‖‖‖＝‖＝＝‖‖‖‖‖‖‖‖‖‖‖‖‖‖‖‖‖‖‖＝‖‖‖‖‖‖‖‖‖‖‖‖‖‖‖‖＝‖‖＝‖‖‖‖‖‖＝＝‖‖‖‖‖‖‖‖‖川Ill………ll………‖‖‖‖……ll………………………………lll……………l1．ディジタル・ハーフトーキングを紹介します．ここでは，単純二値化法，組織的ティサ法，誤差拡散法について述べます．

パソコンのモニタ上の写真とそれをプリンタで印刷

単純二値化法ではある閥値を設定して各画素についしたものを比べてみたことがあるでしょうか？ 比べて，その明るさか閥値以下なら0に，開催よ−）上ならてみるとモニタ上のものの方かきれいに見えることで255にします．この方法は単純なため画像が多階調画しょう．では，なせモニタの方がきれいなのでしょう

像ですと原画に似たものは得られません．多階調画像

か？ パソコンのモニタではその設定にもよるけれどでなくとも，階調か127である灰色一色の画像は閥値も1画素につき赤，緑，青をそれぞれ256階調の濃淡か127ならば，黒一色の画像になりますし，128であをもっています．つまり1画素で2563＝16，777，216

る灰色一色の画像は白い画像になります．図1は単純色を表現できます．では，もう一方のプリンタを見て二値化法を施した画像です．ところどころ画像か潰れみましょう．トナー交換やインク交換をするときにカているのか分かります．ただ，この方法にも長所はあラープリンタなら4色くらいですし，■モノクロームなってコピーやスキャナで白色度の低い紙に書かれた文ら黒のインクしか入っていません．4色のカラープリ

字を読みとる時には閥値を紙の色と文字の色の間に設ンタの場合はシアン，マゼンタ，黄色そして黒のイン定することで文字だけを読みとるようにできます．こクが用意されています．たった4色のトナーでの間値の決め方にもいくつかの方法があります［12］か16，777，216色を印刷できるわけはありません．最近

本題から離れていくので，ここでは省きます．

は中間色のインクを用意して，8色のインクを持つプ

組織的ティザ法は単純二値化方法に改良を加えたもリンタもありますか，この方法でも16，777，216色はのと言えます．単純二値化方法ではある特定の閥値を印刷できません．つまりモニタでは黄色を256階調の決めましたが，この方法は各画素について異なる閥値濃淡で映し出していますかプリンタでは黄色のインクを用います．異なる開催といっても各画素の階調を考を紙に吹き付けるか吹き付けないかの2通りしかない慮して決めるのではなく，ティザ行列と呼ばれる行列わけです．このためモニタの写真の方か印刷したものを用意し，そのディザ行列の各値を閥値とします．下よりきれいに見えるのです．すると，プリンタにとっ記の例は原画か4×4の画素である場合のBayer型とて階調が中間の色をどう印刷するかかその善し悪しに呼ばれるティサ行列です［6］．原画か256階調の場合つながってきます．つま−）プリンタは256の濃溌を0か255に振り分けて原画を近似しているのです．この振り分けをティシタル・ハーフトーニングと言います［9］．そして，その振ー）分け方のアルゴリズムには様々なものか提案されています．問題を考えやすくするために単一色からなる画像（モノクローム画像）について考えることにします．いくつかのアルゴリズム
きくち ようすけ
細科学技術振興機構今井量子計算機構プロシュクト〒113−0033文京区本郷5−28−3
あさの てつお北陸先端科学技術大学院大学情報科学研究科〒923−1292石川児能美郡辰口町旭台1−1
2005年1月号

図1単純二値化法を施した画像（木の上の2匹の亀）© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

（35）35

これらの値を16倍したものが閥値となります．
0 8 2 1012 4 14 6
β4＝3 111 9（ 15 7 13 5

この例の2行3列めの値は14なので14×16＝224を閥値として対応する原画の画素を0か255に振り分けます．この方法では確率として階調がgの画素を確率g／256で黒とします．すると階調とその確率の256倍は一致するので，原画の色の濃淡を反映しているよ
うに思えます．ということで画素数が十分多ければ，図2 組織的ティザ法を施した画像（木の上の2匹の亀）良い結果が得られます．そして少ないと当然，悪い結果になります．組織的ティザ法ではディザ行列の値を2＼︶

次のように決めます．
1β2＝（4β2侶＋2J2〃−1

4β2〃−1β2乃＝（4上）2乃−1＋3ノ2… 4β2…＋み−1

ただし，んはすべての要素が1である2乃×2乃行列です．このように再帰的に要素の値を決めてできる行列を用いるのを組織的ディザ法，ランダムに値を決めていくのをランダムディザ法と呼びます．また，組織的図3 誤差拡散法を施した画像（木の上の2匹の亀）ディザ法で用いるディザ行列にも閉値か中心では小さく周辺では大きいドット集中型と閥値がなるべく均等になるように構成されたドット分散型かあります．
Bayer型はドット分散型の一つです．図2は組織的ディザ法を施した画像ですが，周期的な模様が見てとれます．

誤差拡散法は上記の二つの方法とはだいぶ異なります．上記の二つの方法では各画素を周一）の画素を考慮せすに二値化しました．誤差拡散方では閥値との誤差を周囲の画素に振ー）分けていきます．原画の各行を順に右から左に走査することをラスタ走査と言います．
これはインクジェットプリンタのヘッドの動きと同じです．このラスタ順に誤差をまだ走査していない周囲の画素に振り分けます．次に代表的な誤差拡散行列
El，E2を示します．

列の値をその対応する画素に加えていきます．この方法では大きな誤差拡散行列を用いれば滑らかな画像か得られます．しかし解像能は低下します．実際には，この方法を改良したものかインクジェットプリンタに広く使われています．誤差拡散法を施した図の例が図3です．誤左拡散法特有の粒状の模様か現れています．
この他にもブルーノイズマスク法［11］という方法があります．これはティザ法と人間の視覚特性（空間周波数の高周波成分を検出しにくい）を組み合わせて画像のノイズを目立たなくする方法です．この方法を用いると誤差拡散法と同程度の画像が得られます．
このように様々な手法か提案されているのは二値化する原画や目的によってそれそれに一長一短があるためです．

︶

6611

ここでもうー度Bayer型ディザ行列について考えす．このときBayer型ディザ行列の閥値の高い値と414343′／てみましょう．灰色の原画を二値化することを考えま

00

458／

84587〃

8／847／

05／00／．

月．

853481／ノ

8−00

843（／E2＝●．烏∵〃●173／166（1El＝′／ ′／●走査している画素です．0と閲値との差×誤差拡散行

低い値は均等に分布しているために灰色に見える画像か構成できるわけです．

a，E2において●はすで七走査済みの画素，○は現在，36（36）© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

オペレーションズ・リサーチ

2．食い違い度からみたディザ行列
さて，ディジタル・ハーフトーニングはある種の近似なのですが，その尺度か問題となります．現実には集合Pを考えます．A⊂尿2の族を粛とします．
Ⅴ（A）をAに含まれる点の個数とします．このとき，β（P，A）＝乃Ⅴ（A）一匿nAlβ（P，粛）＝Sup月∈〟lβ（P，A）I印刷されたものかきれいかどうかの判断は人間の日にとおきます．β（P，ぷ）はPと粛か与えられたときの，頼っています．これでは客観性に欠ける部分かあるでPの遜における食い違い度です．さらに，しょう．というか，近似というからには数学的にモテβ（乃，粛）＝1nfエ）（P，粛）P（虎2ル化して較べてみたいと数理工学者は思うわけです．

lPl＝タブでは，どういう尺度か良いのでしょうか，何か客観的が粛の食い違い度となります．遜か戌2内の長方形な基準はないのでしょうか？ 先ほど閥値の高い値と領域の集合であるとき0（logプ？）であることか知られ低い値か均等に分布していると書きました．β。の例ています．

をみると0と1は斜めに1マス離れていて15と14もさて，ティザ行列に戻りましょう．乃×乃のディザ同じだけ離れています．0と2は15と13と同じだけ

行列には0から乃2−1までの数字かおのおの1回すつ離れています．この均等に分布していることによりど現れます．この値を頂点の個数だと思います．では，の部分を見ても部分の閥値の平均が同じ程度になり，上の粛に相当するものと考えましょう．乃×1，1×乃

平均的に黒い画素かばらまかれて灰色に見えると考えの集合を要素とする粛を考えてみましょう．この場られそうです．そこで，この均等に分布しているとい合，食い違い度か0になるものは半魔法陣と呼ばれてう状況を数学的に評価すればデイサ行列の近似の良さいます．つまー），半魔方陣とは乃×犯行列で要素かを評価できそうです．

0，…，乃2−1によって満たされてしさて，各行，各列の様々な基準があると思いますか，ここでは食い違い和か等しいものです．ここでは各行，各列の和の代わ度（dlSCrepanCy）［5，7，8，10］という基準で考えてりに任意の々×々の連続する部分行列の和を考えましみましょう．

ょう．つまり，々×々の連続する部分行列の集合か先食い違い度は［0，1］区間内の点列の一様性や，幾何ほどの粛に相当します．々×々の連続する部分行列のの点配置の一様性を測る尺度として生まれました．［0，和か等しい乃×乃行列を々×々一様乃×乃行列と呼び，1］区間内の無限点列5＝（sl，ざ2，…）か一様に分布していN（々，乃）を々×々一様乃×乃行列の集合とします．

声というのを任意の半開区間［α，∂＝こ対して無（忘】（sl，…，扉［α，占）l）≧∂−α3．〟×〟一様∩×∩行列
正整数乃＞1に対して，Z（乃，∽）を乃×乃整数行列で定義します．乃を無限大にとばしたとき：sの中ので要素か（0，・，∽−1）の要素であるものとします．

点が［a，b）に含まれる確率か占−αに等しければ一様

さらにZ（乃）⊂Z（乃，乃2）を（0，…，乃2−1）のすべてのであるというわけです．実際に一様である点列は存在要素を含む乃×乃行列とします．

します．無理数γに対して，5＝（51，52，・）を∫乃＝（γ乃）で与えます．ここで（γ乃）はγ乃の小数部分をあ々×々の連続した部分行列（以下，領域と呼ぶ）を私ノ＝斤≡5）を（才，ノ）を左上の要素とし，らわすものとします．このとき，Sは［0，1］区間で一様となることが知られています．では，点列がどれだ
け一様ではなヽ−かという尺度を考えましょう．先ほどの一様であることの式から，

腔′）

ト一三：≡∴ニ：…二；かつ），で定表します／ここでz′，ノ′は乃を法とします．

行列Pと々×々の領域札ノについてP（私ノ）で．私J

β（∫，乃）＝ Supll（5．，・，S乃）∩［α，∂）ト乃（∂−α）lO≦〟≦藩≦1に含まれるPの要素の総和をあらわすことにします．

を考えます．これか点列sの食い違い度です．点列に同様にCり＝C三雲）は要素（z，ノ）を最左要素とする々×1対する食い違い度と同様に2次元の有界な平面におけの領域であり，P（Cり）はCり含まれるPの要素の総る点の分布の食い違い度も考えることかできます．こ和をあらわします．ここでは，乃×乃行列に現れるゐれについては計算幾何の分野で盛んに研究されてきま×々領域の族した．児2＝［0，1］2の単位正方形と虎内の雅一頂点の矛如＝（斤至3）lz，ノ＝0，1，‥，乃−1）に着目していきます．この族矛烏，乃に対する乃×犯行

2005年1月号© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

（37）37

PP

0 1 2 3 4 5 6 78 9 10 1112 13 14 15

J㊥P＝β＝

16 17 18 19 20 21 22 2324 25 26 27 28 29 30 31

P P ‥・P32 33 34 35 36 37 38 39
40 41 42 43 44 45 46 47

次にkxk行列Pのcyclic column shiftをPの］列48 49 50 51 52 53 54 55

をノ＋1列に移し，々列を1列に移す操作とします．

56 57 58 59 60 61 62 63

同様にcycllCrOWShiftをPのl行をl＋1行に移し，々行を1行に移す操作とします．そして，この行列ク≠0 62 2 60 4 58 6 56にc回のcyclic column shiftとr回のcyclic row

55 9 53 11 5113 49 15

shiftを施した行列をP（C・r）と表記します．つまり，P16 46 18 44 20 42 22 40の（z，ノ）成分はP（C・r）では（（z＋γ）（mod々），（ノ＋c）

39 25 37 27 35 29 33 31
32 30 34 28 36 26 38 24（mod々））成分になります．このP（C，r）を使ってゐ2×

23 41 21 43 19 45 17 47々2行列β＝（β之，ノ）を

48 14 50 12 52 10 54 8

P（0，0） p（0・1）… P（0，々−1）

7 57 5 59 3 61 1 63

P（1，0）… P（1，々￣1）p（1，1）

図4 定理1（a）の具体例

P（烏￣1，0）p（々￣1，1） p（烏￣1，烏￣1）

列Pのkxk−dlSCrepanCyZ）h，h（P）をZ）h，n（P）＝maX P（R）−mlnP（R′）
〟（グ…

〟∈ぎ烏〝で定義します．ます，幻た，乃（P）＝0となる，つまり々×々一様乃×乃行列P∈Z（乃）はあるのかを考えます．
すると次のことか分かります．と定義します．このとき，任意のz，ノに対して九ノ＝
み，ノとなるのはl ＝l＋L］戊」かつ］′＝］＋Lz戊」（modk）．のときであることが分かります．
行列P＝（れノ）が，どのオ，Z′，ノ，ノ′に対しても定理1々×々一様乃×乃行列の集合N（々，乃）について次の性質か成†）立つ［1］．

れノーれノ＝♪z，ノー久りを満たすとき，行列Pを定差行列（constant−gap（a）々と乃かともに偶数ならばⅣ（々，乃）≠8．

matrix）と呼びます．

（b）々と乃か互いに素ならばN（々，乃）＝8．

定差行列の定義から，行，列の入れ換えに対して定（C）ゐが奇数かつ乃が偶数ならばⅣ（々，乃）＝軋差行列の性質は保存されます．また，正方行列のとき（d）任意の整数々と∽（々≧2，研≧2）に対してN（々，には，転置に対しても定差行列の性質は保存されるこ々椚）≠8．

とか分かります．

上のことから（a），（d）の場合には々×々一様乃×犯行列が存在します．実際，（a）についてはz十ノが奇数となる（z，ノ）成分九ノをカ乃＿トl，乃−トノに移すことで得られます．図4は乃＝8の場合の例となっています．

Pが々×々定差行列ならば，βは々×々一様行列になります．
P＝（九ノ），0＝（吼り）をそれぞれZ（々）の行列とします．そしてPと￠を用し−て次の二つの行列C（1）＝（d）については次の節で少し詳しくみてみましょう．

C（1）（P，￠）＝（cIJ）＝∂＋々2j∋，C（2）＝C（2）（P，0）＝（c；ノ）4．〟×々一様片肌X〟m行列の構成＝β＋々2（）を新たに作ります．このとき，Pか々×々定差行列ならば，任意の整数∽について々×々一様ゐ∽×々m行列を構成します．ます，烏×々一様々2×々2行列の存在を示

1．C（1）とC（2）はZ（々2）に含まれる行列であり，2 C（1）とC（2）は々×ゐ一様行列になります．

し，この結果を用いて点×々一様々刀×々澗行列に対す

さらにP≠￠ならば，C（1）≠C（2）となります．この結る結果を得ます．

果はN（々，々椚）の∽＝2の場合です．この結果を拡張

まず，βを定義します．これは々×々のすべての要することで，任意の整数ゐ，∽≧2に対してN（点，々m）素が1である行列Jと々×々行列Pのテンソル積で≠8であることか示せます．ポイントは研∈（0，…，す．

々m−1）は∽＝∑㌫1（Z々2王，0≦α≦々2−1と一意に表現

38（38）© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

オペレーションズ・リサーチ●

でき，Zの値ことに々×々定差行列を作ることにあります．また，々×々一様々mx々別行列であることの判

8 9 10 11

6 7 812 13 14 15す．例として々＝2，∽＝3の々×々一様々∽×々m行列を構成してみましょう．

0 1 4 50 1 8 92 3 6 72 3 10 118 9 12 13

4 5 12 1310 1114 15

6 7 14 15﹈23p＝［とします．このとき

P1▲0P（1・0）

図5 プ？＝3の定差行列の同値類の標準形と乃＝4の走差行列の同値類の標準形

00

PP（l・0）0OOll

00

P（0・0）〟＝々4

列置換，転置に対して定差の性質が保存されることも正方行列の場合と同様に成り立ちます．これらの性質

lO101

OO101OOOOO
10

ハU l▲
OP一P⊥ nr＋PO On︶

P一P▲ nr＋PP一P⊥ nr一戸 P■ P⊥ nr＋PP■ P⊥ nr一 P■ P．nr＋PP P

00

P（0・0）

を考慮し，行置換，列置換，串云置を施して同じ行列となる場合はその行列は同値であるとして同じものとみなします．ただし，転置を施して同じとなるのは正方P．nr＋P

これで朗（∽，乃）か同値類に分けられました．そこ

で各同値類の標準形を次の性質を満たす行列P＝︹r＋P︹r＋PP一口⊥P■P⊥IP▲
1nr＋P＋P一P⊥

行列だけです．

（れ，ノ）∈朗（∽，乃）とします．
（a）Pのすべての行はソートされている．つまりとすると，

み，0＜九1＜…＜れ乃＿1となっている．簡単のため，533552292160

17563427461958

3262

51442711431025 15162839481350

3424914204724

7565136381659374526314081 12954

これもノ＝0，…，乃−1に対し，CJ＝九ノとします．

5532と同様に九ノ＜九ノ＜…＜轟＿1，ノということです．

3330486322410〟＝

4 5 6 73 4 5定は0（∽々2）の領域計算量を用いて線形時間でできま＋々20 1 2 30 1 2となり，〃は2×2一様8×8行列となっています．
今まで述べてきた々×々一様々mx々m行列の構成には々×々定差行列か重要な役割をします．そして異なる走差行列を選ぶことで，異なる一様行列が得られます．では，行列の大きさか与えられたとき，定差行列はいくつあるのでしょうか？ ここでは，Z（乃）の左差行列の特徴づけについて考えていきます．少し一般的な場合で考えてみましょう．ます，朗（∽，乃）を0，…，〃甘乃−1を要素とし，すべてを要素とする∽×乃行列の集合とします．任意のz，ノ；z′，ノ1こ対して∽zJ＋∽り＝研り＋研。であるとき，行列〟＝（∽zJ）∈朗（∽，乃）は定差であると呼びます．これは先に定義した正方行列の場合と同じです．また，行列の行置換，2005年11月号

z＝0，‥，乃−1に対してγ〜＝れ，。とします．
．（b）Pのすべての列はソートされている．これは（a）（c）（a），（b）をまとめるとオ≦z′，ノ≦ノ′，かつ（z，ノ）≠（z′，ノ′）ならば九ノ＜れノとなります．
（d）九0＝Co＝杓＝0，♪m，〃＝刀甘和一1．
（e）Pは（cJ），（γ乙）によって決まり，れノ＝γヱ＋Gとなります．
乃＝3のときZ（乃）の定差行列の同値類の個数は一つだけであることは簡単に分かります．乃＝4のときは同値類の個数は三つです．また，乃＝5のときZ（乃）の定差行列の同値類の個数は一つだけです．朗（研，乃）の定差行列の標準形の集合を濫（刑，乃）であらわすことにします．特に，Ⅸ（乃，乃）を濫（乃）とあらわすことにします．整数研，乃＞0に対し濫（∽，乃）と濫（乃）がどのような集合なのかを考えましょう．
ます，与えられた行列P＝（久，ノ）∈濫（∽，乃）と0＝（吼り）∈Ⅸ（∽′，乃′）に対して拡張樺戸O（∂を定義します．
これはPO￠＝〃＝（ぁり）とすると′／ ゐz，ノ＝研乃れ／川」，Lノ／′り＋仇Ⅷ。dm，Jm。d乃．
で与えられます．これはテンソル積を用いると© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

（39）39のhorizontalrun（h−run）をその行の中で最長の連続〝＝∽′乃′p㊥ん，乃十ん乃⑳0した整数列とします．また，hてunの長さを含まれるとも書けます．
濫（∽，1），濫（1，乃）はともに一つの要素しかありま整数の個数とします．このとき，h−runの長さは少なせん．それらの要素の拡張積からつくられる行列は

くとも2となります．特に九0から始まる行でのh−朗（刑，乃）の要素で，定差行列になります．特に∽，乃runを1nitialh−runと呼びます．po，0から始まる列の＞1に対してl濫（研，乃）l≧2であり，濫（乃）では，つく長さを／とします．すると，このときの行美加，0一九0られた二つの行列は同じ標準形を持つので，乃＞1にはJとなります（図6参照）．

対して怪（乃）l≧1となります．また，P∈濫（∽，乃），￠∈Ⅸ（研′，乃′）ならばPO￠∈Ⅸ（〝び粥′，乃乃′）となりま

このh−runについて，どのh−runの長さもinltialh−runの長さを越えることはありません．

さらに言えば，すべてのhてunは同じ長さになりす．
Ⅸ（1，乃）の要素を単純行，濫（∽，1）の要素を単純列ます．

行差，列差の性質とh−runの性質から先ほど挙けと呼ぶことにします．

これにより濫（∽，乃）は次のように特徴づけられまた濫（肌，乃）の特徴づけは得られます．

々×々一様々mx々m行列の特徴つけかこれでできたす．
（a）P∈旺（∽，乃）はわけですが，実は定理1（d）については，任意の整数

P＝月㊥…㊥鳥α，々と∽（ゑ≧2，椚≧2）に対してⅣ（α々，々m）≠￠というと一意に表現できます．ただし，月，…鳥は長さが2ことがなりたちます．ここでは，ティジタルハーフト

以上の単純行，単純列の交互列です．∽＝乃＝1のとー ニングに用いられる手法を概観しました．特にオーきは々＝0と定義します．

ダードディザ法に用いられるBayerのディザ行列の（b）∽，乃＞0に対してⅨ（研，乃）＝8となります．

性質に着目して，食い違い度の観点から，乃×乃行列lⅨ（研，乃）l＝1となるのは乃＝1または研＝1であり，の性質について考察しました．特に，々×々一様々椚×かつそのときに限ります．この場合，濫（∽，乃）は単々m行列の特徴づけを行いました．

実際には，人間の視覚特性などを数理工学的にきち

純行，単純列のみからなります．
P∈Ⅸ（∽，乃）において整数ノ≠々に対して，列差をんとモデル化できればいいのですが，なかなかうまくれ一九々＝れノー丸々で定義します．定差行列の性質かいきません．提案した行列をブルーノイズ法に適用しら列差は行のとり方に依存しません．同様に行差を整た場合どうなるかは興味のあるところです．

数オ≠々に対してれ0一飯，0＝れノー如，ノと定義します．
このとき，どの行差と列差も同じとはなりません．
つまり，任意の0≦z＜々≦乃−1と0≦ノ＜J≦乃−1に謝辞 この原稿を書くことを薦めてくださった文教大学の根本俊男先生に感謝致します．

対して九た一動い≠れ。一九川となります．P＝（れノ）∈

参考文献∬（研，乃）とし，Pの一つの行を考えます．その行の最後の要素と最初の要素は連続しているとします．P［1］B Aronov，T Asano，Y Klkuchl，S C Nandy，SSasahara，T UnoA generallZatlOn Of maglC

SquareS Wlth applicatlOnS tO dlgitalhalftoning，

O J−1

accepted Annualmternational＄ymPoslum On Aなor−／／／〃〃、ヾ′仙／し−、′りノ小J／′J／／りJJけヾ．・トlし 二川1日
［2］浅野哲夫 ティシタル・ハーフトーニング：アルコ

リズム工学の視点

情報処理，Vo143，No5，pp554−

561，2002［3］T Asano，N Katoh，K Obokata，T Tokuyama
ComblnatOrlaland GeometrlC Problems Related toDigitalHalftonlng， 771eOntlCalFbundat10nS qf Com−♪／両J・†′′／ゴ‖川．Cし、0〃Jビ／り−，ノIJo丹／川／（フよ、・、（川〟」 v−−・−−ノ 」 √一−ノ＼−−「′ J ｝maxh−runS

図6 h−runの長さによる行列の分割
40（40）

Compuiat10na11m（qlng，LNCS2616，Springer，2003［4］T Asano

DlgltalHalftonlng Algorlthm Engl−© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

オペレーションズ・リサーチ

neerlngCha11enges，

1m77uns on hげand Syst，

M Grotschel，L Lovasz Eds，EIsevlerSclenCe，1995［8］B Chazelle・771e DISC7勿ancy Method．Randoml

VoIE86−D，No2，pp159−178，2003［5］T Asano，K Obokata，N Katoh，T Tokuyama

ness and Con4）lexl奴 Cambridge UnlVerSlty Press，MatrlXrOundlngundertheLp−dlSCrepanCymeaSureandltSappllCatlOntOdigltalhalftoning，

2000

Proc ACM− ［9］岩本明人，小寺宏，編 テシタルハードコピー技術，共S〟1〟劫〝ゆ05Z〟椚0乃βz5Cγ℃feAな0門Jん∽5，pp896−904，

SanFrancISCO，2002

立出版，2000［10］JMatou5ek Geometnc DISC7勿ancy，Sprlnger，［6］B E Bayer・ An optlmum method for two−1evel
rendltlOn Of continuous−tOne plCtureS， CoクゆYmCe

1991［11］T MltSa，KJParker．

Dlgltalhaiftonlng teCh−几・川・／・／／√／で／で／ノ小川√′／／州′′／（一旬／こ′川l−‥りJ〔、り川川′川トnlqueuSingablue−nOISemaSk，

cαfわ乃5，1，pp（26−11）−（26−15），1973

Vo19，Noll，pp1920−1929，1992［7］JBeck，V T S6s： Discrepancytheory HandbookJOt）t Soc Am，A／［12］村上伸一 画像処理工学，東京電機大学出版局，1996〆Combinatoncs，VoIII，pp1405−1446，R Graham，2005年1月号© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

（41）41