標本化定理と信号の補間

draft 画像処理

画像の標本化では、標本化定理の条件を満たしていれば、標本値からもとの連続信号を完全に復元できることを見ました。
ここでは、その復元がどのように行われるのかを見ていきます。

補間による信号の復元
画像処理

標本化で得られるのは、とびとびの標本値、すなわち離散的な点の並びだけです。
これらの点を滑らかに繋ぎ直して、もとの連続的な信号を取り戻す操作を補間といいます。

標本化定理の条件を満たしていれば、標本点の値を滑らかに繋ぐ波は1つに定まります。言い換えると、正しく標本化された標本値からは、もとの正弦波（連続信号）が一意に復元されるのです。

この理想的な補間には、sinc関数と呼ばれる波形を各標本値に重ね合わせる方法が用いられます。

! ACTION：要編集

次の点に着目して、デモを観察してみよう

sinc関数を1本ずつ表示した状態で、1本の波が自分の標本点では標本値の高さに届き、他のすべての標本点ではちょうど0を通ること
重ね合わせる標本点の数を増やしていくと、重ね合わせた波が中央から順にもとの波へ重なっていくこと

Three.jsによる実装概要

// 標本点の数（中央の1点を決められるよう奇数にする）と、標本値のもとにする波の山と谷の数
const SAMPLE_COUNT = 13
const CENTER_INDEX = (SAMPLE_COUNT - 1) / 2
const WAVE_CYCLES = 2.5

// 重ね合わせる標本点の数。中央の 1 本から始める
const TERM_COUNT = 1

// 位置の 0〜1 を PLOT_WIDTH、明るさのふれの -1〜1 を ±WAVE_HEIGHT に対応させる
const PLOT_WIDTH = 5.2
const WAVE_HEIGHT = 1
const CURVE_SEGMENTS = 720
const SINC_SEGMENTS = 360

// xy 平面に重なる要素を、奥から手前へ少しずつ振り分ける z。
// 正面から見る構図に固定しているため、この厚みは絵には出ない
const LAYER_SINC = 0
const LAYER_AXIS = 0.01
const LAYER_SOURCE = 0.02
const LAYER_SUM = 0.03
const LAYER_STEM = 0.04
const LAYER_DOT = 0.05

// sinc 関数。sin(πt) / πt の t = 0 での値は 1 とする
const sinc = (t: number) => (t === 0 ? 1 : Math.sin(Math.PI * t) / (Math.PI * t))

// k 番目の標本点の位置と、標本点の間隔。sinc 関数の山の幅は、この間隔に合わせる
const samplePosition = (k: number) => (k + 0.5) / SAMPLE_COUNT
const SAMPLE_INTERVAL = 1 / SAMPLE_COUNT

// k 番目の標本値。両端で 0 になる重みを掛けた波から読み取る。描画域の外に標本点が残らないので、
// 描画域の中の標本値だけで、もとの波を過不足なく組み立てられる
const sampleValueAt = (k: number) => {
  const t = k / (SAMPLE_COUNT - 1)
  const fade = 0.5 * (1 - Math.cos(2 * Math.PI * t))
  return Math.sin(2 * Math.PI * WAVE_CYCLES * t) * fade
}
const SAMPLE_VALUES = Array.from({ length: SAMPLE_COUNT }, (_, k) => sampleValueAt(k))

// k 番目の標本値に重ねる sinc 関数の、位置 u での値
const sincTermAt = (u: number, k: number) =>
  SAMPLE_VALUES[k] * sinc((u - samplePosition(k)) / SAMPLE_INTERVAL)

// 重ね合わせる順序。中央の標本点から左右へ交互に広げていく。
// 端から順に足すと、まだ足していない側の食い違いが描画域の中央にまで残る
const ADD_ORDER = Array.from({ length: SAMPLE_COUNT }, (_, k) => k).sort(
  (a, b) => Math.abs(a - CENTER_INDEX) - Math.abs(b - CENTER_INDEX) || a - b
)
const added = ADD_ORDER.slice(0, TERM_COUNT)

// グラフ全体を canvas の中央に寄せる
const graph = new Group()
graph.position.set(-PLOT_WIDTH / 2, -0.18, 0)
scene.add(graph)

// 明るさの中間を通る横軸（位置）と、明るさを測る縦軸。縦軸には明・暗の目盛りを付ける
const axisGeometry = new BufferGeometry().setFromPoints([
  new Vector3(-0.2, 0, LAYER_AXIS),
  new Vector3(PLOT_WIDTH + 0.2, 0, LAYER_AXIS),
  new Vector3(0, -WAVE_HEIGHT - 0.2, LAYER_AXIS),
  new Vector3(0, WAVE_HEIGHT + 0.2, LAYER_AXIS),
  new Vector3(-0.08, WAVE_HEIGHT, LAYER_AXIS),
  new Vector3(0, WAVE_HEIGHT, LAYER_AXIS),
  new Vector3(-0.08, -WAVE_HEIGHT, LAYER_AXIS),
  new Vector3(0, -WAVE_HEIGHT, LAYER_AXIS)
])
graph.add(new LineSegments(axisGeometry, new LineBasicMaterial({ color: "#9aa3b0" })))

// もとの波。すべての標本値の sinc 関数を足し合わせたもので、標本点の位置を必ず通る
const sourcePoints: Vector3[] = []
for (let step = 0; step <= CURVE_SEGMENTS; step++) {
  const u = step / CURVE_SEGMENTS
  let level = 0
  for (let k = 0; k < SAMPLE_COUNT; k++) {
    level += sincTermAt(u, k)
  }
  sourcePoints.push(new Vector3(u * PLOT_WIDTH, level * WAVE_HEIGHT, LAYER_SOURCE))
}
const sourceGeometry = new BufferGeometry().setFromPoints(sourcePoints)
graph.add(new Line(sourceGeometry, new LineBasicMaterial({ color: "#5ec8f2" })))

// ここまでに重ね合わせた波。対象の標本値の sinc 関数だけを足し合わせる。
// もとの波と重なったときに下が透けるよう、破線で描く
const sumPoints: Vector3[] = []
for (let step = 0; step <= CURVE_SEGMENTS; step++) {
  const u = step / CURVE_SEGMENTS
  let level = 0
  for (const k of added) {
    level += sincTermAt(u, k)
  }
  sumPoints.push(new Vector3(u * PLOT_WIDTH, level * WAVE_HEIGHT, LAYER_SUM))
}
const sumGeometry = new BufferGeometry().setFromPoints(sumPoints)
const sum = new Line(
  sumGeometry,
  new LineDashedMaterial({ color: "#f2766a", dashSize: 0.08, gapSize: 0.06 })
)
// 破線の刻みは頂点間の距離から決まるので、頂点を置いたら測る
sum.computeLineDistances()
graph.add(sum)

// 標本点から横軸へ下ろした垂線。どの位置で明るさを読み取ったかを示す
const stemPoints: Vector3[] = []
for (let k = 0; k < SAMPLE_COUNT; k++) {
  const x = samplePosition(k) * PLOT_WIDTH
  const y = SAMPLE_VALUES[k] * WAVE_HEIGHT
  stemPoints.push(new Vector3(x, 0, LAYER_STEM), new Vector3(x, y, LAYER_STEM))
}
const stemGeometry = new BufferGeometry().setFromPoints(stemPoints)
const stemMaterial = new LineBasicMaterial({ color: "#ffc857", transparent: true, opacity: 0.55 })
graph.add(new LineSegments(stemGeometry, stemMaterial))

// 標本点。重ね合わせが済んだ点だけを濃く塗り、まだの点は沈ませる
const dots = new InstancedMesh(
  new SphereGeometry(0.045, 12, 8),
  new MeshBasicMaterial(),
  SAMPLE_COUNT
)
const matrix = new Matrix4()
const addedColor = new Color("#ffc857")
const pendingColor = new Color("#6b7280")
for (let k = 0; k < SAMPLE_COUNT; k++) {
  const x = samplePosition(k) * PLOT_WIDTH
  const y = SAMPLE_VALUES[k] * WAVE_HEIGHT
  dots.setMatrixAt(k, matrix.setPosition(x, y, LAYER_DOT))
  dots.setColorAt(k, added.includes(k) ? addedColor : pendingColor)
}
dots.instanceMatrix.needsUpdate = true
graph.add(dots)

// 足し合わせる前の sinc 関数。標本値の大きさだけ縦に伸縮し、標本点の位置に山がくる
for (const k of added) {
  const sincPoints: Vector3[] = []
  for (let step = 0; step <= SINC_SEGMENTS; step++) {
    const u = step / SINC_SEGMENTS
    sincPoints.push(new Vector3(u * PLOT_WIDTH, sincTermAt(u, k) * WAVE_HEIGHT, LAYER_SINC))
  }
  const sincGeometry = new BufferGeometry().setFromPoints(sincPoints)
  graph.add(new Line(sincGeometry, new LineBasicMaterial({ color: "#ffc857" })))
}

sinc関数による補間は、標本化定理が保証するもとの信号の完全な復元を数学的に実現するものですが、実際の画像処理では計算量の都合から、より単純な補間で近似することがほとんどです。

エイリアスとしての復元
画像処理

標本化定理の条件を満たしていない場合は、標本値を滑らかに繋ぐ波が一意に定まりません。
もとの細かい波ではなく、それより緩やかな別の波であるエイリアスとして復元されてしまいます。この波がエイリアシングの正体です。

このように、もとの画像の細かい模様を正しく復元できるかどうかは、標本化の段階で十分な細かさを確保できていたかどうかにかかっています。

Action

縞の空間周波数と標本化周波数を動かして、1つの山や谷に2点以上の標本点が配置されるようになると、復元された波がもとの波にぴったり重なることを確認しよう

Three.jsによる実装概要

// もとの波の空間周波数（描画域の幅あたりに入る縞の本数）と、標本化周波数（標本点の数）
const FREQUENCY = 7
const SAMPLE_COUNT = 9

// 位置の 0〜1 を PLOT_WIDTH、明るさのふれの -1〜1 を ±WAVE_HEIGHT に対応させる
const PLOT_WIDTH = 5.2
const WAVE_HEIGHT = 1
const CURVE_SEGMENTS = 720

// xy 平面に重なる要素を、奥から手前へ少しずつ振り分ける z。
// 正面から見る構図に固定しているため、この厚みは絵には出ない
const LAYER_AXIS = 0.01
const LAYER_SOURCE = 0.02
const LAYER_RECONSTRUCTION = 0.03
const LAYER_STEM = 0.04
const LAYER_DOT = 0.05

// もとの連続的な波。位置 u（0〜1）での明るさのふれ（-1〜1）を返す
const waveAt = (u: number) => Math.sin(2 * Math.PI * FREQUENCY * u)

// k 番目の標本点の位置。画素 1 つ分の真ん中で明るさを読み取るのと同じ取り方
const samplePosition = (k: number) => (k + 0.5) / SAMPLE_COUNT

// sinc 関数。sin(πt) / πt の t = 0 での値は 1 とする
const sinc = (t: number) => (t === 0 ? 1 : Math.sin(Math.PI * t) / (Math.PI * t))

// グラフ全体を canvas の中央に寄せる
const graph = new Group()
graph.position.set(-PLOT_WIDTH / 2, -0.18, 0)
scene.add(graph)

// 明るさの中間を通る横軸（位置）と、明るさを測る縦軸。縦軸には明・暗の目盛りを付ける
const axisGeometry = new BufferGeometry().setFromPoints([
  new Vector3(-0.2, 0, LAYER_AXIS),
  new Vector3(PLOT_WIDTH + 0.2, 0, LAYER_AXIS),
  new Vector3(0, -WAVE_HEIGHT - 0.2, LAYER_AXIS),
  new Vector3(0, WAVE_HEIGHT + 0.2, LAYER_AXIS),
  new Vector3(-0.08, WAVE_HEIGHT, LAYER_AXIS),
  new Vector3(0, WAVE_HEIGHT, LAYER_AXIS),
  new Vector3(-0.08, -WAVE_HEIGHT, LAYER_AXIS),
  new Vector3(0, -WAVE_HEIGHT, LAYER_AXIS)
])
graph.add(new LineSegments(axisGeometry, new LineBasicMaterial({ color: "#9aa3b0" })))

// もとの連続的な波
const sourcePoints: Vector3[] = []
for (let step = 0; step <= CURVE_SEGMENTS; step++) {
  const u = step / CURVE_SEGMENTS
  sourcePoints.push(new Vector3(u * PLOT_WIDTH, waveAt(u) * WAVE_HEIGHT, LAYER_SOURCE))
}
const sourceGeometry = new BufferGeometry().setFromPoints(sourcePoints)
graph.add(new Line(sourceGeometry, new LineBasicMaterial({ color: "#5ec8f2" })))

// 標本化。標本点の位置で、もとの波の明るさを読み取る。
// sinc 関数は左右に無限に伸びるので、足し合わせを打ち切った影響が両端に波打って現れないよう、
// 描画域の外の標本点も 64 点ぶん読んでおく
const SINC_TAIL = 64
const interval = 1 / SAMPLE_COUNT
const sampledValues: number[] = []
for (let k = -SINC_TAIL; k < SAMPLE_COUNT + SINC_TAIL; k++) {
  sampledValues.push(waveAt(samplePosition(k)))
}

// 復元。各標本値に sinc 関数を重ね合わせる
const reconstructionPoints: Vector3[] = []
for (let step = 0; step <= CURVE_SEGMENTS; step++) {
  const u = step / CURVE_SEGMENTS
  let level = 0
  for (let k = -SINC_TAIL; k < SAMPLE_COUNT + SINC_TAIL; k++) {
    level += sampledValues[k + SINC_TAIL] * sinc((u - samplePosition(k)) / interval)
  }
  reconstructionPoints.push(new Vector3(u * PLOT_WIDTH, level * WAVE_HEIGHT, LAYER_RECONSTRUCTION))
}

// 復元された波。もとの波と重なったときに下が透けるよう、破線で描く
const reconstructionGeometry = new BufferGeometry().setFromPoints(reconstructionPoints)
const reconstruction = new Line(
  reconstructionGeometry,
  new LineDashedMaterial({ color: "#f2766a", dashSize: 0.08, gapSize: 0.06 })
)
// 破線の刻みは頂点間の距離から決まるので、頂点を置いたら測る
reconstruction.computeLineDistances()
graph.add(reconstruction)

// 標本点。読み取った明るさの位置に球を置く
const dots = new InstancedMesh(
  new SphereGeometry(0.045, 12, 8),
  new MeshBasicMaterial({ color: "#ffc857" }),
  SAMPLE_COUNT
)
const matrix = new Matrix4()

// 標本点から横軸へ下ろした垂線。どの位置で明るさを読み取ったかを示す
const stemPoints: Vector3[] = []
for (let k = 0; k < SAMPLE_COUNT; k++) {
  const x = samplePosition(k) * PLOT_WIDTH
  const y = sampledValues[k + SINC_TAIL] * WAVE_HEIGHT
  stemPoints.push(new Vector3(x, 0, LAYER_STEM), new Vector3(x, y, LAYER_STEM))
  dots.setMatrixAt(k, matrix.setPosition(x, y, LAYER_DOT))
}
dots.instanceMatrix.needsUpdate = true
graph.add(dots)

const stemGeometry = new BufferGeometry().setFromPoints(stemPoints)
const stemMaterial = new LineBasicMaterial({ color: "#ffc857", transparent: true, opacity: 0.55 })
graph.add(new LineSegments(stemGeometry, stemMaterial))

標本化定理と信号の補間

補間による信号の復元 画像処理

エイリアスとしての復元 画像処理

補間による信号の復元
画像処理

エイリアスとしての復元
画像処理