Ahogy tettem a leggyorsabb a képek átméretezése
Ahogy tettem a leggyorsabb a képek átméretezése. Rész 0 78
- 14.02.17 08:17 •
- Homm •
- • # 321744
- • Habrahabr
- 66 •
- 14800
- mint a Forbes, csak jobb.
Helló, a nevem Sasha, én írtam a leggyorsabb a képek átméretezése a mai x86 processzorok. Azt állítják, mint az összes többi könyvtár voltam képes megtalálni és vizsgálat, lassabb volt. Vettem a kihívást, ha dolgozik az optimalizálása a képek átméretezése a légy Uploadcare. Úgy döntöttünk, hogy nyissa ki a kódot, és az eredmény az volt Párna-SIMD projekt. Bárki könnyen használni az alkalmazás Pythonban.
Bármilyen kód fut egy adott hardver- és jó optimalizálás csak úgy érhető el, ha megértjük az építészet. Annyit kiadunk egy 4 vagy 5 cikkből, hogy megmondja, hogyan kell alkalmazni a tudás vas architektúra optimalizálása az igazi probléma. Az ő példája azt szeretnénk bátorítani, hogy optimalizálja más alkalmazásokat. Az első két cikk fog megjelenni egy héten belül, és a többi -, ha kész.
A „képátméretezése” kifejezés azt jelenti képméret módosítása segítségével újramintavételezési módszerrel csomagot. Újramintavételezési végzünk egy sor 8-bites RGB pixelek a memóriában, tekintet nélkül a kódolási és dekódolási, azonban a memória kiosztás és a végső kép előállításához az együtthatók szükséges egy adott művelet.
Ez annyira szigorúak. Nincsenek trükkök (például dekódolása dzhipega kisebb képek), és nem egyesíti algoritmusok csak a tisztességes mérése egy adott algoritmus. Trükkök és optimalizálása bizonyos esetekben lehet alkalmazni később, ezek nem képezik e cikksorozat.
... a újramintavételezési módszer a csomagot. Mi az?
Annak érdekében, hogy világos, hogy pontosan mit kell optimalizálni, megmondom mi újramintavételezési convolutions. Convolution (konvolúció a jogot, hogy beszélni diszkrét értékek diszkrét képpontok.) - egy nagyon egyszerű matematikai művelet. Van egy bizonyos számú érték №1 (együtthatók), és egy sor értékek №2 (adat, ebben az esetben a támogatási intenzitás a pixelek a csatornák). Az eredmény a konvolúció a két sorozat az összege a termék valamennyi tagja párban. Csakúgy, mint hogy - az értékek összege. Matan véget ért, mielőtt elkezdődött.
Szűrő funkciók nem végtelenek, értékük nem egyenlő nullával csak a központi része: ez egy értéktartományt bilineáris szűrő -1 és 1; a bicubic -2 és 2, a Lanczos -3 és 3 (bár vannak még más fajták Lanczos).
Ezek a számok az úgynevezett szűrő ablakon, szűrő alkalmazása csak ebben a tartományban, és azon túl nulla. Ennek megfelelően, a számát háttér pixelek szükséges konvolúciót vesszük a sugara az ablak méretét szűrő szorozva a csökkentési arány (vagy egy, ha a növekedés bekövetkezik). Azt hiszem, ez jobb példa szemlélteti. Meg kell csökkenteni a kép szélessége a szélessége 2560 képpont 2048 használatával bicubic szűrőt. Tegyük fel, hogy meg akarjuk találni az érték a 33. végső képpont. A bicubic szűrő ablak mérete egyenlő a két, és a csökkentési tényezőt kapunk 2560/2048 = 1,25, így szükséges, hogy egy sor pixel az eredeti kép a padlóról ((33 -. 2) 1,25), hogy ceil ((33 + 2) . 1,25). Ie 38-én és 44-dik pixel. Ezekre képpontok számított az együtthatók.
Eddig a pontig azt mondtam számos tényező és a képpontok számát, tévesztve szem elől azt a tényt, hogy a kép - ez valójában egy kétdimenziós szerkezet. És mint a logika, ne kapcsolja ki a sort, és néhány eredeti kép területen. Azonban az egyik tulajdonsága a csomag, hogy a művelet végezhető külön mind függőlegesen, mind vízszintesen, hogy két menetben. Nagyjából elmondható, hogy ez csökkenti a bonyolultsága olyan konvolúciós O (n?) O (2n) (ténylegesen kisebb, de még mindig jelentős).
Miért mindegy konvolúció
Általában az „átméretezett kép„hordozza minimális információt arról, hogy mit kell tennie. Azt mondja, hogy van, hogy a végső méretét a kép az eredeti, megőrizve a geometria tárgyak formájában. De, hogy az eredeti kép eltérő lehet. Lehetőség van például, hogy mindkét végén a pixel egy pixel sorban a forrás és vigye változtatás nélkül. Ezt nevezik a legközelebbi szomszéd. A kép durva, egyenetlen, kellemetlen:
Ez azért történik, mert egy nagyon kis töredéke az eredeti pixel (a fenti példában, kevesebb mint egy százalék) használták a végső képet. Információk azok a pixelek, amelyek nem szerepelnek a végső kép, elvesztettük.
De úgy néz ki, mint az átméretezés a csomag:
Újramintavételezést segítségével kanyarulatok kellően figyelembe veszi a hozzájárulás minden egyes forrás pixel a végső képet. Univerzális, mert ad egyformán jó, és kiszámítható eredményeket széles skálatényező, nem tartalmaz torzítást lokálisan geometriát (azzal a megkötéssel, hogy egy szűrőt alkalmazunk, amely nem rendelkezik ilyen torzulás, mert néhány szűrők még mindig ad). És különben is, jól van, és olyan jó, minden oldalról, kivéve egyet: a teljesítmény.
Párna - a könyvtár a képkezeléshez Python által kifejlesztett, a közösség által vezetett Alex Clark és Eric Soroos. A Uploadcare Párna korábban használt, ahogy jött a csapat. Aztán úgy tűnt nekem furcsa - Work képekkel volt az egyik fő feladata, miért tart a könyvtár, a kötött nyelvet. Hát nem jobb, hogy ugyanazt a ImageMagick, amely egy csomó funkciók, amelyek milliói használják a fejlesztők, így valószínűleg minden kell jól a teljesítményt. Néhány év múlva, azt mondhatom, hogy ez volt a szerencse rám, és párna. Mint kiderül, a teljesítmény mind a könyvtárak elején közel azonos volt, de nagyon kétlem, hogy én lenne az ereje megtenni ImageMagicknek van valami, hogy én tettem párna.
Párna - ez a villa a nagyon régi PIL könyvtárban. Történelmileg, az átméretezés a PIL nem használták konvolúció. Az első végrehajtási átméretezés a konvolúció a PIL megjelent verzió 1.1.3 és elérhető volt használatakor antialias szűrőt, amelynek neve hangsúlyozza azt a tényt, hogy a fennmaradó használt szűrők alacsonyabb minőségű algoritmusok. A hálózat továbbra is gyakran megtalálható nem aktuális ajánlások használni, ha átméretezés a PIL (a párna, mint vevő) csak antialias szűrőt.
Sajnos antialias meglehetősen alacsony volt a termelékenység. Belenyúltam a forráskódot. hogy mit lehet tenni, és kiderült, hogy a végrehajtás átméretezése az antialias (azaz, konvolúció), akkor is lehet használni más szűrőkkel. A konstans maga antialias felel Lánczos szűrő, amely egy nagy ablak (± 3), ezért ez elég lassú. A legelső optimalizálás, hogy én akartam csinálni - viszont a hajtás bilineáris és bicubic szűrőket. Így lehetséges lenne az én alkalmazást olcsóbb bikubikus szűrőt (egy ablak ± 2) és nem túl veszít a minőség.
Következő érdekes volt nézni a kódot az átméretezés. Azt könnyen megtalálható ebben a modulban. És bár írok nagyrészt Pythonban, rögtön észrevettem néhány megkérdőjelezhető helyen a teljesítmény tekintetében. Miután több optimalizálási kaptam a növekedés 2,5-szerese (ez lesz szó a következő cikkben). Aztán elkezdtem kísérletezni a SIMD, átadása minden számítást egész agresszíven telepíteni ciklusok és a csoport számításai. A feladatot a rendkívül érdekes, a fejemben mindig is egy pár ötletet, hogyan lehetne javítani a teljesítményt. Azt zuhant a nyúl üregébe mélyebbre és mélyebbre, rendszeresen ellenőrzi a következő hipotézist.
Fokozatosan, a kód egyre több és nagyobb sebesség. Rész fejlesztések megadta magát vissza párna. De SIMD-kód nehéz volt mozogni, mert meg van írva egy adott építészeti és párna - egy cross-platform könyvtárban. Ezért úgy döntöttek, hogy ne egy cross-platform villa Párna-SIMD. Párna-SIMD változat teljes mértékben megfelelnek az eredeti változat a párna és adjuk hozzá a gyorsulás egyes műveleteket.
A legújabb változat a párna-SIMD AVX2 átméretezni futó 15-30-szer gyorsabb, mint az eredeti PIL. Mint mondtam az elején, hogy ez a gyors végrehajtását magas színvonalú átméretezés, amely képes voltam kipróbálni. Megnézheti az oldalt. amely összegyűjtötte a benchmark eredmények a különböző könyvtárakban.
mért teljesítményeket
A második oszlop az időt másodpercben, és a harmadik - a sávszélesség az eredeti kép ehhez a művelethez. Azaz, ha a műveletet elvégzik 0,2 másodperc, az áteresztőképesség lesz 2560? 1600 / 0,2 = 20,48 megapixel másodpercenként.
Ha ilyen hatást lehet extrapolálni, hogy a skála a bolygó, és cserélje ki az összes kódot foglalkozó átméretezés képek hatékonyabb felhasználása óriási lenne. Több tízezer mentett szerverek, több száz kilowatt villamos energiát. És ez egy milliomod része a globális fogyasztás. Igen, lehetett menteni a bolygót!
majd hirtelen ez pátosz?
gyors - ítélet becslést kell a leggyorsabb, ez felesleges, van, hogy elég gyors, hogy megoldja a kitűzött nyelvi kihívásokat, és Python foglalkozik velük, az utóbbi időben egyre sikeresebb és sikeres, és ha nem, akkor lehetőség van arra, hogy adjunk hozzá sebesség és igen jelentős mértékben, más szóval azt, hogy feladataikat jól, mintha ütvefúró, nem minden vált körmök
Talán valami, amit nem értettem, de vettem OpenCV és csak az úgynevezett átméretezés:
2560 x 1600 -> 320 x 200 bicubic = 3 ms
És te SIMD SSE4 - 7,7 ms, és SIMD AVX2 - 5.7 ms, azaz 2-2,5-szer lassabb.
Az a tény, hogy a OpenCV átméretezése módszer nem használja a csomagban. Ugyanazt a módszert, mint a párna, hogy 2.7-es verziója a bilineáris és bicubic ugyanazt a módszert, hogy használják a canvas elem a böngészők. Küldök olvassa el a cikket a képek átméretezése a böngészőben. Minden nagyon rossz. Minimális különbség - csökkenő képablakot nem növeli faktorral csökken, ahogy konvolúció. De ez radikálisan befolyásolja a minőséget és sebességet. Például, hogy ugyanazt a képet. ez a cikk (7000. 2926> 512 214).
Mint látható, ez sokkal közelebb van a legközelebbi szomszéd. A feladattól függően lehet gondolni egy ilyen algoritmus, vagy úgy vélik, hogy érvénytelen.
Köszönöm az informatív, és ami a legfontosabb, érthető történet) módszert meghatározott nagyon világosan és egyértelműen, nagyon híres írva.
Azt azonban nem lehet nagyon hálás, ha azt mondja nekem egy linket, ahol ugyanaz az elv egyértelműen le kell egyszerűsíteni a konvolúció két menetben. Mert abban a pillanatban én nem egyértelmű, hogy ez adhat azonos eredményt (nem tudjuk, mert valójában egy ilyen forgatókönyv, hogy vegye figyelembe a hatását a diagonális pixel a szűrő ablakban).
Minden pixel után a vízszintes konvolúciós válik kombinációja több szomszédos pixelek vízszintesen. Későbbi átjáró ötvözi függőleges konvolúció képpontok között már nem az eredeti képet, és ezek a „kombináció több pixel.” Mondjuk a 5x5 szűrőt, ha vagyunk kíváncsiak szög (-2, 2) lépésben kiszámítunk egy konvolúciós vízszintes pixel p_horizontal [2] = weighted_sum ([-2,2], [-1,2], [0,2], [ 1.2], [2,2]), majd a helyettesítő p = weighted_sum (p_horizontal [-2], [-1], [0], [1], [2]); Könnyen belátható, hogy ez az összeg fog jönni, és [-2,2] némi súlya.
Ez nem működik minden lehetséges 2D konvolúció, de csak azok speciális alosztálya úgynevezett convolutions a „szétválasztható” magot. Szerencsére szinte minden átméretezés elválasztható kernel.
Köszönöm, úgy tűnik, hogy megértsék)
Függőleges konvolúciós mi „add” pixel függőleges „vonal” a kívánt arányt, amelyek mindegyike már összegezte vízszintes „vonal”. És plusz „saját” sor már elszámolni. Igen, minden szuper.
Az egyetlen dolog, ami - ha eljut a tényezők lehetnek bizonyos közös.
Például, azt szeretnék, hogy egy 3x3 filter az egyszerűség és a szélsőséges pixeles felbontás 0,4 együtthatóval. Ezután, amikor a vízszintes konvolúció hozzátesszük 0.4 a szélsőséges elemek a lényeg, és ha ehhez hozzátesszük a függőleges területén 0,4 * 0,4 = 0,16, azaz négyzetes együttható mi lesz. Bár logikus, talán, használja a négyzetgyöke (például a távolság). Ha a szűrő nem bi-lineáris, és minden bizonnyal nem áll arányban azzal a távolsággal, de azt jelenti, hogy minden ugyanaz együtthatók e mátrix kellene számítani ez a módszer lesz :)