Способ и система адаптивного переформатирования цифровых изображений
Изобретение относится к области обработки изображений и может быть использовано при редактировании изображения, при котором не нарушаются размеры, пропорции и взаимное расположение наиболее важных объектов. Техническим результатом является повышение качества переформатированных изображений. В способе и системе для адаптивного переформатирования цифровых фотографий и изображений документов выбирают правило вычисления функции стоимости для пикселя в зависимости от результатов анализа изображения; генерируют карты стоимостей и истории; изменяют размеры изображения посредством добавления/удаления, по меньшей мере, одного найденного пути с применением интерполяции, используя как горизонтальный, так и вертикальный пути. Горизонтальный путь является цепочкой связанных пикселей, у которой начальный пиксель пути находится на левой границе изображения, конечный пиксель пути - на правой границе изображения. Количество пикселей в пути равно ширине изображения в пикселях. Вертикальный путь является цепочкой связанных пикселей, у которой начальный пиксель пути находится на верхней границе изображения, конечный пиксель пути - на нижней границе изображения. Количество пикселей в пути равно высоте изображения в пикселях. Поиск пути осуществляют минимизацией суммарной стоимости пикселей пути. Повторяют генерацию карт стоимостей и истории, а также этапы изменения размеров изображения, пока не будет достигнут один из двух результатов: получен требуемый размер изображения, суммарная стоимость пути превысит предопределенный порог. 2 н. и 7 з.п. ф-лы, 23 ил.
Заявляемое изобретение относится к области обработки изображений, в частности к способам изменения размера/формата цифрового изображения, и может найти применение в редактировании изображений, при котором не нарушаются размеры, пропорции и взаимное расположение наиболее важных объектов изображения.
Среди известных решений в этой области можно упомянуть следующие технологии и методы: линейное масштабирование, кадрирование, переформатирование (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.
Основная идея данного изобретения заключается в изменении размера изображения путем добавления или удаления пикселей, которые имеют низкую значимость (информативность). Значимость каждого пикселя определяется функцией стоимости. Вид этой функции зависит от содержащейся в изображении информации и определяет результат переформатирования.
На Фиг.1 приведена блок-схема этапов работы способа. На шаге 101 выбирают правило вычисления функции стоимости для пикселя в зависимости от результатов анализа изображения. Правило вычисления функции стоимости выбирается из предопределенного множества правил автоматически или интерактивно. Далее на шаге 102 генерируют карты стоимостей и истории. На шаге 103 увеличивают или уменьшают изображение в зависимости от исходного и требуемого размеров. Увеличение или уменьшение изображения производят посредством добавления в него, по меньшей мере, одного найденного горизонтального или вертикального пути с применением интерполяции или удаления из него, по меньшей мере, одного найденного горизонтального или вертикального пути. Горизонтальный путь есть цепочка связанных пикселей, причем начальный пиксель пути находится на левой границе изображения, конечный пиксель пути находится на правой границе изображения, а количество пикселей в пути равно ширине изображения в пикселях. Вертикальный путь есть цепочка связанных пикселей, причем начальный пиксель пути находится на верхней границе изображения, конечный пиксель пути находится на нижней границе изображения, а количество пикселей в пути равно высоте изображения в пикселях. Поиск пути основан на минимизации суммарной стоимости пикселей пути. Если достигнут требуемый размер изображения (условие 104), то метод заканчивает свою работу. В противном случае повторяют итерационно генерацию карт стоимостей и истории (102), а также этап увеличения или уменьшения (103), пока не будет достигнут требуемый размер изображения или пока суммарная стоимость пути не превысит предопределенный порог.
В целом, функция стоимости F определяется следующим соотношением:
F(I,х,у)=grad(I,х,у)+РОI(I,х,у),
где I - обрабатываемое изображение; х, у - координаты пикселя, grad(I,х,у) - функция вычисления градиента для пикселя с координатами (х,у), POI - функция для обнаружения особых пикселей
Функция grad(I,х,у) задает общую значимость каждого пикселя в терминах высоко-частотных границ изображений. Линейные и нелинейные высокочастотные фильтры, такие как оператор Собеля, модуль градиента цветов, горизонтальные и вертикальные конечные разности, Лапласиан-гауссиана могут использоваться в качестве данной функции. Однако, не только пиксели на высокочастотных границах важны на цифровых изображениях. Функция POI добавляет стоимость к равномерным, но значимым областям, таким как кожа человека, фрагменты архитектурных сооружений и так далее.
На фиг.2 показана блок-схема анализа изображения при выборе правила вычисления функции стоимости для пикселя. Для начала на шаге 201 выполняется детектирование наличия на изображении людей. В предпочтительном варианте изобретения это реализуется с помощью функций, задающих цвета, характерные для кожи человека. Подобные функции описаны, например, в статье G.Gomez, E.Morales, Automatic feature construction and a simple rule induction algorithm for skin detection, proc. of the ICML Workshop on Machine Learning in Computer Vision, pp.31-38, 2002 [19]. Если пиксели, имеющие цвета, характерные для кожи человека занимают значительную площадь, то считается, что на изображении есть человек, и на шаге 203 выбирается такое правило вычисления функции стоимости для пикселя, что пикселям, которые предположительно относятся к изображению человека, присваиваются большие значения стоимостей. На шаге 205 применяют детектор городских сцен и архитектурных сооружений. Существует ряд подобных детекторов, например, описанные в статье N.Serrano, A.Savakis, J.Luo, A computationally efficient approach to indoor/outdoor scene classification, Proc. International Conference on Pattern Recognition, 2002, 146-149. [20]; в патентной заявке РФ 2006136861 [21] и в докладе A.Vailaya, A.Jain, J.Z.Hong, On image classification: city vs. landscape, Proc. IEEE Workshop on Content-Based Access of Image and Video Libraries, pp.3-8, 1998 [22]. Если на изображении есть архитектурные сооружения, то на шаге 206 выбирается такое правило вычисления функции стоимости для пикселя, что пикселям, которые соответствуют протяженным прямым линиям, присваиваются большие значения стоимостей. На шаге 207 выбирают какой-либо из высокочастотных фильтров для вычисления стоимости каждого пикселя. Понятно, что детекторы не зависят друг от друга и могут применяться в произвольной последовательности.
На Фиг.3 показана блок-схема увеличения изображения посредством добавления пути. На шаге 301 определяют, по меньшей мере, один путь с наименьшей суммарной стоимостью. Возможна обработка нескольких путей параллельно за одну итерацию. Добавляют новые пиксели, соседние с пикселями пути с применением интерполяции по нескольким ближайшим пикселям (шаг 302). На шаге 303 обновляют карту истории, добавляя в нее значения, соответствующие пикселям пути, и ослабляя значения, которые были в данной карте ранее. Обновляют значения в карте стоимостей (шаг 304) посредством применения к пикселям изображения функции вычисления стоимости и карты истории.
На Фиг.4 показана блок-схема уменьшения изображения посредством удаления пути. На шаге 401 определяют, по меньшей мере, один путь с наименьшей суммарной стоимостью. Возможна обработка нескольких путей параллельно за одну итерацию. Удаляют пиксели пути и корректируют значения пикселей, которые граничили с пикселями удаленного пути (шаг 402). На шаге 403 обновляют карту истории, удаляя из карты элементы, соответствующие пикселям пути, добавляя в нее значения, соответствующие пикселям, соседним с пикселями пути, и ослабляя значения, которые были в данной карте ранее. Обновляют значения в карте стоимостей (шаг 404) посредством применения к пикселям изображения функции вычисления стоимости и карты истории.
Схема модулей системы адаптивного переформатирования цифровых фотографий и изображений документов показана на Фиг.5. Система состоит из следующих основных компонентов: модуль выбора правила вычисления функции стоимости для пикселя (501), генератор карт стоимостей и истории (502), модуль анализа карты стоимостей и выбора пути (503), модуль добавления пути в изображение (506), модуль удаления пути из изображения (505), модуль масштабирования (504), модуль ослабления карты истории (507), модуль обновления карты стоимостей (508). Выход модуля выбора правила вычисления функции стоимости для пикселя связан с входом генератора карт стоимостей и истории, а также с входом модуля обновления карты стоимостей. Выход генератора карт стоимостей и истории связан с входом модуля анализа карты стоимостей и выбора пути. Выход модуля анализа карты стоимостей и выбора пути связан с входами модулей добавления пути в изображение, удаления пути из изображения и масштабирования. Выходы модулей добавления пути в изображение и удаления пути из изображения связаны с входом модуля ослабления карты истории. Выход модуля ослабления карты истории связан с входом модуля обновления карты стоимостей. Выход модуля обновления карты стоимостей связан с входом модуля анализа карты стоимостей и выбора пути.
Модуль выбора правила вычисления функции стоимости для пикселя выполнен с возможностью выбирать из набора предопределенных правил вычисления функции стоимости для каждого пикселя изображения в зависимости от содержащейся в изображении информации. Генератор карт стоимостей и истории выполнен с возможностью генерировать, применяя выбранное правило, исходные карту стоимостей и карту истории. Модуль анализа карты стоимостей и выбора пути выполнен с возможностью определения, по меньшей мере, одного горизонтального пути из связанных пикселей, где начальный пиксель пути находится на левой границе изображения, конечный пиксель пути находится на правой границе изображения, а количество пикселей в пути равно ширине изображения в пикселях, а также с возможностью определения, по меньшей мере, одного вертикального пути из связанных пикселей, где начальный пиксель пути находится на верхней границе изображения, конечный пиксель пути находится на нижней границе изображения, а количество пикселей в пути равно высоте изображения в пикселях, причем если суммарная стоимость всех пикселей пути у всех найденных путей больше предопределенного порога, то изображение передается в модуль масштабирования, иначе данный модуль передает изображение, карты стоимостей и истории в модуль добавления пути в изображение или в модуль удаления пути из изображения в зависимости от текущего и требуемого соотношения сторон изображения. Модуль добавления пути в изображение выполнен с возможностью увеличения текущего изображения посредством добавления в него, по меньшей мере, одного найденного пути с применением интерполяции по нескольким ближайшим пикселям. Модуль удаления пути из изображения выполнен с возможностью уменьшения текущего изображения посредством удаления из него, по меньшей мере, одного найденного пути. Модуль ослабления карты истории выполнен с возможностью уменьшать значения в карте истории, которые соответствуют окрестностям пикселей путей, удаленных или добавленных ранее. Модуль обновления карты стоимостей выполнен с возможностью пересчитывать карту стоимостей, применяя ранее выбранное правило и карту истории.
В основном, наиболее важные этапы метода были описаны выше. Далее детально описываются этап вычисления оптимального пути, карта истории и процесс изменения размера/формата изображения.
Главная задача этапа вычисления оптимального пути состоит в поиске связанного пути пикселей в вертикальном или горизонтальном направлении между противоположными границами изображения. На Фиг.6 изображена верхняя 601 и нижняя 602 границы изображения, левая 603 и правая 604 границы изображения также приведены на Фиг.6. Поиск вертикального пути осуществляется между верхней 601 и нижней границей 602, а горизонтального пути - между левой 603 и правой 604 границей соответственно.
Для каждого пикселя, который принадлежит верхней 601 или левой 603 границе изображения, строится направленный взвешенный граф, отображенный на Фиг.7. Каждый пиксель изображения ассоциируется с соответствующим узлом графа. Каждый узел имеет три ребра с назначенными весовыми коэффициентами. Количество ребер жестко не ограничивается. Возможны реализации заявленного изобретения с графом с пятью и более ребрами, исходящими из каждого узла. Однако в случае использования графа с более чем с тремя ребрами, увеличивается вычислительная сложность алгоритма поиска оптимального пути, и уменьшается связность объектов на изображении, что может привести к уменьшению качества получаемых результатов.
Каждому ребру присваивается весовой коэффициент w(i,j,k), равный соответствующему значению карты стоимостей, плюс соответствующее значение элемента карты истории согласно схеме, отображенной на Фиг.8. Каждому ребру, исходящему из текущего узла графа, назначается весовой коэффициент по следующим формулам:
w(i,j,1)=a(i-1,j+1)+h(i-1,j+1)
w(i,j,2)=a(i,j+1)+h(i,j+1)
w(i,j,3)=a(i+1,j+1)+h(i+1,j+1),
где i, j - соответствующие координаты узла, k - номер ребра, а() - соответствующий элемент карты стоимостей, h() - соответствующий элемент карты истории.
Далее формулируется оптимизационная задача поиска оптимального пути между границами изображений на заданном графе. Оптимальность определяется как поиск связанного пути с минимальной суммарной стоимостью вдоль этого пути. Суммарная стоимость пути µ, состоящего из последовательности ребер а1, а2…аn, представляет собой число l(µ), которое равно сумме весовых коэффициентов вдоль µ и определяется следующей формулой:
Эффективный поиск оптимального пути может быть получен с помощью алгоритмов поиска на графе и методов динамического программирования. На данный момент существует множество таких алгоритмов, поэтому реализация и описание таких алгоритмов выходит за рамки заявленного изобретения.
Найденный оптимальный путь 901 разделяет обрабатываемое изображение 906 на две части 902 (белые окружности) и 903 (белые прямоугольники). Уменьшенное изображение 907 состоит из двух частей 902а и 903а. Данные части эквиваленты частям 902 и 903. Группы пикселей 905 и 904, которые состоят из пикселей, находящи[ся в непосредственной близости от пикселей, принадлежащих найденному оптимальному пути 901, могут дополнительно обрабатываться с помощью процедуры интерполяции для сглаживания и компенсации возможных дефектов, возникающих в процессе исключения пути 901 из изображения.
Аналогичный подход применяется и в операции увеличения (см. Фиг.10). Найденный оптимальный путь 1001 разделяет обрабатываемое изображение 1004 на две части 1002 и 1003. Увеличенное изображение 1005 состоит из двух частей 1002а и 1003а, эквивалентных частям изображения 1002 и 1003. Найденный оптимальный путь 1001 добавляется на изображение 1005 путем дублирования пикселей вдоль найденного пути, формируя копии 1001a и 1001b. Данные пиксели, принадлежащие копиям оптимального пути 1001a и 1001b, также могут быть дополнительно обработаны интерполяционными процедурами.
На каждой итерации увеличения изображения также обновляется карта истории, согласно найденному оптимальному пути. На Фиг.11 приведен пример обновления 1103 и ослабления 1105 карты истории. Карта истории 1102 и найденный оптимальный путь 1101 используются для получения увеличенной карты истории 1104. Элементам карты истории, которые принадлежат найденному оптимальному пути 1101a и его продублированной копии 1101b, присваиваются максимальные значения. Ослабленная карта истории 1106 представляет собой увеличенную карту истории 1104, элементы которой уменьшены на определенное значение. В данном примере использовалась следующая функция ослабления:
H(i,j)=H(i,j)-1-С,
где H(i,j) - значение элемента ослабленной карты истории, H(i,j)-1 - значение элемента карты истории до процедуры ослабления, С - предопределенная константа. Использование других функций ослабления также возможно и не ограничивается приведенной выше функцией ослабления.
Система адаптивного переформатирования цифровых изображений, согласно формуле и описанию заявленного изобретения, может работать полностью в автоматическом режиме, когда известен требуемый размер/формат результирующего изображения. Кроме того? заявленный способ может быть реализован в виде интерактивной системы переформатирования (см. Фиг.12), в случае когда конечный размер/формат изображения неизвестен. Исходное цифровое изображение 1201 переформатируется адаптивной системой переформатирования 1202 в изображение 1203 с новым размером/форматом. Размер/формат результирующего изображения контролируется пользователем 1205 в интерактивном режиме путем генерации пользовательских сигналов, которые поступают на вход системы переформатирования. Промежуточные/окончательные результаты переформатирования 1203 отображаются на устройстве отображения 1204 и воспринимаются пользователем 1205. Пользователь 1205 принимает решение на основе промежуточных результатов, отображенных на устройстве отображения 1204, и генерирует новые управляющие сигналы для получения желаемого результирующего изображения.
Еще одно промышленное применение изобретения может иметь место в составе копировальных устройств (см. Фиг.13). Исходный бумажный документ 1301 сканируется с помощью устройства сканирования 1302. Полученное цифровое представление бумажного документа переформатируется с помощью заявленной в изобретении системы переформатирования 1303 согласно поступающим управляющим сигналам 1304, поступающим от пользователя и/или копировального устройства. Переформатированное цифровое изображение затем печатается/отображается на соответствующем устройстве отображения 1305. Таким образом, получается бумажный переформатированный документ 1306. Аналогичный подход может быть применен для факсимильных устройств (см. Фиг.14), для переформатирования факсимильных документов.
Важное промышленное применение адаптивной системы переформатирования цифровых изображений заключается в переформатировании HTML документов. Система переформатирования HTML документов отображена на Фиг.15. Проблема с HTML документами состоит в том, что размер HTML документа может быть жестко задан разработчиком, что ведет к возникновению «полос прокруток» при отображении HTML документа в области отображения с размерами меньше, чем предусмотрел разработчик HTML документа. Другой причиной проблемы является наличие множества изображений на HTML документе, размер которых сложно уменьшить/увеличить без внесения дефектов отображения. Поэтому возникает проблема отображения HTML страниц на устройствах (КПК, мобильные телефоны, медиаплееры и т.д.) с дисплеями с маленьким разрешением экрана. Другая проблема заключается в печати HTML документов на принтере.
Для корректного отображения HTML документов предлагается использовать систему переформатирования HTML документов (Фиг.15). Исходный HTML документ поступает на вход модуля анализа изображений 1501, который анализирует изображения/флеш анимацию, содержащиеся в HTML документе. Полученные изображения переформатируются системой переформатирования 1503 для изменения размера/формата изображений согласно управляющим сигналам 1504. HTML компоновщик 1505 создает новый HTML документ с переформатированными изображениями. Переформатированный документ 1506 отображается на соответствующем устройстве 1507 отображения.
Хотя указанный выше вариант выполнения изобретения был изложен с целью иллюстрации, специалистам ясно, что возможны разные модификации, добавления и замены, не выходящие из объема и смысла настоящего изобретения, раскрытого в прилагаемой формуле изобретения.
1. Система адаптивного переформатирования цифровых фотографий, содержащая модуль выбора правила вычисления функции стоимости для пикселя, генератор карт стоимостей и истории, модуль анализа карты стоимостей и выбора пути, модуль добавления пути в изображение, модуль удаления пути из изображения, модуль масштабирования, модуль ослабления карты истории, модуль обновления карты стоимостей, причем выход модуля выбора правила вычисления функции стоимости для пикселя связан с входом генератора карт стоимостей и истории, а также с входом модуля обновления карты стоимостей, выход генератора карт стоимостей и истории связан с входом модуля анализа карты стоимостей и выбора пути, выход модуля анализа карты стоимостей и выбора пути связан с входами модулей добавления пути в изображение, удаления пути из изображения и масштабирования, выходы модулей добавления пути в изображение и удаления пути из изображения связаны с входом модуля ослабления карты истории, выход модуля ослабления карты истории связан с входом модуля обновления карты стоимостей, выход модуля обновления карты стоимостей связан с входом модуля анализа карты стоимостей и выбора пути, причем модуль выбора правила вычисления функции стоимости для пикселя выполнен с возможностью выбирать из набора предопределенных правило вычисления функции стоимости для каждого пикселя изображения в зависимости от содержащейся в изображении информации, генератор карт стоимостей и истории выполнен с возможностью генерировать, применяя выбранное правило, исходные карту стоимостей и карту истории, модуль анализа карты стоимостей и выбора пути выполнен с возможностью определения, по меньшей мере, одного горизонтального пути из связанных пикселей, где начальный пиксель пути находится на левой границе изображения, конечный пиксель пути находится на правой границе изображения, а количество пикселей в пути равно ширине изображения в пикселях, а также с возможностью определения, по меньшей мере, одного вертикального пути из связанных пикселей, где начальный пиксель пути находится на верхней границе изображения, конечный пиксель пути находится на нижней границе изображения, а количество пикселей в пути равно высоте изображения в пикселях, причем если суммарная стоимость всех пикселей пути у всех найденных путей больше предопределенного порога, то изображение передается в модуль масштабирования, иначе данный модуль передает изображение, карты стоимостей и истории в модуль добавления пути в изображение или в модуль удаления пути из изображения в зависимости от текущего и требуемого соотношения сторон изображения, модуль добавления пути в изображение выполнен с возможностью увеличения текущего изображения посредством добавления в него, по меньшей мере, одного найденного пути с применением интерполяции по нескольким ближайшим пикселям, модуль удаления пути из изображения выполнен с возможностью уменьшения текущего изображения посредством удаления из него, по меньшей мере, одного найденного пути, модуль ослабления карты истории выполнен с возможностью уменьшать значения в карте истории, которые соответствуют окрестностям пикселей путей удаленных или добавленных ранее, модуль обновления карты стоимостей выполнен с возможностью пересчитывать карту стоимостей, применяя ранее выбранное правило и карту истории.
2. Способ адаптивного переформатирования цифровых фотографий и изображений документов, предусматривающий выполнение следующих этапов:
выбирают правило вычисления функции стоимости для пикселя в зависимости от результатов анализа изображения;
генерируют карты стоимостей и истории;
изменяют размеры изображения посредством добавления/удаления, по меньшей мере, одного найденного пути с применением интерполяции, при этом допустимо использование как горизонтального, так и вертикального пути, причем горизонтальный путь является цепочкой связанных пикселей, у которой начальный пиксель пути находится на левой границе изображения, конечный пиксель пути находится на правой границе изображения, а количество пикселей в пути равно ширине изображения в пикселях, тогда как вертикальный путь является цепочкой связанных пикселей, у которой начальный пиксель пути находится на верхней границе изображения, конечный пиксель пути находится на нижней границе изображения, а количество пикселей в пути равно высоте изображения в пикселях, при этом поиск пути осуществляют посредством минимизации суммарной стоимости пикселей пути;
повторяют генерацию карт стоимостей и истории, а также этапы изменения размеров изображения пока не будет достигнут один из двух результатов:
получен требуемый размер изображения,
суммарная стоимость пути превысит предопределенный порог.
3. Способ по п.2, отличающийся тем, что при выборе правила вычисления функции стоимости применяют детектирование изображения лиц людей.
4. Способ по п.2, отличающийся тем, что, при выборе правила вычисления функции стоимости применяют детектор городских сцен и архитектурных сооружений.
5. Способ по п.2, отличающийся тем, что при генерации карты стоимостей применяют высокочастотный фильтр.
6. Способ по п.2, отличающийся тем, что при генерации карты стоимостей применяют функцию, описывающую цвета типичные для кожи человека.
7. Способ по п.2, отличающийся тем, что изменение размеров изображения осуществляют посредством его увеличения за счет добавления, по меньшей мере, одного пути, выполняя при этом следующие операции:
определяют путь с наименьшей суммарной стоимостью;
добавляют новые пиксели, соседние с пикселями пути с применением интерполяции по нескольким ближайшим пикселям;
ослабляют значения в карте истории и обновляют карту истории;
обновляют значения в карте стоимостей.
8. Способ по п.2, отличающийся тем, что изменение размеров изображения осуществляют посредством его уменьшения за счет удаления, по меньшей мере, одного пути, выполняя при этом следующие операции:
определяют путь с наименьшей суммарной стоимостью;
удаляют пиксели пути и корректируют значения пикселей, которые граничили с пикселями удаленного пути;
ослабляют значения в карте истории и обновляют карту истории;
обновляют значения в карте стоимостей.
9. Способ по п.2, отличающийся тем, что функцию ослабления значений в карте истории описывают соотношением:
H(i,j)=H(i,j)-1-С,
где H(i,j) - значение элемента карты истории;
H(i,j)-1 - значение элемента карты истории до ослабления;
С - предопределенная константа.
