CS664 Computer Vision1. IntroductionDan Huttenlocher2Computer Vision Machines that “see”– Broad field, any course will cover a subset of problems and techniques Closely related fields of study– Artificial intelligence and machine learning (CS)– Spatial statistics (Math/Stats)– Image processing (EE/CE)– Algorithms and optimization (CS/OR)– Optics and reflectance models (Physics)– Human visual perception and cognition (Psych)– Animal vision (Neuroscience)3Preparation Background in– Algorithms and data structures– Writing code with attention to efficiency– Basic probability– Linear algebra Some degree of mathematical sophistication– Ability to learn new math along the way without too much effort4Course Requirements Readings for class Short in-class quizzes Two programming assignments– Probably easiest in C/C++ because of libraries such as OpenCV Open ended final project on topic of your choice5Applications of Computer Vision Computer vision increasingly useful as digital images become ubiquitous– But still many simple-seeming problems still beyond state of art Wide range of areas– Image and video enhancement for consumer and entertainment applications– Automatic detection of faces and license plates for privacy, recognition for security– Automated inspection for industrial applications– Robotic automation and user assistance 6Applications Industrial inspection– Wide range of industries from electronics to product labels to food– Match images to ideal prototypes• Highly controlled imaging conditions7Applications License plate reading– Roads and parking• E.g., garages, central London– License plate finding and character recognition– Structured location of plate8Applications Face detection and recognition– Finding faces in cluttered images– Recognizing faces (more controlled conditions)– Obscuring for privacy• E.g., Google’s Streetview9Applications Image cleanup (inpainting)– Replace pixels byfilling in surrounding image– Model as diffusion orspatial statisticalprocess– Texture challenging10Applications Image compositing and synthesis– Image/video insertion– Panoramic images by stitching together multiple photos– Merging best of several photos together11Applications Robotics– Ego-based and environment-based cameras– Integration of different sensing modalities•Lidar, radar, ir12Active Sensing Helps But… Lidar data provides cloud of points– Still “image-like” but with distances instead of intensities (or both) Still a vision problem– Analogous to working with stereo data13Applications Driving assistance (limited)– Monitor freeway lane change and forward vehicles14Visual Road Following Mobileye lane departure warning product15Computer Vision Algorithms Making things run fast an important part of practical computer vision techniques– Both algorithms and attention to coding details  Dynamic programming (DP) common– Methods that cache solutions to sub-problems rather than re-computing them Applies to problems that can be decomposed into sequence of stages– Each stage expressed in terms of results of fixed number of previous stages16Basic Example Consider following problem– For every pixel in an mxn image, sum all the pixel values in a wxh window around the pixel– Naïve method takes O(mnwh) time• 4 nested loops– Solve in O((m+w)(n+h)) time• Low constants, faster even for small windows0011212112123223991254795124798111183x3 sum ⇒17Simplify: What About 1D? For every element in an n-vector sum all elements in a width w interval Running sum – slide window of width w– Add entering element, subtract exiting one– Time independent of width w110232101223576321+1-0+2-1+3-0+2-1+0-2+1-3+0-0+1-2+0-0w=3182D Sums from 1D Sums Compute horizontal sums using sliding window On result compute vertical sums – This gives overall sum Running time independent of w,h– Just add 2 and subtract 2 elements per pixel Extension to variable size windows001121211212322399125479512479811118223135613356533519 Fast summations over arbitrary sized rectangles (intervals) – consider 1D Cumulative sum– S[x] = f[0] + … + f[x] DP recurrence O(n) time– S[x] = S[x-1] + f[x] Sum over region of f independent of size k– F[x]+…+F[x+k-1] = S[x+k-1]-S[x-1]Using Integral Images33322211123 6 9 11131516171820…20N-Dimensional Integral Images Analogous for higher dimensions, 2D:– S[x,y] = f[0,0] + … + f[0,y] + …f[x,0] + … + f[x,y] Separate recurrence per dimension– C[x,y] = C[x,y-1] + f[x,y] (column sum)– S[x,y] = S[x-1,y] + C[x,y] (total sum)– Or vice versa……21 Sum over arbitrary rectangle in constant time – with integral image preprocessing– S[b_r] + S[t_l-(1,1)] –S[b_l-(1,0)] – S[t_r-(0,1)] Also sum over arbitrary region, linear time– Running time proportional to length of boundary not areaFast Sums Using Integral Images+1-1+1-1+2-2+1b_rb_lt_rt_l22Fast Detection With II Features formed from combinations of sums over rectangles– For example positive and negative regions– Running time independent of rectangle size Viola and Jones use for face detection at approximately video rates23Fast Object Detection Classifier (set of rectangles) learned from examples24Course Outline Filtering Edge detection Corner Detection Interest points – SIFT features 2D Geometry/Transforms Matching, Chamfer and Hausdorff Distance Transforms 3D camera geometry Multiview geometry Image Panoramas Image stitching/mosaicing25Course Outline Visual motion/optical flow Parametric motion Structure from motion Stereo Markov Random Fields for stereo MRF Inference Image segmentation Face Recognition, Subspace Methods Object Category Recognition Flexible template models Tracking by