algorithmgraph-algorithmpanoramaslongest-path

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.

Solution

  • 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.