Алгоритм распознования образов, основанный на Хеминговой мере близости. c++/Qt Опции

[Andrewshkovskii]

Суть такая : есть эталонная картинка с символом, пользователь в поле ввода, рисует свой символ, после чего, программа должна распознать введенный символ и указать процент вероятности.
вот примерно вот как Здесь или тут.
Интерфейс я прикрутил, рисовалку сделал. Но есть одна мне не понятная штука , вот первый шаг алгоритма :

Шаг 1. [Преобразование символов] Шаблоны распознаваемых M
символов разбивают на растровые картинки размером 30х30. В том случае,
если на ячейку накладывается символ, ей приписывают единицу, в
противном случае - ноль (см. рис. 2).

Допустим, у меня есть QPixmap размером 231х231, из него я получаю QImage(что бы можно было получить доступ к пикселам) такого же размера. Но тут встает вопрос..как делить картинку на растры 30х30? В смысле, определить цвет-то то я смогу (для того, что бы узнать, находиться символ в растре или нет) , а вот как поделить и отрисовать пиксельную сетку, при учете, что изображение шириной и высотой 231 будет всего 7 полных квадратов 30х30...
Прикладываю методичку к посту..

[volvo]

Я бы сделал так: берем QPicture размером 240*240 (чтоб на 30 нацело делилось), тогда каждый "пиксель" распознаваемого изображения будет отображаться на таком QPicture участком 8*8, правда? Это 64 реальных пикселя. Ну, и считай, сколько пикселей черного цвета попало в эту область из 64-х возможных. Больше половины - значит в матрицу заносишь 1... Меньше - значит ноль... Ну, или какое другое соотношение возьми, не обязательно 50/50.

На Дельфи программка-то написана из методички

[Andrewshkovskii]

Ну не QPicture ты имел ввиду,а QImage, наверное? Ну хорошо, а как быть с отрисовкой сетки?ну не самой сетки (Её с помощью QBrush::CrossPattern можно отрисовать),а с "квадратиками-пикселями", т.е в каких координатах из отрисовывать(проще говоря - выявить соответствие). ?

[volvo]

т.е в каких координатах из отрисовывать

Бррр... Мы по-моему с тобой на разных языках говорим... Чего тебе отрисовывать-то надо? Сделал 2 одинаковых изображения, одно (которое означено на первом скриншоте) "Сетка пикселей эталонов символов" нарезал квадратиками 8*8. Что тебе еще отрисовывать?

А, ну да, пиксель изображения с координатами (x, y) принадлежит ячейке - квадратику, связанному с матрицей, как угодно назови, суть от этого не меняется - с индексами [x/8, y/8]

[Andrewshkovskii]

Я понимаю, что начинаю опять тебя злить..Но я пытаюсь разобраться
Под отрисовкой, я имел ввиду сетку пикселей, там же не одинаковое изображение а преобразованное в некую бинарную матрицу, где 0 - это белый квадратик, 1 - черный.
Так вот, имеет оно(сетка пикселей) , такой же размер, что и исходное изображение(эталон).
Берем последовательно квадраты от этого изображения ,стороны которого равны QImage.width()/30.
Проверяем их на наличия черных пикселей и если процент заполнения >= порогу, тогда мы рисуем этот пиксел на изображении Сетка пикселей. Я правильно понимаю?
Но вот как мне соотнести координата квадрата который прошел валидацию и координату того пикселя, который отображать будет этот квадрат?
Или я не так думаю?Может сначала надо построить матрицу, и от матрицы плясать?

[volvo]

В общем, рисует пользователь изображение на QImage. Потом делаешь что угодно, накладываешь сверху сетку, это твои проблемы, как ты реализуешь это, главное - то, что нарисовал пользователь - измениться не должно, QImage неприкасаем!!! А матрица сама строится так:

    // image = это тот самый QImage, в котором картинка, нарисованная пользователем
    int matrix[30][30] = {0};
    const int value = 32; // на выбор, можешь сделать и больше

    for(int i = 0; i < image.width(); i++)
        for(int j = 0; j < image.height(); j++)
            matrix[i / 8][j / 8] += (image.pixel(i, j) == Qt::black) ? 1 : 0;

    for(int i = 0; i < 30; i++)
        for(int j = 0; j < 30; j++)
        {
            matrix[i][j] /= value;
        }

Все, в таблице либо 0 либо 1 в зависимости от того, сколько пикселей попало в соотв. область рисунка... А уже после построения матрицы ее раскладываешь в массив, и так далее.

[Andrewshkovskii]

Ну я вообще говорил про то, что как строить пиксельную сетку из матрицы ?
Умножать индекс элемента на 8, и это будет координата пикселя?
Только вот у меня проблема в том, что цвета какие-то странные дает pixel(int x,int y) у QImage,а точнее, их там более 30 разных возвращает.. Ведь pixel() возвращает QRgb, что есть тайпдеф для unsigned int , и почему-то их там много очень получается. а должно , по-логике , быть 2..
И из-за этого матрица будет вся в нулях.
Рисую-то я вот так

//Ручка.
    //drawPen.setColor(Qt::black);
    //drawPen.setCapStyle(Qt::RoundCap);
    //drawPen.setBrush(Qt::SolidPattern);
    //drawPen.setWidth(17);
    //drawPen.setStyle(Qt::SolidLine);
    //drawPen.setJoinStyle(Qt::RoundJoin);
bool recognizer::eventFilter(QObject *o, QEvent *e)
{
//что бы не наследоваться от Qlabel, и не придумывать свою рисовалку, установил фильтер событий да место рисования (QPixmap в QLabel)
    QMouseEvent me = *(static_cast<QMouseEvent*> (e));
    if (o == ui->inputSymbolFiled)
    {
        if (me.type()== QEvent::MouseButtonPress)
           {
               if(me.button() == Qt::LeftButton)
                {
                   painter->begin(inputSymbolPixmap);
                   painter->setRenderHint(QPainter::HighQualityAntialiasing,true);
                   painter->setPen(drawPen);
                   painter->drawLine(me.pos(),me.pos());
                   painter->end();
                   lastpoint=me.pos();
                   ui->inputSymbolFiled->setPixmap(*inputSymbolPixmap);
                   return true;
                }
           }else
               if (me.type() == QEvent::MouseMove)
               {
                 painter->begin(inputSymbolPixmap);
                 painter->setRenderHint(QPainter::HighQualityAntialiasing,true);
                 painter->setPen(drawPen);
                 painter->drawLine(lastpoint,me.pos());
                 painter->end();
                 lastpoint=me.pos();
                 ui->inputSymbolFiled->setPixmap(*inputSymbolPixmap);
                 return true;
                }
    }
    return QWidget::eventFilter(o,e);
}

Upd : Добавил исходники...

Сообщение отредактировано: Andrewshkovskii - 8.12.2009 19:53

[Andrewshkovskii]

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

Вот код, как я это в модельку все "пихаю." и вывожу ..
:

void recognizer::getEtalonArray(QImage image)
{
//    qDebug() << image.pixel(0,0) << " " << image.pixel(100,100);
    QString str;
    QStringList arrayList;
    int h=image.height();
    int w=image.width();
    int matrix[30][30]={0};
    int value = 32;
    //получим пиксели..
    for(int i=0;i<w;++i)
        for(int j=0;j<h;++j)
            matrix[i/8][j/8]+=(image.pixel(i,j)==4278190080 /*Qt::black*/)? 1 : 0;//определим цвет, 1 если черный, 0 если нет
    for(int i = 0; i < 30; i++)
    {
        for(int j = 0; j < 30; j++)
        {
            matrix[i][j] /= value;//если делиться value -значит прошел проверку на value% наполнения
            cout << matrix[i][j] << " ";
            str.append(QString::number(matrix[i][j])); // число в строку засунем
            etalonArray.push_back(matrix[i][j]);//etalonArray - qVector <int>
        }
        cout << "\n";
        arrayList << str;//строку в стринг лист
        str.clear();
    }
    etalonArrayModel.setStringList(arrayList);//установим стринг лист для модельки..
}

вот что для буквы 'А'



Т.е повернуто на 90 градусов в лево и 2йка откуда-то берутся

Сообщение отредактировано: volvo - 23.11.2010 13:44

[Andrewshkovskii]

Почему появилась 2ой - понял, из-за

matrix[i/8][j/8]+=(image.pixel(i,j)

, и видимо он проходит по каким-то координатам дважды.. а вот почему перевернуто..

[volvo]

Т.е повернуто на 90 градусов в лево

Это я стормозил... Если i это ширина, а j - высота, то должно быть:

    for(int i = 0; i < image.width(); i++)
        for(int j = 0; j < image.height(); j++)
            matrix[j / 8][i / 8] += (image.pixel(i, j) == Qt::black) ? 1 : 0;

, индексы местами попутал... А двойка - потому как 64/32 = 2. Увеличь value до 33, тогда не будет ничего кроме 0 и 1.

[Andrewshkovskii]

хех..Понятно..Спасибо.но вот мой основной вопрос, который снедает меня словно старческий недуг

Ну я вообще говорил про то, что как строить пиксельную сетку из матрицы ?
Умножать индекс элемента на 8, и это будет координата пикселя?

я правильно понял, про умножение?

[volvo]

Почему ты рассматриваешь только один пиксель? Если тебе надо из матрицы получить изображение в натуральную величину (30*30 пикселей) - то ты знаешь, что надо делать: индекс = координата пикселя. Если же надо из 30*30 получить 240*240, то элементу с индексами [i][j] соответствуют пиксели
(8*i .. 8*i + 7, 8*j .. 8*j + 7)

[Andrewshkovskii]

А почему.. +7, тоесть это какая-то переменная от 0 до 7, я так понимаю?Извини, что достаю уже, но я пытаюсь разобраться,а не в глупую переписывать..

[volvo]

Ну, потому, что если индекс = 0, то у нас пикселы 0 .. 7, index = 1 -> пикселы 8 .. 15, и так далее. То есть, фактически от index*8 до (index+1)*8 - 1. Открой скобки, что получишь?

[Andrewshkovskii]

Хм..ну верно, ага, спасибо!

[volvo]

Так... Прочитал я, как ты прокомментировал код из сообщения №8, и что-то мне кажется, что ты не до конца понимаешь, что там происходит...

Итак, вот тот же фрагмент, но с моими комментариями:

    // почему ты избавляешься от константности - непонятно. У меня наоборот
    // выработалась привычка: все, что только можно объявлять со спецификатором const
    const int value = 33;
    
    for(int i=0;i<w;++i)
        for(int j=0;j<h;++j)
            // проверяем каждый пиксель на черный цвет, и если да, то добавляем
            // к ячейке матрицы, к которой принадлежит этот пиксель, единицу. Другими
	    // словами - здесь идет подсчет черных пикселей в каждой из областей 8*8
            matrix[j/8][i/8]+=(image.pixel(i, j) == QColor(Qt::black).rgb())? 1 : 0;
    for(int i = 0; i < 30; i++)
    {
        for(int j = 0; j < 30; j++)
        {
            // А теперь, устанавливаем ячейку в 0, если черных пикселов в соотв. области
            // было найдено меньше, чем задано в value, иначе устанавливаем в 1
            // Эту строку (с делением) можно заменить на:
            // matrix[i][j] = (matrix[i][j] > value) ? 1 : 0;
            // или, что одно и то же:
            // if(matrix[i][j] > value) matrix[i][j] = 1; else matrix[i][j] = 0;
            matrix[i][j] /= value;
            cout << matrix[i][j] << " ";
            str.append(QString::number(matrix[i][j])); // число в строку
            etalonArray.push_back(matrix[i][j]); // etalonArray - qVector <int>		
        }
        arrayList << str;
        str.clear();
    }

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

[Andrewshkovskii]

Ну единственное что было не понятно, так это почему цвет не определялся, не думал, что так можно преобразовать. Спасибо...А про деление было очевидно, комментарий просто не так записал. Дописал распознавание, забавно..