Intelligent scissors Опции

[wiz29]

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

[ufna]

ну вот смотри, промелькнуло название "заданная вершина". Как вывод, нас интересуют кратчайшие маршруты от этих точек до затравочной. Как вариант, возможно использование A*, либо алгоритм Флойда. Во втором случае мы получаем уже просчитанную матрицу, поэтому для всех заданных вершин значения будут вычислены, а не считаться "до затравочной" - это как минимум снижает объем вычислений. В первом - вычисление всей матрицы становится нафиг не нужно, но возникает определенная погрешность, вызываемая эвристической функцией (но здесь нужно продумать правильно эвристику, возможно вариант будет очень быстрым).

А сколько "заданных вершин" участвуют в алгоритме? Т.е. откуда они беруться? Это те пиксели где пользователь провел пером?

про вычисление весов спрашивал в том контексте, что нельзя ли матрицу "сжать" по размером, не слишком теряя точность.


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

Сообщение отредактировал ufna - 27.8.2010, 15:29