속도 최대 루프와 R

Question

와 조건은 입력이 정수를 포함한 배열의 3x3x3하고 이웃을 기반으로, 그들은 제로 경우, 각각에 대한 교체

R.

이 코드를 속도를 번호.

출력은 새로운 값을 갖는 배열 "mask_roi"입니다.

###### Start here 

list_neig = array(0, dim = c(3,3,3)) 

mask_roi = array(sample(c(0,1,2),27,replace=T), dim = c(3,3,3)) 

values_mask = array(1:27, dim = c(3,3,3)) 

values_mask_melted = melt(values_mask, varnames=c("x","y","z")) 

### Tranform the 3D Matrix in a data.table wit 4 columns position and value 
image_melted <- melt(mask_roi, varnames=c("x","y","z")) # 4 columns: x, y, z, value 

image_melted$box = rownames(image_melted) 

image_melted_non_zeros<-image_melted[!(image_melted$value==0),] 

box_neigbors = vector("list", nrow(image_melted)) 

for (i in 1:(nrow(image_melted_non_zeros))){ 
    cat(i,"\n") 
    x = image_melted_non_zeros[i,1] 
    y = image_melted_non_zeros[i,2] 
    z = image_melted_non_zeros[i,3] 

    box_neigbors[[image_melted_non_zeros[i,5]]] <- list(nearestNeighbors(values_mask, elem = c(x,y,z), dist = 1,dim = c(3,3,3))) 

} 

내가

이 수행 한 "box_neighbors"벡터, 단지 그것을 활용하는 방법을 보여주기 위해 여기에 포함이, 우리는 빨리 여기 끝에서 확인해야합니다. 아이디어는 제로의 다른 모든 복셀을 확인하고 모든 이웃을 확인합니다. 그의 이웃이 0이면 동일한 가치를 지니고 그렇지 않으면 0을 유지합니다.

for (i in 1:(nrow(image_melted_non_zeros))){ 
    cat(i,"\n") 
    x = image_melted_non_zeros[i,1] 
    y = image_melted_non_zeros[i,2] 
    z = image_melted_non_zeros[i,3] 

    number_of_nei = length(box_neigbors[[image_melted_non_zeros[i,5]]][[1]]) 
    value_vozel = mask_roi[x,y,z] # it will give this new value 

    for (j in 1:number_of_nei){ 
    nei_number = box_neigbors[[image_melted_non_zeros[i,5]]][[1]][j] 

    xx = image_melted[nei_number,1] 
    yy = image_melted[nei_number,2] 
    zz = image_melted[nei_number,3]  

    value_nei = mask_roi[xx,yy,zz] 

    if(value_nei == 0){  
     mask_roi[xx,yy,zz] = value_vozel 
    } 
    } 
} 

3x3x3이 아닌 256x256x256 배열에이 작업을 수행해야합니다.

고맙습니다.

nearestNeighbors <- function(ary, elem, dist, dims){ 
    usedims <- mapply(function(el, d) { 
    seq(max(1, el - dist), min(d, el + dist)) 
    }, elem, dims, SIMPLIFY=FALSE) 
    df <- as.matrix(do.call('expand.grid', usedims)) 
    ndist <- sqrt(apply(df, 1, function(x) sum((x - elem)^2))) 
    ret <- df[which(ndist > 0 & ndist <= dist),,drop = FALSE] 

    return(ary[ret]) 

} 

Answer 1

나는 K-d 트리를 사용하는 구현을 구성했다. 16GB RAM 및 2.3GHz i.7 프로세서가 장착 된 MacBookPro에서 실행되는 ~ 13 초 내에 256x256x256 어레이를 처리 할 수 ​​있습니다. 특정 벤치마킹을하지 않았지만 13 세는 답변을 게시하기에 충분하다고 생각합니다. 아래에 내 단계를 설명했습니다. 제가 질문의 일부를 잘못 이해했는지 알려주십시오.

설정 :

우리는 포인트 가득 측면 길이 n의 상자가 있습니다. 상자의 점은 좌표 i, j, k로 결정되며 범위 1에서 n까지 지정할 수 있습니다. 총 상자에는 n^3 고유 점이 들어 있습니다. 각 점에 연관된 정수 0, 1 또는 2

문제 값을 갖는다 : 0 값을 갖는 각각의 점 P를 들면 상자와

갖는 N = 256 를 그 K 가까운 NON를 찾을 -ZERO-VALUED 이웃을 업데이트하고 그 이웃의 값으로 P를 업데이트하십시오. 업데이트 후 상자의 모든 지점이 0이 아니어야합니다.

해결책 :

상자 우리는 16,777 (256^3) 따라서 무력 방법 외출 포인트 갖는다. 운 좋게도 정확히 K-d 나무가 https://en.wikipedia.org/wiki/K-d_tree에 유용합니다. 메트릭 데이터 구조에 중점을 둔 몇 개의 R 라이브러리가 있습니다. 더 견고한 API를 가지고 있기 때문에이 예제에서는 FNN을 사용하고 있습니다 https://cran.r-project.org/web/packages/FNN/index.html보다 더 나은 API가 있다고 생각합니다.

규범 :

박스은 열 이름 (I, J, K, 가치)와 매트릭스로 표현된다. 각 행은 상자의 단일 지점을 나타냅니다.

set.seed(256) 
library(FNN) 
len = 256 
values = c(0, 1, 2) 
createBox = function(n, vals) { 
    index = 1:len^3 
    value = sample(vals, length(index), replace = T) 
    box = as.matrix(cbind(index, index, index, value)) 
    dimnames(box) = list(NULL, c("i", "j", "k", "value")) 
    box 
} 
box= createBox(len, values) 

knnx.index 함수는 상자 행렬과 쿼리 행렬 (상자 행렬의 서브 세트) 을 인수로 받아들이고 쿼리의 각 점에 가장 가까운 이웃 색인을 반환합니다.

updateZeroValuedPoints = function(box, kval) { 
    zeroPointIndx = which(box[ , "value"] == 0) 
    nonZeroPoints = box[-1 * zeroPointIndx, ] 
    zeroPoints = box[zeroPointIndx, ] 
    nnIdx = knnx.index(nonZeroPoints, zeroPoints, k = kval, algorithm = "kd_tree") 
    zeroPoints[, "value"] = nonZeroPoints[nnIdx[ , ncol(nnIdx)], "value"] 
    zeroPoints 
} 

당신이되면 이웃이이 값을 업데이트하는 간단한 스왑입니다 인덱스는, 아니 루프 필요합니다.

system.time(updateZeroValuedPoints(box, 1)) 
# > system.time(updateZeroValuedPoints(box, 1)) 
# user system elapsed 
# 13.517 1.162 14.676 

실적이 예상되는 곳에서 유용하고 어딘가에 있기를 바랍니다.