Ein Freihand Modellierungstool für Surfaceubicomp/projekte/master2011... · Einf uhrung Related Work Abgrenzung Literatur Inhaltsverzeichnis 1 Einf uhrung 2 Related Work PreRecognition

EinfuhrungRelated WorkAbgrenzung

Literatur

Ein Freihand Modellierungstool fur SurfaceTM

Dennis Kilan

22. Juni 2011

1 / 29


Literatur

Inhaltsverzeichnis

1 Einfuhrung

2 Related WorkPreRecognitionObject Recognition

3 Abgrenzung

2 / 29


Literatur

Motivation

• Modellierung von Systemen wichtiger Schritt

• Variante 1: Zeichnen auf Papier• + Intuitiv, Einfach,Kollaborativ und Schnell• - keine Moglichkeit zu Speichern oder Andern

• Variante 2: Zeichnen mit CASE-Tools• + Anderbar, Speicherbar,Verteilbar• - Oft Komplex, Kontraintuitiv, wenig Support fur

kollaboratives Arbeiten

3 / 29


Literatur

Motivation





3 / 29


Literatur

Motivation





3 / 29


Literatur

Vision

• Zeichnen von Modellen uber Touch Input auf dem MicrosoftSurfaceTM

• Erkennen der gezeichneten Elemente und Umwandlung inModellelemente

• Export der gezeichneten Elemente in CASE Tools

4 / 29


Literatur

PreRecognitionObject Recognition

Related Work

5 / 29


Literatur


Sketch Recognition Architektur

1 Der Stroke wird uber die Positiondes Eingabegerategerates inbestimmten Zeitintervallenaufgezeichnet

2 Der Prerecognizer erkennt ausdiesen Punkten Ecken und primitiveFormen wie z.B. Linien oder Kreise

3 Die Object Recognition setzt ausden primitiven Formen komplexeFormen zusammen, wie z.B. einRechteck

6 / 29


Literatur


Sketch Based Interfaces[3]Vorstellung

• 2001 von Sezgin, Stahovich (MIT) und Davis(CMU)entwickelt

• Ziel: Formerkennung unabhangig davon, wie sie gezeichnetwurde

• Approximation Versucht Linien und Kurven zu erkennen

• Beautification Glattet die Formen

• Basic Recognition Interpretiert die Zeichnung

7 / 29


Literatur


Sketch Based InterfacesApproximation(1)

• Im ersten Schritt: Erkennen von Ecken

• Eine Ecke weist eine hohe Krummungauf

• Problem: Noise verursacht viele FalsePositives

8 / 29


Literatur


Sketch Based InterfacesApproximation(2)

• Losung: Average Based Filteringmit variablem Treshold(Mean)

• Absicherung mitGeschwindigkeitsdaten (lokaleMinima)

• Das Finden von Ecken erfolgt uberHybrid Fit beider Daten

• Bester Fit: Wenigste Ecken

9 / 29


Literatur


Sketch Based InterfacesErkennen von Linien und Kurven

• Linienerkennung Abweichung der Datenpunkte von eineridealisierten Linie zwischen 2 Ecken

• Falls quadratische Abweichung unter Treshold: Linie

• Kurven Verhaltnis von Bogenlange zu euklidischer Distanznahe 1 bei Linien, bei Kurven wesentlich hoher

• Approximation der Kurve uber Bezier Kurve mit 2Kontrollpunkten

• Bewertung der Kurve uber Diskretisierung und stuckweiserZerlegung in lineare Stucke

10 / 29


Literatur


A Domain-Independent System for Sketch Recognition(2003)[5]Vorstellung

• 2003 von Bu Yi und Shije Cai an der Nanjing University inChina entwickelt

• Nutzt ebenfalls Krummungsdaten zum Finden von Ecken

• Es ist hier auch egal wie die Form gezeichnet wird

• Erkennen von Ecken und das Umwandeln in primitive Objektein einem Schritt

• 2 Phasen: Imprecise Stroke Recognition(Erkennen vonprimitiven Shapes) und Post Process (Saubern der Zeichnungund Object Recognition)

11 / 29


Literatur


A Domain-Independent System for Sketch RecognitionImprecise Stroke Recognition

• Nutzt die Richtungs- undKrummungsdaten eines Stroke,sowie die Feature Area zu einemReferenzobjekt

• Hohe Krummung, StarkerRichtungswechsel und die FeatureArea bedeutet auch hier moglicheEcke

• Verzichtet aufGeschwindigkeitsdaten, da diese zunoisy sind und nicht zu denvisuellen Features gehoren

12 / 29


Literatur


A Domain-Independent System for Sketch RecognitionErkennen von Linien

• Direction Graph kann durchhorizontale Linie genahert werden

• Echte Datenpunkte konnen durchLinie genahert werden

• Falls Feature Area und Flache derechten Linie ca. gleich groß sind,ist eine Linie gefunden

13 / 29


Literatur


A Domain-Independent System for Sketch RecognitionErkennen von Kurven

• Kreiserkennung: Krummungsgraph zu noisy

• Aber Richtungsgraph zeigt eine Kurve mit einer Steigung von(−)2π/n

• Angepasster Kreis: Mittelpunkt des Kreises ist Mittelpunkt derBounding Box und der Radius ist mittlerer Radius

• Bogenerkennung: Ahnlich wie Kreis nur mit wenigerSteigung

• Ambiguitat zwischen Bogen mit wenig Krummung und Linien

14 / 29


Literatur


ShortStraw: A Simple and Effective Corner Finder forPolylines [4]Einfuhrung

• 2008 von Wolin an der Texas A&M University entwickelt

• Einfaches Finden von Ecken

• Ermittlung von Krummungsdaten eines Stroke ungenau undkompliziert

• Idee: Aufteilen des Strokes in gleichmaßig verteilte Punkte

15 / 29


Literatur


ShortStraw: A Simple and Effective Corner Finder forPolylines [4]Einfuhrung

• Ecken erkennt man durch dieLange von Straws

• Kurzerer Straw bedeutet Ecke

• High Level False Positive- undNegative Filterungen

• Jedoch keine Erkennung vonKurven =>viele False Positives

16 / 29


Literatur


Object Recognition

17 / 29


Literatur


LADDER [2]Einfuhrung

• 2007 von Tracy Hammond und Randall Davis am MITentwickelt

• Domanenunabhangige Sprache zur Beschreibung von Shapes

• Beschreibt nicht nur das Aussehen eines Shapes sondern auchdas Verhalten

• Aus der Beschreibung werden Shape Recognizer, EditingRecognizer und Shape Exhibitors erzeugt

18 / 29


Literatur


LADDERBeschreibung

19 / 29


Literatur


LADDER

• Shapes konnen auch hierarchisch definiert werden

• Shapes konnen gruppiert werden

• Domanenspezifische Shapes werden uber JESS Regelsystemerkannt

• Problem: Schlecht fur kurvenreiche und irregulare Shapes

• Problem2: Viele kleine Shapes und unerkannte Primitivebremsen LADDER aus

20 / 29


Literatur


SketchML [1]Vorstellung

• 2009 von Avolo,DelBuono,Gianforme,Paolozzi (inRom) und Wang (SaarlandUniversitat) entwickelt

• Framework zum Erstellen undErkennen von Shapes bestimmterDomanen

• Nutzt SVG/XML Dateien zumBeschreiben von Shapes

• 2 Teile: Library EditorEnviroment(LEE) und SketchRecognition Enviroment(SRE)

21 / 29


Literatur


SketchMLLibrary Editor Enviroment

• 4 Phasen: First Layer Segmentation: Zerlegt Stroke inClosed Regions und Polylinien

• Second Layer Segmentation: Nutzt First LayerSegmentation um Stroke in Ellipsen und Linien einzuteilen

• Constraints Determination: Pruft Constraints der einzelnenElemente

• SketchML Descriptor: Ubersetzt die gefunden Elemente indas SVG Format

22 / 29


Literatur


SketchMLSketch Recognition Enviroment

• Matcht gezeichnete Elemente mit den Elementen dergeladenen Library(Domane)

• Idee: Sowohl das gerade gezeichnete Element und dieElemente liegen im SVG Format vor

• Jedes SVG Element ist eine Node die mittels Constraints inBeziehungen zu den anderen Nodes stehen

• Problem: Matching aller Elemente sehr aufwandig

• Nachteil: Das Matching erfolgt nicht dynamisch beimZeichnen

23 / 29


Literatur


Abgrenzung

24 / 29


Literatur

Abgrenzung(1)

• Vertex Detection uber hohe Krummung lieferte keine gutenErgebnisse

• Eigene funktionierende Idee: Vertex Detection uberVeranderung der Richtung

• Funktioniert nur uber Resampling wie bei Wolin[4]

• False Positive Filterung uber Steigung zwischen 2 Punkten

25 / 29


Literatur

Abgrenzung(2)

• Erkennung von Primitives ahnlich wie bei Yu[5]

• Object Recognition ahnlich wie LADDER[2]

• Unterschied: Moglichst die vorhandenen Manipulationsgestenvon Surface nutzen

• Objekterkennung ohne Semantik, Interpretation erfolgt inhoherer Ebene

26 / 29


Literatur

Ende

Vielen Dank furs Zuhoren und viel Erfolg bei den Klausuren

27 / 29


Literatur

[1] Danilo Avola, Andrea Del Buono, Gianfor Giorgio, StefanoPaolozzi, and Rui Wang. Sketchml a representation languagefor novel sketch recognition approach. In Proceedings of the2nd International Conference on PErvasive TechnologiesRelated to Assistive Environments, PETRA ’09, pages31:1–31:8, New York, NY, USA, 2009. ACM.

[2] Tracy Hammond and Randall Davis. Ladder, a sketchinglanguage for user interface developers. In ACM SIGGRAPH2007 courses, SIGGRAPH ’07, New York, NY, USA, 2007.ACM.

[3] Tevfik Metin Sezgin, Thomas Stahovich, and Randall Davis.Sketch based interfaces: early processing for sketchunderstanding. In ACM SIGGRAPH 2006 Courses, SIGGRAPH’06, New York, NY, USA, 2006. ACM.

28 / 29


Literatur

[4] Aaron Wolin, B.Eoff, and Tracy Hammon. Shortstraw: Asimple and effective corner finder for polylines. InEUROGRAPHICS Workshop on Sketch-Based Interfaces andModeling (2008), 2008.

[5] Bo Yu and Shijie Cai. A domain-independent system for sketchrecognition. In Proceedings of the 1st international conferenceon Computer graphics and interactive techniques in Australasiaand South East Asia, GRAPHITE ’03, pages 141–146, NewYork, NY, USA, 2003. ACM.

29 / 29

Documents

Ein Freihand Modellierungstool für Surfaceubicomp/projekte/master2011... · Einf uhrung Related Work Abgrenzung Literatur Inhaltsverzeichnis 1 Einf uhrung 2 Related Work PreRecognition