Kvadratikus optimalizáció és alkalmazásai digitális képfeldolgozásban – Boros Endre külső tag székfoglaló előadása

Nemlineáris diszkrét optimalizációs problémák megoldását 50-60 éve tanulmányozzák a kutatók. Ezek általában számítástechnikailag igen nehéz feladatok, de jelentőségük nagy, mert számos alkalmazásuk van. Az egyik fontos alkalmazási terület a digitális képfeldolgozás, amelyben sok különböző gyakorlati feladat vezethető vissza nemlineáris, azon belül különösen kvadratikus, 0-1-es optimalizációs problémákra. Boros Endre előadásában egy 30 éves kutatássorozat eredményeiről számolt be.

Boros Endre Fotó: mta.hu/Szigeti Tamás

Képgaléria a székfoglaló előadásrólA legalapvetőbb képfeldolgozási feladatok egy közelítő modellje kvadratikus 0-1-es problémákhoz vezet. Az előadó ilyen kvadratikus problémákat tanulmányozott Hammer Péterrel az 1980-as években, és felfedeztek egy hatékony eljárást, amellyel e feladatok egyszerűbb és kisebb méretű formára hozhatók. A módszerrel bizonyos esetekben meghatározhatók a változók egy részének optimális értékei. Mivel azonban nem ad előzetes garanciákat, és sikere függ a problémától, 30 évvel ezelőtt nem látszott ígéretes eljárásnak.

Úgy 12-13 évvel ezelőtt a megnövekedett számítógépes kapacitás lehetővé tette, hogy a módszert kipróbálják már a gyakorlatban is használható méretű problémákon. Meglepő módon sok gyakorlati problémára – köztük a képfeldolgozásból eredőkre – igen hatékonynak bizonyult: gyakran a változók 60-80%-át sikerült a bizonyíthatóan optimális értéken rögzíteni. Boros Endre egy 2006-ban a Cornell Egyetemen tartott előadása után a képfeldolgozással foglalkozó informatikusok felfigyeltek a módszerre. Néhány év alatt nagyon népszerű lett, QPBO néven terjedt el, és sok ma használatos szoftver épül rá. Ma a Google keresőben már majdnem 15 000 weboldal foglalkozik a kapcsolódó eredményekkel, kutatással.

A módszer hatékonysága arra ösztönözte a kutatókat, hogy más, bonyolultabb problémákat is megpróbáljanak kvadratikus 0-1-es optimalizációs problémaként megfogalmazni, hogy a QPBO módszer rájuk is alkalmazható legyen. Ez vezet el az előadás fő részéhez, amely egy máig elhúzódó, igen aktív kutatási területről számol be.

A bonyolultabb és egyre gyakoribb alkalmazások miatt megnövekedett fontosságú gyakorlati problémák egyre magasabb fokú nemlineáris 0-1-es optimalizációs problémákhoz vezetnek. Sajnos ezekre mindmáig nincs a QPBO-hoz hasonló hatékony módszer. Így megnőtt az igény arra, hogy egy ilyen magasabb fokú polinomiális problémát ekvivalens kvadratikus problémaként fogalmazzunk meg. Ez úgy oldható meg, hogy további mesterséges változókat vezetünk be, amelyek segítségével le tudjuk csökkenteni a polinom fokszámát kettőre. Lényeges kérdés természetesen, hogy pontosan hogyan lehet ezt megtenni, milyen hatékonysággal, és hány mesterséges változóra van hozzá szükségünk. Boros Endre előadásának zárórészében ezekkel a problémákkal kapcsolatos friss eredményekről számolt be.

Az előadás anyaga a következő munkatársakkal végzett közös kutatások eredményeire épül: Martin Anthony (London School of Economics), Yves Crama (University of Liege), Alex Fix (Cornell University), Aritanan Gruber (University of São Paulo), Peter L. Hammer (1936–2006; Rutgers University), Gabriel Tavares (FICO, Xpress-MP), Ramin Zabih (Cornell University).