nedoPC.org

Community of electronics hobbyists established in 2002

...
Atom Feed | View unanswered posts | View active topics It is currently 20 Sep 2017 09:10



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

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

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

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

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

_________________
iLavr


07 Sep 2017 06:29
Profile
Online
God

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


07 Sep 2017 07:56
Profile
Supreme God
User avatar

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

_________________
iLavr


07 Sep 2017 09:24
Profile
Online
God

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


07 Sep 2017 20:55
Profile
Supreme God
User avatar

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

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

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

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

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

_________________
iLavr


07 Sep 2017 21:23
Profile
Doomed

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


08 Sep 2017 05:40
Profile
Supreme God
User avatar

Joined: 21 Oct 2009 11: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 09:49
Profile
Supreme God
User avatar

Joined: 21 Oct 2009 11: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 85 times ]


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

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

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

_________________
iLavr


08 Sep 2017 11:28
Profile
Writer

Joined: 21 Mar 2017 15:50
Posts: 23
Location: Spb
Reply with quote
Как по мне, то берется квадрат (2х2, 3х3, 4х4) и вычисляется средний цвет. При "не кратном зуммировании" квадраты могут накладываться друг на друга на 1 пиксель (даже через несколько столбцов/строк).


Attachments:
25.png
25.png [ 28.44 KiB | Viewed 74 times ]
08 Sep 2017 16:54
Profile
Writer

Joined: 21 Mar 2017 15:50
Posts: 23
Location: Spb
Reply with quote
Вот тут хорошо заметно, что некоторые вертикали лестниц стали двойными.


Attachments:
30.png
30.png [ 24.09 KiB | Viewed 74 times ]
08 Sep 2017 16:59
Profile
Writer

Joined: 21 Mar 2017 15:50
Posts: 23
Location: Spb
Reply with quote
Lavr wrote:
А вот Proteus, масштабируя изображение, тонкие линии начинает терять...

Видимо он не изменяет (расширяет) палитру, а тупо берет каждую n-ю строку/столбец изображения. Плохо, зато быстро. В том числе и по скорости написания кода.

А откуда картинка, если не секрет? Гугль как-то помалкивает...


08 Sep 2017 17:05
Profile
Supreme God
User avatar

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

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

_________________
iLavr


08 Sep 2017 17:59
Profile
Online
God

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


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

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

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


08 Sep 2017 21:45
Profile
Supreme God
User avatar

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

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

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

_________________
iLavr


08 Sep 2017 23:47
Profile
Supreme God
User avatar

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


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

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

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

_________________
iLavr


09 Sep 2017 13:00
Profile
Display posts from previous:  Sort by  
Reply to topic   [ 20 posts ]  Go to page 1, 2  Next

Who is online

Users browsing this forum: No registered users and 1 guest


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.