Файл: Анализ поисковых систем в сети Интернет (Задачи поисковых систем).pdf

• масштаб;

• расположение на сцене;

• фон и помехи;

• проекция, вращение и угол обзора.

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

• масштабом;

• поворотом в плоскости изображения;

• расположением на сцене;

• наличием шумов, заслоняющих объектов;

• другими значениями яркости и контраста.

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

SURF (Speed Up Robust Feature) — один из наиболее популярных методов выделения ключевых точек и их дескрипторов. Он широко применяется в области систем компьютерного зрения, так как обеспечивает высокую степень инвариантности повороту, масштабу и шумам, а также является одним из самых эффективных и быстрых современных алгоритмов этого класса. В совокупности с эффективным алгоритмом поиска ближайших соседей (Randomized KD-Tree) система представляет современное высокопроизводительное решение для большого круга задач, связанных с поиском изображений. Предлагаемая система изображена на рисунке. Наборы признаков заранее выделяются из изображений, находящихся в базе данных, и помещаются в виде многомерных векторов в базу признаков, при этом происходит индексирование. Для извлечения изображений из базы данных для образца, заданного пользователем, точно таким же способом выделяется набор признаков, который подается на вход алгоритма поиска ближайших точек (векторов) в базе признаков. Далее используется алгоритм отбора изображений, для которых суммарное расстояние от принадлежащих им точек до точек образца является минимальным.

Рис. 1. Основные модули CBIR-системы

Каждую точку описывает вектор, составленный из SURF-дескриптора (64 числа с плавающей точкой одинарной точности) и вектора, определяющего среднее значение цвета в окрестности 5 на 5 соответствующей точки (6 чисел). Для поиска был выбран алгоритм Randomized KD-Tree — наиболее эффективный для конкретного случая. Так как метод SURF работает только в оттенках серого, часть информации об исходном изображении теряется. Для того чтобы исправить этот недостаток, необходимо добавить к каждой ключевой точке описание цветовых характеристик в некоторой ее окрестности. Выберем область 5 на 5 вокруг ключевой точки и вычислим средние значения для каждого RGB-канала среди 25 точек^[3].

Для работы с базой изображений желательно иметь некоторый способ поиска изображений, который был бы удобнее и эффективнее, чем непосредственный просмотр всей базы. Большинство компаний выполняет всего два этапа обработки: отбор изображений, для включения в базу и классификация изображений посредством назначения им ключевых слов. Интернет-поисковики обычно получают ключевые слова автоматически из подписей к картинкам. С помощью обычных баз данных изображения можно находить на основе их текстовых атрибутов. При обычном поиске этими атрибутами могут быть категории, имена присутствующих на изображении людей, а также дата создания изображения. Для ускорения поиска содержимое базы может быть проиндексировано по всем этим полям. Тогда для поиска изображений можно будет воспользоваться языком SQL. Например, запрос:

SELECT * FROM IMAGEBD

WHERE CATEGORY=”МЭИ”

мог бы найти и вернуть все изображения из базы на которых изображён МЭИ. Но на самом деле всё не так просто. Такой тип поиска имеет ряд серьёзных ограничений. Назначение ключевых слов человеком является трудоёмкой задачей. Но, что гораздо хуже, эта задача допускает неоднозначное выполнение. Из-за этого некоторые из найденных изображений могут весьма и весьма сильно отличаться от ожиданий пользователя. На рисунке показана выдача google по запросу «МЭИ».

Рис. 2.Результаты поиска по запросу

Приняв, как факт, что использование ключевых слов не обеспечивает достаточной эффективности, мы рассмотрим ряд других методов поиска изображений^[4].

Поиск по образцу. Вместо того, чтобы указывать ключевые слова, пользователь мог бы предъявить системе образец изображения, или нарисовать эскиз. Затем наша система поиска должна найти похожие изображения или изображения, содержащие требуемые объекты. Для простоты будем считать, что пользователь представляет системе грубый эскиз ожидаемого изображения и некоторый набор ограничений. Если пользователем предоставлен пустой эскиз, то система должна вернуть все изображения, удовлетворяющие ограничениям. Ограничения же логичней всего задавать в виде ключевых слов и различных логических условий, объединяющих их. В самом общем случае, запрос содержит какое-то изображение, которое сравнивается с изображениями из базы согласно применяемой мере расстояния. Если расстояние равно 0, то считается, что изображение точно соответствует запросу. Значения больше 0 соответствуют различной степени сходства рассматриваемого изображения с запросом. Поисковая система должна возвращать изображения, отсортированные по значению расстояния от эскиза^[5].

На рисунке показаны поиска в системе QBIC с применением меры расстояния на основе цветового макета.

Рис. 3. Поиск в системе QBIC с применением меры расстояния на основе цветового макета^[6]

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

1. Цветовое сходство

2. Текстурное сходство

3. Сходство формы

4. Сходство объектов и отношений между объектами^[7]

Для простоты рассмотрим только методы цветового сходства. Характеристики цветового сходства часто выбираются очень простыми. Они позволяют сравнить цветовое содержание одного изображения с цветовым содержанием другого изображения или с параметрами, заданными в запросе. Например, в системе QBIC пользователь может указать процентное соотношение цветов в искомых изображениях. На рисунке показан набор изображений, полученных в результате выполнения запроса с указанием 40% красного, 30% жёлтого и 10% чёрного цвета. Хотя найденные изображения содержат очень похожие цвета, но смысловое содержание этих изображений существенно отличается.

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

где h(I), h(Q) – гистограммы изображений I,Q, A – матрица сходства. В матрице сходства элементы, значения которых близки к 1, соответствуют похожим цветам, близкие 0 соответствуют сильно различающимся цветам. Ещё одна возможная мера расстоянии основана на цветовом макете. При формировании запроса пользователю обычно предъявляется пустая сетка. Для каждой клетки пользователь может указать цвет из таблицы.

Характеристики сходства на основе цветового макета, в которых используется закрашенная сетка, требуют меры, которая учитывала бы содержание двух закрашенных сеток. Эта мера должна обеспечивать сравнение каждой клетки сетки, указанной в запросе, соответствующей клеткой сетки произвольного изображения из базы данных. Результаты сравнения всех клеток комбинируются для получения значения расстояния между изображениями^[8]:

где C^I (g),C^Q (g) — это цвета клетки g в изображениях I,Q соответственно.

Поиск на основе текстурного сходства, а тем более на основе сходства формы гораздо сложнее, но, стоит сказать, что уже сделаны первые шаги в этом направлении. Например, в системе ART MUSEUM хранятся цветные изображения многих картин. Эти цветные изображения подвергаются обработке для получения промежуточного представления. Предварительная обработка состоит из трёх этапов^[9]:

1. Уменьшение изображения до заданного размера и удаление шумов с помощью медианного фильтра.

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

Когда пользователь представляет системе эскиз, над ним производятся такие же операции обработки, и мы получаем линейный эскиз. Алгоритм сопоставления имеет корелляционный характер: изображение делится на клетки, и для каждой клетки вычисляется корреляция с аналогичной клеткой изображения из базы данных. Для надёжности эта процедура выполняется несколько раз для разных значений сдвига линейного эскиза. В большинстве случаев этот метод позволяет успешно находить требуемые изображения.

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

ГЛАВА 2. АНАЛИЗ ПОИСКОВЫХ СИСТЕМ В СЕТИ ИНТЕРНЕТ

2.1 Принцип работы Google

Алгоритм ранжирования Google сложнее, чем алгоритм Яндекса. Продвигать сайты в Google, особенно на начальном этапе, немного сложнее. Раскрутка молодого сайта в Google затруднительна, так как на новые веб-ресурсы накладывается фильтр (так называемая «песочница»). Google при ранжировании использует порядка 200 факторов, оптимизатор может повлиять лишь на некоторые.

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

Контент и ссылки – вот два фактора, на которые может повлиять оптимизатор при продвижении сайта в поисковой системе Google.

Релевантность контента относительно поискового запроса повышается следующим образом: простановка ключевых слов в заголовках (тегах title и h1 – h6). В title прописывается единственная ключевая фраза без лишних слов. Ключевые слова в начале html-кода страницы сайта так же увеличивает релевантность текста.^[10]

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

Сайт-акцептором называют сайт А, на который стоит ссылка с сайта B, а сайтом-донором – сайт B, который размещает ссылку на сайт A.

Перед продвижением сайта в Google следует:

• В случае нового сайта сообщить поисковой системе по адресу: https://www.google.com/webmasters/tools/submit-url/
• С помощью страницы «инструменты для веб-мастеров» https://www.google.com/webmasters/tools/home?hl=ru подтвердить права на сайт, создать файл sitemap.xml и добавить ссылку на карту сайта вида http://www.site.ru/sitemap.xml.
• Проверить код на валидность
• Проверить работоспособность всех ссылок на сайте, при необходимости исправить ошибки.

Это позволит поисковому роботу Google полнее и точнее проиндексировать сайт и выделить заслуженное место на страницах своей выдачи.

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

PageRank (далее просто PR) это числовая величина — мера “важности” страницы в поисковой системе Google. Зависит от числа внешних ссылок на данную страницу и от их веса (важности). Другими словами от количества и качества ссылающихся страниц. А если говорить математическим языком, то PR – это алгоритм расчёта авторитетности страницы, используемый поисковой системой Google. PR не является основным, но является одним из вспомогательных факторов при ранжировании сайтов в результатах поиска.

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