интересует как можно сделать следующее:
имеем бинарное изображение
также задано квадратное окно размером 2^N пикселей по X и Y
нужно определить существует ли область на изображении, в которую полностью попадает это окно.
ну к примеру нарисована окружность радиуса 10, т.е. окно размером 2^3 = 8 полностью может поместиться внутрь круга. Т.е. ответ — TRUE
Хотяб с чего начать???

PS: тупым перебором работает.

Здравствуйте, piAnd, Вы писали:

A>интересует как можно сделать следующее:
A>имеем бинарное изображение
A>также задано квадратное окно размером 2^N пикселей по X и Y
A>нужно определить существует ли область на изображении, в которую полностью попадает это окно.
A>ну к примеру нарисована окружность радиуса 10, т.е. окно размером 2^3 = 8 полностью может поместиться внутрь круга. Т.е. ответ — TRUE
A>Хотяб с чего начать???
A>PS: тупым перебором работает.

Дано: битмап B[w,h] и размер вписываемого прямоугольника p,q (в случае квадрата p==q).

Заведём табличный предикат L(x,y), который отвечает: есть ли слева от (x,y) не менее p белых точек.
Таблица строится за один проход по B (по строкам, в строках слева направо).

Заведём табличный предикат T(x,y), который отвечает: есть ли сверху от (x,y) не менее q белых полосок шириной p — то есть, не менее белых (true) точек в таблице L.
Таблица строится за один проход по L (по столбцам, в столбцах сверху вниз).

Как только найдём белую (true) точку в T, это и будет ответ: (x,y) соответствует правому нижнему углу.

Причём можно заметить, что элементарно можно переиспользовать память битмапа B — поскольку для нахождения L(x,y) нужен только B[x,y] и аккумулятор, значение L(x,y) можно записать прямо в B[x,y]. Затем то же самое сделать с T.

Итого, это займёт O(w*h) + O((w-p+1)*h) + O((w-p+1)*(h-q+1))
где последнее слагаемое — если мы захотем найти все положения окна.

Здравствуйте, Кодт, Вы писали:

[skip]
К>Итого, это займёт O(w*h) + O((w-p+1)*h) + O((w-p+1)*(h-q+1))
К>где последнее слагаемое — если мы захотем найти все положения окна.
Спась!
Ваш вариант сделал, но терь стало казаться, что можно и за O(w*h).
Только доп память несколько должна возрасти, если не использовать тот же битмеп

Здравствуйте, piAnd, Вы писали:

A>Ваш вариант сделал, но терь стало казаться, что можно и за O(w*h).

Ты имеешь в виду — за один проход?

A>Только доп память несколько должна возрасти, если не использовать тот же битмеп

Да в общем ничего сложного. Заведём массив вертикальных аккумуляторов.

bool B[w][h];
int p,q;

/////////////////////

int al; // аккумулятор для L
bool Lxy; // значение L(x,y) - нам не нужно заполнять таблицу, достаточно следить за текущим значением

int at[w] = {0}; // аккумуляторы для T (по столбцам)
bool Txy; // текущее значение T(x,y) - смотри ниже

for(int y=0; y<h; ++y)
{
  al=0;
  for(int x=0; x<w; ++x)
  {
    al = B[x][y] ? al+1 : 0;
    Lxy = al >= p;

    at[x] = Lxy ? at[x]+1 : 0;
    Txy = at[x] >= q;

    // теперь можно вывести это значение
    if(Txy) cout << "square is (" << x-p+1 << "," << y-q+1 << ") - (" << x << "," << y << ")" << endl;
    // и/или запомнить его
    T[x][y] = Txy;
    // и/или завершить обработку
    if(Txy) return;
  }
}

Итого: два прохода и разрушение битмапа, или один проход и O(min(w,h)) дополнительной памяти.

Здравствуйте, Кодт, Вы писали:

К>Итого: два прохода и разрушение битмапа, или один проход и O(min(w,h)) дополнительной памяти.
Теперь пытаюсь сделать немного обратную задачу: найти такой размер окна (размер 2^N), при котором на бинарном изображении можно будет вписать максимум таких окон.
Пока что только написал приближенный анализ подозрительных квадрантов.
А именно:
Разбиваем бин. изображение (для простоты W и H у него будут кратны 2^Nmax) на квадраты — строим дерево. Верхний узел — все изображение целиком, у верхнего узла 4 дочерних, размером W/2 H/2, потом у каждого из подузлов W/4 H/4 итд. Т.е. делим каждый раз каждый подузел на 4 равных.
Вычисляем последовательно средние яркости всех узлов, начиная с нижнего уровня.
Считаем на каждом уровне разбиения количество подузлов, имеющих среднюю яркость >= K — некий порог.
Т.е. тот уровень, где будет больше таких квадратов, и будет искомым размером окна.

Пока не ясно, какой именно выбирать порог K, и вообще будет ли это корректным методом...

A>Считаем на каждом уровне разбиения количество подузлов, имеющих среднюю яркость >= K — некий порог.
A>Т.е. тот уровень, где будет больше таких квадратов, и будет искомым размером окна.
Да, еще одно условие пропустил: если четыре смежных квадрата имеют порог >= K, то переходим на следующий уровень. Т.е. чтобы не выбрался самый высокий уровень разбиения

Здравствуйте, piAnd, Вы писали:

A>Здравствуйте, Кодт, Вы писали:

К>>Итого: два прохода и разрушение битмапа, или один проход и O(min(w,h)) дополнительной памяти.
A>Теперь пытаюсь сделать немного обратную задачу: найти такой размер окна (размер 2^N), при котором на бинарном изображении можно будет вписать максимум таких окон.

Ну, при N=0 размер окна будет 1*1, и очевидно, таких окон (белых пикселов) будет больше, чем любых других прямоугольников

А если стоит задача замостить битмап квадратиками (чую, что это имеет отношение к сжатию изображений ), то надо подумать.

Здравствуйте, Кодт, Вы писали:

К>А если стоит задача замостить битмап квадратиками (чую, что это имеет отношение к сжатию изображений )
Не, задача тут такая: дано какое-то бин. изображение (больше всего на нем будет контуров некой ширины — она варьирует в некоторых пределах)
Надо найти векторные ломаные линии, которые примерно повторяют эти контура или иные объекты, которые там находятся.