[PHP][HELP] Скелетолизация изображения

[draliokero]

http://www.mathworks.co.jp/matlabcentral/fx_files/25865/1/skeleton.jpg

Помогите пожалуйста реализовать бинаризацию и скелетонизацию изображения с помощью GD.
Вот, что нарыл по скелетонизации http://dic.academic.ru/dic.nsf/ruwiki/683052 .

[draliokero]

Что касается бинаризации: нашел AS сценарий, из него выдернул принцип
<?php
$im = imagecreatefrompng("php.png");
$width = imagesx($im);
$height = imagesy($im);
for ($y = 0; $y < $height; $y++) {
for ($x = 0; $x < $width; $x++) {
if (imagecolorat($im, $x , $y) <= 0x7FFFFF) imagesetpixel($im, $x, $y, 0x000000);
else imagesetpixel($im, $x, $y, 0xFFFFFF);
}
}

header('Content-type: image/png');
imagepng($im);

[Gifts]

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

[draliokero]

Gifts, сразу в поиск полез, как думаете этим вопрос решится http://bubble.ro/How_to_check_if_an_image_is_grayscale_in_PHP.html ?


На Google Code нашел С++ проект (http://www.google.ru/codesearch/p?#FOOG9CoE38c/lib/MorphologicalFilter.h) с фильтром скелетонизации (алгоритм Zhang Suen PDF на Google Docs (http://tinyurl.com/yc6qwzc) (Редирект с tinyurl.com, потому что парсер режет [forbidden link])) переписал, получилось вот это:

<?php
$im = imagecreatefrompng("php.png");
$width = imagesx($im);
$height = imagesy($im);
for ($y = 0; $y < $height; $y++) {
for ($x = 0; $x < $width; $x++) {
if (imagecolorat($im, $x , $y) <= 0x7FFFFF) imagesetpixel($im, $x, $y, 0x000000);
else imagesetpixel($im, $x, $y, 0xFFFFFF);
}
}
// Функция скелетонизации бинарного изображения
function zhang_suen_thinning_iteration($im, $condition_switch)
{
global $width, $height;

$running = false;
for($y = 1; $y < $height - 1; $y++) {
for($x = 1; $x < $width - 1; $x++) {
$p1 = imagecolorat($im, $x, $y) > 0 ? 1 : 0;
if ($p1 > 0) {
$p2 = imagecolorat($im, $x, $y - 1) > 0 ? 1 : 0;
$p3 = imagecolorat($im, $x + 1, $y - 1) > 0 ? 1 : 0;
$p4 = imagecolorat($im, $x + 1, $y) > 0 ? 1 : 0;
$p5 = imagecolorat($im, $x + 1, $y + 1) > 0 ? 1 : 0;
$p6 = imagecolorat($im, $x, $y + 1) > 0 ? 1 : 0;
$p7 = imagecolorat($im, $x - 1, $y + 1) > 0 ? 1 : 0;
$p8 = imagecolorat($im, $x - 1, $y) > 0 ? 1 : 0;
$p9 = imagecolorat($im, $x - 1, $y - 1) > 0 ? 1 : 0;
$connectivity =
($p2 == 0 && $p3 == 1 ? 1 : 0) +
($p3 == 0 && $p4 == 1 ? 1 : 0) +
($p4 == 0 && $p5 == 1 ? 1 : 0) +
($p5 == 0 && $p6 == 1 ? 1 : 0) +
($p6 == 0 && $p7 == 1 ? 1 : 0) +
($p7 == 0 && $p8 == 1 ? 1 : 0) +
($p8 == 0 && $p9 == 1 ? 1 : 0) +
($p9 == 0 && $p2 == 1 ? 1 : 0);
$non_zero_neighbors = $p2 + $p3 + $p4 + $p5 + $p6 + $p7 + $p8 + $p9;

if (2 <= $non_zero_neighbors && $non_zero_neighbors <= 6 && $connectivity == 1) {
if ($condition_switch == true) {
if (($p2 * $p4 * $p6 == 0) && ($p4 * $p6 * $p8 == 0)) {
imagesetpixel($im, $x, $y, 0x000000);
$running = true;
}
} else {
if (($p2 * $p4 * $p8 == 0) && ($p2 * $p6 * $p8 == 0)) {
imagesetpixel($im, $x, $y, 0x000000);
$running = true;
}
}
}
}
}
}
return $running;
}

zhang_suen_thinning_iteration($im, true);

header('Content-type: image/png');
imagepng($im);

Но работает как-то криво, с точностью на оборот – происходит не скелетонизации, а ожирение o_O

Есть на Java, Perl, C++, Pas куски из OCR модулей,
вот один из них: ZhangSuen.java (http://www.google.ru/codesearch/p?#Cl0RMnxdRug/portfolio/accode/MapDetector.zip%7CBUaDlG16dWs/src/ZhangSuen.java)
Вроде все понятно, может кто-нибудь поможет тогда исправить ошибку и доделать?

[Gifts]

draliokero Изображение мы должны изменять только после завершения итерации. Из-за того что мы насилуем imageGD постоянно - код получается очень медленным, по хорошему - лучше при бинаризации создавать двумерный массив, а потом уже раскрашивать обратно. Работающий код, без оптимизации:

<?php

set_time_limit(0);


$im = imagecreatefrompng("skeleton.png");
$width = imagesx($im);
$height = imagesy($im);
for ($y = 0; $y < $height; $y++) {
for ($x = 0; $x < $width; $x++) {
if (imagecolorat($im, $x , $y) <= 0x7FFFFF) imagesetpixel($im, $x, $y, 0x000000);
else imagesetpixel($im, $x, $y, 0xFFFFFF);
}
}
// Функция скелетонизации бинарного изображения
function zhang_suen_thinning_iteration($condition_switch)
{
global $width, $height, $im;

$im2 = imagecreatetruecolor($width, $height);

$running = false;
for($y = 1; $y < $height - 1; $y++) {
for($x = 1; $x < $width - 1; $x++) {
$p1 = imagecolorat($im, $x, $y) > 0 ? 1 : 0;

if ($p1 > 0) {
imagesetpixel($im2,$x,$y,0xFFFFFF);
$p2 = imagecolorat($im, $x, $y - 1) > 0 ? 1 : 0;
$p3 = imagecolorat($im, $x + 1, $y - 1) > 0 ? 1 : 0;
$p4 = imagecolorat($im, $x + 1, $y) > 0 ? 1 : 0;
$p5 = imagecolorat($im, $x + 1, $y + 1) > 0 ? 1 : 0;
$p6 = imagecolorat($im, $x, $y + 1) > 0 ? 1 : 0;
$p7 = imagecolorat($im, $x - 1, $y + 1) > 0 ? 1 : 0;
$p8 = imagecolorat($im, $x - 1, $y) > 0 ? 1 : 0;
$p9 = imagecolorat($im, $x - 1, $y - 1) > 0 ? 1 : 0;
$connectivity =
($p2 == 0 && $p3 == 1 ? 1 : 0) +
($p3 == 0 && $p4 == 1 ? 1 : 0) +
($p4 == 0 && $p5 == 1 ? 1 : 0) +
($p5 == 0 && $p6 == 1 ? 1 : 0) +
($p6 == 0 && $p7 == 1 ? 1 : 0) +
($p7 == 0 && $p8 == 1 ? 1 : 0) +
($p8 == 0 && $p9 == 1 ? 1 : 0) +
($p9 == 0 && $p2 == 1 ? 1 : 0);
$non_zero_neighbors = $p2 + $p3 + $p4 + $p5 + $p6 + $p7 + $p8 + $p9;

if (2 <= $non_zero_neighbors && $non_zero_neighbors <= 6 && $connectivity == 1) {
if ($condition_switch == true) {
if (($p2 * $p4 * $p6 == 0) && ($p4 * $p6 * $p8 == 0)) {
imagesetpixel($im2, $x, $y, 0x000000);
$running = true;
}
} else {
if (($p2 * $p4 * $p8 == 0) && ($p2 * $p6 * $p8 == 0)) {
imagesetpixel($im2, $x, $y, 0x000000);
$running = true;
}
}
}
} else imagesetpixel($im2, $x, $y, 0x000000);
}
}
imagecopy($im,$im2,0,0,0,0,$width,$height);
return $running;
}
$flag = true;$count = 0;

//zhang_suen_thinning_iteration($im, $flag);
while (zhang_suen_thinning_iteration($im, $flag = !$flag) && $count++ < 60) {}

header('Content-type: image/png');
imagepng($im);

За 60 итераций получаем такое изображение из левой верхней картинки первого поста (С увеличением чиасла итераций треугольник конечно пропадет, но достаточно не быстро):
http://i057.radikal.ru/1003/43/e77905cee0b3.png

З.Ы. получить ЧБ изображение можно через среднее арифметическое трех каналов цветного (что, кстати, и будет яркостью пиксела)

[Omegа]

Решил попробовать - вот что получилось =D
http://s60.radikal.ru/i169/1003/1f/711976dc89ef.png
<?php
header('Content-type: image/png');
$im = imagecreatefrompng('FILE.PNG');
$im0 = imagecreatefrompng('FILE.PNG');
$w = imagesx($im);
$h = imagesy($im);
for($y=0;$y<$h;$y++) {
for($x=0;$x<$w;$x++) {
if((imagecolorat($im, $x, $y) & 0xFF)>(256/2)) {
imagesetpixel($im,$x,$y,0xFFFFFF);
imagesetpixel($im0,$x,$y,0xFFFFFF);
} else {
imagesetpixel($im,$x,$y,0x000000);
imagesetpixel($im0,$x,$y,0x000000);
}
}
}
$open = false;
for($y=0;$y<$h;$y++) {
for($x=0;$x<$w;$x++) {
if($open!=true) {
if(imagecolorat($im,$x,$y)==0xFFFFFF) {
$open=true;
$start = $x;
}
} else {
if(imagecolorat($im,$x,$y)==0x000000) {
$open=false;
$x0 = $x-1;
$c = round(($start+$x0)/2);
imageline($im,$start,$y,($c-1),$y,0x000000);
imageline($im,($c+1),$y,$x0,$y,0x000000);
}
}
}
}
$open=false;
for($x=0;$x<$w;$x++) {
for($y=0;$y<$h;$y++) {
if($open!=true) {
if(imagecolorat($im0,$x,$y)==0xFFFFFF) {
$open=true;
$start = $y;
}
} else {
if(imagecolorat($im0,$x,$y)==0x000000) {
$open=false;
$y0 = $y-1;
$c = round(($start+$y0)/2);
imagesetpixel($im,$x,$c,0xFFFFFF);
}
}
}
}
imagepng($im);
imagedestroy($im);
?>