Thuật toán để phân phối điểm phân bố 2D

Question

Trong mảng pixel 2D, tôi cần một thuật toán hiệu quả sẽ chọn p% pixel được trải rộng nhất.

Điều này có thể được thực hiện một cách thích nghi bằng cách chọn điểm, sau đó liên tục điều chỉnh các vị trí của các điểm quá gần nhau. Nhưng điều này không hiệu quả vì nó đòi hỏi nhiều lần lặp lại và tính toán khoảng cách.

Nó không phải là hoàn hảo, nó chỉ cần tránh các cụm điểm càng nhiều càng tốt có thể được thực hiện hiệu quả.

Answer 1

Làm thế nào về điều này:

1. Khám phá tổng các khoảng cách từ mỗi điểm đến mỗi điểm khác. Vì vậy, điểm A có một khoảng cách tổng của khoảng cách (A, B) + dist (A, C) + dist (A, D) + dist (A, D) + ...
2. Sắp xếp các khoảng cách tổng hợp này.
3. Xóa các điểm có tổng khoảng cách nhỏ nhất cho đến khi bạn đạt đến phần trăm mong muốn.

này có thể đủ chính xác, nhưng nếu không, bạn luôn có thể thay thế bước 3 với:

"Hủy bỏ các điểm có tổng nhỏ nhất, và nếu bạn cần phải loại bỏ nhiều điểm hơn để đạt được mong muốn của bạn phần trăm, sau đó quay lại bước 1. "

Đợi. Bây giờ tôi đang tự hỏi. Bạn đang cố gắng tìm những điểm được trải ra nhiều nhất từ ​​một tập hợp các điểm nhất định ... hay cố gắng, từ một mảng nhất định, để tìm ra những điểm sẽ lan rộng nhất? Điều đó hoàn toàn khác ... và vẫn thực sự khó khăn.

Answer 2

Cách tính giá trị "mật độ" cho mỗi pixel để bắt đầu, dựa trên mức độ gần với tất cả các pixel khác. Sau đó, nhiều lần xóa pixel "dày đặc nhất" cho đến khi bạn ở dưới p% còn lại trong danh sách.

Bạn cần thực hiện phép tính khoảng cách để xác định mật độ giữa hai điểm nhất định nhiều nhất hai lần. Lần đầu tiên là khi bạn xây dựng danh sách ban đầu - mỗi pixel sẽ cần phải được so sánh với mỗi pixel khác. Thứ hai sẽ là khi bạn xóa một pixel khỏi danh sách - bạn phải tính toán điểm ảnh đã xóa đối với mỗi pixel còn lại trong danh sách. Điều này là để tính toán các giá trị mật độ thay đổi khi mỗi pixel bị xóa - ví dụ, 2 pixel trực tiếp cạnh nhau sẽ có giá trị rất cao, nhưng khi một pixel bị xóa, giá trị còn lại có thể có giá trị rất thấp.

Một số giả nhanh (lưu ý rằng trong ví dụ này, các khu vực mật độ cao hơn có một số lượng thấp)

For I = 0 to MaxPixel 
    For J = I to MaxPixel 
     PixelDensity[I], PixelDensity[J] += DistanceBetween(Pixels[I], Pixels[J]) 

While PixelDensity.Count > TargetCount 
    RemovePixel = IndexOfSmallest(PixelDensity) 
    ForEach I in PixelDensity 
     PixelDensity[I] -= DistanceBetween(Pixels[I], Pixels[RemovePixel]) 
    PixelDensity.Remove(RemovePixel) 

Nếu bộ nhớ là ít quan tâm hơn thời gian tính toán, bạn cũng có thể lưu trữ khoảng cách giữa bất kỳ hai điểm trong một mảng 2d đơn giản. Ngoài ra, thay vì khoảng cách đơn giản, có thể hữu ích khi tính toán khoảng cách tính toán - điều đó sẽ tránh được thứ gì đó giống như có hai điểm gần như trên đầu trang của nhau, nhưng cách xa mọi thứ khác và cả hai đều vượt qua.

Answer 3

Phương pháp tiếp cận tràn ngập lũ quét lặp lại sẽ đơn giản để hình dung.

1. Đối với mỗi ô, tìm hai điểm gần nhất và ghi lại sản phẩm của hai khoảng cách đó.
2. Những ô có sản phẩm cao nhất là những ô được gắn vào điểm xa nhất.

Answer 4

Bạn muốn bản phân phối đĩa Poisson, nhưng rất khó. Tìm kiếm sẽ trả về rất nhiều tài liệu học thuật về cách thực hiện hiệu quả: http://people.csail.mit.edu/thouis/JonesPoissonPreprint.pdf

Answer 5

Ooh! Còn cái này thì sao!

(Trong một cách rất tay Xù, vì tôi không biết liệu ma trận của bạn là hình vuông hoặc bất cứ điều gì ... Tôi sẽ cho rằng đó là.)

Giả sử bạn có một mảng 1000x1000 mà bạn muốn để đặt 47 điểm vào (tôi chọn 47 để nó là một số bất thường mà sẽ không phù hợp "độc đáo").

Bạn lấy ceil (sqrt (47)) ... sẽ cho bạn giá trị (7). Vì vậy, chúng tôi tạo một hình vuông 7x7, điền vào nó với 47 pixel (một số là trống), và tưởng tượng đặt nó ở góc của mảng.

Bây giờ, dịch từng pixel đó sang vị trí mới, dựa vào vị trí của chúng trong mảng nhỏ (7x7) đến mảng lớn (1000x1000). Một phương trình đơn giản nên làm điều này cho bạn ... cho tọa độ X, ví dụ:

xBigArrayIndex = xSmallArrayIndex * 1000/7; 

Sau đó, điểm ảnh của bạn sẽ siêu trải ra! Và nó đẹp và nhanh.

Nhược điểm duy nhất là điều này chỉ hoạt động hoàn hảo khi hình vuông của bạn là lý tưởng để bắt đầu ... nếu bạn điền nó ngây thơ (bắt đầu từ trên cùng bên trái, đi qua, vv), bạn sẽ kết thúc với một hơi phân tán lý tưởng một chút ... vì các pixel đã dịch sẽ không hoàn toàn đạt đến phần dưới cùng bên phải của mảng lớn. Nhưng có lẽ điều này là đủ tốt? Và nếu không, có lẽ đó là một tập con nhỏ hơn của vấn đề dễ giải quyết hơn?

Answer 6

Bạn có thể sử dụng thuật toán thân lồi và loại trừ điểm mà thuật toán này sẽ tính toán và lặp lại nó miễn là nó có được để p% tiêu chí của bạn, hoặc

thực hiện các bước thuật toán thân lồi, kiểm tra các điểm có trong thân và bên trong của nó để đáp ứng các tiêu chí 100% - p%

một số demo của thân lồi đang ở đây http://www.cs.unc.edu/~snoeyink/demos/

và ở đây bạn có một số biết thêm http://softsurfer.com/Archive/algorithm_0109/algorithm_0109.htm

Answer 7

Cảm ơn mọi người đã trả lời!

Giải pháp tốt nhất dường như đang sử dụng "khối dựng sẵn dựng sẵn": n x n mảng với các ô đã chọn và phủ mảng pixel bằng các ô này.

Ví dụ, một mảng 4 x 4 với độ bao phủ 12,5% sẽ là:

0 0 1 0 
0 0 0 0 
1 0 0 0 
0 0 0 0 

Với 6,3% bảo hiểm:

0 0 0 0 
0 1 0 0 
0 0 0 0 
0 0 0 0 

Để có được một bảo hiểm% trong giai đoạn này, chỉ thay thế giữa các khối theo một kiểm đếm hoạt động của phạm vi thực tế% tổng thể cho đến nay. Để che chiều rộng không phải là bội số của 4, hãy sử dụng một số khối 3 x 3. Để trang trải một khu vực lớn hơn hiệu quả hơn, chỉ cần sử dụng các khối lớn hơn.

Điều này bao gồm toàn bộ mảng hiệu quả mà không tính toán khoảng cách hoặc số học dấu phẩy động.

Answer 8

Lựa chọn pixel "trải rộng nhất" là tập hợp có tam giác Delaunay bao gồm các hình tam giác đều. Tập hợp các điểm dẫn đến triangulation này được tìm thấy bằng cách chia mảng pixel thành một tập các hộp, trong đó mỗi ô là sqrt (3) dài hơn chiều rộng. Mỗi hộp đóng góp 5 điểm ảnh cho tập hợp pixel cuối cùng (một điểm ở mỗi góc, cộng với một nút trung tâm ở giữa hộp). Bí quyết là để tìm bao nhiêu hàng và cột của hộp sẽ cung cấp cho bạn tỷ lệ 1: sqrt (3) này. Mà không đi qua nguồn gốc, dưới đây là cách bạn nhận được rằng:

std::vector<PixelIndices> PickPixels(int width, int height, float percent) 
{ 
    int total_pixels = width*height; 
    int desired_pixel_count = (int)total_pixels*percent; 

    // split the region up into "boxes" with 4 corner nodes and a center node. 
    // each box is sqrt(3) times taller than it is wide. 

    // calculate how many columns of boxes 
    float a = 1.155*height/(float)width; 
    float b = .577*height/(float)width + 1; 
    float c = 1 - desired_pixel_count; 
    int num_columns = (int)((-b + sqrt(b*b -4*a*c))/(2*a)); 

    // Now calculate how many rows 
    int num_rows = .577*height*num_columns/(float)width; 

    // total number of pixels 
    int actual_pixel_count = 2*num_rows*num_columns + num_rows + num_columns + 1; 

    std::cout << " Total pixels: " << total_pixels << std::endl; 
    std::cout << "  Percent: " << percent << std::endl; 
    std::cout << "Desired pixels: " << desired_pixel_count << std::endl; 
    std::cout << " Actual pixels: " << actual_pixel_count << std::endl; 
    std::cout << " Number Rows: " << num_rows << std::endl; 
    std::cout << "Number Columns: " << num_columns << std::endl; 

    // Pre-allocate space for the pixels 
    std::vector<PixelIndices> results; 
    results.reserve(actual_pixel_count); 

    // Now get the pixels, my integer math is probably wrong here, didn't test 
    // (didn't even finish, ran out of time) 
    for (int row = 0; row <= num_rows; row++) 
    { 
    int row_index = row*height/num_rows; 

    // Top of box 
    for (int col = 0; col <= num_columns; col++) 
    { 
     int col_index = col*width/num_columns; 
     results.push_back(PixelIndices(row_index, col_index)); 
    } 

    // Middle of box 
    if (row != num_columns) 
    { 
     for (int col = 0; col < num_columns; col++) 
     { 
     // I'll leave it to you to get this, I gotta go! 
     } 
    } 
    } 

    return results; 
} 

Thay vì sử dụng phân chia số nguyên để tìm các chỉ số, bạn có thể tăng tốc độ này lên bằng cách tìm khoảng cách giữa mỗi điểm trong một hàng/cột và chỉ cần thêm bởi bù đắp.

Answer 9

Bạn có thể thử Wang gạch:
http://en.wikipedia.org/wiki/Wang_tile
(Xem các trang liên kết đó để giấy Cohen, và giấy Kopf của tôi là một người dùng mới nên không thể gửi tất cả các liên kết.).

Các liên kết với nhau cả ý tưởng lát sẵn có, cũng như yêu cầu phân bố đồng đều thường được giải quyết bằng mẫu đĩa Poisson. Gạch Wang có thể tránh các hiệu ứng kỳ hạn gần như chắc chắn là một vấn đề với việc sử dụng trực tiếp hơn các lát dựng sẵn.

Answer 10

Rất cũ, nhưng đáng giá, vì câu trả lời đã bỏ lỡ một phương pháp quan trọng và tập trung vào các giải pháp tối ưu mà bạn không quan tâm. Tuy nhiên, phương pháp tôi đề xuất có thể hoặc không phù hợp với nhu cầu của bạn.

Bạn có thể sử dụng quasi random sequences, được thiết kế cho các sự cố như vậy. Phổ biến nhất là Sobol sequences, mà bạn có thể tìm thấy các gói đóng hộp cho hầu như bất kỳ ngôn ngữ nào. Chúng cực kỳ nhanh: chỉ số học bitwise.

Rất có thể sẽ tạo ra một số cụm, nhưng điều này có thể tránh được bằng cách chọn "hạt giống" để sử dụng cho kích thước x và y trước và kiểm tra bằng mắt thường.

Nó phụ thuộc vào những gì bạn muốn làm với các điểm: nếu "trải rộng hình ảnh" là quan trọng, điều này có thể không phải là những gì bạn muốn. Nếu bạn muốn điểm mà "điền vào máy bay" gần như đồng đều, họ hoàn toàn làm công việc. Chúng đặc biệt hữu ích để trung bình một cái gì đó trên một hình ảnh một cách nhanh chóng, vì nó đòi hỏi ít điểm hơn với thế hệ ngẫu nhiên "bình thường". Thử nghiệm với các kích thước khác nhau và xem.

Xem thêm this link để thử nghiệm exemples và ảnh.