Разпознавание линий.

[Faust]

Всем доброго времени суток! Да не отошлют меня в FAQ с вопросом о распознавании изображений! На моей памяти подобным образом этот вопрос еще не ставился. Предположим, имеется некий черно-белый растр, на котором присутствует несколько линий (треков частиц). Проблема заключается в том, чтобы распознать эти самые линии, которые, вообще-то могут иметь толщину в несколько пикселей и не быть непрерывными. Вот, предположим, я задал точку на одной из таких кривых и хочу узнать уравнение касательной к ней. КАК???

[Ennor]

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

Блин, слишком нетривиальная задача. А алгоритмист из меня тот еще...

[alibek]

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

[alibek]

А алгоритм я бы прикинул примерно такой.
Делишь изображение на несколько фрагментов, размером, к примеру, не более 50x50 пикселов. В каждом фрагменте оцениваешь "плотность", т.е. суммируешь количество пикселов с цветом, отличных от фонового цвета. Выбираешь фрагмент с минимальной плотностью и находишь в нем точку.
От этой точки идешь по расширяющейся окружности, фиксируя все точки такого же (не фонового) цвета. Когда процент фоновых пикселов превысит 50%, то останавливаешь цикл и находишь геометрический центр полученной фигуры. Кроме того, определяешь среднее минимальное расстояние (т.е. берешь только те расстояния, которые меньше среднего расстояния, и вычисляешь из них среднее значение) от этого центра до границы фигуры. Это будет средняя толщина линии кривой.
Потом двигаешься от текущей (центральной) точки по расширяющейся окружности с шагом, равным толщине линии. Все встречающиеся точки запоминаешь в массив, после того, как окружность будет замкнута, анализируешь этот массив -- продолжением линии будет та точка, касательная к которой минимально отличается от касательной к текущей линии.

[Faust]

Трабл первый: треков на пленке как минимум два (лишние обрезать руцями не так уж и сложно, вот только какой же я тогда програмер!?): притом один из них - это спираль с ~10 различимыми витками.
Трабл второй: возможны такие деффекты пленки, как незначащие точки и "рарывы" тонких треков.

у тебя там камера Вильсона или чего покруче?

Она, родимая. Пленки "Made in Dubna".

Если кривая не слишком кривая (т.е. не скручивается спиралью)

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

[Approximator]

Alibek близко подошёл к решению проблемы.
Одно одополнение. Предварительно необходимо уравнения кривых (спиралей) параметризировать на энергию частиц (сиречь, величину капелек) и отношение заряда частиц к массе ("кривизна" спирали). В дальнейшем необходимо искать именно точки подходящие под те или иные вводные для этой модели. А вовсе не наоборот.

[Faust]

Approximator, суть работы как раз и заключается в поиске энергии частиц, исходя из трека. Можно судить лишь о промежутке значений, которые, вероятней всего, будут наблюдаться. У меня есть подозрение, что при двух степенях свободы пребирать значения типа Double - расточительно по отношению к ресурсам системы.

[Approximator]

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

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

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

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

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

У меня есть подозрение, что при двух степенях свободы пребирать значения типа Double - расточительно по отношению к ресурсам системы.

Для каких величин? Вообще у тебя все единицы измерения должны быть привязаны к "степеням свободы" в пределах изображения, то есть к длине и ширине изображения в пикселях.

[Mikle]

Вот когда-то решалась очень близкая задача:
http://bbs.vbstreets.ru/viewtopic.php?t=7600&highlight=

[Faust]

Не очень-то близкая, но все равно спасибо, что напомнил месторасположение топика.

[Approximator]

Если всё ещё актуально, могу связать с человеком, имеющем отношение к работающей программе на АЛИСЕ (по ходу, star'овскую программу собираются делать по её образу и подобию). А можно и с тем, что раньше занимался этой проблемой в ОИЯИ (сейчас он в Германии). Будет желание сообщи в личку.