H. Chase Stevens Logo

Most Common Tags

  1. programming
  2. python
  3. code
  4. philosophy
  5. evolution
  6. game design
  7. probability
  8. video games
  9. genetic algorithms
  10. government

Archives

Loading

Posts with tag "voting":

Reconstructing Images Using Damaged Copies (in Python)

posted on: Thursday, September 13, 2012 (4:01 pm) by Chase Stevens

I've recently been working on implementing various methods of image reconstruction in python. The idea is to, given several imperfect (that is to say, noisy, incomplete, photoshopped, or otherwise damaged) copies of some original image, attempt to arrive at something close to (if not precisely) the original image by combining said copies. Through these means, an approximation of the original image can be generated should the original be lost, itself damaged, irretrievable, or otherwise unavailable or useless. In writing the various functions for doing this, I implemented techniques used in signal averaging and variants thereof. I also implemented a “modal image" function which, for each pixel, uses the “modal" RGB values across all image copies or, failing that, performs a simple mean of values.

Examples and Analysis

Original Christian Bale photograph

For the following examples, I modified the above image of actor Christian Bale. Ironically enough, in testing for this article, I overwrote the original image and had to employ the use of Google's reverse image-search in order to find it.

Damaged images
Damaged Christian Bale #1 Damaged Christian Bale #2 Damaged Christian Bale #3
Delta: 105.122025 Delta: 88.026425 Delta: 68.5942
Function results (listed with difference from original image as given by get_delta, lower is better):
<function average_images_add at 0x00000000030E8F28> : 155.35693875
<function average_images_sub at 0x00000000030E95F8> : 72.4844575
<function average_images at 0x0000000002EF0208> : 43.92254625
<function average_noisefilter_all_sub at 0x0000000002EF0278> : 51.1805645833
<function average_noisefilter_all_delta at 0x0000000002EF02E8> : 36.9071316667
<function modal_image at 0x0000000002EF0358> : 42.53322
Christian Bale Reconstructed Using modal_image Christian Bale Reconstructed Using average_noisefilter_all_delta
Function: modal_image
Delta: 42.53322
Function: average_noisefilter_all_delta
Delta: 36.9071316667
As is readily visible, in this example the naïve “voting”-type approach used by modal_image is deceived in any case where forms of damage across multiple images “agree” with each other. Given a larger number of copies or a less artificial form of damage, this would likely cease to be an issue; in theory, modal_image could even go so far as to reconstruct the original image perfectly. average_noisefilter_all_delta produced the best results on average, although, to its detriment, its output relies on the order of the list of image copies passed to it. In addition, while it manages to be closer to the original image, the subtraction of image differences it employs creates a slightly “jarring” visual effect (as seen above). The inherent issue in reconstructing damaged images is one of knowledge. To humans, it seems obvious that the original image of Christian Bale didn't have streaks of white across it. However, this is a mere assumption based on our vast pool of experience in viewing photographs. Who's to say that the original photo didn't have white scribbles on it? The computer is hampered, from our perspective, by its inability to make these assumptions when reconstructing the original image, so although it produces results better than a mere superposition of the copies, they rarely are better than what could be accomplished by human hands.

Noisy images
Noisy Christian Bale #1 Noisy Christian Bale #2 Noisy Christian Bale #3
Delta: 92.715475 Delta: 93.352175 Delta: 93.08885
Function results (listed with difference from original image as given by get_delta, lower is better):
<function average_images_add at 0x00000000030E8F28> : 103.01672125
<function average_images_sub at 0x00000000030E95F8> : 81.929801875
<function average_images at 0x0000000002EF0208> : 82.971985
<function average_noisefilter_all_sub at 0x0000000002EF0278> : 69.6356495833
<function average_noisefilter_all_delta at 0x0000000002EF02E8> : 75.23682
<function modal_image at 0x0000000002EF0358> : 65.2880416667
Christian Bale De-Noised Using modal_image Christian Bale De-Noised Using average_noisefilter_all_sub
Function: modal_image
Delta: 65.2880416667
Function: average_noisefilter_all_sub
Delta: 69.6356495833
In this case, modal_image produced the best results, although its output is still quite noisy. Again, having more copies would significantly improve the end product. The output also appears to be slightly brighter than would be expected. average_noisefilter_all_sub comes in at a close second, although (to the human eye) its results appear to be quite a bit noisier than modal_image.

I tried to use these image reconstruction methods on compressed images with jpeg artifacts as well, although the results were much poorer. Output deltas ended up being worse than the least compressed copy of a given set, although better than an average copy. modal_image and average_images_add seemed to perform best. The overall problem was again one of knowledge: could less compressed images be prioritized or weighted given their closeness to the source, results would likely be much better. However, the computer has no means by which to determine what is closest to the original, and thus fails to leverage this. Some kind of programmatic detection of jpeg artifacts could be of great help in improving this situation.

As a final note before my code, I just recently launched Broverbs. Please do check it out if you've got the time!

Download
from __future__ import division
from PIL import Image as PILImage
from Tkinter import *
from tkFileDialog import askopenfilename as openfile
from itertools import product
from random import shuffle

class Image():
    def __init__(self,filename=None,dimensions=None):
        if filename!=None:
            self.pic = PILImage.open(filename)
            self.imgData = self.pic.load()
            self.size = self.pic.size
        else:
            if dimensions!=None:
                self.size = dimensions
            else:
                self.size = [0,0]
            self.pic = None
            self.imgData = {}
            for x,y in product(range(self.size[0]),range(self.size[1])):
                self.setpixel(x,y,0,0,0)
    def setpixel(self,x,y,r,g,b):
        self.imgData[x,y] = tuple(map(max,zip((r,g,b),(0,0,0))))
    def getpixellist(self):
        return product(range(self.size[0]),range(self.size[1]))
    def show(self):
        tempImage = PILImage.new('RGB',self.size)
        for x,y in self.getpixellist():
            tempImage.putpixel((x,y),self.imgData[x,y])
        tempImage.show()

def get_delta(image1,image2):
    if image1.size != image2.size: raise ValueError("Image sizes do not match")
    delta = 0
    for x,y in image1.getpixellist():
        delta += sum(abs_pixel_diff(image1,image2,x,y))
    return delta / (image1.size[0] * image1.size[1])

mode = (lambda l: max([(l.count(i), i) for i in set(l)])[1] if len(set(l)) < len(l) else sum(l)/float(len(l)))

pixel_operation = lambda f: lambda image1,image2,x,y: map(f,zip(image1.imgData[x,y],image2.imgData[x,y]))
abs_pixel_diff = pixel_operation(lambda (x,y): abs(x-y))
pixel_diff = pixel_operation(lambda (x,y): x-y)
pixel_avg = pixel_operation(lambda (x,y): (x+y)/2)
pixel_sum = pixel_operation(lambda (x,y): x+y)

def image_operation(operation,image1,image2):
    if image1.size != image2.size: raise ValueError("Image sizes do not match")
    result = Image(dimensions=image1.size)
    for x,y in result.getpixellist():
        r,g,b = operation(image1,image2,x,y)
        result.setpixel(x,y,r,g,b)
    return result

get_delta_image = lambda image1,image2: image_operation(abs_pixel_diff,image1,image2)
subtract_image = lambda minuend,subtrahend: image_operation(pixel_diff,minuend,subtrahend)
average_image = lambda image1,image2: image_operation(pixel_avg,image1,image2)
add_image = lambda image1,image2: image_operation(pixel_sum,image1,image2)

def get_average_image(image_list):
    output = Image(dimensions=set1[0].size)
    for x,y in output.getpixellist():
        r,g,b = reduce(lambda a,b: (a[0]+b[0],a[1]+b[1],a[2]+b[2]),[image.imgData[x,y] for image in image_list])
        output.setpixel(x,y,r/len(image_list),g/len(image_list),b/len(image_list))
    return output

def generalized_average(image_list, combination_function, function1, function2):
    shuffle(image_list)
    set1 = image_list[0::2]
    image1 = get_average_image(set1)
    set2 = image_list[1::2]
    image2 = get_average_image(set2)
    return combination_function(function1(image1,image2),function2(image1,image2))

def average_images_add(image_list): 
    return generalized_average(image_list,add_image,average_image,subtract_image)

def average_images_sub(image_list):
    return generalized_average(image_list,subtract_image,average_image,subtract_image)

def average_images(image_list): 
    return generalized_average(image_list,subtract_image,average_image,get_delta_image)

def generalized_noisefilter(image_list,function):
    shuffle(image_list)
    set1 = image_list[0::2]
    image1 = get_average_image(set1)
    set2 = image_list[1::2]
    image2 = get_average_image(set2)
    noise = function(image1,image2)
    denoise_set = [subtract_image(image,noise) for image in image_list]
    return get_average_image(denoise_set)

def average_noisefilter_all_sub(image_list):
    return generalized_noisefilter(image_list,subtract_image)

def average_noisefilter_all_delta(image_list):
    return generalized_noisefilter(image_list,get_delta_image)

def modal_image(image_list):
    shuffle(image_list)
    result = Image(dimensions=image_list[0].size)
    for x,y in result.getpixellist():
        r = mode([image.imgData[x,y][0] for image in image_list])
        g = mode([image.imgData[x,y][1] for image in image_list])
        b = mode([image.imgData[x,y][2] for image in image_list])
        result.setpixel(x,y,r,g,b)
    return result

def test_func(f,images,original,trials=25):
    results = list()
    for x in range(trials):
        print "Trial #"+str(x+1)
        results.append(get_delta(f(images),original))
    return sum(results)/len(results)

function_list = [average_images_add,average_images_sub,average_images,average_noisefilter_all_sub,average_noisefilter_all_delta,modal_image]

def test_functions(image_list,original,functions=function_list,trials=10):
    out = ''
    for f in functions:
        out += (str(f) + ' ')
        out += (': ')
        out += (str(test_func(f,image_list,original,trials)))
        out += ('n')
    print out

Tags: code, image processing, information theory, programming, python, voting

Consensus Voting and Scanlon's Contractualism (A Case Study of The New School)

posted on: Tuesday, November 29, 2011 (10:24 pm) by Chase Stevens

In his 1982 work Contractualism and Utilitarianism, T.M. Scanlon, in an attempt to explain morality, formulated a new type of Contract Theory, building upon the work done by his predecessor Rawls. Scanlon's approach was novel: whereas contract theories posited before his time focused on what members of a society would mutually agree upon, Scanlon took the opposite approach by focusing on what people find unacceptable. This lead him to arrive at the following definition for a morally wrong act:

"An act is wrong if its performance under the circumstances would be disallowed by any system of rules for the general regulation of behavior which no one could reasonably reject as the basis for informed, unforced general agreement […] An act is wrong if it is forbidden by a principle which no one can reasonably reject."
To simplify, under Scanlon's contractualism, an act is wrong if and only if someone can provide a reasonable objection to it. Conversely, an act is acceptable if no such reasonable objection can be provided by anyone. One ought also to include objections that would arise if everyone was well-informed, or those that would arise if coercive forces were not in play.

Ignoring this contractualism as an explanation of morality, I would like in this piece to examine the implementation (plus minusve) of Scanlon's "wrongness" criterion in consensus voting, via a case study of my former high school, The New School ("TNSK"), as well as how it handled (or failed to handle) cases or situations that serve as objections to said criterion.

First, however, I should provide some background. TNSK is a school run on democratic principles. The vast majority of decisions about the school and its governance (including such things as what classes are offered, the annual budget and the hiring of teachers) are made by students, teachers, parents, alumni (and alumni parents), members of the school's "Leadership Team" (on which I served from Spring of 2008 to August 2011), members of the Board of Directors of The New School Corporation (on which I served from Spring of 2009 to August 2011), and general members of The New School Corporation (i.e. anyone who has donated more than a dollar to the school). The majority of decisions made in the school (save for those made by the Board of Directors of the Corporation) are voted on or at least ratified using a voting system called "Fist to Five," a modified form of consensus voting.

Fist to Five diagram

When voting, a person can raise between one and five fingers or a fist. The one to five fingers represent the voter's amenability to the proposal, with five being particularly gung-ho and one being reluctant in the utmost, likely with several pressing concerns or objections. However, all votes except for a fist are forms of "yea", with the fist being the only true consensus-breaker. Although usually a proposal will be modified or, in some cases, dismissed because of low votes, the throwing of a fist by any single member of the voting body is the only action that technically and absolutely bars the proposal from passing per se.

Now, let's examine some objections to Scanlon. The first is not so much an immediate objection, but, rather, a question: What counts as a reasonable objection? Scanlon clarifies this a bit via several qualifiers. First, Scanlon deems it unreasonable to object to an act solely because it imposes a burden on yourself, whereas other acts would pose a greater burden on others. For example, suppose that I was a part of some club of five people which was going to increase its membership costs by four dollars. It would not be reasonable for me to object to this because I would be charged four dollars and to then offer an alternative in which everyone but me gets charged five dollars. Scanlon also says that reasons must be personal, not impersonal. As an example, an unreasonable objection to the paving over of a park would be that it "destroys the beauty of the city", whereas a reasonable objection might be "I would no longer have somewhere in which to play frisbee."

How did TNSK handle this? When I first started attending the school, there was no "reasonableness" criterion or criteria that had been established, at least to my knowledge [Edit: I was informed by a former classmate of mine that this was not, in fact, the case, and that displaying a fist has always required at least a moral objection to a proposal. However, I have left this section intact, for the sake of completeness]. One could fist a proposal at will. Naturally, it would seem as though this is problematic, as anyone could hold up the entire governmental process for petty or even nonexistent reasons (although I can't recall an instance of this ever occurring). At some point, it was decreed (by the principal, not through democratic process) that, to put up a fist, one must have "moral objections" to a given proposal. This seemed problematic on several levels. Firstly, to require moral objections without specifying a system of morality is useless; one could easily say that their moral system was a kind of hedonistic solipsism that required they not do anything they didn't care to do. On the flip side, I was at the time and still am an error theorist, which presumably left me with no right to object to anything whatsoever. Moreover, it wouldn't appear that one has to have a moral objection to very, very strongly refuse to accept or endorse a policy, or indeed for a policy to be worth objecting to. For example, let's say that there was a proposal to remove the roof from the school: although I may not have any moral qualms about this, it still seems like I should be able to object to this course of action and stop the proposal from going through. The final requirement of which I am aware (and which was also added without any democratic process) was that any person who fisted a proposal would have to come back later with an alternative proposal. I think this is very clearly fallacious, being tantamount to saying "Well, do you have any better ideas?" Simply because I am unable to think of a better proposal does not mean that I de facto lose my right to object to a proposal. Again, an example: Suppose the school is facing a large deficit, and suppose also that I have no knowledge of fundraising or how to handle finances. I would still seem to be within my rights to object to a proposal that all the teachers be fired, despite not having any alternative proposal for alleviating the school's financial troubles.

The second objection to Scanlon I'd like to present is that of aggregation. Scanlon's contractualism is fantastic in that it helps us avoid scenarios in which we might consider allowing one or few to suffer greatly against their will to bring an even greater amount of happiness or benefit to others (for example: gladiatorial games). Consider the following, however: Suppose that there are two groups of drowning people. One group contains five people, the other group is comprised of a single man. There is a ship that can save either one group or the other, but not both, as a group will have to drown during the time it will take to save the opposite group. In this case, it seems that the lone man has very strong grounds on which to object to the captain of the boat saving the group of five, seeing as he would die. However, each of the group of five has the same claim. In this case would could say that the needs of the many (the group of five) outweighs the needs of the few (the man), but doing so would severely undermine the contractualist system that we've established. The same can easily be applied to TNSK: Suppose that there are five seniors, all of whom need a half-credit of math to graduate. Suppose also that the math teacher is already teaching seven classes, far more than is normally expected of a teacher. It would seem that all five students can reasonably object to a suitable math class not being offered for them (i.e. could fist a proposal that did not include a senior-level math class). However, the teacher also seems to have the reasonable objection that teaching an eighth class would present too much of a burden (and therefore could fist any proposal that did include the additional senior-level math class). I remember clearly an example of this occurring some time during the first few years I went to TNSK. The school had been presented with an American flag by the Daughters of the American Revolution (if I remember correctly). There was a proposal made for us to purchase or otherwise obtain a flagpole and fly the American flag on it. One or two students, citing aversions to U.S. foreign and domestic policy as well as nationalism and patriotism in general, threw up a fist for the proposal. As facilitator for one of the many meetings we had on the subject, I asked for a fist-to-five vote on the proposal of not displaying the flag we had been given, a proposal which a greater number of people fisted. Both this issue and that of what constitutes a reasonable objection pose a grave threat to the voting system employed by TNSK and, I would argue, to consensus-based voting systems in general.

As a final thought: If you're a current member of the TNSK community (or of any other democratic school that uses consensus voting) that found the above to be concerning (or even simply a matter worthy of discussion and contemplation), be you student, parent or teacher, I deeply encourage you to bring up your feelings at your next student meeting, committee meeting, all-school meeting, or meeting of the corporation. Frank conversation regarding the tenets and foundations of governance at the school can only lead to a better and more open system. Of course, if you found this post enlightening, please check back regularly, as I plan on making this the first in a series of pieces examining TNSK's governmental structure, philosophical underpinnings, et cetera.

Tags: contract theory, contractualism, education, error theory, government, morality, philosophy, rawls, scanlon, tnsk, voting

Democracy, Anonymity and the Prisoner's Dilemma

posted on: Friday, November 25, 2011 (1:56 pm) by Chase Stevens

Human beings are social animals. We live and interact in societies, adopt social norms, and incorporate our society into our identity. I would even say that our sense of justice, morality, and fairness stem from the fact that we are constantly interacting with each other within (in the ancestral environment) a mostly closed community. Doing so means that we are in a constant, mutiplayer iterated prisoner's dilemma, wherein we can earn reputations which will influence our interactions with others. For those not familiar with this concept, allow me to explain: the prisoner's dilemma can be explained as a two-player game. Each of the two players has but a single option: to either cooperate or to defect (in the original scenario, there were two prisoners who could either choose to "rat out" their criminal accomplice or to remain silent). Both players cooperating produces a moderately good outcome for both, whereas both defecting produces a mutually bad outcome for both. Should one player choose to cooperate while the other chooses to defect, the cooperating player gets the worst possible outcome and the defecting player gets the best. This can be represented in the below table:

Player 1 CooperatesPlayer 1 Defects
Player 2 CooperatesPlayer 1: 3
Player 2: 3
Player 1: 5
Player 2: 0
Player 2 DefectsPlayer 1: 0
Player 2: 5
Player 1: 1
Player 2: 1
If two players choose to play only one round of this game, the optimal strategy is to defect, as defection will net an average of 3 points, whereas cooperation will net only 1.5. Moreover, if this game is viewed under the lens of the maximin principle (which states that you should opt for the decision that will have the best worst-case scenario), the worst case for cooperating gets you 0 points, whereas defecting ensures you are rewarded with at least one point.

However, if two players choose to play this game for a number of rounds, the general best strategy is to behave in an altruistic but reciprocal manner (although for larger groups and more complex but similar games, other more refined strategies come into play). This is to say, initially assume in good faith that your partner is going to cooperate and do so yourself, but if they defect, defect yourself in turn. When this is applied to a larger group, this translates into looking into the reputation of the person you have been partnered with, seeing what their record is in terms of defection and cooperation, and responding accordingly.

As has been a fairly recent focus of attention, this poses a problem on the internet. Online, being anonymous (or at least having the ability to operate under a discardable pseudonym) is the rule, not the exception, the result of which being that you either are incapable of gaining a reputation or can shed one easily if necessary. This breaks the connection between iterations that allows for cooperative strategies in the prisoner's dilemma, essentially turning the game into a series of one-off rounds, as neither party can ever truly know whom they're interacting with. This is only compounded by the fact that human empathy grossly decreases when we're not face-to-face with one another; inability to observe the facial expressions, verbal tone, and body language of a person you're interacting with impairs your ability to create a model of that person and thereby your ability to empathize with them. This leads to people on the internet often making incredibly callous, distasteful and offensive statements, the likes of which they would never normally make "in real life," the obvious example of this being the infamous 4chan. If given the opportunity, such as in the massively mutiplayer EVE Online, people will lie, cheat, steal, betray, backstab, defraud and destroy each other with nary a second thought. However, when these people are encountered offline they are typically soft-spoken, courteous and otherwise normal.

Of course, the internet isn't the only environment in which this can happen. Driving also grants us an unusually high level of anonymity while cars themselves abstract our fellow humans into mere "drivers". This results in a casual level of rudeness that seems to avoid descending into complete sociopathic chaos only by the virtue of everyone having some degree of self-preservation.

Where else are these environmental conditions manifested? The voting booth. Although obviously a tad more complex than a prisoner's dilemma, it stands that voters quite often are put in a position where they could vote in a manner directly in accordance with their own self-interest, and not that of the community/country/what have you. Given what things people do in other circumstances when granted anonymity, it does not seem overly bold to assume that at least a certain percentage of people vote selfishly. The natural question that therefore arises (and which I'd like to address) is that of the benefits of voting records becoming public.

Before delving into that, however, we should investigate whether or not votes being made public would really change anything. It could perhaps be the case that people would continue to vote the same way regardless. However, the Bradley effect would seem to claim otherwise. To be concise, the Bradley effect refers to a phenomenon wherein non-white candidates score higher in polls than they do once votes have actually been tallied, the presumption being that people being polled claim that they'll vote for the non-white candidate when asked by a pollster to avoid a potential accusation of racism. Historically the effect seems to have been responsible for polling discrepancies of up to 12 points. A reverse-Bradley effect has also been observed, such as in the case with former Louisiana State Representative David Duke, a Nazi sympathizer and former KKK Grand Wizard, who won his position despite few people being willing to admit to pollsters that they supported him. So indeed, it seems that, at least in some cases, people will change their votes (or at least admitted voting intentions) if the way they voted will be made public. Although perhaps the difference wouldn't be as great as observed in the above cases (more being at stake when actually voting, as opposed to telling someone how you'll vote), it would be reasonable to expect to see some change.

What is the advantage of having peoples votes be influenced by societal pressure? Well, for one, it would seem as though we might be able to avoid having KKK members as state representatives, which most people would agree is a definite boon. We could also expect to see more effects such as this, where people wouldn't vote in ways that others might find objectionable. One example might be gay marriage: those who privately oppose it could be far less willing to have their objections exposed publicly (this, of course, assumes that the legalization of gay marriage would be a "good thing"). Public voting outcomes could be as different from the anonymous voting outcomes we have now as behavior in public is from anonymous online behavior.

Of course, there are numerous objections to this course of action. What if society's standards are unconscionable? One might easily imagine an area of the country in which the pressure would be to vote for the KKK member, as opposed to against him. Could those who would otherwise oppose racism then be peer pressured into voting against their morals? Moreover, in a less extreme case, could the Bradley effect cause people to vote for non-white candidates not because of political ideology, but instead to not appear racist? Such a system would also enable a great deal of coercion to come into play, enabling unscrupulous groups or individuals to influence votes through bribery or threat. Buying votes would be a simple matter if only one could verify how someone voted. Lastly, does one not have a right to vote selfishly? It could easily be argued that the voting booth is one of the few places in which one can express their opinions and influence the world around them in an honest way, free from repercussions or persecution.

While the suggestion of having one's votes be made public might not be a likelihood, it's probably not as fanciful as we might be inclined to imagine. Although currently no one has access to how you voted, in the United States any interested party can find out whether or not you voted. In fact, in 2009 a group in Virginia called "The Know Campaign" sent out a letter to voters informing them not only of their past voting history, but also that of their neighbors, all in an effort to use societal pressure in order to get people to vote more (the implication being that the neighbors have also received your voting record). The campaign was directly stated by executive director Debra Girvin as being not a "shame tactic", but instead a "peer pressure tactic." Although the efficacy of the campaign hasn't (to my knowledge) been disclosed, it did generate at least 1,000 letters of complaint.

Tags: anonymity, democracy, ethics, evolution, game theory, gaming, government, internet, morality, philosophy, probability, society, united states, voting