CODEWITHSUNDEEP
algorithmgraph-algorithmpanoramaslongest-path
Silex
Silex

Reputation: 1847

Most inefficient algorithm to visit each elements of a 2d array once

I'm creating panorama images, and for this I use a camera that I move programmatically step by step. The images are captured rows by rows.

So basically the captures can be seen as some kind a 2d array:

[ 0, 1, 2, 3 ] # row 1
[ 4, 5, 6, 7 ] # row 2

Where the camera moves sequentially through the numbers.

I noticed that if a car moves in front of the camera and follows the same pace as the camera, the car appears on every picture and the panorama looks weird.

So, I had the following idea: move the camera in a non-sequential order that way the car is very likely to be only captured once. I then thought about how to capture the images in a way that the camera travels the most between each position.

I found a way for single-row panoramas. Basically it start at the beginning, jumps half way right, goes back half-way left minus 1, and repeats.

Here are examples:

# 1x5 --> [0, 2, 4, 1, 3]          # sequential indices: 0 3 1 4 2
# 1x6 --> [0, 2, 4, 1, 3, 5]       # sequential indices: 0 3 1 4 2 5
# 1x7 --> [0, 2, 4, 6, 1, 3, 5]    # sequential indices: 0 4 1 5 2 6 3
# 1x8 --> [0, 2, 4, 6, 1, 3, 5, 7] # sequential indices: 0 4 1 5 2 6 3 7

To be clear, this means that for 1x6 (0, 2, 4, 1, 3, 5) the camera moves as follow:

x----- # pos 1
---x-- # pos 2
-x---- # pos 3
----x- # pos 4
--x--- # pos 5
-----x # pos 6

So basically it jumps all the time by at least n/2, which looks optimal as no capture ends up being the neighbor of another one and the distance between captures looks maximized and fluctuates very little.

The simplified code I use is something like:

def index_for(n, cols)
  col = n % cols
  if n.even?
    col/2
  else
    (col / 2.0).ceil + (cols / 2.0).ceil - 1
  end
end

# Sequential indices [0, 4, 1, 5, 2, 6, 3]
seq = (0..6).map{ |i| index_for(i, 7) }

# Visualization [0, 2, 4, 6, 1, 3, 5]
(0..6).map{ |i| seq.index(i) }

I tried making it work with several rows, and almost got there but then gave up. Here are examples of the idea I had:

 # 3x4
 [0,  2, 9, 11]
 [4,  6, 1,  3]
 [8, 10, 5,  7]

 # 2x5
 [0, 2, 5, 7, 9]
 [4, 6, 8, 1, 3]

If you look at the numbers, we see that the left side is usually simply the even numbers, and the right side are odd numbers but shifted in a modulus way. This shifting of the odd numbers is tricky to algorithmize, because the logic change slightly depending on the rows/cols being even/odd.

At the moment I ignore the rows and simply reapply the same algorithm for each rows. That means the 2x5 is done like this:

 [0, 2, 4, 1, 3]
 [5, 7, 9, 6, 8]

So, here are my questions:

EDIT: additional informations: the car usually moves slowly (at the speed of the sequential captures), so jumping around is a good way to avoid repetitions. It's also better to see the car in 2-3 tiles than in 7 of them if the car moves exactly at the speed of the camera (this happened). The panoramas are usually around 180°, but 360° should be supported. There's a pause of around 3 seconds between each image capture. The panoramas are mostly about capturing the construction of giant construction sites (buildings), but sometimes a car or a person walks in front of the building. We don't care about the moving parts, the goal is to capture the building and minimize the person/car photobombing the panorama.

Upvotes: 1

Views: 147

Answers (2)

Silex
Silex

Reputation: 1847

Ok I have found as simpler formula for each rows:

formula

The code becomes trivial:

def index_for(n, cols)
  (n + cols * (n % 2)) / 2
end

(0..7).map{ |i| index_for(i, 8) }
=> [0, 4, 1, 5, 2, 6, 3, 7]

So, for now I'll just use this for each row. I'll wait a while in the case someone comes up with a better answer to my questions.

Upvotes: 0

Jim Mischel
Jim Mischel

Reputation: 134085

I'm not convinced that maximizing the camera's distance traveled would make the car appear only once. It's probably more likely that the car would be seen in multiple, non-successive frames. That, too, would look pretty strange. But it's worth testing.

An easy way to test things is to represent your 2D array as a 1D array, do your scrambling, and then map it back to two dimensions. For example, this 2D array:

[ 1, 2, 3, 4, 5]
[ 6, 7, 8, 9,10]
[11,12,13,14,15]

becomes [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15]

Now you can use your 1D algorithm to adjust the order, and then map it back to two dimensions.

I suspect that, rather than going exactly halfway, you'll want to choose a prime number that is not a divisor of the width or height.

Another possibility would be to just randomize the cells using a Fisher-Yates shuffle. That's easy to do, and in practice could very well do just as good a job of eliminating the car as would a deterministic scrambling algorithm.

Upvotes: 0

Related Questions