MMX регистры и метод Робертса

[alexis031182]

Нужна помощь в написании кода алгоритма Робертса с использованием регистров MMX. Алгоритм предназначен для обработки изображения с целью выделения краёв различных объектов в кадре. Формула проста: A' = |A - D| + |B - C|. Каждая из букв - значения соседних пикселей по отношению к пикселю A'. Просто на С цикл получается ресурсоёмок. Может ли вообще решение данной задачи с помощью MMX регистров повысить производительность? Заранее спасибо.

[Sancho_s_rancho]

А вам именно этот алгоритм нужен? Если опишите задачу и требования, то может чего подскажу по выделению краев. В свое время я любопытствовал на схожие темы.

[alexis031182]

Честно говоря не обязательно этот. Просто как мне показалось он наиболее простой и соответственно наименее ресурсозатратный. При этом, как мне кажется, весьма эффективен.

Я занялся детектором движения, без наворотов. С методом Робертса он работает великолепно (во всяком случае меня вполне устраивает). Поделив кадр при анализе на мелкие участки (например, 16x16 пикселей) можно к минимуму снизить ложные срабатывания. А выделяемые границы на изображении, после обработки алгоритмом, позволяют в большинстве случаев точно определить наличие движения даже мелких объектов.

Проблема только в том, что при наличии, например, 8-ми видеоканалов с разрешением 512х384 пикс. мой процессор (Core 2 Duo) загружается процентов на 60 (в программе реализована многопоточность, поэтому успевает при двух ядрах). Я уверен, что алгоритм детекции (по сути простой цикл) можно многократно ускорить, но с ассемблером я не в ладах, а потому и возможности процессора, к сожалению, не использую полностью.

Если нужны исходники приложения, то без проблем закину сюда или куда укажете.

[alexis031182]

Вот что примерно получается. Сработка на движение пальцев

[Sancho_s_rancho]

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

[alexis031182]

Исходниками я готов поделиться и без советов. Лицензия GPLv3, ОС Linux

[spectre71]

Немног оптимизации. Должно помочь.

Было:

Код

C++ (Qt)
for(int y = 0; y < sh; ++y)
	{
	for(int x = 0; x < sw; ++x)
		{
		int scale_y = 16 * y;
		int m_scale_y = scale_y + 16;
		int scale_x = 16 * x;
		int m_scale_x = scale_x + 16;
 
		for(int sy = scale_y; sy < m_scale_y; ++sy)
			{
			for(int sx = scale_x; sx < m_scale_x; ++sx)
				{
				int i = sy * width + sx;
				int koef = i + width;
				curbuf[i] = abs(curbuf[i] - curbuf[koef+1]) + abs(curbuf[koef] - curbuf[i+1]);
				if(abs(prevbuf[i] - curbuf[i]) > _sensitive) p.append(i);
			}
		}
 
		if(p.size() > _treshold)
			{mutex.lock(); points.append(p); mutex.unlock(); is_detect = true;}
		p.clear();
	}
}

Стало:

Код

C++ (Qt)
int A,B,C,D;
int i, x, y, sx, sy;
uchar *buf;
uchar *rbuf;
for(y = 0; y < sh; ++y)
    {
    for(x = 0; x < sw; ++x)
        {
        i = (y*width + x)*16;
        for(sy = 16; sy > 0; --sy, i+=width-16)
            {
            for(sx = 16; sx > 0; --sx, ++i)
                {
                buf  = curbuf+i;
                rbuf = buf;
                A = *rbuf;
                D = *(++rbuf);
                C = *(rbuf+=width);
                B = *(++rbuf);
                A = ((A>B)?A-B:B-A) + (C>D)?C-D:D-C;
                *buf = A;
                B = prevbuf[i];
                if(((A>B)?A-B:B-A)  > _sensitive) p.append(i);
            }
        }
 
        if(p.size() > _treshold)
            {mutex.lock(); points.append(p); mutex.unlock(); is_detect = true;}
        p.clear();
    }
}

[spectre71]

И еще один момент

Код:

QList<int> p;
...
if(abs(prevbuf[i] - curbuf[i]) > _sensitive) p.append(i);
...
if(p.size() > _treshold)
	{mutex.lock(); points.append(p); mutex.unlock(); is_detect = true;}
p.clear();
...
...
		QList<int> points = _motion->getPoints();
		for(int i = 0; i < points.size(); ++i)
			{vdata[points.at(i)] = 255;}

Плохая идея использовать QList<int> - большие тормоза.
Насколько я понял это исползуется для отображения маскирования точек ответственных за движение. здесь можно не плохо снизить затраты.

Лучше сделать так:

Код:

int sens[16*16];
int sens_count;

for(y = 0; y < sh; ++y)
    {
    for(x = 0; x < sw; ++x)
        {
        sens_count = 0;
...
...
...
                if(((A>B)?A-B:B-A)  > _sensitive) {sens[sens_count]=i, sens_count++;}
            }
        }
 
        if(sens_count > _treshold)
            {
            mutex.lock(); 
            for(int i=0; i<sens_count; ++i) {points.append(sens[i]);}
            mutex.unlock(); 
            is_detect = true;
        }
    }
}

[Sancho_s_rancho]

/usr/include/libavutil/common.h:154: error: ‘UINT64_C’ was not declared in this scope

Надо видимо куда-то #define __STDC_CONSTANT_MACROS поместить.

[alexis031182]

Немног оптимизации. Должно помочь.
...

Спасибо большое за помощь. Ваш код мне хоть глаза открыл на очевидные вещи. Тем не менее проблема осталась, так как предложенный Вами алгоритм выдаёт несколько иной результат. Первый скриншот - новый код. Второй соответственно старый. Поскольку в детекторе подсчитывается количество сильно отклоняющихся значений точек друг от друга в двух разных кадрах, то получается, что "сработка" детектора в новом коде идёт всегда.

Я попытался первым делом присмотреться к тому месту в коде, где в старом указывается функция abs. Оказалось, что просто буквы расположены не в соответствии с алгоритмом Робертса. Я поменял, и результат получился ближе к старому коду, однако всё же не тот - резко упала чувствительность. Приходится движок "Толерантность" (переменная sensitive) двигать до упора влево на значение 10, чтобы уловить движение объектов на значительном удалении. Но это всё фигня, цифры всё равно относительные. Больше всего меня удивило возросшее потребление процессорного времени. Это тем паче обескураживает, поскольку я используемые Вами в коде методы видел и в других программах и там это определяло увеличение производительности. А у меня получается наоборот. Непонятно...

[alexis031182]

И еще один момент
...
Плохая идея использовать QList<int> - большие тормоза.
Насколько я понял это исползуется для отображения маскирования точек ответственных за движение. здесь можно не плохо снизить затраты.
...

Вы правы, это действительно плохое решение. Я думал вернуться к этой задаче позже, теперь не придётся. Спасибо

[alexis031182]

/usr/include/libavutil/common.h:154: error: ‘UINT64_C’ was not declared in this scope

Надо видимо куда-то #define __STDC_CONSTANT_MACROS поместить.

Может в файл EsperXM2.pro? Там у меня уже один макрос имеется. Тоже у кого-то не хотело компилироваться без его указания.

[spectre71]

Спасибо большое за помощь. Ваш код мне хоть глаза открыл на очевидные вещи. Тем не менее проблема осталась, так как предложенный Вами алгоритм выдаёт несколько иной результат. Первый скриншот - новый код. Второй соответственно старый. Поскольку в детекторе подсчитывается количество сильно отклоняющихся значений точек друг от друга в двух разных кадрах, то получается, что "сработка" детектора в новом коде идёт всегда.

Я попытался первым делом присмотреться к тому месту в коде, где в старом указывается функция abs. Оказалось, что просто буквы расположены не в соответствии с алгоритмом Робертса. Я поменял, и результат получился ближе к старому коду, однако всё же не тот - резко упала чувствительность. Приходится движок "Толерантность" (переменная sensitive) двигать до упора влево на значение 10, чтобы уловить движение объектов на значительном удалении. Но это всё фигня, цифры всё равно относительные. Больше всего меня удивило возросшее потребление процессорного времени. Это тем паче обескураживает, поскольку я используемые Вами в коде методы видел и в других программах и там это определяло увеличение производительности. А у меня получается наоборот. Непонятно...

Разницы в алгоритме нет => разница, будет только в производительности.
Возможно я где-то ошибся, поскольку делал на "коленке", без тестирования (ваш проект у меня не собирается)
Проверь внимательно, видимо где-то ошибка.

[spectre71]

Одну нашел
C = *(rbuf+=width); заменить на C = *(rbuf+=width-1);

Код

C++ (Qt)
int sens[16*16];
int sens_count;
 
int sw = (width / 16);
int sh = (height / 16);
 
bool is_detect = false;
int A,B,C,D;
int i, x, y, sx, sy;
uchar *buf;
uchar *rbuf;
for(y = 0; y < sh; ++y)
    {
    for(x = 0; x < sw; ++x)
        {
        i = (y*width + x)*16;
        sens_count = 0;
        for(sy = 16; sy != 0; --sy, i+=width-16)
            {
            for(sx = 16; sx != 0; --sx, ++i)
                {
                buf  = curbuf+i;
                rbuf = buf;
                A = *rbuf;
                D = *(++rbuf);
                C = *(rbuf+=width-1);
                B = *(++rbuf);
                A = ((A>B)?A-B:B-A) + (C>D)?C-D:D-C;
                *buf = A;
                B = prevbuf[i];
                if(((A>B)?A-B:B-A)  > _sensitive) {sens[sens_count]=i, sens_count++;}
/*
                curbuf[i] = abs(curbuf[i] - curbuf[i+width+1]) + abs(curbuf[i+width] - curbuf[i+1]);
                if(abs(prevbuf[i] - curbuf[i]) > _sensitive) {sens[sens_count]=i, sens_count++;}
*/                
            }
        }
 
        if(sens_count > _treshold)
            {
            mutex.lock(); 
            for(int i=0; i<sens_count; ++i) {points.append(sens[i]);}
            mutex.unlock(); 
            is_detect = true;
        }
    }
}

Скобочку забыл.

[alexis031182]

Одну нашел
C = *(rbuf+=width); заменить на C = *(rbuf+=width-1);
...

Точно, вот теперь полностью идентичный результат:

Код:

buf  = curbuf+i;
rbuf = buf;
A = *rbuf;
C = *(++rbuf);
B = *(rbuf+=(width-1));
D = *(++rbuf);
A = ((A>D)?A-D:D-A) + ((B>C)?B-C:C-B);
*buf = A;
B = prevbuf[i];
if(((B>A)?B-A:A-B)  > _sensitive) p.append(i);

Но нет увеличения производительности. Как я могу точно отмерить используемое проц.время? Я забыл как эта функция называется.