Thuật toán nhanh cho cực -> chuyển đổi Descartes

Question

Tôi có một hình ảnh trên một mạng lưới cực. Hình ảnh này nên được chuyển đổi thành một mạng lưới Descartes, nhưng thuật toán duy nhất tôi biết là thực sự chậm cho việc này. Bây giờ tôi sử dụng lưới Descartes, cho mỗi điểm tôi tìm thấy các giá trị r và theta, và sau đó tôi nhìn vào hai vectơ để tìm lỗi nhỏ nhất được xác định bởi:

min {(th_vec - theta)^2 + (range - r)^2}

Điều này cho phép vòng lặp lồng nhau bên trong vòng lặp lồng nhau bên ngoài, vì vậy tôi có độ phức tạp của O (N^4). Hình ảnh 512x512 sử dụng toàn bộ phút để hoàn thành. Tất nhiên, một sự phức tạp như vậy không thể được sử dụng, vì vậy tôi tự hỏi nếu có ai biết về bất kỳ thuật toán nhanh hơn để làm điều này?

Tôi có hình ảnh và hai vectơ. Trục X của hình ảnh là góc, trong khi trục Y của hình ảnh là chiều dài từ tâm. Góc luôn từ 0-2pi và phạm vi từ 0 đến r_max.

Cảm ơn bạn trước.

CHỈNH SỬA: Phạm vi từ 0 đến r_max, không phải -r_max thành r_max như trước. Tôi thấy rằng đã có một số sai sót. Tôi đã sử dụng bình thường, nghịch đảo, chuyển đổi với;

 

r=sqrt(x^2 + y^2); 
theta=atan2(y,x); 
 

Vấn đề là tôi phải lần đầu tiên chuyển đổi các giá trị x và y để x 'và y' giá trị, kể từ khi lưới là từ -r_max để r_max trong hình ảnh kết quả, nhưng theo pixel trong dữ liệu. Vì vậy, tôi có một hình ảnh 512x512, nhưng r_max có thể là một cái gì đó giống như 3.512. Vì vậy, tôi phải chuyển đổi mỗi giá trị pixel thành giá trị lưới, sau đó tìm giá trị r và theta. Khi tôi đã tìm thấy giá trị r và theta tôi phải chạy máng hai vectơ, phạm vi và th_vec, để tìm pixel trong hình ảnh gốc khớp với:

min {(range - r)^2 + (th_vec - theta)^2}

Điều này mang lại cho tôi sự phức tạp của O (n^4), vì vectơ th_vec và phạm vi có cùng kích thước với hình ảnh. Vì vậy, nếu tôi có một ma trận vuông 512x512 yếu tố, tôi phải chạy trough 68 719 476 736 yếu tố, đó là cách chậm. Vì vậy, tôi tự hỏi nếu có một thuật toán nhanh hơn? Tôi không thể thay đổi dữ liệu đầu vào, vì vậy theo như tôi biết, đây là cách duy nhất để làm điều đó nếu bạn không bắt đầu với triangulation và các công cụ, nhưng điều này là tốn kém trong thời gian của bộ nhớ.

Answer 1

Làm thế nào về

x=r*cos(angle) 
y=r*sin(angle) 

Đây là cách tiêu chuẩn chuyển đổi từ cực đến Descartes, và trừ khi bạn đang sử dụng một số loại tra cứu bảng, không có thực sự là một lựa chọn nhanh hơn.

Chỉnh sửa: wrang wrang có điểm tốt. Nếu bạn đang cố gắng để thay đổi một hình ảnh trong tọa độ cực I(angle, r) đến một hình ảnh trong Descartes phối I_new(x, y), bạn chắc chắn nên sử dụng việc chuyển đổi ngược lại, như sau:

for x=1,...,width 
    for y=1,...,height 
     angle=atan2(y, x) 
     r=sqrt(x^2+y^2) 
     I_new(x, y)=I(angle, r) 
    end 
end 

Như một quy luật, angle và r sẽ không là số nguyên, vì vậy bạn phải làm một số loại nội suy trong hình ảnh I. Cách dễ nhất để làm điều này chỉ đơn giản là làm tròn angle và r; điều này sẽ cung cấp cho bạn nearest-neighbour interpolation. Nếu bạn cần chất lượng tốt hơn, hãy thử các loại nội suy phức tạp hơn như nội suy bilinear hoặc bicubic.

Answer 2

Nếu bạn không quan tâm đến việc làm mịn, tại sao bạn không tính toán tọa độ cực cho từng tọa độ điểm ảnh Descartes và đọc giá trị màu? Xem http://en.wikipedia.org/wiki/Polar_coordinate_system#Converting_between_polar_and_Cartesian_coordinates nếu bạn cần trợ giúp thực hiện điều đó.

Answer 3

Nếu lưới của bạn được phân chia đồng đều theo tọa độ cực thì thuật toán của bạn có thể được giảm xuống O (N^2) nếu bạn tận dụng thực tế là điểm gần nhất tới (r, theta) sẽ là một trong bốn góc của phần tử lưới trong đó nó được chứa.

Trong trường hợp tổng quát hơn khi lưới là sản phẩm của phân vùng tùy ý của kích thước r và theta, có thể tăng lên O ((N log N)^2) nếu bạn phải tìm kiếm vị trí của điểm trong mỗi phân vùng. Tuy nhiên, nếu các phân vùng được xây dựng có hệ thống, bạn sẽ có thể quay trở lại O (N^2).

Answer 4

Bạn lặp trên mỗi pixel trong bản đồ hình ảnh cực và sau đó có thể làm cho phần hồ quang dẫn đến mặt phẳng ảnh Descartes:

polar to cartesian conversion http://img24.imageshack.us/img24/4635/polartocartesian.png

const float dR = 2*r_max/polar_image_height; 
const float dA = 2*pi/polar_image_width; 

float angle; 
float radius; 
for (int polar_x = 0; polar_x < polar_image_width; polar_x++) 
{ 
    for (int polar_y = 0; polar_y < polar_image_height; polar_y++) 
    { 
     angle = polar_x * dA; 
     radius = polar_y * dR - r_max; 
     DrawArcSection(radius, radius+dR, angle, angle+dA); 
    } 
} 

Nhiều thư viện bản vẽ đã được xây dựng trong các chức năng để vẽ phần hồ quang đó, nhưng bạn luôn có thể chỉ xấp xỉ nó với một đa giác đơn giản:

void DrawArcSection(float minRadius, float maxRadius, 
        float minAngle, float maxAngle) 
{ 
    point P1 = MakePoint(minRadius * cos(minAngle) + image_width/2, 
         minRadius * sin(minAngle) + image_height/2); 
    point P2 = MakePoint(minRadius * cos(maxAngle) + image_width/2, 
         minRadius * sin(maxAngle) + image_height/2); 
    point P3 = MakePoint(maxRadius * cos(minAngle) + image_width/2, 
         maxRadius * sin(minAngle) + image_height/2); 
    point P3 = MakePoint(maxRadius * cos(maxAngle) + image_width/2, 
         maxRadius * sin(maxAngle) + image_height/2); 

    DrawPolygon(P1, P2, P3, P4); 
} 

Answer 5

Bộ nhớ không thành công, nhưng có thể có một phiên bản nhanh của thuật toán này liên quan đến FFT. Ngày xửa ngày xưa tôi học một lớp về hình ảnh y khoa và có vẻ như những thứ như thế này xuất hiện khi không biến đổi/rasterize CT scan. Một số từ khóa cần tìm kiếm sẽ là biến đổi radon, thuật toán backprojection được lọc và quét CT. Tôi đã xem xét một thời gian ngắn trên wikipedia và không có gì nhảy ra ngoài, nhưng có lẽ một đánh giá kỹ lưỡng hơn sẽ bật lên một số vàng.

Answer 6

O (N log (N)) thuật toán:

• mảng S sẽ được sử dụng cho nguồn gần nhất (cực) coord mỗi coord Descartes.
• S bắt đầu được điền bằng giá trị "chưa được khởi tạo". (Python: Không, Haskell: Không có gì, v.v.)
• O (N) - Lặp lại tất cả các tọa độ cực của bạn.
  • Dịch chuyển mạch đồng nghiệp
  • Tìm tọa độ gần nhất trong hình ảnh đích của bạn.(Bằng cách làm tròn và biên giới áp dụng)
  • Fill trong tế bào có liên quan trong S với điều này phối hợp
• O (N log (N)) - Thực hiện một thuật toán Dijkstra sửa đổi như mô tả dưới đây:
  • các "Graph" cho thuật toán tìm kiếm của chúng tôi là như sau:
    • Tất cả các tế bào của S là các nút
    • hàng xóm của một tế bào là những nhà vua trong cờ vua có thể di chuyển đến từ nó
  • Các "Điểm" của một tế bào là vô hạn nếu nó không được khởi tạo, và khoảng cách từ ảnh hưởng coord Descartes của coord cực trỏ của nó để
  • Khi cập nhật một người hàng xóm của tế bào N chúng tôi đưa giá trị từ tế bào N trong nó (nhưng cũng giống như trong Dijkstra, chỉ khi nó làm cho số điểm của nó tốt hơn so với số điểm hiện tại của nó)
  • điểm khởi đầu là mảng chỉ số S khởi tạo như mô tả ở trên

Answer 7

Nếu tất cả của bạn hình ảnh là 512x512 sau đó tôi sẽ sử dụng một bảng tra cứu bản đồ một tập hợp các điểm ảnh có trọng số trong hình ảnh cực của bạn thành hình ảnh Descartes. Đây là rất nhiều công việc trả trước nhưng làm cho phép tính cuối cùng của bạn O (n^2). Nếu một LUT không phải là một tùy chọn thì tôi sẽ sử dụng:

x=r*cos(angle) 
y=r*sin(angle) 

Trên mỗi pixel trong ảnh cực để ánh xạ tới điểm ảnh "a" trong ảnh Descartes, nơi pixel đầu ra là trung bình của tất cả đầu vào điểm ảnh rơi trên đó. Sau đó, áp dụng các độ giãn nở lặp lại cho đến khi không còn các điểm ảnh chưa được khởi tạo. Đối với sự giãn nở, bạn sử dụng phần tử cấu trúc 3x3 và chỉ thay thế giá trị của pixel đầu ra bằng giá trị của pixel trung tâm nếu trước đó nó không có giá trị. Sau đó, như một biện pháp cuối cùng, áp dụng một bộ lọc gaussian cho toàn bộ hình ảnh để làm mịn các cạnh cứng. Đây là phương pháp nhanh nhất tôi có thể nghĩ về điều đó sẽ tạo ra một hình ảnh dễ chịu để xem xét trong một khoảng thời gian hợp lý.