SignatureMedian - 1D Running Median 완전 해설

Overview · Architecture

SignatureMedian 전체 구조

1D 수치 시퀀스에 Running Median 스무딩을 적용합니다. 반경 R(→윈도우 W=2R+1)을 지정하면 각 데이터 포인트에 대해 주변 W개 값의 중앙값을 계산합니다.

진입점 구조 - ComputeMediansByRadius → ComputeMedians

Entry

ComputeMediansByRadius()

Conversion

R → W = 2R+1

Core

ComputeMedians()

Branch

useMiddle ?

Output

List(Of Double)

' ComputeMediansByRadius — R → W 변환 후 ComputeMedians 호출
Dim w64 As Long = CLng(kernelRadius) * 2L + 1L   ' 오버플로 방지
If w64 > Integer.MaxValue Then Throw ...
Dim w As Integer = CInt(w64)                    ' 항상 홀수 ≥ 1
Return ComputeMedians(input, useMiddle, kernelWidth:=w, ...)

🔑 핵심 분기 - useMiddle (All Median vs Middle Median)

ComputeMedians() 내부에서 useMiddle 플래그에 따라 처리 경로가 완전히 분기됩니다.

useMiddle = False → All Median

전체 데이터(0 ~ n-1)에 Median 적용
BoundaryMode가 적용됨
Adaptive: 윈도우를 [0, n-1] 내부로 슬라이드
Symmetric / Replicate / ZeroPad: GetValueWithBoundary()로 범위 밖 값 합성

useMiddle = True → Middle Median

borderCount 만큼 양쪽 경계를 제외
BoundaryMode 무시 (레거시 경로)
iMin/iMax 클램핑으로 가변 길이 윈도우
경계 데이터는 원본 값 그대로 유지

📊 모드 · 경계 처리 특성 비교

항목	All Median	Middle Median
처리 범위	startIdx=0, endIdx=n-1	startIdx=borderCount, endIdx=n-borderCount-1
경계 처리	BoundaryMode 4가지 선택	iMin/iMax 클램핑 (BoundaryMode 무시)
윈도우 크기	항상 W (Adaptive 제외)	가변 (경계에서 축소)
경계 데이터	합성 / 반사 / 복제 / 0	원본 값 그대로 보존
use case	전체 시퀀스 스무딩	내부 영역만 스무딩, 경계 원본 유지

🗂️ BoundaryMode 열거형

Symmetric (Mirror) Replicate (Edge Clamp) ZeroPad Adaptive (Window Slide)

Public Enum BoundaryMode
    Symmetric     ' 거울 반사: … 3,2,1 | 1,2,3,4,5 | 5,4,3 …
    Replicate     ' 가장자리 복제: … 1,1,1 | 1,2,3,4,5 | 5,5,5 …
    ZeroPad       ' 0 패딩: … 0,0,0 | 1,2,3,4,5 | 0,0,0 …
    Adaptive      ' 윈도우 슬라이드: W를 [0, n-1] 안에 유지
End Enum

Mode · All Median

All Median (useMiddle = False)

전체 데이터(인덱스 0 ~ n-1)에 Running Median을 적용합니다. 커널이 데이터 경계를 벗어나는 위치에서는 BoundaryMode에 따라 범위 밖 값을 합성합니다.

🔄 처리 흐름 - 단계별 분석

오프셋 계산

offsetLow = (W-1) \ 2 · offsetHigh = (W-1) - offsetLow · W가 홀수이면 offsetLow = offsetHigh = R

처리 범위 설정

startIdx = 0, endIdx = n-1 → 전체 데이터를 순회합니다.

BoundaryMode 분기

Adaptive: W를 [0, n-1] 안에 맞도록 시작점을 조정하여 항상 길이 W 윈도우 사용.
기타 모드: 각 pos에 대해 GetValueWithBoundary(arr, i+k, mode)로 범위 밖 값을 합성합니다.

Median 계산

GetWindowMedian(win, length) → Array.Sort 후 중앙값 반환. 짝수 길이는 두 중앙값의 평균.

📐 Adaptive 모드 - 윈도우 슬라이드 상세

Adaptive는 합성 값을 사용하지 않고, 전체 윈도우 W를 데이터 범위 [0, n-1] 안에서 유지합니다.

' Adaptive 분기 핵심 코드
Dim desiredW As Integer = kernelWidth
Dim W As Integer = Math.Min(desiredW, n)    ' n보다 크면 n으로 제한
Dim start As Integer = i - offsetLow
If start < 0 Then start = 0                ' 왼쪽 경계 클램핑
If start > n - W Then start = n - W        ' 오른쪽 경계 클램핑
If start < 0 Then start = 0                ' 방어적 클램핑

For pos As Integer = 0 To W - 1
    win(pos) = arr(start + pos)              ' 실제 데이터만 수집
Next
buffer(i) = GetWindowMedian(win, W)

내부 i=5

start=3

win=[3,4,5,6,7]

→

왼쪽 경계 i=1

start=0 (클램핑)

win=[0,1,2,3,4]

→

오른쪽 경계 i=n-2

start=n-W (클램핑)

win=[n-5..n-1]

🔗 기타 모드 - GetValueWithBoundary 합성 경로

' Symmetric / Replicate / ZeroPad 경로
For pos As Integer = 0 To kernelWidth - 1
    Dim k As Integer = pos - offsetLow         ' 중심 기준 오프셋
    win(pos) = GetValueWithBoundary(arr, i + k, boundaryMode)
Next
buffer(i) = GetWindowMedian(win, kernelWidth)

각 pos에서 i + k가 범위 밖이면 mode에 따라 반사(Symmetric), 클램핑(Replicate), 0.0(ZeroPad)을 반환합니다. Adaptive는 이 경로를 타지 않습니다.

Mode · Middle Median

Middle Median (useMiddle = True)

borderCount 만큼 양쪽 경계를 제외한 내부 영역만 Median을 적용합니다. BoundaryMode는 무시되며, 경계 데이터는 원본 값 그대로 유지됩니다.

🔄 처리 흐름 - 레거시 클램핑 경로

처리 범위 축소

b = Max(0, borderCount) · startIdx = b · endIdx = n - b - 1 · 2b ≥ n이면 처리 없이 원본 반환.

가변 길이 윈도우 수집

iMin = Max(0, i - offsetLow) · iMax = Min(n-1, i + offsetHigh) · length = iMax - iMin + 1 → 경계에서 윈도우가 자동으로 축소됩니다.

Median 계산

축소된 길이(length)의 윈도우로 GetWindowMedian() 호출. 짝수 길이도 처리됩니다.

📐 레거시 클램핑 코드 상세

' useMiddle = True 경로 — BoundaryMode 무시
Dim iMin = Math.Max(0, i - offsetLow)
Dim iMax = Math.Min(n - 1, i + offsetHigh)
Dim length = iMax - iMin + 1

For k As Integer = 0 To length - 1
    win(k) = arr(iMin + k)
Next

buffer(i) = GetWindowMedian(win, length)

iMin/iMax 클램핑: 데이터 양 끝에서 윈도우가 자연스럽게 좁아집니다. 예: i=1, R=3이면 iMin=0 (1-3=-2 → 0으로 클램핑), length=5 (W=7 대비 축소).

📊 borderCount의 역할

borderCount	처리 범위	경계 데이터
0	0 ~ n-1 (전체)	클램핑된 윈도우로 Median 적용
R (= kernelRadius)	R ~ n-R-1	원본 값 보존 (가장 일반적)
n/2 이상	처리 없음	전체 원본 반환

borderCount는 "원본 값을 보존할 양쪽 영역의 크기"를 지정합니다. 일반적으로 kernelRadius와 같은 값을 사용하여, 커널이 완전히 데이터 내부에 있는 영역만 스무딩합니다.

Shared Infrastructure · GetValueWithBoundary()

BoundaryMode - 경계 처리 4가지

커널이 데이터 경계를 벗어날 때 범위 밖 인덱스에 어떤 값을 할당할지 결정합니다. All Median 모드(useMiddle=False)에서만 적용됩니다.

🔍 왜 경계 처리가 필요한가?

W=5(R=2)인 커널을 i=1에 적용하면 인덱스 -1을 참조합니다. 이 범위 밖 인덱스에 대한 처리가 BoundaryMode입니다.

경계 처리 인터랙티브 시각화

커서 위치 i = 1 R = 2, 데이터 길이 = 9

원본 데이터

커널 윈도우 [i−2 … i+2] - 모드별 처리

GetValueWithBoundary() - 전체 코드

Private Shared Function GetValueWithBoundary(
    data As Double(), idx As Integer, mode As BoundaryMode) As Double

    Dim n As Integer = If(data Is Nothing, 0, data.Length)
    If n = 0 Then Return 0.0

    Select Case mode
        Case BoundaryMode.Symmetric
            If n = 1 Then Return data(0)
            Dim period As Long = 2L * (CLng(n) - 1L)  ' 64-bit 주기
            Dim m As Long = idx Mod period
            If m < 0 Then m += period
            Dim mapped = If(m < n, m, 2L*(n-1L)-m)
            Return data(CInt(mapped))

        Case BoundaryMode.Replicate
            If idx < 0 Then idx = 0
            ElseIf idx >= n Then idx = n - 1
            Return data(idx)

        Case BoundaryMode.ZeroPad
            If idx < 0 OrElse idx >= n Then Return 0.0
            Return data(idx)

        Case BoundaryMode.Adaptive
            ' Symmetric과 동일한 64-bit 주기 반사
            ...
    End Select
End Function

Symmetric 거울 반사

c b a

a b c d e

e d c

period = 2*(n-1). 64-bit Mod로 음수 · 양수 모두 안전 처리.

Replicate 가장자리 복제

a a a

a b c d e

e e e

idx < 0 → 0, idx ≥ n → n-1. 가장 단순.

ZeroPad 0 패딩

0 0 0

a b c d e

0 0 0

범위 밖 = 0.0. 경계 값이 0 방향으로 편향됨.

Adaptive 윈도우 슬라이드

' 합성 없이 W를 데이터 안에서 슬라이드
start = max(0, min(i-R, n-W))

경계 효과 없이 항상 실제 데이터만 사용. All Median 내에서 별도 분기.

📊 모드 선택 가이드

Mode	경계 왜곡	특성	권장 용도
Symmetric	거의 없음	연속적인 1차 도함수 보존	일반 용도 (기본값)
Replicate	약간 (평탄화)	가장 단순, 빠름	경계 평탄화 허용 시
ZeroPad	있음 (감쇠)	경계에서 0 방향 편향	주파수 / 신호 처리
Adaptive	없음	합성 없이 실제 데이터만	합성 거부 시

Algorithm · GetWindowMedian

Median 계산 알고리즘

윈도우 내 값을 정렬하여 중앙값을 구합니다. Array.Sort in-place 정렬 후, 홀수 길이는 가운데 원소, 짝수 길이는 두 중앙 원소의 평균을 반환합니다.

📐 GetWindowMedian() 전체 코드

Private Shared Function GetWindowMedian(
    win() As Double, length As Integer) As Double

    Array.Sort(win, 0, length)  ' 앞 length개만 in-place 정렬
    Dim mid = length \ 2

    If (length And 1) = 0 Then
        ' 짝수 길이 : 두 중앙값의 평균
        Return (win(mid - 1) + win(mid)) / 2.0
    Else
        ' 홀수 길이 : 정확한 가운데 원소
        Return win(mid)
    End If
End Function

📊 Median 계산 예시

윈도우	정렬 후	mid	결과	유형
[5, 2, 8, 1, 4]	[1, 2, 4, 5, 8]	2	4	홀수(5)
[3, 7, 1, 9]	[1, 3, 7, 9]	2	(3+7)/2 = 5	짝수(4)
[10]	[10]	0	10	홀수(1)
[4, 6]	[4, 6]	1	(4+6)/2 = 5	짝수(2)

⚡ R → W 변환 & 오버플로 보호

' ComputeMediansByRadius 내부
Dim w64 As Long = CLng(kernelRadius) * 2L + 1L
If w64 > Integer.MaxValue Then
    Throw New ArgumentOutOfRangeException(...)
End If
Dim w As Integer = CInt(w64)  ' 항상 홀수, ≥ 1

Long으로 곱셈하여 Integer 오버플로를 방지합니다. R = 1,073,741,823 (Integer.MaxValue / 2) 이상이면 예외.

🔬 offsetLow / offsetHigh 계산 원리

offsetLow = (W−1) \ 2 offsetHigh = (W−1) − offsetLow

R	W = 2R+1	offsetLow	offsetHigh	윈도우 범위
1	3	1	1	[i-1, i, i+1]
2	5	2	2	[i-2, i-1, i, i+1, i+2]
3	7	3	3	[i-3 .. i+3]
5	11	5	5	[i-5 .. i+5]

W가 항상 홀수(2R+1)이므로 offsetLow = offsetHigh = R. 정수 나눗셈 (W-1)\2로 계산합니다.

Interactive · Visualization

Median Lab

입력 데이터 · 모드 · 경계 처리 · 반경을 설정하고 실시간으로 결과를 확인합니다. 각 인덱스별 윈도우 수집 → 정렬 → Median 과정을 단계별로 로그합니다.

프리셋

모드

Boundary

Radius R = 2 → W = 5

borderCount =

입력 데이터 (쉼표 구분, 프리셋 또는 직접 편집)

입력 vs 출력 비교

INPUT

OUTPUT

📋 단계별 처리 로그

각 인덱스 i에 대한 윈도우 수집 → 정렬 → Median 선택 과정

(실행 버튼을 클릭하세요)

Performance · Optimization

병렬화 & 성능 최적화

SignatureMedian은 .NET의 Parallel.For, ThreadLocal, Interlocked 등을 활용해 멀티코어에서 효율적으로 동작합니다.

1. Parallel.For - 행 단위 병렬화

Parallel.For(startIdx, endIdx + 1, Sub(i)
    ' 각 데이터 포인트 독립 처리
    ' 입력 arr은 읽기 전용 → 경쟁 조건 없음
    ' buffer(i) 쓰기는 인덱스 i 고유 → 동기화 불필요
End Sub)

각 데이터 포인트 i는 독립적으로 계산됩니다. 입력 arr은 읽기 전용이고, 출력 buffer(i)는 인덱스별 고유 접근이므로 lock 없이 완전 병렬화됩니다.

2. ThreadLocal - 스레드별 독립 버퍼

Dim localWin As New ThreadLocal(Of Double())(
    Function() New Double(kernelWidth - 1) {}
)

' Parallel.For 내부에서:
Dim win = localWin.Value  ' 스레드별 고유 배열

Parallel.For 내에서 win 배열이 필요하지만, 매 반복마다 new 하면 GC 부담이 큽니다. ThreadLocal로 스레드당 1회만 할당하여 재사용합니다.

3. Interlocked - 원자적 진행률 보고

Dim cnt = Interlocked.Increment(processed)
If cnt Mod reportInterval = 0 Then
    progress?.Report(Math.Min(n, cnt))
End If

reportInterval = Max(1, n\200)으로 ~0.5% 간격으로만 Report()를 호출하여 UI 스레드 부담을 최소화합니다.

4. Array.Sort in-place - GC 최적화

' GetWindowMedian — 별도 배열 할당 없음
Array.Sort(win, 0, length)  ' win 배열의 앞 length개만 정렬
' win은 ThreadLocal 버퍼 → GC 없음, 할당 없음

이전 구현(주석 처리된 코드): win.Take(length).ToArray()로 매번 새 배열을 할당했습니다. 현재는 in-place 정렬으로 GC 부담을 제거했습니다.

📊 성능 특성 요약

항목	상세
시간 복잡도	O(n · W · log W) — 각 포인트에서 W개 정렬
공간 복잡도	O(n + W·threads) — buffer + 스레드별 win 배열
병렬화	Parallel.For — 코어 수에 비례하는 속도 향상
GC 부담	최소 — ThreadLocal 재사용, in-place 정렬
진행 보고	~0.5% 간격 IProgress<Integer> 콜백

1D Running MedianAll / Middle · Boundary · Demo

SignatureMedian 전체 구조

진입점 구조 - ComputeMediansByRadius → ComputeMedians

🔑 핵심 분기 - useMiddle (All Median vs Middle Median)

useMiddle = False → All Median

useMiddle = True → Middle Median

📊 모드 · 경계 처리 특성 비교

🗂️ BoundaryMode 열거형

All Median (useMiddle = False)

🔄 처리 흐름 - 단계별 분석

📐 Adaptive 모드 - 윈도우 슬라이드 상세

🔗 기타 모드 - GetValueWithBoundary 합성 경로

Middle Median (useMiddle = True)

🔄 처리 흐름 - 레거시 클램핑 경로

📐 레거시 클램핑 코드 상세

📊 borderCount의 역할

BoundaryMode - 경계 처리 4가지

🔍 왜 경계 처리가 필요한가?

GetValueWithBoundary() - 전체 코드

Symmetric 거울 반사

Replicate 가장자리 복제

ZeroPad 0 패딩

Adaptive 윈도우 슬라이드

📊 모드 선택 가이드

Median 계산 알고리즘

📐 GetWindowMedian() 전체 코드

📊 Median 계산 예시

⚡ R → W 변환 & 오버플로 보호

🔬 offsetLow / offsetHigh 계산 원리

Median Lab

입력 vs 출력 비교

📋 단계별 처리 로그

병렬화 & 성능 최적화

1. Parallel.For - 행 단위 병렬화

2. ThreadLocal - 스레드별 독립 버퍼

3. Interlocked - 원자적 진행률 보고

4. Array.Sort in-place - GC 최적화

📊 성능 특성 요약

1D Running Median
All / Middle · Boundary · Demo