Thursday, July 21, 2011

Vess Cola, Part 5.

I had to tinker a while but I think I found a nice way to draw the pieces with ImageMagick's '-draw' operators.

Using the 'floodfill' didn't turn out too well. The line's anti-aliasing caused weird artifacts. (See previous post.) Instead of a square plus two lines, I switched to four triangles.Zooming in looks nicer.

Ha!  Fun.











#!/bin/sh

# draw Vess Cola puzzle bottles
# davep 10-Jul-2011

SIZE=300
HALF=$(( ${SIZE}/2 ))
FOURTH=$(( ${SIZE}/4 ))
EIGHTH=$(( ${SIZE}/8 ))
THREEFOURTH=$(( ${FOURTH}/3 ))

function north {
    if [ $1 == "bottom" ] ; then
        echo "rectangle $(($HALF-$EIGHTH)),0 $(($HALF+$EIGHTH)),$FOURTH"
    else
        echo "polygon $(($HALF-$EIGHTH)),0 $(($HALF+$EIGHTH)),0 $HALF,$FOURTH"
    fi
}

function east {
    if [ $1 == "bottom" ] ; then
        echo "rectangle $(($SIZE-$FOURTH)),$(($HALF-$EIGHTH))  $SIZE,$(($HALF+$EIGHTH))"
    else
        echo "polygon $SIZE,$(($HALF-$EIGHTH)) $SIZE,$(($HALF+$EIGHTH)) $(($SIZE-$FOURTH)),$HALF"
    fi
}

function south {
    if [ $1 == "bottom" ] ; then
        echo "rectangle $(($HALF-$EIGHTH)),$(($SIZE-$FOURTH)) $(($HALF+$EIGHTH)),$SIZE"
    else
        echo "polygon $HALF,$(($SIZE-$FOURTH)) $(($HALF+$EIGHTH)),$SIZE $(($HALF-$EIGHTH)),$SIZE"
    fi
}

function west {
    if [ $1 == "bottom" ] ; then
        echo "rectangle 0,$(($HALF-$EIGHTH)) $FOURTH,$(($HALF+$EIGHTH))"
    else
        echo "polygon 0,$(($HALF-$EIGHTH)) $FOURTH,$HALF 0,$(($HALF+$EIGHTH))"
    fi
}

function piece {
    num=$1
    shift
    convert -size $((${SIZE}+1))x$((${SIZE}+1)) xc:gray -fill white -stroke black \
        -draw "rectangle 0,0 $SIZE,$SIZE" \
        -fill $1 -draw "polygon 0,0 $SIZE,$0 $HALF,$HALF"\
        -fill $3 -draw "polygon $SIZE,0 $SIZE,$SIZE $HALF,$HALF" \
        -fill $5 -draw "polygon 0,$SIZE $SIZE,$SIZE $HALF,$HALF"\
        -fill $7 -draw "polygon 0,0 0,$SIZE $HALF,$HALF"\
        -fill black -draw "$(north $2)"\
        -fill black -draw "$(east $4)"\
        -fill black -draw "$(south $6)"\
        -fill black -draw "$(west $8)"\
        puzzlepiece${num}.png
}

piece 0 red bottom green top blue top yellow bottom
piece 1 red bottom blue bottom green top yellow top
piece 2 red top yellow top blue bottom green bottom
piece 3 green bottom blue bottom green top yellow top
piece 4 yellow bottom red top blue top red bottom
piece 5 green top yellow top red bottom blue bottom
piece 6 red top yellow top green bottom blue bottom
piece 7 blue top green bottom yellow bottom red top
piece 8 red top blue bottom yellow bottom green top

Sunday, July 10, 2011

Vess Cola, Part 4.

I started writing a post on how I was arrive at the 4**9 calculation. I wanted a way to illustrate the 4x pattern of the puzzle pieces.

My original drawings were done with OmniGraffle. OmniGraffle is an amazing piece of software. Its ease-of-use gives me something to strive for in my own software.

However, OmniGraffle is quite good at diagramming, drawing squares, shapes, connecting them, etc, but I wanted a nicely colored red/green/yellow/blue square. Flood fill isn't something in OmniGraffle's design.

So how to draw a puzzle piece? I don't want to use my Tkinter GUI app yet (saving that for a future post) but I needed a way to get a simple puzzle piece into a post. And taking a screen shot felt like cheating. Too easy. Yes, I like to find the hard way to do things. I learn a lot that way.

Several years ago, I wrote a little Python+ImageMagick script to do the familiar "Forbidden!" red crossed-out circle. ImageMagick has some very nice drawing primitives. (I'll post the cross.py at some point. I'd like to stay remotely close to the Vess Cola topic for a while.)

First shot was something like:

% convert -size 100x100 xc:gray -fill white -stroke black -draw "rectangle 10,10 90,90" -draw "line 10,10 90,90" -draw "line 90,10 10,90" puzzlepiece.png

Well. It's square with a cross through it. Missing color. Needs some fill. Needs some flood fill. Easy with a paint program. But what's the fun in that? ImageMagick can do flood fill.


% convert -size 100x100 xc:gray -fill white -stroke black \
    -draw "rectangle 10,10 90,90" \
    -draw "line 10,10 90,90" \
    -draw "line 90,10 10,90" \
    -fill blue -draw 'color 20,50 floodfill' \
    -fill red -draw 'color 50,20 floodfill' \
    -fill green -draw 'color 75,50 floodfill' \
    -fill yellow -draw 'color 50,75 floodfill' puzzlepiece2.png




Flood fill is a bit tricky. There can be strange effects around the edges. I'm getting weird white borders. The diagonals are because of anti-aliasing (ImageMagick's web page warns about this). Not sure what's causing the white along the red, green, and blue triangles. Not the yellow, though.

Zooming in on the image via an ImageMagick scaling operation:

% convert -resize 500% -filter Point puzzlepiece2.png p3.png

I'm using the 'point' filter to avoid interpolating the result. I didn't want a soft scaled up image. I wanted to see pixel-by-pixel.

(I could have scaled up with OSX's Preview which does a good job of not interpolating pixels. I would have had to take a dreaded screen shot. Nothing against screen shots but I'm having fun looking for a good way to create these images programatically.)

My Tkinter app I used filled triangles. I wonder how that would look in ImageMagick? Could I do it even as an SVG to avoid the jaggies?

Friday, July 8, 2011

Vess Cola, Part 3.

Graphs can be made with pointers or an array configuration.

Speed is of the essence in this application. Why? The sheer number of permutations.

Flexibility isn't important. I don't need the full range of capabilities of a directed graph. Each vertex needs a right and a down edge.

But how many permutations are there? Curious.

There are nine items that can be arranged.

Permutations http://en.wikipedia.org/wiki/Permutation. 9! == 362880

But each card has four positions. Crud. (How did I calculate this again?)  4**9 comes to mind.

Wednesday, July 6, 2011

Vess Cola, Part 2.

The problem is how to represent the 3x3 grid of Vess Cola cards in such a way that I can compare the color and bottle top/bottom. Red Top must match Red Bottom, and so forth.

At first glance, a good data structure to represent the cards' grid would be a directed graph.


A directed graph would be simpler than an undirected graph. The compare only needs to work one way.


For example, Card 0 only has to compare itself to Cards 1 and 3. The relationship is symmetrical. If Card 0 matches Card 1 then certainly Card 1 matches Card 0. With a directed graph, I can connect the cards together to quickly traverse the pattern.

So how to represent in Python?

There are numerous graph libraries. There are numerous graph libraries in Python.

Tuesday, July 5, 2011

Vess Cola, Part 1.

When I was growing up, I had a wonderful window+grandmotherly next door neighbor--Gerri (Jeri? Geraldine?) LeVeaux. She was the kind of next door neighbor who always had cookies for us kids and paid us $1 to mow her tiny lawn even though she was perfectly able to mow it herself.

Some time, when I was a kid, she gave me a puzzle she said belonged to her son. I became the proud caretaker of the Vess Puzzle.


Hmmm... I need to scan the back of the pieces, too.

I've long since lost the envelope the puzzle came in. But the puzzle is simple enough. Match up the same color top and bottom of the Vess Cola bottles.

During college, I'd get the puzzle out of my desk, solve it to avoid doing homework.

A little while ago, I started talking with my father-in-law about puzzles. I hadn't played with Vess for quite a while so I brought out the puzzle. And couldn't solve it.

Being a programmer nerd, I thought Vess would be a fun programming problem. So I set about solving the puzzle with a Python script.

Installing 32-bit Support to 64-bit Ubuntu

If you are running Ubuntu 64-bit, install the ia32-libs

# sudo apt-get install ia32-libs

(Or use Synaptic.)

References:
http://ubuntuforums.org/showthread.php?t=720732
http://www.debian-administration.org/articles/534

Friday, May 20, 2011

Linux USB Printer/Scanner Hacks.

I develop scanner/printer firmware. I develop under Linux.

Here are a few handy things I use to make my life easier.

Disable the Ubuntu “New Printer” dialog.
From Jeremy Ward, a coworker.

“One issue I was having was the printer driver install prompts displayed when plugging the dev board in/loading code on the dev board. I remember you mentioning that you had the same problem on Ubuntu. I was able to fix this issue by modifying the rules in /lib/udev/rules.d/70-printers.rules. I commented out all of the rules since that is what tells the system to launch the prompts. I don’t think there are any negative consequences from doing so.”

Allow user read/write to /dev/usb/lp*.
Add yourself to the ‘lp’ group with usermod. See usermod(8) man page.

Fedora : run system-config-users script (tested on FC14)
Ubuntu 11.04 : (from Desktop) System -> Administration -> Users and Groups

Allow user to scan without using root.
Either of the following methods should work. The following examples assume a USB VID of 0×8086 and USB PID of 0×1234.

From Eric Huang, a coworker.

- Add a new file called /etc/udev/rules.d/mrvl-printer.rules
- Add a line to the new file:
ATTRS{idVendor}==”8086” MODE:=”0666”

From David Poole.

- Edit /etc/udev/rules.d/40-libsane.d
- Add the following before the first ATTRS{idVendor}:
ATTRS{idVendor}==”8086″, ATTRS{idProduct}==”1234″, ENV{libsane_matched}=”yes”

I've also found being logged in to the console (the PC itself) allows me to scan on Fedora. There is some magic going on in udev where, if the user is on the console, access to the USB devices is allowed.

Tuesday, March 15, 2011

Installing 32-bit Support to 64-bit Fedora 14

I'm moving to a new Linux build box. My original Linux box is a 32-bit Fedora FC14. My new Linux box is a 64-bit Fedora FC14.

Our compiler toolchain is a 32-bit app. The compiler didn't run on the new box, giving a cryptic error about /ld/ld-linux.so.2

Dug around Google. There are two postfixes (?) on FC14 packages: .i686 and .x86_64 (FC13 used .i586).

Short story: as root,
rpm -i bzip2-libs.i686

The dependency pulled in the 32-bit glibc. Probably could have installed just glibc.i686

The two glibc versions are installable side-by-side.

Tuesday, March 1, 2011

Products I've Worked on.

HP LaserJet m1005. First scanner/copier.
HP LaserJet m1120. First network scan.
HP LaserJet m1319. First ADF, stepper motor.
HP LaserJet m1130. Low memory. Digital sensor.
HP LaserJet m1212nf. First combo ADF,flatbed. Digital sensor.

Sunday, January 30, 2011

Document Recognition and Retrieval. Electronic Imaging Conference. 27-Jan-2011

"Example centric document design and development"

Wilcoxon-Mann-Whitney statistic
http://en.wikipedia.org/wiki/Mann%E2%80%93Whitney_U

Spearman Correlation Coefficient
http://en.wikipedia.org/wiki/Spearman%27s_rank_correlation_coefficient

Blueprint - Adobe Labs

Perceptron
http://en.wikipedia.org/wiki/Perceptron



"Feature relevance analysis for writer identification"

Freeman chain codes
http://en.wikipedia.org/wiki/Chain_code

Grapheme
http://en.wikipedia.org/wiki/Grapheme

Chi-squared
http://en.wikipedia.org/wiki/Chi-square_test



"Using perturbed handwriting to support writer identification in the presence of data constraints"

MGH - Model Generated Handwriting

MPG - Model Perturbed Handwriting

"Text-Independent Writer Identification and Verification on Offline Arabic Handwriting"
Bulacu, Schomaker, Brink 2007

SVM (Support Vector Machine) with radius basis kernel

McNemar's Test
http://en.wikipedia.org/wiki/McNemar%27s_test



"Statistical characterization of handwriting characteristics using automated tools"

Probabalistic Graphical Model
http://en.wikipedia.org/wiki/Graphical_model

Document Recognition and Retrieval. Electronic Imaging Conference. 26-Jan-2011

Capture: Image to Archive (conference)

Scene Analysis "Functional Role Labeling"

Image Template -> template management

Trainable pattern classifiers. Features + Classifiers.
Features
--------
Haar
runlength
Fourier
word counts

Classifiers
-----------
Decision tree
nearest neighbor
SVM (Support Vector Machine)
generative probability
density

"Learning Image Anchor Templates for Document Classification and Data Extraction"
Sarkar. http://www.icpr2010.org/pdfs/icpr2010_ThAT7.5.pdf

Constellation Model
http://en.wikipedia.org/wiki/Constellation_model

Information extraction by finding repeated structure
Evgeniy Bart, Prateek Sarkar
http://dx.doi.org/10.1145/1815330.1815353

Best First Leaf Search (from aforementioned paper)

NIST tax form data sets
http://www.nist.gov/srd/nistsd2.cfm



"Introduction of Statistical Information in a Syntactic Analyzer for Document Image Recognition"

Sayre's Paradox
http://dx.doi.org/10.1016/0031-3203(73)90044-7

Hidden Markov Model
http://en.wikipedia.org/wiki/Hidden_Markov_model



"MRF Model w/ Parameter Optimization by CRF for online recognition of handwritten Japanese characters"

MRF - Markov Random Field
http://en.wikipedia.org/wiki/Markov_random_field

CRF - Conditional Random Field
http://en.wikipedia.org/wiki/Conditional_random_field

Extract feature points using Ramner method
U. Ramer “An Iterative Procedure for the Polygonal Approximation of Plan Closed Curves” Computer Graphics and Image Processing, vol.1, pp244-256, 1972.
http://dx.doi.org/10.1016/S0146-664X(72)80017-0

Stochastic Gradient Descent
http://en.wikipedia.org/wiki/Stochastic_gradient_descent

Viterbi algorithm
http://en.wikipedia.org/wiki/Viterbi_algorithm

Baum-Welch algorithm
http://en.wikipedia.org/wiki/Baum%E2%80%93Welch_algorithm

Elastic matching
http://en.wikipedia.org/wiki/Elastic_Matching



"Improving an HMM based offline handwriting recognition system using MME-PSO optimization"

MME -

PSO - Particle Swarm Optimization
http://en.wikipedia.org/wiki/Particle_swarm_optimization

MD-LSTM
http://en.wikipedia.org/wiki/Long_short_term_memory

HTK - toolkit for building HMMs (Cambridge)
http://htk.eng.cam.ac.uk/



"Segmenting text from outdoor images taken by mobile phones using color features"

Preprocessing:
RGB -> HSI
histogram equalization Intensity channel
HSI -> RGB

Image binarization

Noise removal

Image Segmentation.
http://people.cs.uchicago.edu/~pff/

"Font and Background Color Independent Text Binarization"
Kasar edge cue based algorithm
http://www.imlab.jp/cbdar2007/proceedings/papers/O1-1.pdf

Levenshtein Distance
http://en.wikipedia.org/wiki/Levenshtein_distance

Bag of Words
http://en.wikipedia.org/wiki/Bag_of_words_model_in_computer_vision

Local Adaptive Binarization



"Perceptive Method for Handwritten Text Segmentation"

Kalman Filtering
http://en.wikipedia.org/wiki/Kalman_filter

Delaunay graph for distance computation
http://en.wikipedia.org/wiki/Delaunay_triangulation

DMOSp



"A masked based enhancement method for historical documents"

Filtering (noise reduction)
- Wiener
http://en.wikipedia.org/wiki/Wiener_filter
- Median
http://en.wikipedia.org/wiki/Median_filter

Markov Random Fields
http://en.wikipedia.org/wiki/Markov_random_field

Local Binarization [Gatos 2006]
"Adaptive degraded document image binarization"
http://dx.doi.org/10.1016/j.patcog.2005.09.010

OCR - Tesseract
http://en.wikipedia.org/wiki/Tesseract_%28software%29

Electronic Imaging Conference. 26-Jan-2011

Keynote: "Problems in Biological Imaging: Opportunities for Signal Processing"

PSF - Point Spread Function
http://en.wikipedia.org/wiki/Point_spread_function

Restoration: Denoise, Deconvolution.

http://en.wikipedia.org/wiki/Deconvolution

Hysteresis
http://en.wikipedia.org/wiki/Hysteresis

Segmentation
- thresholding
http://en.wikipedia.org/wiki/Thresholding_%28image_processing%29

- watershed
http://en.wikipedia.org/wiki/Watershed_%28image_processing%29

Electronic Imaging Conference. 25-Jan-2011

Keynote. "New Dimensions in Image Quality"

Full Reference (have pristine original)

"Blind" - no reference

MSE - Mean Squared Error

Spearman Correlation
http://en.wikipedia.org/wiki/Spearman_correlation

Hysterisis
http://en.wikipedia.org/wiki/Hysteresis

LIVE VQA
http://live.ece.utexas.edu/research/quality/live_video.html

- Natural Images obey statistical laws
- Our brain adapted to these statistics over eons

Natural Scene Statistics
- gaussian scale mixture (GSM)
http://en.wikipedia.org/wiki/Location_testing_for_Gaussian_scale_mixture_distributions
- generalized gaussian distribution (GGD)
http://en.wikipedia.org/wiki/Generalized_normal_distribution

Augmented Reality.

ISO 3664. Viewing Conditions.
http://www.iso.org/iso/catalogue_detail?csnumber=43234

ISO 13655. Metrology.
http://www.iso.org/iso/catalogue_detail.htm?csnumber=22476

USB2000 UV-VIS Spectronomer
http://www.oceanoptics.com/Products/usb2000+.asp

www.create.uwe.ac.uk
Color Research European Advanced Technology Employment (CREATE)

"Human Vision Based Color Edge Detection"
Delta-E-CAM-VCS > Delta-E-00 > Delta-E-CMC

"Object Classification by Color Normalization or Calibration?"
Gray World. Buchsbaum 1980. (Color constancy algorithm)

Finlayson 1998. http://www.springerlink.com/content/nhcjvku49b4jnn5r/

Retinex
http://en.wikipedia.org/wiki/Color_constancy

Colorimetric Calibration, [lee88]
maybe http://onlinelibrary.wiley.com/doi/10.1002/col.5080130311/abstract

KOPID data set uni-koblenz.de/kopid

Histogram comparison:
- sum of squares difference (SSD)
- histogram intersection
- simplified chi-squared

Earth-Mover's Distance
http://en.wikipedia.org/wiki/Earth_mover%27s_distance

"Evaluating the Smoothness of Color Transforms"

Thor Olson: Smooth Ramps: Walking the Straight and Narrow Path through Color Space. Color Imaging Conference 1999: 57-64

journalofvision.org

Electronic Imaging Conference Notes, 24-Jan-2011

24-Jan-2011

Eigenspace
http://en.wikipedia.org/wiki/Eigenvalues_and_eigenvectors

Gabor filter bank
a linear filter used for edge detection
http://en.wikipedia.org/wiki/Gabor_filter

mean-shift clustering technique
a non-parametric feature-space analysis technique[1]. Application domains include clustering in computer vision and image processing[2].
http://en.wikipedia.org/wiki/Mean-shift

Anisotropic Diffusion
“a technique aiming at reducing image noise without removing significant parts of the image content, typically edges, lines or other details”
http://en.wikipedia.org/wiki/Anisotropic_diffusion

Bilateral filters
“A bilateral filter is an edge-preserving and noise reducing smoothing filter”
http://en.wikipedia.org/wiki/Bilateral_filter

Moving Least Squares.
“Moving least squares is a method of reconstructing continuous functions from a set of unorganized point samples”
http://en.wikipedia.org/wiki/Moving_least_squares

Non-local means.
[Buades et al. ‘05]

LARK - Locally Adaptive Regression Kernel
Denoise algorithms: LARK, BM3D, KVSD

Markov Chains
http://en.wikipedia.org/wiki/Markov_chain

Wiener Filter
“reduce the amount of noise present in a signal by comparison with an estimation of the desired noiseless signal.”
http://en.wikipedia.org/wiki/Wiener_filter

Twicing (Tukey, 1977)

MMSE - Minimum Mean Squared Error
http://en.wikipedia.org/wiki/Minimum_mean_square_error



Conference 7867. "Image Quality and System Performance"

Quality Attribute Tree

Registration - translation, rotation, scaling

"Survey of full-reference image quality metrics"
by: M. Pedersen, J. Y. Hardeberg

SC 871. Noise, Image Processing, and their Influence on Resolution.

SC 871. Noise, Image Processing, and their Influence on Resolution.

23-Jan-2011.

Electronic Imaging Conference. 23-27 Jan, 2011

Spectrogram.
http://en.wikipedia.org/wiki/Spectrogram

Measuring noise: ISO 15739
http://www.iso.org/iso/catalogue_detail.htm?csnumber=28835

Viewing Conditions. ISO 3664.
http://www.iso.org/iso/catalogue_detail.htm?csnumber=43234

European Machine Vision Association.
http://emva.org/cms/index.php

MTF - Modulation Transfer Function
http://en.wikipedia.org/wiki/Optical_transfer_function

SFR - Spatial Frequency Response

kurtosis
http://en.wikipedia.org/wiki/Kurtosis

Image Sensors and Signal Processing for Digital Still Cameras.
http://amzn.com/0849335450

SC1015. Understanding and Interpreting Images.

SC1015. Understanding and Interpreting Images.
23-Jan-2011

Electronic Imaging Conference. 23-27 Jan, 2011.

Edward Adelson
http://web.mit.edu/persci/people/adelson/

“Pictures are not taken in a vacuum--an overview of exploiting context for semantic scene content understanding” Signal Processing Magazine, IEEE
March 2006, Vol23 Issue 2.

Main subject detection. Belief map.

Duda, Hurt, and Storic. Statistical Pattern Recognition
http://amzn.com/0471056693

Earth Mover Distance
http://en.wikipedia.org/wiki/Earth_mover%27s_distance

Mahalonobis Distance
http://en.wikipedia.org/wiki/Mahalanobis_distance

PCA - Principle Component Analysis
http://en.wikipedia.org/wiki/Principal_component_analysis

SURF : Speed-up Robust Features (came after SIFT)
http://en.wikipedia.org/wiki/SURF

“A computational approach to determination of main subject regions in photographic images”
http://dx.doi.org/10.1016/j.imavis.2003.09.012

Integral Image
http://en.wikipedia.org/wiki/Summed_area_table

Haar Filters
http://en.wikipedia.org/wiki/Haar-like_features

Gradient Field.
http://en.wikipedia.org/wiki/Gradient

libsvm Support Vector Machine library
http://www.csie.ntu.edu.tw/~cjlin/libsvm/

AdaBoost
http://en.wikipedia.org/wiki/AdaBoost

Weka is a collection of machine learning algorithms for data mining tasks. The algorithms can either be applied directly to a dataset or called from your own Java code. Weka contains tools for data pre-processing, classification, regression, clustering, association rules, and visualization. It is also well-suited for developing new machine learning schemes.
http://www.cs.waikato.ac.nz/ml/weka/

AndreaMosaic - photo mosaic software (Windows)