LINUX.ORG.RU

Алгоритмы отождествления объектов на изображении


0

2

Не могу даже придумать, как правильно составить поисковый запрос в google.

Проблема такова: есть набор изображений одной и той же звездной области, положение области от кадра к кадру изменяется (небольшие колебания + вращение). Для определения некоторых параметров мне необходимо выбрать несколько звезд, присутствующих на всех изображениях, и вычислить координаты центра тяжести каждой.

Для отдельно взятого кадра все выполняется элементарно, но вот когда появляется следующий кадр, возникают проблемы:

  1. экспозиция на разных снимках может быть разной, поэтому количество слабых объектов непостоянно даже на точных копиях одной и той же области;
  2. из-за смещений и поворота часть объектов постепенно скрывается из поля зрения, часть появляется.

Если бы был только лишь параллельный перенос, я просто посчитал бы кросс-корреляционную функцию для двух изображений, вычислил бы по ней примерный вектор смещения, а затем уточнил бы его по координатам объектов. Здесь же изображение еще и вращается, т.е. так просто сделать не получится.

Вопрос: подскажите, пожалуйста, что можно почитать, чтобы понять, какой алгоритм мне стоит использовать для решения проблемы.

Апробацию алгоритма буду проводить в Octave, применять - в своем велосипеде на С.

P.S. Да, вот здесь я привожу пример изображения.

☆☆☆☆☆

Последнее исправление: Eddy_Em (всего исправлений: 1)

Нашел в вики нечто похожее: «sequence labeling», глянул статейку. Неужели все так запущенно и простеньких алгоритмов нет?


На ум приходит следующий алгоритм: выделить наиболее яркие объекты (штучки 3-4, не больше), определить их взаимную ориентацию (т.е. для каждого объекта в полярной системе координат записать положение остальных), а затем выделить еще десяток-другой объектов послабее и точно так же для каждого яркого объекта построить в полярной системе координаты тех объектов.

Хранить эти данные можно, например, отсортировав их по полярной координате, начиная с самого близкого объекта.

Для отождествления объектов перебирать опорные, пока не получим наиболее полное (в идеале - точное) соответствие с точностью до погрешности dr.

Но, сдается мне, этот алгоритм - какой-то ущербный. Например, если яркие объекты будут располагаться по углам почти равностороннего треугольника (с точностью до dr), а четвертого опорного объекта с одного кадра на следующем не будет (и вместо него будет выбран следующий по яркости объект), то придется еще и перебирать по вспомогательным объектам. В общем, сдается мне, вычисляться все это будет очень долго.

Или я не прав?

Eddy_Em ☆☆☆☆☆
() автор топика
Ответ на: комментарий от marvin_yorke

В трех это вообще проблема занятная. А вот два измерения - даже на курсовую не тянет. Вот найти бы только нормальные быстрые алгоритмы. А то даже не гуглится как-то.

Eddy_Em ☆☆☆☆☆
() автор топика
Ответ на: комментарий от Eddy_Em

а медленные есть? ибо если задача разовая, то может лучше подождать на медленных, чем голову морочить, если профит не пропорционален усилиям на его достижения?
плюс насколько я вижу, задача должна хорошо параллелиться - каждую пару (тройку/четверку/... по желанию) кадров можно считать независимо друг от друга

marvin_yorke ★★★
()
Ответ на: комментарий от Eddy_Em

и еще такой вопрос - программы для сшивания панорам делают что-то очень похожее. может стоит покопать алгоритмы там?

marvin_yorke ★★★
()
Ответ на: комментарий от marvin_yorke

Параллельно находить объекты не получится: один снимок занимает почти 100МБ оперативки, если загрузить штуки 4, система начинает жутко тормозить из-за нехватки оперативы (хоть ее и 2ГБ).

А вот строить «деревья» можно и в параллели. Там данных немного. Можно, конечно, попробовать реализовать мой способ в Octave.

Но хотелось бы подождать других вариантов. Вдруг есть что-то попроще?

Eddy_Em ☆☆☆☆☆
() автор топика
Ответ на: комментарий от marvin_yorke

Там идет выделение участка изображения на основе градиентных карт. Это несколько другое.

Eddy_Em ☆☆☆☆☆
() автор топика
Ответ на: комментарий от Eddy_Em

И да, для панорам найти примерное расположение небольшого (чтобы не сказывались нелинейные искажения) участка изображения можно и корреляционным методом (если, конечно, предполагать, что изображения не поворачиваются - что, по идее, является априорным предположением).

Eddy_Em ☆☆☆☆☆
() автор топика
Ответ на: комментарий от Eddy_Em

я правильно понимаю, что относительное положение объектов друг к другу у тебя не меняется? или помимо сдвига и поворота, еще и сжатие/растяжение надо учитывать?

marvin_yorke ★★★
()
Ответ на: комментарий от marvin_yorke

Относительное расположение с точностью до погрешности определения центра объекта не изменяется.

Только небольшой сдвиг и поворот.

Eddy_Em ☆☆☆☆☆
() автор топика
Ответ на: комментарий от Eddy_Em

тогда не будет ли самым простым вариантом сначалы выровняться сдвигом по самому яркому/крупному объекту, а потом поворотом вокруг полученного центра искать положение остальных? предложение, вероятно, дурацкое, т.к. ни разу не математик, но сам бы начал искать с этого

marvin_yorke ★★★
()
Ответ на: комментарий от marvin_yorke

Самого яркого объекта может не быть: может быть несколько объектов примерно одинаковой яркости. В этом-то и загвоздка.

Eddy_Em ☆☆☆☆☆
() автор топика

а может что-нибудь про фракталы, про фрактальный кепстр какой-нибудь?
а ещё могут подойти алгоритмы кластеризации

dimon555 ★★★★★
()
Ответ на: комментарий от dimon555

Погуглю завтра по кластеризации. Я надеялся, что кто-то уже с подобным сталкивался и мог бы мне посоветовать годный вариант.

Eddy_Em ☆☆☆☆☆
() автор топика
Ответ на: комментарий от psv1967

Тоже погуглю, как реализовать. OpenCV использовать не хочу: зачем мне этот монстр?

Eddy_Em ☆☆☆☆☆
() автор топика
Ответ на: комментарий от Eddy_Em

ну а вручную по точкам просто все...

расстояния от каждой до каждой, после этого ищем объект с таким же набором в предыдущем кадре... совпало --- объекты идентичны

psv1967 ★★★★★
()
Ответ на: комментарий от psv1967

Да, если ничего лучше не нагуглю, этот вариант и буду реализовывать. Правда, считает octave ужасно медленно (выделение объектов и получение их характеристик на С безо всяких CUDA работает почти на 2 порядка быстрее, чем в octave).

Пока лишь не могу придумать, как мне попроще находить соответствия между объектами (т.к. набор для одного и того же объекта может отличаться: слабые объекты могут не обнаружиться, либо же они могут зайти за край кадра).

В принципе, если выделять лишь несколько наиболее ярких объектов, используя более слабые только для дополнительной проверки, возможно, процесс будет быстрее. Но не нравится мне поштучный перебор в поиске совпадений. Хочется чего-нибудь вроде корреляции...

Eddy_Em ☆☆☆☆☆
() автор топика

Ладно, пока у меня вроде бы до конца года экстренных нагрузок не предвидится, так что, скорее всего, на днях я смогу даже эту задачу добить.

Решение, естественно, обязательно опубликую в ЖЖ (завел себе тратилку времени помимо ЛОРа, теперь вспоминаю все старые «достижения» и описываю там; заодно и новые буду выкладывать).

Eddy_Em ☆☆☆☆☆
() автор топика
Ответ на: комментарий от Eddy_Em

ну например можно просто брать центральную область более старого снимка и искать сходство наборов расстояний у объектов в наборе всего более позднего кадра ...

другой подход сравнить две матрицы расстояний? надо подумать...

psv1967 ★★★★★
()
Ответ на: комментарий от Eddy_Em

ну вот например:

способ трансформации дескрипторов я придумал когда резвился на медицинском форуме статистическом :)

берем все расстояния между парами звезд и определяем интервалы группировки (что бы достаточно точно измеряло).

после этого легким движением руки превращаем число расстояний до звезд (не совпадающих на обоих снимках) в число попаданий в интервалы группировки. эти интервалы группировки уже одинаковы для обоих снимков.

ну теперь применяем кластерный анализ с общему набору данных. выцепляем парные объекты :)

psv1967 ★★★★★
()
Ответ на: комментарий от psv1967

В принципе, да: как вариант, можно отсортировать пары по увеличению расстояния между ними, затем найти, две пары с почти одинаковыми расстояниями и уточнять уже по расстояниям от одного из объектов пары до остальных.

Правда, здесь будет довольно сложная структура данных: для каждого обнаруженного объекта придется запоминать интенсивность, координаты центра и векторы расстояний. В то же время, эти векторы расстояний должны будут быть обособленны (чтобы иметь возможность отсортировать по r).

Если сделать только один набор, то сложнее будет искать соответствия (отсортировать по r, либо выделить все векторы для данной звезды).

А искать соответствия для других опорных звезд по найденной паре равных векторов можно будет, приняв эти вектора за единицу. Если знать примерное положение центра вращения, можно легко определить базовый объект; иначе - придется проверять два варианта.

Eddy_Em ☆☆☆☆☆
() автор топика
Ответ на: комментарий от Eddy_Em

думаю что индивидуальная группировка расстояний звезды до всех остальных в кадре по общему для обоих снимков интервальному ряду даст возможность сразу получить все четкие пары соответствия

потом конечно надо будет дополнительно верифицировать наверняка 4-5 опорных звезд

psv1967 ★★★★★
()
Ответ на: комментарий от Eddy_Em

fig1 <- cbind(runif(10,1,10),runif(10,1,10))

fig1
[,1] [,2]
[1,] 7.414383 8.005984
[2,] 5.974652 3.584448
[3,] 9.117579 9.393274
[4,] 3.473168 3.297126
[5,] 1.260410 5.059692
[6,] 4.229807 7.837822
[7,] 3.695025 2.255150
[8,] 6.526372 8.293782
[9,] 5.637989 8.979291
[10,] 7.298260 7.840072

fig2[,1] <- fig2[,1]+2
fig2[,2] <- fig2[,2]+4

fig2
[,1] [,2]
[1,] 9.414383 12.005984
[2,] 7.974652 7.584448
[3,] 11.117579 13.393274
[4,] 5.473168 7.297126
[5,] 3.260410 9.059692
[6,] 6.229807 11.837822
[7,] 5.695025 6.255150
[8,] 8.526372 12.293782
[9,] 7.637989 12.979291
[10,] 9.298260 11.840072

dist(fig1, method = «manhattan»)
1 2 3 4 5 6 7
2 5.861267
3 3.090486 8.951753
4 8.650073 2.788806 11.740559
5 9.100265 6.189486 12.190751 3.975324
6 3.352738 5.998220 6.443224 5.297334 5.747527
7 9.470193 3.608926 12.560679 1.263833 5.239157 6.117454
8 1.175810 5.261053 3.690700 8.049859 8.500052 2.752525 8.869979
9 2.749701 5.731505 3.893573 7.846985 8.297178 2.549651 8.667105
10 0.282035 5.579232 3.372521 8.368038 8.818230 3.070704 9.188158
8 9
2
3
4
5
6
7
8
9 1.573891
10 1.225598 2.799489

dist(fig2, method = «manhattan»)
1 2 3 4 5 6 7
2 5.861267
3 3.090486 8.951753
4 8.650073 2.788806 11.740559
5 9.100265 6.189486 12.190751 3.975324
6 3.352738 5.998220 6.443224 5.297334 5.747527
7 9.470193 3.608926 12.560679 1.263833 5.239157 6.117454
8 1.175810 5.261053 3.690700 8.049859 8.500052 2.752525 8.869979
9 2.749701 5.731505 3.893573 7.846985 8.297178 2.549651 8.667105
10 0.282035 5.579232 3.372521 8.368038 8.818230 3.070704 9.188158
8 9
2
3
4
5
6
7
8
9 1.573891
10 1.225598 2.799489

psv1967 ★★★★★
()
Ответ на: комментарий от psv1967

> dist(fig2, method = «manhattan», upper =TRUE, diag =TRUE)
1 2 3 4 5 6 7
1 0.000000 5.861267 3.090486 8.650073 9.100265 3.352738 9.470193
2 5.861267 0.000000 8.951753 2.788806 6.189486 5.998220 3.608926
3 3.090486 8.951753 0.000000 11.740559 12.190751 6.443224 12.560679
4 8.650073 2.788806 11.740559 0.000000 3.975324 5.297334 1.263833
5 9.100265 6.189486 12.190751 3.975324 0.000000 5.747527 5.239157
6 3.352738 5.998220 6.443224 5.297334 5.747527 0.000000 6.117454
7 9.470193 3.608926 12.560679 1.263833 5.239157 6.117454 0.000000
8 1.175810 5.261053 3.690700 8.049859 8.500052 2.752525 8.869979
9 2.749701 5.731505 3.893573 7.846985 8.297178 2.549651 8.667105
10 0.282035 5.579232 3.372521 8.368038 8.818230 3.070704 9.188158
8 9 10
1 1.175810 2.749701 0.282035
2 5.261053 5.731505 5.579232
3 3.690700 3.893573 3.372521
4 8.049859 7.846985 8.368038
5 8.500052 8.297178 8.818230
6 2.752525 2.549651 3.070704
7 8.869979 8.667105 9.188158
8 0.000000 1.573891 1.225598
9 1.573891 0.000000 2.799489
10 1.225598 2.799489 0.000000


as.vector(dist(fig2, method = «manhattan»))

[1] 5.861267 3.090486 8.650073 9.100265 3.352738 9.470193 1.175810
[8] 2.749701 0.282035 8.951753 2.788806 6.189486 5.998220 3.608926
[15] 5.261053 5.731505 5.579232 11.740559 12.190751 6.443224 12.560679
[22] 3.690700 3.893573 3.372521 3.975324 5.297334 1.263833 8.049859
[29] 7.846985 8.368038 5.747527 5.239157 8.500052 8.297178 8.818230
[36] 6.117454 2.752525 2.549651 3.070704 8.869979 8.667105 9.188158
[43] 1.573891 1.225598 2.799489

(hist(as.vector(dist(fig2, method = «manhattan»))))$breaks

[1] 0 2 4 6 8 10 12 14

br <- (hist(as.vector(dist(fig2, method = «manhattan»))))$breaks


as.matrix(dist(fig2, method = «manhattan», upper =TRUE, diag =TRUE))[1,]

1 2 3 4 5 6 7 8
0.000000 5.861267 3.090486 8.650073 9.100265 3.352738 9.470193 1.175810
9 10
2.749701 0.282035

hist(as.matrix(dist(fig2, method = «manhattan», upper =TRUE, diag =TRUE))[1,], breaks = c(0, 2, 4, 6, 8, 10, 12, 14))$counts

[1] 3 3 1 0 3 0 0

datafig2 <- t(apply(as.matrix(dist(fig2, method = «manhattan», upper =TRUE, diag =TRUE)), 1, function (x) hist(x, breaks = c(0, 2, 4, 6, 8, 10, 12, 14))$counts))

datafig2


[,1] [,2] [,3] [,4] [,5] [,6] [,7]
1 3 3 1 0 3 0 0
2 1 2 5 1 1 0 0
3 1 4 0 1 1 1 2
4 2 2 1 1 3 1 0
5 1 1 2 1 4 0 1
6 1 4 3 2 0 0 0
7 2 1 1 1 4 0 1
8 4 2 1 0 3 0 0
9 2 4 1 1 2 0 0
10 3 3 1 0 3 0 0

datafig1 <- t(apply(as.matrix(dist(fig1, method = «manhattan», upper =TRUE, diag =TRUE)), 1, function (x) {hist(x, breaks = c(0, 2, 4, 6, 8, 10, 12, 14))$counts}))

datafig1

[,1] [,2] [,3] [,4] [,5] [,6] [,7]
1 3 3 1 0 3 0 0
2 1 2 5 1 1 0 0
3 1 4 0 1 1 1 2
4 2 2 1 1 3 1 0
5 1 1 2 1 4 0 1
6 1 4 3 2 0 0 0
7 2 1 1 1 4 0 1
8 4 2 1 0 3 0 0
9 2 4 1 1 2 0 0
10 3 3 1 0 3 0 0

rbind(datafig1, datafig2)

[,1] [,2] [,3] [,4] [,5] [,6] [,7]
1 3 3 1 0 3 0 0
2 1 2 5 1 1 0 0
3 1 4 0 1 1 1 2
4 2 2 1 1 3 1 0
5 1 1 2 1 4 0 1
6 1 4 3 2 0 0 0
7 2 1 1 1 4 0 1
8 4 2 1 0 3 0 0
9 2 4 1 1 2 0 0
10 3 3 1 0 3 0 0
1 3 3 1 0 3 0 0
2 1 2 5 1 1 0 0
3 1 4 0 1 1 1 2
4 2 2 1 1 3 1 0
5 1 1 2 1 4 0 1
6 1 4 3 2 0 0 0
7 2 1 1 1 4 0 1
8 4 2 1 0 3 0 0
9 2 4 1 1 2 0 0
10 3 3 1 0 3 0 0

result<-hclust(dist(rbind(datafig1, datafig2), method = «manhattan»))

hclust(dist(rbind(datafig1, datafig2), method = «manhattan»))$merge
[,1] [,2]
[1,] -1 -10
[2,] -11 1
[3,] -20 2
[4,] -2 -12
[5,] -3 -13
[6,] -4 -14
[7,] -5 -15
[8,] -6 -16
[9,] -7 -17
[10,] -8 -18
[11,] -9 -19
[12,] 3 10
[13,] 7 9
[14,] 6 12
[15,] 11 14
[16,] 4 8
[17,] 13 15
[18,] 5 16
[19,] 17 18

cbind(result$labels, 1:20)
[,1] [,2]
[1,] «1» «1»
[2,] «2» «2»
[3,] «3» «3»
[4,] «4» «4»
[5,] «5» «5»
[6,] «6» «6»
[7,] «7» «7»
[8,] «8» «8»
[9,] «9» «9»
[10,] «10» «10»
[11,] «1» «11»
[12,] «2» «12»
[13,] «3» «13»
[14,] «4» «14»
[15,] «5» «15»
[16,] «6» «16»
[17,] «7» «17»
[18,] «8» «18»
[19,] «9» «19»
[20,] «10» «20»

psv1967 ★★★★★
()
Ответ на: комментарий от psv1967

да, еще, наверное лучше группировать в интервальный ряд только расстояния меньше например половины максимального для снимка

psv1967 ★★★★★
()
Ответ на: комментарий от Eddy_Em

в R набросал ход работы алгоритма :)

в конце, поскольку графику сюда впилить очень сложно, (да и нужен просто порядок агрегации строк кластерным алгоритмом), этот самый порядок и вывел (ну и метки исходные соответствующие номерам строк преобразованных данных)

psv1967 ★★★★★
()
Ответ на: комментарий от psv1967

даже проще можно

as.matrix(dist(rbind(datafig1, datafig2), method = «manhattan»))==0

1 2 3 4 5 6 7 8 9 10 1 2 1 TRUE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE TRUE TRUE FALSE 2 FALSE TRUE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE TRUE 3 FALSE FALSE TRUE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE 4 FALSE FALSE FALSE TRUE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE 5 FALSE FALSE FALSE FALSE TRUE FALSE FALSE FALSE FALSE FALSE FALSE FALSE 6 FALSE FALSE FALSE FALSE FALSE TRUE FALSE FALSE FALSE FALSE FALSE FALSE 7 FALSE FALSE FALSE FALSE FALSE FALSE TRUE FALSE FALSE FALSE FALSE FALSE 8 FALSE FALSE FALSE FALSE FALSE FALSE FALSE TRUE FALSE FALSE FALSE FALSE 9 FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE TRUE FALSE FALSE FALSE 10 TRUE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE TRUE TRUE FALSE 1 TRUE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE TRUE TRUE FALSE 2 FALSE TRUE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE TRUE 3 FALSE FALSE TRUE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE 4 FALSE FALSE FALSE TRUE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE 5 FALSE FALSE FALSE FALSE TRUE FALSE FALSE FALSE FALSE FALSE FALSE FALSE 6 FALSE FALSE FALSE FALSE FALSE TRUE FALSE FALSE FALSE FALSE FALSE FALSE 7 FALSE FALSE FALSE FALSE FALSE FALSE TRUE FALSE FALSE FALSE FALSE FALSE 8 FALSE FALSE FALSE FALSE FALSE FALSE FALSE TRUE FALSE FALSE FALSE FALSE 9 FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE TRUE FALSE FALSE FALSE 10 TRUE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE TRUE TRUE FALSE 3 4 5 6 7 8 9 10 1 FALSE FALSE FALSE FALSE FALSE FALSE FALSE TRUE 2 FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE 3 TRUE FALSE FALSE FALSE FALSE FALSE FALSE FALSE 4 FALSE TRUE FALSE FALSE FALSE FALSE FALSE FALSE 5 FALSE FALSE TRUE FALSE FALSE FALSE FALSE FALSE 6 FALSE FALSE FALSE TRUE FALSE FALSE FALSE FALSE 7 FALSE FALSE FALSE FALSE TRUE FALSE FALSE FALSE 8 FALSE FALSE FALSE FALSE FALSE TRUE FALSE FALSE 9 FALSE FALSE FALSE FALSE FALSE FALSE TRUE FALSE 10 FALSE FALSE FALSE FALSE FALSE FALSE FALSE TRUE 1 FALSE FALSE FALSE FALSE FALSE FALSE FALSE TRUE 2 FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE 3 TRUE FALSE FALSE FALSE FALSE FALSE FALSE FALSE 4 FALSE TRUE FALSE FALSE FALSE FALSE FALSE FALSE 5 FALSE FALSE TRUE FALSE FALSE FALSE FALSE FALSE 6 FALSE FALSE FALSE TRUE FALSE FALSE FALSE FALSE 7 FALSE FALSE FALSE FALSE TRUE FALSE FALSE FALSE 8 FALSE FALSE FALSE FALSE FALSE TRUE FALSE FALSE 9 FALSE FALSE FALSE FALSE FALSE FALSE TRUE FALSE 10 FALSE FALSE FALSE FALSE FALSE FALSE FALSE TRUE

psv1967 ★★★★★
()
Ответ на: комментарий от Eddy_Em

сейчас, не могу удержаться

f1f2.matr<-as.matrix(dist(rbind(datafig1, datafig2), method = «manhattan»))
f1f2.matr[lower.tri(f1f2.matr)] <- NA
diag(f1f2.matr)<- NA
f1f2.matr

1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 1 NA 10 10 4 8 10 6 2 4 0 0 10 10 4 8 10 6 2 4 0 2 NA NA 10 8 8 6 10 10 8 10 10 0 10 8 8 6 10 10 8 10 3 NA NA NA 8 10 8 10 12 6 10 10 10 0 8 10 8 10 12 6 10 4 NA NA NA NA 6 10 4 4 4 4 4 8 8 0 6 10 4 4 4 4 5 NA NA NA NA NA 10 2 8 8 8 8 8 10 6 0 10 2 8 8 8 6 NA NA NA NA NA NA 12 12 6 10 10 6 8 10 10 0 12 12 6 10 7 NA NA NA NA NA NA NA 6 6 6 6 10 10 4 2 12 0 6 6 6 8 NA NA NA NA NA NA NA NA 6 2 2 10 12 4 8 12 6 0 6 2 9 NA NA NA NA NA NA NA NA NA 4 4 8 6 4 8 6 6 6 0 4 10 NA NA NA NA NA NA NA NA NA NA 0 10 10 4 8 10 6 2 4 0 1 NA NA NA NA NA NA NA NA NA NA NA 10 10 4 8 10 6 2 4 0 2 NA NA NA NA NA NA NA NA NA NA NA NA 10 8 8 6 10 10 8 10 3 NA NA NA NA NA NA NA NA NA NA NA NA NA 8 10 8 10 12 6 10 4 NA NA NA NA NA NA NA NA NA NA NA NA NA NA 6 10 4 4 4 4 5 NA NA NA NA NA NA NA NA NA NA NA NA NA NA NA 10 2 8 8 8 6 NA NA NA NA NA NA NA NA NA NA NA NA NA NA NA NA 12 12 6 10 7 NA NA NA NA NA NA NA NA NA NA NA NA NA NA NA NA NA 6 6 6 8 NA NA NA NA NA NA NA NA NA NA NA NA NA NA NA NA NA NA 6 2 9 NA NA NA NA NA NA NA NA NA NA NA NA NA NA NA NA NA NA NA 4 10 NA NA NA NA NA NA NA NA NA NA NA NA NA NA NA NA NA NA NA NA

which(f1f2.matr==0, arr.ind=TRUE)

row col 1 1 10 1 1 11 10 10 11 2 2 12 3 3 13 4 4 14 5 5 15 6 6 16 7 7 17 8 8 18 9 9 19 1 1 20 10 10 20 1 11 20

ну и осталось взять только уникальные пары.

а алгоритм записан простой

в fig1 точки (x,y) координаты звезд на снимке. в данном случае случайные, а при анализе каким стандартным алгоритмом найденные.

в fig2 помещаем сдвинутый снимок (это формальность потому что расстояния между точками не меняются)

рассчитываем матрицы расстояний

по гистограмме всех расстояний определяем интервалы группировки (я подумал может и пожиже интервалы можно взять).

применяем с помощью apply() группировку к каждой строке матрицы расстояний fig1 и fig2 соответсвенно. Полученные таблицы в каждой строке которой записан интервальный ряд мы уже можем просто слить в одну.

находим матрицу расстояния для общей таблицы интервальных рядов звезд и показываем уникальные нулевые (на практике близкие к нулевым).

все получен набор опорных звезд, мы знаем какая звезда fig1 соответствует какой звезде fig2

psv1967 ★★★★★
()
Ответ на: комментарий от psv1967

можно еще впилить этап проверки окончательной когда анализируем только расстояния между набором выявленных опорных звезд

psv1967 ★★★★★
()
Ответ на: комментарий от Eddy_Em

этож расстояния, разницы не будет никакой пока нет растяжения и сжатия

psv1967 ★★★★★
()
Ответ на: комментарий от psv1967

Честно говоря, я в вашем коде себя чувствую, как корова на ледовом катке :)

Даже не представляю, как это все на С перевести.

Eddy_Em ☆☆☆☆☆
() автор топика
Ответ на: комментарий от Eddy_Em

подключить R как библиотеку и вызывать эти функции?

или необходимый сишный код внутрь программы на R ?

оба варианта возможны

а какая скорость нужна? по идее все это достаточно быстро считается (единственно память будет есть пропорционально число звезд^2 потому что матрица расстояний полная)

psv1967 ★★★★★
()
Ответ на: комментарий от psv1967

подключить R как библиотеку и вызывать эти функции?

Да у меня и так уже уйма библиотек подключается. Это же зависимостей уйма будет, причем некоторые совершенно ненужные (leptonica еще хотя бы cuneiform'у нужна, а уж R точно практически никому не нужен).

а какая скорость нужна?

Хочется, чтобы полторы-две сотни изображений обрабатывались за разумное время: минут 5, не больше. А лучше - вообще минуты за полторы...

А насчет съедания памяти - не страшно. Одно изображение занимает ~72МБ. Так что матрицы 100х100 - мелочевка.

Eddy_Em ☆☆☆☆☆
() автор топика
Ответ на: комментарий от Eddy_Em

> Хочется, чтобы полторы-две сотни изображений обрабатывались за разумное время: минут 5, не больше. А лучше - вообще минуты за полторы...

вполне достижимо даже в R (если поиск-выделение звёзд-точек выносить на C)

psv1967 ★★★★★
()

Велосипедостроение

Вот такой велосипед я соорудил.

Он довольно просто реализуется на С (тем более, что кое-что можно будет даже подсократить в этом случае, т.к. в С используются не матричные вычисления, лишние итерации проводить не нужно будет).

Eddy_Em ☆☆☆☆☆
() автор топика
Ответ на: комментарий от psv1967

Там, увы, без циклов не обойтись.

Eddy_Em ☆☆☆☆☆
() автор топика
Ответ на: комментарий от Eddy_Em

может действительно не все звезды (и снимки) пускать в расчет, а только дающие наименьшую ошибку в итоговых вычислениях центра? ведь для вычисления центра будут полезны какие то особые пары из найденных? это наверное резко размер матриц сократит?

или предположив что центр известен (и типа совпадает всегда) посчитать в обратную сторону ошибки положения звезд на снимках?

psv1967 ★★★★★
()
Ответ на: комментарий от psv1967

может действительно не все звезды (и снимки) пускать в расчет, а только дающие наименьшую ошибку в итоговых вычислениях центра?

Я и это учел, но когда количество изображений достаточно большое (как в моем случае) это можно не учитывать (замедляется вычисление).

или предположив что центр известен (и типа совпадает всегда) посчитать в обратную сторону ошибки положения звезд на снимках?

Вычислив медиану положения центра, можно уже для каждого снимка определить собственные колебания.

Кстати, в моем случае можно, по идее, прикинуть положение центра вращения и методом наименьших квадратов. А вот для двух изображений годится только матричный способ.

Eddy_Em ☆☆☆☆☆
() автор топика

Классическая задача Image registration.

Вот тут братья славяне решают ту же задачу (и, похоже, тоже не любят делать литобзор). Кстати, для поиска оптимального смещения и поворота при заданном соответствии точек есть аналитическое решение (у них ссылка на Arun1987, но также можно погуглить absolute orientation problem).

eth
()
Ответ на: комментарий от eth

и, похоже, тоже не любят делать литобзор

Я только одну статью по теме нашел, и то после того, как сам задачу почти решил. Либо плохо искал, либо не любит народ по этой теме публиковаться.

Но за ссылочку спасибо, почитаю.

Eddy_Em ☆☆☆☆☆
() автор топика
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.