画像の補間と間引き

画素は? 画素は: 正方形 円板 小さな光る点 ではない。 画素の見え方はディスプレイによって 異なる 画素は「標本」である 長さはない 　　異なる 画素は「標本」である 長さはない 面積もない 見ることはできない 座標がある 値がある

標本化について 世の中の殆どのものは連続的なものである。が , コンピュータの中の全ては離散的なものである。 連続関数を離散関数に写像する過程は標本化という 連続な値をを離散的な値に写像する過程は量子化という コンピュータで画像を表現・表示するために、標本化と量子化を行う必要がある (8-bits) discrete value discrete position

画像は2次元関数 理想的なグレー画像は濃淡値の連続的な関数I(x,y) 高さの「場」として表示することができる 一般的に、画像は「式」（連続的な解析関数）で表現できない 代わりに、画像を表で表現する この表をどうやって埋める？

標本化格子 デルタ関数の格子を画像の連続関数にかけることによって表の値を生成することができる

画像を標本化する 結果は標本点（画素）の集合である

画像の幾何学変換： （拡大、縮小、回転、移動など） 画像の幾何学変換： 　（拡大、縮小、回転、移動など） 画素の位置、密度が変化する 正しく処理するために： 　①　離散画像を復元して、元の連続画像を再構成する ②　復元した連続画像に対して、再度標本化を行う。 これをうまく処理しないと．．．

エイリアシングの例 エイリアシング（aliasing)：画像や文字の縁辺のぎざぎざ. エイリアシングの原因は標本化と再構成にある

エイリアシングの例

エイリアシングの例

エイリアシングの例 Texture Errors point sampling

標本化密度 How densely must we sample an image in order to capture its essence? If we under-sample the signal, we won't be able to accurately reconstruct it...

標本化密度 不適切な標本化を行うと、その信号を再構成するとき、元の信号と異なった　“簡単のもの”になってしまいます。それはaliasingです Image from Robert L. Cook, "Stochastic Sampling and Distributed Ray Tracing", An Introduction to Ray Tracing, Andrew Glassner, ed., Academic Press Limited, 1989.

標本化密度 不適切な標本化密度によるAliasing

標本化理論 When sampling a signal at discrete intervals, the sampling frequency must be greater than twice the highest frequency of the input signal in order to be able to reconstruct the original perfectly from the sampled version (Shannon, Nyquist)

Fourier Analysis – Harmonics All periodic signals can be represented as a summation of sinusoidal waves. Images from http://axion.physics.ubc.ca/341-02/fourier/fourier.html

Fourier Analysis - Signals Every periodic signal in the spatial domain has a dual in the frequency domain. This particular signal is band-limited, meaning it has no frequencies above some threshold spatial domain frequency domain

Remember Fourier Analysis? We can transform from one domain to the other using the Fourier Transform. frequency domain spatial domain Fourier Transform Inverse Fourier Transform Discrete Versions ?

Images from Mark Meyer http://www.gg.caltech.edu/~cs174ta/ Convolution? Discrete versions ? h Images from Mark Meyer http://www.gg.caltech.edu/~cs174ta/

Understanding Convolution Some operations that are difficult to compute in the spatial domain can be simplified by transforming to its dual representation in the frequency domain. For example, convolution in the spatial domain is the same as multiplication in the frequency domain. And, convolution in the frequency domain is the same as multiplication in the spatial domain

Sampling in the Frequency Domain Fourier Transform original signal Fourier Transform sampling grid (multiplication) (convolution) Fourier Transform sampled signal

Reconstruction If we can extract a copy of the original signal from the frequency domain of the sampled signal, we can reconstruct the original signal! But there may be overlap between the copies.

Proper Reconstruction Separate by removing high frequencies from the original signal (low pass pre-filtering) Separate by increasing the sampling density If we can't separate the copies, we will have overlapping frequency spectrum during reconstruction → aliasing.

Filters Filters are used to reconstruct a continuous signal from a sampled signal (reconstruction filters) – just saw that  band-limit continuous signals to avoid aliasing during sampling (low-pass filters) – Desired frequency domain properties are the same for both types of filters Often, the same filters are used as reconstruction and low-pass filters

The Ideal Filter Unfortunately it has infinite spatial extent Every sample contributes to every interpolated point Expensive/impossible to compute spatial frequency

Problems with Practical Filters Many visible artifacts in re-sampled images are caused by poor reconstruction filters Excessive pass-band attenuation results in blurry images Excessive high-frequency leakage causes "ringing" and can accentuate the sampling grid (anisotropy) frequency

Gaussian Filter This is what a CRT does for free! spatial frequency

Box Filter / Nearest Neighbor Pretending pixels are little squares. spatial frequency

Why is the Box filter bad? (Why is it bad to think of pixels as squares) Original high- resolution image Down-sampled with a 5x5 box filter (uniform weights) Down-sampled with a 5x5 Gaussian filter (non-uniform weights) notice the ugly horizontal banding

Tent Filter / Bi-Linear Interpolation Simple to implement Reasonably smooth spatial frequency

Bi-Cubic Interpolation Begins to approximate the ideal spatial filter, the sinc function spatial frequency