Помогите пожалуйста решить такую проблему:
имеем:
1. черно-белое изображение
2. размеры квадратной области в пикселах
необходимо:
получить координаты пустых областей на изображении, куда входит область
надеюсь внятно вопрос задал ))
Огромная благодарность всем кто ответит, ну очень надо
Здравствуйте, kwsergio, Вы писали:
K>Приветсвую, All!!!
K>Помогите пожалуйста решить такую проблему: K>имеем: K>1. черно-белое изображение K>2. размеры квадратной области в пикселах K>необходимо: K>получить координаты пустых областей на изображении, куда входит область
K>надеюсь внятно вопрос задал ))
K>Огромная благодарность всем кто ответит, ну очень надо
Допустим размер этой квадратной области — K. Введем две функции. Первая — g(x, y) — количество подряд идущих "пустых" пикселов начиная от (x,y) если смотреть вверх. Считается следующим образом:
g(x, y) = 0, если (x, y) — не пустой
g(x, y) = g(x, y — 1) + 1, в противном случае
Вторая функция — f(x, y) — максимальная ширина "пустого" прямоугольника, с высотой K, и правым нижним углом в клетке (x, y).
f(x,y) = 0, если g(x, y) < K
f(x,y) = f(x — 1, y) + 1, если g(x, y) >= K
На выход идут все квадраты с левым нижним уголом в клетках (x, y), где f(x, y) >= K
Начальные значения: g(-1, x) = 0. f(x, -1) = 0, если считать, что строки и столбцы нумеруются с нуля.
Для оптимизации по памями можно при вычислении хранить соответствующих таблицах только 2 последних строки. Сложность пропорциональна размеру изображения.
K>Помогите пожалуйста решить такую проблему: K>имеем: K>1. черно-белое изображение
размеры изображения эквивалентны примерно формату A0 отсканированному с разрешением 300dpi (т.е. очень большое)
K>2. размеры квадратной области в пикселах
ошибся немного прямоугольную
K>необходимо: K>получить координаты пустых областей на изображении, куда входит область
Здравствуйте, kwsergio, Вы писали:
K>>Помогите пожалуйста решить такую проблему: K>>имеем: K>>1. черно-белое изображение K>размеры изображения эквивалентны примерно формату A0 отсканированному с разрешением 300dpi (т.е. очень большое)
K>>2. размеры квадратной области в пикселах
K>ошибся немного прямоугольную
K>>необходимо: K>>получить координаты пустых областей на изображении, куда входит область
Тогда то же самое, что я писал выше, только K будем считать высотой прямоугольника, а на выход пойдут прямоугольники с левым нижним углом (x, y), где f(x, y) >= M, где M — его ширина. В этом алгоритме все изображение всего лишь просматривается один раз, а сделать меньше операций, чем просмотреть каждый пиксель один раз, я думаю, не получится
Выше я писал, что можно хранить 2 строчки. На самом деле для вычисления g достаточно хранить одну строку и в ней же пересчитывать, а f вообще можно сократить до одной переменной, потому что для вычисления f(x, y), нужно лишь предыдущее значение: f(x, y — 1). Т.е. что касается памяти, нужен всего 1 массив размера, равного ширине изображения.
Здравствуйте, twisted_mind, Вы писали:
_> Тогда то же самое, что я писал выше, только K будем считать высотой прямоугольника, а на выход пойдут прямоугольники с левым нижним углом (x, y), где f(x, y) >= M, где M — его ширина. В этом алгоритме все изображение всего лишь просматривается один раз, а сделать меньше операций, чем просмотреть каждый пиксель один раз, я думаю, не получится _>Выше я писал, что можно хранить 2 строчки. На самом деле для вычисления g достаточно хранить одну строку и в ней же пересчитывать, а f вообще можно сократить до одной переменной, потому что для вычисления f(x, y), нужно лишь предыдущее значение: f(x, y — 1). Т.е. что касается памяти, нужен всего 1 массив размера, равного ширине изображения.
