4

I am trying to perform inverse warping given a homography matrix, and to do that efficiently I need a numpy array that looks like this:

([[0, 0, 1], [0, 1, 1], [0, 2, 1], ... [1, 0, 1], [1, 1, 1], ... [n, p, 1]])

Where n is an image's width (im.shape[0]) and p is the image's height (im.shape[1]). Any idea on how to efficiently construct numpy arrays that look like that?

Edit:

There is some discussion on which is the fastest, if anyone has any info on that I think it'd be interesting to hear. I appreciate everyone's help!

James L.
  • 12,893
  • 4
  • 49
  • 60
  • 1
    You don't need to state "appreciation of help" - you [generally just upvote every answer that was helpful for you](https://stackoverflow.com/help/someone-answers). But stating that you're interested in benchmarks or the fastest solution is appropriate. But maybe you want to [edit] your "edit". :) – MSeifert Sep 28 '17 at 14:12

4 Answers4

5

Using indices_merged_arr_generic_using_cp by @unutbu -

def indices_one_grid(n,p):
    ar = np.ones((n,p),dtype=int)
    return indices_merged_arr_generic_using_cp(ar)

Sample run -

In [141]: indices_one_grid(n=3,p=4)
Out[141]: 
array([[0, 0, 1],
       [0, 1, 1],
       [0, 2, 1],
       [0, 3, 1],
       [1, 0, 1],
       [1, 1, 1],
       [1, 2, 1],
       [1, 3, 1],
       [2, 0, 1],
       [2, 1, 1],
       [2, 2, 1],
       [2, 3, 1]])

Benchmarking

Other approaches -

def MSeifert(n,p):
    x, y = np.mgrid[:n, :p]
    return np.stack([x.ravel(), y.ravel(), np.ones(x.size, dtype=int)], axis=1)

def DanielF(n,p):
    return np.vstack([np.indices((n,p)), np.ones((1, n,p))]).reshape(3,-1).T

def Aaron(n,p):
    arr = np.empty([n*p,3])
    arr[:,0] = np.repeat(np.arange(n),p)
    arr[:,1] = np.tile(np.arange(p),n)
    arr[:,2] = 1
    return arr

Timings -

In [152]: n=1000;p=1000

In [153]: %timeit MSeifert(n,p)
     ...: %timeit DanielF(n,p)
     ...: %timeit Aaron(n,p)
     ...: %timeit indices_one_grid(n,p)
     ...: 
100 loops, best of 3: 15.8 ms per loop
100 loops, best of 3: 8.46 ms per loop
100 loops, best of 3: 10.4 ms per loop
100 loops, best of 3: 4.78 ms per loop
Divakar
  • 218,885
  • 19
  • 262
  • 358
1

You could use np.mgrid to create the grid (first two entries of each subarray) with np.stack to concatenate them:

>>> x, y = np.mgrid[:3, :3]   # assuming a 3x3 image
>>> np.stack([x.ravel(), y.ravel(), np.ones(x.size, dtype=int)], axis=1)
array([[0, 0, 1],
       [0, 1, 1],
       [0, 2, 1],
       [1, 0, 1],
       [1, 1, 1],
       [1, 2, 1],
       [2, 0, 1],
       [2, 1, 1],
       [2, 2, 1]])

In this case I used 3 as width and height but by altering the arguments for np.mgrid you can change them.

MSeifert
  • 145,886
  • 38
  • 333
  • 352
1

In one line:

np.vstack([np.indices(im.shape), np.ones((1, *im.shape))]).reshape(3,-1).T

Basically, key to getting indices like this is using something like indices, mgrid/meshgrid or the like.

Daniel F
  • 13,620
  • 2
  • 29
  • 55
1

You can do this all without looping using numpy.tile and numpy.repeat and a pre-allocated container

import numpy as np
arr = np.empty([n*p,3])
arr[:,0] = np.repeat(np.arange(n),p)
arr[:,1] = np.tile(np.arange(p),n)
arr[:,2] = 1
Aaron
  • 10,133
  • 1
  • 24
  • 40
  • I always forget that 2D that's the easier and faster method. – Daniel F Sep 28 '17 at 13:57
  • @MSeifert what can sometimes be slow is the memory allocation incurred by np.stack... probably true with indices being faster than repeat and tile though. – Aaron Sep 28 '17 at 14:00
  • @Aaron It's the same memory allocation just different order. I create the small arrays first and then use stack to create the big one. While you create the big one first and then create small ones that are copied into the large array. – MSeifert Sep 28 '17 at 14:05