ディジタル・ハーフトーニング：アルゴリズム工学の視点
8
0
0
全文
(2) -2 Bayer. -1. 8. 8. -3. 2. 2. 2. れた 2 値画像を示したものです． 単純 2 値化法では画像全体で 0.5 という固定の閾値を 使って 2 値化を行いましたが，場所によって異なる閾値 を用いるのがオーダードディザ法（Ordered Dither 法）で. 誤差拡散法（Error Diffusion）とか誤差伝播法の名前で. -2 に示したような行列を周期的に. 知られている方法では明るさの平均値を保つことが可. す．この方法では，. 並べることにより，入力の画像全体を覆い尽くします．. 能です．この方法では，単純 2 値化法と同様に固定の閾. このような小行列はディザ行列と呼ばれています．1 か. 値を使いますが，丸めの際に生じた誤差を周囲の未処. ら 64 までの整数がちょうど一度ずつ現れていることに. 理画素に拡散するところに違いがあります．たとえば，. 注意してください．. ある画素の明るさが 0.4 だったとしましょう．これは固. 画像をディザ行列で覆い尽くすと，各画素には行列. 定の閾値である 0.5 未満ですから，0 に丸めることにな. の 1 つの要素が対応することになりますが，その値を 65. ります．この丸めの誤差は 0.4 ということになりますが，. で割った値を 2 値化のための閾値として用います．たと. この誤差を周囲の未処理画素に拡散するのです．一方，. えば，7 に対応するところでは，入力画像における対応. 明るさが 0.7 であれば 1 に丸められますが，このときの. 画素の明るさが 765 以上なら出力の値を 1 に，765 未. 誤差は 0.3です．. 満なら出力の値を 0 にします．. 画素をラスターの順に走査するものとしましょう．. 今度は灰色の画像が入力された場合でも，約半数の. そうすると，未処理画素は，右，左下，下，右下とい. 画素は 0 に，残りは 1 に丸めることになりますから，多. うことになります．これらの画素に. 少明るさが変化しても安定的に灰色に見える画像を出. 誤差を伝播するのです．. 力することができます．. -3 は，この方法によって得ら. -4 に示した割合で. 誤差拡散法では丸めの誤差を伝えていきますから， IPSJ Magazine Vol.43 No.5 May 2002. −2−.
(3) -4. Floyd-Steinberg. （randomized rounding）という考え方を用いました．これ は，0,1 区間の実数 x を確率 x で 1 に切り上げるという 入力画像の明るさの総和と出力画像の明るさの総和の. ものですが，まさに上記の白色雑音による 2 値化と等価. 差は高々1 以内ということになります．. です．この考え方はランダム化アルゴリズム（rand-. これまでに，単純 2 値化法，オーダードディザ法，誤. moized algorithm）の 1 つの典型的な実現方法としてもよ. 差拡散法について見てきました．単純 2 値化法でも意外. く使われていますから，アルゴリズム関係者には白色. に良い結果が得られることがありますが，細部の再現. 雑音による 2 値化というよりは理解されやすいでしょ. 性には問題があります．その点，オーダードディザ法. う．. は細部の再現性の点では優れていますが，特有の模様 が見えてしまうという欠点があります．誤差拡散法は 安定的に良い画質の画像を生成することができるので，. 単一の閾値による単純 2 値化法を一般化するのに，変 動する乱数を閾値として用いる方法を説明しましたが，. 実際のプリンタでもよく使われています．. 毎回乱数を発生するのは計算コストがかさみます．そ こで，毎回乱数を発生する代わりに，あらかじめ作っ ておいた乱数表を用いるという方法が考えられます． 前章では主たる方法の原理だけを説明しましたが，. この乱数表に相当するのがディザ行列です．乱数表が. 実用に供するためにはさまざまなチューニングが必要. 小さければ，乱数表のパターンが見えてしまう危険性. となります．本章では，従来法に対してどのような変. がありますから，メモリが許す限り大きな乱数表を使. 形が可能かを探るとともに，アルゴリズムに関連する. うのが有利になります．実際，この考え方に沿った方. 問題について考えます．. 法が提案されています．ブルーノイズマスク法という 名前で一般に知られている方法ですが, この方法では乱. 2. 数の技術を駆使して作った 256 × 256 のような大きなデ. 先に説明した単純 2 値化法は，それぞれの画素を独立. ィザ行列を用います．. に 2 値化するもので，アルゴリズム的には最も簡単なも のです．しかし，画像全体で固定の閾値を用いるため. さて，オーダードディザ法の性能がディザ行列に依. に，中間色（灰色）の領域をうまく表現できません．こ. 存することは明らかです．では，どんなディザ行列が. の欠点を補う 1 つの方法は白色雑音法と呼ばれるもので. 最適でしょうか？ 前節で説明したディザ行列は再帰. す．すなわち，各画素の明るさを 0 ∼ 1 の白色雑音と比. 的に作られたものです．その作り方は以下の通りで. 較するというものです．白色雑音は 0,1 区間の一様乱. す 8）： まず，1 × 1 のディザ行列 D01 から始めて，再帰的. 数と考えることができますから，結局，0,1 区間の乱. に Dk k1, 2, …を次のように定義します．. 数との大小比較で出力のレベルを決めることになりま す．たとえば，画素の明るさが 0.3 の場合，0.3 以下の乱 数が生成される確率は 0.3 ですから，この画素の出力値. Dk. の期待値は 0.3 ということになります．したがって，明. 4D 4D. k13Uk1 k1. 4Dk1Uk1 4Dk12Uk1. . ただし，U k は各要素がすべて 1 の 2 k × 2 k の正方行列. るさが 0.5 で均一な領域では 0.5 の確率で黒点が生成され. です．. ることになり，全体としては灰色に見えることが予想. これでディザ行列の作り方は分かりましたが，なぜ. されます． これと同じ考え方はアルゴリズムの分野でも知られ. この行列を使うのでしょう．1 から 2 2k の整数を行列内. ています．“Randomized Algorithms”のテキストで有名. にばら撒くだけなら，他に何通りも考えられます．デ. な Raghavan が VLSI の概略配線経路決定に確率的な丸め. ィザ行列は，周期的に繰り返すことにより画像を覆い. 43巻5号 情報処理 2002年5月. −3−.
(4) 尽くして，画素とディザ行列の要素の対応を作るため に用いました．したがって，たとえば 8 × 8 のディザ行 -5. 列を用いる場合，i, j 要素の番号と i8, j8 の要素の 番号は等しいことになります．この周期性を頭に入れ てもう一度ディザ行列を見てみましょう．1 から 4 まで 等距離の所にあることが分かるでしょう．同様に，. ることを示すことができます．点を単位正方形の内部 √ にランダムに配置してもディスクレパンシーは O n. 5,6,7,8 も互いに等距離にあり，しかも 1 ∼ 8 の場所を見. のままであることが知られています．ところが，点を. ると，全体がちょうど等間隔で並んでいることが分か. うまく配置すると，この差を O log n にまで小さくする. ります．. ことができます．. の番号がどのように現れているかを見ると，ちょうど. では，等間隔で点を並べるのがいいのでしょうか？. オーダードディザ法に特有の模様を消すのにディザ. この問に答えるために，規則的に並んだ点の模様を考. 行列を回転する方法が考えられますが，回転しなくて. えてみましょう．人間の目で知覚するのは平均的な明. も模様を消す良い方法があります．単にディザ行列の. るさですから，一様な明るさに見えるためには，どん. サイズを大きくするのです．ディザ行列としては 8 × 8. な小領域をとっても，そこでの平均的な明るさがほぼ. 程度のものが一般的ですが，一挙に 128 × 128 あるいは. 一定であることが必要です．規則的に点が並んでいる. 256 × 256 にまで拡大するのです．ここまで大きな行列. のですから，どのように小領域をとっても平均的な明. を注意深く設計すればパターン特有の模様が目立つこ. るさ，すなわち領域内の白点の個数の密度はほぼ一定. ともありません．問題は，大きなディザ行列をいかに. であると思われますが，実際にはかなり変動がありま. して設計するかと，ディザ行列を蓄えるための記憶領. す．白点は規則的に並んでいますから，同じ 8 × 8 の大. 域の大きさです．. きさの正方形であっても，ちょうど白点が境界上にく. 上では大きな乱数表と表現しましたが，このように. るようにした場合と少し斜めにずらした場合では，2 辺. 巨大なディザ行列を用いた方法のことをブルーノイズ. の上にあった白点の個数分だけ異なることになります．. マスク法といいます．たとえば，256 × 256 のサイズの. このような密度の差をディスクレパンシー（食い違い. ブルーノイズマスクを設計する場合を考えてみましょ. 度，discrepancy）といいます．. う．行列の要素は 1 から 256 までの整数ですから，同じ 数がちょうど 256 回ずつ含まれていることになります．. ディスクレパンシーに関しては計算幾何学の分 野 7），11）で詳しく調べられています．たとえば，単位正. このとき大事なことは，1 から 256 までのどの数 p に対. 方形の内部に n 個の点を配置する問題を考えます．軸平. しても，p 以下の数を持つ要素が一様に散らばるように. 行な長方形 R を任意にとって，その面積 A R と，R に含. 設計されていることです．たとえば，p16 の場合，全. まれる点の個数 n Rにより，. 体の 116 の要素が 16 以下の数を持つことになりますか ら，面積が 16 の領域あたり平均的に 1 つの要素を選ぶこ. D R n AR nR . とになります．格子状に点を配置したとき，4 × 4 の正 方形領域を考えると，その頂点にちょうど点が配置さ. という差を長方形 R のディスクレパンシーと定義します √ √ n× n のグリッド上に点を配置すると （ -5 参照）． √ n の長方 いう規則的なパターンだと，幅が 1 で高さ 1 √ n 形 R を考えると，グリッドに辺が重なる場合には 2 √ √ n 2 n 個の点が含まれます．このとき，D R √ √ n となります．実際，D R の値の最大値は n であ. れている特別な場合には 4 点を含みますが，それ以外の 場合には 1 点しか含みません．これに対して，16 × 1 ま たは 1 × 16 の細長い長方形領域を考えると，位置によっ ては 5 個の点を含む場合も，4 個の点を含むこともあり ます．さらにまったく点を含まないこともあります． このように，長方形領域を考えると格子状に点を配置 IPSJ Magazine Vol.43 No.5 May 2002. −4−.
(5) -6 a. . b. 良好な結果が得られています 1）． するのはディスクレパンシーの意味でも良くないこと が分かります．ディスクレパンシーのところでも説明 これまでに述べてきた方法では，さまざまなテスト. しましたように，規則的なパターンよりも一見ランダ. 画像に対して出力画像を生成した後，人間の目視によ. ムに見えるパターンの方が望ましいのです．. って画質の良し悪しを判定するというものがほとんど で，出力画像の画質を定量的に評価することはあまり 誤差拡散法は画質の点では優れていますが，明るさ. ありませんでした．画像処理の分野では画質評価につ. が一定の部分で誤差拡散係数を反映する模様が生じて. いて多数の研究がありますが 10），2 値画像の画質につい. しまうという欠点が指摘されています．模様を消すに. てはあまり研究が進んでいません．. は誤差拡散係数にランダムな成分を持たせればよいの. 上記の研究でほぼ共通している最適化の基準は次の. ですが，そうすると今度は画像がぼけてしまうという. ようなものです．入力の画像を行列 A aiji,j1,..., N によ. 問題が生じます．1 つの解決方法は，明るさが一定の部. って表します．行列の各要素 aij は，格子点 i, j における. 分と明るさが急激に変化するエッジ部で誤差拡散係数. 明度を表します．通常，明度は 8 ビット程度の整数で表. を変えるというものです．エッジ部ではさらにエッジ. 現されますが，ここでは 0, 1 区間の実数として表現す. の方向にのみ誤差を拡散することも考えられます 12）．. ることにします．すなわち， 0 aij 1, i, j1, ..., N. 模様を消すもう 1 つの方法は，ラスター走査を別のも のに変更することです．ラスター走査は，すべての画. です．簡単のため画像は 1 辺の長さ（画素数）が N であ. 素を一度ずつ訪問する 1 つの順序を決めるものですが，. る正方形であると仮定し，全画素数を n と記すことにし. 一般にそのようなものは，空間（平面）充填曲線また. ます．すなわち，n N × N．. はスペースフィリングカーブ（space-filling curve）と呼. 出力画像は同じサイズの 2 値行列 B bij です．入力. ばれています 2）．実際，古くから知られているヒルベル. 画像と人間の目視でよく似ている出力画像を求めるこ. ト曲線のような再帰的に定義されたスペースフィリン. とが問題です．そのために人間の視覚特性をモデル化. グカーブを用いる方法も提案されていますが，適用可. する必要がありますが，画像処理の分野で一般的に用. 能な画像サイズに大きな制約があるのと，曲線の規則. いられているのは，重みつき平均値の 2 乗和 W A, B を. 性が出力画像に模様となって現れるという問題があり，. 最小化するという基準でしょう 10）． このように入力画像と出力画像の距離を定めたとき，. 実用的には問題があります．その制限から逃れるため に，指定された大きさの格子平面を埋め尽くすランダ. 目標は入力画像 A との距離 W A, B を最小にする 2 値画. ムスペースフィリングカーブを効率よく設計する方法. 像（行列）Bを求めることとなります．. が提案されています（. -6参照）．. スペースフィリングカーブの利点は，本来 2 次元的な データに 1 次元的な順序を導入できることです．このと. 人間の視覚特性を考慮すると上記のような最適化基. き問題となるのは，スペースフィリングカーブ上での. 準になりますが，問題の計算複雑度を解析するために，. 近傍がどの程度 2 次元的な広がりを持っているかです. 上記の基準を若干簡単にした基準を用いましょう．. が，これについては Asano-Ranjan-Roos5）による理論的. （1）まず，人間の視覚特性を考慮するためには重み行. 解析があり，素朴な予想を超える広がりを持たせるこ. 列 V は必須ですが，ここでは重みはすべて 1 であると仮. とが可能であることが分かっています．この結果に基. 定します．平均化のための領域のサイズが比較的大き. づいて，ランダムスペースフィリングカーブ上での誤. い場合には許されないことですが，主として 2 × 2 程度. 差拡散法が実装され，画質と計算時間の両面で比較的. の小さな領域を想定すると，重みを無視しても影響は. 43巻5号 情報処理 2002年5月. −5−.
(6) 少ないと考えられます．重みを無視すると，領域 R にお. しますが，これがディジタルハーフトーニング問題を. ける平均値を領域 R 内の行列要素の和で置き換えること. 最も一般的に定義したものと考えます．. ができます． P Gn, F, p :. Lp-. （2）次に，上では誤差の 2 乗和を評価しましたが，ここ. 0,1-行列 A∈A，. Gn 上の領域集合 F，および整数 p が与えられたとき，. では，より一般的な L p ノルムにおける基準を考えるこ とにします．. DistpF A, B ARB R p 1/p. （3）さらに，上では小領域として各点を中心とする正. R∈F. 方形領域だけを考えましたが，ここでは領域の連結性 を最小にする 0,1 -行列 B ∈ Bを求めよ．. すら仮定せずに，任意の画素集合を領域とみなすこと にします．したがって，入力画像の他に小領域の集合. 1. も入力の一部とみなします． 問題を一般的に定義するために，画素集合に対応す. 上に定義した問題 P Gn, F, p は，2 次元の行列に対し. る集合 Gn を Gn 1,1 , 1, 2 , ..., N, N p1, p2, ..., pn と定めます．. てだけでなく，1 次元の配列（ベクトル）に対しても同. ただし，nN2 は全画素数を表します．このとき，行列. 様に定義することができます．1 次元の場合には領域の. 上の小領域は Gn の部分集合として表すことができます．. 代わりに区間の概念を用いるのが自然です．特に，長. 以下では，評価のための領域の集合を F という記号で表. さ k のすべての区間からなる集合 Fk を考えたとき，問題. すことにします．. P Gn, F, p は多項式時間で解けるでしょうか．この問題. AAGn をインデックス集合 Gn を持つ 0,1 行列全体. に対しては古くから Viterbi のアルゴリズム（本質的には. の集合とし，BB Gn をその部分集合で 0, 1 の要素か. 動的計画法に基づく方法）として知られている方法が. らなる行列全体とします．F に属する領域を R とすると. あります．それを用いると O 2 k n の時間と記憶スペー. き，R における行列 A の要素の和を AR と表します．す. スで最適解を求めることができます．計算時間をあま. なわち，. り増やさずに記憶スペースを n に比例する程度に削減す る方法 3） も知られていますが，いずれにしても計算時 間は区間の長さ k に関して指数関数的に増加してしまい. AR piR api .. ます．紙数の関係で詳しいことは説明できませんが，k さて，領域の集合 F を固定したとき，A の 2 つの行列 Aと A'の間の距離 DistpF. に関しても多項式の計算時間と記憶スペースで最適解. A, A' を. を 求 め る 方 法 が 提 案 さ れ て い ま す 3 ）． 実 際 に は O n 1.5 log 2 n 時間と O n スペースのアルゴリズムと，. DistpF A, A' ARA'R p 1/p. O k 2n log n 時間と O nk スペースのアルゴリズムが提. R∈F. 案されています．k が比較的大きい場合には前者が有利 によって定めます．ただし，p は ∞ を含む正整数です．. ですが，k < n1/4 の場合には後者が有利です．. この距離を領域の集合 F に関する L p 距離と呼びます．. 2. 特に，p∞ の場合は， DistpF A, A'plim DistpF A, A' →∞. 1 次元の場合には，同じ長さの区間の集合を領域集合. max ARA' R. F とみなした場合には多項式時間で最適解が求まること. RF. が分かりましたが，2 次元の場合にはかなり事情が異な ります．基本的な観察は，領域集合 F R1, R2, ..., Rm. となります． 以上の準備の下に問題 P G n , F, p を次のように定義. と画素集合 Gn p1, p2, ..., pn との接続関係を表す制約 IPSJ Magazine Vol.43 No.5 May 2002. −6−.
(7) 行列 C Gn, F c ij を. totally unimodular であるような領域の集合 F が与えられ たとき，すべての R ∈F に対して A RB R 1 が成り. cij. p ∈ R のとき， 10 それ以外のとき i. 立つような整数値行列 B bij が存在する．. j. 上記の結果を定理の形でまとめると次のようになり ます 4）.. 3. と定めるとき，この行列が totally unimodular であれば，. Gn をインデックス集合とする画像. 多項式時間で最適解を求めることができるというもの. 行列 A と領域集合 F が与えられたとき，制約行列 C G n ,. です．ただし，行列 C が totally unimodular であるのは，. F が totally unimodular であれば，領域集合 F によって定. C のどの正方部分行列をとっても，その行列式の値が 0,. まる基準において最適な 2 値行列 B を多項式時間で求め. 1, 1 のいずれかであることです．. ることができる．. 意味のある領域集合として最も簡単なものはすべて の 2 × 2 領域からなるものでしょう．残念ながら，この 領域集合に対応する制約行列は totally unimodular ではあ. スペースフィリングカーブ上での区間集合によって. りません．実際，この場合については最適解を求める. 領域集合 F を定義する以外にも有望な方法があります．. 問題が NP-完全であることが証明されています 3）．. 最初の問題は totally unimodular の範囲内でどこまででき. 1 次元の問題は区間集合に対して多項式時間で解けま. るかを検討することです．. した．区間集合に対しては制約行列が行方向に 1 が連続. F R1, R2, ..., Rm を Gn の 1 つの分割集合族としまし. するという性質を持ちますが，そのような性質を持つ. ょう．すなわち，Gn のどの要素も F の 1 つの領域に含ま. 行列は totally unimodular であることが分かっているから. れ，F のどの 2 つの領域も互いに共通部分を持ちません．. です.. このような分割集合族 F が与えられたとき，F の領域の 合併をとっては新しい領域を定義していくというやり 方で新たな領域集合Fˆ Rˆ , Rˆ , ..., Rˆ を構成します．こ 1. 2. M. のとき，各 Rˆ i は F の領域または F の領域の合併として ˆ とR ˆ に対して， 与えられ，しかも任意の 2 つの領域 R. 行列丸め問題に関して古くから知られている定理に 次のようなものがあります．. i. j. 行列 A のすべての列，すべての行，行列全体からなる集. Rˆ i Rˆ j , Rˆ j Rˆ i , Rˆ i Rˆ j ∅のいずれかが必ず成り立たなけ ればなりません．このように定義される領域集合 Fˆ を分. 合 F が与えられたとき，すべての R∈F に対して. 割に対応する領域族 F のラミナー（laminar）拡張といい. A R B R 1 が成り立つような整数値行列 B bij が. ます．. 1. Baranyai 6. 1974. 実数値行列 A a ij と，. 4. 存在する．. -. -. -. 4. 2002 Fˆ を入力画像. A のインデックス集合 Gn の 2 通りの分割に対応する分割 集合族 F と F のラミナー拡張の和集合 Fˆ Fˆ として. この定理ではすべての列，すべての行，行列全体か らなる集合が F として与えられていますが，対応する制. 1. 2. 1. 2. とができます．したがって，上記の基本的な観察に照. ˆ に対応する制約行列 定義される領域集合とすると，F C G , Fˆ は totally unimodular である．. らしてみると，条件を満たす 2 値行列の存在を主張する. したがって，領域集合 Fˆ に関する基準で最適な解を多. だけではなく，max R ∈ F A R B R の値を最小にする. 項式時間で求めることができることは保証されました．. 2 値行列を多項式時間で求めることができることを保証. 実用的にはネットワークフローによる定式化で解ける. できるのです．また，Baranyai の定理ではすべての列，. かどうかが問題ですが，領域集合 F の構成方法に対応. すべての行，行列全体からなる集合のみを対象として. するネットワークにより解を求めることができます．. 考えましたが，対応する制約行列が totally unimodular で. 紙数の関係で詳細な説明は省略しますが，. あればよいので，次のように拡張することができます．. 要領でネットワークを構成すればよいのです 4）．. 約行列 C Gn, F は totally unimodular であることを示すこ. 2. n. 実数値行列 Aa ij と，制約行列 C G n , F が. 43巻5号 情報処理 2002年5月. −7−. -7 に示した.
(8) -7 2. 上で述べた最小コストネットワークフローを求める アルゴリズムは実際に実装され，印刷用の標準画像デ ータに対して計算機実験が行われています 4）．最小コス トネットワークフローを求めるアルゴリズムは，効率 のよいアルゴリズムとデータ構造のためのライブラリ -8. である LEDA9）を利用して実装されています．原画像の サイズは 4096 × 3072 ですが，実験では 1024 × 768 に単 純縮小したものを用いています．実験結果を比較して 見れば，本稿で紹介した方法は一般的に誤差拡散法よ りもメリハリのきいた画像を得る傾向があります（. -8. pp.307-316（1998）. 3）Asano, T., Matsui, T. and Tokuyama, T.: Optimal Roundings of Sequences and Matrices, Nordic Journal of Computing, Vol.7, No.3, pp.241-256, Fall （2000）. 4）Asano, T., Obokata, K., Katoh, N. and Tokuyama, T.: Matrix Orunding Under the Lp-Discrepancy Measure and Its Application to Digital Halftoning, Proc. ACM-SIAM Symposium on Discrete Algorithms, pp.896-904, San Francisco（2002）. 5）Asano, T., Ranjan, D. and Roos, T.: Digital Halftoning Algorithms Based on Optimization Criteria and their Experimental Evaluation, IEICE Trans. Fundamentals, Vol.E79-A, No.4, pp.524-532（Apr. 1996）. 6）Baranyai, Z.: On the Factorization of the Complete Uniform Hypergraphs, in Infinite and Finite Sets, eds. A. Hanaj, R. Rado and V. T. Sós, Colloq. Math. Soc. János Bolyai, 10, pp.91-108. 7）de Berg, M., van Kreveld, M., Overmars, M. and Schwartzkopf, O. : Computational Geometry: Algorithms and Applications, Springer-Verlag （1997）. 浅 野 哲 夫 訳 : コ ン ピ ュ ー タ ・ ジ オ メ ト リ ー , 近 代 科 学 社 （2000）. 8）小寺監修: 実践ディジタルカラー画像の設計と評価, トリケップス （2000）. 9）LEDA homepage: http://www.algorithmic-solutions.com/as_html/products/products.html 10）Miyahara, M., Kotani, K. and Algazi, V.R.: Objective Picture Quality Scale（PQS）for Image Coding, IEEE Trans. on Communications, 46, 9, pp.1215-1226（Sep. 1998）. 11）Preparata, F.P. and Shamos, M.I.: Computational Geometry: An Introduction, Springer-Verlag（1990）. 浅野孝夫, 浅野哲夫訳: 計算幾何学, 総研出版（1992）. 12）臼井, 浅野: ハーフトーン化方法およびハーフトーン化装置並びにハ ーフトーン化プログラムを記録したコンピュータ読み取り可能な記録 媒体, 特許広報9951700（1998） ． （平成14 年4 月4 日受付）. 参照）． 本稿はディジタルハーフトーニングに関する 一連の論文に基づいています．それらの論文の共著者 である徳山豪氏（東北大学），小保方幸次氏（JAIST），藤 川直樹氏（JAIST 卒業生），松井知己氏（東京大学），玉 木久夫氏（明治大学），加藤直樹氏（京都大学），永持仁 氏（豊橋技術科学大学），臼井信昭氏（富士通研究所）に 感謝します．また，有益なコメントをいただいた伊藤 大雄氏（京都大学），David Mount 氏（Maryland University, USA），清見礼氏（東京大学），中野浩嗣氏（JAIST）に感 謝します． 最後に，著者のハーフトーニングに関する研究は文 部科学省の科学研究費（特定研究および基盤研究）と 栢森情報科学振興財団の援助を得て行われたものです．. 1）Asano, T. : Digital Halftoning Algorithm Based on Random Space-Filling Curve, IEICE Trans. on Fundamentals, Vol.E82-A, No.3, pp.553-556, Medgeh（1999）. 2）Asano, T., Katoh, N., Tamaki, H. and Tokuyama, T. : Convertibility Among Grid Filling Curves, Proc. ISAAC98, Springer LNCS 1533,. IPSJ Magazine Vol.43 No.5 May 2002. −8−.
(9)
関連したドキュメント
Proof of Theorem 2: The Push-and-Pull algorithm consists of the Initialization phase to generate an initial tableau that contains some basic variables, followed by the Push and
An easy-to-use procedure is presented for improving the ε-constraint method for computing the efficient frontier of the portfolio selection problem endowed with additional cardinality
Restricting the input to n-vertex cubic graphs of girth at least 5, we apply a modified algorithm that is based on selecting vertices of minimum degree, using operations that remove
These constructions are also used to obtain extension results for maps with subexponentially integrable dilatation as well as BM O-quasiconformal maps of the
We study the classical invariant theory of the B´ ezoutiant R(A, B) of a pair of binary forms A, B.. We also describe a ‘generic reduc- tion formula’ which recovers B from R(A, B)
Based on sequential numerical results [28], Klawonn and Pavarino showed that the number of GMRES [39] iterations for the two-level additive Schwarz methods for symmetric
We note that in the case m = 1, the class K 1,n (D) properly contains the classical Kato class K n (D) introduced in [1] as the natural class of singular functions which replaces the
In particular this implies a shorter and much more transparent proof of the combinatorial part of the Mullineux conjecture with additional insights (Section 4). We also note that
