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

Единственное, что мог нарыть по этому поводу: http://ocr.apmath.spbu.ru/algorithms/Detec...eDirection.html
Может есть другие алгоритмы?

Преобразование Хафа (Хоха, Hough) попробуй.
Возможно, лучше будет сгладить изображение и отшарпить, чтобы строчки в линии превратились.

А чем этот алгоритм не устраивает?

Хотя можно наверное попроще:
1. Конвертим в черно-белое изображение (чтоб от шумов избавиться). - можно и не делать
2. Берем самый верхний(нижний)-левый пиксель отличный от цвета фона
3. Берем самы вархний(нижний)-правый пиксель отличный от цвета фона
4. Считаем прямую. Например при помощи параметрического представления (так удобней угол считать)
5. Определяме угол наклона прямой. Это и будет угол наклона листа.

Добавлено @ 14:04
Правда, если будет много шумов, придется какой то фильтра делать или на крайняк проверку по другому краю листа.

Цитата(MBo @ 12.5.2005, 16:36)

Преобразование Хафа (Хоха, Hough) попробуй. Возможно, лучше будет сгладить изображение и отшарпить, чтобы строчки в линии превратились.

У связки: сглаживание -> резкость -> Преобразование Хафа. Не получится ли слишком большая стоимость по времени? Или я ошибаюсь? Дело в том, что у меня изображения размером 150 мегапикселей, и хотелось бы найти более-менее эффективный алгоритм.

Цитата

А чем этот алгоритм не устраивает?

Хотел узнать, может какие есть еще алгоритмы, т.к. у того, на который я привел ссылку, есть некоторые недостатки.

Цитата

Хотя можно наверное попроще: 1. Конвертим в черно-белое изображение (чтоб от шумов избавиться). - можно и не делать 2. Берем самый верхний...

К сожалению этот способ подходит только для изображений с прямоугольным текстовым блоком и без помех (хотя помехи в этом случае можно обходить). В реальности изображения другие.

А если на изображении строки не совсем ровные на краях (из-за аббераций фотаппарата), то преобразование Хафа может выделить эти дуги?

Цитата(Y @ 14.5.2005, 11:01)

К сожалению этот способ подходит только для изображений с прямоугольным текстовым блоком

Почему это? Я же не говорю взять два крайних конца строки, можно взять и некое расстояние, главное чтоб страка была одна, а для простоты можно взять верхнюю/нижнюю строку.

Цитата(Y @ 14.5.2005, 11:01)

В реальности изображения другие.

Какие?

Цитата(Y @ 14.5.2005, 11:01)

А если на изображении строки не совсем ровные на краях (из-за аббераций фотаппарата), то преобразование Хафа может выделить эти дуги?

В зависимости от оптимизации алгоритма преобразования их можно выделить и как дуги и как прямые (допустим по усредненным значениям). К томуже я не думаю, что при таком разрешении радиус дуги будет настолько большим, что бы иметь значение.

Вобще зачем тебе брать именно края возьми середину строки в каком то диапазоне.

>У связки: сглаживание -> резкость -> Преобразование Хафа. Не получится ли слишком большая
стоимость по времени?

сглаживание-резкость - не знаю, понадобится ли. Надо проверять.
Само преобразование Хафа для такого размера картинок довольно дорогое, конечно.
Впрочем, откуда столько точек? А4 в разрешении 1200 dpi? Так для определения наклона такое разрешение не требуется, нужно снимать с меньшим или сжать, если картинки уже имеются. Ведь даже для распознавания в большинстве случаев хватает 300dpi, а 600 - за глаза.

Цитата(MBo @ 14.5.2005, 12:54)

Само преобразование Хафа для такого размера картинок довольно дорогое, конечно.

Для всего документа машина "офигеет" считать.

Если оптимизировать алгоритм, например брать не весь документ целиком, а какую то его часть, то вполне сносно получиться. Даже со всеми сглаживаниями и резкостью.
Главное правильно критерии преобразования задать, а то можно и текст распознать сразу.


Если с применением Хафа, то получиться что то вроде:
1. Выделяем строку целиком путем пробегания по ней квадратом с размером по гоизантали в полтора раза больше чем самый длинный символ и по высоте на 7-10% меньше высоты строчного символа. Если сверху /снизу этого квадрата есть явный проблеск, то смещаемся в противоположную сторону. И закрашиваем эту строку чисто черным или проводим прямую 30% от высоты символов.
2. Дальше берем нашего Хафа и считаем параметрическое уравнение прямой.
3. Из него выделяем угол наклона прямой.

Только будут проблемы с символами не являющимися буквами: !";:*()_+=- и т.д.
Надо думать

Цитата

Почему это? Я же не говорю взять два крайних конца строки, можно взять и некое расстояние, главное чтоб страка была одна, а для простоты можно взять верхнюю/нижнюю строку.

Может получится так, что первая точка будет взята из одной строки, а вторая - из другой. Или может подсчитать за строчку, к примеру, колонтитул или помехи.

Цитата

В реальности изображения другие... Какие?

Вот пример фрагмента реального изображения, которое я хочу обрабатывать:

Здесь присутствуют вертикальные, горизонтальные прямые и строчки по краям (здесь не видно) расходятся чуток.

Цитата(MBo @ 14.5.2005, 11:54)

Впрочем, откуда столько точек? А4 в разрешении 1200 dpi?

Да нет - метр на пол метра в 300 dpi - это газета 1890 года, у них большой формат. Фотографируется при помощи офигенно дорогого устройства, которое выдает 10000*15000 пикселей.

Цитата

Выделяем строку целиком путем пробегания по ней квадратом с размером по гоизантали в полтора раза больше чем самый длинный символ и по высоте на 7-10% меньше высоты строчного символа

Проблема в том, что часто встречаются и большие символы и обрамляющие прямоугольники. Надо как-то в среднем все это брать...

Цитата(Y @ 14.5.2005, 16:53)

метр на пол метра

Ну так сделай привайв в котором будешь выбирать кусок страницы наиболее подходящий для определения, узнаешь на какой угол повернут кусок и поворачиваешь на минус такой угол весь лист.

Цитата

выбирать кусок страницы наиболее подходящий для определения

А как можно определить, что такой-то кусок наиболее подходит для вычисления угла?

Вообще я хочу случайным образом (или по шаблону) выбрать несколько областей и найти там угол наклона, затем вычислить среднее - на него и повернуть все изображение.

Рамки присутствуют на каждом листе?
Если да, то преобразование надо делать именно их. ИМХО удобней.
Если нет, то вероятнее всего надо выбирать прямоугольные блоки текста, и справа и слева они ровненькие.

Цитата

Рамки присутствуют на каждом листе?

Нет, не на каждом...

Цитата

Если нет, то вероятнее всего надо выбирать прямоугольные блоки текста, и справа и слева они ровненькие.

А по какому критерию их можно выбирать, т.е. как лучше определить, что такой-то блок является текстом?

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

Цитата(MBo @ 12.5.2005, 16:36)

Преобразование Хафа (Хоха, Hough) попробуй. Возможно, лучше будет сгладить изображение и отшарпить, чтобы строчки в линии превратились.

Согласен. Можно текст также уменьшить, чтобы буквы стали почти точечными.

Цитата(Graf @ 17.5.2005, 13:55)

Согласен. Можно текст также уменьшить, чтобы буквы стали почти точечными.

Да вот как раз уменьшать то ему и не рекомендуется, ибо на таких размерах исходного листа могут быть скожения в разную строноу (в зависимости от поверхности на которой он лежит и удаленности кусков проверяемого места друг от друга, от линзы в фотике и т.д.). Скорее надо не по строкам смотреть, а по бокам текстовых блоков, их правые и левые границы достаточно ровыне, что бы по ним можно было провести прямую. Или искать рамки (если они есть) и по ним проводит прямые.

Это сообщение отредактировал(а) ~FoX~ - 17.5.2005, 14:06