[Project-Outline] Smooth Algorithm 개선

🧐 문제 상황

Smooth 알고리즘 문제점 발견

아래와 같이 Smooth 적용 후 크지 않은 경로는 아래와 같이 조금 뭉개지는 현상과 처음과 끝이 연결되지 않는 상황이 발생했다!

💡 해결 과정

기존 로직 뜯어보기

기존의 코드를 살펴보았다. 내가 봐야할 부분은 마지막이 연결이 안되는 부분과 라인이 뭉개지는 이유였다.

    private func smoothLocations(_ locations: [CLLocationCoordinate2D]) -> [CLLocationCoordinate2D] {
        guard locations.count > 1 else { return locations }
        
        var smoothed: [CLLocationCoordinate2D] = []
        for i in 0..<locations.count {
            let start = max(0, i - 2)
            let end = min(locations.count - 1, i + 2)
            let subset = Array(locations[start...end])
            
            let avgLatitude = subset.map { $0.latitude }.reduce(0, +) / Double(subset.count)
            let avgLongitude = subset.map { $0.longitude }.reduce(0, +) / Double(subset.count)
            
            smoothed.append(CLLocationCoordinate2D(latitude: avgLatitude, longitude: avgLongitude))
        }
        
        return smoothed
    }

기존의 로직은 다음과 같다. 의사결정코드로 만들어 봤다.

    private func smoothLocations(_ locations: [CLLocationCoordinate2D]) -> [CLLocationCoordinate2D] {
        배열의 요소가 1개 이하일 경우 입력 받은 값 그대로 리턴한다
        
        해당 인덱스에 최대 앞 2개, 뒷 2개까지의 배열을 가져온다.
        최대 5개의 배열의 평균을 구하여 배열을 만든다.
        
        결과 배열을 리턴한다
    }

결국 이전값과 함께 평균값을 내는 것이기 때문에 마지막 요소는 영원히 들어갈 수 없다는 문제를 발견했다. ☠️ 경로가 뭉개진 이유는 평균값을 내다보니 앞뒤차이가 크게되면 총 5개의 배열이 평균이 나버리기 때문에 촘촘하지 않는다면 평균값으로 뭉개지게 되었다. 물론 러닝의 경우에는 촘촘하게 포인트가 찍히기 때문에 이런 예외상황은 보기 힘들겠지만 ❗️어쨋든 예외상황이 있다는 것❗️이 안좋게 느껴졌다.

마지막이 연결되지 않았고, 촘촘하지 않으면 뭉개진 모습

새로운 Smoothing Algorithm 서칭 및 적용

역시 문제들을 찾아보니 그래프를 표현할때나 이러한 경로를 표시하는데 정말 많은 알고리즘들이 있었다.

1. 이동 평균 (Moving Average)

기존에 적용했던 알고리즘은 이 알고리즘인 듯 싶었다. 하지만 기존은 앞뒤 2개의 값을 종합해서 이동평균을 했다면 아래의 이동평균은 뒤의 값 만으로 이동평균을 구하는 알고리즘을 구현해 봤다.

    func movingAverage(coordinates: [CLLocationCoordinate2D], size: Int) -> [CLLocationCoordinate2D] {
        guard size > 1 else { return coordinates }
        
        var smoothedCoordinates: [CLLocationCoordinate2D] = []
        
        for i in 0..<(coordinates.count - size + 1) {
            let window = coordinates[i..<i+size]
            let avgLatitude = window.map { $0.latitude }.reduce(0, +) / Double(size)
            let avgLongitude = window.map { $0.longitude }.reduce(0, +) / Double(size)
            smoothedCoordinates.append(CLLocationCoordinate2D(latitude: avgLatitude, longitude: avgLongitude))
        }
        
        return smoothedCoordinates
    }

필터를 적용하지 않아도 스무싱이 된다는 장점이 있었지만 기존과 똑같고 넓은 범위의 이동평균을 구하면 똑같은 문제가 발생한다!

2. 가우시안 스무딩 (Gausisian Smoothing)

정규분포를 사용하는 방법. 커널의 크기와 표준 편차를 사용하여 smooth의 정도를 결정할 수 있다. 중심에 가까운 값일수록 더 높은 가중치를 부여하고, 멀어질수록 가중치가 낮아진다. 이러한 방식으로 중심 값에 주변 값들의 영향을 부드럽게 반영하게 된다.

    func gaussianSmoothing(coordinates: [CLLocationCoordinate2D], size: Int, sigma: Double) -> [CLLocationCoordinate2D] {
        let kernel = gaussianKernel(size: size, sigma: sigma)
        var smoothedCoordinates: [CLLocationCoordinate2D] = []
        
        for i in 0..<(coordinates.count - size + 1) {
            let window = coordinates[i..<i+size]
            let sumLatitude = zip(window, kernel).map { $0.latitude * $1 }.reduce(0, +)
            let sumLongitude = zip(window, kernel).map { $0.longitude * $1 }.reduce(0, +)
            smoothedCoordinates.append(CLLocationCoordinate2D(latitude: sumLatitude, longitude: sumLongitude))
        }
        
        return smoothedCoordinates
    }
    
    func gaussianKernel(size: Int, sigma: Double) -> [Double] {
        var kernel = [Double]()
        let mean = size / 2
        
        for i in 0..<size {
            let value = exp(-0.5 * pow((Double(i) - Double(mean)) / sigma, 2))
            kernel.append(value)
        }
        
        let sum = kernel.reduce(0, +)
        return kernel.map { $0 / sum }
    }

3. 칼만 필터 (Kalman Filter)

간단하게 이야기하면 상태를 예측하고, 실제 측정된 데이터와 비교하여 오차를 수정하는 방식으로 진행되는 알고리즘이다. 😇 여기부터 뭔가 너무 딥다이브가 되지 않을까 걱정하며 조금은 가볍게 접근했다.

    struct KalmanFilter {
        var initialValue: Double // 필터의 초기값으로, 첫 번째 좌표의 위도와 경도
        var processNoise: Double // 시스템 모델의 불확실성(노이즈)을 나타냄
        var measurementNoise: Double // 측정값의 노이즈 수준을 나타내며, 큰 값은 예측값을 더 신뢰
        var estimationError: Double // 초기 추정값의 불확실성을 나타내며, 큰 값은 초기값에 대한 신뢰도를 낮춤
        var kalmanGain: Double = 0

        mutating func update(measurement: Double) -> Double {
            estimationError += processNoise
            
            kalmanGain = estimationError / (estimationError + measurementNoise)
            initialValue += kalmanGain * (measurement - initialValue)
            estimationError = (1 - kalmanGain) * estimationError
            
            return initialValue
        }
    }

    func kalmanSmoothing(coordinates: [CLLocationCoordinate2D]) -> [CLLocationCoordinate2D] {
        guard let firstCoordinate = coordinates.first else { return [] }
        
        var kalmanLatitude = KalmanFilter(initialValue: firstCoordinate.latitude, processNoise: 0.5, measurementNoise: 2.0, estimationError: 1.0)
        var kalmanLongitude = KalmanFilter(initialValue: firstCoordinate.longitude, processNoise: 0.5, measurementNoise: 2.0, estimationError: 1.0)
        
        return coordinates.map { coordinate in
            let lat = kalmanLatitude.update(measurement: coordinate.latitude)
            let lon = kalmanLongitude.update(measurement: coordinate.longitude)
            return CLLocationCoordinate2D(latitude: lat, longitude: lon)
        }
    }

4. 캣멀 롬 스플라인 (Catmull-Rom Spline)

주어진 제어점을 부드럽게 연결하여 자연스러운 곡선을 생성하는 데 사용된다고 한다. 수학적으로 각 점을 통과하는 다항식 곡선을 생성하며, 다른 스플라인 기법들과 달리 제어점을 정확히 통과한다는 특징이 있다. path.addQuadCurve 메서드와 유사하다.

    // alpha 곡선의 긴장도, 0으로 갈수록 느슨해지고 1로 갈수록 각 제어점을 좀 더 예리하게 통과
    // numPoints 세분화 정도
    func catmullRomSpline(coordinates: [CLLocationCoordinate2D], alpha: Double = 0.5, numPoints: Int = 100) -> [CLLocationCoordinate2D] {
        guard coordinates.count >= 4 else {
            return coordinates // 최소한 4개의 포인트가 필요
        }
        
        var splineCoordinates: [CLLocationCoordinate2D] = []
        
        for i in 1..<(coordinates.count - 2) {
            let p0 = coordinates[i - 1]
            let p1 = coordinates[i]
            let p2 = coordinates[i + 1]
            let p3 = coordinates[i + 2]
            
            for t in stride(from: 0, through: 1, by: 1.0 / Double(numPoints)) {
                let t2 = t * t
                let t3 = t2 * t
                
                let f1 = -alpha * t3 + 2.0 * alpha * t2 - alpha * t
                let f2 = (2.0 - alpha) * t3 + (alpha - 3.0) * t2 + 1.0
                let f3 = (alpha - 2.0) * t3 + (3.0 - 2.0 * alpha) * t2 + alpha * t
                let f4 = alpha * t3 - alpha * t2
                
                let latitude = p0.latitude * f1 + p1.latitude * f2 + p2.latitude * f3 + p3.latitude * f4
                let longitude = p0.longitude * f1 + p1.longitude * f2 + p2.longitude * f3 + p3.longitude * f4
                
                splineCoordinates.append(CLLocationCoordinate2D(latitude: latitude, longitude: longitude))
            }
        }
        
        return splineCoordinates
    }

알고리즘 선정

위 4개의 알고리즘중에 선정하는것이 좋아 보였다. 이동평균, 가우시안, 칼만 필터, 캣멀 롬... 이 네가지를 정리해봤다.

• 이동평균의 경우 기존 알고리즘이기도 하고, 마지막 값이 많이 손실된다는 부분에서 쓰게된다면 가우시안 스무싱을 하는 것이 좋다고 판단했다.
• 칼만 필더의 경우 불확실성, 노이즈 수준 등 여러가지 값들을 추가로 계산해주고 설정해주어야 하는데 더 복잡성을 늘리는 것이 좋지는 않겠다고 판단했다.
• 캣멀 롬의 경우 무조건 지점을 지나간다는 장점이 있지만 문제는 gps를 실시간으로 측정하다보니 어느정도 튀는 값이 생기는데 이부분을 커버하지 못한다는 문제가 있었다. 만약 정확한 값들이 있고, 이것을 부드럽게 연결하기에는 최고의 선택 같았다.

⭐️ 캣멀 롬과 가우시안 스무딩... 둘중 고민하다가 결국 가우시안 스무딩 알고리즘을 채택했다.

 

🤣🫠 이상하게 문제 해결??

LineCap, LineJoin...

갑자기 혹시? 해서 setLineCap(.round), setLineJoin(.round) 두개를 path에 적용하는 것이 아닌 context에 적용해 봤다.

    private func drawPolyline(on snapshot: MKMapSnapshotter.Snapshot, in context: CGContext?) {
		// 경로 넣는 로직
        
        // 추가 된 부분
        context?.setLineCap(.round)
        context?.setLineJoin(.round)
        
        context?.addPath(path.cgPath)
        context?.setLineWidth(lineWidth)
        context?.strokePath()
    }

아....

사실 이거로도 충분하겠구나... 싶었다. 하지만... smooth 알고리즘은 러닝 도중이나 여러군데에서 많이 쓰일 것으로 예상되어 헛된 일은 아니었다... 그리고 이경우 경로가 튀는 근본적인 문제를 해결할순 없었다. 

가우시안 스무싱 알고리즘 적용

아래와 같이 러닝 특성상 첫번째 값이 필요하기 때문에 적용해주었다.

    func gaussianSmoothing(coordinates: [CLLocationCoordinate2D], size: Int, sigma: Double) -> [CLLocationCoordinate2D] {
        // size가 0이거나 coordinates 배열의 크기보다 클 경우 원본 배열 반환
        guard size > 0, coordinates.count >= size else { return coordinates }
        let kernel = gaussianKernel(size: size, sigma: sigma)
        // 러닝 특성상 첫번째 값은 무조건 필요하기 때문에 첫번째 값 추가
        var smoothedCoordinates: [CLLocationCoordinate2D] = [coordinates[0]]
        
        for i in 0..<(coordinates.count - size + 1) {
            let window = coordinates[i..<i+size]
            let sumLatitude = zip(window, kernel).map { $0.latitude * $1 }.reduce(0, +)
            let sumLongitude = zip(window, kernel).map { $0.longitude * $1 }.reduce(0, +)
            smoothedCoordinates.append(CLLocationCoordinate2D(latitude: sumLatitude, longitude: sumLongitude))
        }
        
        return smoothedCoordinates
    }
    
    func gaussianKernel(size: Int, sigma: Double) -> [Double] {
        let mean = Double(size) / 2
        let kernel = (0..<size).map { i in
            exp(-0.5 * pow((Double(i) - mean) / sigma, 2))
        }
        let sum = kernel.reduce(0, +)
        return kernel.map { $0 / sum }
    }

확실히 경로가 부드러워지고, 깔끔해진 느낌이 난다.