Полный текст заданий.

Руководитель: Линский Е. М.

I. Определитель плагиата в рефератах

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

II. Кроссворд

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

III. Алгоритм для сжатия листингов на языке C.

Разработать архиватор для сжатия листингов программ на языке C. Хорошим кандидатом для данной задачи является словарный метод сжатия LZW. Этот алгоритм пытается найти одинаковые подстроки в тексте и закодировать их одним и тем же кодом.

IV. Искусственный интеллект для игры в шашки-поддавки

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

Руководитель: Гильмутдинов М. Р.

I. Алгоритмы изменения размеров изображения

  1. Выполнить загрузку в память BMP файла в формате RGB24. BMP файл представляется в виде одномерного массива, в котором данные, относящиеся к отдельным пикселам, записаны по строкам. Каждый пиксел представляется тремя байтами. Первый содержит значение компоненты R, второй - G и третий – B. Обратите внимание, формат BMP предусматривает, что размер строки изображения в байтах должен быть выравнен на границу двойного слова (д.б. кратным числу 4). При необходимости, недостающие байты должны быть добавлены в конце каждой строки.
  2. Для каждой компоненты R, G и B реализовать один из известных алгоритмов увеличения изображения в N раз по ширине и высоте (исключение - простое повторение пикселей) или предложить свой вариант решения.
  3. Проанализировать эффективность реализованного алгоритма:
    1. уменьшить исходное изображение в графическом редакторе (например, Picasa);
    2. восстановить исходный размер реализованным алгоритмом;
    3. вычислить пиковое отношение сигнал-шум (Peak Signal-to-Noise Ratio – PSNR) по исходному и восстановленному изображениям;
    4. выполнить пункты 3.2, 3.3 с помощью графического редактора и сравнить значения PSNR;
    5. провести визуальное сравнение результатов, выделить области изображения (критические области) с максимальными искажениями и описать их специфику;
    6. предложить вариант улучшения алгоритма за счет изменения обработки критических областей.

II. Алгоритмы увеличения кадровой скорости видеопоследовательности

  1. Прочитать AVI файл с видеопоследовательностью в формате RGB24.
  2. Реализовать один из известных алгоритмов преобразования кадровой скорости (Frame Rate Conversion - FRC) или предложить свой вариант решения. Алгоритм должен увеличивать кадровую скорость в N раз, где N - целое число. Суть алгоритма в интерполяции одного или нескольких недостающих кадров на основе информации из существующих соседних кадров.
  3. Проанализировать эффективность реализованного алгоритма:
    1. создать на основе исходной последовательности V1 новую (V2) путем удаления кадров с нечетными номерами из исходной;
    2. применить к V2 разработанный алгоритм и увеличить кадровую скорость в два раза, тем самым получить фильм V3 с кадровой скоростью, равной скорости исходного фильма;
    3. для кадров с нечетными номерами последовательностей V1 и V3 вычислить PSNR. Построить график, демонстрирующий эффективность разработанного алгоритма. По оси абсцисс отложить номер кадра, по оси ординат - PSNR;
    4. подобрать несколько последовательностей, на которых продемонстрировать достоинства и недостатки разработанного алгоритма.

III. Анализ методов, используемых в алгоритмах сжатия изображений без потерь

  1. Выполнить загрузку в память BMP файла в формате RGB24. BMP файл представляется в виде одномерного массива, в котором данные, относящиеся к отдельным пикселам, записаны по строкам. Каждый пиксел представляется тремя байтами. Первый содержит значение компоненты R, второй - G и третий - B. Обратите внимание, формат BMP предусматривает, что размер строки изображения в байтах должен быть выравнен на границу двойного слова (д.б. кратным числу 4). При необходимости, недостающие байты должны быть добавлены в конце каждой строки.
  2. Проанализировать статистические свойства элементов изображения – пикселей. Для каждой составляющей R, G и B выполнить следующие действия:
    1. вычислить коэффициент корреляции между каждой парой компонент изображения;
    2. построить автокорреляционную функцию r(x, y). Отобразить сечения трехмерного графика автокорреляционной функции, зафиксировав значения по оси y в точках (0, ±5, ±10, ±20). Шаг по оси x определить самостоятельно;
    3. построить гистограммы частот на основе значений компонент R, G, B. Гистограммы необходимо построить отдельно для каждой компоненты;
    4. оценить число бит, затрачиваемых при независимом, поэлементном кодировании компонент R, G, B.
  3. Изучить подходы, используемые для уменьшения пространственной избыточности при кодировании пикселей изображения.
    1. Предложить алгоритм предсказания значения пикселя по его соседям:
      1. для каждой компоненты изображения вычислить массив ошибок предсказания пикселей;
      2. построить гистограммы частот ошибок и оценить число бит при независимом, поэлементном кодировании ошибок предсказания;
      3. сравнить данные, полученные в 3.1.3 с данными из 2.3 и 2.4.
    2. Предложить алгоритм формирования новых компонент, учитывающий межкомпонентную корреляцию R, G и B, например, на основе преобразования RGB в YUV или YCbCr форматы:
      1. построить гистограммы частот ошибок и оценить число бит при независимом, поэлементном кодировании значений новых компонент;
      2. сравнить данные, полученные в 3.2.2 с данными из 3.1.3, 2.3 и 2.4.

IV.Алгоритмы детектирования движения в видеопоследовательности

  1. Прочитать AVI файл с видеопоследовательностью в формате RGB24.
  2. Разработать алгоритм выделения объектов на изображении. За основу взять, например, оператор Собеля (Sobel) для выделения контуров.
  3. Разработать алгоритм, основанный на анализе статистических свойств видеопоследовательности.
  4. Разработать алгоритм слежения за движущимися объектами, основанный на методе компенсации движения.
  5. Предложить алгоритмы нейтрализации влияния шумов камеры, изменения освещенности для уменьшения вероятности ложной тревоги при детектировании движения.

Список рекомендуемой литературы

  1. Красильников Н. Н. Цифровая обработка изображений. – М.: Вузовская книга, 2001.
  2. Ватолин Д., Ратушняк А. и др. Методы сжатия данных. – М.: Диалог-МИФИ. 2003. -384 с.
  3. Гонсалес Р., Вудс Р. Цифровая обработка изображений. – М.: Техносфера, 2006. -1072 с.
  4. Шапиро Л., Стокман Дж. Компьютерное зрение. – М.:Бином, 2006, -752 с.
  5. Сэломон Д. Сжатие данных, изображений и звука. – М.: Техносфера, 2004. -368 с.

Руководитель: Козлов А. В.

I. Debayering

Изображение, получаемое с видеокамер, обычно представлено в bayer формате, а не в формате R, G, B. Bayer формат формируется выходами сенсоров, каждый из которых улавливает один цвет (либо красный, либо синий, либо зеленый). При этом сенсоров, улавливающих зеленый цвет - 50%, красный цвет - 25%, синий цвет - 25%. Такое распределение обусловлено физическими свойствами человеческого глаза. Расположение сенсоров задано следующим шаблоном:

[ bgbgbg ]

[ grgrgr ]

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

II. Кодирование для систем хранения данных

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

Хранимый файл разбивается на k (k<n) сегментов, которые дополняются r (r=n-k) сегментами по специальному алгоритму. Каждый из n полученных сегментов записывается на отдельный носитель. В результате при поломке любых r носителей исходный файл может быть восстановлен из оставшихся k сегментов. Требуется разработать программу, обеспечивающую разбиение и восстановление файла по описанному алгоритму.

III. Cuda

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

Контактные данные

Директор: д.т.н. профессор 
Крук Евгений Аврамович

Адрес: 196128, Санкт-Петербург, ул. Московский пр, д. 149в
Телефон/Факс
: +7 (812) 494 70 52
E-mail: ictacademy@vu.spb.ru
Или воспользуйтесь online-формой

Описание: Опыт работ и направления исследований представлены в AcademyICT.pdf

Новости и События [все]

Наши партнеры


Проводимые конференции

Конференции, симпозиумы, семинары, проводимые при поддержке Академии ИКТ:

1. FRUCT Community Annual Conference, с 2007 г.
2. Redundancy2007. Международный симпозиум по проблемам избыточности в информационных и управляющих системах, 2007 г.
3. Redundancy2009. Международный симпозиум по проблемам избыточности в информационных и управляющих системах, 2009 г.
4. ISIT2011. 2011 IEEE International Symposium on Information Theory
5. Redundancy2012. Международный симпозиум по проблемам избыточности в информационных и управляющих системах, 2012 г.