СПОСОБ ОБНАРУЖЕНИЯ ТЕКСТА В РАСТРОВОМ ИЗОБРАЖЕНИИ (ВАРИАНТЫ) И СПОСОБ ВЫЯВЛЕНИЯ СПАМА, СОДЕРЖАЩЕГО РАСТРОВЫЕ ИЗОБРАЖЕНИЯ Российский патент 2009 года по МПК G06K9/36 

Область изобретения

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

Уровень техники

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

Известен способ многоэтапного анализа информации растрового изображения (патент РФ №2234734, опубл. 20.08.2004), в котором анализ осуществляют в два этапа: сначала - этап предварительного распознавания с применением менее точных методов распознавания, а затем - этап точного распознавания тех объектов, которые остались нераспознанными после первого этапа. На первом этапе сегментируют изображение на области, таблицы, фрагменты текста, строки, слова, символы, а на втором этапе уточняют эту сегментацию с учетом дополнительной информации, полученной на первом этапе.

Сходный принцип реализован и в способе анализа растрового изображения (патент РФ №2251151, опубл. 27.04.2005), когда все возможные в изображении объекты разделяют на уровни, отличающиеся степенью сложности (символ, слово, строка, абзац, таблица, область). Затем устанавливают принадлежность каждого объекта тому или иному уровню и устанавливают связи между объектами разных уровней и одного уровня сложности. Дальше выдвигают гипотезу о наличии свойств того или иного объекта и проверяют эту гипотезу, корректируя свойства объектов, связанных с анализируемым.

В обоих этих способах фактически осуществляют распознавание элементов текста, имеющегося в изображении, что усложняет и удлиняет обработку поступающих по сети связи изображений.

В заявке США №2004/0221062 (опубл. 04.11.2004) описан способ, в котором для идентификации контентных признаков осуществляется предварительная визуализация принятого сообщения в первом формате, после чего это сообщение преобразуется в чисто символьное сообщение во втором формате, чтобы до фильтрации текста исключить, скажем, декоративные компоненты. Здесь также осуществляется распознавание текста.

Распознавание текста осуществляется и в патенте США №7171046 (опубл. 30.01.2007).

В заявке США №2005/0281455 (опубл. 22.12.2005) раскрыт способ различения текста и картинки в изображении с помощью нейронной сети. В этом способе изображение разделяется на данные изображения в уровнях серого для блоков изображения. Обученная нейронная сеть обрабатывает непрерывные пикселы, генерируя доверенное значение текста для каждого из пикселов и получая наибольшее доверенное значение текста, которое сравнивается с порогом для определения статуса блока изображения. К недостаткам можно отнести проблемы переобучения нейронных сетей или необходимость тратить время на обучение такой сети.

В патенте США №6470094 (опубл. 22.10.2002) раскрыта обобщенная локализация текстов в изображениях, когда в изображении в качестве символа выделяются совокупности смежных пикселов, которые, в свою очередь, объединяются в слова.

Наиболее близким к заявленному изобретению можно считать способ обнаружения текста в видеоизображениях (патент США №6608930, опубл. 19.08.2003). В этом способе в видеоизображениях сначала выделяют один цвет, что дает контрастное изображение, которое еще усиливают с помощью маски 3×3. Кроме того, медианной фильтрацией удаляют случайный шум из изображения («соль и перец»). Обнаруживают край изображения, причем используют адаптивный порог (если у пиксела все соседи краевые, порог для текущего пиксела понижается). Затем осуществляют (в кадре или подкадрах) краевую фильтрацию, в которой удаляют из анализа те области, где текста нет или где он не может быть надежно обнаружен. Далее объединяют в единый символ краевые пикселы, находящие друг от друга на расстоянии меньше заданного. При этом определяются границы символа по осям координат и количество пикселов, и все это сравнивается с заранее заданными порогами. Потом процессор определяет, лежат ли соседние символы в одной строке. Определяется среднее значение серого для выделенного текста и сравнивается с уровнями белого и черного, чтобы назначить фон белым, а текст черным.

Этот способ, однако, имеет ограниченные возможности вследствие того, что требует достаточно много вычислений.

Раскрытие изобретения

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

Указанный технический результат достигается в первом объекте настоящего изобретения за счет обеспечения способа обнаружения текста в растровом двухцветном изображении, заключающегося в том, что: распознают фоновый цвет в растровом двухцветном изображении; находят границы замкнутого контура, описанного вокруг каждого из отдельных рисунков слитных пикселов цвета, отличного от фонового цвета, и запоминают его координаты; сравнивают размеры каждого из замкнутых контуров с первыми заранее заданными пределами; исключают из дальнейшего рассмотрения те замкнутые контуры, размеры которых не попадают в первые заранее заданные пределы; интерпретируют каждый из оставшихся замкнутых контуров как контур текстового символа; находят предполагаемые строки текстовых символов по всем замкнутым контурам, интерпретированным как контуры текстовых символов; разбивают найденные предполагаемые строки текстовых символов на наборы, интерпретируемые как вероятные слова; сравнивают количества контуров, интерпретированных как контуры текстовых символов, в каждом из вероятных слов со вторыми заранее заданными пределами; исключают из дальнейшего рассмотрения те вероятные слова, в которых количество контуров, интерпретированных как контуры текстовых символов, не попадает во вторые заранее заданные пределы; сравнивают оставшиеся количества вероятных слов в каждой предполагаемой строке с третьими заранее заданными пределами; исключают из дальнейшего рассмотрения те из предполагаемых строк, в которых количество вероятных слов не попадает в третьи заранее заданные пределы; подсчитывают в оставшемся изображении количество пикселов упомянутого цвета, отличного от фонового цвета; вычисляют отношение подсчитанного количества пикселов упомянутого цвета, отличного от фонового цвета, к ранее подсчитанному количеству пикселов того же цвета в исходном двухцветном изображении; если вычисленное в предыдущей операции отношение больше четвертого заранее заданного предела, то считают факт наличия оставшихся предполагаемых строк с вероятными словами обнаружением текста в растровом изображении.

Указанный технический результат достигается во втором объекте настоящего изобретения за счет обеспечения способа обнаружения текста в растровом многоцветном изображении, заключающегося в том, что: приводят растровое многоцветное изображение к растровому двухцветному изображению; распознают фоновый цвет в растровом двухцветном изображении; находят границы замкнутого контура, описанного вокруг каждого из отдельных рисунков слитных пикселов цвета, отличного от фонового цвета, и запоминают его координаты; сравнивают размеры каждого из замкнутых контуров с первыми заранее заданными пределами; исключают из дальнейшего рассмотрения те замкнутые контуры, размеры которых не попадают в первые заранее заданные пределы; интерпретируют каждый из оставшихся замкнутых контуров как контур текстового символа; находят предполагаемые строки текстовых символов по всем замкнутым контурам, интерпретированным как контуры текстовых символов; разбивают найденные предполагаемые строки текстовых символов на наборы, интерпретируемые как вероятные слова; сравнивают количества контуров, интерпретированных как контуры текстовых символов, в каждом из вероятных слов со вторыми заранее заданными пределами; исключают из дальнейшего рассмотрения те вероятные слова, в которых количество контуров, интерпретированных как контуры текстовых символов, не попадает во вторые заранее заданные пределы; сравнивают оставшиеся количества вероятных слов в каждой предполагаемой строке с третьими заранее заданными пределами; исключают из дальнейшего рассмотрения те из предполагаемых строк, в которых количество вероятных слов не попадает в третьи заранее заданные пределы; подсчитывают в оставшемся изображении количество пикселов упомянутого цвета, отличного от фонового цвета; вычисляют отношение подсчитанного количества пикселов упомянутого цвета, отличного от фонового цвета, к ранее подсчитанному количеству пикселов того же цвета в исходном двухцветном изображении; если вычисленное в предыдущей операции отношение больше четвертого заранее заданного предела, то считают факт наличия оставшихся предполагаемых строк с вероятными словами обнаружением текста в растровом изображении.

В данном способе приведение к растровому двухцветному изображению осуществляют с помощью следующих операций: преобразуют цвета растрового многоцветного изображения в оттенки серого; строят для преобразованного изображения гистограмму частот оттенков серого; находят центр тяжести построенной гистограммы; задают порог черно-белого на уровне 3/4 от первого использованного цвета до найденного центра тяжести.

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

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

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

Еще одна особенность обоих данных способов состоит в том, что нахождение предполагаемых строк текстовых символов осуществляют с помощью следующих операций: выбирают очередной контур текстового символа, не участвующий в какой-либо из предполагаемых строк; осуществляют нанизывание строки слева и справа от выбранного контура текстового символа; производят объединение левой и правой подстрок для формирования новой строки. Нужно добавить, что продолжение нанизывания строки продолжается именно с того символа, который был сейчас выбран следующим.

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

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

Указанный технический результат достигается в третьем объекте настоящего изобретения за счет обеспечения способа выявления спама, содержащего растровое изображение, заключающийся в том, что: осуществляют обнаружение текста в растровом изображении по одному из вышеприведенных способов; формируют сигнатуру обнаруженного текста; сравнивают сформированную сигнатуру с эталонными шаблонами спама, хранящимися в базе данных; считают принятое электронное сообщение спамом при совпадении с заранее заданной точностью сформированной сигнатуры с, по меньшей мере, одним эталонным шаблоном спама.

При этом сигнатуру формируют на основе длин слов, оставшихся после сравнения с вторыми заранее заданными пределами, и количества предполагаемых строк, оставшихся после сравнения с третьими заранее заданными пределами.

Краткое описание чертежей

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

Фиг.1 является блок-схемой алгоритма, иллюстрирующего реализацию способа обнаружения текста в растровом многоцветном изображении по настоящему изобретению.

Фиг.2 является примером спама в виде изображения, которое обычно находится внутри спам-писем.

Фиг.3 иллюстрирует шаг приведения многоцветного изображения на фиг.2 к двухцветному.

Фиг.4 иллюстрирует вырисовывание контуров вокруг вероятных символов с фиг.3.

Фиг.5 иллюстрирует процесс создания контура вокруг вероятного символа.

Фиг.6 иллюстрирует оставшиеся контуры на фиг.4 после удаления слишком маленьких и слишком больших контуров (а также удаления прочего шума).

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

Фиг.8 иллюстрирует процесс разделения оставшихся контуров на слова.

Фиг.9 иллюстрирует процесс разделения текстовых строк на слова.

Фиг.10 является блок-схемой алгоритма, показывающего подробности получения решения о наличии спама по алгоритму на фиг.1.

Фиг.11 является блок-схемой алгоритма по преобразованию цветного изображения к двухцветному.

Фиг.12 иллюстрирует гистограмму частот оттенков серого при выполнении алгоритма по преобразованию цветного изображения к двухцветному.

Фиг.13 является блок-схемой алгоритма по выбору одного из двух цветов как фонового.

Фиг.14 является блок-схемой алгоритма, показывающего подробности выполнения шага нахождения предполагаемых строк.

Фиг.15-17 иллюстрируют процесс выполнения шага нахождения предполагаемых строк.

Фиг.18 является блок-схемой алгоритма разбиения предполагаемых строк на вероятные слова.

Фиг.19-20 являются блок-схемами алгоритмов по нанизыванию символов в строку как с левой стороны, так и с правой.

Фиг.21-56 иллюстрируют вышеописанный процесс в деталях и с дополнительными комментариями.

Фиг.57 является дополнительной иллюстрацией алгоритма по нанизыванию символов в строку как с левой стороны, так и с правой.

Описание предпочтительных вариантов осуществления

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

Настоящее изобретение предназначено для использования в любом вычислительном средстве, способном воспринимать и обрабатывать как текстовые данные, так и данные изображений. Это могут быть серверы, персональные компьютеры (ПК), персональные цифровые ассистенты (PDA), переносные компьютеры (ноутбуки), компактные компьютеры (лаптопы) и любые иные существующие или разрабатываемые, а также будущие вычислительные устройства, подключаемые к компьютерной сети. Настоящее изобретение наиболее просто реализуется посредством соответствующего программного обеспечения (software), однако его можно также при желании воплотить и в аппаратном (hardware) или программно-аппаратном (firmware) виде. В случае программной реализации настоящего изобретения в память вычислительного средства (пусть это будет для наглядности компьютер) заносятся соответствующие программные коды, под управлением которых в ходе их считывания процессор компьютера осуществляет действия того или иного способа по настоящему изобретению. На фиг.7 изображена примерная схема компьютерной системы, на которой может быть реализовано настоящее изобретение.

На фиг.1 показана блок-схема алгоритма для осуществления способа обнаружения текста в растровом многоцветном изображении по настоящему изобретению. На вход компьютера поступает растровое изображение. В случае векторного изображения его необходимо предварительно преобразовать в растровое, что условно показано пунктирным блоком 101. Это можно сделать с помощью соответствующей библиотеки. На растре рисуется рисунок с заданными размерами и масштабом, после чего растр готов для использования.

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

Для приведения многоцветного растрового изображения к двухцветному растровому изображению (фиг.11) сначала на шаге 1101 преобразуют цвета растрового многоцветного изображения в оттенки серого. На фиг.2 приведен пример многоцветного изображения, а на фиг.3 это же изображение показано в оттенках серого.

Далее на шаге 1102 строят для преобразованного изображения гистограмму частот оттенков серого. Пример такой гистограммы приведен на фиг.12. Затем находят центр тяжести построенной гистограммы и определяют его абсциссу Х_цт на шаге 1103 (см. фиг.11). После этого на шаге 1104 находят абсциссу X₁ первого уровня серого этой гистограммы.

Наконец, на шаге 1105 задают порог черно-белого на уровне расстояния X₁+³/₄(Х_цт-X₁) от первого уровня серого до найденного центра тяжести.

Операция шага 102 (на фиг.1) может осуществляться и иными средствами, например, цвета темнее RGB (127, 127, 127) становятся черными, светлее - белыми.

После приведения на шаге 102 многоцветного растрового изображения к двухцветному растровому изображению на шаге 103А распознают фоновый цвет в этом растровом двухцветном изображении. Эта процедура иллюстрируется блок-схемой на фиг.13.

Для распознавания фонового цвета сначала на шагах 1301 и 1302 подсчитывают количество пикселов каждого из двух цветов растрового двухцветного изображения. Подсчитанные количества пикселов обоих цветов сравнивают друг с другом на шаге 1303 и на шаге 1304 выбирают в качестве фонового цвета тот из этих двух цветов, который имеет большее количество подсчитанных пикселов.

Операцию 103А (на фиг.1) распознавания фона можно осуществлять и иными средствами, например, взяв цветом фона цвет, преобладающий на крае рисунка.

После определения фонового цвета на шаге 104А находят границы замкнутого контура, описанного вокруг каждого из отдельных рисунков слитных пикселов цвета, отличного от фонового цвета, и запоминают его координаты. Этот шаг иллюстрируется на фиг.4 и 5.

Когда на шаге 104А определены границы (и координаты) всех замкнутых контуров вокруг каждого отдельного рисунка слитных пикселов «нефонового» цвета, на шаге 105 сравнивают размеры каждого из этих замкнутых контуров с первыми заранее заданными пределами. Эти пределы устанавливают эмпирически в процессе анализа имеющихся образцов изображений с текстом. В том случае, когда размеры какого-либо замкнутого контура не попадают в эти первые заранее заданные пределы, данный замкнутый контур исключают из дальнейшего рассмотрения (шаг 106). На шаге 105А проверяют наличие еще нерассмотренных контуров. Если остался хотя бы один, то алгоритм возвращается к шагу 105. Каждый из оставшихся замкнутых контуров интерпретируют как контур текстового символа и продолжают процесс обработки.

На шаге 107 находят предполагаемые строки текстовых символов по всем замкнутым контурам, интерпретированным как контуры текстовых символов. Эта процедура иллюстрируется на фиг.6. Более подробно шаг 107 проиллюстрирован на блок-схеме на фиг.14.

В процессе нахождения предполагаемых строк сначала на шаге 1401 выбирают следующий свободный контур текстового символа, не участвующий в какой-либо из предполагаемых строк. На шаге 1402 происходит нанизывание левой подстроки, после чего происходит нанизывание правой подстроки на шаге 1403. После получения левой и правой подстрок происходит их объединение на шаге 1404. Получив новую строку, алгоритм проверяет, есть ли оставшиеся свободные контуры для построения новых строк. Если таковые есть, то алгоритм снова переходит к шагу 1401. В противном случае алгоритм заканчивает свою работу. На фиг.15-17 иллюстрируется результат нанизывания строки слева и справа.

Более подробно шаги 1402 и 1403 рассмотрены на фиг.19 и 20. Переход в левую текстовую подстроку подробно представлен на фиг.19. Вначале вычисляют верхнюю и нижнюю границу контура на этапе 1901. Для этого увеличивают высоту контура текущего символа на 1/3 вверх и на 1/3 вниз. На шаге 1902 находят контур с координатой y центра внутри заданных границ и ближайшей координатой х от левой стороны текущего контура. При этом этот контур не должен являться частью какой-либо текстовой строки. Если на этапе 1903 контур найден, то далее на этапе 1904 он добавляется к началу подстроки и устанавливается как текущий на этапе 1905. Фиг.20 иллюстрирует тот же самый алгоритм, но для правой стороны.

На шаге 108 после нахождения предполагаемых строк текстовых символов их разбивают на наборы, интерпретируемые как вероятные слова. Эта процедура более подробно показана на фиг.8.

Для того чтобы разбить предполагаемые строки на вероятные слова, сначала на шаге 1801 находят в каждой из предполагаемых строк расстояния между всеми парами соседних контуров текстовых символов. После этого на шаге 1802 строят гистограмму частот найденных расстояний. На шаге 1803 находят абсциссу Х_1м первого максимума построенной гистограммы и выбирают Х_1м в качестве самого частого расстояния. Затем на шаге 1804 сравнивают в каждой из предполагаемых строк расстояния между всеми соседними парами контуров текстовых символов с двойным выбранным самым частым расстоянием Х_1м. Если сравниваемое расстояние превышает удвоенное самое частое расстояние Х_1м, то на шаге 1805 интерпретируют это расстояние как разрыв между вероятными словами. На шаге 1806 проверяют наличие оставшихся пар соседних контуров, и если еще остались непроверенные пары контуров, то алгоритм возвращается к шагу 1804. Результат выполнения этой процедуры проиллюстрирован на фиг.9.

После того, как на шаге 108 (на фиг.1) предполагаемые строки разбиты (разделены) на вероятные слова, на шаге 109 сравнивают количества упомянутых контуров, интерпретированных как контуры текстовых символов, в каждом из вероятных слов со вторыми заранее заданными пределами. Эти вторые заранее заданные пределы определяются, как и первые заранее заданные пределы, эмпирически и могут составлять, например, минимум 2, максимум 16. Если количество замкнутых контуров, интерпретированных как контуры текстовых символов, какого-либо вероятного слова не попадает во вторые заранее заданные пределы, то на шаге 110 это вероятное слово исключают из дальнейшего рассмотрения. На шаге 109А проверяют наличие еще нерассмотренных слов. Если осталось хотя бы одно слово, то алгоритм возвращается к шагу 109. Затем на шаге 111 сравнивают количества оставшихся вероятных слов в каждой предполагаемой строке с третьими заранее заданными пределами, которые задаются эмпирически, как и уже упоминавшиеся первые и вторые заранее заданные пределы. Если количество вероятных слов в какой-либо предполагаемой строке не попадает в третьи заранее заданные пределы, эту предполагаемую строку на шаге 112 исключают из дальнейшего рассмотрения. На шаге 111 A проверяют наличие еще нерассмотренных строк. Если осталась хотя бы одна строка, то алгоритм возвращается к шагу 111. Далее на этапе 113 считают количество черных пикселов (N₂) внутри оставшихся контуров, которые представляют символы или буквы. Далее вычисляется отношение количества черных пикселов (N₂) внутри оставшихся контуров к количеству пикселов (N₁), отличных от цвета фона. При условии, что это отношение попадает в четвертый заданный предел, то принимают решение о том, что анализируемое растровое изображение содержит текст.

На фиг.1 показаны еще несколько операций, которые стоит рассмотреть более подробно.

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

Кроме того, после распознавания на шаге 103В фонового цвета подсчитывают в исходном изображении количество N₁ пикселов цвета, отличного от фонового. После же выполнения шагов 110 и 112 по исключению вероятных слов, в которых количество контуров текстовых символов не попадает во вторые заранее заданные пределы, и предполагаемых строк, в которых количество вероятных слов не попадает в третьи заранее заданные пределы, на шаге 113 подсчитывают в оставшемся изображении количество N₂ пикселов цвета, отличного от фонового цвета. Затем вычисляют отношение подсчитанного на шаге 114 количества N₂ пикселов «нефонового» цвета к подсчитанному на шаге 103В количеству N₁ пикселов того же цвета в исходном двухцветном изображении и сравнивают (шаг 114) это отношение N₂/N₁ с четвертым заранее заданным (эмпирически, как и предыдущие) пределом. Если это отношение оказывается меньше четвертого заранее заданного предела, анализируемое изображение исключают из дальнейшего рассмотрения (шаг 115). В противном случае делается вывод о наличии текста в этом изображении (шаг 116).

Случай анализа двухцветного растрового изображения отличается от рассмотренного случая анализа многоцветного растрового изображения только лишь отсутствием шага 102, на котором многоцветное изображение приводят к двухцветному (а значит, и всей последовательности шагов 1101-1105 на фиг.11).

В качестве дополнительной иллюстрации работы алгоритма на фиг.1 приведены фиг.21-57, на которых изображено поэтапное выполнение всех шагов алгоритма с приведенными комментариями.

Рассмотренные способы обнаружения текста в растровом изображении могут использоваться как самостоятельно, так и для определения того, является ли данное изображение спамом. В этом случае, как показано на фиг.10, сначала выполняется один из способов, проиллюстрированных на фиг.1, а затем выход этого способа (из блока 116) попадает в блок 1001 на фиг.10, где формируют сигнатуру обнаруженного текста. Это формирование сигнатуры можно выполнять так же, как это делается, к примеру, в патенте США №7158961 (опубл. 02.01.2007), где раскрыты способ и устройство для оценки сходства, сравнивающие эскизы объектов, генерируемые как векторы, соответствующие объектам, где каждая координата вектора связана с соответствующим весом. Эти веса перемножаются с заранее заданным вектором хеширования, и произведения суммируются. Получается компактное представление объекта. В данном случае сигнатуру формируют на основе длин вероятных слов, оставшихся после сравнения со вторыми заранее заданными пределами.

Далее на шаге 1002 сравнивают сформированную сигнатуру с эталонными шаблонами спама, хранящимися в базе данных. Эти эталонные шаблоны находят в процессе анализа изображений с текстами, которые однозначно отнесены к спамовым. При совпадении с заранее заданной точностью сформированной сигнатуры с, по меньшей мере, одним эталонным шаблоном спама анализируемое растровое изображение считают спамом.

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

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

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

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

3. Способ по п.1, в котором в процессе или после нахождения границ каждого из упомянутых замкнутых контуров заменяют цвет в рисунке слитных пикселов, лежащем в данном замкнутом контуре, на цвет фона.

4. Способ по п.1 или 3, в котором упомянутые замкнутые контуры представляются описывающими их прямоугольниками.

5. Способ по п.1, в котором нахождение упомянутых предполагаемых строк текстовых символов осуществляют с помощью следующих операций:
выбирают очередной контур текстового символа, не участвующий в какой-либо из упомянутых предполагаемых строк;
осуществляют нанизывание строки слева и справа от выбранного контура текстового символа за счет выполнения следующих операций:
производят объединение правой и левой подстрок для получения новой строки.

6. Способ по п.5, в котором разбиение упомянутых предполагаемых строк текстовых символов на вероятные слова осуществляют с помощью следующих операций:
находят в каждой из упомянутых предполагаемых строк расстояния между всеми соседними парами контуров текстовых символов;
строят гистограмму частот найденных расстояний;
выбирают в качестве самого частого расстояния абсциссу первого максимума построенной гистограммы;
сравнивают в каждой из упомянутых предполагаемых строк расстояния между всеми соседними парами контуров текстовых символов с выбранным самым частым расстоянием;
разделяют в каждой из упомянутых предполагаемых строк любые два соседних контура текстового символа на вероятные слова, если расстояние между ними не меньше удвоенного упомянутого самого частого расстояния.

7. Способ по п.1, в котором при распознавании фонового цвета подсчитывают в исходном изображении количество пикселов цвета, отличного от фонового, а после упомянутого исключения вероятных слов, в которых количество контуров текстовых символов не попадает в упомянутые вторые заранее заданные пределы, и предполагаемых строк, в которых количество вероятных слов не попадает в упомянутые третьи заранее заданные пределы, выполняют следующие операции:
подсчитывают в оставшемся изображении количество пикселов упомянутого цвета, отличного от фонового цвета;
вычисляют отношение подсчитанного количества пикселов упомянутого цвета, отличного от фонового цвета, к ранее подсчитанному количеству пикселов того же цвета в исходном двухцветном изображении;
исключают из дальнейшего рассмотрения изображение, если для него вычисленное в предыдущей операции отношение меньше четвертого заранее заданного предела.

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

9. Способ по п.8, в котором приведение к растровому двухцветному изображению осуществляют с помощью следующих операций:
преобразуют цвета растрового многоцветного изображения в оттенки серого;
строят для преобразованного изображения гистограмму частот оттенков серого;
находят центр тяжести построенной гистограммы;
задают порог черно-белого на уровне 3/4 расстояния от первого уровня серого до найденного центра тяжести.

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

11. Способ по п.8, в котором в процессе или после нахождения границ каждого из упомянутых замкнутых контуров заменяют цвет в рисунке слитных пикселов, лежащем в данном замкнутом контуре, на цвет фона.

12. Способ по п.8 или 10, в котором упомянутые замкнутые контуры представляются описывающими их прямоугольниками.

13. Способ по п.8, в котором нахождение упомянутых предполагаемых строк текстовых символов осуществляют с помощью следующих операций:
выбирают очередной контур текстового символа, не участвующий в какой-либо из упомянутых предполагаемых строк;
осуществляют нанизывание строки слева и справа от выбранного контура текстового символа за счет выполнения следующих операций:
производят объединение правой и левой подстрок для получения новой строки.

14. Способ по п.13, в котором разбиение упомянутых предполагаемых строк текстовых символов на вероятные слова осуществляют с помощью следующих операций:
находят в каждой из упомянутых предполагаемых строк расстояния между всеми парами соседних контуров текстовых символов;
строят гистограмму частот найденных расстояний;
выбирают в качестве самого частого расстояния абсциссу первого максимума построенной гистограммы;
сравнивают в каждой из упомянутых предполагаемых строк расстояния между всеми соседними парами контуров текстовых символов с выбранным самым частым расстоянием;
разделяют в каждой из упомянутых предполагаемых строк любые два соседних контура текстового символа на вероятные слова, если расстояние между ними не меньше удвоенного упомянутого самого частого расстояния.

15. Способ по п.8, в котором при распознавании фонового цвета подсчитывают в исходном изображении количество пикселов цвета, отличного от фонового, а после упомянутого исключения вероятных слов, в которых количество контуров текстовых символов не попадает в упомянутые вторые заранее заданные пределы, и предполагаемых строк, в которых количество вероятных слов не попадает в упомянутые третьи заранее заданные пределы, выполняют следующие операции:
подсчитывают в оставшемся изображении количество пикселов упомянутого цвета, отличного от фонового цвета;
вычисляют отношение подсчитанного количества пикселов упомянутого цвета, отличного от фонового цвета, к ранее подсчитанному количеству пикселов того же цвета в исходном двухцветном изображении;
исключают из дальнейшего рассмотрения изображение, если для него вычисленное в предыдущей операции отношение меньше четвертого заранее заданного предела.

16. Способ выявления спама, содержащего растровое изображение, заключающийся в том, что:
осуществляют обнаружение текста в упомянутом растровом изображении по п.1 или 8;
формируют сигнатуру обнаруженного текста;
сравнивают сформированную сигнатуру с эталонными шаблонами спама, хранящимися в базе данных;
считают упомянутое растровое изображение спамом при совпадении с заранее заданной точностью сформированной сигнатуры с по меньшей мере одним эталонным шаблоном спама.

17. Способ по п.16, в котором сигнатуру формируют на основе длин вероятных слов, оставшихся после сравнения с упомянутыми вторыми заранее заданными пределами.