Haar Classifier Training Program

If you haven't used Processing to power through some small application that you need, I highly recommend it. (I just now remembered I still haven't posted about my poster in the conference, and given that it's officially published, I can officially talk about at least the extent to what we've done so far. Next post will be on that.) In any case, as part of the research, we're now switching to an OpenCV implementation, which means training a Haar Classifier. Now this is a task that is...a pain. It involves ideally thousands of images, and if you want the best accuracy, you should hand-annotate where your object is in the images.

To avoid going crazy and needing to destroy everything in the lab, I wrote a short app in processing to create the Haar file. I'll probably post a link to the code after I've completed the training on our images and verified that it doesn't start eating memory like no-one's business for large samples, since I had tried so very hard to avoid writing this app myself. Still, using Processing, it took all of 30 minutes to produce something that will be useful. I could've spent more time with the interface, and if I decide to release it, I very well may modify the code to have a nicer I/F and support multiple occurrences in the same image, but for now, this little app is sufficient for my purposes.

For the record, there's something utterly satisfying about completing a program in under an hour. :)

UbiComp 2010: Paper of MY Conference

So while this paper was not nominated for best paper, and should not have been, it did quite a bit for me personally in terms of considering structure for my own future thesis.

Andrea Grimes, Vasudhara Kantroo and Rebecca E. Grinter (2010). Let's Play! Mobile Health Games for Adults. Proc. of UBICOMP 2010. (Link is to Ms.Grimes website, and you can find the full paper on the publications page.)

Let me sum up the gist of the idea, rather than going into the details of the paper, as there are some fundamental problems with the study. The gist is that a casual game might be better suited for games that aim to improve behavior. The behavior here was based on healthy eating, and the research targeted African American individuals because of the high incidence of diabetes among that population. The game was designed with food items that such folks would find in their neighborhoods, including soul food type items, sandwiches, etc.

The critical part for me was the introduction of the casual game premise. I had been structuring my thesis idea around epistemic games, thinking only in terms of long story arc type things, and listening to this proposal has given me an alternate idea. I'm definitely going to need to start with an exploratory study to examine which of those two paths is going to be the better choice for me, I think. Additionally, discussing the shape of the study and what might have been a better question for the study format has helped me think about how to structure my own studies to avoid those types of critiques.

I'm likely going to blog about a few more of the papers that were interesting or that I discussed in a critical fashion with Leilah as well.

Academics: Very Smart, Very Dumb

I have one major complaint about UbiComp 2010 as far as comfort goes. The seatting arrangement during the presentations is a typical lecture hall, but one with absolutely no space to move if someone is sitting in a chair. For some reason, every single person will opt to sit on the very end of the row. This means that every person who is not in the lecture hall before the presentation begins has to squeeze past those folks who sat down first. This is particularly difficult as some folks refuse to stand up to let people pass.

This is particularly humiliating in my case. I'm not a small woman by most standards, and it. is. not. comfortable. for me to move myself and my laptop pass you. You're forcing me to choose to show you either my rear or my front in a small area. It is awkward for me. I can't imagine you're enjoying it that much, given your reluctance to even stand up. When I say "Excuse me," it isn't a request for you to turn your knees to the side, which adds maybe three inches to the first three that were there. I'm simply not six inches wide.

So please, colleagues. If you're organizing a conference, do choose a venue that it is accessible for various body types. If you're at a conference that doesn't have wide aisles, either sit near the center of the row, or be prepared to stand up when people need to get by.

A further update about UbiComp as far as interesting papers went will be posted either later today or tomorrow.

Software Review: Mendeley

Finding a resource management software ended up being really easy. I searched cross-plastform because I work on a Mac in the lab, a PC at home, and up until today, my laptop was running ubuntu. (Since ASUS is no longer providing drivers for linux, and I really wanted to be able to skype with Braden while in Denmark, I'm installing Windows on it, at least temporarily.) Mendeley is absolutely fantastic. It scans pdfs to try and autofill citation information, while allowing you to sync files or information across computers. I'm so into this software right now. I have't encountered any bugs that I want gone or features that I'm desperately missing.

Mendeley exports to EndNote if you happen to have access to commercial software, as well as exporting to BibTex. I'm digging it so far. I'd chat it up a bit more, but I need to put together my personal-item purse/bag/whatevs for the flight to Denmark. :)

Catching Up/Getting Ahead

It's been a while because I haven't yet gotten through my thick skull that blogging more frequently might actually assist me in keeping my thoughts straight about the various projects I'm working on. This semester started all of two weeks ago, and things haven't really started to kick in full gear yet as far as academics are concerned, though I've been out of town for the last two weekends and have two more social engagements on the next two weekends, and then get to take a plane to my first ever real-computer-science-conference.

What? I never posted here about that? Right, well the poster paper on Paper-to-Parameters was accepted to UbiComp. On September 25th, I take my first international flight using my first passport(which cost me way too much money), to go to the first conference where my first paper ever will be published. I've spent a lot of time in the last week working on the poster, and working considerably harder since realizing that this may very well be a conference I'll want to be taken seriously at when I'm working the angles on my thesis.

Question to be asked at the department sometime soon: can we publish partial parts of our PhD research in a similar way to how the work we're doing right now is being published as a WiP in a couple of conference before the final paper is published? I really don't know these things at UIC yet, and I have a feeling it could be critical.

I'm planning on applying to the NSFGRF program this year. Getting accepted means some $30,000 a year stipend, along with an allotted tuition waiver, as well as travel assistance. It would also mean free time to actually do my research without having to work for someone else. The other nice thing about the NSFGRF is that it basically sets me up to get background work done for my thesis and to put some really intense thought into what I want to do and how I would do it. It's basically a mini-grant proposal. I'm actually really excited to start working on it, if only I could start budgeting my time better.

A couple of things I'm going to try and do: find a reference management software that I like, and then leave the references in my dropbox folder so I can access them from all three computers. Write up short reviews here again for papers that I've read, because well, I should be doing that anyway as I finish the papers to avoid re-reading too deeply the ones that are uninteresting/disconnected from what I'm doing. Discuss with Leilah what is appropriate to be spoken of with the internet before publication so that I can figure out just how much to reveal here about what I'm currently working on. Some open source software reviews for various toolkits I've been having to use.

For now, that's catch up time. I'm working on putting together a study group for the Foundations exam amongst my fellow graduate students, so that may be updated here as well.

CRA-W Grad Cohort

This weekend, I took a break from the last-week-of-school panic to attend a conference in Seattle for women in computer science. It's actually not so much a conference as let's all get together, eat free food, and talk about how to get through graduate school. And for the most part, I learned quite a bit and enjoyed myself quite thoroughly and actually made some new friends.

There were certain parts that concerned me. The two sessions that one wouldn't have seen at a similar event for any gendered cs grad student were...pretty gender biased. In a bad way. The suggested reactions to possible situations made me uncomfortable. They were all very passive reactions, which only leads to the persistence of the attitude that it's okay to say that someone only got their position because of their gender, or to interrupt a female speaker just because they're female. I do not believe in simply sitting back if I'm having a conversation with someone and someone else butts in and tries to end my conversation preemptively. I am far more likely to inject myself into the "new" conversation, politely. Restraint is something I should learn.

But there were constant references to "having a cry" when a rejection letter was received. There were the 'jokes' about shopping. If we're talking about activities that are relaxing, why are they all so stereotypically gendered activities? It...perturbed me. For all of the information I received, the attitudes I encountered at CRA-W were not really...about being equal. They were about establishing our femininity within being a computer scientist and somehow trying to be normal.

I have no desire to be normal. Not a normal woman, whatever that means, not a normal computer scientist, not a normal anything. Will I return to CRA-W next year if they fund me? Yes, I likely will. The opportunity to network with women in computing research is much too large to ignore. Will I perhaps be skipping the sessions on "Building Self Confidence" and "Being a Woman in Computing Technology" ...no, because I think it's critical that someone stands up and says that we should not let even "unintentional" sexism stand.

On a somewhat related note, if ever you have to be stranded in an airport for two hours, SeaTac is a great one for it. Comfortable seats, true free wi-fi, and outlets galore.

Qualifier Results & Summer Plans

Qualifiers Scores:

Foundations: No Go. Retry in September. We received the exams back, and I really need to study algorithms in depth, as well as some dynamic programming techniques. Whoops.

Human Centered Computing : Conditional Pass. I have to take Artificial Intelligence this Fall, which is cool. My AI course was not a practical course, instead being largely a theoretical approach. UIC emphasizes practice so much that I'm actually mildly excited. I did rock the HCI portion of the HCC exam, and that delighted me.

Systems: Pass. I find it peculiar that the only test I passed absolutely on the first try is the only one I didn't explicitly study for, but I'll take what I can get. Primarily my success here was due to taking Networking the prior semester.

While I attempted to apply for internships, I was largely unsuccessful. For some reason, places that are looking for research interns actually desire research experience. Fancy that. Luckily for me, I've been talking at length with Dr.Leilah Lyons about a project that only recently was given a small budget so that my summer will be partially funded, which is a delightful development that makes my summer much less stressful. The project?

The project involves two subjects that I'm aware of and one that I've studied with just a bit of depth. Essentially, it's an augmented reality project that will take AR input for a system, and then run a simulation for that system, based on the input. I actually question the extent to which this is Augmented Reality to some extent, since it's being used as input only, and not active input. Once the images are captured, they are not then acknowledged again unless another capture is requested.

The semester is coming to a close and Kenchi Games is taking up quite a bit of my time. Reach has been an interesting project with many, many problems that we're working on, a day at a time. Hopefully, we'll be making another video capture this week to post on youTube. The original intent had been to do that far more often than we have, but the amount of progress between weeks has been less than desired.

Additionally, for User Interface Design, we're now working on small projects in Android. This slow build up will hopefully lead to a good understanding of the API so that I can build small applications over the summer and increase my portfolio of work. (Speaking of portfolio, another high priority item on the list is definitely completing a portfolio website by the end of summer, since the school year seems to not include much real time.)

Qualifier Exams

Last Thursday and Friday were the qualifier exams. After reading some ten texts on computer science in the short time of a month, I still feel that I was under prepared for the exams and should've started studying about the same time I was accepted into UIC if I had wanted to actually excel, instead of merely feeling that it was possible I passed certain portions of the exams.

From here, things start to get interesting. When the results from quals come back, quite a bit changes. But for now? For now I am content to know that I have two possible research projects lined up, one possibly starting this summer. Now that I am not aggressively reading textbooks, it's time to turn back to the original plan for this blog, which implies doing quite a bit more reading of various journals and actually writing summaries on the interesting articles. I'll be posting a few of the summaries I've done for CS 594 here in the next few days, as well as the cleaned up version of our report for User Interface Design.

Additionally, if anyone is interested in what we are currently doing for Video Game Design, you can track our progress at Kenchi Games. That website should continue to be updated over the semester.

Human Centered Computing Exam: HCI

HCI Question 1 – 100 points:

The interface for a typical elevator is still based on physical buttons that allow the user to select a specific floor, hold the door open, close the door, or ring the alarm bell. With the price of flat panel displays dropping, it is possible that in the coming years we will see touch screen LCD panels replacing the existing designs.

A – What are the advantages of completely replacing a typical elevator button panel like the one

shown below with a touch-screen LCD panel?

Completely replacing the panel would allow for more information to be presented. There would be fewer individual mechanical pieces that could go faulty. Particularly in the case of some mechanical error, the LCD screen could provide information about what had happened to the caller to be relayed to the technician.

B – What are the disadvantages of that complete replacement?

With all changes there is a learning curve, and the newness may cause some confusion. Going beyond that, an LCD screen is unlikely to provide the same immediate feedback when a 'button' is pushed.

C – Suggest a hybrid design combining the current interface and an LCD touch screen that

maximizes the advantages and minimizes the disadvantages. Note which principles you

are using and how they affect your design.

HCI Question 2 – 33 points:

On some computer systems, using a mouse to move the cursor to the corner of the screen causes the system to sleep or go into alternative display modes. Is this a Fitts’ task? Explain your answer.

Yes, this task is a Fitts task. Since Fitts' Law deals with the placement and utilization of space for the distribution of objects for a task, placing the most frequently used objects near the center of the task, the act of placing a common task that shouldn't interfere with normal use at the edges of the screen falls under that umbrella of tasks.

HCI Question 3 – 34 points:

Touch-screen interactions often face the problem that the user’s finger occludes the object being

manipulated (e.g., selected, moved).

A - Describe two techniques that might potentially mitigate this problem, and discuss the

advantages and disadvantages of each technique.

One technique would be to have an offset of the touch, displaying the selection as slightly above(to avoid occlusion by the rest of the finger) of the contact. The advantage of this technique

B - Describe a procedure (including subjects, tasks, and analysis methods) for characterizing the

performance of the two proposed methods.

More later. Need to go back to foundations and really hard core study so...backing away from this for now. I feel this is easier and more comfortable than hard comp sci, and that's not cool.

Qualifier Practice Exam : Foundations

Part III: Theory of Computation (40 pts)
Question 1 (3 Points): Consider the following language over the alphabet of the 10
decimal digits (i.e., {0, 1, , 2, 3, 4, 5, 6, 7, 8, 9}):
L = {n : n = closing price of oil rounded to nearest U.S. dollar on Dec. 29, 2017}
What is the smallest class of languages of which L is a member?

(a) Languages decidable in linear deterministic time.
(b) NP
(c) NP-complete languages (?)
(d) P
(e) The undecidable languages

Question 2 (3 Points): The FUBAR problem is a new decision problem that you have
just begun to study. So far you have been able to show the following two things about the
FUBAR problem:
• There is a polynomial-time reduction from the Satisfiability problem (“Is a given
Boolean formula satisfiable?”) to the FUBAR problem.
• You have a nondeterministic method that solves the FUBAR problem and that never
consumes more than a polynomial amount of space.
What do you know for sure about the FUBAR problem given current knowledge?
(a) It is NP complete
(b) It is in the complexity class NP
(c) It is in the complexity class P
(d) It is not in the complexity class P
(e) It is NP hard.

Question 3 (4 Points): The minimum number of states of a Deterministic Finite State
Automaton (DFSA) over the alphabet {0, 1} recognizing the language containing the single
string of n 0s (n is fixed) is:
(a) 2n (b) n + 2 (c) n^2 (d) 10. (no)
Not sure if this is saying 0*1*(0^n)1*0* or just 0^n

Question 4 (4 Points): Let L be the language over {0, 1} consisting of all strings that
have a 1 in the third symbol from the end (e.g., the string 0100 is in L). The minimum
number of states of a DFSA recognizing L is:
(a) 50 (b) 5 (c) 8 (d) 100.

Qualifer Practice Exam: Foundations

Question 5 (9 Points): Below are three recursive java methods. In each case, the

“problem size” n is given by r − l + 1 – the number of elements in the subarray being

processed. For each method do the following:

(1) Derive and explain a recurrence relation for the runtime T(n) of the recursive method.

(2) Give and explain a tight Big- bound on the T(N).

Ugh. Coming back to this problem some other time. (Ugly code.)

Question 6 (5 Points): Suppose the following values are inserted into a “generic” (i.e.,

not self-balancing) binary search tree:

10, 2, 8, 11, 14, 3, 42

(They will not necessarily be inserted in the given order).

Devise an insertion order which will result in the tree having minimum height.

10, 3, 14, 2, 8, 11, 42 (Creates a balanced tree, w/ h=2)

Question 7 (6 Points): Draw a minimum sized AVL tree of height 4 (an AVL tree

with 1 node has height 0). (In other words, among all AVL trees of height 4, draw one with

a minimum number of nodes). How many nodes does your tree have?

Recall that a Binary Search Tree T is an AVL tree if and only if the following holds: for

all nodes v in T, the height of v’s subtrees differ by at most 1. Sometimes this is called

“height-balanced-1”.

x

/ \

x x

/ \ / \

x x x x

/ \ / \ / \ / \

x x x x x x x x

/

x

It has 16 nodes. (Not sure if this needed to have values, but it would not be difficult to come up with values.

Question 8 (7 Points): Below is (part of) a simple java class for a Binary Tree node.

The method isBST is supposed to determine if the given tree is a valid Binary Search Tree.

(E.g., the developer might use it as a sanity checker).

Is the algorithm correct?

If your answer is YES give a concise argument of correctness.

If your answer is NO give and explain a counterexample.

public class BTNode {

private int key;

private BTNode left;

private BTNode right;

// Returns true iff binary tree rooted at

// t is a valid Binary Search Tree with

// respect to the stored keys.

public static boolean isBST(BTNode t) {

if(t == null) return true;

if(t.left != null && t.key <>

else if(t.right != null && t.key > t.right.key) return false;

else return isBST(t.left) && isBST(t.right);

}

}

This is a correct method for determining if a BST is correct. If each sub-tree is correct, than the entire BST is correct. This could be proven via induction. It may not be as pretty as an AVL tree, but it will be correct.

Qualifier Practice Exam: Foundations

Question 7 (5 Points): A complete ternary tree is defined as a tree in which every non-leaf

node has exactly 3 children and every leaf is the same distance from the root. The height of

a complete ternary tree is defined as the distance (number of links) from the root to a leaf.

A ternary tree with just one node has height 0.

Prove the following by mathematical induction: “a complete ternary tree of height h has

a total of (3^(h+1)−1)/2 nodes.”

i. Base Case: Let h=0. (3 ^ (0+1) - 1)/2 = 1. Just one node, h=0.

ii. Let h be an arbitrary value such that h > 1. Assume P(h) holds.

iii. Profit?

I know this section should somehow involve (3 ^ ((h+1)+1)-1)/2, but there really isn't a "left side" to this equation to work with.

Using our induction hypothesis, P(h) = (3^(h+1)-1)/2

Spending too long on this problem, moving on. This is not boding well. ._.

Part II: Data Structures and Algorithms (52 pts)

Question 1 (8 Points): Which of the following problems is known to be solvable in

running time O (n3)? (Give a list of the problem numbers.)

1. Finding the longest simple path from a given start vertex to a given end vertex in a

directed acyclic graph on n vertices with nonnegative integer weights.

2. Finding the shortest path from a given start vertex to a given end vertex in a directed

graph on n vertices with arbitrary integer weights.

3. Finding the longest simple path from a given start vertex to a given end vertex in a

directed graph on n vertices with nonnegative integer weights.

This is referring to Floyd-Warshall algorithm. Definitely 1, 3. It mentions an ability to identify (2), but since the cycles produce arbitrary weights when negative, I'm going to stick with 1, 3.

Question 2 (5 Points): True or False: Circle your final answers.

T [F] If an algorithm runs in O(n) time on the worst case input then it runs in O(n) time on every input.

[T] F Running BFS on a directed unweighted graph with cycles will produce shortest paths from the source vertex to all other reachable vertices (where path length is simply the number of edges).

T [F] log(n!) = o(n2)

[T] F Running DFS on an undirected graph may produce cross edges.

[T] F The lowest weight edge in a graph with all unique edge-weights is always included in any minimum spanning tree

Question 3 (6 Points): Code for the Floyd-Warshall all-pairs shortest paths algorithm (the dynamic programming based O(V 3) algorithm) appears below. Write a loop invariant for the end of the outer loop (on variable k) – i.e., at the point in the code indicated, what can be claimed about adj[i][j] with respect to k. Hint: this loop invariant essentially why the algorithm works!

// adj[][] is initially the weight matrix.

// If there is no edge (i,j) then adj[i][j] = Infinity

// where Infinity is a sufficiently large number (e.g.,

// n*MAX_EDGE_WEIGHT).

for (k = 1 to n){

for (i = 1 to n){

for (j = 1 to n){

adj[i][j] = min(adj[i][j], adj[i][k] + adj[k][j]);

}

}

// adj[i][j] is the minimum path as far nodes 1...k are concerned.

}

Question 4 (6 Points):

Part (A) Give example functions f(n) and g(n) where f(n) = o(g(n)).

f(n) = n

g(n) = n^2

o(g(n)) = n

(Because lim(n->inf) (n/(n^2))=0)

Part (B) Is the following statement TRUE or FALSE (if it is true, give a clear argument;

if it is false, give a counter-example):

“If f(n) = o(g(n)) then log(f(n)) = o(log(g(n))).”

False.

Let's use the previous f(n)-(g(n) pair here. log(f(n))= log(n), while log(g(n))= log(n^2) = 2log(n)

lim(n->inf) logn/2logn = .5 =/= 0.

Qualifier Practice Exam: Foundations

Question 3 (4 Points): Suppose you have an alphabet with k characters. How many
strings of length n from this alphabet are palindromes?

Return later.

Question 4 (5 Points): should get a math-writing piece of software. Ugh. Will return later.

Question 5 (3 Points): Write a truth table for the following logical expression.
A V B' -> (A V B)'

A B B' AVB' AVB (AVB)' A V B' -> (A V B)'
T T F T T F F
T F T T T F F
F T F F T F T
F F T T F T T

Question 6 (2 Points): Draw a Venn Diagram (shaded circle diagram) for the following
set.
{x|((x in A) or (x in B)) and x not in A ^ B}

I don't have a drawing utility right now, but that would be two circles that overlap with the circles shaded but not the section of overlap not shaded.

Depth Cues for Augmented Reality Stakeout

Paper by Volkert Jurgens, Andy Cockburn, Mark Billinghurst

I read this paper because it isolates stereo cues and tests them against other augmented reality assistance for placing a stake in the correct position. The study finds no significant difference between the several types of augmentation used. The conclusion is that the task is more reliant on kinesthetic memory than it is on visual cues. There was some discussion of the subjective preferences, but it seems the critical lesson to learn from this experiment is to assess whether a task is as visual cue driven as it seems before committing time and energy to an experiment.

Qualifer Practice Exam: Foundations

Question 1 (3 Points): Conte di Savoia on Taylor Street (between Racine and Ashland) sells 6 different kinds of pastries. How many different pastry trays can they make that have 20 pastries, with at least 3 of those 20 being cannoli? Note that the order of the pastries on the tray does not make a tray different, but having different numbers of pastries does. (I.e., “10 apple strudels and 10 cannoli” is the same tray as “10 cannoli and 10 apple strudels”, but “11 apple strudels and 9 cannoli” is different. You may use exponents and factorial symbols in your answer; you do not need to simplify to a single integer.

Order doesn't matter, so this is a combinations problem. Now 3 of the twenty positions are already handled since 3 have to be cannoli. The formula for combinations with repetition is (n+k-1)!/k!(n-1)! Since ALL of the combinations will have 3 cannoli, we are only choosing 17 items of the 6 types. n=17, k=6. (22)!/6!16! (The problem says simplifying is unnecessary, but let's finish for the sake of cleanliness.

(22)!/6!16! = (17*18*19*20*21*22)/2*3*4*5*6 = 17*3*19*7*11 = 74613 different plates.

Question 2 (5 Points): Suppose there are 10 students in a class and that each will receive one of the following grades: A, B, C, D, F. For each of the following you need not give a final numerical answer; an equivalent expression is sufficient.

Part I: How many distinct ways are there for the instructor to assign the grades?

Now order matters, because student 1 is not student 2. So there are 5 grades being chosen (n), ten times (r). Therefore, there are 5^10 distinct ways to assign the grades.

Part II: Now suppose the Dean has stated that at least two of the students must receive F’s. With this added constraint on the instructor, how many distinct grade assignments are there?

So the tricky thing I'm not sure about here is that the core part is definitely 5^8, in that the eight students without F's can have any grade. Come back.

Introduction

My name is Tia Shelley and I am a graduate student in computer science, pursuing human-centered design and specifically the human computer interaction tree. You have likely found this blog through a link I delivered, and thus, that's the depth of introduction to me that I feel I should present.

Over the years, I've written many different types of blogs. On-going stories, the livejournal that documents most of my high school career and all of my college years. This blog is not for that. This is for documenting the path to becoming a PhD. That means, in general, this blog is going to be utterly filled with summaries, abstracts, and various links to projects I'm working on. I'm keeping this to keep track of my sources because it's easier to search a web page than it is to search a binder full of papers. I'm using this to make sure I process every paper I read at least to the depth that I can post a summary and brief review of each article. My frustrations and successes with courses and the graduate school life style will, for the most part, be something for my personal journal and not for this particular blog, unless it has some greater impact than just my mood.

Last semester, I took Virtual Reality and Networking. Networking will probably come up again while I'm studying for my qualifier exams over the next month, but VR has a very high potential of becoming a common topic despite the fact that the class is over. This semester, I'm taking User Interface Design, Research Methods in Computer Science and Video Game Design. Any projects for these classes will probably be roughly outlined here under tags for each class. General research will be tagged with authors, subject, and either review or summary.