Способ и система адаптивного переформатирования цифровых изображений

Способ и система адаптивного переформатирования цифровых изображений

Иллюстрации

Показать все

Реферат

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

Среди известных решений в этой области можно упомянуть следующие технологии и методы: линейное масштабирование, кадрирование, переформатирование (retargeting), прореживание швов (seam carving), ретуширование. Остановимся более подробно на анализе перечисленных выше технологий.

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

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

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

Обычно двумерная интерполяция производится как серия одномерных интерполяций во взаимно перпендикулярных направлениях. Например, изобретение, описанное в патенте США № 6,915,026 [1], предполагает увеличение изображения в два этапа: сначала в вертикальном направлении, затем - в горизонтальном, предварительно рассчитывая и сохраняя коэффициенты для интерполяции. Этот метод имеет недостаток: все одномерные интерполяции производятся параллельно координатным осям изображения, и проявляющиеся артефакты обнаруживают лежащую в их основе координатную решетку. Некоторые методы предполагают предварительную низкочастотную фильтрацию в диагональных направлениях, но это, к сожалению, ухудшает качество самого изображения. Патенты США № 5,719,967 [2] и 6,606,093 [3] описывают специальные приемы для подавления зубчатости краев в изображении.

Решение, описанное в патенте США № 5,446,804 [4], использует предварительно рассчитанную субпиксельную карту краев. Для каждого интерполируемого пикселя находятся четыре ближайших соседа. Если ни один из соседних пикселей не отсекается краем от остальных, искомое значение вычисляется как сумма этих соседей с весами. Если же соседи лежат по разные стороны от края, для искомого пикселя вычисляется промежуточное значение с использованием двух диагональных пикселей, лежащих по одну сторону края, выбор которых осуществляется на основе карты краев. Затем искомое значение в позиции, лежащей по другую сторону границы, заменяется на значение, полученное с помощью соседей, лежащих по одну сторону края, и вычисленной величины. Такое решение позволяет получить изображение с резкими границами, однако содержащее зубчатые края.

Ниже перечислены методы, позволяющие преодолеть эффект зубчатых краев путем ухода от интерполяции вдоль оси, лежащей в основе координатной решетки, а также производящие двумерное увеличение, то есть одновременно в вертикальном и горизонтальном направлениях. Первый метод, описанный в статье Li, X., and M.Orchard, "New Edge Directed Interpolation," IEEE International Conference on Image Processing, Vancouver, Sept. 2000 [5], основывается на предположении о существовании геометрического дуализма между ковариациями изображений с низким и высоким разрешением. Предохранение краев на изображении обуславливается адаптивностью значений коэффициентов к интерполяции произвольно направленного края-ступени. Данный метод предназначен для увеличения в кратное двум число раз. Интерполяция производится в два прохода, сначала вычисляются пиксели с координатами (2i+1, 2j+1), используя известные значения в позициях (2i, 2j). Затем аналогичная процедура, с поворотом на 45 градусов, производится над остальными пикселями. Каждый пиксель находится как линейная комбинация ближайших четырех соседей, задача определения коэффициентов линейной комбинации решается методом наименьших квадратов. Данный метод интерполяции обеспечивает приемлемые результаты, за исключением областей с текстурой, в которых предположение о геометрическом дуализме не выполняется.

Второй метод, описанный в статье Yu, X., Morse, В. and T.Sederberg, 2001, "Image Reconstruction Using Data-Dependent Triangulation", IEEE Computer Graphics and Applications, vol.21 No.3, pp.62-68 [6], производит триангуляцию поверхности, рассматривая значения яркости как высоту точек над некоторым нулевым уровнем. Авторы данного метода конструируют сетку триангуляции и восстанавливают изображение линейной интерполяцией интенсивности внутри треугольника, используя значения в вершинах. Этот подход основывается на методе data-dependent triangulation (DDT) с другим методом оптимизации и целевой функцией. Таким образом, триангуляция предохраняет края (резкие перепады яркости) и улучшает качество изображения. Однако этот метод довольно сложен с вычислительной точки зрения, так как триангуляция производится итеративно.

Иногда увеличение изображения производится в два этапа. Сначала вычисляются неизвестные значения яркости, затем для увеличения резкости изображения и улучшения краев производится постобработка изображения. Например, патент США № 6,714,688 [7] описывает метод постобработки изображения для увеличения резкости. Сначала производится билинейная интерполяция изображения, затем производится постобработка краев с помощью движущегося окна. Размер окна определяется исходя из степени увеличения. Сначала к пикселям внутри окна применяется низкочастотный фильтр для выделения высокочастотной составляющей изображения. Высокочастотная составляющая затем суммируется с низкочастотной с некоторым коэффициентом, определяемым на основе локальных яркостных характеристик. Затем края дополнительно обрабатываются с помощью специальной кривой преобразования яркости.

Метод, описанный в патентной заявке ЕР №1533899 [8], направлен также на изменение размеров цифрового изображения посредством следующих этапов: интерполяции вдоль границ и дополнительной постобработки. Сначала изображение увеличивается в 2n раз, после чего уменьшается до нужных размеров. Далее производится постобработка краев. Данный метод обеспечивает хорошие результаты, но является достаточно сложным с вычислительной точки зрения.

Известны также способы интеллектуальной обрезки или кадрирования изображения (фотографии), которые предназначены для изменения соотношения геометрических размеров (соотношения сторон) изображения, т.е. отношения его ширины к высоте, путем обрезки нижней и/или верхней (левой и/или правой) части изображения. Термин «интеллектуальная» означает, что обрезка фотографии производится на основе анализа ее содержания с целью исключить обрезку важных объектов, запечатленных на фотографии. Потребность в изменении соотношения сторон фотографии возникает, например, у пользователей цифровых фотокамер, желающих распечатать свои цифровые снимки: обычная цифровая фотография имеет соотношение сторон 4:3, тогда как стандартные листы фотобумаги в лабораториях печати имеют соотношение сторон 3:2.

Существуют два подхода к решению задачи обрезки фотографии, не связанных с анализом ее содержания. Первый подход заключается в обрезке верхнего и нижнего краев фотографии в отношении 50% на 50%, или 20% на 80%, соответственно. Это означает, что если высота фотографии должна быть уменьшена на 1 см, то сверху и снизу будут отрезаны горизонтальные полосы высотой, соответственно, 5 и 5 мм, или 2 и 8 мм. Во многих случаях этот подход не приводит к обрезке важных объектов на фотографии, расположенных в центре снимка. Однако в тех нередких случаях, когда объект съемки, например, человек, находится близко к краю фотографии, этот подход может приводить к обрезке частей лица, головы, или других частей изображения человека.

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

Основная проблема в задаче автоматической обрезки заключается в определении и сегментации главного объекта (объектов) на изображении. Методы определения главного объекта разделяются на две категории. Методы, основанные на обработке пикселей, выделяют отдельные пиксели или небольшие группы пикселей, которые, как правило, соответствуют частям объектов, запечатленных на фотографии. К числу таких методов относятся, например, методы выделения краев. Методы, основанные на обработке областей, выделяют области, соответствующие целым семантически значимым объектам на изображении.

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

Программа XV (www.trilon.com/xv) [9] имеет функцию автоматического обрезания изображений, работающую следующим образом.

1. Выделяются граничные строки и столбцы изображения (верхняя и нижняя строки, крайние столбцы слева и справа).

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

3. Операции 1-2 повторяются необходимое число раз.

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

В патенте США № 5,978,519 [10] рассматривается метод обрезания изображений, основанный на дифференциации уровней интенсивности. Типичное изображение содержит как области однородной интенсивности и цвета, так и области, где интенсивность и цвет значительно меняются. Например, портрет обычно содержит резкие яркостные переходы от главного объекта к фону. В описываемом методе размер изображения уменьшается, и оно делится на не перекрывающиеся блоки. Для каждого блока вычисляются среднее значение и дисперсия интенсивности. На основе распределения дисперсии в блоках выбирается порог, и все блоки с дисперсией выше пороговой отмечаются как области интереса. Области интереса затем вырезаются ограничивающим прямоугольником.

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

Функция интеллектуального обрезания пакета Microsoft Digital Image Suite 2006 [11] обладает возможностью определения лиц на портретах или семейных фотографиях. Программа предлагает некоторый вариант обрезки, после чего пользователь может выбрать нужное соотношение сторон из списка стандартных форматов печати. Кроме того, пользователь может задать размеры изображения в пикселях.

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

Патент США № 6,282,317 [12] описывает метод обнаружения главного объекта на изображении. Метод включает в себя получение цифрового изображения; извлечение областей произвольной формы и размера, соответствующих присутствующим на изображении объектам; группирование областей в более крупные области, соответствующие физически связанным объектам; извлечение для каждой области, как минимум, одной структурно выделяемой особенности и, как минимум, одной семантически выделяемой особенности; оценку для каждой выделенной области вероятности того, что эта область соответствует главному объекту.

Патент США № 6,654,506 [13] описывает метод кадрирования цифровых изображений, который включает ввод доверительной карты изображения, значение в каждой точке которой описывает важность информации в соответствующей точке изображения; выбор масштабирующего коэффициента и окна обрезки; кластеризацию областей доверительной карты для определения областей фона, вторичных областей и областей главного объекта; позиционирование окна обрезки в области главного объекта так, чтобы сумма значений доверия внутри окна была максимальной; и обрезку изображения по границам окна обрезки.

Выложенная заявка на патент США № 2002/0191861 [14] описывает автоматическое и полуавтоматическое кадрирование изображений, и, в частности, аппарат и метод использования электронной камеры для захвата и кадрирования изображений. Электронное устройство для кадрирования изображений включает средства обработки изображения, - в частности, электронный процессор и программируемое оборудование и/или программное обеспечение для обработки изображений. Устройство идентифицирует особенности композиции изображения и для каждой выделенной особенности находит похожую в некотором смысле особенность из числа предопределенных особенностей, хранимых в устройстве. Затем выбирается одно или несколько предопределенных композиционных правил, связанных с хранимыми особенностями. Устройство определяет одну или несколько подходящих границ кадрирования, применяя одно или несколько выбранных композиционных правил.

Интересная идея интеллектуального добавления фрагментов фотоизображения приводится в патентной заявке RU 2005137049 [15]. Согласно данной заявке данные фрагменты могут быть получены с помощью операций зеркального отображения/дублирования боковых частей изображения.

Наиболее близким к заявляемому изобретению является решение, описанное в выложенной заявке США №2007/0025637 [16]. Данное изобретение было частично опубликовано ранее в Setlur et al, "Automatic Image Retargeting" ACM International Conference on Mobile and Ubiquitous Multimedia (MUM) 2005, v.154, pp.59-68 [17]. Авторы описали новый подход для автоматического переформатирования изображений (automatic image retargeting), сохраняющий пропорции важных объектов изображения при уменьшении размеров изображения. Для исходного изображения и заданного формата данный метод выполняет следующие действия. В первую очередь исходное изображение сегментируется на регионы с помощью анализа распределения цветовых и яркостных характеристик изображения. Затем создается карта важности пикселей/регионов исходного изображения на основе модели человеческого зрения и методов детектирования лиц людей на цифровых изображениях. Если заданный формат содержит все важные регионы, тогда изображение кадрируется. В противном случае, важные регионы исключаются из изображения, которое масштабируется согласно заданному формату. Затем важные регионы вставляются на модифицированное изображение, согласно степени важности и топологи. Описанная выше технология позволяет минимизировать потерю деталей изображения и снизить искажения, вносимые традиционными подходами. Также стоит отметить, что данный метод делает важные регионы ближе друг к другу, сохраняя их топологию.

В статье Shai Avidan, Ariel Shamir, "Seam Carving for Content-Aware Image Resizing ACM Transactions on Graphics, Volume 26, Number 3, SIGGRAPH 2007" [18] описывается эффективная процедура изменения размеров изображения, которая учитывает не только геометрические ограничения, но и содержание изображения. Также вводится понятие и определение оператора прореживания швов (seam carving), который используется как для уменьшения, так и увеличения изображения с учетом его содержания. Шов (seam) представляет собой связный оптимальный путь из пикселей изображения, причем оптимальность определяется с помощью функции энергии изображения. Неоднократное удаление или добавление швов позволяет добиться изменения формата/размера изображения.

По результатам анализа уровня техники можно сделать следующие выводы. В последнее время наблюдается непрерывный рост количества цифровых фотографий и изображений документов, которые получаются и отображаются с помощью различных устройств, таких как цифровая камера, мобильные телефоны, телевизионные устройства (в том числе высокой четкости) и т.д. Однако соотношение геометрических размеров (формат) цифрового изображения не всегда соответствует соотношению геометрических размеров области для отображения. Например, цифровой снимок имеет соотношение сторон 4:3, а печать осуществляется на бумаге с соотношением сторон 3:2. Для приведения в соответствие соотношения сторон цифрового снимка и области для отображения предлагается множество методов. Наиболее известны следующие методы: масштабирование, кадрирование и адаптивное добавление или дублирование частей изображения. Данные методы получили широкое распространение из-за сравнительно простой реализации. Однако существующие подходы обладают двумя существенными недостатками: уменьшение зоны просмотра за счет кадрирования или возникновение эффектов «растянутого изображения» или «сжатого изображения».

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

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

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

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

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

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

- выбирают правило вычисления функции стоимости для пикселя в зависимости от результатов анализа изображения;

- генерируют карты стоимостей и истории;

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

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

- получен требуемый размер изображения,

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

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

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

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

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

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

- определяли путь с наименьшей суммарной стоимостью;

- добавляли новые пиксели, соседние с пикселями пути с применением интерполяции по нескольким ближайшим пикселям;

- ослабляли значения в карте истории и обновляли карту истории;

- обновляли значения в карте стоимостей.

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

- определяли путь с наименьшей суммарной стоимостью;

- удаляли пиксели пути и корректировали значения пикселей, которые граничили с пикселями удаленного пути;

- ослабляли значения в карте истории и обновляли карту истории;

- обновляли значения в карте стоимостей.

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

H(i,j)=H(i,j)^-1-С,

где H(i,j) - значение элемента карты истории, H(i,j)^-1 - значение элемента карты истории до ослабления, С - предопределенная константа.

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

В заявляемом изобретении решена проблема переформатирования цифрового изображения; переформатирование изображение отличается от исходного формой, размерами и/или форматом (соотношение геометрических размеров цифрового изображения), причем размер и пропорции наиболее важных объектов на изображении сохраняются. В заявляемом изобретении предлагаются способ и система адаптивного переформатирования цифровых изображений путем удаления и/или добавления наименее важных пикселей изображения.

Для сохранения связности и формы цифрового изображения, на каждом шаге переформатирования вычисляется, по крайней мере, одна группа наименее важных связных пикселей в вертикальном или горизонтальном направлении. Здесь и далее по тексту связную группу пикселей будем называть «путь». На каждом шаге переформатирования вычисленный путь удаляется или добавляется в новое изображение с измененными геометрическими размерами. Впоследствии полученное изображение используется в качестве исходного на последующих шагах переформатирования. Данный процесс повторяется до тех пор, пока изображение не принимает необходимые размеры/формат.

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

- используется специальный шаг для определения содержания изображения и соответствующей функции стоимости, которая наилучшим способом описывает важность пикселей для данного класса изображений;

- функция стоимости выбирается пользователем интерактивно;

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

Для текущего изображения вычисляется карта стоимостей после того, как был осуществлен выбор функции стоимости. Карта стоимостей представляет собой массив размерностью, эквивалентной размерности обрабатываемого изображения. Каждый элемент карты стоимости задает численное значение степени важности соответствующего пикселя изображения. Для нахождения оптимального связного пути, который содержит наименее важные пиксели, строится взвешенный направленный граф, на котором решается оптимизационная задача поиска пути с наименьшей суммарной стоимостью. Узлы такого графа соответствуют пикселям изображения, а ребрам графа назначаются весовые коэффициенты с помощью карты стоимостей. Данный поиск производится в вертикальном и горизонтальном направлениях для вычисления горизонтальных и вертикальных путей соответственно. Решение поставленной оптимизационной задачи получается с помощью алгоритмов и методов динамического программирования и описано более подробно ниже. Полученные таким образом пути удаляются или добавляются к изображению для изменения его размера/формата.

Определенный выше метод переформатирования может быть использован для уменьшения одной или нескольких сторон изображения с помощью простого исключения найденного пути из изображения. Однако для операции увеличения изображения существуют определенные ограничения. Очевидно, что после нахождения и добавления на изображение оптимального пути, сохраняется большой шанс нахождения и дублирования того же пути на последующих итерациях переформатирования. Это приводит к эффекту растягивания изображения и дублирования одного и того же пути на всех итерациях переформатирования. Для предотвращения такой ситуации и снятия ограничений на размер получаемого изображения в процессе увеличения изображений предлагается использовать карту истории. Каждый элемент карты истории представляет собой дополнительную степень важности для каждого пикселя изображения, причем данная степень важности не зависит от изображения, а зависит от добавленных/удаленных путей на предыдущих итерациях.

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

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

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

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

- Инициализация карты истории;

- Выбор функции стоимости согласно содержанию изображения;

- Вычисление карты стоимостей;

- Ослабление карты истории;

- Поиск оптимального пути;

- Обновление (операция удаление/добавление пути) обрабатываемого изображения с помощью, по крайней мере, одного вычисленного пути;

- Обновление карты истории с помощью вычисленного пути/путей;

- Повторение шагов со 2 по 7 до тех пор, пока не получен необходимый размер/формат изображения.

Далее существо заявляемого изобретения поясняется с привлечением чертежей.

Фиг.1. Блок-схема этапов работы метода адаптивного переформатирования цифровых фотографий и изображений документов.

Фиг.2. Блок-схема анализа изображения при выборе правила вычисления функции стоимости.

Фиг.3. Блок-схема увеличения изображения посредством добавления пути.

Фиг.4. Блок-схема уменьшения изображения посредством удаления пути.

Фиг.5. Схема модулей системы.

Фиг.6. Границы изображения, используемые при поиске оптимального пути.

Фиг.7. Модель графа для решения оптимизационной задачи поиска оптимального пути.

Фиг.8. Схема назначения весов ребрам графа.

Фиг.9. Уменьшение изображения в процессе переформатирования.

Фиг.10. Увеличение изображения в процессе переформатирования.

Фиг.11. Обновление и ослабление карты истории.

Фиг.12. Блок-схема интерактивной системы переформатирования.

Фиг.13. Блок-схема системы переформатирования для копировальных устройств.

Фиг.14. Блок-схема системы переформатирования для факсимильных устройств.

Фиг.15. Блок-схема системы переформатирования для HTML документов.

Фиг.16-19. Примеры переформатирования изображений документов.

Фиг.18. Пример переформатирования HTML документа.

Фиг.20-23. Примеры применения системы переформатирования к фотографиям для преобразования исходного формата 4:3 к формату 3:2.

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