Способ и система для идентификации связанности изображения, используя анализ ссылок и компоновки страницы
Изобретение относится к поиску изображений на Web-страницах и к анализу связанности изображений Web-страниц. Изобретение позволяет осуществлять поиск, основанный на изображении, который в вычислительном отношении не такой затратный, как обычные способы поиска, основанные на контенте. Определяют связанность между изображениями, сначала идентифицируя блоки в пределах Web-страниц и затем анализируя важность блоков для Web-страниц, Web-страниц для блоков и изображений для блоков. На основании этого анализа определяется степень, с которой каждое изображение связано с каждым другим изображением. Связанность изображений можно также использовать для генерации ранжирования изображений. Можно также генерировать векторное представление изображений на основании их связанности и применять алгоритм кластеризации к векторным представлениям для идентификации кластеров связанных изображений. Принимают от пользователя выбор изображения блока на Web-странице в качестве запроса на поиск, идентифицируют кластер связанных изображений, содержащий выбранное изображение, и выдают пользователю индикацию Web-страниц, которые содержат изображения из идентифицированного кластера, в качестве результата поиска. 3 н. и 15 з.п. ф-лы, 6 табл., 6 ил.
Область техники
Описанная технология в целом относится к анализу Web-страниц и, в частности, к связанности изображений Web-страниц.
Предшествующий уровень техники
Многие услуги машин поиска, например от фирм Google и Overture, предусматривают поиск информации, которая доступна через Интернет. Эти услуги машин поиска позволяют пользователям искать дисплейные страницы (страницы отображения), такие как Web-страницы, которые могут быть интересны пользователям. После того как пользователь вводит запрос на поиск, который включает в себя термины поиска, служба машины поиска идентифицирует Web-страницы, которые могут быть связаны с этими терминами поиска. Чтобы быстро идентифицировать связанные Web-страницы, услуги машины поиска могут поддерживать отображение ключевых слов в Web-страницы. Это отображение может быть сгенерировано посредством "кроулинга (автоматического выбора документов по ссылкам) и индексации" в сети (то есть Всемирной паутине) для идентификации ключевых слов каждой Web-страницы. Чтобы осуществить кроулинг в сети, служба машины поиска может использовать список корневых Web-страниц для идентификации всех Web-страниц, которые доступны через эти корневые Web-страницы. Ключевые слова любой конкретной Web-страницы могут быть идентифицированы, используя различные хорошо известные способы извлечения информации, такие как идентификация слов заголовка, слов в метаданных Web-страницы, слов, которые подсвечены, и т.д. Служба машины поиска затем ранжирует Web-страницы результата поиска на основании степени близости каждого соответствия, популярности Web-страницы (например, PageRank для Google) и т.д. Служба машины поиска может также генерировать оценку релевантности, чтобы указать, насколько релевантной информация Web-страницы может быть к запросу поиска. Служба машины поиска затем отображает пользователю ссылки на такие Web-страницы в том порядке, который основан на их ранжировании.
Хотя много Web-страниц являются графически ориентированными в том смысле, что они могут содержать много изображений, обычные услуги машин поиска обычно осуществляют поиск на основании только текстового содержимого Web-страницы. Некоторые попытки были сделаны, однако, чтобы поддерживать поиск Web-страниц на основании изображения. Например, пользователь, просматривающий Web-страницу, может пожелать идентифицировать другие Web-страницы, которые содержат изображения, связанные с изображением на этой Web-странице. Способы поиска на основании изображения являются обычно или основанными на контенте (содержимом), или основанными на ссылках и дополнительно используют сопровождающий текст, чтобы помочь в анализе изображений. Основанные на контенте способы используют визуальную информацию низкого уровня для индексации изображения. Поскольку основанные на контенте способы поиска требуют больших вычислительных ресурсов, они не имеют практического значения для поиска изображений в сети. Основанные на ссылках способы поиска обычно предполагают, что изображения на одной и той же Web-странице вероятно являются связанными и что изображения на Web-страницах, каждое из которых связано с одной и той же Web-страницей, связаны. К сожалению, эти предположения неверны во многих ситуациях прежде всего потому, что одиночная Web-страница может иметь содержимое, относящееся ко многим различным темам. Например, Web-страница для Web-страницы новостей может содержать содержимое (контент), относящееся к международному политическому событию, и содержимое, относящееся к национальному спортивному событию. В таком случае маловероятно, что изображение спортивной команды, относящееся к национальному спортивному событию, связано с Web-страницей, связанной с содержимым, относящимся к международному политическому событию.
Было бы желательно иметь способ поиска, основанный на изображении, который в вычислительном отношении не будет столь же дорог, как обычные основанные на контенте способы поиска, и который, в отличие от обычных основанных на ссылках способов поиска, принимал бы во внимание разнообразные темы, которые могут иметь место на одиночной Web-странице.
Сущность изобретения
Предлагается система для определения связанности изображений страниц на основании анализа ссылок и компоновки страницы. Система анализа ссылок обнаруживает связанность между изображениями посредством сначала идентификации блоков в пределах страницы и затем анализа важности блоков для страниц, страниц для блоков и изображений для блоков. На основании этого анализа система анализа ссылок определяет степень, с которой каждое изображение связано с каждым другим изображением. Поскольку связанность изображения с другим изображением основана на (значении) важности на уровне блоков, что является меньшей единицей, чем страница, вместо важности на уровне страниц, эта связанность является более точным представлением связанности, чем обычные основанные на ссылках способы поиска.
Краткое описание чертежей
Фиг.1 является диаграммой, иллюстрирующей блоки, изображения и ссылки в типовой коллекции Web-страниц.
Фиг.2 является диаграммой, иллюстрирующей компоненты системы анализа ссылок в одном варианте осуществления.
Фиг.3 изображает последовательность операций, которая иллюстрирует обработку компонента генерации матрицы "изображение-для-изображения" в одном варианте осуществления.
Фиг.4 изображает последовательность операций, которая иллюстрирует обработку компонента генерации матрицы "блок-для-страницы" в одном варианте осуществления.
Фиг.5 изображает последовательность операций, которая иллюстрирует обработку компонента генерации матрицы "страница-для-блока" в одном варианте осуществления.
Фиг.6 изображает последовательность операций, которая иллюстрирует обработку компонента генерации матрицы "блок-для-изображения" в одном варианте осуществления.
Подробное описание
Предложены способ и система для определения связанности изображений страниц на основании анализа ссылок и компоновки страницы. В одном варианте осуществления система анализа ссылок определяет связанность между изображениями посредством сначала идентификации блоков в Web-страницах и затем анализа важности блоков для Web-страниц, Web-страниц для блоков и изображений для блоков. На основании этого анализа система анализа ссылок определяет степень, с которой каждое изображение связано с каждым другим изображением. Блок Web-страницы представляет область Web-страницы, которая, как предполагается, относится к аналогичной теме. Например, статья новостей, касающаяся международного политического события, может представлять один блок, а статья новостей, касающаяся национального спортивного события, может представлять другой блок. Важность блока для страницы может указывать вероятность того, что пользователь сосредоточится на этом блоке при просмотре этой страницы. Важность страницы для блока может указывать вероятность того, что пользователь выберет из этого блока ссылку на эту страницу. Важность изображения для блока может указывать вероятность того, что пользователь сосредоточится на этом изображении при просмотре этого блока. После вычисления числового индикатора этих значений важности для пар страниц и блоков и пар изображений и блоков система анализа ссылок генерирует индикатор связанности каждого изображения к каждому другому изображению посредством объединения вычисленной важности блока для страницы, вычисленной важности страницы для блока и вычисленной важности изображения для блока. Поскольку связанность изображения с другим изображением основана на важности на уровне блоков вместо важности на уровне страниц, эта связанность является более точным представлением связанности, чем обычные основанные на ссылках способы поиска.
Система анализа ссылок может также использовать связанность изображений для генерации ранжирования изображений. Ранжирование может быть основано на вероятности того, что пользователь, который начинает просматривать произвольное изображение, будет переходить к другому изображению после произвольно большого количества переходов между изображениями. Система анализа ссылок может также генерировать векторное представление изображений на основании их связанности и применять алгоритм кластеризации к векторным представлениям для идентификации кластеров связанных изображений.
Фиг.1 является диаграммой, иллюстрирующей блоки, изображения и ссылки в типовой коллекции Web-страниц. Эта коллекция Web-страниц включает в себя Web-страницы 1-4. Блоки в Web-страницах представлены как прямоугольники, изображения в блоках представлены как круги, и ссылки в блоках представлены в виде направленных стрелок от блока к связанной Web-странице. Web-страница 1 содержит блок 1, который содержит изображения 1 и 2 и ссылки 1 и 2. Web-страница 2 содержит блок 2, который содержит изображение 3 и ссылку 3, и блок 3, который содержит изображение 4 и ссылку 4. Web-страница 3 содержит блок 4, который содержит изображение 5 и ссылки 5 и 6, и блок 5, который содержит изображение 6 и ссылку 7. Web-страница 4 содержит блок 5, который содержит изображения 7, 8, 9 и 10 и ссылку 8. Поскольку система анализа ссылок основывает связанность изображения на блоках, а не на всей Web-странице, связанность изображения с другими изображениями вероятно основана на более точном представлении темы изображения. Например, Web-страница 2 содержит блоки 2 и 3, которые могут быть посвящены различным темам, таким как международное политическое событие и национальное спортивное событие соответственно. Система анализа ссылок может идентифицировать, что изображение 4 более тесно связано с изображениями Web-страницы 4, чем с изображениями Web-страницы 3, потому что блок 3, который содержит изображение 4, имеет ссылку 4 на Web-страницу 4. Например, Web-страница 4 более вероятно относится к спорту, чем Web-страница 3, потому что блок 3 содержит ссылку на Web-страницу 4, но не на Web-страницу 3. Как таковое, изображение 4 более вероятно связано с изображениями 7, 8, 9 и 10, чем с изображениями 5 и 6 из Web-страницы 3. Способы, которые не основаны на анализе на уровне блоков, могут идентифицировать, что изображение 4 одинаково связано с Web-страницей 3 и Web-страницей 4, потому что эти способы не отличают блок 2 от блока 3 на Web-странице 2.
В одном варианте осуществления система анализа ссылок вычисляет важность страницы для блока, для каждого блока и комбинации страниц как вероятность того, что пользователь, который выбирает ссылку этого блока, выберет ссылку к этой странице. Если блок не имеет ссылки на страницу, то вероятность равна нулю. Если блок имеет ссылку на страницу, то система анализа ссылок может предполагать, что пользователь выберет каждую из ссылок блока с равной вероятностью. Матрица вероятностей "блок-для-страницы" определяется следующим уравнением:
где 
представляет вероятность того, что пользователь, который выбирает ссылку блока 
, выберет ссылку к странице 
, и 
- число ссылок в блоке . Матрица 
"блок-для-страницы" для Web-страниц на Фиг.1 показана в Таблице 1. Строки Таблицы 1 представляют блоки, а столбцы представляют страницы. В этом примере вероятность того, что пользователь, который выбирает ссылку блока 4, выберет ссылку на Web-страницу 2, равна 0,5.
| Таблица 1 | ||||
| 1 | 2 | 3 | 4 | |
| 1 | 0,5 | 0,5 | ||
| 2 | 1 | |||
| 3 | 1 | |||
| 4 | 0,5 | 0,5 | ||
| 5 | 1 | |||
| 6 | 1 |
В одном варианте осуществления система анализа ссылок вычисляет для каждой комбинации страницы и блока важность блока для страницы как вероятность того, что этот блок является наиболее важным блоком страницы. Вероятность того, что блок, не содержащийся на странице, является наиболее важным блоком этой страницы, равна нулю. Система анализа ссылок может предполагать с равной вероятностью, что каждый блок, содержащийся на странице, является наиболее важным. Матрица вероятностей "страница-для-блока" определяется следующим уравнением:
где 
представляет вероятность того, что блок 
является наиболее важным блоком страницы 
, и 
- число блоков на странице .
В одном варианте осуществления система анализа ссылок вычисляет вероятность того, что блок является наиболее важным блоком страницы, на основании позиции, размера, шрифта, цвета и других физических атрибутов блока. Например, большой блок, который центрирован в середине страницы, может быть более важным, чем маленький блок в нижнем левом углу страницы. Методика для вычисления важности блока и степени связности блоков описана в заявке США на патент "Способ и система для вычисления важности блока в пределах дисплейной страницы", поданной 29 апреля 2004, которая тем самым включена (в настоящее описание) по ссылке. Матрица 
"страница-для-блока" может быть в более общем случае представлена как:
где 
- функция, представляющая вероятность того, что блок 
является наиболее важным блоком страницы 
. В одном варианте осуществления функция определена как размер блока , разделенного расстоянием центра блока от центра экрана, когда отображается страница . Функция 
может быть определена следующим образом:
где α - коэффициент нормализации, который гарантирует, что сумма значений функции для блока равна 1. Функция может рассматриваться как вероятность того, что пользователь сосредоточится на блоке 
при просмотре страницы 
. Матрица 
"страница-для-блока" для Web-страниц на Фиг.1 показана в Таблице 2. Строки Таблицы 2 представляют страницы, а столбцы представляют блоки. В этом примере вероятность того, что блок 4 является наиболее важным блоком Web-страницы 3, равна 0,8.
| Таблица 2 | ||||||
| 1 | 2 | 3 | 4 | 5 | 6 | |
| 1 | 1 | |||||
| 2 | 0,5 | 0,5 | ||||
| 3 | 0,8 | 0,2 | ||||
| 4 | 1 |
В одном варианте осуществления система анализа ссылок вычисляет для каждой комбинации блока и изображения важность изображения для блока как вероятность того, что изображение является наиболее важным изображением этого блока. Если блок не содержит некоторого изображения, то вероятность того, что изображение является наиболее важным этого блока, равна нулю. Система анализа ссылок может предполагать с равной вероятностью, что каждое изображение блока является наиболее важным. Система анализа ссылок может использовать другие критерии важности изображения для блока, например на основании относительных размеров изображений, расположения изображений в блоках и т.д. Матрица вероятностей "блок-для-изображения" определяется следующим уравнением:
где 
представляет вероятность того, что изображение 
является наиболее важным изображением блока 
, и 
- число изображений в блоке . Матрица 
"блок-для-изображения" для Web-страниц на Фиг.1 показана в Таблице 3. Строки Таблицы 3 представляют блоки, а столбцы представляют изображения. В этом примере вероятность того, что изображение 2 является наиболее важным изображением блока 1, равна 0,5.
| Таблица 3 | ||||||||||
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | |
| 1 | 0,5 | 0,5 | ||||||||
| 2 | 1 | |||||||||
| 3 | 1 | |||||||||
| 4 | 1 | |||||||||
| 5 | 1 | |||||||||
| 6 | 0,25 | 0,25 | 0,25 | 0,25 |
В одном варианте осуществления система анализа ссылок вычисляет важность одной страницы для другой страницы для каждой упорядоченной пары страниц как вероятность того, что пользователь, просматривающий первую страницу пары, выберет ссылку ко второй странице пары. Система анализа ссылок вычисляет вероятность для каждой пары, суммируя по каждому блоку первой страницы вероятность того, что блок является наиболее важным блоком первой страницы, умноженной на вероятностью того, что вторая страница является наиболее важной страницей для этого блока. Важность страницы для другой страницы таким образом раскладывается на множители в отношении того, что пользователи могут предпочитать выбирать ссылки в пределах наиболее важных блоков страницы. Матрица "страница-для-страницы" этих вероятностей представлена следующим образом:
где 
представляет матрицу "страница-для-страницы". Вероятность 
может быть альтернативно представлена как:
где α представляет первую страницу пары и β представляет вторую страницу пары. Матрица "страница-для-страницы" для Web-страниц на Фиг.1 показана в Таблице 4. В этом примере вероятность того, что пользователь, просматривающий страницу 3, будет переходить на страницу 2, равна 0,4.
| Таблица 4 | ||||
| 1 | 2 | 3 | 4 | |
| 1 | 0 | 0,5 | 0,5 | 0 |
| 2 | 0 | 0 | 0,5 | 0,5 |
| 3 | 0,2 | 0,4 | 0 | 0,4 |
| 4 | 0 | 0 | 1 | 0 |
Система анализа ссылок вычисляет для каждой упорядоченной пары блоков важность одного блока для другого блока как вероятность того, что пользователь, просматривающий первый блок из пары, выберет ссылку на страницу, содержащую второй блок из пары, и найдет, что этот второй блок будет наиболее важным для его страницы. Система анализа ссылок вычисляет вероятность для каждой пары, суммируя вероятности того, что пользователь, который выбирает ссылку первого блока, выберет ссылку для страницы, которая содержит второй блок, умноженную на вероятность того, что этот второй блок является наиболее важным блоком его страницы. Таким образом, важность одного блока для другого блока представляет то, что пользователь, просматривающий первый блок, выберет ссылку на страницу, содержащую второй блок, и сосредоточит (их) внимание на втором блоке. Матрица "блок-для-блока" этих вероятностей представлена следующим образом:
где 
представляет матрицу "блок-для-блока". Вероятности альтернативно могут быть представлены как:
Матрица "блок-для-блока" для Web-страниц на Фиг.1 показана в Таблице 5. В этом примере вероятность того, что пользователь, просматривающий блок 4, перейдет на страницу 2 и сосредоточит внимание на блоке 3, равна 0,25.
| Таблица 5 | ||||||
| 1 | 2 | 3 | 4 | 5 | 6 | |
| 1 | 0 | 0,25 | 0,25 | 0,4 | 0,1 | 0 |
| 2 | 0 | 0 | 0,8 | 0,2 | 0 | 0 |
| 3 | 0 | 0 | 0 | 0 | 0 | 1 |
| 4 | 0 | 0,25 | 0,25 | 0 | 0 | 0,5 |
| 5 | 1 | 0 | 0 | 0 | 0 | 0 |
| 6 | 0 | 0 | 0,8 | 0,2 | 0 | 0 |
В одном варианте осуществления система анализа ссылок разлагает в матрицу "блок-для-блока" вероятность того, что два блока на одной и той же странице могут быть связаны. Исправленная матрица "блок-для-блока" представлена следующим образом:
где 
- диагональная матрица 
, 
- является матрицей связности и 
- весовой коэффициент. Матрица определена следующим образом:
где 
- степень связности самого маленького блока, содержащего и блок 
и блок 
. Весовой коэффициент 
может обычно устанавливаться равным малому значению (например, менее 0,1), потому что в большинстве случаев различные блоки на одной и той же странице относятся к различным темам.
Система анализа ссылок вычисляет для каждой упорядоченной пары изображений вероятность того, что первое изображение из пары связано со вторым изображением из пары. Система анализа ссылок вычисляет эту вероятность, суммируя вероятности "блок-для-блока" для комбинации каждого блока, который содержит первое изображение, с каждым блоком, который содержит второе изображение. Матрица "изображение-для-изображения" этих вероятностей представлена следующим образом:
где 
представляет матрицу "изображение-для-изображения". Матрица "изображение-для-изображения" для Web-страниц на Фиг.1 показана в Таблице 6. В этом примере вероятность того, что пользователь, просматривающий блок 10, затем просмотрит страницу 3 и сосредоточится на блоке 5, равна 0,05.
| Таблица 6 | ||||||||||
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | |
| 1 | 0 | 0 | 0,125 | 0,125 | 0,2 | 0,05 | 0 | 0 | 0 | 0 |
| 2 | 0 | 0 | 0,125 | 0,125 | 0,2 | 0,05 | 0 | 0 | 0 | 0 |
| 3 | 0 | 0 | 0 | 0,8 | 0,2 | 0 | 0 | 0 | 0 | 0 |
| 4 | 0 | 0 | 0 | 0 | 0 | 0 | 0,25 | 0,25 | 0,25 | 0,25 |
| 5 | 0 | 0 | 0,25 | 0,25 | 0 | 0 | 0,125 | 0,125 | 0,125 | 0,125 |
| 6 | 0,5 | 0,5 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 7 | 0 | 0 | 0 | 0,2 | 0,05 | 0 | 0 | 0 | 0 | 0 |
| 8 | 0 | 0 | 0 | 0,2 | 0,05 | 0 | 0 | 0 | 0 | 0 |
| 9 | 0 | 0 | 0 | 0,2 | 0,05 | 0 | 0 | 0 | 0 | 0 |
| 10 | 0 | 0 | 0 | 0,2 | 0,05 | 0 | 0 | 0 | 0 | 0 |
В одном варианте осуществления система анализа ссылок разлагает в матрицу "изображение-для-изображения" вероятность того, что два блока на одной и той же странице могут быть связаны. Исправленная матрица "изображение-для-изображения" представлена следующим образом:
где 
- весовой коэффициент и 
- диагональное матричное представление
Весовой коэффициент может быть установлен равным большому значению (например, 0,7-0,9), потому что два изображения в одном и том же блоке, вероятно, связаны.
В одном варианте осуществления система анализа ссылок генерирует векторное представление каждого изображения из матрицы "изображение-для-изображения". Система анализа ссылок генерирует векторы, используя подход наименьших квадратов, который разлагает на (значения) подобия между парой изображений, как указано матрицей "изображение-для-изображения". Система анализа ссылок первоначально преобразовывает матрицу "изображение-для-изображения" в матрицу подобия, представленную следующим образом:
где 
представляет матрицу подобия. Если 
является векторным представлением изображения 
, то оптимальный набор векторов изображения 
, получаемый с использованием следующей целевой функции:
Если является диагональной матрицей, такой что 
является суммой значений -й строки матрицы подобий, то проблема минимизации сводится к следующему:
где 
равно 
. Решение задается решением минимальных собственных значений для общей задачи собственных значений:
Если (
,
), (
,
), …, (
,
) являются решениями уравнения 16, и <<…<, то 
=0 и =(1, 1, ..,1). Система анализа ссылок выбирает собственные вектора 1 - 
для представления изображения в 
-мерном евклидовом пространстве. Вектор для изображения представлен следующим образом:
где 
обозначает 
-й элемент 
.
Система анализа ссылок идентифицирует кластеры связанных изображений, представляя каждое изображение вектором так, что расстояние между векторами изображения представляет их семантическое подобие. Различные алгоритмы кластеризации могут применяться к векторам изображения для идентификации кластеров семантически связанных изображений. Эти алгоритмы кластеризации могут включать вектор Фидлера (Fiedler) из спектральной теории графов, -значную кластеризацию и т.д.
Кластеризация изображений может использоваться, чтобы помочь в просмотре. Например, при просмотре Web-страницы пользователь может выбирать изображение и делать запрос, чтобы видеть связанные изображения. Web-страницы, которые содержат изображения, которые являются объединенными в кластеры вместе с выбранным изображением, могут затем быть представлены как результат запроса. В одном варианте осуществления Web-страницы могут быть представлены в порядке, который основан на расстоянии между вектором изображения каждого изображения и вектором изображения выбранного изображения.
Кластеризация изображений может также использоваться, чтобы обеспечить многомерную визуализацию изображений, которые семантически связаны. Векторы изображения могут быть сгенерированы для изображений из коллекции Web-страниц. Как только кластеры идентифицированы, система может отображать индикацию каждого кластера на двумерной сетке, представляющей кластеры, на основании различных собственных векторов.
Система анализа ссылок может ранжировать изображения на основании матрицы "изображение-для-изображения". Матрица "изображение-для-изображения" представляет вероятность перехода от изображения к изображению. Возможно, что пользователь будет переходить к изображению случайно. Чтобы это принять во внимание, система анализа ссылок генерирует матрицу вероятных переходов, которая разлагает эту случайность в матрицу "изображение-для-изображения" следующим образом:
где 
- матрица вероятных переходов, 
- весовой коэффициент (например, 0,1-0,2), и 
- матрица переходов для вероятностей однородных переходов (
для всех 
, 
). Из-за введения граф является связным, и существует стационарное распределение случайного обхода графа. Ранг изображения может быть представлен следующим образом:
где 
- собственный вектор 
с собственным значением 1, представляющим ранг изображения, 
представляет стационарное распределение вероятности и 
представляет ранг изображения 
.
Фиг.2 является диаграммой, иллюстрирующей компоненты системы анализа ссылок в одном варианте осуществления. Система 200 анализа ссылок включает в себя хранилище 201 Web-страниц, компонент 202 вычисления ранга изображения, компонент 203 идентификации кластеров изображения и компонент 211 генерации матрицы "изображение-для-изображения". Компонент 211 генерации матрицы "изображение-для-изображения" использует компонент 212 идентификации блоков, компонент 213 генерации матрицы "блок-для-страницы", компонент 214 генерации матрицы "страница-для-блока" и компонент 215 генерации матрицы "блок-для-изображения" для генерации матрицы, которая указывает связанность "изображения-для-изображения". Хранилище Web-страниц содержит коллекцию Web-страниц. Компонент вычисления ранга изображения использует компонент генерации "изображение-для-изображения" для вычисления связанности изображений и затем использует эти вычисления связанности для ранжирования изображений. Компонент идентификации кластеров изображения использует компонент генерации матрицы "изображение-для-изображения" для вычисления связанности изображений, генерирует векторное представление изображений на основании этой матрицы и идентифицирует кластеры изображений, используя сгенерированные векторы. Хотя и не показано на Фиг.2, система анализа ссылок может также включать в себя компонент для вычисления элементов ранжирования Web-страницы, отличной от этих изображений. Например, система анализа ссылок может применять ранжирования уравнений 20 и 21 к матрице "блок-для-блока" для ранжирования блоков и к матрице "страница-для-страницы" для ранжирования самих страниц.
Вычислительное устройство, на котором реализуется система анализа ссылок, может включать в себя центральный модуль обработки, память, устройства ввода данных (например, клавиатуру и устройства управления позицией), устройства вывода (например, устройства отображения) и устройства хранения (например, дисковые накопители). Память и устройства хранения являются считываемыми компьютером средствами, которые могут содержать команды, которые реализуют систему анализа ссылок. Кроме того, структуры данных и структуры сообщения могут быть сохранены или переданы посредством среды передачи данных, такой как сигнал на линии связи. Могут использоваться различные линии связи, например Интернет, локальная сеть, глобальная сеть или двухточечное подключение модемной связи.
Фиг.2 иллюстрирует пример подходящей рабочей среды, в которой может быть осуществлена система анализа ссылок. Рабочая среда является только одним из примеров подходящей среды и не предназначена для наложения какого-либо ограничения на контекст использования или функциональные возможности системы анализа ссылок. Другие известные вычислительные системы, среды и конфигурации, которые могут быть подходящими для использования, включают в себя персональные компьютеры, серверные компьютеры, карманные или портативные ЭВМ, мультипроцессорные системы, основанные на микропроцессорах системы, программируемую бытовую электронику, сетевые ПК, миникомпьютеры, универсальные компьютеры, распределенные вычислительные среды, которые включают в себя любую из вышеупомянутых систем или устройств, и т.п.
Система анализа ссылок может быть описана в общем контексте выполняемых компьютером команд, таких как программные модули, выполняемых одним или более компьютерами или другими устройствами. Вообще, программные модули включают в себя подпрограммы, программы, объекты, компоненты, структуры данных и т.д., которые выполняют конкретные задачи или реализуют специфические абстрактные типы данных. Как правило, функциональные возможности программных модулей могут быть объединены или распределены как необходимо в различных вариантах осуществления.
Фиг.3 изображает схему последовательности операций, которая иллюстрирует обработку (работу) компонента генерации матрицы "изображение-для-изображения" в одном варианте осуществления. На этапе 301 компонент идентифицирует блоки в пределах Web-страниц, сохраненных в хранилище Web-страниц. На этапе 302 компонент вызывает компонент генерации матрицы "блок-для-страницы". На этапе 303 компонент вызывает компонент генерации матрицы "страница-для-блока". На этапе 304 компонент вызывает компонент генерации матрицы "блок-для-изображения". На этапе 305 компонент генерирует матрицу "блок-для-блока". На этапе 306 компонент генерирует матрицу "изображение-для-изображения" и затем завершает работу.
Фиг.4 изображает схему последовательности операций, которая иллюстрирует обработку (работу) компонента генерации матрицы "блок-для-страницы" в одном варианте осуществления. На этапах 401-408 компонент в циклах выбирает каждую страницу, каждый блок в пределах каждой страницы и каждую ссылку в пределах каждого блока и устанавливает важность страниц, связанных этой ссылкой, для этого блока. На этапе 401 компонент выбирает следующую страницу. На этапе 402 принятия решения, если все страницы уже были выбраны, то компонент возвращает матрицу "блок-для-страницы", иначе компонент продолжает работу на этапе 403. На этапе 403 компонент выбирает следующий блок выбранной страницы. На этапе 404 принятия решения, если все блоки выбранной страницы уже были выбраны, то компонент переходит в цикле на этап 401 для выбора следующей страницы, иначе компонент продолжает работу на этапе 405. На этапе 405 компонент подсчитывает число ссылок в пределах выбранного блока. На этапе 406 компонент выбирает указанную ссылкой страницу для следующей ссылки для выбранного блока. На этапе 407 принятия решения, если все указанные ссылкой страницы выбранного блока уже были выбраны, то компонент переходит в цикле на этап 403, чтобы выбрать следующий блок, иначе компонент продолжает работу на этапе 408. На этапе 408 компонент устанавливает важность указанной ссылкой страницы для блока и затем переходит в цикле на этап 406, чтобы выбрать связанную ссылкой страницу для следующей ссылки выбранного блока.
Фиг.5 изображает схему последовательности операций, которая иллюстрирует обработку компонента генерации матрицы "страница-для-блока" в одном варианте осуществления. На этапах 501-506 компонент в циклах выбирает каждую страницу и каждый блок в пределах каждой страницы и устанавливает важность этого блока для выбранной страницы. На этапе 501 компонент выбирает следующую страницу из хранилища Web-страниц. На этапе 502 принятия решения, если все страницы уже были выбраны, то компонент возвращает матрицу "страница-для-блока", иначе компонент продолжает работу на этапе 503. На этапе 503 компонент выбирает следующий блок выбранной страницы. На этапе 504 принятия решения, если все блоки выбранной страницы уже были выбраны, то осуществляется переход в цикле на этап 501 для выбора следующей страницы, иначе компонент продолжает работу на этапе 505. На этапе 505 компонент вычисляет важность выбранного блока для выбранной страницы. На этапе 506 компонент устанавливает важность выбранного блока для выбранной страницы и затем осуществляется переход в цикле на этап 503 для выбора следующего блока выбранной страницы.
Фиг.6 изображает схему последовательности операций, которая иллюстрирует обработку (работу) компонента генерации матрицы "блок-для-изображения" в одном варианте осуществления. На этапах 601-607 компонент в циклах выбирает каждую страницу, каждый блок в пределах каждой страницы и каждое изображение в пределах каждого блока и устанавливает важность изображения для выбранного блока. На этапе 601 компонент выбирает следующую страницу из хранилища Web-страниц. На этапе 602 принятия решения, если все страницы уже были выбраны, то компонент возвращает матрицу "блок-для-изображения", иначе компонент продолжает работу на этапе 603. На этапе 603 компонент выбирает следующий блок выбранной страницы. На этапе 604 принятия решения, если все блоки выбранной страницы уже были выбраны, то осуществляется переход в цикле на этап 601, чтобы выбрать следующую страницу, иначе компонент продолжает работу на этапе 605. На этапе 605 компонент подсчитывает количество изображений выбранного блока. На этапе 606 компонент выбирает следующее изображение выбранного блока. На этапе 607 принятия решения, если все изображения выбранного блока уже были выбраны, то осуществляется переход в цикле на этап 603, чтобы выбрать следующий блок, иначе компонент продолжает работу на этапе 608. На этапе 608 компонент устанавливает важность выбранного изображения для выбранного блока и затем в цикле переходит к этапу 606 для выбора следующего изображения выбранного блока.
Специалистам ясно, что хотя конкретные варианты осуществления системы анализа ссылок были описаны с целью иллюстрации, различные модификации могут быть сделаны без отрыва от объема и контекста изобретения. Соответственно изобретение не ограничено ничем, кроме прилагаемой формулы изобретения.
1. Способ выполнения поиска и выдачи результатов поиска пользователю, реализуемый в компьютерной системе и основанный на связанности посредством ссылок между изображениями в пределах блоков в Web-страницах, содержащий этапы:
вычисляют индикаторы важности блока в Web-странице для этой Web-страницы;
вычисляют индикаторы важности Web-страницы для блока в этой Web-странице;
вычисляют индикаторы важности изображения для блока в Web-странице и
вычисляют индикаторы связанности "изображение-с-изображением" изображения с другим изображением посредством объединения индикаторов важности блока в Web-странице для Web-страницы, индикаторов важности Web-страницы для блока в Web-странице и индикаторов важности изображения для блока в Web-странице, генерируют кластеры связанных изображений на основе вычисленных индикаторов связанности изображения с другим изображением,
принимают от пользователя выбор изображения блока в Web-станице в качестве запроса на поиск;
идентифицируют кластер связанных изображений, который включает в себя выбранное изображение и
выдают пользователю индикацию Web-страниц, которые содержат изображения из идентифицированного кластера в качестве результата поиска в ответ на запрос поиска.
2. Способ по п.1, в котором индикаторы важности Web-страницы для блока в этой Web-странице являются вероятностями того, что пользователь выберет ссылку от каждого блока, которая будет вести на каждую другую Web-страницу.
3. Способ по п.1, в котором индикаторы важности блока в Web-странице для этой Web-страницы являются вероятностями того, что пользователь сосредоточится на каждом блоке этой Web-страницы.
4. Способ по п.1, в котором индикаторы важности изображения для блока в Web-странице являются вероятностями того, что пользователь сосредоточится на каждом изображении каждого блока.
5. Способ по п.1, в котором индикаторы важности Web-страницы для блока в этой Web-странице являются вероятностями того, что пользователь выберет ссылку от каждого блока, которая будет вести на каждую другую Web-страницу, индикаторы важности блока в Web-странице для этой Web-страницы являются вероятностями того, что пользователь сосредоточится на каждом блоке этой Web-страницы, и индикаторы важности изображения для блока Web-страницы являются вероятностями того, что пользователь сосредоточится на каждом изображении каждого блока этой Web-страницы.
6. Способ по п.1, включающий в себя вычисление ранга изображений из индикаторов "изображение-с-изображением".
7. Способ по п.6, в котором вычисленный ранг основан на вероятности того, что пользователь, начиная с произвольного изображения, будет переходить к другому изображению после произвольно большого количества переходов между изображениями.
8. Способ по п.1, в котором индикаторы "изображение-с-изображением" вычисляются следующим образом:
WI=YTWBY,
где WI - матрица индикаторов "изображение-с-изображением", Y - матрица индикаторов "изображение-с-блоком", и
WB=ZX,
где WB - матрица индикаторов "блок-с-блоком", Z - матрица индикаторов важности Web-страницы для блока в этой Web-странице, и X - матрица индикаторов важности блока в Web-странице для этой Web-страницы.
9. Способ выполнения поиска и выдачи результатов поиска пользователю на основании связанных изображений на Web-страницах, имеющих ссылки, причем каждая ссылка ведет от блока на Web-странице, содержащей изображение, на Web-страницу, имеющую другой блок в Web-странице, которая содержит другое изображение, реализованный в компьютерной системе и содержащий этапы:
для каждого изображения вычисляют для каждого другого изображения вероятность того, что, если пользователь просматривает это изображение, этот пользователь выберет ссылку от блока на Web-странице, содержащей это изображение, которая ведет к другой Web-странице, имеющей блок, который содержит другое изображение;
для каждого изображения генерируют векторное представление изображения на основании вычисленных вероятностей и идентифицируют кластеры изображений на основании их векторных представлений, причем изображения в кластере являются связанными, принимают от пользователя выбор изображения блока в Web-странице в качестве запроса на поиск;
идентифицируют кластер связанных изображений, который включает в себя выбранное изображение, и
выдают пользователю индикацию Web-страниц, которые содержат изображения из идентифицированного кластера в качестве результата поиска в ответ на запрос поиска.
10. Способ по п.9, в котором генерирование векторного представления включает в себя выбор векторных представлений, которые минимизируют целевую функцию.
11. Способ по п.10, в котором целевая функция является суммой квадрата расстояния между векторными представлениями для каждой пары изображений, умноженной на значение подобия для пары изображений, которое выведено из вычисленных вероятностей.
12. Способ по п.9, в котором вычисление вероятности включает в себя вычисление вероятностей, которые указывают вероятность того, что пользователь выберет ссылку от каждого блока в Web-странице, которая будет вести на каждую другую Web-страницу, вероятностей, которые указывают вероятность того, что пользователь сосредоточится на каждом блоке этой Web-страницы, и вероятностей, которые указывают вероятность того, что пользователь сосредоточится на каждом изображении каждого блока в Web-странице.
13. Компьютерная система для выполнения поиска и выдачи результатов поиска пользователю на основе связанности между изображениями в пределах блоков Web-страниц, содержащая
индикаторы важности Web-страницы для блока;
индикаторы важности блока для Web-страницы;
индикаторы важности изображения для блока в Web-странице;
средство для вычисления индикаторов связанности "изображение-с-изображением" изображения с другим изображением посредством объединения индикаторов важности блока Web-страницы для этой Web-страницы, индикаторов важности Web-страницы для блока в этой Web-странице и индикаторов изображения для блока в Web-странице; средство для приема от пользователя выбора изображения блока в Web-странице в качестве запроса на поиск;
средство для идентификации кластера связанных изображений, который связан с выбранным изображением, и
средство для выдачи пользователю индикации Web-страниц, которые содержат изображения из идентифицированного кластера в качестве результата поиска в ответ на запрос поиска.
14. Компьютерная система по п.13, включающая в себя средство для вычисления индикаторов важности Web-страницы для блока как вероятностей того, что пользователь выберет ссылку от каждого блока, которая будет вести на каждую другую Web-страницу.
15. Компьютерная система по п.13, включающая в себя средство для вычисления индикаторов важности блока для Web-страницы как вероятностей того, что пользователь сосредоточится на каждом блоке этой Web-страницы.
16. Компьютерная система по п.13, включающая в себя средство для вычисления индикаторов важности изображения для блока в Web-странице как вероятностей того, что пользователь сосредоточится на каждом изображении каждого блока этой Web-страницы.
17. Компьютерная система по п.13, включающая в себя средство для вычисления ранга изображений из индикаторов "изображение-с-изображением".
18. Компьютерная система по п.17, в которой вычисленный ранг основан на вероятности того, что пользователь, начиная с произвольного изображения, будет переходить к другому изображению после произвольно большого количества переходов между изображениями.
