首页patchmatch stereo matching
patchmatch stereo matching
需积分: 10 139 浏览量 更新于2023-05-22 评论 收藏 59.09MB PDF 举报
PatchMatch: A Fast Randomized Matching
Algorithm with Application to Image and Video
Presented to the Faculty
of Princeton University
in Candidacy for the Degree
of Doctor of Philosophy
Recommended for Acceptance
by the Department of
Adviser: Adam Finkelstein
Copyright by Connelly Barnes, 2011.
All Rights Reserved
This thesis presents a novel fast randomized matching algorithm for ﬁnding correspondences between
small local regions of images. We also explore a wide variety of applications of this new fast
randomized matching technique.
The core matching algorithm, which we call PatchMatch, can ﬁnd similar regions or “patches” of
an image one to two orders of magnitude faster than previous techniques. The algorithm is motivated
by statistical properties of nearest neighbors in natural images. We observe that neighboring
correspondences tend to be similar or “coherent” and use this observation in our algorithm in
order to quickly converge to an approximate solution. Our algorithm in the most general form can
ﬁnd k-nearest neighbor matchings, using patches that translate, rotate, or scale, using arbitrary
descriptors, and between two or more images. Speed-ups are obtained over alternative techniques
in a number of these areas. We analyze convergence both empirically and theoretically for many of
these image matching algorithms.
We have explored many applications of this matching algorithm. In computer graphics, we have
explored removing unwanted objects from images, seamlessly moving objects in images, changing
image aspect ratios, and video summarization. Because our technique for removing unwanted objects
from photographs is both high quality and interactive, due to the fast matching algorithm, it has been
included in Adobe Photoshop CS5 as a new feature “content aware ﬁll.” In computer vision we have
explored denoising images, object detection, detecting image forgeries, and detecting symmetries.
We also apply our algorithm to large collections of images. We conclude by discussing the limitations
of our algorithm and areas for future research.
I would like to thank my advisor, Adam Finkelstein, for supporting me and being a good role model.
I was fortunate to work with a number of collaborators: Jia Deng, Dan B Goldman, Hugues
Hoppe, David Jacobs, Jacob Lewellen, Jason Sanders, Eli Shechtman, Szymon Rusinkiewicz, and
Tim Weyrich. Special thanks go to Dan Goldman and Eli Shechtman for providing research
mentorship during my three internships at Adobe Systems. From you and my advisor, I have
learned a great deal about research, career, and life. Thanks to the other Princeton graphics lab
members, who provided useful research advise, including Aleksey Boyko, Xiaobai Chen, Forrester
Cole, Tom Funkhouser, Vladimir Kim, Jingwan Lu, Linjie Luo, and Corey Toler-Franklin. Thanks
also to the reviewers of papers at TIGGRAPH and Adobe CTL Retreat.
Special thanks to our collaborator Jacob Lewellen who worked on PatchWeb for his undergrad-
uate thesis at Princeton.
I thank the following funding sources for sponsoring this work: National Science Foundation
under grant IIS-0511965 and 0937139, Adobe Systems Inc, and Microsoft.
We would like to thank a number of artists for their original works. We thank Lorelay Bove for
the color script. The short ﬁlm Kind of a Blur is Copyright Skunk Creek Productions. The ﬁlms
Elephants Dream and Big Buck Bunny are licensed as Creative Commons by the Blender Foundation.
The ﬁlm Star Wreck is licensed as Creative Commons by Energia Productions. We thank the
following Flickr users for Creative Commons imagery: Moogs, Swami Stream, Laurence & Annie,
Bill Liao, Badwsky, Cwalker71, Swamibu, Stuck in Customs, Xymox, Chris Penn, Eric Brumble,
Kibondo, Mazzaq Mazzacurati, Slack12, Thomashawk, Bex in Beijing, Paul Keleher, CarbonNYC,
SteveWhis, Arranging Matches, Professor Bop, Whirling Phoenix, Cindy47452, Sevenbrane, Wili,
Moi of Ra, Celie, and Bart van der Mark.
Finally, I thank everyone who supported me during my graduate school. Particularly, my parents,
brother, and grandparents have provided me support and encouragement. Thanks to my friends that
I have made at activities such as tango, rock climbing, skiing, and broomball.
To my parents for their love and encouragement.
- 我的内容管理 收起
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额