Разработка и реализация математической модели графической поисковой системы тема диссертации и автореферата по ВАК РФ 05.13.01, кандидат технических наук Мирошкин, Алексей Владимирович

• Мирошкин, Алексей Владимирович
• кандидат технических наук
• 2005

Оглавление диссертации кандидат технических наук Мирошкин, Алексей Владимирович

Список иллюстраций

Список таблиц

Введение

ГЛАВА 1. Анализ задачи построения поисковой системы по содержанию изображений

1.1. Введение в поиск изображений по содержанию.

1.1.1. Области применения.

1.1.2. Типы поиска по содержанию изображений.

1.2. Понятие поисковой системы и принципы поиска информации

1.2.1. Булевская модель.

1.2.2. Векторная модель.

1.2.3. Вероятностная модель.

1.3. Вопросы описания и обработки изображений.

1.3.1. Цвет.

1.3.2. Применение линейных фильтров для обработки изображений

1.3.3. Определение границ объектов на изображении

1.3.4. Текстура.

1.4. Поиск на основе графических примитивов.

1.4.1. Цветовые характеристики.

1.4.2. Характеристики текстуры

1.4.3. Характеристики контура.

1.5. Обзор поисковых систем по содержанию изображений

1.5.1. Excalibur Visual Retrieval Ware.

1.5.2. ImageFinder.

1.5.3. IMatch.

1.5.4. QBIC.

1.5.5. VIR Image Engine.

1.6. Парадигма контекстно-зависимого распознавания

1.7. Выводы.

ГЛАВА 2. Модель поисковой системы

2.1. Математическая модель поисковой системы

2.2. Анализ изложенной модели.

2.3. Методы построения числового описания графического объекта.

2.3.1. Модифицированный алгоритм arch height.

2.3.2. Алгоритм SDBMA.

Введение диссертации (часть автореферата) на тему «Разработка и реализация математической модели графической поисковой системы»

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

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

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

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

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

• Анализ современного состояния области исследований.

• Построение математической модели поисковой системы по содержанию изображений.

• Создание архитектуры ПС по содержанию изображений на основе математической модели.

• Анализ существующих методов построения числового описания содержания изображения и создание новых.

• Создание программного обеспечения, предназначенного для поиска изображений по содержанию.

• Экспериментальные исследования по оценке результатов поиска и характеристик производительности поисковой системы.

Методы исследования. Для выполнения поставленной задачи применялись методы функционального анализа, математического моделирования, теории информации, теории алгоритмов, численные методы, методы объектно-ориентированного анализа и проектирования программного обеспечения.

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

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

Практическое применение. Разработанная программная реализация была внедрена в исследовательском центре компании Reasoning Mind, Inc. Компания занимается созданием систем дистанционного обучения, ориентированных на школьников разных стран. Поисковая система используется в работе с учебными пособиями, содержащими большое количество графических материалов.

Апробация результатов работы. Основные положения и результаты диссертации были представлены на Всероссийской конференции по проблемам математики, информатики, физики и химии в 2002 г. (г. Москва, РУДЫ), Межрегиональной научно-технической конференции „Интеллектуальные информационные системы" в 2003 г. (г. Тула), ХЬ Всероссийской конференции по проблемам математики, информатики, физики и химии, секция „Оптические, математические и электронные методы обработки изображений и сигналов" в 2004 г. (г. Москва, РУДН), Международной конференции „Распределенные вычисления и грид-технологии в науке и образовании" в 2004 г. (г. Дубна), научном семинаре МНТОРС им. Попова в 2004 г. (г. Москва).

Публикации. По материалам диссертационной работы имеется 6 публикаций.

Диссертация состоит из 4 глав. Первая глава посвящена анализу постановки задачи построения поисковых систем по содержанию изображений. В разделе 1.1. дается введение в проблематику поисковых систем, рассмотрены основные понятия и изложены принципы их функционирования. Описаны области применения ПС и типы поиска по содержанию, такие как точное соответствие, композиционное сходство и семантическое соответствие. Само понятие ПС и принципы поиска информации представлены в разделе 1.2., рассмотрены основные модели построения поисковых систем - булевская (раздел 1.2.1.), векторная (раздел 1.2.2.) и вероятностная (раздел 1.2.З.). Раздел 1.3. посвящен вопросам описания и обработки изображений. В разделе 1.3.1. рассматривается понятие цвета и цветовых пространств, описываются линейные, нелинейные и равномерные цветовые пространства. В 1.3.2. описано применение линейных фильтров для обработки изображений. В разделе 1.3.3. рассматривается вопрос определения границ объектов на изображении, в частности, детекторы границ на основе лапласиана и градиентов. Раздел 1.3.4. посвящен применению текстур для описания содержания изображения. В разделе 1.4. предлагается подход к организации поиска изображений по содержанию на основе графических примитивов, таких как цвет, текстура и контуры. Обзор существующих поисковых систем по содержанию изображений приведен в разделе 1.5. В последнем разделе главы описана парадигма контекстно-зависимого распознавания.

Глава 2 диссертационной работы посвящена решению поставленной задачи в части разработки методов построения поисковой системы по содержанию изображений. В разделе 2.1. представлена математическая модель поисковой системы, сделана попытка формализации процесса построения поисковой системы. Раздел 2.2. посвящен анализу деталей математической модели и содержит указания к методике построения поисковой системы. В разделе 2.3. описаны методы построения числового описания объектов на изображении, разработанные в рамках диссертационной работы. Это модифицированный алгоритм arch height и алгоритм SDBMA. Результаты главы 2 диссертации, имеют прикладное значение и используются при проектировании и практической реализации поисковой системы.

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

Четвертая глава посвящена реализации поисковой системы и анализу ее эффективности. В разделе 4.1. описана функциональность ПС и основные сценарии взаимодействия пользователя с ПС. В разделе 4.2. приведена программная архитектура поисковой системы с использованием нотации 11МЬ, даны пояснения по аспектам реализации. В разделе 4.3. изложены общие принципы реализации системы, рассмотрены технологии, которые применялись при реализации. В разделе 4.4. приведен анализ результатов работы поисковой системы.

Заключение диссертации по теме «Системный анализ, управление и обработка информации (по отраслям)», Мирошкин, Алексей Владимирович

ЗАКЛЮЧЕНИЕ

Основными теоретическими и практическими результатами являются:

• Построена математическая модель поисковой системы по содержанию изображений

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

• Предложены два новых метода построения числового описания объекта на изображении

• Предложены методы оптимизации поиска изображений

• Описан подход к построению распределенной поисковой системы, создана ее модель и описаны протоколы взаимодействия компонент такой системы

• Создана программная реализация поисковой системы по содержанию изображений

• Проведены экспериментальные исследования по оценке результатов поиска и характеристик производительности поисковой системы.

Список литературы диссертационного исследования кандидат технических наук Мирошкин, Алексей Владимирович, 2005 год

1. Люггер Д. Искусственный интеллект. — М.: Вильяме, 2003.

2. Gudivada V., Raghavan V., Grosky W. Information retrieval on the World Wide Web // IEEE Transactions Internet Computing. — No 10. — 1997.

3. Chang С. C., Lee S. Retrieval of Similar Pictures on Pictorial Databases // Pattern Recognition. — No 7. — 1991.

4. Enser P. G. B. Query Analysis in a Visual Information Retrieval Context // Journal of Document and Text Management. — No 1. 1993.

5. Kato T. Database Architecture for Content-Based Image Retrieval // Proceedings of Society of the Photo-Optical Instrumentation Engineers: Image Storage and Retrieval. — San Jose, California, USA, 1992.

6. Bimbo A. D. Visual Information Retrieval. — New York: Morgan Kaufmann, 1999.

7. Rui Y., Huang T. S., Chang S.-F. Image Retrieval: Current Techniques, Promising Directions, and Open Issues // Journal of Visual Communication and Image Representation. — No 1. — 1999.

8. Batley S. Visual Information Retrieval: Browsing Strategies in Pictorial Databases // 12th International Online Information Meeting: ONLINE88 Information. — London, England, 1988.

9. Cavnar W., Gillies A. Data retrieval and realities of document donversion // 1st Annual Conference on the Teory and Practice of Digital Libraries. — College Station, TX, USA, 1994.

10. Agnew В., Faloustos C. Multimedia index over Web // SPIE Conference on Storage and retrieval. — Pittsburgh, PA USA, 1997.

11. Jacobs C., Finkelstein A., Basri R. Fast multiresolution image querying // SIGGRAPH-95. 1995.

12. Enser P. Query analysis in a visual information retrieval context // Document and Text Management. — No 1. — 1993.

13. Benitez A., Beigi M. Using relevance feedback in content-based image metasearch // IEEE Internet Computing. — No 4. — 1998.

14. Booch G., Rumbaugh J., Jacobson I. The Unified Modelling Language User Guide. — MA: Addison-Wesley, 1998.

15. Booch G.} Rumbaugh J., Jacobson I. The Unified Modelling Language Reference Manual. — MA: Addison-Wesley, 1998.

16. Baeza-Yates R., Riberio-Neto B. Modern Information Retrieval. — New York: Addison-Wesley, 1999.

17. Klass W., Sheth A. Special issue on metadata for digital media // SIGMOD Record. No 4. - 1994.

18. Новиков Ф. Дискретная математика для программистов. — СПб: Питер, 2001.

19. Bookstein A. Implication of Boolean structure for probabalistic retrieval // 8th Annual International ACM/SIGIR Conference. — Denver, USA, 1985.

20. Salton G. The SMART retrieval system. Experiments in Automatic Document Processing. — MA: Prentice Hall, 1971.

21. Saltón G., Lesk E. Computer evaluation of indexing and text processing // Journal of ACM. — No 8. — 1968.

22. Robertson S., Jones K. Relevance weighting of search terms // Journal of American Society for Information Sciences. — No 3. — 1976.

23. Fuhr N. Probabilistic models in information retrieval // Information Processing and Management. — No 25. — 1989.

24. Croft W., Harper D. Using probabilistic models of retrieval without relevance information // Information Technology: Research and Development. — No 2. — 1983.

25. Furuta R. Defining and using structure in digital documents // 1st Annual Conference on the Teory and Practice of Digital Libraries. College Station, TX, USA, 1994.

26. Swain M., Ballard D. Color Indexing // Int. Journal of Computer Vision. No 1. - 1991.

27. Nathans J., Thomas D., Hogness D. Molecular genetics of human color vision: The genes encoding blue, green and red pigments // Science 232. — No 1. 1986.

28. Marr D., Hildreth E. Theory of edge detection // Proceedings of Royal Society of London, B207. — 1980.

29. Canny J. A Computational Approach to Edge Detection // IEEE Trans, on PAMI. No 8. - 1986.

30. Ma W., Manjuhath B. Texture features and learning similarity // IEEE Conference on Computer Vision and Pattern Recognition. — Chicago, 1996.

31. Card S., MacKinlay J., Shneiderman B. Readings in Information Visualisation. — NY: Morgan Kauffman, 1998.

32. Swain M. J., Ballard D. H. Color indexing // International Journal of Computer Vision. — No 7. — 1991.

33. Flickner M., Sawhney H., Niblack W. Query by image and video content: the QBIC system // IEEE Computer. — No 9. — 1995.

34. Strieker M., Orengo M. Similarity of color images // Conference Storage and Retrieval for Image and Video Databases III. — San Jose, CA, USA, 1995.

35. Rubner Y., Tomasi C., Guibas L. The earth movers distance as a metric for image retrieval // International Journal of Computer Vision. — No 2. — 1999.

36. Pass G., Zabih R., Miller J. Comparing images using color coherence vectors // ACM International Conference on Multimedia. — Boston, MA, USA, 1996.

37. Strieker M., Dimai A. Color indexing with weak spatial constraints // Storage and Retrieval for Image and Video Databases IV. San Jose, CA, USA, 1996.

38. Huang J., Kumar S., Mitra M. Spatial color indexing and applications // IEEE International Conference on Computer Vision (ICCV). Bombay, India, 1998.

39. Ashley J., Barber R., Flickner M. Automatic and semi-automatic methods for image annotation and retrieval in QBIC // Conference Storage and Retrieval for Image and Video Databases III. — San Jose, CA, USA, 1995.

40. Chang J. S. S. Local color and texture extraction and spatial query // IEEE International Conference on Image Processing. — Lausanne, Switzerland, 1996.

41. Wang J., Li J., Wiederhold G. SIMPLIcity: Semantics-sensitive integrated matching for picture libraries // Advances in Visual Information Systems (VISUAL). — Lyon, France, 2000.

42. Liu F., Picard R. Periodicity, directionality, and randomness: wold features for image modeling and retrieval // IEEE Transactions on PAMI. — No 7. — 1996.

43. Puzicha J., Rubner Y., Buhmann J. Empirical evaluation of dissimilarity measures for color and texture // IEEE International Conference on Computer Vision (ICCV). — Kerkyra, Greece, 1999.

44. Dimai A. Rotation invariant texture description using general moment invariants and Gabor filters // Scandinavian Conference on Image Analysis (SCIA). — Kangerlussuaq, Greenland, 1999.

45. Chen C. H. A study of texture classification using spectral features // In Proceedings of the 6th International Conference on Pattern Recognition. — Boston, MA, 1982.

46. Carlucci L. A formal system for texture languages // Pattern Recognition. — No 1. — 1972.

47. Haralick R. M., Shanmugam K., Dinstein I. Textural features for image classification // IEEE Transactions on Systems, Man and Cybernetics. — No 3. — 1973.

48. Veltkamp R., Hagedoorn M. State-of-the-art in shape matching // Technical Report UU-CS. No 27. - 1999.

49. Hu M. Visual pattern recognition by moment invariants // IEEE Trans, on Information Theory. — Vol. IT-8. — 1962.

50. Zahn C., Roskies R. Fourier descriptors for plane closed curves // IEEE Transactions on Computers. — No 3. — 1972.

51. Mehra P., Wah В. Artificial Neural Networks: Concepts and Theory. — IEEE Computer Society Press, 1992.

52. Уоссермен Ф. Нейрокомпьютерная техника. — СПб: Мир, 1992.

53. Кальоти Д. От восприятия к мысли. — М.: Мир, 1998.

54. Gordon I. Theories of Visual Perceptions. — John Wiley and Son, 1997.

55. Мирошкин А. О вопросе построения поисковых систем по содержанию изображений // Тезисы XL Всероссийской конференции по проблемам математики, информатики, физики и химии. Москва: РУДН, 2004.

56. Мирошкин А., Гостев И. Математическая модель одного класса поисковых систем // Вестник Российского Университета Дружбы Народов, серия 'Прикладная и компьютерная математика', Т. 3, № 1. — 2004.

57. Гостев И. М. О методах распознавания графических образов // Изв. РАН ТиСУ. № 1. - 2004.

58. Дейт К. Д. Введение в системы баз данных. — М.: Вильяме, 1999.

59. Мирошкин А. Об одном методе ранжирования формы объектов в графических поисковых системах // Тезисы межрегиональной научно-технической конференции 'Интеллектуальные информационные системы'. — Тула, 2003.

60. Saltón G. Automatic Text Processing: The Transformation, Analysis, and Retrieval of Information by Computer. — MA: Addison-Wesley, 1989.

61. Bates M. The design of browsing and berrypicking techniques for online search interface // Online Review. — No 2. — 1989.

62. Мирошкин А. Применение алгоритма Arch height в системе поиска изображений // Тезисы межрегиональной всероссийской конференции по проблемам математики, информатики, физики и химии. — Москва, 2002.

63. Croft W. What do people want from information retrieval? // D-Lib Magazine. — No 11. — 1995.

64. Arms W., Blanchi C., Overly E. An Architecture for Informtaion in digital libraries // D-Lib magazine. — No 2. — 1997.

65. Bertino E., Martino L. Object-Oriented Database Systems. — Addison-Wesley, 1993.

66. Abiteboul S. Querying semi-structured data. // Int. Conference on Database Theory. — 1997.

67. Hancock-Вeaulieu M., Fieldhouse M. An evaluation of interactive query expansion in online library catalogue with a graphical user interface // Journal of Documentation. — No 5. — 1995.

68. Berchtold S., Boehm C. Fast similarity search in multimedia databases // ACM SIGMOD Int. Conf. on Management of Data. — Tucson, Arizona, USA, 1997.

69. Hildreht C. The use and understanding of keyword searching in an university online catalog // Information Technology and Libraries. — No 16. — 1997.

70. Byers D. Full-text indexing of non-textual resources // 7th WWW Conference. 1998.

71. Кнут Д. Э. Искусство программирования. — М.: Addison-Wesley, 2000.

72. Fernandez M., Forescu D., Levy A. A query language for a Website management system // SIGMOD Record. — No 3. — 1997.

73. Bartell В., Cottrell G. Latent semantic indexing is an optimal special case of multidemensional scaling // 15th annual international ACM SGIR conference. — 1992.

74. Tanenbaum A. S., van Steen M. Distributed Systems: Principles and Paradigms. — Prentice Hall, 2002.

75. Coulouris G., Dollimore J., Kindberg T. Distributed Systems: Concepts and Design. — Addison-Wesley, 2000.

76. Dolin R.} Agrawal D. Pharos: a scalable distributed architecture for locating heterogeneus information sources // 6th CIKM Conference. — Las Vegas, Nevada, USA, 1997.

77. Мирошкин А., Гостев И. О методах индексации больших потоков информации на основе систем распределенных вычислений. Дубна ОИЯИ, 2004.

78. Jeyong В., Omiecinski Е. Inverted file partitioning schemes in multiple disk systems // IEEE Transactions. — No 2. — 1995.

79. Gauch S., Wang G., Gomez M. ProFusion: Intelligent fusion from multiple distributed search engines // Journal of Universal Computing. — No 2. — 1996.

80. Мирошкин А., Гостев И. О методах индексации больших потоков информации на основе систем распределенных вычислений // Международная конференция 'Распределенные вычисления и грид-технологии в науке и образовании'. — Дубна ОИЯИ, 2004.

81. Wilson В. J. JXTA. NY: New Riders Publishing, 2002.

82. Gamma E., Helm R. Design Patterns. Elements of reusable Object-Oriented Software. — Addison-Wesley, 1995.

83. Робинсон С. для профессиналов. — M.: Лори, 2003.

84. Cooper A. About Face: The Essentials of User Interface design. — Boston: IDG Books, 1995.

85. Tague-Sutcliffe J. Measuring the informativeness of a retrieval process // 15th annual int. ACM SIGIR Conference on reasearch and development in information retrieval. — Copenhagen, Denmark, 1992.