가장 가까운 벡터를 찾으십시오

Question

최근에 RGB 이미지를 양자화하는 알고리즘을 작성했습니다. 모든 픽셀은 (R, G, B) 벡터로 표현되고, 양자화 코드북은 3 차원 벡터로 구성됩니다. 이미지의 모든 픽셀은 유클리드 거리 (더 정확하게는 유클리드 제곱)와 관련하여 가장 가까운 코드북 픽셀에 매핑 (예 : "대체")되어야합니다. 다음과 같이 나는 그것을했다 :

class EuclideanMetric(DistanceMetric): 
    def __call__(self, x, y): 
     d = x - y 
     return sqrt(sum(d * d, -1)) 

class Quantizer(object): 
    def __init__(self, codebook, distanceMetric = EuclideanMetric()): 
     self._codebook = codebook 
     self._distMetric = distanceMetric 

    def quantize(self, imageArray): 
     quantizedRaster = zeros(imageArray.shape) 

     X = quantizedRaster.shape[0] 
     Y = quantizedRaster.shape[1] 
     for i in xrange(0, X): 
      print i 
      for j in xrange(0, Y): 
       dist = self._distMetric(imageArray[i,j], self._codebook) 
       code = argmin(dist) 
       quantizedRaster[i,j] = self._codebook[code] 

     return quantizedRaster 

... 그것은 지독 2600 * 2700 픽셀, 내 펜티엄 코어 듀오 2.2 GHz의 거의 8백초, 4 메모리의 연주회 및 이미지를 작동 :(

?

다소이 어쩌면 다른 알고리즘 또는 일부 파이썬 고유의 최적화를 최적화 할 수있는 방법이 있나요

UPD :. 나는 이 유클리드 제곱 사용하고 여전히 엄청난 시간을 얻기 위해 노력

,536.

Answer 1

하나의 간단한 최적화는 sqrt 호출을 삭제하는 것입니다. x는 sqrt (x)와 단조 적이므로 실제 거리, 최소 거리가 필요하지 않으므로 대신 x^2를 사용하십시오. sqrt가 비싸기 때문에 조금 도와 주어야합니다.

이 트릭은 거리에서 작업 할 때 많이 사용됩니다. 예를 들어 거리 임계 값이있는 경우 임계 값^2를 사용하고 거리 계산에 sqrt를 놓을 수 있습니다. 실제로 sqrt는 절대 거리가 필요할 때만 필요합니다. 상대 거리의 경우 sqrt를 떨어 뜨립니다.

업데이트 : 알고리즘 변경이 필요할 것입니다. 지금 당신은 모든 코드북 벡터를 모든 픽셀과 비교하고 있습니다. 거리 계산의 횟수를 줄이기 위해 속도를 높일 것입니다.

이 경우 kd-tree을 사용하는 것이 더 좋을 수 있습니다. 그러면 O (코드북)에서 O (로그 (코드북))까지 각 픽셀의 검색이 줄어 듭니다. 파이썬에서는이 작업을 한 적이 없지만 일부 인터넷 검색은 here을 사용할 수있는 구현을 제공했습니다.

Answer 2

scipy.cluster.vq에서 벡터 양자화 함수 vq을 사용할 수 있습니다.

Answer 3

X이 매우 큰 경우 i이 상당히 많이 인쇄되므로 성능이 저하 될 수 있습니다. 덜 구체적인 답변을 보려면 계속 읽으십시오. 프로세스의 병목 현상, 나는 타이밍 장식, 내가 옛적에 한 번이 곳을 발견하고 항상 위치를 파악하는 데 사용했다

from functools import wraps 
import time 

def time_this(func): 
    @wraps(func) 
    def wrapper(*args, **kwargs): 
     start = time.time() 
     result = func(*args, **kwargs) 
     finish = time.time() 
     elapsed = (finish - start) * 1000 
     print '{0}: {1} ms'.format(func.__name__, elapsed) 
     return result 
    return wrapper 

의 라인을 따라 뭔가를 제안된다

를 찾으려면 내 코드가 느리다. 알고리즘을 일련의 개별 함수로 분해 한 다음이 데코레이터로 함수를 장식하여 각 함수 호출의 소요 시간을 확인할 수 있습니다. 그렇다면 어떤 문장이 어떤 기능을 가지고 있는지 알아 내서 장식 된 기능이 실행되는 데 걸리는 시간을 향상시키는 것이 중요합니다. 주로 당신은 다음과 같은 두 가지를 찾고 있습니다. 1) 실행에 오래 걸리는 문장 2) 실행에 오래 걸리는 것은 아니지만 여러 번 실행되어 성능이 약간 향상되어 전반적인 성능에 큰 영향을줍니다.

행운을 빈다.