Signal & Image P ocessing: An In e na ional Jou nal (SIPIJ) Vol.10, No.4, Augus 2019
DOI: 10.5121/sipij.2019.10402 9
RANSAC BASED MOTION COMPENSATED
RESTORATION FOR COLONOSCOPY IMAGES
Nidhal Azawi and John Gauch
Depa men o Compu e Science and Compu e Enginee ing,
Uni e si y o A kansas, Faye e ille, A kansas
ABSTRACT
Colonoscopy is a p ocedu e ha has been used widely o de ec he abno mali y in a colon. Colonoscopy
images su e om a lo o p oblems ha make i ha d o he doc o o in es iga e/ unde s and a colon
pa ien . Un o una ely, wi h he cu en echnology, h ee is no way o doc o s o know i he whole colon
su ace has been in es iga ed o no . We ha e de eloped a me hod ha u ilizes RANSAC-based image
egis a ion o align sequences o any leng h in he colonoscopy ideo and es o es each ame o he ideo
using in o ma ion om hese aligned images. We p oposed wo me hods. Fi s me hod used he deep neu al
ne o he classi ica ion o in o ma i e and non-in o ma i e image. The classi ica ion esul was used as a
p ep ocessing o alignmen me hod. Also, we p oposed a isualiza ion s uc u e o he classi ica ion
esul s. The second me hod used he alignmen o decide/classi y he bad and good alignmen by using wo
ac o s. The i s ac o is he accumula ed e o and he second ac o con ain h ee checking s eps ha
check he pai e o alignmen beside he geome y ans o m s a us. The second me hod was able o align
long sequences.
KEYWORDS
Visualiza ion, RANSAC, sequence leng h, geome y ans o m, classi ica ion, Colonoscopy.
1. INTRODUCTION
The main goal o his pape is o emo e specula highligh s and shiny a eas in colonoscopy
images. Colonoscopy images su e om many p oblems. Some o hese p oblems/issues a e
blu ing which caused by ei he he came a is e y close o he colon su ace o some di on he
lens ha p e en he doc o o see hings clea ly. Ano he p oblem is he exis ence o he specula
highligh s which a e a y om one image o ano he based on he amoun o ligh e lec ed om
he colon su ace o he came a which has been illus a ed in de ail in ou p e ious wo pape s.
We used image egis a ion as a ool o help o emo e some unwan ed a e ac s om
colonoscopy images. We add essed he p oblem o colonoscopy image egis a ion in [1], [2].
The p oposed app oach elies on h ee p e-p ocessing s eps. These h ee p ocessing s eps a e he
emo al o non-in o ma i e images, median and mean il e ing wi h o wi hou image esizing
and image esizing. To he bes o ou knowledge we a e he i s esea che who es ed hese
h ee p e-p ocessing s eps in image egis a ion o colonoscopy images. We we e able o es o e
and enhance image de ails in colonoscopy by c ea ing an image pano ama om egis e ed
images. The expe imen al esul s show ha he emo al o non-in o ma i e images allows
enhancing he alignmen esul s.
Signal & Image P ocessing: An In e na ional Jou nal (SIPIJ) Vol.10, No.4, Augus 2019
10
In his pape , we ha e modi ied ou app oach by excluding he p ep ocessing classi ica ion phase
and ins ead we used ano he app oach o classi y bad and good aligned images. We used wo
ac o s o con ol he p ocess o aligning sequence o images. Fi s ac o by compu ing he
accumula ed e o a e and be o e alignmen o con ol he p ocess o aligning sequence o
images beside elying on he h ee condi ion in ou p e ious app oach o au oma ically exclude
he unwan ed images ha canno be aligned wi h oge he . This app oach can speed up he
algo i hm implemen a ion by omi ing he classi ica ion phase and le he alignmen algo i hm
decide he good and bad aligned images.
A lo o wo k has been done o align wo o mo e han one image and we a e going o men ion
some o hem. Image egis a ion/alignmen has been used in many ields such as compu e
ision, medical image p ocessing, mo ion acking and many o he s. Fo his eason, a lo o wo k
has been done o de elop as and e icien image alignmen me hods [2].
Image egis a ion has been de ined in many ways. Some au ho s de ined he image egis a ion is
he p ocess o ma ching common ea u es in o de o align wo o mo e images. O he au ho s
men ioned ha image alignmen is he way o iden i ying an op imal ans o ma ion ha can i o
gi e he bes ans o ma ion o a pa icula inpu image [3][4]. These images can be aken om
di e en iewpoin s. Image egis a ion-based ea u e ma ching in ol es ea u e de ec ion and
ex ac ion, ea u e ma ching, ans o ma ion and i ing unc ion, and image esampling and
ans o ma ion. Image egis a ion can in eg a e in o ma ion om a sequence o image.
Image alignmen me hods can be classi ied in o wo b oad ca ego ies based on how images a e
aligned wi h each o he . The i s ca ego y is a ea-based ma ching. A la ge numbe o me hods
ha e been de ised o compa ing pa ches, and o looking o (displacemen s wi h di e en
accu acy/speed ade-o s. Recen examples o a ea-based app oaches a e desc ibed by [2] [5],
[6], [7] and [8].
A p oposed wo k in 2018 has been implemen ed by [9]. Au ho s used wo phases o esol e he
specula highligh exis ence in he colonoscopy images. Fi s phase is o de ec he specula
highligh and he second phase pu pose is o emo e he specula by using inpain ing echniques.
Alignmen based ea u e ma ching is he second ca ego y. In his ca ego y, image is examined o
ind keys poin s and desc ibe he a ea su ounding each key poin o c ea e a ea u e ec o ha
can be ma ched agains ea u e ec o s om ano he image. Some o Key poin s examples a e
co ne s, cen es o b igh /da k objec s and blobs. Fea u e desc ip o s a e chosen so hey desc ibe
he local neighbo hood o ea u e poin s in a way ha is obus o changes in posi ion, o ien a ion,
scale, and illumina ion. The scale in a ian ea u e ans o m (SIFT) is e y popula me hod ha
used ea u e-based image alignmen echniques [10]. O he ecen examples o his app oach
include [11], [12] and [13].
Two s ages scheme has been p oposed by [14]. I consis s o Fi s , di ec ional mapping o
no malize images and o mi iga e he e ec o sa u a ion has been implemen ed. Second, in ensi y
in a ian ea u es ha e been ep esen ed using LBP (a non-pa ame ic local bina y pa e n). The
expe imen al esul s showed ha hei me hod achie ed be e accu acy han he s a e-o - he-a
me hods. A obus app oach agains non-uni o m illumina ion me hod has been done in image
alignmen based on ma ching o ela i e g adien map [15]. Images ha a e seen o cap u ed om
di e en iewpoin s has been used in [16]. The au ho men ioned ha hei app oach has he
abili y o dis inguish be ween squa e and ec angle while a ine in a ian app oaches could no
ecognize hem.
Signal & Image P ocessing: An In e na ional Jou nal (SIPIJ) Vol.10, No.4, Augus 2019
11
Image egis a ion has been used a lo in medical image analysis including many applica ions.
Applica ion a eas include compu e aided diagnosis, su ge y simula ion, in e en ion and
ea men planning, adia ion he apy, ana omy segmen a ion, compu a ional model building, and
con as enhanced based app oach, pa ial olume co ec ions based on CT images, and
assis ed/guided su ge y. Medical image egis a ion has been applied on a wide ange o body
images, see [17], [18], [19], [20] and [2].
The es o he pape is o ganized as ollows. Sec ion 2 p esen s ou wo p oposed me hods in
de ail wi h he expe imen al esul s. The conclusion and u u e wo k a e in Sec ion3.
2. OUR APPROACH
2.1. Me hod1
The me hod we used o ind and emo e bad images is based on ea u e-based image
classi ica ion desc ibed in ou ea lie pape [1]. Two app oaches ha e been p oposed wi h
RANSAC image alignmen o align colonoscopy images. We c ea ed wo isualiza ion s uc u e
o each app oach.
Fo cla i ica ion, we used RANSAC ( andom sample consensus) To egis e sequences o N
colonoscopy images o each o he o sol e o he p ojec i e ans o ma ion ha p oduces he bes
image alignmen . We used pai wise and N sequence alignmen me hods. RANSAC is a i ing
model o some da a in he p esence o ou lie s and i uses ial and e o app oach o ind model
pa ame e s ha bes i he da a. Fo mo e in o ma ion see [2], [21].
P ojec i e homog aphy ma ix has eigh DOF (deg ee o eedom) and he a ine homog aphy
ma ix has six DOF. Compa ison be ween he p ojec i e and a ine ans o ma ion and mo e
in o ma ion abou hem can be ound in [22], [23], [2].
Using RANSAC o align colonoscopy images wi h a ine ans o ma ions yields a la ge numbe
o nonsingula ans o ma ion ma ices, which means he e is no iable a ine ans o ma ion ha
can success ully align hese wo images. Hence a ine ans o ma ions a e no a good choice o
image egis a ion. Since he came a cap u ing colonoscopy ideo is changing posi ion du ing he
p ocedu e, we will use RANSAC o calcula e he bes p ojec i e ans o ma ion ha aligns all
pai s o images wi hin a mo ing 10 ame window o he colonoscopy image. The algo i hm we
use o egis e , and p ocess colonoscopy images has he ollowing s eps [2]:
S ep1: Classi y images—Images ha e been au oma ically classi ied as being in o ma i e o non-
in o ma i e using ea u e-based image classi ica ion [1].
S ep2:
• Loop o e all se s o 10 consecu i e images in he colonoscopy ideo.
• De ec and ex ac ea u es poin s o all 10 images in he sequence.
• Find he ma ching ea u e poin s o all pai s o images.
• Find he bes p ojec i e ans o ma ion using RANSAC algo i hm as ollow: -
a. Including all ans o ms ha sa is y all condi ions below:
1- The numbe o inlie s poin s g ea e han 5 poin s.
2- The de e minan o he ans o m g ea e han 0.5.
3- The image di e ence a e alignmen is less han be o e alignmen .
• Sa e aligned images.
• C ea e Pano ama.
Signal & Image P ocessing: An In e na ional Jou nal (SIPIJ) Vol.10, No.4, Augus 2019
12
2.1.1 Me hod1 Expe imen al Resul s
A p ep ocessing s ep o image pano ama c ea ion is used in [2]. The ou pu esul ed om he
p ep ocessing me hod is used as inpu o ou alignmen me hod. The bes alignmen wi h he 10
subsequen images has been calcula ed o each ame. We se he maximum sequence leng h o
11. Figu e 1 shows ha in some cases only a subse o he 10 subsequen images we e able o be
success ully aligned wi h he s a ing image.
Figu e 1. illus a ion o pano ama sequence leng h o colonoscopy ames [2].
We had a RMSE o 4.16 and a pe cen age aligned o 37% o he o iginal ideo bu a e
excluding he non-in o ma i e images using classi ica ion phase, he RMSE inc eased sligh ly o
4.38 and he pe cen age aligned inc eased signi ican ly o 48%.
The a e age CPU ime o image alignmen and pano ama c ea ion was also signi ican ly educed
when non-in o ma i e images we e excluded. This is because he RANSAC me hod execu e he
maximum numbe o i e a ion when ying o align no in o ma i e images. The esul s om ou
image sequence alignmen and pano ama c ea ion a e illus a ed in he igu es below. In igu e 2,
we show how bad subsequences p oduce e y poo pano amas ha has no use ul in o ma ion.
Enhanced e sion examples can be ound in igu e 3.
Figu e 2. Examples o unsuccess ul pano ama c ea ion. pano amas a e bad because hey a e been gene a ed
om highly dis o ed images [2].
Signal & Image P ocessing: An In e na ional Jou nal (SIPIJ) Vol.10, No.4, Augus 2019
13
Figu e 3. Examples o pano amas o image sequences ha had zooming ou mo ions. The images on he
igh a e he co esponding pano amas and he images on he le a e he o iginal colonoscopy images. Blue
boxes indica e a eas o whe e specula highligh s ha e been emo ed and whe e mo e image de ail is
isible [2].
This me hod helps o educe he specula highligh , bu he compu a ion ime g ows wi h he
exis ence o bad/nonin o ma i e images.
2.2. Me hod2
Excluding he classi ica ion phase can educe he compu a ional ime equi ed o implemen ou
RANSAC algo i hm. Me hod2 s eps can be lis ed as ollows: -
• Calcula e he accumula ed e o a e and be o e alignmen .
• Do he ollowing i he accumula ed e o a e alignmen is less han be o e alignmen
o Use s ep2 in me hod1
• Sa e he aligned sequences and c ea e sub ideos.
Signal & Image P ocessing: An In e na ional Jou nal (SIPIJ) Vol.10, No.4, Augus 2019
14
The accumula ed e o is esul ing om adding he e o gene a ed in each alignmen s ep. The
esul ed alignmen sequence au oma ically speci ied and con olled by calcula ion he o al
alignmen e o . Hence, we did no need o speci y he maximum leng h in his expe imen . In
his way, he bad and good aligned images ha e been classi ied au oma ically. A e we
implemen ed Me hod2, he esul s showed ha he aligned sequence leng h a ies o each ame
and some imes i exceeded 300 images.
3. CONCLUSION AND FUTURE WORK
We illus a ed ou me hods o mo ion compensa ed colonoscopy image es o a ion using
RANSAC-based image egis a ion. Me hod1 uses p ep ocessing s eps o align sequences o 11
consecu i e images(me hod1) while me hod2 exclude he p ep ocessing s eps o align sequences
o a ious consecu i e images leng h in he colonoscopy ideo.
In me hod1, ou expe imen s e i y ha he emo al o non-in o ma i e images p io o image
egis a ion educes he CPU ime necessa y o image alignmen and i helps o gene a e some
good pano amas o good images.
In me hod2, we ied o use he alignmen algo i hm o speci y he good sequence leng h ins ead
o using machine lea ning algo i hm. Me hod 2 helps o educe he compu a ion ime and i also
able o align a long sequence o consecu i e images.
Fo u u e wo k, we will ocus on enhancing and imp o ing he quali y o image alignmen by
educing he CPU ime using di e en pa allel p og amming and image egis a ion echniques.
REFERENCES
[1] N. Azawi, J. Gauch, “Au oma ic Me hod o Classi ica ion o In o ma i e and Nonin o ma i e
Images in Colonoscopy Video”, In . Con . on Medical Image P ocessing and Analysis (ICMIPA),
Vancou e , Canada, Augus 2018.
[2] N. Azawi and J. Gauch, “MOTION C OMPENSATED RESTORATION OF COLONOSCOPY
VIDEO,” pp. 243–256, 2019.
[3] L. Dung, C. Huang, and Y. Wu, “Implemen a ion o RANSAC Algo i hm o Fea u e-Based Image
Regis a ion,” Jou nal o Compu e and Communica ions, pp. 46–50, 2013.
[4] F.P.M. Oli ei a, J.M.R.S. Ta a es. Medical Image Regis a ion: a Re iew. Compu e Me hods in
Biomechanics and Biomedical Enginee ing 17(2):73-93, 2014.
[5] S. B. Kang, M. Uy endaele, S. Winde , and R. Szeliski, “High dynamic ange ideo,” ACM T ans.
G aph., ol. 23, no. 3, pp. 319–325, 2003.
[6] F. M. Candocia, “On he Fea u eless Regis a ion o Di e en ly Exposed Images,” in P oc. In . Con .
Imaging Science, Sys ems & Technology, Las Vegas, NV, USA, Jun. 2003, ol. I, pp. 163–169.
[7] Hossain and B. K. Gun u k, “High Dynamic Range Imaging o Non-S a ic Scenes,” in P oc.SPIE
Digi al Pho og aphy VII, 2011, ol. ol. 7876.
Signal & Image P ocessing: An In e na ional Jou nal (SIPIJ) Vol.10, No.4, Augus 2019
15
[8] H. Q. Luong, B. Goossens, A. Pizu ica, and W. Philips, “Join pho ome ic and geome ic image
egis a ion in he o al leas squa e sense,” Pa e n. Recogni ion. Le ., ol. 32, no. 15, pp. 2061–
2067, 2011.
[9] O. El Meslouhi, M. Ka douchi, H. Allali, T. Gadi, and Y. A. Benkaddou , “Au oma ic de ec ion and
inpain ing o specula e lec ions o colposcopic images,” Open Compu . Sci., ol. 1, no. 3, pp. 341–
354, 2011.
[10] D. G. Lowe, "Objec ecogni ion om local scale-in a ian ea u es," P oc. o he In . Con . on
Compu e Vision, pp. 1150–1157, 1999.
[11] B. Zi o a and J. Flusse , “Image egis a ion me hods: A su ey,” Image Vis. Compu e , ol. 21, pp.
977–1000, 2003.
[12] S. Old idge, G. Mille , and S. Fels, “Mapping he p oblem space o image egis a ion,” in P oc. Can.
Con . Compu e and Robo Vision, S . John’s, NF, Canada, May 2011, pp. 309–315.
[13] M. Tico and K. Pulli, “Robus image egis a ion o mul i- ame mobile applica ions,” in P oc.
Asiloma Con . Signals, Sys ems & Compu e s, Paci ic G o e, CA, USA, 2010, pp. 860–864.
[14] S. Wu, Z. Li, J. Zheng, and Z. Zhu, “Exposu e- obus alignmen o di e en ly exposed images,” IEEE
Signal P ocess. Le ., ol. 21, no. 7, pp. 885–889, 2014.
[15] S. Wu, Z. Li, J. Zheng, and Z. Zhu, “Exposu e- obus alignmen o di e en ly exposed images,” IEEE
Signal P ocess. Le ., ol. 21, no. 7, pp. 885–889, 2014.
[16] S. Wei and S. Lai, “Robus and e icien image alignmen based on ela i e g adien ma ching,” IEEE
T ans. image P ocess., ol. 15, no. 10, pp. 2936–43, 2006.
[17] C. Wu, B. Clipp, X. Li, J. M. F ahm, and M. Polle eys, “3D model ma ching wi h iewpoin in a ian
pa ches (VIP),” 26 h IEEE Con . Compu . Vis. Pa e n Recogni ion, CVPR, pp. 1–8, 2008.
[18] P. A. F eebo ough and N. C. Fox, “Modelling B ain De o ma ions in Alzheime Disease by Fluid
Regis a ion o Se ial 3D MR Images”, ol. 22. 1998.
[19] D. Leow, A. D. Klunde , C. R. Jack, A. W. Toga, A. M. Dale, M. A. Be ns ein, P. J. B i son, J. L.
Gun e , C. P. Wa d, J. L. Whi well, B. J. Bo owski, A. S. Fleishe , N. C. Fox, D. Ha ey, J. Ko nak,
N. Schu , C. S udholme, G. E. Alexande , M. W. Weine , and P. M. Thompson, “Longi udinal
s abili y o MRI o mapping b ain change using enso -based mo phome y,” Neu oimage, ol. 31,
no. 2, pp. 627–640, 2006.
[20] K. A. Ganse , H. Dickhaus, R. Me zne , and C. R. Wi z, “A de o mable digi al b ain a las sys em
acco ding o Talaic ach and Tou noux,” Med. Image Anal., ol. 8, no. 1, pp. 3–22, 2004.
[21] X. Huang, J. Ren, G. Gui audon, D. Boughne and T. M. Pe e s, "Rapid Dynamic Image Regis a ion
o he Bea ing Hea o Diagnosis and Su gical Na iga ion," in IEEE T ansac ions on Medical
Imaging, ol. 28, no. 11, pp. 1802-1814, No . 2009. doi:10.1109/TMI.2009.2024684.
[22] R. Redzuwan, N. A. M. Radzi, N. M. Din, and I. S. Mus a a, “A ine e sus p ojec i e ans o ma ion
o SIFT and RANSAC image ma ching me hods,” 2015 IEEE In . Con . Signal Image P ocess.
Appl., pp. 447–451, 2015.
[23] O. El Meslouhi, M. Ka douchi, H. Allali, T. Gadi, and Y. A. Benkaddou , “Au oma ic de ec ion and
inpain ing o specula e lec ions o colposcopic images,” Open Compu . Sci., ol. 1, no. 3, pp. 341–
354, 2011.
Signal & Image P ocessing: An In e na ional Jou nal (SIPIJ) Vol.10, No.4, Augus 2019
16
AUTHORS
Nidhal K. Azawi inished he bachelo and mas e ’s deg ee in compu e science / image p ocessing a he
Uni e si y o Technology / depa men o compu e science in Baghdad. She was an assis an eache in he
compu e science and Enginee ing in he Uni e si y o Al_Mus ansi iya in Baghdad. She is now a PhD
s uden esea che in compu e science and enginee ing depa men in he Uni e si y o A kansas. He
esea ch is in image p ocessing and compu e ision applica ion, biomedical image enhancemen , and
mo ion acking applica ions. He esea ch in e es seeks o combine machine lea ning wi h image
p ocessing and compu e ision o ad ancemen s in he medical ield pe aining o image enhancemen ,
econs uc ion, mo ion analysis, and isualiza ion.
John M. Gauch joined he compu e science and compu e enginee ing depa men a he Uni e si y o
A kansas as a p o esso in 2008. He held p e ious acul y posi ions a he Uni e si y o Kansas and
No heas e n Uni e si y. His esea ch in e es s include eal- ime digi al ideo p ocessing, con en -based
image and ideo e ie al, biomedical image enhancemen , image segmen a ion, and mo ion acking
applica ions. This esea ch has esul ed in o e six y publica ions in hese a eas including one book and one
pa en .
