Алгоритм FAST для полярного-> декартово преобразование
Это позволяет Вам использовать ключевое слово C# в качестве переменной. Например:
class MyClass
{
public string name { get; set; }
public string @class { get; set; }
}
7 ответов
Как насчет
x=r*cos(angle)
y=r*sin(angle)
Это стандартный способ преобразования из полярного в декартово, и, если вы не собираетесь использовать какой-либо поиск по таблице, на самом деле нет более быстрого варианта.
Править : wrang wrang имеет хороший смысл. Если вы пытаетесь преобразовать изображение в полярных координатах I (угол, r) в изображение в декартовых координатах I_new (x, y) , вам определенно лучше использовать обратное преобразование, как показано ниже:
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
Как правило, угол и r не будут целыми числами, поэтому вам нужно выполнить некоторую интерполяцию в изображении I . Самый простой способ сделать это - просто округлить угол и r ; это даст вам интерполяцию ближайшего соседа . Если вам нужно лучшее качество,
Вы можете перебрать каждый пиксель в полярном карту изображения, а затем визуализируйте результирующий участок дуги в декартовой плоскости изображения:
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);
}
}
Многие библиотеки рисования имеют встроенные функции для рисования этого участка дуги, но вы всегда можете просто аппроксимировать его простым многоугольником:
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);
}
Если вас не волнует сглаживание, почему бы вам просто не вычислить полярные координаты для каждой декартовой пиксельной координаты назначения и не прочитать значение цвета? См. http://en.wikipedia.org/wiki/Polar_coordinate_system#Converting_between_polar_and_Cartesian_coordinates , если вам нужна помощь в этом.
Если ваша сетка равномерно разделена по полярным координатам, тогда ваш алгоритм может быть сокращен до O (N ^ 2), если вы воспользуетесь преимуществом того факта, что ближайшая точка к (r, theta) будет одним из четырех углов элемента сетки, в котором он содержится.
В более общем случае, когда сетка является произведением произвольных разбиений размерности r и тета, она может вырасти до O ((N log N) ^ 2), если вам нужно найти местоположение точки в каждый раздел. Однако, если разделы создавались систематически, вы сможете вернуться к O (N ^ 2).
Ошибка памяти, но может существовать быстрая версия этого алгоритма, которая включает БПФ. Однажды я проходил курс по медицинской визуализации, и мне показалось, что подобные вещи возникали при непревращении / растрировании компьютерной томографии. Некоторые ключевые слова для поиска - это преобразование радона, алгоритм фильтрованной обратной проекции и компьютерная томография. Я быстро просмотрел их в Википедии, и ничего не выскочило, но, возможно, более тщательный обзор принесет немного золота.
алгоритм фильтрованной обратной проекции и компьютерная томография. Я быстро просмотрел их в Википедии, и ничего не выскочило, но, возможно, более тщательный обзор принесет немного золота. алгоритм фильтрованной обратной проекции и компьютерная томография. Я быстро просмотрел их в Википедии, и ничего не выскочило, но, возможно, более тщательный обзор принесет немного золота.Алгоритм O (N 2 log (N)):
- Массив S будет использоваться для координат ближайшего источника (полярных) в декартовых координатах.
- S начинает заполняться значением «еще не инициализировано». (Python: None, Haskell: Nothing и т. Д.)
- O (N 2 ) - Итерация всех полярных координат.
- Перевести в декартовы координаты
- Найдите ближайшую декартову координату на изображении назначения. (округляя и применяя границы)
- Заполните соответствующую ячейку в S этой координатой
- O (N 2 log (N)) - Выполните модифицированный алгоритм Дейкстры, как описано ниже:
- «График» для нашего алгоритма поиска выглядит следующим образом:
- Все ячейки S являются узлами.
- Соседями ячейки являются те, к которым король в шахматах может перейти от нее.
- «Счет» ячейки бесконечен, если она не инициализирована, и расстояние от нетронутой декартова координата полярной координаты, на которую он указывает
- При обновлении соседа ячейки N мы помещаем в него значение из ячейки N (но, как и в случае с Дейкстрой, только если его оценка лучше, чем текущая оценка)
- начальная точка - это массив S, инициализированный, как описано выше
- «График» для нашего алгоритма поиска выглядит следующим образом:
Если все ваши изображения имеют размер 512x512, я бы использовал таблицу поиска, которая сопоставляет взвешенный набор пикселей в вашем полярном изображении с декартовым изображением. Это большая работа заранее, но окончательный расчет будет O (n ^ 2). Если LUT не подходит, я бы использовал:
x=r*cos(angle)
y=r*sin(angle)
Для каждого пикселя в полярном изображении, чтобы сопоставить его с «a» пикселем в декартовом изображении, где выходной пиксель - это среднее значение всех входных пикселей, которые попадают на Это. Затем применяйте повторяющиеся расширения, пока не останутся неинициализированные пиксели. Для расширения вы используете элемент структурирования 3x3 и заменяете значение выходного пикселя значением центрального пикселя, только если оно ранее не имело значения. Затем, в качестве последней меры, примените фильтр Гаусса ко всему изображению, чтобы сгладить резкие края.