Grouping - Cornell University

Grouping - Cornell University

Grouping What is grouping? Why grouping? Pixels property of sensor, not world Reasoning at object level (might) make things easy: objects at consistent depth

objects can be recognized objects move as one "I stand at the window and see a house, trees, sky. Theoretically I might say there were 327 brightnesses and nuances of colour. Do I have "327"? No. I have sky, house, and trees." Max Wertheimer

Regions Boundaries Is grouping well-defined? Depends on purpose A

B C Object parts Background segmentation

Is grouping well-defined? A Perceptual organization forms a tree: Image B

A BG B L-bird R-bird

C grass bush far

beak body beak body

C eye D. Martin, C. Fowlkes, D. Tal, J. Malik. "A Database of Human Segmented Natural Images and its Application to Evaluating Segmentation Algorithms and Measuring Ecological Statistics", ICCV, 2001 head

eye head How do we group things? Gestalt principles Principle of proximity

https://courses.lumenlearning.com/wsu-sandbox/chapter/gestalt-principles-of-perception/ How do we group things? Gestalt principles Principle of similarity https://courses.lumenlearning.com/wsu-sandbox/chapter/gestalt-principles-of-perception/

How do we group things? Gestalt principles Principle of continuity and closure https://courses.lumenlearning.com/wsu-sandbox/chapter/gestalt-principles-of-perception/ How do we group things? Gestalt principles

Principle of common fate Gestalt principles in the context of images Principle of proximity: nearby pixels are part of the same object Principle of similarity: similar pixels are part of the same object

Look for differences in color, intensity, or texture across the boundary Principle of closure and continuity: contours are likely to continue High-level knowledge? Regions

Boundaries Designing a good boundary detector Differences in color, intensity, or texture across the boundary Continuity and closure

High-level knowledge Criteria for a good boundary detector Criteria for a good boundary detector: Good detection: Fire only on real edges, not anywhere else Good localization the edges detected must be as close as possible to the true edges

the detector must return one point only for each true edge point Source: L. Fei-Fei Canny edge detector The classic edge detector Baseline for all later work on grouping

Theoretical model: step-edges corrupted by additive Gaussian noise J. Canny, A Computational Approach To Edge Detection, IEEE Trans. Pattern Analysis and Machine Intelligence, 8:679-714, 1986. 22,000 citations! Source: L. Fei-Fei

Image gradient The gradient of an image: The gradient points in the direction of most rapid increase in intensity The edge strength is given by the gradient magnitude: The gradient direction is given by:

how does this relate to the direction of the edge? Source: Steve Seitz Image gradient Source: L. Lazebnik With a little Gaussian noise

Gradient Source: D. Hoiem Effects of noise Noisy input image

Where is the edge? Source: S. Seitz Effects of noise Noise is high frequency Differentiation accentuates noise

Solution: smooth first f h f*h To find edges, look for peaks in

Source: S. Seitz Associative property of convolution Differentiation is a convolution Convolution is associative: This saves us one operation:

f Source: S. Seitz 2D edge detection filters Gaussian

derivative of Gaussian (x) Derivative of Gaussian filter x-direction y-direction

Example original image Compute Gradients (DoG) X-Derivative of Gaussian

Y-Derivative of Gaussian Image gradient The gradient of an image: The gradient points in the direction of most rapid increase in intensity The edge strength is given by the gradient magnitude:

The gradient direction is given by: how does this relate to the direction of the edge? Source: Steve Seitz Gradient magnitude and orientation Orientation is undefined at pixels with 0 gradient

Magnitude Orientation theta = numpy.arctan2(gy, gx) Non-maximum suppression for each orientation At q, we have a

maximum if the value is larger than those at both p and at r. Interpolate to get these values. Source: D. Forsyth

Before Non-max Suppression After Non-max Suppression Hysteresis thresholding Threshold at low/high levels to get weak/strong edge pixels Do connected components, starting from strong edge pixels

Final Canny Edges Canny edge detector 1. Filter image with x, y derivatives of Gaussian 2. Find magnitude and orientation of gradient 3. Non-maximum suppression: Thin multi-pixel wide ridges down to single pixel width

4. Thresholding and linking (hysteresis): Define two thresholds: low and high Use the high threshold to start edge curves and the low threshold to continue them Source: D. Lowe, L. Fei-Fei

Does Canny always work? The challenges of edge detection Texture Low-contrast boundaries Regions

Boundaries Grouping by clustering G R

B Grouping by clustering Idea: embed pixels into highdimensional space (e.g. 3dimensions) Each pixel is a

point Group together points K-means Assumption: each group is a Gaussian with different means and same standard deviation

Suppose we know all . Which group should a point belong to? The j with highest = The j with smallest K-means Assumption: each group = a Gaussian with different means and same standard deviation

If means are known, then trivial assignment to groups. How? Assign data point to nearest mean! K-means Problem: means are not known What if we know a set of points from each cluster?

belong to cluster k What should be ? K-means Problem: means are not known If assignment of points to clusters is known, then finding means is easy How? Compute the mean of every cluster!

K-means Given means, can assign points to clusters Given assignments, can compute means Idea: iterate! K-means Step-1 : randomly pick k centers

K-means Step 2: Assign each point to nearest center K-means Step 3: re-estimate centers K-means

Step 4: Repeat K-means - another example K-means Input: set of data points, k 1. Randomly pick k points as means

2. For i in [0, maxiters]: 1. Assign each point to nearest center 2. Re-estimate each center as mean of points assigned to it K-means - the math Input: set of data points , k 1. Randomly pick k points as means

2. For iteration in [0, maxiters]: 1. Assign each point to nearest center 2. Re-estimate each center as mean of points assigned to it K-means - the math An objective function that must be minimized:

Every iteration of k-means takes a downward step: Fixes and sets to minimize objective Fixes and sets to minimize objective K-means on image pixels K-means on image pixels

Picture courtesy David Forsyth One of the clusters from kmeans K-means on image pixels What is wrong?

Pixel position Nearby pixels are likely to belong to the same object Far-away pixels are likely to belong to different objects How do we incorporate pixel position?

Instead of representing each pixel as (r,g,b) Represent each pixel as (r,g,b,x,y) K-means on image pixels The issues with k-means Captures pixel similarity

but Doesnt capture continuity Captures proximity only weakly Can merge far away objects together Requires knowledge of k!

Oversegmentation and superpixels We dont know k. What is a safe choice? Idea: Use large k Can potentially break big objects, but will hopefully not merge unrelated objects Later processing can decide which groups to merge

Called superpixels

Recently Viewed Presentations

  • Communication Accomodation Theory (Howard Giles)

    Communication Accomodation Theory (Howard Giles)

    Communication Accommodation Theory(Howard Giles) Socio-psychological tradition. Communication Accommodation. When two people from different ethnic or cultural groups interact, they tend to accommodate each other in the way they speak in order to gain the other's approval.
  • Lack of Minority K65R Resistant Viral Populations Detected

    Lack of Minority K65R Resistant Viral Populations Detected

    K65 : 5'AGT ATT TGC CAT AAA AA 3'(HIV-1 subtype C) K65: 5'AGT ATT TGC CAT AAA GA 3' (all other HIV-1 subtypes except C) M184: 5'AGA TCC TAC ATA CAA GTC ATC3' Tenofovir (TDF) is being used increasingly as...
  • Introduction - Thrombosis Canada - Thrombose Canada

    Introduction - Thrombosis Canada - Thrombose Canada

    sur la Thrombose du Canada. www.tigc.org. B. The CCS antiplatelet committee was composed of national physicians, with specialties in interventional cardiology, general cardiology, thrombosis, internal medicine, primary care, CV surgery, peripheral vascular surgery, neurology, endocrinology ...
  • Circles - Modules 15 - Mr. Gussaroff's Math Site!

    Circles - Modules 15 - Mr. Gussaroff's Math Site!

    Module 15: Angles and Segments in Circles. Central Angle. A. B. Measure of Arc AB = 105˚ 105˚ Central Angle - The angle created by two. radii of the circle, with the vertex being the center of the circle.
  • Welcome To Purdue

    Welcome To Purdue

    Our CAMPEP Report. The objectives of the medical physics program are . to deliver a core medical physics program that embodies the content and spirit of American Association of Physicists in Medicine (AAPM) Report 197 Academic Program Recommendations for Graduate...
  • Teoría de sistemas y "pensamiento complejo"

    Teoría de sistemas y "pensamiento complejo"

    * lo sencillo es hermoso * Harry Markopolos venía avisando... "Harry Markopolos puso la cabeza de Bernard Madoff en bandeja de plata ante el supervisor del mercado de valores (SEC). Eso fue hace nueve años, cuando alertó al supervisor estadounidense...
  • Communication and Optimal Resolution (CANDOR) Toolkit Module 5:

    Communication and Optimal Resolution (CANDOR) Toolkit Module 5:

    Describe the importance of disclosure communication and transparency with patients and families. Define the elements of disclosure communication. Describe the knowledge, skills, and attitudes necessary for an individual to serve as a CANDOR Disclosure Lead. Identify the essential role of...
  • Dr S H Quraishi Consultant Psychiatrist Lancashire Care

    Dr S H Quraishi Consultant Psychiatrist Lancashire Care

    Times New Roman Arial Calibri Default Design Slide 1 PMETB PMETB PMETB PMETB PMETB Objectives of this session Before Preparing Application Portfolio Why a Portfolio What is a Portfolio Portfolio's in other Professions Company Directors Portfolio Portfolio of a doctor-...