[python] 2D 어레이에서 피크 검출

해결책

데이터 파일 : paw.txt . 소스 코드:

from scipy import *
from operator import itemgetter

n = 5  # how many fingers are we looking for

d = loadtxt("paw.txt")
width, height = d.shape

# Create an array where every element is a sum of 2x2 squares.

fourSums = d[:-1,:-1] + d[1:,:-1] + d[1:,1:] + d[:-1,1:]

# Find positions of the fingers.

# Pair each sum with its position number (from 0 to width*height-1),

pairs = zip(arange(width*height), fourSums.flatten())

# Sort by descending sum value, filter overlapping squares

def drop_overlapping(pairs):
    no_overlaps = []
    def does_not_overlap(p1, p2):
        i1, i2 = p1[0], p2[0]
        r1, col1 = i1 / (width-1), i1 % (width-1)
        r2, col2 = i2 / (width-1), i2 % (width-1)
        return (max(abs(r1-r2),abs(col1-col2)) >= 2)
    for p in pairs:
        if all(map(lambda prev: does_not_overlap(p,prev), no_overlaps)):
            no_overlaps.append(p)
    return no_overlaps

pairs2 = drop_overlapping(sorted(pairs, key=itemgetter(1), reverse=True))

# Take the first n with the heighest values

positions = pairs2[:n]

# Print results

print d, "\n"

for i, val in positions:
    row = i / (width-1)
    column = i % (width-1)
    print "sum = %f @ %d,%d (%d)" % (val, row, column, i)
    print d[row:row+2,column:column+2], "\n"

사각형이 겹치지 않고 출력 됩니다. 귀하의 예에서와 동일한 영역이 선택된 것 같습니다.

일부 의견

까다로운 부분은 모든 2×2 제곱의 합을 계산하는 것입니다. 나는 당신이 그들 모두를 필요로한다고 가정 했으므로 약간 겹칠 수 있습니다. 슬라이스를 사용하여 원래 2D 배열에서 첫 번째 / 마지막 열과 행을 잘라낸 다음 모두 함께 겹쳐서 합계를 계산했습니다.

더 잘 이해하려면 3×3 배열을 이미징하십시오.

>>> a = arange(9).reshape(3,3) ; a
array([[0, 1, 2],
       [3, 4, 5],
       [6, 7, 8]])

그런 다음 조각을 취할 수 있습니다.

>>> a[:-1,:-1]
array([[0, 1],
       [3, 4]])
>>> a[1:,:-1]
array([[3, 4],
       [6, 7]])
>>> a[:-1,1:]
array([[1, 2],
       [4, 5]])
>>> a[1:,1:]
array([[4, 5],
       [7, 8]])

이제 그것들을 다른 것 위에 쌓고 같은 위치에 요소를 합산한다고 상상해보십시오. 이 합계는 왼쪽 위 모서리가 같은 위치에있는 2×2 정사각형에 대해 정확히 같은 합계입니다.

>>> sums = a[:-1,:-1] + a[1:,:-1] + a[:-1,1:] + a[1:,1:]; sums
array([[ 8, 12],
       [20, 24]])

합계가 2×2 제곱을 초과 max하면 최대 값 sort또는 sorted을 찾거나 피크를 찾는 데 사용할 수 있습니다 .

피크의 위치를 ​​기억하기 위해 모든 값 (합)을 평평한 배열의 서수 위치와 결합합니다 (참조 zip). 그런 다음 결과를 인쇄 할 때 행 / 열 위치를 다시 계산합니다.

노트

2×2 사각형이 겹치도록 허용했습니다. 편집 된 버전은 겹치지 않는 사각형 만 결과에 나타나도록 일부를 필터링합니다.

손가락 선택 (아이디어)

또 다른 문제는 모든 피크에서 손가락이 될 가능성을 선택하는 방법입니다. 작동하거나 작동하지 않을 수있는 아이디어가 있습니다. 지금 당장 구현할 시간이 없으므로 의사 코드 만 있습니다.

앞 손가락이 거의 완벽한 원 안에 있으면 뒷 손가락이 그 원 안에 있어야한다는 것을 알았습니다. 또한 앞쪽 손가락의 간격이 거의 동일합니다. 이러한 휴리스틱 속성을 사용하여 손가락을 감지하려고 할 수 있습니다.

의사 코드 :

select the top N finger candidates (not too many, 10 or 12)
consider all possible combinations of 5 out of N (use itertools.combinations)
for each combination of 5 fingers:
    for each finger out of 5:
        fit the best circle to the remaining 4
        => position of the center, radius
        check if the selected finger is inside of the circle
        check if the remaining four are evenly spread
        (for example, consider angles from the center of the circle)
        assign some cost (penalty) to this selection of 4 peaks + a rear finger
        (consider, probably weighted:
             circle fitting error,
             if the rear finger is inside,
             variance in the spreading of the front fingers,
             total intensity of 5 peaks)
choose a combination of 4 peaks + a rear peak with the lowest penalty

이것은 무차별 접근 방식입니다. N이 상대적으로 작 으면 가능하다고 생각합니다. N = 12의 경우, C_12 ^ 5 = 792 조합, 배 손가락을 선택하는 5 가지 방법이 있으므로 모든 발에 대해 3960 개의 사례를 평가합니다.

답변