Алгоритм сжатия и растяжения картинки

Использование и разработка софта (преимущественно на ПЦ)

Moderator: Shaos

User avatar
Lavr
Supreme God
Posts: 16689
Joined: 21 Oct 2009 08:08
Location: Россия

Алгоритм сжатия и растяжения картинки

Post by Lavr »

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

В Вендовском АПИ есть две функции: Function BitBlt Lib "gdi32.dll" (...) и Function StretchBlt Lib "gdi32.dll" (...),
первая выдает картинку один-в-один куда ей сказали, вторая же упихивает любое изображение
в заданный размер - вот её алгоритм меня и интересует...

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

Я, конечно же, гуглил, прежде чем здесь спросить... но может я не теми словами ищу... :-?
iLavr
jdigreze
God
Posts: 1388
Joined: 02 Jan 2006 02:28
Location: Abakan

Re: Алгоритм сжатия и растяжения картинки

Post by jdigreze »

Читай про интерполяцию: линейная, кубическая и Ланцоша.
User avatar
Lavr
Supreme God
Posts: 16689
Joined: 21 Oct 2009 08:08
Location: Россия

Re: Алгоритм сжатия и растяжения картинки

Post by Lavr »

jdigreze wrote:Читай про интерполяцию: линейная, кубическая и Ланцоша.
А где? Ткни меня носом, я почитаю...
А то я любил тоже так говорить своим преподам: читайте Ландау и Лифшица - там всё написано! :mrgreen:
iLavr
jdigreze
God
Posts: 1388
Joined: 02 Jan 2006 02:28
Location: Abakan

Re: Алгоритм сжатия и растяжения картинки

Post by jdigreze »

Ну вот немного теории сжато: https://habrahabr.ru/post/243285/ и http://wedframe.ru/showthread.php?t=231 ... 3ae7649d91
Я когда-то давно немного касался этой темы, но за давностью никаких наработок не могу предоставить, даже сейчас на вскидку не могу сказать по какой литературе я тогда экспериментировал.
User avatar
Lavr
Supreme God
Posts: 16689
Joined: 21 Oct 2009 08:08
Location: Россия

Re: Алгоритм сжатия и растяжения картинки

Post by Lavr »

jdigreze wrote:даже сейчас на вскидку не могу сказать по какой литературе я тогда экспериментировал.
Да вот экспериментировать мне как раз и не охота, хотя я и поэкспериментировал.
Но я понял, что изобретаю велосипед - всё давно изобретено, и надо просто спросить
у людей - где это написано, прочитать и сделать.

Мне, честно говоря, в гуглении попадаются очень заумные вещи, но мне заумствовать
некогда - надо сделать простую задачу, суть её я точно описал.

Уточню ещё конкретнее - есть картинка черно-белая, скажем, 100х100 точек для простоты.
Я хочу её сжать до 80%. Как я понимаю, мне надо выкинуть лишние точки по Х и по У - но
какие?

Если сжимать до 50% надо выкинуть каждую вторую точку, или 1-ю, 3-ю, 5-ю... и т.д.?
Или я вобще неверно понимаю суть сжатия картинки?
iLavr
Tronix
Doomed
Posts: 662
Joined: 18 Nov 2013 02:38
Location: Москва

Re: Алгоритм сжатия и растяжения картинки

Post by Tronix »

User avatar
Lavr
Supreme God
Posts: 16689
Joined: 21 Oct 2009 08:08
Location: Россия

Re: Алгоритм сжатия и растяжения картинки

Post by Lavr »

Tronix wrote:http://www.enlight.ru/demo/faq/smth.phtml?query=alg_scale_bitmap
Спасибо! Вот это вроде по делу! Надо будет найти почитать подробности:"Как масштабиpовать pастpовые изобpажения и не только это..." ( by А. Ефлеев ) - жуpнал МОHИТОР.

А вот когда я читаю:"пpо усpеднение палитpы методами кластеpизации" - мне башню сносит напрочь... :o
Нет... такое не читал... :mrgreen:
iLavr
User avatar
Lavr
Supreme God
Posts: 16689
Joined: 21 Oct 2009 08:08
Location: Россия

Re: Алгоритм сжатия и растяжения картинки

Post by Lavr »

Ну, особой "америки" г-н А. Ефлеев мне не открыл...
Hа самом деле изобpажение непpеpывно, а мы его pазлагаем в pастp.
Ассоциация - пpиближаем непpеpывную функцию значениями в точках.
Пpи масштабиpовании
1) восстанавливаем непpеpывную функцию (напpимеp полином
N - ной степени, если изначально было N точек.
2) делим отpезок [1,N] на M частей ( если надо M точек )
и смотpим значение полученного полинома в этих точках.
Сначала делаем это со всеми стpоками, а потом аналогично со столбцами.

Пpоблема в следующем:

1) отдельно по стpокам и столбцам - хуже (по логике), чем
pассматpивать функцию от двух пеpеменных. (но тяжелее).
2) делать это пpиходится для каждого цвета в отдельности.
Если каpтинка имела 256 цветов, то после таких пpеобpазований
получим (теоpетически) 16 милл.

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

И у меня так отлично получалось со звуком!
Скажем есть файл WAV из 100 отсчетов длительностью в 1 секунду (грубая аналогия со 100 точками).
Т.е. каждый отсчет амплитуды звукового сигнала брали за каждую 1/100=0.01 секунды.
Мне надо его переделать в новый файл с дискретностью 80 отсчетов в секунду (аналогия сжатия картинки на 80%).
Не мудрствуя лукаво со всякими полиномами, я просто соединяю вершины всех отсчетов прямыми линиями.
Получается непрерывное приближение исходного дискретного WAV сигнала.
А теперь я должен взять новые отсчеты этого непрерывного сигнала, но через интервалы 1/80=0,0125 секунды.
И я получаю тот же по форме звуковой фрагмент, длительностью 1 сек., но вместо 100 отсчетов -
у меня их 80.
Качество звука чуть ухудшится, но не очень заметно...

А теперь перейдем к изображению. Вот оно, в нём всего 2 цвета, т.е. градаций яркости нет, соединять
прямыми линиями получается и нечего!... :osad:
LCD580GDI.gif
А теперь смотрим, как это "порешал" MS Word:
LCD581GDI.gif
То есть, даже безобразно мерзко уменьшая, MS Word не теряет "сути" изображения:
лестницы, толщиной в 1 пиксел в исходной картинке - так и остаются различимы! :o

А вот Proteus, масштабируя изображение, тонкие линии начинает терять... :osad:
viewtopic.php?p=121510#p121510
И я никак не могу разрешить эту проблему... хороший проект завис... :-?
You do not have the required permissions to view the files attached to this post.
iLavr
User avatar
Lavr
Supreme God
Posts: 16689
Joined: 21 Oct 2009 08:08
Location: Россия

Re: Алгоритм сжатия и растяжения картинки

Post by Lavr »

AlexanderZh wrote:Как по мне, то берется квадрат (2х2, 3х3, 4х4) и вычисляется средний цвет.
А что такое "средний цвет"? Если цвета всего два - черный и белый?
Это Протеус подкладывет подложку болотного цвета, а когда я "внутри его динамической библиотеки",
то мне доступны только:"нет цвета" = '0' - черный, "есть цвет" = '1' - белый.
Амплитуды цвета там нет, и цвет, скажем, 0.5 мне программно внутри недоступен.
iLavr
jdigreze
God
Posts: 1388
Joined: 02 Jan 2006 02:28
Location: Abakan

Re: Алгоритм сжатия и растяжения картинки

Post by jdigreze »

Lavr wrote:А что такое "средний цвет"? Если цвета всего два - черный и белый?
...
Амплитуды цвета там нет, и цвет, скажем, 0.5 мне программно внутри недоступен.
Может и не доступен, но вычислять нужно именно амплитуду. А вся эта засада из-за мнимой простоты вот этого алгоритма:
Lavr wrote:Не мудрствуя лукаво со всякими полиномами, я просто соединяю вершины всех отсчетов прямыми линиями.
Получается непрерывное приближение исходного дискретного WAV сигнала.
А теперь я должен взять новые отсчеты этого непрерывного сигнала
Где применительно к цвету выборка возьмёт "0" при стоящей рядом "1", и тогда целые вертикальные или горизонтальные линии просто исчезнут, если попадут в пропуск выборки, что и происходит в Протеусе. Чтобы этого не происходило, к примеру "билинейный" алгоритм берёт точки из квадрата 2х2, вычисляет средний цвет/градацию, что и наблюдается в ворде. А без градаций любой алгоритм даст результат Протеуса.

Кстати, за счёт градаций получается мнимая линейность сжатия изображения.
User avatar
Lavr
Supreme God
Posts: 16689
Joined: 21 Oct 2009 08:08
Location: Россия

Re: Алгоритм сжатия и растяжения картинки

Post by Lavr »

jdigreze wrote:А вся эта засада из-за мнимой простоты вот этого алгоритма:
Lavr wrote:Не мудрствуя лукаво со всякими полиномами, я просто соединяю вершины всех отсчетов прямыми линиями.
Получается непрерывное приближение исходного дискретного WAV сигнала.
А теперь я должен взять новые отсчеты этого непрерывного сигнала
Этот метод ни в чем не виноват. Это называется кусочно-линейная аппроксимация функции.
Может быть, аппроксимация полиномом или там параболами и точнее, но кусочно-линейная
аппроксимация функции - быстрее в простых случаях.
Ну и я же сказал, что метод работает:
Lavr wrote:...только если между отсчетами есть некоторая разница по амплитуде.
А в случае "0" и "1" этот метод не работает, и не в нём засада - тут и полиномом ничего не сделаешь.
iLavr
User avatar
Lavr
Supreme God
Posts: 16689
Joined: 21 Oct 2009 08:08
Location: Россия

Re: Алгоритм сжатия и растяжения картинки

Post by Lavr »

Повторил начальный эксперимент в более чистом виде: там была картинка, захваченная с экрана Proteus.
Теперь - это чисто BW-картинка размером 384х256. Но MS_WORD - справляется с ней! :o
LCD582GDI.gif
А теперь - для сравнения - та же картинка, но сжатая функцией Win32 API - StretchBlt Lib "gdi32.dll" (...) до 60%.
LCDStretchBlt.gif
Видно, что элементы изображения теряются, хотя я и облегчил задачу для StretchBlt Lib "gdi32.dll" (...),
превратив изображение в картинку с максимальным числом градаций яркости.

Похоже, что Proteus как раз и использует стандартную функциб Win32 API - StretchBlt Lib "gdi32.dll" (...),
а вот MS_WORD применяет другие алгоритмы.
You do not have the required permissions to view the files attached to this post.
iLavr
Tronix
Doomed
Posts: 662
Joined: 18 Nov 2013 02:38
Location: Москва

Re: Алгоритм сжатия и растяжения картинки

Post by Tronix »

http://www.geisswerks.com/ryan/FAQS/resize.html

Не проверял, но на взгляд, не плохо должно быть.
jdigreze
God
Posts: 1388
Joined: 02 Jan 2006 02:28
Location: Abakan

Re: Алгоритм сжатия и растяжения картинки

Post by jdigreze »

Lavr wrote:Теперь - это чисто BW-картинка размером 384х256. Но MS_WORD - справляется с ней!
Он её к полутонам привёл.
Lavr wrote:Видно, что элементы изображения теряются, хотя я и облегчил задачу для StretchBlt Lib "gdi32.dll" (...),
превратив изображение в картинку с максимальным числом градаций яркости.
Значит стандартный стретчер работает по самому простому и самому быстрому алгоритму - Ближайший сосед (Nearest neighbor), а Ворд использует что-то более продвинутое из своих закромов, скорее всего - Суперсэмплинг.
b2m
Devil
Posts: 907
Joined: 26 May 2003 06:57

Re: Алгоритм сжатия и растяжения картинки

Post by b2m »

jdigreze wrote:а Ворд использует что-то более продвинутое
Видимо делает сначала SetStretchBltMode(hdc, HALFTONE);
Страничка эмулятора наших компьютеров
http://bashkiria-2m.narod.ru/