somewhat randomly create 3d points given 2 images
the goal create set of n 3d coordinates (seeds) 2 images. n 100 - 1000 points.
i have 2 pure black , white images heights same , widths variable. size of images can big 1000x1000 pixels. read them numpy arrays , flattened rgb codes 1's (black) , zeros (white).
here example processing 2 small images:
in [6]: img1 out[6]: array([[1, 1, 1, 1, 1, 1, 1, 1, 1, 1], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1], [1, 1, 0, 0, 0, 0, 0, 0, 1, 1], [1, 1, 0, 0, 0, 0, 0, 0, 1, 1], [1, 1, 0, 0, 0, 0, 0, 0, 1, 1], [1, 1, 0, 0, 0, 0, 0, 0, 1, 1], [1, 1, 0, 0, 0, 0, 0, 0, 1, 1], [1, 1, 0, 0, 0, 0, 0, 0, 1, 1], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1]], dtype=uint8) in [8]: img2 out[8]: array([[0, 0, 0, 0, 0, 0, 1, 0, 0, 0], [0, 0, 0, 0, 1, 1, 1, 0, 0, 0], [0, 0, 0, 1, 1, 0, 0, 1, 0, 0], [0, 0, 1, 1, 0, 0, 0, 1, 0, 0], [1, 1, 0, 0, 0, 0, 0, 0, 1, 1], [1, 1, 0, 0, 0, 0, 0, 0, 1, 1], [0, 0, 1, 0, 0, 0, 1, 1, 0, 0], [0, 0, 1, 0, 0, 1, 1, 0, 0, 0], [0, 0, 0, 1, 1, 1, 0, 0, 0, 0], [0, 0, 0, 1, 0, 0, 0, 0, 0, 0]], dtype=uint8) next, create index array map locations of black pixels each image so:
in [10]: np.transpose(np.nonzero(img1)) out[10]: array([[0, 0], [0, 1], [0, 2], [0, 3], [0, 4], [0, 5], [0, 6], ... i want extend each 2d black pixel each image 3d space. 3d points intersect, want randomly grab n number of 3d ponts (seeds). furthermore, enhancement, better if disperse these 3d points evenly in 3d space avoid 'clustering' of points there areas of greater black pixel density. haven't been able wrap head around process yet.
here's visualization of set up:
what i've tried below seems work on small images slows halt images bigger. bottleneck seems occur assign common_points.
img1_array = process_image("images/nhx.jpg", nheight) img2_array = process_image("images/ku.jpg", nheight) img1_black = get_black_pixels(img1_array) img2_black = get_black_pixels(img2_array) # create img1 3d points: img1_3d = [] z1 = len(img2_array[1]) # number of img2 columns pixel in img1_black: in range(z1): img1_3d.append((pixel[0], pixel[1], i)) # (img1_row, img1_col, img2_col) # create img2 3d points: img2_3d = [] z2 = len(img1_array[1]) # number of img1 columns pixel in img2_black: in range(z2): img2_3d.append((pixel[0], pixel[1], i)) # (img2_row, img2_col, img1_col) # common 3d points common_points = [x x in img1_3d if x in img2_3d] # num_seeds number of random common_points seed_indices = np.random.choice(len(common_points), num_seeds, replace=false) seeds = [] index_num in seed_indices: seeds.append(common_points[index_num]) questions:
- how can avoid bottleneck? haven't been able come numpy solution.
- is there better solution, in general, how coding this?
- any thoughts on how evenly disperse seeds?
update edit:
based on luke's algorithm, i've come following working code. correct implementation? improved upon?
img1_array = process_image("images/john.jpg", 500) img2_array = process_image("images/ryan.jpg", 500) img1_black = get_black_pixels(img1_array) # img2_black = get_black_pixels(img2_array) density = 0.00001 seeds = [] img1_pixel in img1_black: row = img1_pixel[0] img2_row = np.array(np.nonzero(img2_array[row])) # array of column numbers there black pixel if np.any(img2_row): img2_col in img2_row[0]: if np.random.uniform(0, 1) < density: seeds.append([row, img1_pixel[1], img2_col])
the bottleneck because you're comparing every 3d point in "apple" shaded area every 3d point in "orange" shaded area, huge number of comparisons. speed factor of imgheight looking @ points in same row. speed storing img2_3d set instead of list, because calling "in" on set faster (it's o(1) operation instead of o(n) operation).
however, it's better avoid making lists of 3d points. here's 1 solution:
- choose arbitrary density parameter, call density. try density = 0.10 fill in 10% of intersection points.
- for each black pixel in apple, loop through black pixels in same row of orange. if (random.uniform(0,1) < density), create 3d point @ (applex, orangex, row) or whatever correct arrangement coordinate system.
that algorithm sample evenly, 3d areas more black have more samples. if understand last question, want sample more densely in areas less black (though i'm not sure why). could:
- do gaussian blur of inverse of 2 images (opencv has functions this), , multiply each times 0.9 , add 0.1. have image has higher value image more white.
- do algorithm above, each pixel pair in step 2, set density = blurredorangepixel * blurredapplepixel. thus, selection density higher in white regions.
i try basic algorithm first though; think better.
