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

Форум работает в режиме архива, только для чтения и поиска.
Архив 2004 Архив 2007 Архив 2013

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 24.11.2010, 19:55
Новичок

Отправить личное сообщение для Даниил Алиевский Посмотреть профиль Найти все сообщения от Даниил Алиевский
 
Регистрация: 18.09.2007
Сообщений: 6

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

Теорема воистину "выстрадана": убил почти месяц, чтобы наконец гарантировать, что мои 3x5-скелеты из библиотек AlgART правильные. Очень долго вместо доказательства получались дикие монстры, в которых к тому же были ошибки - но сейчас, кажется, я нашел "правильные" и "красивые" исходные условия, и теорема таки доказалась, с Божьей помощью.

Фишка теоремы - возможность гарантировать связность для параллельных, а не последовательных алгоритмов, т.е. для алгоритмов, которые для битов работают в сотни раз быстрее. Статьи про скелетизацию, которые я находил пока в интернете, с академической невозмутимостью игнорируют такие приземленные вещи, как возможность за 1 такт обработать все 128 битов SSE2-регистра.

Полагаю, что эта теорема пригодится не только мне и моей фирме. Посему публикую здесь ссылку. В любом случае буду чрезвычайно признателен, если кто-нибудь заинтересуется и прочтет доказательство - вдруг до сих пор имеют место ошибки.
  #2  
Старый 24.11.2010, 20:38
MBo MBo вне форума
Местный

Отправить личное сообщение для MBo Посмотреть профиль Найти все сообщения от MBo
 
Регистрация: 21.09.2006
Адрес: Новосибирск
Сообщений: 1,374

На английском можно публиковаться на
http://arxiv.org/
В разделе Computer Science можно подыскать соотв. подраздел.
Возможно, подобные сайты есть и для русскоязычных статей, но не знаю, какие являются солидными.
  #3  
Старый 28.11.2010, 22:28
Новичок

Отправить личное сообщение для Даниил Алиевский Посмотреть профиль Найти все сообщения от Даниил Алиевский
 
Регистрация: 18.09.2007
Сообщений: 6

Дополнил теорему двумя конкретными примерами скелетизирующих алгоритмов, а также теоремами тонкости, дающими оценку наихудших по "толстоте" узлов в получаемом скелете. Прошу любить и жаловаться.
  #4  
Старый 28.11.2010, 23:01
гость

 
Сообщений: n/a

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

Нет обзора ранее проделанных исследований (т.е prior work) в литературе. Простой поиск в гугле тут же находит например такую статью 2000-го года - http://portal.acm.org/citation.cfm?id=1080615 - про параллельный алгоритм истончения. Как ваш алгоритм согласуется с результатами этой работы? Это первый вопрос который возникнет у любого специалиста из области, читающего вашу статью.
  #5  
Старый 28.11.2010, 23:06
гость

 
Сообщений: n/a

Или вот еще работа аж 1984 года, высокоцитируемая. http://www-prima.inrialpes.fr/perso/...ateway.cfm.pdf Тоже про параллельные алгоритмы.
  #6  
Старый 28.11.2010, 23:20
гость

 
Сообщений: n/a

Цитата:
Я несколько далек от академической науки и не очень представляю, как принято публиковать новые идеи.
Ищите академические журналы по вашей теме (смотрите, где публикуются другие люди по вашей теме), и отправляете их редакторам вашу статью, e-mail'ом, через форму на сайте, в запущенных случаях - бумажной почтой. Если заниматься наукой серьезно, а не абы как "для диссера", то публиковаться, разумеется, лучше на английском. У каждого журнала могут быть своим требования к оформлению, формату статьи и т.п., на сайтах обычно пишут. Вашу статью прочтут рецензенты журнала, напишут замечания, вы их исправляете, и т.д. через ноль или более итераций вашу статью либо принимают к публикации, либо (что чаще) посылают ко всем чертям.
  #7  
Старый 29.11.2010, 00:04
Новичок

Отправить личное сообщение для Даниил Алиевский Посмотреть профиль Найти все сообщения от Даниил Алиевский
 
Регистрация: 18.09.2007
Сообщений: 6

Сообщение от гость
Что-то очень подозрительно что вы никого не цитируете - отправите статью в любой журнал, за это ее однозначно зарежут.
Почему подозрительно? Я же не академический ученый, а программист. Статья получилась как побочный продукт коммерческой разработки. Мне просто некогда заниматься поисками статей, если их не удается найти быстро. Все, что я более или менее всерьез читал на эту тему - весьма поверхностная работа http://www.geometrictools.com/Docume.../Skeletons.pdf Давида Эберли, где изложен крайне корявый последовательный алгоритм. Как разработчик сайтов (среди прочих профессий), я не хочу "грузить" посетителя подобной явно бесполезной ссылкой. Попадались мне и более сложные разработки однопроходных алгоритмов, но это опять же совершенно не по теме: мой алгоритм многопроходный. Если дойдут руки (и коммерческая необходимость) до реализации однопроходных методов, основанных на вычислительной геометрии, будет повод сравнить эффективность. Пока что мне сдается, что эти алгоритмы будут на порядки уступать моим для объектов "разумной" толщины, даром что я на Java пишу. А для очень "толстых" объектов есть очевидная логарифмирующая оптимизация: построить при помощи конъюнкций пирамиду разрешений и скелетизировать итеративно, наращивая степень детальности.

Та работа 1984 года, кажется, начисто избегает вопроса доказательства связности - то самое, из-за чего мне пришлось убить месяц. Кроме того, скелеты 3x3 - это изначально несерьезно, они страдают разнообразными артефактами - вроде того, что толстый объект, помещенный на "шахматное поле", вообще не скелетизируется.

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

В любом случае спасибо.
 


Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Теорема Тутте Flashback Графы 0 04.01.2010 16:11
Обнаружение параллельных узлов в ветвях орграфа Кирилл Графы 5 08.10.2008 03:41
максимальный поток в графе с использованием параллельных вычислений kernel1987 Графы 0 19.04.2008 21:22
Библиотека параллельных вычислений Sundials Serega Математические алгоритмы 1 01.03.2007 16:05