Я хотел бы попытался подсказать, как можно улучшить этот код, но для этого желательно на словах объяснить, что он должен делать - код не прозрачен и практически не читается, к сожалению. Подскажите, если задача не потеряла актуальность.
Задача состоит в следующем: на вход функции поступает полутоновое (серое) 8-ми битовое изображение Image размерами Height и Width. Типичный пример изображения - звёзды на фоне космического пространства. Необходимо разбить изображение на непересекающиеся пронумерованные области в соответствии с двуми порогами: Thr1 - порог фона (нижний порог); Thr2 - порог объектов (верхний порог). Те пикселы, которые находятся между порогами Thr1 и Thr2 (т. е. Thr1 < PixelValue < Thr2) являются переходными и могут быть отнесены к любой ближайшей наиболее близкой (с точки зрения близости значений пикселов) области. На выходе функции в массиве AreasNumbBuf для каждого пиксела сохраняется номер области, к которой принадлежит этот пиксель (это может быть или космическое пространство или звезда или НЛО
).
Алгоритм с последней публикации был достаточно сильно изменён, поэтому привожу его заново. Но несмотря на значительную оптимизацию его быстродействие на процессоре DM642 оставляет желать лучшего. Например для изображения размерами 640*480 он выполняется порядка 0.6 сек, что неприемлемо. Планировалось, что он должен выполняться порядка 20 мсек (50 Гц).
#include <stdlib.h>
//Максимальное кол-во областей в изображении
#define MAX_AREAS 1000
#define min(x,y) (x<y?x:y)
//Структура хранения информации об областях
typedef struct TAreaInfo
{
//Номер кластера
short iNumber;
//Номер моды
short iMode;
//Счётчик мощности моды
int iCount;
} TAreaInfo;
//Счётчики количества областей в изображении и в контейнере
static int iAreasCount=0, iAreasInfoCount=0;
//Ограниченный массив структур описателей областей!!!
static TAreaInfo AreasInfo[MAX_AREAS+1];
//Таблица соответствия значений пикселов модам гистограммы
static int ModeNumb4Pix[256];
//Функция создания новой области
static inline int AddNewAreaInfo(const int iModeNumb)
{
// if (iAreasInfoCount>=MAX_AREAS) return -1;
iAreasCount++;
AreasInfo[iAreasInfoCount].iMode=iModeNumb;
AreasInfo[iAreasInfoCount].iNumber=-1;
AreasInfo[iAreasInfoCount].iCount=0;
return iAreasInfoCount++;
}
/*!\brief Разбиение изображения на непересекающиеся области
* \param Image - исходное изображение
* \param Height - высота изображения
* \param Width - ширина изображение
* \param AreasNumbBuf - буфер результата, отражающий номера областей каждого из пикселов
* \param Thr1 - нижний порог
* \param Thr2 - верхний порог
* \result Количество непересекающихся областей в изображении
*/
int SplitImage2Areas(
register unsigned char ** __restrict Image,
register int Height, register int Width,
register int ** __restrict AreasNumbBuf,
register int Thr1, register int Thr2)
{
//Изображение последовательно просматривается по строкам
//для отнесения каждого пиксела к определённой области
//Вычисление площади, занимаемой каждой областью и модой
register int iPrevAreaNumbL=-1; //Номер области предыдущей левой точки
register int iPrevModeNumbL=-1; //Номер моды предыдущей левой точки
register int iPrevAreaNumbU=-1; //Номер области предыдущей верхней точки
register int iPrevModeNumbU=-1; //Номер моды предыдущей верхней точки
register int iPrevAreaNumbUL=-1; //Номер области предыдущей верхней левой точки
register int iPrevModeNumbUL=-1; //Номер моды предыдущей верхней левой точки
register int iPrevAreaNumbUR=-1; //Номер области предыдущей верхней правой точки
register int iPrevModeNumbUR=-1; //Номер моды предыдущей верхней правой точки
//Временные переменные
register int i, y, x, iSrcIndex, iDstIndex, iDelta, iTmp;
register int iCurrPixel, iCurrAreaNumb, iCurrModeNumb;
register TAreaInfo * __restrict pSrcObj, * __restrict pDstObj, * __restrict pTmpObj;
//Проверка корректности входных параметров
if ((Image==0)||(Width<=0)||(Height<=0)||(ModeNumb4Pix==0)||(AreasNumbBuf==0)) return -1;
//Формирование таблицы мод пикселей
for (i=0; i<256; i++)
{
if (i<Thr1)
ModeNumb4Pix[i]=0;
else if (i>=Thr2)
ModeNumb4Pix[i]=1;
else
ModeNumb4Pix[i]=-1;
}
//Обнуление счётчиков кол-ва областей
iAreasCount=iAreasInfoCount=0;
//Обработка верхней левой точки изображения
iCurrPixel=Image[0][0];
iCurrModeNumb=ModeNumb4Pix[iCurrPixel];
if (iCurrModeNumb<0)
{
//Сканирование зигзагом окрестных точек для
//выявления ближайшей с установленной модой
iDelta=min(Width,Height);
for (i=1; i<iDelta; i++)
{
iSrcIndex=-1;
for (y=i, x=0; y>=0; y--, x++)
{
iDstIndex=Image[y][x];
iTmp=ModeNumb4Pix[iDstIndex];
if (iTmp<0) continue;
iDstIndex=abs(iDstIndex-iCurrPixel);
if ((iSrcIndex<0)||(iSrcIndex>iDstIndex))
{
iSrcIndex=iDstIndex;
iCurrModeNumb=iTmp;
}
}
//Нашли подходящую точку - выход из поиска
if (iCurrModeNumb>=0) break;
}
//Если точек нет, то нулевая мода
if (iCurrModeNumb<0) iCurrModeNumb=0;
}
iCurrAreaNumb=AddNewAreaInfo(iCurrModeNumb);
AreasNumbBuf[0][0]=iCurrAreaNumb;
//Обработка первой верхней строки изображения,
//начиная со второго пиксела строки
for (x=1; x<Width; x++)
{
//Запоминание номера области и моды для левой точки
iPrevAreaNumbL=iCurrAreaNumb;
iPrevModeNumbL=iCurrModeNumb;
//Номер моды текущей точки
iCurrModeNumb=ModeNumb4Pix[Image[0][x]];
//В зависимости от наличия моды
if (iCurrModeNumb<0) {
iCurrModeNumb=iPrevModeNumbL;
iCurrAreaNumb=iPrevAreaNumbL;
}
else if (iCurrModeNumb==iPrevModeNumbL) {
iCurrAreaNumb=iPrevAreaNumbL;
}
else {
//Добавление новой области
iCurrAreaNumb=AddNewAreaInfo(iCurrModeNumb);
}
//Установка номера области текущей точки
AreasNumbBuf[0][x] = iCurrAreaNumb;
//Инкремент счётчика площади, занимаемой областью
AreasInfo[iCurrAreaNumb].iCount++;
}
//Декремент ширины изображения для увеличения скорости обработки
Width--;
//Цикл по всем точкам изображения
for (y=1; y<Height; y++)
{
//Установка начального значения для верхней левой точки
iPrevAreaNumbUL=AreasNumbBuf[y-1][0];
iPrevModeNumbUL=AreasInfo[iPrevAreaNumbUL].iMode;
//Установка начального значения для верхней точки
iPrevAreaNumbU=AreasNumbBuf[y-1][1];
iPrevModeNumbU=AreasInfo[iPrevAreaNumbU].iMode;
//Значение яркости первого пикселя строки
iCurrPixel=Image[y][0];
//Значение моды первого пикселя строки
iPrevModeNumbL=ModeNumb4Pix[iCurrPixel];
//В зависимости от признака переходности пиксела
if (iPrevModeNumbL<0) {
if (abs(iCurrPixel-Image[y-1][0])<abs(iCurrPixel-Image[y-1][1]))
{
iPrevModeNumbL=iPrevModeNumbUL;
iPrevAreaNumbL=iPrevAreaNumbUL;
}
else
{
iPrevModeNumbL=iPrevModeNumbU;
iPrevAreaNumbL=iPrevAreaNumbU;
}
}
else if (iPrevModeNumbL==iPrevModeNumbUL)
iPrevAreaNumbL=iPrevAreaNumbUL; //Верхняя левая точка
else if (iPrevModeNumbL==iPrevModeNumbU)
iPrevAreaNumbL=iPrevAreaNumbU; //Верхняя точка
else {
//Добавление новой области
iPrevAreaNumbL=AddNewAreaInfo(iPrevModeNumbL);
}
//Установка номера области первого пиксела строки
AreasNumbBuf[y][0] = iPrevAreaNumbL;
//Инкремент счётчика площади, занимаемой областью
AreasInfo[iPrevAreaNumbL].iCount++;
//Обработка очередной строки изображения
for (x=1; x<Width; x++)
{
//Определение параметров верхней правой точки
iPrevAreaNumbUR=AreasNumbBuf[y-1][x+1];
iPrevModeNumbUR=AreasInfo[iPrevAreaNumbUR].iMode;
//Значение яркости текущего пикселя
iCurrPixel=Image[y][x];
//Номер моды текущей точки
iCurrModeNumb=ModeNumb4Pix[iCurrPixel];
//В зависимости от того является ли точка переходной
if (iCurrModeNumb<0)
{
//Текущая точка является переходной к любой области
//Перебор всех точек окрестности и выбор наиболее близкой области
//Левая точка
iDelta=abs(Image[y][x-1]-iCurrPixel);
iCurrAreaNumb=iPrevAreaNumbL;
iCurrModeNumb=iPrevModeNumbL;
//Верхняя точка
iTmp=abs(Image[y-1][x]-iCurrPixel);
if (iDelta>iTmp) {
iDelta=iTmp;
iCurrAreaNumb=iPrevAreaNumbU;
iCurrModeNumb=iPrevModeNumbU;
}
//Верхняя левая точка
iTmp=abs(Image[y-1][x-1]-iCurrPixel);
if (iDelta>iTmp) {
iDelta=iTmp;
iCurrAreaNumb=iPrevAreaNumbUL;
iCurrModeNumb=iPrevModeNumbUL;
}
//Верхняя правая точка
iTmp=abs(Image[y-1][x+1]-iCurrPixel);
if (iDelta>iTmp) {
iDelta=iTmp;
iCurrAreaNumb=iPrevAreaNumbUR;
iCurrModeNumb=iPrevModeNumbUR;
}
}
//Эта точка не является переходной ни к одной из мод
//Просмотр всех соседних уже размеченных ранее точек
//для возможного определения номера области текущей точки
else if (iCurrModeNumb==iPrevModeNumbL)
iCurrAreaNumb=iPrevAreaNumbL; //Левая точка
else if (iCurrModeNumb==iPrevModeNumbUL)
iCurrAreaNumb=iPrevAreaNumbUL; //Верхняя левая точка
else if (iCurrModeNumb==iPrevModeNumbU)
iCurrAreaNumb=iPrevAreaNumbU; //Верхняя точка
else if (iCurrModeNumb==iPrevModeNumbUR)
iCurrAreaNumb=iPrevAreaNumbUR; //Верхняя правая точка
else {
//Добавление новой области
iCurrAreaNumb=AddNewAreaInfo(iCurrModeNumb);
}
//Установка номера области текущей точки
AreasNumbBuf[y][x] = iCurrAreaNumb;
//Объект области в дереве
pSrcObj=&AreasInfo[iCurrAreaNumb];
//Инкремент счётчика площади, занимаемой областью
pSrcObj->iCount++;
//Сканирование верхней правой точки для добавления её в список соседних областей
if ((iCurrModeNumb==iPrevModeNumbUR)&&(iCurrAreaNumb!=iPrevAreaNumbUR))
{
//Объект области предыдущей ссылки
pDstObj=&AreasInfo[iPrevAreaNumbUR];
//Всего четыре возможных варианта
if (pSrcObj->iNumber<0)
{
if (pDstObj->iNumber>=0)
{
//Только добавляется ссылка на ссылочную область
pSrcObj->iNumber=pDstObj->iNumber;
//Декремент кол-ва областей
iAreasCount--;
}
else
{
//Обе области являются доменными
iTmp=min(iCurrAreaNumb,iPrevAreaNumbUR);
pSrcObj->iNumber=iTmp;
pDstObj->iNumber=iTmp;
//Декремент кол-ва областей
iAreasCount--;
}
}
else //if (pSrcObj->iNumber>=0)
{
if (pDstObj->iNumber<0)
{
//Только добавляется ссылка на ссылочную область
pDstObj->iNumber=pSrcObj->iNumber;
//Декремент кол-ва областей
iAreasCount--;
}
else
{
iSrcIndex=pSrcObj->iNumber;
iDstIndex=pDstObj->iNumber;
if (iSrcIndex!=iDstIndex)
{
//Это самый трудоёмкий случай.
//Но, к счастью, самый редкий!
//Необходимо объединить две области
for (i=0; i<iAreasInfoCount; i++)
{
pTmpObj=&AreasInfo[i];
if (pTmpObj->iNumber==iSrcIndex)
pTmpObj->iNumber=iDstIndex;
}
//Декремент кол-ва областей
iAreasCount--;
}
}
}
}
//Запоминание номера области и моды для левой точки
iPrevAreaNumbL=iCurrAreaNumb;
iPrevModeNumbL=iCurrModeNumb;
//Запоминание номера области и моды для верхней левой точки
iPrevAreaNumbUL=iPrevAreaNumbU;
iPrevModeNumbUL=iPrevModeNumbU;
//Запоминание номера области и моды для верхней точки
iPrevAreaNumbU=iPrevAreaNumbUR;
iPrevModeNumbU=iPrevModeNumbUR;
}
//Значение яркости последнего пикселя строки
iCurrPixel=Image[y][Width];
//Значение моды последнего пикселя строки
iCurrModeNumb=ModeNumb4Pix[iCurrPixel];
//В зависимости от наличия моды
if (iCurrModeNumb<0) {
//Левая точка
iDelta=abs(Image[y][x-1]-iCurrPixel);
iCurrAreaNumb=iPrevAreaNumbL;
iCurrModeNumb=iPrevModeNumbL;
//Верхняя левая точка
iTmp=abs(Image[y-1][x-1]-iCurrPixel);
if (iDelta>iTmp) {
iDelta=iTmp;
iCurrAreaNumb=iPrevAreaNumbUL;
iCurrModeNumb=iPrevModeNumbUL;
}
//Верхняя точка
iTmp=abs(Image[y-1][x]-iCurrPixel);
if (iDelta>iTmp) {
iDelta=iTmp;
iCurrAreaNumb=iPrevAreaNumbU;
iCurrModeNumb=iPrevModeNumbU;
}
}
else if (iCurrModeNumb==iPrevModeNumbL)
iCurrAreaNumb=iPrevAreaNumbL; //Левая точка
else if (iCurrModeNumb==iPrevModeNumbUL)
iCurrAreaNumb=iPrevAreaNumbUL; //Верхняя левая точка
else if (iCurrModeNumb==iPrevModeNumbU)
iCurrAreaNumb=iPrevAreaNumbU; //Верхняя правая точка
else {
//Добавление новой области
iCurrAreaNumb=AddNewAreaInfo(iCurrModeNumb);
}
//Установка номера области последнего пикселя строки
AreasNumbBuf[y][Width] = iCurrAreaNumb;
//Инкремент счётчика площади, занимаемой областью
AreasInfo[iCurrAreaNumb].iCount++;
}
//Восстановление исходной ширины изображения
Width++;
//Упорядочивание переадресации областей (именно здесь)!!!!!
for (i=0; i<iAreasInfoCount; i++)
{
pTmpObj=&AreasInfo[i];
iTmp=pTmpObj->iNumber;
if (iTmp<0)
{
//Это независимый кластер
pTmpObj->iNumber=i;
}
else if (iTmp!=i)
{
//Это не кластерная область
AreasInfo[iTmp].iCount+=pTmpObj->iCount;
//Обнуление счётчика - выключение области
pTmpObj->iCount=0;
}
}
//Могут оставаться независимые области с индексами больше iAreasCount
for (iDstIndex=0, iSrcIndex=iAreasCount; iSrcIndex<iAreasInfoCount; iSrcIndex++)
{
//Если эта область уже переадресована - все нормально
pSrcObj=&AreasInfo[iSrcIndex];
if ((pSrcObj==NULL)||(pSrcObj->iCount==0)) continue;
//Поиск индекса для переадресации
for (; iDstIndex<iAreasCount; iDstIndex++)
{
pDstObj=&AreasInfo[iDstIndex];
if ((pDstObj!=NULL)&&(pDstObj->iCount==0)) break;
}
//Сохранение указателя на моду
pDstObj->iMode=pSrcObj->iMode;
//Коррекция счётчиков мощности областей
pDstObj->iCount=pSrcObj->iCount;
pSrcObj->iCount=0;
//Установка ссылки данной области на переадресованную
pSrcObj->iNumber=iDstIndex;
//Замена всех ссылок на эту область!!!!!!!!
for (i=0; i<iAreasInfoCount; i++)
{
pTmpObj=&AreasInfo[i];
if (pTmpObj->iNumber==iSrcIndex) pTmpObj->iNumber=iDstIndex;
}
}
//Переписывание индексов областей на новые переназначенные
for (y=0; y<Height; y++) for (x=0; x<Width; x++)
{
iTmp=AreasNumbBuf[y][x];
iTmp=AreasInfo[iTmp].iNumber;
AreasNumbBuf[y][x]=iTmp;
}
return iAreasCount;
}
Лишние NOP в ассемблерном коде
Oct 23 2007, 11:54
).
