多角形カーネルに対応した統計的画像フィルタアルゴリズムの高速化
2023年度研究会推薦博士論文速報
［コンピュータグラフィックスとビジュアル情報学研究会］
諸戸雄治
（（株）Preferred Networks Software Engineer／（株）オー・エル・エム・デジタル 研究開発部門 Visiting Researcher／情報オリンピック日本委員会 育成強化部会）
■キーワード
画像処理／コンピューターグラフィックス／アルゴリズム
【背景】画像や動画の共有サイトの普及により，映像や画像を編集することが一般的になった
【問題】一部の画像フィルタは，高性能な計算機でも処理に時間がかかっていた
【貢献】計算量を改善するような革新的なアルゴリズムの提案し，誰でも利用できるようにするための社会実装を行った
コンピュータを用いて制作された華やかな画像や映像は，さまざまな基礎的な画像フィルタを組み合わせることで制作されています．また最近はYouTubeをはじめとする映像共有プラットフォームの台頭により，一般の人々にも映像制作の機会が広がっています．しかし，動画の高解像度化が進む現代において画像フィルタの処理コストは依然として高く，特に高品質なエフェクトがいくつもかけられた映像のリアルタイムプレビューやレンダリングは最新のコンピュータでも非常に時間がかかります．
たとえば，近年のスマートフォンでは画像の深度推定を行うことにより被写体以外をぼかし，一眼レフカメラで撮影したかのような被写界深度効果を得るポートレート撮影が人気を博しています．しかし，写実的なぼかし処理にかかる計算コストはとても高く，一枚の画像の処理に数秒から十数秒かかります．ほかにも，たとえばノイズ除去・美肌化フィルタなどは照明が十分でない場所での撮影で需要が高いですが，これらの中心技術として使われている中央値フィルタをリアルタイムに処理することは難しいです．
ぼかし手法の1つにガウシアンブラーという手法があり，高速な計算法が知られていますが，実際のレンズのぼけとは結果が大きく異なるため，クリエイターの間ではレンズブラーが好まれて使用されてきました（図-1）．しかし，レンズブラーはガウシアンブラーとは違い，高速な計算法は知られておらず，大きなぼかしを得たい場合は長い計算時間を我慢して待つか，ガウシアンブラーに頼るかという選択肢しかありませんでした．本研究では，レンズブラーや中央値フィルタなどの画像フィルタに対し，計算量から改善した高速なアルゴリズムを提案しました．
レンズブラーに関しては，既存手法では高速フーリエ変換を用いた計算時間O(WH log WH)の手法などが使われてきました（W, Hは画像の幅と高さ，rはカーネル半径）．これに対し提案手法では，競技プログラミングの分野で「いもす法」で知られているアルゴリズムをベースに，O(WH)の手法を提案し，実測でも10倍以上の高速化を達成しました．
中央値フィルタに関しては，既存手法ではソートを用いたO(WHr²)の手法か，ヒストグラムを用いたO(WH2ᵇ)の手法が主流でした（bは画像ピクセルのbit数）．ソート法はカーネル半径が小さい場合に特に有効です．ヒストグラム法はカーネル半径が計算時間に影響しませんが，8bit画像はともかく16bit画像やfloat画像の場合は使用できない特性がありました．それに対し本研究では，高速文字列解析や競技プログラミングの分野で知られていたWavelet行列をベースに二次元配列を扱えるように理論を拡張し，O(WH b log W)の手法を新規提案しました．これはカーネル半径にも影響されず，また画像のbit数の上昇にも強い，まったく新たな第三の中央値フィルタ計算法です．8bitのヒストグラム法と比べると10倍以上高速であり，ソート法と比較すると半径12以上で提案手法の方が高速になり，半径50で比較すると200倍以上高速になります（図-2）．この研究はACMが主催するCG分野最高峰の会議SIGGRAPH Asia 2022に採択され，更に特に優秀な研究に与えられるBest Paper Awardを受賞しました．
レンズブラーに関する研究は，大手動画編集ソフトであるAdobe Premiere ProやAfter Effectsのプラグインとして世界最大手のAdobeプラグイン配布サービス上で公開しており，プロ・アマ問わず全世界のスタジオ・クリエイターに使用されています．また中央値フィルタの実装も，世界中で最もよく使われる画像処理オープンソースライブラリであるOpenCVへ提供し，OpenCV 4.10に正式採用されました．これから世界中のアプリケーションで活躍することになるでしょう．
■Webサイト／動画／アプリなどのURL
個人ページ
https://cgenglab.github.io/ja/authors/moroto/
研究ページ1 （中央値フィルタ）
https://cgenglab.github.io/en/publication/sigga22_wmatrix_median/
研究ページ2 （レンズブラー）
https://cgenglab.github.io/en/publication/egsr21_blur/
Adobe 用レンズブラープラグイン
https://aescripts.com/fast-camera-lens-blur/
■動画URL（YouTubeチャンネル用）
中央値フィルタ研究紹介
https://www.youtube.com/watch?v=4_QNDYUcckM
レンズブラー研究紹介
https://www.youtube.com/watch?v=F5sRzwi_Q5E
（2024年5月31日受付）
（2024年8月15日note公開）
ー ー ー ー ー ー ー ー ー ー ー ー ー ー ー ー ー ー
取得年月：2024年3月
学位種別：博士（情報理工学）
大学：東京大学
ー ー ー ー ー ー ー ー ー ー ー ー ー ー ー ー ー ー
推薦文［メディア知能情報領域］コンピュータグラフィックスとビジュアル情報学研究会
映像制作の現場では，さまざまな画像フィルタが多用される．しかし求められる映像が高解像度になるにしたがって，最新の計算機を使っても処理に時間がかかる問題があった．本博論ではレンズブラーや中央値フィルタ等の計算オーダーを根本的に改善する新しいアルゴリズムを提案し，十数倍から数百倍の高速化を実現した．
研究生活 高校時代から放送部に所属し，映像制作を行いNHKのコンテストに参加していました．特に私が活動していた時期は一眼レフカメラで映像を撮ることが一般的になり始めた頃で，私もカメラ沼に沈んでいきました．映像制作では編集段階でレンズブラーを追加することも日常茶飯事なのですが，レンズブラーエフェクトは非常に低速で，皆がもどかしさを感じていました．私はコンピュータ部にも所属し，情報オリンピックやACM-ICPCなどにも参加していたのですが，そこで培ったアルゴリズムの知識でこの問題を解決できることに気づきました．
現代では，問題が複雑化しており，単一の興味や知識だけで問題を解決することは難しくなっています．複数の興味分野の知識を吸収することは，新たな問題の発見や解決に役立つと考えています．私の博士課程期間中も，研究活動のほかにプログラミングコンテストへの参加や映像出展活動を行ってきました．皆さんもぜひ幅広い興味を持ち，知識に貪欲であり続けてください．