Sketch Recognition for Digital Circuit Diagrams in the Classroom .

Uploaded on:
Category: Education / Career
Sketch Recognition for Digital Circuit Diagrams in the Classroom. Christine Alvarado Harvey Mudd College March 26, 2007. Joint work with the HMC Sketchers group: Aaron Wolin , Ned Burns , Jason Fennell, Max Pfleuger, Devin Smith, Paul Wais, Howard Chen, Matt Weiner, Prof. Sarah Harris.
Slide 1

Outline Recognition for Digital Circuit Diagrams in the Classroom Christine Alvarado Harvey Mudd College March 26, 2007 Joint work with the HMC Sketchers amass: Aaron Wolin , Ned Burns , Jason Fennell, Max Pfleuger, Devin Smith, Paul Wais, Howard Chen, Matt Weiner, Prof. Sarah Harris

Slide 2

Sketching In Education Digital Circuit Design

Slide 3

Educational Technologies "Most of the time the lab was more about fighting Xilinx than really learning anything useful" –HMC, E85 understudy

Slide 4

Problem: Design a 1-bit full snake

Slide 5

Correct! Also, 2 OR-2 AND-2 XOR-2 XOR-2

Slide 6

Goals Build an outline based circuit reproduction instrument that: is sufficiently powerful for genuine utilize permits understudies to portray as uninhibitedly as could reasonably be expected is less demanding to use than current programming We require: An incorporated circuit recreation framework Improved free-outline acknowledgment calculations A comprehension of UI issues

Slide 7

Integrated System Overview Front End hand-drawn portray Circuit Recognition and Translation Verilog record Simulation (Xilinx)

Slide 8

Integrated System Overview Front End User Interface Design hand-drawn draw Recognize Symbols Free-outline Recognition Construct Circuit Diagram Parsing Translate to Verilog document Simulation (Xilinx)

Slide 9

Sketch Recognition Subtasks Stroke Fragmentation NOR Symbol Recognition Stroke Grouping

Slide 10

A Typical Approach to Recognition Stroke Fragmentation Stroke Grouping Symbol Recognition

Slide 11

A Typical Approach to Recognition: Problem erroneous gathering

Slide 12

Why is Grouping Hard? No unmistakable limits in space…

Slide 13

Why is Grouping Hard? No unmistakable limits in space or time

Slide 14

A Typical Approach to Recognition: Problem ??? Stroke Grouping is impossible without acknowledgment (But acknowledgment is impossible without stroke gathering)

Slide 15

Our Approach Stroke Fragmentation Single-Stroke Recognition Stroke Grouping Symbol Recognition

Slide 16

Our Approach Stroke Fragmentation Single-Stroke Recognition Stroke Grouping Symbol Recognition

Slide 17

Single-Stroke Recognition Goal: Label every stroke as WIRE, GATE or SIGNAL Method: Conditional Random Field Approach in view of Yuan Qi, Martin Szummer, Thomas P. Minka. Chart Structure Recognition by Bayesian Conditional Random Fields June 2005 Proc Comp. Vision Pattern Recogn. (CVPR) C. Schmid and S. Soatto and C. Tomasi 191- - 196 entryway door wire entryway flag wire entryway wire

Slide 18

Conditional Random Field (CRF) Determines P( y | x ) y : vector of names ( wire or door ), one for every section (stroke) x : set of all perceptions (stroke highlights)

Slide 19

Single-Stroke Classification Demo

Slide 20

Training the CRF: Data Collection and Labeling

Slide 21

Data Collection Goal: Free outlining in building instruction Method: Distributed Tablet Computers to ~35 understudies in HMC E85 (advanced circuit plan) and E84 (simple circuit plan) Collected portrayals from notes, homeworks, and labs But shouldn\'t something be said about marking?

Slide 22

Labeling Tasks Stroke Fragmentation Stroke Grouping and Labeling

Slide 23

Labeler Demo

Slide 24

Designing the UI User Study to look at: Recognition Triggers (catch, motion, delay) Feedback components (shading, image, content) Error Rates and Types Preliminary Results Users favor dynamic acknowledgment Trigger must be solid Users infrequently trigger acknowledgment

Slide 25

(Some Immediate) Future Work Stroke Fragmentation Single-Stroke Recognition Stroke Grouping Symbol Recognition Multi-class acknowledgment wire versus entryway versus flag

Slide 26

Conclusion Single-stroke acknowledgment  Improved gathering + acknowledgment Direct control marking  more entire datasets Robust free-outline acknowledgment  bring down boundaries to learning

Slide 27

Extra Slides

Slide 28

Nodes for each stroke (part)

Slide 29

Edges between related sections

Slide 30

Example of a name set

Slide 31

CRF Probability Distribution The likelihood of an arrangement of names given information Want to amplify P(y|x) Normalizing term Local similarity with names Compatibility in light of setting Normalize by whole over all conceivable name sets. Awful term Need guess to make this computationally doable

Slide 32

Feature capacities CRF can\'t utilize crude stroke information Feature capacities separate helpful numerical information Vector of information extricated for every hub and match of contiguous hubs P( y | x ) What are these perceptions?

Slide 33

Parameters Relative handiness of elements for characterization should be represented Parameters go about as weights for individual components Weighted elements consolidated with an aggregate Represented with a dab item

Slide 34

Site Potentials Measure similarity amongst marks and a hub The exponential makes the math more pleasant All possibilities joined with an item highlight work weight vector Site Potential

Slide 35

Interaction Potentials Where the CRF gets its energy Uses setting by measuring similarity between sets of nearby hubs and sets of names Mathematically, same story as site possibilities include work weight vector Interaction Potential

Slide 36

What does a CRF require? Assemble information on the portray and individual strokes ( include capacities ) Determine weights ( preparing ) Maximize P( y | x ) in a computationally plausible manner ( deduction ) Not going to discuss this

Slide 37

Feature Functions Can\'t pass stroke information straightforwardly into the CRF Feature capacities make an interpretation of crude stroke information into basic direct values that the CRF can follow up on We required returned qualities to be in the scope of [-1, 1] in principle different extents work, however we had issues with them

Slide 38

Mathematical Limitations The CRF must react straightly to the qualities returned by highlight works This can be dangerous if the returned esteem has physical significance, similar to the length of a stroke To manage highlights like length we made a few distinct components for whether the length was inside a specific range

Slide 39

Site Feature: Turning Calculates the aggregate amount of pivot in a stroke After ascertaining the estimation of Turning, we returned four unique qualities for various areas To see why we have to do this, consider the red, blue, and green strokes underneath

Slide 40

Interaction Feature: T-Junction Detects whether two strokes are arranged in a T-Junction with each other Might happen where a wire meets a door Note that this capacity is non-symmetric We need to separate the cross from the stem of a T-Junction We utilize two indistinguishable adaptations of this capacity with the contentions switched

Slide 41

Parameters regardless we require a rundown of weights or parameters relating each site highlight to each name, and each cooperation highlight to each combine of marks Must take in parameters from named information

Slide 42

Likelihood work The probability capacity is a representation of how well a given arrangement of parameters orders a given information set We really utilize (- log(likelihood)) to make the math less difficult Training permits us to discover

Slide 43

Training: Idea How would we be able to minimize ? Take the subsidiary and set it to 0? Condition is excessively muddled Gradient plunge: Locally take after the inclination down to the most minimal point (ideally!) [evaluated on preparing data] [w,v] ideal parameters

Slide 44

Future Work More/better element capacities Computational issues Numerical under-and flood Multi-Pass CRFs Find Gates and Wires Train the CRF again on the doors, recognizing the sort of entryway Circuit understanding, interface with Xilinx

View more...