Здравствуйте, xmlx, Вы писали:
X>Как сделать алгоритм, который приведёт к утоньшения этой буквы L, к X>такому виду, что у любой "1" было только две или только одна соседняя "1"
Здравствуйте, Were, Вы писали:
W>Здравствуйте, xmlx, Вы писали:
X>>Как сделать алгоритм, который приведёт к утоньшения этой буквы L, к X>>такому виду, что у любой "1" было только две или только одна соседняя "1"
W>Topological skeleton W>Внизу есть ссылки на алгоритмы.
я всё это прочитал. к сожалению, это не то что нужно.
у меня скелетонизация выполняется в два этапа. на первом — distance transform, вот после первого этапа получается изображение с "переменной толшиной" от 1 до 2 пикселей и нужно сделать заключительное утоньшение, оставив связное изображение толщиной точно в 1 пиксел. Я уже сделал такой алгоритм и он прекрасно работает, но мне он не совсем нравится, он не оптимальный. Может есть какие-то более "умные варианты"?
Здравствуйте, xmlx, Вы писали:
X>Здравствуйте, Were, Вы писали:
W>>Здравствуйте, xmlx, Вы писали:
X>>>Как сделать алгоритм, который приведёт к утоньшения этой буквы L, к X>>>такому виду, что у любой "1" было только две или только одна соседняя "1"
W>>Topological skeleton W>>Внизу есть ссылки на алгоритмы.
X>я всё это прочитал. к сожалению, это не то что нужно. X>у меня скелетонизация выполняется в два этапа. на первом — distance transform, вот после первого этапа получается изображение с "переменной толшиной" от 1 до 2 пикселей и нужно сделать заключительное утоньшение, оставив связное изображение толщиной точно в 1 пиксел. Я уже сделал такой алгоритм и он прекрасно работает, но мне он не совсем нравится, он не оптимальный. Может есть какие-то более "умные варианты"?
Я как-то делал скелетонизацию, но посеял pdf с алгоритмом (может позже найду). Остался только код:
void Skeletize()
{
int x, y,
n[8],
A, B,
subiter = 0;
bool bFound, bFound1 = true, bFound2 = true;
while( bFound1 || bFound2 )
{
for ( y = 0; y < m_Height; y++ )
{
for ( x = 0; x < m_Width; x++ )
{
if ( !At( x, y ))
continue;
n[0] = At( x, y - 1 );
n[1] = At( x + 1, y - 1 );
n[2] = At( x + 1, y);
n[3] = At( x + 1, y + 1 );
n[4] = At( x, y + 1 );
n[5] = At( x - 1, y + 1 );
n[6] = At( x - 1, y );
n[7] = At( x - 1, y - 1 );
B = 0 != n[0];
B += 0 != n[1];
B += 0 != n[2];
B += 0 != n[3];
B += 0 != n[4];
B += 0 != n[5];
B += 0 != n[6];
B += 0 != n[7];
if ( B < 2 || B > 6 )
continue;
A = !n[0] && n[1];
A += !n[1] && n[2];
A += !n[2] && n[3];
A += !n[3] && n[4];
A += !n[4] && n[5];
A += !n[5] && n[6];
A += !n[6] && n[7];
A += !n[7] && n[0];
if ( A != 1 )
continue;
if ( subiter == 0 &&
( n[0] && n[2] && n[4] ||
n[2] && n[4] && n[6] ))
continue;
if ( subiter == 1 &&
( n[0] && n[2] && n[6] ||
n[0] && n[4] && n[6] ))
continue;
At( x, y ) = 2;
}
}
bFound = false;
for ( y = 0; y < m_Height; y++ )
{
for ( x = 0; x < m_Width; x++ )
{
int &v = At( x, y );
if ( v == 2 )
{
bFound = true;
v = 0;
}
}
}
if ( subiter == 0 )
bFound1 = bFound;
else
bFound2 = bFound;
subiter = !subiter;
}
}
Небольшой комментарий:
Skeletize() — метод класса бинарного поля.
m_Height, m_Width — ширина и длина поля.
At() — метод, возвращающий ссылку на элемент поля. Если координаты вне поля, то ссылку на временный элемент.
X>Понимаю, что задача имеет множествоqwq решений. нужно найти оптимальное.
1.Просматриваешь изображение через окно 3x3
2.Если в центре окна 0 — нечего не делать
3.Если в центре окна 1, то
если граничные клетки содержат только одно связное множество единиц и кол-во единиц в нём >2, но меньше 8- записать в центральную клетку 0
4.Сдвинуть окно на шаг.
Граничных клеток — 8. Комбинация 0 и 1 в них образует число щт 0 до 255. Строим таблицу и указываем в ней те комбинации, при которых в центральную клетку будет записываться 0.
Это почти реализация одного из вариантов игры "Жизнь". Важно, что вышеописанные операции надо проводить последовательно!
X>>Понимаю, что задача имеет множествоqwq решений. нужно найти оптимальное.
А>1.Просматриваешь изображение через окно 3x3 А>2.Если в центре окна 0 — нечего не делать А>3.Если в центре окна 1, то А> если граничные клетки содержат только одно связное множество единиц и кол-во единиц в нём >2, но меньше 8- записать в центральную клетку 0 А>4.Сдвинуть окно на шаг.
А>Примеры на картинках:
А>000 000 001 001 111 111 А>011 ->001 010 ->010 110->100 и т.д. А>011 011 010 010 111 111
А>Граничных клеток — 8. Комбинация 0 и 1 в них образует число щт 0 до 255. Строим таблицу и указываем в ней те комбинации, при которых в центральную клетку будет записываться 0.
а можете привести здесь эту таблицу? заранее thanx.
X>>Понимаю, что задача имеет множествоqwq решений. нужно найти оптимальное.
А>1.Просматриваешь изображение через окно 3x3 А>2.Если в центре окна 0 — нечего не делать А>3.Если в центре окна 1, то А> если граничные клетки содержат только одно связное множество единиц и кол-во единиц в нём >2, но меньше 8- записать в центральную клетку 0 А>4.Сдвинуть окно на шаг.
А>Примеры на картинках:
А>000 000 001 001 111 111 А>011 ->001 010 ->010 110->100 и т.д. А>011 011 010 010 111 111
А>Граничных клеток — 8. Комбинация 0 и 1 в них образует число щт 0 до 255. Строим таблицу и указываем в ней те комбинации, при которых в центральную клетку будет записываться 0.
А>Это почти реализация одного из вариантов игры "Жизнь". Важно, что вышеописанные операции надо проводить последовательно!
если не трудно, напишите таблицу, вот с таким порядком нумерации
012
7x3
654
thanx. сорри за дубль... забыл написать порядок нумерации...
Re[3]: Алгоритм утоньшения изображения
От:
Аноним
Дата:
16.08.08 16:07
Оценка:
Здравствуйте, True2008, Вы писали:
T>Здравствуйте, Аноним, Вы писали:
А>>Здравствуйте, xmlx, Вы писали:
X>>>Понимаю, что задача имеет множествоqwq решений. нужно найти оптимальное.
А>>1.Просматриваешь изображение через окно 3x3 А>>2.Если в центре окна 0 — нечего не делать А>>3.Если в центре окна 1, то А>> если граничные клетки содержат только одно связное множество единиц и кол-во единиц в нём >2, но меньше 8- записать в центральную клетку 0 А>>4.Сдвинуть окно на шаг.
А>>Примеры на картинках:
А>>000 000 001 001 111 111 А>>011 ->001 010 ->010 110->100 и т.д. А>>011 011 010 010 111 111
А>>Граничных клеток — 8. Комбинация 0 и 1 в них образует число щт 0 до 255. Строим таблицу и указываем в ней те комбинации, при которых в центральную клетку будет записываться 0.
А>>Это почти реализация одного из вариантов игры "Жизнь". Важно, что вышеописанные операции надо проводить последовательно!
T>если не трудно, напишите таблицу, вот с таким порядком нумерации T>
T>012
T>7x3
T>654
T>
T>thanx. сорри за дубль... забыл написать порядок нумерации...
Алгоритм формирования таблицы.
Замена единицы на ноль происходит в тех случаях, когда граница содержит от 3 до семи подряд идущих (смежных) единиц (старшая единица и младшая считаются смежными).
Т.е. для трёх единиц — это случаи: 00000111, 00001110, 00011100, 00111000, 01110000, 11100000, 11000001, 10000011 (3,7,14,...).
— взять тройку и сдвигать её циклически влево (разряд из переполнения записывать в младший бит). А можно и вправо(не пробовал . Аналогично для четырёх и более единиц.
Таким образом, если биты границы образуют число 3 (7, 14, 15...), то центральный бит скользящего окна надо заменить но 0.
Конечно, результат(скелет двухградационного изображения) зависит от пути обхода. Но если сканировать изображение просто построчно, то в большинстве случаев этот алгоритм работает удовлетворительно.
Ну а уж выписывать таблицу — просто лень.
Вот в этом документе описан The thinning algorithm,
который они взяли видимо из книги Digital Image Processing (Rafael C. Gonzalez, Richard E. Woods) http://www.vision.auc.dk/~tbm/Student_projects/02-automatic.pdf
4.4.2 End points, страница 62 документа.
Есть его реализация в коде (должно работать ), если надо.
Здравствуйте, Аноним, Вы писали:
А>Конечно, результат(скелет двухградационного изображения) зависит от пути обхода. Но если сканировать изображение просто построчно, то в большинстве случаев этот алгоритм работает удовлетворительно. А>Ну а уж выписывать таблицу — просто лень.
Здравствуйте, True2008, Вы писали:
T>Здравствуйте, Аноним, Вы писали:
А>>Конечно, результат(скелет двухградационного изображения) зависит от пути обхода. Но если сканировать изображение просто построчно, то в большинстве случаев этот алгоритм работает удовлетворительно. А>>Ну а уж выписывать таблицу — просто лень.
T>
. Аналогично для четырёх и более единиц.
