СПОСОБ ВЫЯВЛЕНИЯ СПАМА В РАСТРОВОМ ИЗОБРАЖЕНИИ Российский патент 2012 года по МПК G06K9/00 

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

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

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

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

Известен способ многоэтапного анализа информации растрового изображения (патент РФ №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. Кроме того, медианной фильтрацией удаляют случайный шум из изображения («соль и перец»). Обнаруживают край изображения, причем используют адаптивный порог (если у пиксела все соседи краевые, порог для текущего пиксела понижается). Затем осуществляют (в кадре или подкадрах) краевую фильтрацию, в которой удаляют из анализа те области, где текста нет или где он не может быть надежно обнаружен. Далее объединяют в единый символ краевые пикселы, находящие друг от друга на расстоянии меньше заданного. При этом определяются границы символа по осям координат и количество пикселов и все это сравнивается с заранее заданными порогами. Потом процессор определяет, лежат ли соседние символы в одной строке. Определяется среднее значение серого для выделенного текста и сравнивается с уровнями белого и черного, чтобы назначить фон белым, а текст черным. Этот способ, однако, имеет ограниченные возможности вследствие того, что требует достаточно много вычислений.

Способ обнаружения спама в изображениях описан в патенте RU 2363047 "Способ обнаружения текста в растровом изображении (варианты) и способ выявления спама, содержащего растровые изображения". Предложенный в этом патенте подход позволяет эффективно определять наличие текста в изображении, однако он обладает некоторыми недостатками. Один из недостатков связан с тем, что при наличии малого количества текста в изображении способ не способен определить находящийся текст. Другой недостаток заключался в том, что при обесцвечивании исходного растра изображение обесцвечивается либо слишком сильно (и исходные символы распадались, и терялся их смысл), либо слишком слабо (тогда символы "слипались" - например, два V превращались в одно W).

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

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

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

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

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

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

В одном из вариантов реализации дополнительно проводят обнаружение текста в изображении путем анализа объектов на изображении.

В другом из вариантов реализации сравнивают полученный текст с известными спам-текстами.

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

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

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

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

Фиг.3 иллюстрирует пример одного из изображений, содержащих спам.

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

Фиг.5 показывает увеличенный участок изображения с фиг.4.

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

Фиг.7 показывает увеличенный участок изображения с фиг.6.

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

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

Фиг.10 показывает алгоритм обхода границ (контура) объекта.

Фиг.11 показывает пример работы алгоритма на фиг.10.

Фиг.12 приводит пример, иллюстрирующий формы цифры "5", которые будут распознаны как одна и та же форма.

Фиг.13 иллюстрирует сравнение полученной сигнатуры изображения с известными сигнатурами объектов спам-изображений.

Фиг.14 иллюстрирует пример графического изображения, которое содержит спам.

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

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

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

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

Фиг.1 представляет пример компьютерной системы общего назначения, персональный компьютер или сервер 20, содержащий центральный процессор 21, системную память 22 и системную шину 23, которая содержит разные системные компоненты, в том числе память, связанную с центральным процессором 21. Системная шина 23 реализована как любая известная из уровня техники шинная структура, содержащая в свою очередь память шины или контроллер памяти шины, периферийную шину и локальную шину, которая способна взаимодействовать с любой другой шинной архитектурой. Системная память содержит постоянное запоминающее устройство (ПЗУ) 24, память с произвольным доступом (ОЗУ) 25. Основную систему ввода/вывода (BIOS), содержащую основные процедуры, которые обеспечивают передачу информации между элементами персонального компьютера 20, например, в момент загрузки с использованием ПЗУ 24.

Персональный компьютер 20 в свою очередь содержит жесткий диск 27 для чтения и записи, привод магнитных дисков 28 для чтения и записи на сменные магнитные диски 29 и оптический привод 30 для чтения и записи на сменные оптические диски 31, такие как CD-ROM, DVD-ROM и иные оптические носители информации. Жесткий диск 27, привод магнитных дисков 28, оптический привод 30 соединены с системной шиной 23 через интерфейс жесткого диска 32, интерфейс привода магнитных дисков 33 и интерфейс оптического привода 34 соответственно. Приводы и соответствующие компьютерные носители информации представляют собой энергонезависимые средства хранения компьютерных инструкций, структур данных, программных модулей и прочих данных персонального компьютера 20. Настоящее описание раскрывает реализацию системы, которая использует жесткий диск, сменный магнитный диск 29 и сменный оптический диск 31, но следует понимать, что возможно применение иных типов компьютерных носителей информации, которые способны хранить данные в доступной для чтения компьютером форме (кассеты с магнитной лентой, карты памяти flash, цифровые диски, картриджи Бернулли, память с произвольным доступом (ОЗУ), постоянные запоминающие устройства (ПЗУ), и т.п.). Термином «машиночитаемый носитель программ» или «машиночитаемый носитель информации» обычно называют носитель, такой как жесткий диск, сменный магнитный диск 29 и сменный оптический диск 31.

Некоторые из программных модулей, в том числе операционная система 35, хранятся на жестком диске, магнитном диске 29, оптическом диске 31, ПЗУ 24 или ОЗУ 25. Компьютер 20 имеет файловую систему 36, где хранится записанная операционная система 35 и дополнительные программные приложения 37, другие программные модули 38 и программные данные 39. Пользователь имеет возможность вводить команды и информацию в персональный компьютер 20 посредством устройств ввода (клавиатуры 40, манипулятора «мышь» 42). Другие устройства ввода (не отображены): микрофон, джойстик, игровая консоль, спутниковая тарелка, сканнер и т.п. Подобные устройства ввода по своему обычаю подключают к центральному процессору 21 через последовательный порт 46, который в свою очередь подсоединен в системной шине, но могут быть подключены иным способом, например параллельный порт, игровой порт или универсальная последовательная шина (USB). Монитор 47 или иной тип устройства отображения также подсоединен к системной шине 23 через интерфейс, такой как видеоадаптер 48. В дополнение к монитору 47, персональный компьютер может быть оснащен иными периферийными устройствами вывода (не отображены), например колонки принтер и т.п.

Персональный компьютер 20 способен работать в сетевом окружении, при этом используется логическое соединение с другим или несколькими удаленными компьютерами 49. Удаленный компьютер (или компьютеры) 49 является такими же персональным компьютером, сервером, роутером, сетевой станцией, пиринговым устройством или иным сетевым узлом, и по обыкновению, имеет большинство или все из упомянутых элементов, описанных ранее при объяснении существа персонального компьютера 20, представленного на Фиг.1 лишь только как устройство хранения 50, в котором хранятся приложения 37'. Логические соединения подразумевают локальную вычислительную сеть (LAN) 51 и глобальную вычислительную сеть (WAN) 52. Такие сети являются обычным офисным оборудованием, а также применяются в корпоративных компьютерных сетях, внутренних сетях компаний и Интернет.

При использовании LAN сетей персональный компьютер 20 подсоединен к локальной сети 51 через сетевой адаптер или интерфейс 53. При использовании WAN сетей персональный компьютер 20 имеет модем 54 или иные средства установления связи с глобальной вычислительной сетью 52, такой как Интернет. Модем 54, который является внутренним или внешним, подключен к системной шине 23 посредством последовательного порта 46. В сетевом окружении программные модули раскрытых персональных компьютеров 20 или части таких программ хранят в удаленных устройствах хранения данных. Следует уточнить, что сетевые соединения являются лишь примерными и не обязаны отображать точную сетевую конфигурацию сети, т.е. в действительности существуют иные способы установления логического соединения другими техническими средствами связи одного компьютера с другим.

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

Поступающее на вход компьютера изображение в общем случае является многоцветным. Для удобства дальнейшей работы его необходимо перевести в полутоновое изображение. Множество всех возможных полутонов называют уровнями серого (более подробно можно рассмотреть по ссылке http://en.wikipedia.org/wiki/Gray_scale). Эта операция осуществляется на шаге 102. Отметим, что использование полутонового изображения вместо двухцветного (черно-белого) имеет свои преимущества.

Например, в патенте RU 2363047 задают порог черно-белого на уровне вычисленного расстояния от первого уровня серого до найденного центра тяжести. В том случае, если уровень серого немного отличается, то конечное двухцветное (черно-белое) изображение может существенно отличаться от оригинала. Например, некоторые буквы могут "слипнуться" вместе или один символ перекроет другой. Если уровень серого будет слишком светлым, то многие буквы и символы могут "распасться", например, латинская W превратиться в двойной V. Вообще говоря, в разных частях изображения текст может быть написан разным цветом и шрифтом. Таким образом, при использовании сложного текста требуется выбрать уровень резкости для контура около каждого символа.

На фиг.3 изображено исходное изображение. При выборе слишком темного порога обесцвечивания (т.е. преобразования изображения в двухцветное) исходное растровое изображение могло обесцветиться, как показано на фиг.4. Как показано на фиг.5, которая является небольшим увеличением части текста с фиг.4, некоторые буквы могли слипнуться в таком случае. При выборе слишком светлого порога исходное изображение могло обесцветиться так, как показано на фиг.6. На фиг.7 также содержится небольшой элемент текста с фиг.6, который иллюстрирует "рассыпание" букв.

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

На фиг.8а и 8б показаны примеры соответственно обесцвечивания растра до черно-белого и использования полутонового изображения с выбором уровня резкости контура.

На шаге 103 на изображении выделяются объекты. Например, в патенте RU 2363047 отбрасывались слишком маленькие и слишком большие объекты (т.е. отбрасывались большие графические фрагменты, шум, знаки препинания и т.д.), выделялись контуры объектов, затем контуры объединялись в строки и в конечном итоге определялось содержание текста на изображении в зависимости от количества найденных символов. Однако подобный алгоритм плохо работает в случае использования малого количества найденного текста на изображении. В отличие от патента RU 2363047 предлагаемый способ не отбрасывает из рассмотрения слишком большие объекты (которые не могут считаться буквами).

Вокруг каждого выделенного объекта выделяется собственный контур, который образуется путем обхода границ объекта. С каждого объекта (в частности, буквы) снимается набор признаков: отрезки, углы между ними, образуемые дуги. Обход объекта происходит по часовой стрелке. Пример подобного обхода приведен на фиг.9.

Алгоритм обхода границ (контура) объекта на шаге 104 представлен на фиг.10. Сначала выбирается точка контура на этапе 1001. В каждой точке контура строится касательная на этапе 1002 (она проводиться в пределах заданного количество пикселей назад и вперед относительно порядка прохождения по контуру) и в точке запоминается угол наклона касательной к горизонту на этапе 1003 в одном из вариантов реализации. В другом варианте реализации, значения углов в точках можно заменить на отклонения к значениям углов в ближайших предыдущих точках контура. Таким образом, в том случае если отклонение равно нулю (этап 1004), это означает, что точки контура соединяет отрезок и на этапе 1005 вычисляется его длина. Если же значение отклонения постоянно на некотором промежутке контура (этап 1006), значит, что точки контура соединяет дуга и на этапе 1007 вычисляется длина дуги и радиус ее кривизны. Алгоритм работает пока не будут пройдены все точки контура (этап 1008) и заканчивается на этапе 1009 вычислением сигнатуры. Пример подобной реализации представлен на фиг.11 для слова "Женя".

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

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

Далее на шаге 108 происходит сравнение полученной сигнатуры изображения с известными сигнатурами объектов спам-изображений, что более подробно отражено на фиг.13. Каждый объект исходного изображения выбирается на этапе 1301 и сравнивается с известными объектами спам-изображений на этапе 1302. Для каждого из таких объектов может быть назначен свой собственный спам-вес путем проверки на этапе 1303, который позволяет характеризовать исходное изображение как спам-изображение. Таким образом, на этапе 1304 спам-вес изображения будет увеличен в том случае, если объект изображения является известным объектом спам-изображений. Например, объекты, имеющие вид сексуальной направленности или обнаруженный текст с ссылкой из "черного списка", позволяют проставить такому изображению спам-вес, равный 100% в одном из вариантов реализации. Если итоговый спам-вес превышает заданный порог на этапе 1305, то изображение признается спамом на этапе 1306. В том случае, если были просмотрены все объекты (проверка на этапе 1307), то определяется, что изображение не является спамом и алгоритм заканчивает свою работу на этапе 1308.

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

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

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

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

2. Способ по п.1, в котором сигнатура объекта вычисляется следующим образом:
(i) выбирают точку контура на объекте;
(ii) строят касательную в точке контура;
(iii) вычисляют угол касательной в точке контура;
(iv) вычисляют отклонение угла касательной по сравнению с предыдущим значением угла касательной;
(v) вычисляют длину отрезка, в том случае если отклонение угла касательной равно нулю или
(vi) вычисляют длину дуги и радиус кривизну дуги, если отклонение угла касательной постоянно;
(vii) повторяют этапы (i)-(vi) для всех точек контура объекта.

3. Способ по п.1, в котором дополнительно проводят обнаружение текста в изображении путем анализа объектов на изображении.

4. Способ по п.3, в котором сравнивают полученный текст с известными спам-текстами.