Теорема связности для параллельных растровых скелетов

[Даниил Алиевский]

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

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

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

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

[MBo]

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

[Даниил Алиевский]

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

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

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

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

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

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

[Даниил Алиевский]

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

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

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

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

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