Clash Royale CLAN TAG#URR8PPP

Efficient majority voting for 1-in-N classification with sliding window classifier over 2D Array

Short version: I would like to use the values in a 2D array to index the third dimension of a corresponding subset of a larger array - and then increment those elements.

I would appreciate help making the two incorporate_votes algorithms quicker. Actually sliding the classifier over the array and calculating optimal strides is not the point here.

Long version:
I have an algorithm, which classifies each element in R1xC1 2D array as 1 of N classes.

I would like to classify a larger 2D array of size R2xC2. Rather than tessellating the larger array into multiple R1xC1 2D arrays I would like to slide the classifier over the larger array, such that each element in the larger array is classified multiple times. This means that I will have a R2xC2xN array to store the results in, and as the window slides across the large array each pixel in the window will increment one of elements in third dimension (i.e. one of the N classes).

After all the sliding is finished we can simply get the argmax in the dimension corresponding to the classification to get the per element classification.

I intend to scale this up to classify an array of several million pixels with a few dozens so I am concerned with the efficiency of using the classification results to increment one value in the classification dimension per element.

Below is the toy version of the problem I have been crafting all evening in Python3. It has a naive double for loop implementation and a slightly better one obtained by index swizzling and some smart indexing. The classifier is just random.

import numpy as np

map_rows = 8
map_cols = 10
num_candidates = 3
vote_rows = 6
vote_cols = 5


def display_tally(the_tally):
print(":25s:25s:25s".format("Class 0", "Class 1", "Class 2"))
for i in range(map_rows):
for k in range(num_candidates):
for j in range(map_cols):
print(":<2".format(the_tally[i, j, k]), end='')
print(" ", end='')
print("")


def incorporate_votes(current_tally, this_vote, left, top):
for i in range(vote_rows):
for j in range(vote_cols):
current_tally[top + i, left + j, this_vote[i, j]] += 1
return current_tally


def incorporate_votes2(current_tally, this_vote, left, top):
for i in range(num_candidates):
current_tally[i, top:top + vote_rows, left:left + vote_cols][this_vote == i] += 1
return current_tally


tally = np.zeros((map_rows, map_cols, num_candidates), dtype=int)
swizzled_tally = np.zeros((num_candidates, map_rows, map_cols), dtype=int)
print("Before voting")
display_tally(tally)

print("n Votes from classifier A (centered at (2,2))")
votes = np.random.randint(num_candidates, size=vote_rows*vote_cols).reshape((vote_rows, vote_cols))
print(votes)

tally = incorporate_votes(tally, votes, 0, 0)
swizzled_tally = incorporate_votes2(swizzled_tally, votes, 0, 0)

print("nAfter classifier A voting (centered at (2,2))")
display_tally(tally)

print("n Votes from classifier B (Centered at (5, 4))")
votes2 = np.random.randint(num_candidates, size=vote_rows*vote_cols).reshape((vote_rows, vote_cols))
print(votes2)

tally = incorporate_votes(tally, votes2, 3, 2)
swizzled_tally = incorporate_votes2(swizzled_tally, votes2, 3, 2)

print("nAfter classifier B voting (Centered at (5, 4))")
print("Naive vote counting")
display_tally(tally)
print("nSwizzled vote counting")
display_tally(np.moveaxis(swizzled_tally, [-2, -1], [0, 1]))

new_tally = np.moveaxis(tally, -1, 0)
classifications = np.argmax(swizzled_tally, axis=0)
print("nNaive classifications")
print(classifications)

print("nSwizzled classifications")
classifications = np.argmax(tally, axis=2)
print(classifications)


And some sample output:

Before voting
Class 0 Class 1 Class 2
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

Votes from classifier A (centered at (2,2))
[[1 1 2 2 1]
[0 2 0 2 1]
[0 2 2 0 2]
[1 1 1 2 0]
[1 0 0 2 1]
[2 1 1 1 0]]

After classifier A voting (centered at (2,2))
Class 0 Class 1 Class 2
0 0 0 0 0 0 0 0 0 0 1 1 0 0 1 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0
1 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0
1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 1 0 0 0 0 0
0 0 0 0 1 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0
0 1 1 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0
0 0 0 0 1 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

Votes from classifier B (Centered at (5, 4))
[[2 2 2 0 0]
[0 1 2 1 2]
[2 0 0 2 0]
[2 2 1 1 1]
[1 2 0 2 1]
[1 1 1 1 2]]

After classifier B voting (Centered at (5, 4))
Naive vote counting
Class 0 Class 1 Class 2
0 0 0 0 0 0 0 0 0 0 1 1 0 0 1 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0
1 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0
1 0 0 1 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 2 1 0 0 0 0
0 0 0 1 1 0 0 0 0 0 1 1 1 0 1 0 1 0 0 0 0 0 0 1 0 1 0 1 0 0
0 1 1 0 1 1 0 1 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 2 0 0 1 0 0 0
0 0 0 0 1 0 0 0 0 0 0 1 1 1 0 1 1 1 0 0 1 0 0 1 1 0 0 0 0 0
0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 1 0 1 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 1 0 0

Swizzled vote counting
Class 0 Class 1 Class 2
0 0 0 0 0 0 0 0 0 0 1 1 0 0 1 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0
1 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0
1 0 0 1 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 2 1 0 0 0 0
0 0 0 1 1 0 0 0 0 0 1 1 1 0 1 0 1 0 0 0 0 0 0 1 0 1 0 1 0 0
0 1 1 0 1 1 0 1 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 2 0 0 1 0 0 0
0 0 0 0 1 0 0 0 0 0 0 1 1 1 0 1 1 1 0 0 1 0 0 1 1 0 0 0 0 0
0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 1 0 1 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 1 0 0

Naive classifications
[[1 1 2 2 1 0 0 0 0 0]
[0 2 0 2 1 0 0 0 0 0]
[0 2 2 0 2 2 0 0 0 0]
[1 1 1 0 0 2 1 2 0 0]
[1 0 0 2 0 0 2 0 0 0]
[2 1 1 1 0 1 1 1 0 0]
[0 0 0 1 2 0 2 1 0 0]
[0 0 0 1 1 1 1 2 0 0]]

Swizzled classifications
[[1 1 2 2 1 0 0 0 0 0]
[0 2 0 2 1 0 0 0 0 0]
[0 2 2 0 2 2 0 0 0 0]
[1 1 1 0 0 2 1 2 0 0]
[1 0 0 2 0 0 2 0 0 0]
[2 1 1 1 0 1 1 1 0 0]
[0 0 0 1 2 0 2 1 0 0]
[0 0 0 1 1 1 1 2 0 0]]


By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.