nedoPC.org

Electronics hobbyists community established in 2002
Atom Feed | View unanswered posts | View active topics It is currently 28 Mar 2024 14:50



Reply to topic  [ 16 posts ]  Go to page 1, 2  Next
Алгоритм сжатия и растяжения картинки 
Author Message
Supreme God
User avatar

Joined: 21 Oct 2009 08:08
Posts: 7777
Location: Россия
Reply with quote
Джентльмены, пособите... ибо картинками я никогда не занимался, а хотя бы посмотреть
прототип алгоритма сжатия и растяжения картинки мне очень надо, чтобы не изобретать
свой велосипед.

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

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

Я, конечно же, гуглил, прежде чем здесь спросить... но может я не теми словами ищу... :-?

_________________
iLavr


07 Sep 2017 03:29
Profile
God

Joined: 02 Jan 2006 02:28
Posts: 1390
Location: Abakan
Reply with quote
Читай про интерполяцию: линейная, кубическая и Ланцоша.


07 Sep 2017 04:56
Profile
Supreme God
User avatar

Joined: 21 Oct 2009 08:08
Posts: 7777
Location: Россия
Reply with quote
jdigreze wrote:
Читай про интерполяцию: линейная, кубическая и Ланцоша.
А где? Ткни меня носом, я почитаю...
А то я любил тоже так говорить своим преподам: читайте Ландау и Лифшица - там всё написано! :mrgreen:

_________________
iLavr


07 Sep 2017 06:24
Profile
God

Joined: 02 Jan 2006 02:28
Posts: 1390
Location: Abakan
Reply with quote
Ну вот немного теории сжато: https://habrahabr.ru/post/243285/ и http://wedframe.ru/showthread.php?t=231 ... 3ae7649d91
Я когда-то давно немного касался этой темы, но за давностью никаких наработок не могу предоставить, даже сейчас на вскидку не могу сказать по какой литературе я тогда экспериментировал.


07 Sep 2017 17:55
Profile
Supreme God
User avatar

Joined: 21 Oct 2009 08:08
Posts: 7777
Location: Россия
Reply with quote
jdigreze wrote:
даже сейчас на вскидку не могу сказать по какой литературе я тогда экспериментировал.

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

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

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

Если сжимать до 50% надо выкинуть каждую вторую точку, или 1-ю, 3-ю, 5-ю... и т.д.?
Или я вобще неверно понимаю суть сжатия картинки?

_________________
iLavr


07 Sep 2017 18:23
Profile
Doomed

Joined: 18 Nov 2013 02:38
Posts: 662
Location: Москва
Reply with quote
http://www.enlight.ru/demo/faq/smth.pht ... ale_bitmap

_________________
https://t.me/tronix_blog


08 Sep 2017 02:40
Profile
Supreme God
User avatar

Joined: 21 Oct 2009 08:08
Posts: 7777
Location: Россия
Reply with quote
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


08 Sep 2017 06:49
Profile
Supreme God
User avatar

Joined: 21 Oct 2009 08:08
Posts: 7777
Location: Россия
Reply with quote
Ну, особой "америки" г-н А. Ефлеев мне не открыл...
Quote:
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:
Attachment:
LCD580GDI.gif
LCD580GDI.gif [ 5.74 KiB | Viewed 13952 times ]


А теперь смотрим, как это "порешал" MS Word:
Attachment:
LCD581GDI.gif
LCD581GDI.gif [ 30.77 KiB | Viewed 13952 times ]

То есть, даже безобразно мерзко уменьшая, MS Word не теряет "сути" изображения:
лестницы, толщиной в 1 пиксел в исходной картинке - так и остаются различимы! :o

А вот Proteus, масштабируя изображение, тонкие линии начинает терять... :osad:
http://www.nedopc.org/forum/viewtopic.php?p=121510#p121510
И я никак не могу разрешить эту проблему... хороший проект завис... :-?

_________________
iLavr


08 Sep 2017 08:28
Profile
Supreme God
User avatar

Joined: 21 Oct 2009 08:08
Posts: 7777
Location: Россия
Reply with quote
AlexanderZh wrote:
Как по мне, то берется квадрат (2х2, 3х3, 4х4) и вычисляется средний цвет.

А что такое "средний цвет"? Если цвета всего два - черный и белый?
Это Протеус подкладывет подложку болотного цвета, а когда я "внутри его динамической библиотеки",
то мне доступны только:"нет цвета" = '0' - черный, "есть цвет" = '1' - белый.
Амплитуды цвета там нет, и цвет, скажем, 0.5 мне программно внутри недоступен.

_________________
iLavr


08 Sep 2017 14:59
Profile
God

Joined: 02 Jan 2006 02:28
Posts: 1390
Location: Abakan
Reply with quote
Lavr wrote:
А что такое "средний цвет"? Если цвета всего два - черный и белый?
...
Амплитуды цвета там нет, и цвет, скажем, 0.5 мне программно внутри недоступен.


Может и не доступен, но вычислять нужно именно амплитуду. А вся эта засада из-за мнимой простоты вот этого алгоритма:
Lavr wrote:
Не мудрствуя лукаво со всякими полиномами, я просто соединяю вершины всех отсчетов прямыми линиями.
Получается непрерывное приближение исходного дискретного WAV сигнала.
А теперь я должен взять новые отсчеты этого непрерывного сигнала

Где применительно к цвету выборка возьмёт "0" при стоящей рядом "1", и тогда целые вертикальные или горизонтальные линии просто исчезнут, если попадут в пропуск выборки, что и происходит в Протеусе. Чтобы этого не происходило, к примеру "билинейный" алгоритм берёт точки из квадрата 2х2, вычисляет средний цвет/градацию, что и наблюдается в ворде. А без градаций любой алгоритм даст результат Протеуса.

Кстати, за счёт градаций получается мнимая линейность сжатия изображения.


08 Sep 2017 18:45
Profile
Supreme God
User avatar

Joined: 21 Oct 2009 08:08
Posts: 7777
Location: Россия
Reply with quote
jdigreze wrote:
А вся эта засада из-за мнимой простоты вот этого алгоритма:
Lavr wrote:
Не мудрствуя лукаво со всякими полиномами, я просто соединяю вершины всех отсчетов прямыми линиями.
Получается непрерывное приближение исходного дискретного WAV сигнала.
А теперь я должен взять новые отсчеты этого непрерывного сигнала

Этот метод ни в чем не виноват. Это называется кусочно-линейная аппроксимация функции.
Может быть, аппроксимация полиномом или там параболами и точнее, но кусочно-линейная
аппроксимация функции - быстрее в простых случаях.
Ну и я же сказал, что метод работает:
Lavr wrote:
...только если между отсчетами есть некоторая разница по амплитуде.

А в случае "0" и "1" этот метод не работает, и не в нём засада - тут и полиномом ничего не сделаешь.

_________________
iLavr


08 Sep 2017 20:47
Profile
Supreme God
User avatar

Joined: 21 Oct 2009 08:08
Posts: 7777
Location: Россия
Reply with quote
Повторил начальный эксперимент в более чистом виде: там была картинка, захваченная с экрана Proteus.
Теперь - это чисто BW-картинка размером 384х256. Но MS_WORD - справляется с ней! :o
Attachment:
LCD582GDI.gif
LCD582GDI.gif [ 32.23 KiB | Viewed 13922 times ]


А теперь - для сравнения - та же картинка, но сжатая функцией Win32 API - StretchBlt Lib "gdi32.dll" (...) до 60%.
Attachment:
LCDStretchBlt.gif
LCDStretchBlt.gif [ 4.15 KiB | Viewed 13922 times ]

Видно, что элементы изображения теряются, хотя я и облегчил задачу для StretchBlt Lib "gdi32.dll" (...),
превратив изображение в картинку с максимальным числом градаций яркости.

Похоже, что Proteus как раз и использует стандартную функциб Win32 API - StretchBlt Lib "gdi32.dll" (...),
а вот MS_WORD применяет другие алгоритмы.

_________________
iLavr


09 Sep 2017 10:00
Profile
Doomed

Joined: 18 Nov 2013 02:38
Posts: 662
Location: Москва
Reply with quote
http://www.geisswerks.com/ryan/FAQS/resize.html

Не проверял, но на взгляд, не плохо должно быть.

_________________
https://t.me/tronix_blog


09 Sep 2017 12:03
Profile
God

Joined: 02 Jan 2006 02:28
Posts: 1390
Location: Abakan
Reply with quote
Lavr wrote:
Теперь - это чисто BW-картинка размером 384х256. Но MS_WORD - справляется с ней!
Он её к полутонам привёл.
Lavr wrote:
Видно, что элементы изображения теряются, хотя я и облегчил задачу для StretchBlt Lib "gdi32.dll" (...),
превратив изображение в картинку с максимальным числом градаций яркости.
Значит стандартный стретчер работает по самому простому и самому быстрому алгоритму - Ближайший сосед (Nearest neighbor), а Ворд использует что-то более продвинутое из своих закромов, скорее всего - Суперсэмплинг.


09 Sep 2017 17:26
Profile
Devil

Joined: 26 May 2003 06:57
Posts: 859
Reply with quote
jdigreze wrote:
а Ворд использует что-то более продвинутое

Видимо делает сначала SetStretchBltMode(hdc, HALFTONE);

_________________
Страничка эмулятора наших компьютеров
http://bashkiria-2m.narod.ru/


14 Sep 2017 10:47
Profile WWW
Display posts from previous:  Sort by  
Reply to topic   [ 16 posts ]  Go to page 1, 2  Next

Who is online

Users browsing this forum: No registered users and 16 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
Powered by phpBB® Forum Software © phpBB Group
Designed by ST Software.