• Вступ
• Цілі і завдання, які повинні вирішуватися
• Актуальність теми
• Передбачувана наукова новизна
• Плановані практичні результати
• Алгоритм контентно-залежного масштабування
• Висновки

Застосування комп'ютерної техніки в сучасному житті стало повсюдним. Величезна кількість галузей використовують обчислювальні машини для прискорення рішення задач. З появою могутніх графічних станцій, а також комп'ютерів, здатних вирішувати не тільки математичні задачі, але і візуалізувати складні технологічні процеси на екрані, починається нова ера в комп'ютерній промисловості.

Комп'ютерна графіка використовується практично у всіх наукових та інженерних дисциплінах для наочності сприйняття і передачі інформації.

Однією з задач комп'ютерної графіки є масштабування — зміна розміру зображення. При цьому залежно від типу графіки (растрова, векторна), масштабування здійснюється за різними алгоритмами. Якщо графіка векторна, то масштабування відбувається без втрат якості зображення, якщо растрова, то при масштабуванні відбувається втрата якості зображення, особливо при зміні розміру без збереження пропорцій.

Саме тому дуже важливою є розробка вдосконалених методів масштабування, зокрема контентно-залежних, в основі яких лежить попередній аналіз зображення.

Метою дослідження є вивчення існуючих способів масштабування зображень, можливостей модернізації та оптимізації цих способів, вдосконалення алгоритму, заснованого на попередньому аналізі зображення.

У ході дослідження повинні бути вирішені наступні завдання:

1. Виявлення основних недоліків існуючих алгоритмів, пошук можливостей їх усунення.
2. Розробка алгоритму, що аналізує зображення за його змістом і виявляє найбільш і найменш значущі ділянки зображення.
3. Розробка алгоритму, що масштабує зображення на основі отриманих при аналізі даних.
4. Програмна реалізація алгоритму, що забезпечує контентно-залежне масштабування.
5. Аналіз і порівняння результатів, отриманих при використанні розроблених алгоритмів та вже існуючих алгоритмів.

Завдання масштабування — змінення розмірів зображення — широко застосовується в різних сферах. Це завдання особливо актуальне для перенесення зображень на мобільні пристрої, де воно не може відображатися в повному масштабі, для розміщення зображень на сайтах. Збільшення зображень часто застосовується для більш детального огляду фрагмента зображення, при обробках зображень і т.д.

Основне завдання при масштабуванні — збереження достатньої якості зображення. Пошук ефективних способів реалізації даного алгоритму є предметом досліджень багатьох вчених різних країн світу. До них відносяться:

1. Джефф Етворд (колишній співробітник Vertigo Software, Поінт Річмонд, Каліфорнія). http://www.codinghorror.com/blog/2007/07/better-image-resizing.html
2. Шаї Авідан (співробітник Mitsubishi Electric Research Labs, Північна Америка). http://portal.acm.org/citation.cfm?id=1276377.1276390
3. Аріель Шамір (Техаський університет в Остіні). http://portal.acm.org/citation.cfm?id=1457515.1409064

Таким чином, тема дипломної роботи є досить актуальною на сьогоднішній день.

Існуючі найбільш поширені в даний час алгоритми масштабування зображень не забезпечують досить високої якості при зміні розміру. У зв'язку з цим планується вдосконалення алгоритму контентно-залежного масштабування. Передбачається поліпшення часових і візульних показників результатів роботи алгоритму.

Після закінчення роботи по розробці програмної системи планується отримати працездатний програмний проект, призначений для контентно-залежного масштабування зображень.

Також планується проведення комплексного аналізу та порівняння практичних аспектів реалізації різних алгоритмів масштабування.

Розглянемо алгоритм контентно-залежного масштабування Seam Carving — це алгоритм зміни розмірів зображення, який враховує вміст зображення (як називають автори — Content-Aware Image Resizing Algorithm). Вперше був запропонований у 2007 році.^[6]

Спосіб враховує вміст зображення: спочатку обчислюється важливість різних ділянок зображення, після чого змінюються в розмірі тільки ті частини, які, на думку алгоритму, є не такими важливими. Основні проблеми алгоритму: як визначити наскільки важливими є частини зображення, як знайти і стиснути менш важливі ділянки зображення і т. д.

Основні кроки алгоритму для горизонтального масштабування (для вертикального — аналогічно):

1. Знаходження енергії кожної точки. На цьому етапі необхідно визначити, які частини зображення є більш важливими, а які — менш важливими, виходячи їх цих даних, далі буде змінюватися розмір зображення.
2. Знаходження такого вертикального ланцюжка пікселів, щоб сумарна енергія пікселів, які входять в цей ланцюжок була мінімальною. Ланцюжок пікселів — це такий набір пікселів, що в кожному рядку вибрано рівно по одному пікселю, і сусідні пікселі в ньому поєднані сторонами або кутами. При знаходженні такого ланцюжка можливе видалення його з зображення, мінімально зачіпаючи інформаційне наповнення зображення.
3. Після знаходження ланцюжка з мінімальною енергією, необхідно його видалити, якщо виконується зменшення зображення, або розтягнути, якщо виконується збільшення.^[7]

Розглянемо алгоритм більш детально.

Крок 1. Для визначення важливості пікселя зображення необхідно вирахувати його енергію: чим більше енергія — тим важливіше точка. Існує безліч способів обчислення енергії. Одна з найпростіших функцій дає найбільш оптимальні результати:

Енергія пікселя дорівнює зміні кольору сусідніх пікселів в порівнянні з даними пікселом. Тобто чим більша різниця в кольорі між даними пікселем та сусідніми — тим більше його енергія.

Крок 2. Після визначення значення енергій необхідно вибрати ті пікселі у яких це значення мінімальне. Для початку необхідно визначити «правильний» ланцюжок пікселів — це набір точок, такий, що у кожному рядку зображення вибрано рівно 1 піксель, а пікселі в сусідніх рядках «з'єднані» або сторонами, або кутами (рисунок 1).

а)                          б)

Рисунок 1 — Приклад «правильних» (а) і «неправильних» (б) ланцюжків

Вибирати слід ланцюжок, в якому сума енергій пікселів, які входять до нього, мінімальна. Для його знаходження слід застосувати динамічне програмування. Спочатку створюється новий масив, який за розміром дорівнює масиву з енергіями пікселів. У цей масив для кожного пікселя записується сума елементів мінімального ланцюжка пікселів, який починається біля верхнього краю зображення і закінчується на даному пікселі.

Спочатку визначається який піксел з нижньої строчки зображення належить цьому ланцюжку: шуканий елемент буде мати найменше значення в масиві сум серед елементів нижньої строчки. Ланцюжки, які нас цікавлять закінчуються на пікселі з останнього ряду. Відповідно для всього малюнка мінімальний ланцюжок буде обраний як мінімальний з усіх мінімальних ланцюжків, які закінчуються на пікселях з нижньої строчки.

Після визначення пікселя, на якому закінчується мінімальний ланцюжок, можливо знаходження пікселя з передостаннього рядка. Як вже було написано, з нижнього пікселя ми можемо піти тільки в 3 сусідні пікселі на рядок вище: зліва-зверху, зверху або праворуч-зверху. Серед цих пікселів вибираємо піксел з мінімальним значенням в масиві сум, і переходимо до нього. Продовжуємо, поки на дійдемо до верхнього рядка.

Після виконання всіх цих операцій буде отриманий набір пікселів, які можливо змінити з мінімальними втратами для зображення.

Крок 3. Наше завдання — зміна розміру зображення. Збільшення та зменшення зображення трохи відрізняються, тому спочатку буде розглянуто зменшення, а потім вже збільшення.

Якщо необхідно зменшити ширину зображення на 1 піксель, то все просто: шукається вертикальний ланцюжок, як описано вище, і просто видаляється.

Якщо необхідно зменшення на більше значення, то виконується операція видалення ланцюжка стільки разів, скільки необхідно (щоразу при цьому треба буде шукати новий ланцюжок).

Слід звернути увагу, що операція зменшення зображення на n пікселів і операція зменшення зображення на 1 піксель n раз не є еквівалентними. При зменшенні на 1 піксель n разів, для кожного з проміжних зображень шукається енергія пікселів, а якщо відразу відбувається зменшення на n, то енергія пікселів береться з вихідного зображення. Приклад зменшення показаний на рисунках 2, 3 і 4.^[7]

Рисунок 2 — Оригінальне зображення




Рисунок 3 — Зменшене по горизонталі зображення




Рисунок 4 — Зменшене по вертикалі зображення

При збільшенні зображення не можна просто вибирати ланцюжки та їх «розтягувати». Необхідно брати не один мінімальний ланцюжок, а стільки, скільки треба, щоб доповнити малюнок до потрібної ширини (як при звичайному розтяганні), але збільшувати зображення слід поетапно: так, щоб на кожному етапі охоплювалося як можна більше «не важливих» частин зображення, і як можна менше «важливих». Один з варіантів розбиття на етапи такий, що на кожному етапі зображення не збільшується більше, ніж на 50%. Приклад збільшення показаний на рисунках 5 та 6.^[6]

У результаті аналізу існуючих алгоритмів масштабування були виявлені їх основні недоліки. Для оптимізації масштабування був запропонований метод контентно-залежного масштабування. Надалі планується вдосконалення алгоритму і його програмна реалізація.

1. Thyssen A. Resize and Scaling. // Examples of ImageMagick Usage (Version 6), 2009. — http://www.imagemagick.org/Usage/resize/
2. Билинейная интерполяция. // Статья википедии — свободной Интернет-энциклопедии — http://ru.wikipedia.org/wiki/Билинейная_интерполяция
3. Бикубическая интерполяция. // Статья википедии — свободной Интернет-энциклопедии — http://ru.wikipedia.org/wiki/Бикубическая_интерполяция
4. Алгоритмы масштабирования пиксельной графики // Статья википедии — свободной Интернет-энциклопедии — http://ru.wikipedia.org/wiki/Алгоритмы_масштабирования_...
5. Ronald E. Crochiere, Lawrence R. Rabiner. Multirate digital signal processing. — Prentice-Hall, 1983. — http://www.flipkart.com/multirate-digital-signal-processing-lawrence-book-0136051626
6. Liquid Rescale. // Content-aware resizing for the GIMP, 2009. — http://liquidrescale.wikidot.com/en:examples
7. Михаил М. Liquid Resize своими руками. — Habradigest, №7, январь 2009. — http://habradigest.ru/hd/habradigest_07.pdf
8. Конник М. Новый метод масштабирования растровых изображений с учётом их содержимого Liquid Rescale. — Записки дебианщика, 2007. — http://mydebianblog.blogspot.com/2007/09/blog-post.html
9. Шеховцов С.О. Контентно-зависимое масштабирование изображений с использованием алгоритма Seam Carving // Искусственный интеллект.— Донецк: ІПШІ МОН і НАН України “Наука і освіта”, 2010.
10. Шеховцов С.О. Анализ недостатков алгоритмов масштабирования. Контентно-зависимое масштабирование // ІУС та КМ-2010 — Матеріали І всеукраїнської науково-технічної конференції студентів, аспірантів та молодих вчених — Донецьк: ДонНТУ, 19-21 травня 2010. — 634с.

При написанні даного реферату, магістерська робота ще не завершена. Остаточне завершення: грудень 2010 року. Повний текст роботи та всі матеріали по темі можуть бути отримані у автора або його керівника після зазначеної дати.