Sachverhalt:
A.
In der Gemeinde Walzenhausen, im Gebiet Wilen, befindet sich eine Bestockung, für die bislang noch kein Waldfeststellungsverfahren durchgeführt worden war. Sie steht an einem Hang auf den in der Landwirtschaftszone befindlichen Parzellen Nrn. 526, 527 und 1461, angrenzend an die Parzelle Nr. 1738 (früher: Nr. 529).
Anlässlich der Ortsplanrevision der Gemeinde Walzenhausen führte das Oberforstamt (heute: Amt für Raum und Wald, Abteilung Wald und Natur) des Kantons Appenzell Ausserrhoden am 12. Januar 2012 eine Verpflockung des von ihm als Wald bezeichneten Areals durch. In der Folge legte es den Plan "Festlegung der Waldgrenzen" vom 17. Januar 2012 öffentlich auf, der eine Waldfläche von 536 m2 ausscheidet.
Dagegen erhob unter anderem A._, Eigentümer der Parzelle Nr. 526, Einsprache. Im Auftrag des Oberforstamts erstellte die Scherrer Ingenieurbüro AG am 23. März 2012 einen technischen Bericht zur Auswertung der Flächen- und Altersentwicklung gestützt auf Luftbilder (nachfolgend: Bericht Scherrer). Nach einer Anhörung vor Ort am 2. Mai 2012 wies das Oberforstamt die Einsprache am 8. Juni 2012 ab.
B.
Dagegen erhob A._ Rekurs ans Departement Volks- und Landwirtschaft (heute: Bau und Volkswirtschaft; im Folgenden: Departement). Dieses wies den Rekurs am 8. Juli 2013 ab, soweit es darauf eintrat.
A._ gelangte dagegen mit Beschwerde an das Obergericht des Kantons Appenzell Ausserrhoden. Dieses führte am 29. Oktober 2014 einen Augenschein durch und wies die Beschwerde gleichentags ab, soweit es darauf eintrat. Das begründete Urteil wurde am 11. Juni 2015 zugestellt.
Am 10. Juni 2016 hiess das Bundesgericht eine Beschwerde in öffentlich-rechtlichen Angelegenheiten von A._ gut und hob den obergerichtlichen Entscheid wegen Verletzung des rechtlichen Gehörs auf, weil dem Beschwerdeführer nicht Gelegenheit gegeben worden sei, sich vor Urteilsfällung zum Ergebnis des Augenscheins zu äussern (Urteil 1C_374 und 394/2015).
C.
Das Obergericht nahm das Verfahren wieder auf und gab den Parteien Gelegenheit, sich zur Fotodokumentation und zum nachträglich erstellten Augenscheinsprotokoll zu vernehmen. A._ reichte mehrere Luftbilder sowie einen Plan der Näf & Partner AG von der Bestockung zu den Akten. Mit Eingaben vom 24. Februar, 21. April und 19. Mai 2017 beantragte er eine Protokollberichtigung bzw. eine Wiederholung des Augenscheins. Mit Beschluss vom 31. August 2017 entschied das Obergericht, einen neuen Augenschein durchzuführen und hielt fest, das Protokoll des Augenscheins vom 29. Oktober 2014 finde in Bezug auf A._ keine Anwendung.
Am 24. Mai 2018 führte das Obergericht den zweiten Augenschein durch. A._ äusserte sich am 10. August 2018 zum Augenscheinsprotokoll und beantragte, auch das Ergebnis dieses Augenscheins sei (ganz oder zumindest teilweise) aus dem Recht zu weisen.
Mit Schreiben vom 28. September 2018 wurden den Parteien die von Amtes wegen beigezogenen Orthophotos der umstrittenen Bestockung aus den Jahren 1995, 2001, 2007, 2009, 2011 und 2013 zur Kenntnisnahme zugestellt.
Am 29. November 2018 wies das Obergericht die Beschwerde ab. Der begründete Entscheid wurde am 24. Januar 2019 versandt.
D.
Dagegen hat A._ am 22. Februar 2019 Beschwerde in öffentlich-rechtlichen Angelegenheiten erhoben. Er beantragt, der obergerichtliche Entscheid O4V 16 16 sei dahingehend abzuändern, dass in Gutheissung der Beschwerde festgestellt werde, dass es sich beim Gehölz auf den Grundstücken Nrn. 526, 527 und 1461 in Wilen, Walzenhausen, nicht um Wald handle, mit entsprechenden Kostenfolgen zulasten des Kantons. Eventualiter sei der angefochtene Entscheid samt den vorinstanzlichen Entscheiden aufzuheben und die Sache zur Durchführung des Beweisverfahrens und neuer Beurteilung im Sinne der bundesgerichtlichen Erwägungen an das Amt für Raum und Wald, subeventualiter an das Obergericht, zurückzuweisen.
E.
Das Departement und das Obergericht verweisen auf die vorinstanzlichen Entscheide und verzichten - wie auch die Gemeinde Walzenhausen - auf eine Stellungnahme.
Das Bundesamt für Umwelt (BAFU) verweist auf seine Vernehmlassung im ersten bundesgerichtlichen Verfahren, in dem es die Waldfeststellung als bundesrechtskonform erachtet hatte.
Der Beschwerdeführer hat auf eine Replik verzichtet.

Erwägungen:
1.
Angefochten ist ein kantonal letztinstanzlicher Endentscheid des Obergerichts (Art. 86 Abs. 1 lit. d und 90 BGG) betreffend eine Waldfeststellung, d.h. eine öffentlich-rechtliche Angelegenheit (<ref-law>). Dagegen steht grundsätzlich die Beschwerde in öffentlich-rechtlichen Angelegenheiten an das Bundesgericht offen. Der Beschwerdeführer hat am vorinstanzlichen Verfahren teilgenommen und ist als Eigentümer der betroffenen Parzelle Nr. 526 vom angefochtenen Entscheid besonders berührt, womit er zur Beschwerde befugt ist (<ref-law>). Auf die rechtzeitig erhobene Beschwerde ist daher einzutreten.
1.1. Mit der Beschwerde in öffentlich-rechtlichen Angelegenheiten kann insbesondere die Verletzung von Bundesrecht - einschliesslich Überschreitung oder Missbrauch des Ermessens - gerügt werden (<ref-law>). Das Bundesgericht wendet das Bundesrecht grundsätzlich von Amtes wegen an (<ref-law>). Die Verletzung von Grundrechten prüft es dagegen nur insoweit, als eine solche Rüge in der Beschwerde vorgebracht und genügend begründet worden ist (<ref-law>); hierfür gelten qualifizierte Begründungsanforderungen (<ref-ruling> E. 1.4.2 S. 254 mit Hinweisen).
1.2. Das Bundesgericht legt seinem Urteil den Sachverhalt zugrunde, den die Vorinstanz festgestellt hat, sofern dieser nicht offensichtlich unrichtig ist oder auf einer Rechtsverletzung im Sinne von <ref-law> beruht (Art. 105 und Art. 97 Abs. 1 BGG). "Offensichtlich unrichtig" ist gleichbedeutend mit "willkürlich" (<ref-ruling> E. 1.2.2 S. 252). Dabei werden strenge Anforderungen an die Begründungspflicht in der Beschwerde gestellt: Es genügt nicht, einen von den tatsächlichen Feststellungen der Vorinstanz abweichenden Sachverhalt zu behaupten, sondern es ist in der Beschwerdeschrift detailliert darzulegen und möglichst zu belegen, inwiefern diese Feststellungen willkürlich sind (<ref-ruling> E. 1.4.3 S. 255).
2.
Art. 2 des Bundesgesetzes über den Wald vom 4. Oktober 1991 (WaG; SR 921.0) umschreibt den Begriff des Waldes. Danach gilt als Wald jede Fläche, die mit Waldbäumen oder Waldsträuchern bestockt ist und Waldfunktionen erfüllen kann (Abs. 1; zu Sonderfällen vgl. Abs. 2). Waldfunktionen sind vor allem die Schutz-, Wohlfahrts- und Nutzfunktion des Waldes (<ref-law>). Nicht als Wald gelten u.a. isolierte Baum- und Strauchgruppen sowie Hecken (<ref-law>). Innerhalb des vom Bundesrat festgelegten Rahmens können die Kantone bestimmen, ab welcher Breite, welcher Fläche und welchem Alter eine einwachsende Fläche sowie ab welcher Breite und welcher Fläche eine andere Bestockung als Wald gilt (<ref-law>). Diesen Rahmen legte der Bundesrat in Art. 1 Abs. 1 der Verordnung vom 30. November 1992 über den Wald (WaV, SR 921.01) fest. Erfüllt die Bestockung in besonderem Masse Wohlfahrts- oder Schutzfunktionen, so sind die kantonalen Kriterien nicht massgebend (<ref-law> und <ref-law>).
Gemäss Art. 2 des kantonalen Waldgesetzes vom 28. April 1996 (kWaG; bGS 931.1) gilt eine mit Waldbäumen oder -sträuchern bestockte Fläche als Wald, wenn sie mit Einschluss eines zweckmässigen Waldsaumes mindestens eine Ausdehnung von 500 m2 und eine Breite von 12 m aufweist und wenn die Bestockung einwachsender Flächen mindestens 15 Jahre alt ist. (Abs. 2). Das rechtlich geschützte Waldareal umfasst den gesamten Lebensraum des Waldes und schliesst namentlich den Waldsaum ausserhalb der Stammfüsse mit ein (Abs. 3).
Nach der bundesgerichtlichen Rechtsprechung kommt den quantitativen Kriterien wie Fläche, Breite, Länge und Alter eine Hilfsfunktion für den in erster Linie qualitativen Waldbegriff zu, weshalb diese nicht schematisch, ohne Würdigung der Qualität einer Bestockung, gehandhabt werden dürfen. Sind die quantitativen Kriterien erfüllt, ist die Waldqualität - ausserordentliche Verhältnisse vorbehalten - grundsätzlich zu bejahen; hingegen ist der Umkehrschluss nicht zulässig, da auch kleinere Bestockungen unter Umständen den qualitativen Waldbegriff erfüllen können (<ref-ruling> E. 3b S. 79 f.; <ref-ruling> E. 2c S. 445 f.; Urteil 1A.100/2002 vom 10. Oktober 2002 E. 3.2.2, in: ZBGR 85/2004 S. 287; ZBl 106/2005 S. 251; RDAF 2006 I S. 647).
3.
Das Oberforstamt hielt in seiner Waldfeststellungsverfügung fest, dass die Bestockung auf den Parzellen Nrn. 526, 527 und 1461 sowohl die quantitativen als auch die qualitativen Anforderungen von Wald eindeutig erfülle. Dies wurde vom Obergericht bestätigt: Die bestockte Fläche weise typische Waldelemente auf (einheimische Baum- und Straucharten wie Linden, Kirschen, Fichten, Ahorn, Eschen, Weissdorn, Hasel usw., eine intakte einheimische Strauch- und Krautschicht sowie waldtypische Bodenvegetation). Aufgrund der Luftbilder, des technischen Berichts Scherrer und der Erkenntnisse des Augenscheins sei die Mehrheit der Waldbäume über 15 Jahre alt. Die strittige Bestockung weise samt Waldsaum eine Breite von überwiegend mehr als 12 m auf und eine Fläche von knapp über 500 m2. Die Bestockung sei grundsätzlich geeignet, Holz zu erzeugen und erfülle somit Nutzfunktion. Überdies komme ihr eine gewisse Schutzwirkung gegen Hangrutschungen, landschaftsprägender Charakter und eine ökologische Vernetzungsfunktion zu.
Der Beschwerdeführer erhebt verschiedene formelle Rügen (E. 4-5). In der Sache macht er geltend, die strittige Bestockung erfülle weder die quantitativen noch die qualitativen Mindestanforderungen gemäss <ref-law> und <ref-law> in Verbindung mit Art. 2 kWaG. Quantitativ werde die Mindestfläche von 500 m2 nicht erreicht, weil es sich nicht um eine, sondern um zwei getrennte Bestockungen handle (E. 6) und der Waldsaum willkürlich weit festgelegt worden sei (E. 7). Im Übrigen werde auch die Mindestbreite von 12 m nicht überall erfüllt (E. 8). Qualitativ erfüllt die Bestockung keine Waldfunktionen, geschweige denn besondere Schutz- oder Wohlfahrtsfunktion (E. 9). Schliesslich verletze die Waldfeststellung die Eigentumsgarantie (E. 10).
4.
Der Beschwerdeführer beantragte vor Obergericht, dass aufgrund des grossen zeitlichen Abstands zwischen dem Augenschein (Mai 2018) und dem für die Waldfeststellung massgeblichen Feststellungszeitpunkt (Januar 2012) nicht auf die Ergebnisse des Augenscheins abgestellt werden dürfe. Jedenfalls dürften alle Äusserungen und Feststellungen, welche vom 6-jährigen Wachstum der Bestockung besonders stark beeinflusst worden seien (Kronenschluss, qualitativer Charakter der Bestockung, Feststellung des Waldsaums bei den Jalons 2, 4 und 5), nicht verwertet werden.
4.1. Das Obergericht wies diese Verfahrensanträge ab: Diese verletzten Treu und Glauben, weil der Beschwerdeführer selbst die Wiederholung des Augenscheins beantragt und mit Eingabe vom 19. Mai 2017 sogar als zwingend erforderlich erachtet habe. Im Übrigen taugten die Erkenntnisse des Augenscheins vom 24. Mai 2018 in Verbindung mit den relevanten Luftbildern aus den Jahren 1995-2011 und den von der ersten Instanz eingeholten Berichten und Stellungnahmen sehr wohl zum besseren Verständnis des rechtserheblichen Sachverhalts.
4.2. Damit hat das Obergericht die Abweisung der Verfahrensanträge genügend begründet. Diese Begründung ist auch in der Sache nicht zu beanstanden:
4.2.1. Der Beschwerdeführer machte vor Obergericht in mehreren Eingaben geltend, dass es unzumutbar sei, rund zweieinhalb Jahre nach einem Augenschein zum Protokoll Stellung zu nehmen, weshalb zwingend ein neuer Augenschein durchzuführen sei. Dass dieser mehrere Jahre nach dem für die Waldfeststellung massgeblichen Zeitpunkt stattfinden würde, wusste der Beschwerdeführer schon damals. Wenn er dennoch auf der Wiederholung des Augenscheins beharrte, erscheint es widersprüchlich und verletzt den Grundsatz von Treu und Glauben im Prozess, wenn er nunmehr verlangt, auch die Ergebnisse des zweiten Augenscheins aus dem Recht zu weisen, zumal Gehörsverletzungen im Zusammenhang mit dem zweiten Augenschein weder dargetan werden noch ersichtlich sind.
4.2.2. Es erscheint auch nicht von vornherein unmöglich, an einem Augenschein im Jahre 2018 Schlüsse auf die Zustände im Jahr 2012 zu ziehen, sofern allfällige zwischenzeitliche Veränderungen berücksichtigt werden, wobei den Beschwerdeführer (als Eigentümer bzw. Anrainer der fraglichen Parzellen) insoweit eine Mitwirkungspflicht trifft. Dies wird im Folgenden, bei der Überprüfung der Sachverhaltsrügen des Beschwerdeführers, zu berücksichtigen sein.
5.
Auf die weiteren Gehörsrügen des Beschwerdeführers kann mangels genügender Begründung nicht eingetreten werden (<ref-law>) :
5.1. Der Beschwerdeführer rügt, das Obergericht habe die von ihm eingereichten Luftbilder zu Unrecht nicht berücksichtigt, setzt sich jedoch mit der hierfür gegebenen Begründung im angefochtenen Entscheid (E. 5.4.3 S. 13) nicht auseinander.
5.2. Er wirft dem Obergericht vor, nicht auf seine Rüge eingegangen zu sein, wonach der Bericht Scherrer und die Einschätzungen der kantonalen Fachstellen (Natur- und Landschaftsschutz; Oberforstamt) ohne seine Mitwirkung erstellt worden seien, ohne indessen zu substanziieren und mit Aktenhinweisen zu belegen, wann und inwiefern er die Verwertbarkeit dieser Berichte beanstandet hat. Dies liegt auch nicht auf der Hand, enthält doch zumindest die Beschwerdeschrift vom 9. August 2013 keine diesbezüglichen Ausführungen. Es ist nicht Aufgabe des Bundesgerichts, die kantonalen Akten nach allfälligen Rügen zu durchsuchen.
6.
In der Sache macht der Beschwerdeführer geltend, es handle sich nicht um eine Bestockung, sondern um zwei durch eine Sandsteinrippe getrennte Flächen, die je für sich allein die Mindestfläche von 500 m2 nicht erreichten.
6.1. Das Oberforstamt legte in seiner Verfügung dar, dass ein räumlicher und funktionaler Zusammenhang zwischen den Bestockungen oberhalb und unterhalb der Felsrippe (bei Jalon 5) zu bejahen sei, weil ein Kronenschluss der vorhandenen Bäume im ausgewachsenen Zustand möglich und eine zusammenhängende Strauchschicht und Bodenvegetation mit Waldcharakter gegeben sei. Diese Kriterien wurden auch vom Obergericht zugrundegelegt und bejaht.
6.2. Der Beschwerdeführer hält dies für willkürlich. Er macht geltend, nach ständiger bundesgerichtlicher Rechtsprechung seien die tatsächlichen Verhältnisse im Zeitpunkt des erstinstanzlichen Entscheids massgeblich (<ref-ruling> E. 4d S. 92), weshalb auf die Verhältnisse im Juni 2012 abzustellen sei. Der Kronenschluss müsse daher, um einen Wuchszusammenhang zu begründen, bereits im Zeitpunkt der Waldfeststellung vorliegen (mit Verweis auf das Urteil 1A.242/2002 vom 19. November 2003 E. 3.1 und 3.4, in: ZBl 106/2005 S. 255; RDAF 2006 I S. 648); ansonsten könne aufgrund rein hypothetischer Erwägungen immer ein Zusammenhang zwischen verschiedenen Bestockungen konstruiert werden. Dass im Juni 2012 noch kein Kronenschluss vorgelegen habe, sei von der Abteilung Wald und Natur bestätigt worden, habe sie doch in der Waldfeststellungsverfügung darauf abgestellt, dass ein Kronenschluss erst im ausgewachsenen Zustand entstehen werde. Der anlässlich des Augenscheins vom 24. Mai 2018 vom Obergericht festgestellte Kronenschluss dürfe nicht berücksichtigt werden und werde im Übrigen bestritten.
6.3. Zwar trifft es zu, dass nach der bundesgerichtlichen Praxis grundsätzlich auf die tatsächlichen Verhältnisse zum Zeitpunkt der Waldfeststellungsverfügung abzustellen ist (vgl. z.B. <ref-ruling> E. 9b S. 176), wobei allerdings zugunsten des Waldschutzes Ausnahmen möglich sind (vgl. Urteil 1A.30/2004 vom 11. August 2004 E. 2.2.2). Das vom Beschwerdeführer zitierte Urteil 1A.242/2002 E. 3.4 betraf die Altersbestimmung: hierfür sei darauf abzustellen, ob eine Mehrheit der im Zeitpunkt des erstinstanzlichen Entscheids vorhandenen Waldbäume, Baumstrünke und Waldsträucher das notwendige Mindestalter überschritten hatten.
Wie das Obergericht jedoch zutreffend und unter Verweis auf die einschlägige Rechtsprechung dargelegt hat, lässt es die Rechtsprechung für den Wuchszusammenhang genügen, wenn ein Kronenschluss der zum massgeblichen Zeitpunkt über 15-jährigen Bäume im ausgewachsenen Zustand möglich ist und eine durchgängige Strauchschicht oder Bodenvegetation mit Waldcharakter vorhanden ist (vgl. Urteile 1A.30/- 2004 vom 11. August 2004 E. 3.1 und 1A.44/2003 vom 19. August 2003 E. 3.2, in: ZBl 106/2005 S. 110, betr. Kanton Thurgau). Dafür bedarf es einer Prognose über den natürlichen Wuchs der Bäume, welche auf spezifischen Fachkenntnissen beruhen muss und von den Gerichten (wenn auch mit einer gewissen Zurückhaltung) überprüft werden kann (Urteil 1A.30/2004 E. 3.1 mit Hinweisen). Hierzu eignet sich auch ein gerichtlicher Augenschein, der mehrere Jahre nach dem erstinstanzlichen Entscheid durchgeführt wird: Wird - wie vorliegend - konstatiert, dass der Kronenschluss zwischenzeitlich erfolgt ist, so belegt dies die Richtigkeit der ursprünglich getroffenen Prognose.
Vorliegend hat das Obergericht festgestellt, dass sich am Augenschein vom 24. Mai 2018 der bereits aus den Luftbildern erkennbare Sachverhalt bestätigt habe, wonach über die westliche Sandsteinrippe hinweg und damit auch intern durchgehend ein Kronenschluss bestehe. Dabei befasste sich das Obergericht ausführlich mit den Einwänden des Beschwerdeführers und legte dar, weshalb diese unbegründet seien (angefochtener Entscheid S. 13 f.). Diese Erwägungen werden vom Beschwerdeführer nicht substanziiert bestritten und erst recht wird keine Willkür dargelegt.
7.
Der Beschwerdeführer rügt weiter, der Waldsaum sei falsch und willkürlich festgelegt worden. Dabei sei der Waldsaum, der in der Regel 2 m ab Bestockungsgrenze betrage (<ref-ruling> E. 2d S. 77, 274 E. 4c S. 283) mit dem einzigen Zweck ausgedehnt worden, die Minimalfläche von 500 m2 zu erreichen.
7.1. Der Waldsaum i.S.v. Art. 1 Abs. 1 lit. a und b WaV ist bundesrechtlich nicht definiert, weshalb es den Kantonen obliegt, diesen unbestimmten Rechtsbegriff zu konkretisieren (STEFAN M. JAISSLE, Der dynamische Waldbegriff und die Raumplanung: eine Darstellung der Waldgesetzgebung unter raumplanungsrechtlichen Aspekten, Diss. Zürich 1994, S. 67). Der Kanton Appenzell Ausserrhoden hat dies in Art. 1 der kantonalen Waldverordnung vom 9. Dezember 1996 (kWaV; GS 931.11) getan. Danach gehören zum Waldareal auch der lebenswichtige Kronen- und Wurzelraum der Randbäume sowie die Gehölze und die Waldbodenvegetation des Waldsaumes (Abs. 1). Verlaufen ausserhalb der Stammfüsse zum offenen Land hin Grenzen, Wegränder oder andere markante Trennungslinien, können Ausnahmen bewilligt werden (Abs. 2).
Wie das Obergericht hervorgehoben hat, kennt der Kanton Appenzell Ausserrhoden - im Gegensatz zu anderen Kantonen - keine schematische Breite des Waldsaums, sondern der zweckmässige Waldsaum ist stets aufgrund einer Einzelfallbetrachtung festzulegen, anhand der in Art. 1 Abs. 1 kWaV genannten Kriterien.
7.2. Das Obergericht überprüfte die von der Abteilung Wald und Natur vorgenommene Verpflockung, namentlich die vom Beschwerdeführer kritisierten Jalons 1, 2, 4, 5, 6 und 8. Es konstatierte, dass sämtliche Jalons innerhalb der durch den Bericht Scherrer und die Luftbilder ausgewiesenen bestockten Flächen liegen, was für die Rechtmässigkeit der Abgrenzung spreche. Sodann begründete es im einzelnen, weshalb der Abteilung Wald und Natur bei der Verpflockung keine Ermessensüberschreitung vorgeworfen werden könne, sei es weil die Kriterien gemäss Art. 1 Abs. 1 kWaV erfüllt seien, sei es, weil es ausnahmsweise gemäss Art. 1 Abs. 2 kWaV zulässig sei, auf die Parzellengrenze abzustellen.
Der Beschwerdeführer setzt sich mit diesen Erwägungen nicht auseinander und legt (mit Ausnahme von Jalon 2) nicht dar, inwiefern sie auf einer unhaltbaren Sachverhaltsfeststellung beruhen. Näher zu prüfen ist daher nur der Standort von Jalon 2.
7.3. Der Beschwerdeführer macht geltend, dieser Jalon stehe nahe einem Haselstrauch. Er bestreitet, dass dieser älter als 20 Jahre sei, habe der Oberförster doch am Augenschein explizit festgehalten, dass die Schätzung des Alters nicht möglich sei. Auch der Waldsaum sei seit dem Jahr 2012 gewachsen und könne daher nicht mehr überprüft werden.
Gemäss Protokoll sagte der Oberförster jedoch am Augenschein lediglich, dass eine exakte Altersschätzung nicht möglich sei; aufgrund der Menge Ruten, der Höhe, der Fülle der Blattmasse, der Dicke der Stämme, der verborkten Rinde und der massigen Dimensionen gehe er davon aus, dass der Haselstrauch über 20 Jahre alt sei. Der Beschwerdeführer legt weder dar, weshalb auf diese Schätzung nicht abgestellt werden dürfe, noch befasst er sich mit den vom Obergericht genannten weiteren Elementen, insbesondere den Erkenntnissen des Berichts Scherrer.
7.4. Soweit der Beschwerdeführer die Waldqualität des "Spitzes" von 35 m2 auf Parzelle Nr. 1461 mit dem blossen Hinweis auf dessen angebliche "Heckenqualität" bestreitet, ohne darzulegen, inwiefern insoweit eine offensichtlich unrichtige Sachverhaltsfeststellung vorliegt oder Bundesrecht falsch angewendet wurde, kann darauf nicht eingetreten werden. Gleiches gilt für die pauschale Rüge, auf der gesamten Fläche habe zum massgeblichen Zeitpunkt keine 15-jährige Bestockung vorgelegen.
Soweit er auf die unbestockte Felswand und "weitere isolierte Bau- und Strauchgruppen" verweist, kann auf die Ausführungen zum Wuchszusammenhang oberhalb und unterhalb der Felswand verwiesen werden (oben E. 6).
8.
Der Beschwerdeführer rügt weiter, die Mindestbreite von 12 m gemäss Art. 2 Abs. 2 kWaG sei nicht überall erfüllt. Die nach Südwesten auslaufende Bestockung weise eine Breite von nur 7.5 m auf. Bei einer Durchschnittsberechnung (<ref-ruling> E. 4c S. 283) komme man bei einer Länge von 46.5 m und einer Gesamtfläche von 536 m2 auf eine durchschnittliche Breite von nur 11.5 m. Im Übrigen mache eine Durchschnittsberechnung nur Sinn, wenn die Mindestbreite auf der gesamten Länge +/- 12 m betrage, was aber vorliegend nicht der Fall sei: Rund die Hälfte der Länge der ausgeschiedenen "Waldfläche" unterschreite die Breite von 12 m deutlich.
8.1. Das Obergericht ging dagegen mit den Vorinstanzen davon aus, dass die notwendige Mindestbreite erreicht werde, weil die Bestockung überwiegend eine Breite von 12 m und mehr aufweise und die schmälere, südwestlich auslaufende Bestockung mit der übrigen, breiteren Bestockung eine Einheit bilde (Kronenschluss; zusammenhängende waldtypische Bodenvegetation; vgl. dazu oben E. 6), die bei gesamtheitlicher Betrachtung Waldfunktionen erfülle (vgl. dazu näher unten E. 9).
8.2. Dies ist aus Sicht des Bundesrechts nicht zu beanstanden: Nach der bundesgerichtlichen Praxis ist in Sonderfällen, in denen weder das Bundesrecht noch das kantonale Recht vorschreibt, mit welcher Methode die Mindestbreite einer Bestockung zu bestimmen ist, eine Gesamtbetrachtung vorzunehmen, unter Würdigung aller qualitativen und quantitativen Aspekte (vgl. <ref-ruling> E. 4b S. 282 f. mit Hinweisen). So stellte das Bundesgericht im Fall einer langezogenen Bestockung, die an den Enden am breitesten und in der Mitte am schmalsten war, auf eine Durchschnittsbetrachtung ab und betonte den ununterbrochenen Wuchszusammenhang (E. 4c S. 283). Mindestens einreihig bestockte "Waldzungen" von weniger als 12 m Breite wurden als Wald qualifiziert, weil sie einen räumlichen und funktionalen Zusammenhang mit dem angrenzenden Wald aufwiesen (Wuchszusammenhang) und ihnen jedenfalls Nutzfunktion zukam (Urteile 1A.44/2003 (vom 19. August 2003 E. 3.2 und 3.3, ZBl 106/2005 S. 110 und 1A.30/2004 vom 11. August 2004 E. 3 und 4).
Vorliegend besteht die streitige Bestockung aus einer grösseren Bestockung in Nordosten und einer schmalen Bestockung im Südwesten. Die nördliche Bestockung, die rund zwei Drittel der Fläche ausmacht, ist deutlich breiter als 12 m. Beide Bestockungen treten nach den Feststellungen der Vorinstanzen als Einheit in Erscheinung (Kronenschluss der Bäume im ausgewachsenen Zustand, zusammenhängende Strauchschicht, Bodenvegetation mit Waldcharakter; vgl. oben E. 6). Insofern durften die Vorinstanzen bei einer Gesamtbetrachtung davon ausgehen, dass die Bestockung überwiegend die Mindestbreite von 12 m einhält und die quantitativen Kriterien erfüllt (zu den qualitativen vgl. sogleich E. 9). Dies belegt übrigens auch die vom Beschwerdeführer angestellte Durchschnittsberechnung, die eine Breite von knapp 12 m ergibt.
9.
<ref-law> verlangt, dass die mit Waldbäumen oder -sträuchern bestockte Fläche Waldfunktionen erfüllen kann, wobei es nach der Rechtsprechung bereits genügt, wenn eine von mehreren Funktionen erfüllt wird (Urteil 1A.30/2004 vom 11. August 2004 E. 4; JAISSLE, a.a.O., S. 68).
9.1. Das Oberforstamt legte in seiner Waldfeststellungsverfügung ausführlich dar, dass die streitige Bestockung Wohlfahrts-, Schutz- und Nutzfunktion erfülle: Gestützt auf die Stellungnahme der Fachstelle für Natur- und Landschaftsschutz vom 8. Mai 2012 und die eigene Einschätzung hielt es fest, das Gehölz auf einer Felsrippe sei stark landschaftsprägend und bilde einen ökologisch wertvollen Trittstein, namentlich für trockene und wärmeliebende Gehölze, Insekten und Reptilien, weshalb ihm in besonderem Masse Wohlfahrtsfunktion zukomme. Zudem erfülle der Wald Schutzfunktion, befinde sich doch im fraglichen Gebiet gemäss der Gefahrenhinweiskarte ein Anrissgebiet für Rutschungen. Die FS Geotechnik AG, St. Gallen, habe in ihrer Beurteilung vom 10. Mai 2012 bestätigt, dass die Bestockung einen positiven Einfluss auf die Stabilität der anstehenden Sandsteinschicht habe (Durchwurzelung des Lockergesteins, Schutz des Felsgefüges vor Verwitterung). Auch wenn keine ausgeprägte Naturgefahr bestehe, könne zumindest von einer potenziellen Schutzwirkung des Waldes gesprochen werden. Schliesslich seien die auf der bestockten Fläche vorhandenen Baumarten aus forstlicher Sicht zur Erzeugung von Stammholz sowie Energie- und Brennholz geeignet, weshalb die Nutzfunktion eindeutig gegeben sei.
9.2. Dies wurde vom Obergericht in seinem Entscheid aufgrund der Akten und den Eindrücken des Augenscheins bestätigt. Der Beschwerdeführer habe an der Anhörung vom 2. Mai 2012 selbst eingeräumt, die vorhandenen Fichten 1978 für den späteren Bezug von Holz gepflanzt zu haben. Die Nutzungsfunktion sei auch am Augenschein durch einzelne Baumstrünke bestätigt worden. Die bestockte Fläche sei grundsätzlich geeignet, eine Schutzwirkung gegen Hangrutschungen auszuüben, zumal sie sich im Perimeter einer Gefahrenhinweiskarte befinde. Zudem werde die Sandsteinrippe durch den jahrzehntelangen Blattwurf vor Verwitterung geschützt, was helfe, Steinschläge zu vermeiden. Es bestehe auch kein Anlass, die Einschätzung der kantonalen Fachstelle für Natur- und Landschaftsschutz vom 9. Mai 2012 zum landschaftsprägenden Charakter und zur ökologischen Vernetzungsfunktion der Bestockung in Frage zu stellen, die aufgrund der Eindrücke am Augenschein plausibel erschienen. Damit liege es auf der Hand, dass die strittige Bestockung mehrere Waldfunktionen erfüllen könne bzw. erfülle. Ob sie dies in besonderem Masse tue, könne offenbleiben, weil auch die quantitativen Waldkriterien erfüllt seien.
9.3. Der Beschwerdeführer bestreitet zunächst die Nutzfunktion der Bestockung, weil die Bestockung nie für die Holzproduktion bzw. -versorgung genutzt worden sei und eine nachhaltige Nutzung zu diesem Zweck aufgrund der geringen Fläche auch nicht sinnvoll wäre. Dem ist entgegen zu halten, dass es für die Nutzfunktion ausreicht, dass die vorhandenen Bäume für die Holznutzung geeignet sind, unabhängig davon, ob das Holz regelmässig, in kurzen oder längeren Abständen, oder überhaupt nicht genutzt worden ist (Urteil 1A.44/2003 vom 19. August 2003, in: ZBl 106/2005 S. 110 E. 3.4.1 mit Hinweis; JAISSLE, a.a.O., S. 69). Entgegen dem Einwand des Beschwerdeführers trifft dies nicht auf sämtliche Bestockungen zu, da <ref-law> neben Bäumen auch Waldsträucher umfasst.
9.4. Der Beschwerdeführer bestreitet sodann die Schutzwirkung der Bestockung gegen Hangrutschungen und Steinschlag, weil sie flächenmässig zu klein sei, um eine besondere Schutzfunktion zu erfüllen (mit Verweis auf Urteil 1A.51/2006 vom 8. August 2006 E. 5.1). Anders als im zitierten Entscheid, wo die quantitativen Waldkriterien nicht erfüllt waren, bedarf es jedoch vorliegend keiner besonders ausgeprägten Schutzfunktion. Es genügt daher, dass die Bestockung zur Stabilität des steilen und aufgrund seiner geologischen Zusammensetzung für Lockergesteinsrutschungen und Steinschlag anfälligen Geländes beiträgt.
9.5. Zu den Wohlfahrtsfunktionen gehört insbesondere auch der Landschaftsschutz, das heisst die optisch-ästhetische Funktion der Bestockung und ihre biologische Bedeutung als Lebensraum für Fauna und Flora (<ref-ruling> E. 3d S. 88 mit Hinweis). Zwar ist dem Beschwerdeführer zuzustimmen, dass nicht schon die jeder Baumgruppe im überbauten Gebiet zukommende Wohlfahrtswirkung genügt (Urteil 1A.22/2001 vom 22. August 2001, E. 6b, in: URP 2009 S. 251). Vorliegend wurde der Bestockung jedoch eine darüber hinausgehende ökologische Funktion von der zuständigen Fachstelle zugesprochen, insbesondere als ökologischer Trittstein für die Vernetzung der Lebensräume von Insekten und Reptilien. Solchen Trittsteinen kommt angesichts des Artenschwunds und den immer stärker fragmentierten Lebensräumen der Schweiz verstärkte Bedeutung zu (vgl. Umwelt Schweiz 2018, Bericht des Bundesrates, S. 97 ff.). Eine Wohlfahrtsfunktion kann der streitigen Bestockung daher nicht abgesprochen werden; ob es sich um eine "besondere" Wohlfahrtsfunktion handelt, braucht vorliegend nicht geprüft zu werden.
10.
Schliesslich rügt der Beschwerdeführer eine Verletzung der Eigentumsgarantie (<ref-law>).
Soweit er die gesetzlichen Voraussetzungen für die Ausscheidung von Wald auf seiner Parzelle bestreitet, kann auf die vorstehenden Erwägungen verwiesen werden.
Im Übrigen macht er geltend, sein privates Interesse an der Überbauung seines Grundstücks, ohne Einhaltung eines Waldabstands, überwiege das öffentliche Interesse an der Waldfeststellung. Nach ständiger Rechtsprechung ist jedoch eine Abwägung mit den berührten privaten Interessen im Waldfeststellungsverfahren ausgeschlossen (<ref-ruling> E. 3e S. 89; <ref-ruling> E. 2b S. 279; Urteil 1C_307/2009 vom 16. Februar 2010 E. 5, in: Pra 2010 Nr. 138 S. 906; je mit Hinweisen); diese können allenfalls in einem nachfolgenden Verfahren (z.B. Rodungsverfahren, Ausnahmebewilligung für die Unterschreitung des Waldabstands) berücksichtigt werden.
11.
Die Beschwerde ist daher abzuweisen, soweit darauf einzutreten ist. Ausgangsgemäss trägt der Beschwerdeführer die Gerichtskosten und hat keinen Anspruch auf eine Parteientschädigung (Art. 66 und 68 BGG).

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird abgewiesen, soweit darauf einzutreten ist.
2.
Die Gerichtskosten von Fr. 4'000.-- werden dem Beschwerdeführer auferlegt.
3.
Es werden keine Parteientschädigungen zugesprochen.
4.
Dieses Urteil wird dem Beschwerdeführer, der Einwohnergemeinde Walzenhausen, dem Departement Bau und Volkswirtschaft des Kantons Appenzell Ausserrhoden, dem Amt für Raum und Wald des Kantons Appenzell Ausserrhoden, Abteilung Wald und Natur, dem Obergericht des Kantons Appenzell Ausserrhoden, 4. Abteilung, und dem Bundesamt für Umwelt schriftlich mitgeteilt.
Lausanne, 19. Juli 2019
Im Namen der I. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Chaix
Die Gerichtsschreiberin: Gerber