Sachverhalt: Sachverhalt: A. Am 29. August 2003 wurde X._ von der Kantonspolizei Appenzell Ausserrhoden beim Verhöramt verzeigt, weil er beim Führen seines Personenwagens nicht in fahrfähigem Zustand gewesen sei und die vorgeschriebene Sehhilfe nicht getragen habe. Mit Strafverfügung vom 10. Oktober 2003 wurde X._ mit Fr. 80.-- gebüsst. Dagegen erhob der Beschuldigte, vertreten durch seinen Anwalt, Einsprache. Am 29. Oktober 2003 legte er den Sachverhalt aus seiner Sicht dar und verlangte die Aufhebung der Strafverfügung unter Kosten- und Entschädigungsfolge. Das Verhöramt stellte das Verfahren hierauf mit Verfügung vom 17. Februar 2004 ein, weil von einem leichten Fall auszugehen sei, bei welchem auf eine Strafverfolgung verzichtet werden könne. Von der Ausrichtung einer Entschädigung wurde unter Hinweis auf Art. 246 der Strafprozessordnung vom 30. April 1978 (StPO/AR; bGS 321.1) abgesehen, während die Verfahrenskosten dem Staat auferlegt wurden. Dagegen erhob der Beschuldigte, vertreten durch seinen Anwalt, Einsprache. Am 29. Oktober 2003 legte er den Sachverhalt aus seiner Sicht dar und verlangte die Aufhebung der Strafverfügung unter Kosten- und Entschädigungsfolge. Das Verhöramt stellte das Verfahren hierauf mit Verfügung vom 17. Februar 2004 ein, weil von einem leichten Fall auszugehen sei, bei welchem auf eine Strafverfolgung verzichtet werden könne. Von der Ausrichtung einer Entschädigung wurde unter Hinweis auf Art. 246 der Strafprozessordnung vom 30. April 1978 (StPO/AR; bGS 321.1) abgesehen, während die Verfahrenskosten dem Staat auferlegt wurden. B. Gegen die Einstellungsverfügung gelangte X._ an die Staatsanwaltschaft des Kantons Appenzell Ausserrhoden, welche den Rekurs mit Verfügung vom 12. Mai 2004 abwies. Mit Eingabe vom 10. Juni 2004 erhebt X._ staatsrechtliche Beschwerde. Er rügt eine Verletzung der Unschuldsvermutung und des Willkürverbotes und beantragt deshalb die Aufhebung der Verfügung vom 12. Mai 2004. Die Staatsanwaltschaft des Kantons Appenzell Ausserrhoden schliesst auf Abweisung der Beschwerde, soweit überhaupt darauf einzutreten sei.